💻 computer science

Witness-split + window-cardinality refinement for $r_3(N)$ : Architecture, empirical results, and a structural hard pocket

Questo articolo presenta un framework computazionale riproducibile che combina il witness-splitting, il window-cardinality pruning e solver ibridi SAT/MIP per investigare rigorosamente il limite superiore di $r_3(212)$ , eliminando con successo la maggior parte dei candidati 44-set e isolando due casi strutturali resistenti che rimangono non provati nonostante estesi sforzi di verifica.

Autori originali: Mehmet Ergezer

Pubblicato 2026-06-04

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Mehmet Ergezer

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immagina di dover preparare una valigia (con i numeri da 1 a 212) con il maggior numero possibile di oggetti, ma con una regola ferrea: non puoi scegliere tre oggetti che formino un modello aritmetico perfetto.

Per esempio, se scegli il numero 2, non puoi scegliere anche il 4 e il 6, perché 2, 4, 6 è un modello in cui ogni numero è maggiore del precedente di 2 unità. Questo è chiamato "progressione aritmetica a 3 termini".

I matematici stanno cercando di capire il numero assoluto massimo di oggetti che puoi inserire in questa valigia senza infrangere la regola: per una valigia di dimensione 211, la risposta nota è 43. La grande domanda di questo articolo è: si possono inserire 44 oggetti in una valigia di dimensione 212?

L'autore, Mehmet Ergezer, non ha tirato a indovinare; ha costruito una massiccia fabbrica digitale per cercare di dimostrare che 44 è impossibile. Ecco come si articola l'articolo, utilizzando analogie semplici:

1. La Strategia: La Fabbrica del "Witness Split"

Cercare di controllare ogni possibile combinazione di 4 incastro di 44 numeri su 212 è come cercare di trovare un granello di sabbia specifico su tutte le spiagge della Terra. È troppo grande per essere gestito da un singolo computer.

Così, l'autore ha usato un trucco astuto:

Il Testimone (The Witness): È partito da una lista "sicura" nota di 43 numeri che già funziona.
La Divisione (The Split): Ha preso i 24 numeri più "importanti" da quella lista sicura e ha chiesto al computer di controllare ogni possibile scenario "Sì/No" per essi.
Il Risultato: Questo ha frammentato l'impossibile montagna di dati in 12,5 milioni di piccoli cumuli gestibili (chiamati "chunk"). Il computer ha poi cercato di risolvere ogni cumulo uno alla volta.

2. Gli Strumenti: La "Finestra" e il "Raffinamento"

Per rendere il computer più veloce, l'autore ha aggiunto due strumenti speciali:

La Carta Finestra (Il Potatore): Immagina di guardare attraverso una finestra una piccola sezione della valigia. Sappiamo già da precedenti studi matematici che una piccola finestra di dimensione 50 può contenere, ad esempio, solo 10 elementi. Il computer usa questa regola per scartare istantaneamente qualsiasi cumulo che tenti di inserire 11 elementi in quella finestra. Questo è stato lo strumento più potente, riducendo il numero di cumuli difficili di quasi il 30%.
Il Raffinamento (L'Approfondimento): Se un cumulo era troppo difficile da risolvere in 60 secondi, il computer non si arrendeva. Prendeva quel particolare cumulo difficile, aggiungeva più regole e riprovava con un limite di tempo più lungo. È come prendere una scatola chiusa, scegliere una serratura specifica e riprovare con una chiave più grande.

3. I Risultati: La "Borsa Difficile"

Dopo aver eseguito milioni di questi controlli su un cluster di supercomputer, ecco cosa è successo:

Zero Successi: Il computer non ha mai trovato un singolo modo valido per inserire 44 oggetti. Ogni volta che ci provava, sbatteva contro un muro e diceva: "Impossibile".
L'Evidenza: Questa è una forte evidenza che 44 sia impossibile, ma non è ancora una dimostrazione formale. Perché? Perché ci sono ancora alcuni cumuli ostinati che il computer non è riuscito a finire in tempo.

La "Borsa Difficile" (I Chunk Resistenti):
Tra i milioni di cumuli, l'autore ha trovato un piccolo e ostinato gruppo di 45 cumuli che si sono rifiutati di risolversi anche dopo essere stati dotati di tempo extra e strumenti diversi.

L'Attacco LP: Hanno provato un altro tipo di risolutore matematico (chiamato HiGHS) che guarda al problema come a una curva fluida. È fallito nel risolvere nessuno dei 45 cumuli.
L'Attacco CDCL: Hanno provato un terzo tipo di risolutore (chiamato CDCL) che lavora come un detective, imparando dai propri errori. Questo è stato efficace! Ha risolto 18 dei 45 cumuli.
I 2 Finali: Tuttavia, 2 cumuli (etichettati come T1c) sono rimasti completamente irrisolti. Hanno resistito al primo risolutore, al secondo risolutore e al terzo risolutore. Sono il "boss finale" di questo problema.

4. La Conclusione: Il "Gap dell'Unità"

L'articolo conclude che:

Abbiamo una lista verificata di 43 numeri che funziona.
Abbiamo una forte evidenza che 44 sia impossibile, perché il computer ha provato milioni di volte ed è fallito.
Tuttavia, a causa di quei 2 ultimi cumuli ostinati, non abbiamo ancora una dimostrazione matematica al 100%. La risposta è quasi certamente 43, ma il "gap" tra 43 e 44 è tecnicamente ancora aperto.

5. Il Dono alla Comunità

Inve di dire semplicemente "Mi arrendo", l'autore sta rilasciando tutti i dati. Sta consegnando i 2 cumuli ostinati al mondo come una sfida.

Fornisce il codice e i dati esatti in modo che altri matematici possano provare a risolvere solo quei due cumuli.
Ha persino tradotto il problema in un linguaggio per sistemi di prova formale (Lean), invitando gli scienziati informatici a provare a dimostrarlo usando motori logici.

In breve: L'autore ha costruito una massiccia macchina digitale che ha cercato di infrangere il record di inserimento di numeri senza modelli. La macchina non è riuscita a trovare un modo per infrangere il record, ma si è incagliata su due piccoli e incredibilmente difficili puzzle. L'articolo dice: "Siamo sicuri al 99,9% che la risposta sia 43, ma ecco i due puzzle finali che dovete risolvere per dimostrarlo".

Sintesi Tecnica: Raffinamento Witness-Split + Window-Cardinality per $r_3(212)$

Enunciato del Problema
Il documento affronta il calcolo esatto di $r_3(N)$ , definito come la dimensione massima di un sottoinsieme di $[1, N]$ che non contenga progressioni aritmetiche a tre termini (3-AP) non triviali. Mentre il comportamento asintotico è ben studiato (ad esempio, il teorema di Roth, Kelley–Meka), l'attenzione qui è rivolta alla frontiera finita per $N=212$ . In base a OEIS A003002, $r_3(211) = 43$ . Gli autori indagano il problema decisionale: Esiste un sottoinsieme di 44 elementi privo di 3-AP in $[1, 212]$ ?
Gli autori hanno verificato indipendentemente un testimone (witness) di 43 elementi, stabilendo che $r_3(212) \ge 43$ . La domanda sul limite superiore è se $r_3(212) \le 43$ . Una condizione necessaria per qualsiasi ipotetico insieme di 44 elementi è che esso debba contenere entrambi gli estremi, 1 e 212; altrimenti, si tradurrebbe in un insieme di 44 elementi in $[1, 211]$ , contraddicendo il valore noto. Pertanto, il problema si riduce a dimostrare l'infeasibilità di un insieme di 44 elementi contenente $\{1, 212\}$ .

Metodologia e Architettura
Gli autori propongono un framework computazionale riproducibile che combina cinque componenti per cercare un insieme di 44 elementi fattibile:

Modello CP-SAT in Forma Decisionale: Il problema è codificato utilizzando variabili booleane $x_i$ per $i \in [1, 212]$ . I vincoli includono:
- Disuguaglianze 3-AP: $x_a + x_b + x_c \le 2$ per tutte le terne $(a, b, c)$ che formano una AP.
- Uguaglianza di cardinalità: $\sum x_i = 44$ (più stringente per la propagazione rispetto alla disuguaglianza).
- Forzatura degli estremi: $x_1 = x_{212} = 1$ .
- Rottura della simmetria: ordinamento lessicografico per eliminare la simmetria di riflessione.
Witness-Splitting (Suddivisione del Testimone): Per gestire lo spazio di ricerca, gli autori utilizzano un testimone verificato di 43 elementi $A_{43}$ . Classificano gli elementi di $A_{43}$ in base al grado di incidenza nelle AP e selezionano i primi 24. Lo spazio di ricerca viene suddiviso in $2^{24}$ "pezzi" (chunks) fissando i valori di queste 24 variabili. Molti pezzi vengono eliminati immediatamente se il prefisso fissato forza una 3-AP.
Pruning della Cardinalità di Finestra (Window-Cardinality Pruning): Un intervento critico consiste nell'aggiunta di disuguaglianze valide derivate da OEIS A003002. Per ogni finestra $[a, a+L-1]$ , la somma delle variabili è limitata da $r_3(L)$ . Con $N=212$ , ciò aggiunge 22.154 disuguaglianze, rafforzando significativamente il modello oltre i semplici vincoli 3-AP.
Raffinamento Ricorsivo: I pezzi che restituiscono UNKNOWN allo stadio generale (profondità 24) vengono raffinati estendendo il prefisso fissato con le variabili del testimone a grado più alto successivo (profondità 40, 48, 56, 64) e risolvendo nuovamente con limiti temporali più lunghi.
Diversità dei Solver e Ingegneria: La campagna utilizza una pipeline basata su SLURM sulla classe di calcolo UMass Unity. Impiega:
- CP-SAT (OR-Tools): Per il passaggio generale e il raffinamento ricorsivo.
- HiGHS (MIP): Un solver basato sulla rilassazione LP, utilizzato per attaccare i pezzi "UNKNOWN" più difficili.
- CDCL/SAT (CaDiCaL): Utilizzato per ri-attaccare i pezzi resistenti ai metodi LP, generando prove DRAT per l'insoddisfacibilità.

Risultati Empirici
La campagna ha elaborato milioni di sottoproblemi attraverso lo sweep a profondità 24 e vari livelli di raffinamento.

Zero Soluzioni Fattibili: In tutti i sottoproblemi testati (passaggio generale, raffinamenti, HiGHS e CDCL), sono stati trovati zero insiemi di 44 elementi. Ciò fornisce un forte supporto empirico per $r_3(212) = 43$ , sebbene non costituisca una prova formale.
Impatto della Cardinalità di Finestra: L'abilitazione delle disuguaglianze di cardinalità di finestra ha ridotto il tasso di UNKNOWN nei passaggi generali di circa 28 punti percentuali (ad esempio, da ~30% a ~1,65% in lotti controllati), rendendola lo strato di pruning più efficace.
La "Hard Pocket" Strutturale:
- Da un lotto di espansione di 100.000 pezzi, 6.071 pezzi hanno restituito UNKNOWN.
- Un riepilogo di 300 secondi su un campione casuale di questi ha lasciato 45 pezzi resistenti (Tier T1).
- Attacco HiGHS: Un'esecuzione di un'ora con HiGHS ha chiuso 0/45. Un audit di 8 ore ha chiuso 25/45, lasciando 20 pezzi (Tier T1b) con i limiti duali bloccati a 0.0, indicando che la rilassazione LP non forniva alcun certificato di infeasibilità.
- Attacco CDCL: Un attacco puro CDCL/SAT sui 20 pezzi T1b ha chiuso 18/20, generando prove DRAT indipendentemente verificate.
- Il Residuo (T1c): Due pezzi (ID 40959 e 48895) sono rimasti UNKNOWN anche dopo esecuzioni pure CDCL di 12 ore e diagnostica CDCL con finestre di 4 ore. Questi due pezzi resistono ai paradigmi CP-SAT, HiGHS (LP-MIP) e CDCL.

Contributi Chiave
Il documento inquadra esplicitamente il proprio contributo come metodologico piuttosto che come un nuovo valore esatto per $r_3(212)$ . I contributi specifici sono:

Architettura: Un framework riproducibile che combina witness-splitting, pruning della cardinalità di finestra e raffinamento ricorsivo per ricerche di limiti superiori esatti.
Resoconto Empirico: Un'analisi dettagliata della campagna $N=212, K=44$ , inclusi i trade-off tra i solver e la non uniformità dello spazio di ricerca (ad esempio, i pezzi "middle-out" con assegnazioni di pin specifiche sono significativamente più difficili).
Caratterizzazione della Hard Pocket: Identificazione di un'ostruzione strutturale (T1c) che è invariante attraverso i paradigmi CP-SAT, HiGHS e CDCL sotto generosi limiti temporali.
Rilascio di Benchmark: Un rilascio a livelli degli istanze:
- T1a: 25 pezzi chiusi da HiGHS.
- T1b \ T1c: 18 pezzi chiusi da CDCL con prove DRAT.
- T1c: I due pezzi resistenti finali, inquadrati come il problema aperto più acuto.
- T2/T3: I 6.071 UNKNOWN generali e il generatore completo di 12,5 milioni di pezzi per tentativi futuri.
Formalizzazione: Una codifica in Lean 4 dei target T1c per sistemi di ricerca di prove formali.

Significatività e Rivendicazioni
Gli autori affermano con modestia che, sebbene la campagna supporti fortemente la congettura $r_3(212) = 43$ , essa non costituisce una prova formale a causa del residuo T1c non risolto. La significatività risiede nell'isolare la barriera computazionale specifica:

Il divario tra i limiti certificati è esattamente uno ( $43 \le r_3(212) \le 44$ ).
Il fallimento dei metodi basati su LP (HiGHS) e il successo parziale di CDCL suggeriscono che la difficoltà non è solo un artefatto di propagazione, ma una proprietà strutturale dove il gap della rilassazione LP è stretto e il certificato di infeasibilità intera è combinatoriamente diffuso.
Il lavoro postula che chiudere il divario richieda o limiti additivo-combinatori più forti (ad esempio, analisi di Fourier o limiti di partizione multi-finestra) o sistemi di branch-and-bound personalizzati che sfruttino simmetrie specifiche del problema non catturate dai solver general-purpose.

L'opera funge da benchmark per la comunità, offrendo istanze specifiche e verificate (T1c) che rappresentano l'attuale limite dei solver di ottimizzazione combinatoria general-purpose per questa classe di problemi.