💻 computer science

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

Dit artikel presenteert een reproduceerbaar computationeel framework dat witness-splitting, window-cardinality pruning en hybride SAT/MIP-solvers combineert om de bovengrens van $r_3(212)$ rigoureus te onderzoeken, waarbij succesvol de meeste kandidaat 44-sets zijn geëlimineerd terwijl twee resistente structurele gevallen zijn geïsoleerd die onbewezen blijven ondanks uitgebreide verificatiepogingen.

Oorspronkelijke auteurs: Mehmet Ergezer

Gepubliceerd 2026-06-04

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Mehmet Ergezer

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een koffer probeert te pakken (met de getallen van 1 tot 212) met zoveel mogelijk items, maar met één strikte regel: Je mag niet drie items kiezen die een perfect rekenkundig patroon vormen.

Bijvoorbeeld, als je het getal 2 kiest, mag je ook niet 4 en 6 kiezen, want 2, 4, 6 is een patroon waarbij elk getal 2 groter is dan het vorige. Dit wordt een "3-term rekenkundige progressie" genoemd.

Wiskundigen proberen al een tijdje uit te vinden wat het absolute maximum aantal items is dat je in deze koffer kunt passen zonder de regel te breken. Voor een koffer van grootte 211 is het antwoord bekend als 43. De grote vraag voor dit artikel is: Kun je 44 items in een koffer van grootte 212 passen?

De auteur, Mehmet Ergezer, heeft niet zomaar geraden; hij heeft een enorme digitale fabriek gebouwd om te proberen te bewijzen dat 44 onmogelijk is. Hier is hoe het artikel uiteenvalt, met behulp van eenvoudige analogieën:

1. De Strategie: De "Witness Split" Fabriek

Proberen elke mogelijke combinatie van 44 getallen uit 212 te controleren, is alsof je probeert een specifiek zandkorreltje te vinden op elk strand op aarde. Het is te groot voor één computer om te verwerken.

Daarom gebruikte de auteur een slimme truc:

De Getuige (The Witness): Hij begon met een bekende "veilige" lijst van 43 getallen die al werkt.
De Splitsing (The Split): Hij nam de 24 meest "belangrijke" getallen uit die veilige lijst en vroeg de computer om elk mogelijk "Ja/Nee"-scenario voor deze getallen te controleren.
Het Resultaat: Dit brak de onmogelijke berg data op in 12,5 miljoen kleinere, hanteerbare stapels (genaamd "chunks"). De computer probeerde vervolgens elke stapel één voor één op te lossen.

2. De Instrumenten: Het "Venster" en de "Verfijning"

Om de computer sneller te maken, voegde de auteur twee speciale hulpmidders toe:

De Vensterkaart (De Snoeier - The Window Card): Stel je voor dat je door een raam naar een klein deel van de koffer kijkt. We weten al van eerdere wiskunde dat een klein venster van grootte 50 bijvoorbeeld slechts 10 items kan bevatten. De computer gebruikt deze regel om direct elke stapel weg te gooien die probeert 11 items in dat venster te plaatsen. Dit was het meest krachtige instrument, waarmee het aantal moeilijke stapels met bijna 30% werd verminderd.
De Verfijning (De Diepe Duik - The Refinement): Als een stapel te moeilijk was om binnen 60 seconden op te lossen, gaf de computer niet op. Hij nam die specifieke moeilijke stapel, voegde meer regels toe en probeerde het opnieuw met een langere tijdslimiet. Dit is als het nemen van een slot, het kiezen van een specifiek slot, en het opnieuw proberen met een grotere sleutel.

3. De Resultaten: De "Hard Pocket"

Na het draaien van miljoenen van deze controles op een supercomputercluster, is dit wat er gebeurde:

Nul Succes: De computer vond nooit een enkele geldige manier om 44 items te verpakken. Elke keer als hij het probeerde, liep hij tegen een muur aan en zei: "Onmogelijk."
Het Bewijs: Dit is sterk bewijs dat 44 onmogelijk is, maar het is nog geen formeel bewijs. Waarom? Omdat er nog steeds een paar hardnekkige stapels zijn die de computer niet op tijd kon voltooien.

De "Hard Pocket" (De Weerstandbiedende Chunks):
Uit de miljoenen stapels vond de auteur een kleine, hardnekkige groep van 45 stapels die zelfs na extra tijd en andere hulpmiddelen weigerden op te lossen.

De LP Aanval: Ze probeerden een ander type wiskundige solver (genaamd HiGHS) die naar het probleem kijkt als een vloeiende curve. Dit slaagde er niet in om een van de 45 stapels op te lossen.
De CDCL Aanval: Ze probeerden een derde type solver (genaamd CDCL) die werkt als een detective en leert van zijn fouten. Deze was succesvol! Het loste 18 van de 45 stapels op.
De Laatste 2: Echter, 2 stapels (gelabeld T1c) bleven volledig onopgelost. Ze weerstonden de eerste solver, de tweede solver én de derde solver. Zij zijn de "eindbaas" van dit probleem.

4. De Conclusie: De "Unit Gap"

Het artikel concludeert dat:

We hebben een geverifieerde lijst van 43 getallen die werkt.
We hebben sterk bewijs dat 44 onmogelijk is, omdat de computer miljoenen keren heeft geprobeerd en heeft gefaald.
Echter, vanwege die 2 laatste hardnekkige stapels, hebben we nog geen 100% wiskundig bewijs. Het antwoord is bijna zeker 43, maar de "kloof" tussen 43 en 44 is technisch gezien nog steeds open.

5. Het Cadeau aan de Gemeenschap

In plaats van alleen maar te zeggen "Ik geef het op", geeft de auteur alle data vrij. Hij legt de 2 hardnekkige stapels voor als een uitdaging aan de wereld.

Hij biedt de exacte code en data aan, zodat andere wiskundigen alleen die twee specifieke stapels kunnen proberen op te lossen.
Hij heeft het probleem zelfs vertaald naar een taal voor formele bewijssystemen (Lean), en nodigt computerwetenschappers uit om het met behulp van logische engines te bewijzen.

Kortom: De auteur bouwde een enorme digitale machine die probeerde het record te verbreken voor het verpakken van getallen zonder patronen. De machine slaagde er niet in om een manier te vinden om het record te breken, maar liep vast op twee kleine, ongelooflijk moeilijke puzzels. Het artikel zegt: "We zijn voor 99,9% zeker dat het antwoord 43 is, maar hier zijn de twee laatste puzzels die je moet oplossen om het te bewijzen."

Technische Samenvatting: Witness-Splitting + Window-Cardinality Verfijning voor $r_3(212)$

Probleemstelling
Het artikel behandelt de exacte berekening van $r_3(N)$ , gedefinieerd als de maximale grootte van een deelverzameling van $[1, N]$ die geen niet-triviale drie-termige rekenkundige progressie (3-AP) bevat. Terwijl het asymptotische gedrag goed bestudeerd is (bijv. Roths stelling, Kelley–Meka), ligt de focus hier op de eindige grens bij $N=212$ . Op basis van OEIS A003002 is $r_3(211) = 43$ . De auteurs onderzoeken het beslissingsprobleem: Bestaat er een 44-elementen 3-AP-vrije deelverzameling van $[1, 212]$ ?
De auteurs hebben onafhankelijk een 43-elementen witness geverifieerd, waarmee zij vaststellen dat $r_3(212) \ge 43$ . De vraag voor de bovengrens is of $r_3(212) \le 43$ . Een noodzakelijke voorwaarde voor elke hypothetische 44-set is dat deze beide eindpunten, 1 en 212, moet bevatten; anders zou deze vertalen naar een 44-set in $[1, 211]$ , wat in strijd is met de bekende waarde. De probleemstelling reduceert daarom tot het bewijzen van de onhaalbaarheid van een 44-set die $\{1, 212\}$ bevat.

Methodologie en Architectuur
De auteurs stellen een reproduceerbaar computationeel kader voor dat vijf componenten combineert om te zoeken naar een haalbare 44-set:

Decision-Form CP-SAT Model: Het probleem wordt gecodeerd met behulp van Booleaanse variabelen $x_i$ voor $i \in [1, 212]$ . De beperkingen omvatten:
- 3-AP ongelijkheden: $x_a + x_b + x_c \le 2$ voor alle triples $(a, b, c)$ die een AP vormen.
- Cardinaliteit gelijkheid: $\sum x_i = 44$ (strakker voor propagatie dan ongelijkheid).
- Endpoint forcing: $x_1 = x_{212} = 1$ .
- Symmetriebreking: Lexicografische ordening om reflectiesymmetrie te elimineren.
Witness-Splitting: Om de zoekruimte te beheren, gebruiken de auteurs een geverifieerde 43-elementen witness $A_{43}$ . Zij rangschikken de elementen van $A_{43}$ op basis van hun AP-incidentiegraad en selecteren de top 24. De zoekruimte wordt gesplitst in $2^{24}$ "chunks" door de waarden van deze 24 variabelen vast te leggen. Veel chunks worden direct gepruned als het vaste prefix een 3-AP forceert.
Window-Cardinality Pruning: Een cruciale interventie betreft het toevoegen van geldige ongelijkheden afgeleid van OEIS A003002. Voor elk venster $[a, a+L-1]$ wordt de som van de variabelen begrensd door $r_3(L)$ . Voor $N=212$ voegt dit 22.154 ongelijkheden toe, wat het model aanzienlijk versterkt ten opzien van de ruwe 3-AP beperkingen.
Recursieve Verfijning: Chunks die UNKNOWN teruggeven op het brede niveau (diepte 24), worden verfijnd door het vaste prefix uit te breiden met de volgende hoogste-graad witness variabelen (dieptes 40, 48, 56, 64) en opnieuw op te lossen met langere tijdslimieten.
Solver Diversiteit en Engineering: De campagne maakt gebruik van een SLURM-gebaseerde pipeline die draait op de UMass Unity cluster. Er wordt gebruik gemaakt van:
- CP-SAT (OR-Tools): Voor de brede pass en recursieve verfijning.
- HiGHS (MIP): Een LP-relaxatie-gebaseerde solver die wordt ingezet om de moeilijkste "UNKNOWN" chunks aan te vallen.
- CDCL/SAT (CaDiCaL): Gebruikt om chunks aan te vallen die resistent zijn tegen LP-methoden, waarbij DRAT-bewijzen voor onverzadigbaarheid worden gegenereerd.

Empirische Resultaten
De campagne verwerkte miljoenen subproblemen over de diepte-24 sweep en diverse verfijningsniveaus.

Nul Feasible Oplossingen: Over alle geteste subproblemen (brede pass, verfijningen, HiGHS en CDCL) werden nul feasible 44-sets gevonden. Dit biedt sterke empirische steun voor $r_3(212) = 43$ , hoewel het geen formeel bewijs is.
Impact van Window-Cardinality: Het inschakelen van window-cardinality ongelijkheden verminderde de UNKNOWN ratio in brede passes met ongeveer 28 procentpunten (bijv. van ~30% naar ~1,65% in gecontroleerde batches), wat het meest effectieve pruning-niveau bleek te zijn.
De Structurele Harde Pocket:
- Van een 100.000-chunk expansie batch gaven 6.071 chunks UNKNOWN terug.
- Een 300-seconden recap van een willekeurige steekproef van deze chunks liet 45 resistente chunks over (Tier T1).
- HiGHS Attack: Een een uur durende HiGHS run sloot 0/45. Een 8-urige audit sloot 25/45, waardoor 20 chunks overbleven (Tier T1b) met dual bounds gepind op 0.0, wat aangeeft dat de LP-relaxatie geen certificaat van onhaalbaarheid bood.
- CDCL Attack: Een pure CDCL/SAT aanval op de 20 T1b chunks sloot 18/20, waarbij onafhankelijk geverifieerde DRAT-bewijzen werden gegenereerd.
- De Residuele (T1c): Twee chunks (ID's 40959 en 48895) bleven UNKNOWN zelfs na 12-urige pure CDCL runs en 4-urige windowed CDCL diagnostieken. Deze twee chunks weerstaan CP-SAT, HiGHS (LP-MIP) en CDCL paradigma's.

Belangrijkste Bijdragen
De auteurs framen hun bijdrage expliciet als methodologisch in plaats van een nieuwe exacte waarde voor $r_3(212)$ . De specifieke bijdragen zijn:

Architectuur: Een reproduceerbaar kader dat witness-splitting, window-cardinality pruning en recursieve verfijning combineert voor exacte bovengrens-zoekopdrachten.
Empirisch Verslag: Een gedetailleerde analyse van de $N=212, K=44$ campagne, inclusief solver trade-offs en de niet-uniformiteit van de zoekruimte (bijv. "middle-out" chunks met specifieke pin-assignments zijn significant moeilijker).
Karakterisering van de Harde Pocket: Identificatie van een structurele obstructie (T1c) die invariant is over de CP-SAT, HiGHS en CDCL paradigma's onder genereuze tijdslimieten.
Benchmark Release: Een gelaagde release van instanties:
- T1a: 25 chunks gesloten door HiGHS.
- T1b \ T1c: 18 chunks gesloten door CDCL met DRAT-bewijzen.
- T1c: De laatste 2 resistente chunks, geframed als het scherpste openstaande probleem.
- T2/T3: De 6.071 brede UNKNOWNs en de volledige 12,5M chunk generator voor toekomstige pogingen.
Formalisering: Een Lean 4 encoding van de T1c targets voor formele bewijszoekende systemen.

Significantie en Claims
De auteurs claimen bescheiden dat hoewel de campagne de conjectuur $r_3(212) = 43$ sterk ondersteunt, het geen formeel bewijs vormt vanwege de onopgeloste T1c residu. De significantie ligt in het isoleren van de specifieke computationele barrière:

Het gat tussen gecertificeerde bounds is exact één ( $43 \le r_3(212) \le 44$ ).
Het falen van LP-gebaseerde methoden (HiGHS) en het gedeeltelijke succes van CDCL suggereren dat de hardheid niet louter een propagatie-artefact is, maar een structurele eigenschap waarbij de LP-relaxatie gap nauw is en het integer onhaalbaarheidscertificaat computationeel diffuus is.
Het werk stelt dat het dichten van de kloof ofwel sterkere additief-combinatorische bounds vereist (bijv. Fourier-analytische of multi-window partitie bounds), ofwel aangepaste branch-and-bound systemen die de probleem-specifieke symmetrieën exploiteren die niet door algemene solvers worden gevangen.

Het werk dient als benchmark voor de gemeenschap en biedt specifieke, geverifieerde instanties (T1c) die de huidige limiet vertegenwoordigen van algemene combinatorische optimalisatie-solvers voor deze klasse problemen.