💻 computer science

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

Diese Arbeit präsentiert ein reproduzierbares computergestütztes Framework, das Witness-Splitting, Window-Cardinality-Pruning und hybride SAT/MIP-Solver kombiniert, um die obere Schranke von $r_3(212)$ rigoros zu untersuchen, wobei erfolgreich die meisten Kandidaten-44-Sets eliminiert wurden, während zwei resistente strukturelle Fälle isoliert wurden, die trotz intensiver Verifizierungsbemühungen weiterhin unbewiesen bleiben.

Ursprüngliche Autoren: Mehmet Ergezer

Veröffentlicht 2026-06-04

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Mehmet Ergezer

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie versuchen, einen Koffer (die Zahlen von 1 bis 212) mit so vielen Gegenständen wie möglich zu packen, aber mit einer strengen Regel: Sie dürfen nicht drei Gegenstände auswählen, die ein perfektes arithmetisches Muster bilden.

Zum Beispiel: Wenn Sie die Zahl 2 wählen, dürfen Sie auch nicht die 4 und die 6 wählen, denn 2, 4, 6 ist ein Muster, bei dem jede Zahl um 2 größer ist als die vorangegangene. Dies wird als „3-Term-Arithmetische Progression“ bezeichnet.

Mathematiker versuchen schon lange herauszufinden, wie viele Gegenstände man absolut maximal in diesen Koffer passen kann, ohne die Regel zu brechen. Für einen Koffer der Größe 211 ist die Antwort bekannt: 43. Die große Frage dieser Arbeit ist: Kann man 44 Gegenstände in einen Koffer der Größe 212 packen?

Der Autor, Mehmet Ergezer, hat nicht einfach nur geraten; er hat eine riesige digitale Fabrik gebaut, um zu beweisen, dass 44 unmöglich ist. So ist das Paper aufgebaut, unter Verwendung einfacher Analogien:

1. Die Strategie: Die „Witness Split“-Fabrik

Zu prüfen, welche Kombinationen von 44 Zahlen aus 212 möglich sind, ist so, als würde man versuchen, ein bestimmtes Sandkorn auf allen Stränden der Erde zu finden. Das ist zu groß für einen einzelnen Computer.

Deshalb nutzte der Autor einen cleveren Trick:

Der Zeuge (The Witness): Er begann mit einer bekannten „sicheren“ Liste von 43 Zahlen, die bereits funktioniert.
Die Aufteilung (The Split): Er nahm die 24 „wichtigsten“ Zahlen aus dieser sicheren Liste und fragte den Computer, alle möglichen „Ja/Nein“-Szenarien für diese Zahlen zu prüfen.
Das Ergebnis: Dies zerlegte den unbezwingbaren Berg an Daten in 12,5 Millionen kleinere, handhabbare Haufen (genannt „Chunks“). Der Computer versuchte dann, jeden Haufen einzeln zu lösen.

2. Die Werkzeuge: Das „Fenster“ und die „Verfeinerung“

Um den Computer schneller zu machen, fügte der Autor zwei spezielle Werkzeuge hinzu:

Die Fensterkarte (Der Pruner/Beschneider): Stellen Sie sich vor, Sie schauen durch ein Fenster auf einen kleinen Abschnitt des Koffers. Wir wissen bereits aus früherer Mathematik, dass ein kleines Fenster der Größe 50 nur etwa 10 Gegenstände aufnehmen kann. Der Computer nutzt diese Regel, um sofort jeden Haufen auszusortieren, der versucht, 11 Gegenstände in dieses Fenster zu packen. Dies war das mächtigste Werkzeug und reduzierte die Anzahl der schwierigen Haufen um fast 30 %.
Die Verfeinerung (Der Deep Dive): Wenn ein Haufen zu schwierig war, um ihn in 60 Sekunden zu lösen, gab der Computer nicht auf. Er nahm diesen spezifischen schwierigen Haufen, fügte mehr Regeln hinzu und versuchte es erneut mit einem längeren Zeitlimit. Das ist, als würde man eine verschlossene Box nehmen, ein spezifisches Schloss knacken und es dann mit einem größeren Schlüssel erneut versuchen.

3. Die Ergebnisse: Die „Harte Tasche“ (The Hard Pocket)

Nachdem Millionen dieser Prüfungen auf einem Supercomputer-Cluster durchgeführt wurden, geschah Folgendes:

Null Erfolg: Der Computer fand nie einen einzigen gültigen Weg, um 44 Gegenstände zu packen. Jedes Mal, wenn er es versuchte, stieß er gegen eine Wand und sagte: „Unmöglich.“
Der Beweis: Dies ist ein starkes Indiz dafür, dass 44 unmöglich ist, aber es ist noch kein formeller Beweis. Warum? Weil es noch einige hartnäckige Haufen gibt, die der Computer nicht rechtzeitig fertigstellen konnte.

Die „Harte Tasche“ (Die resistenten Chunks):
Aus den Millionen von Haufen fand der Autor eine winzige, hartnäckige Gruppe von 45 Haufen, die selbst nach zusätzlicher Zeit und anderen Werkzeugen nicht nachgaben.

Der LP-Angriff: Sie versuchten es mit einer anderen Art von mathematischem Solver (genannt HiGHS), der das Problem wie eine glatte Kurve betrachtet. Er konnte keinen der 45 Haufen lösen.
Der CDCL-Angriff: Sie versuchten einen dritten Typ von Solver (genannt CDCL), der wie ein Detektiv arbeitet und aus seinen Fehlern lernt. Dieser war erfolgreich! Er löste 18 der 45 Haufen.
Die letzten 2: Jedoch blieben 2 Haufen (bezeichnet als T1c) völlig ungelöst. Sie trotzten dem ersten Solver, dem zweiten Solver und auch dem dritten Solver. Sie sind der „Endgegner“ dieses Problems.

4. Das Fazit: Die „Einheitslücke“ (The Unit Gap)

Das Paper kommt zu folgendem Schluss:

Wir haben eine verifizierte Liste von 43 Zahlen, die funktioniert.
Wir haben starke Beweise dafür, dass 44 unmöglich ist, weil der Computer Millionen Male versucht hat und gescheitert ist.
Da es jedoch diese 2 letzten hartnäckigen Haufen gibt, haben wir noch keinen 100 % mathematischen Beweis. Die Antwort ist höchstwahrscheinlich 43, aber die „Lücke“ zwischen 43 und 44 ist technisch gesehen noch offen.

5. Das Geschenk an die Gemeinschaft

Anstatt einfach nur zu sagen „Ich gebe auf“, gibt der Autor alle Daten frei. Er überreicht die 2 hartnäckigen Haufen der Welt als Herausforderung.

Er stellt den exakten Code und die Daten zur Verfügung, damit andere Mathematiker versuchen können, nur diese zwei Haufen zu lösen.
Er hat das Problem sogar in eine Sprache für formale Beweissysteme (Lean) übersetzt und lädt Informatiker ein, zu versuchen, dies mithilfe von Logik-Engines zu beweisen.

Kurz gesagt: Der Autor baute eine massive digitale Maschine, die versuchte, den Rekord beim Packen von Zahlen ohne Muster zu brechen. Die Maschine scheiterte daran, einen Weg zu finden, den Rekord zu brechen, aber sie blieb an zwei winzigen, unglaublich schwierigen Rätseln hängen. Das Paper sagt: „Wir sind uns zu 99,9 % sicher, dass die Antwort 43 ist, aber hier sind die zwei finalen Rätsel, die Sie lösen müssen, um es zu beweisen.“

Technisches Resümee: Witness-Split + Window-Cardinality-Verfeinerung für $r_3(212)$

Problemstellung
Die vorliegende Arbeit befasst sich mit der exakten Berechnung von $r_3(N)$ , definiert als die maximale Größe einer Teilmenge von $[1, N]$ , die keine nicht-trivialen arithmetischen Progressionen der Länge drei (3-AP) enthält. Während das asymptotische Verhalten gut untersucht ist (z. B. Roths Theorem, Kelley–Meka), liegt der Fokus hier auf der endlichen Grenze bei $N=212$ . Basierend auf OEIS A003002 gilt $r_3(211) = 43$ . Die Autoren untersuchen das Entscheidungsproblem: Existiert eine 44-elementige 3-AP-freie Teilmenge von $[1, 212]$ ?
Die Autoren haben unabhängig ein 43-elementiges Witness-Set verifiziert und damit $r_3(212) \ge 43$ etabliert. Die Frage der oberen Schranke ist, ob $r_3(212) \le 43$ gilt. Eine notwendige Bedingung für jede hypothetische 44-Element-Menge ist, dass sie beide Endpunkte, 1 und 212, enthalten muss; andernfalls ließe sie sich in eine 44-Element-Menge in $[1, 211]$ transformieren, was dem bekannten Wert widersprechen würde. Somit reduziert sich das Problem auf den Beweis der Unmöglichkeit einer 44-Element-Menge, die $\{1, 212\}$ enthält.

Methodik und Architektur
Die Autoren schlagen ein reproduzierbares computergestütztes Framework vor, das fünf Komponenten kombiniert, um nach einer zulässigen 44-Element-Menge zu suchen:

Decision-Form CP-SAT Modell: Das Problem wird mittels Boole'scher Variablen $x_i$ für $i \in [1, 212]$ kodiert. Die Constraints umfassen:
- 3-AP-Ungleichungen: $x_a + x_b + x_c \le 2$ für alle Tripel $(a, b, c)$ , die eine AP bilden.
- Kardinalitätsgleichheit: $\sum x_i = 44$ (effektiver für die Propagation als eine Ungleichung).
- Endpunkt-Erzwingung: $x_1 = x_{212} = 1$ .
- Symmetriebrechung: Lexikographische Ordnung zur Eliminierung der Reflexionssymmetrie.
Witness-Splitting: Um den Suchraum zu handhaben, verwenden die Autoren ein verifiziertes 43-elementiges Witness-Set $A_{43}$ . Sie ordnen die Elemente von $A_{43}$ nach ihrem AP-Inzidenzgrad und wählen die 24 besten aus. Der Suchraum wird durch das Fixieren der Werte dieser 24 Variablen in $2^{24}$ „Chunks“ aufgeteilt. Viele Chunks werden sofort geprunt, falls das fixierte Präfix eine 3-AP erzwingt.
Window-Cardinality Pruning: Eine entscheidende Intervention ist das Hinzufügen gültiger Ungleichungen, die aus OEIS A003002 abgeleitet wurden. Für jedes Fenster $[a, a+L-1]$ ist die Summe der Variablen durch $r_3(L)$ beschränkt. Für $N=212$ fügt dies 22.154 Ungleichungen hinzu, was das Modell weit über die rohen 3-AP-Constraints hinaus stärkt.
Rekursive Verfeinerung: Chunks, die in der breiten Schicht (Tiefe 24) UNKNOWN zurückgeben, werden verfeinert, indem das fixierte Präfix durch die nächsthöherwertigen Witness-Variablen erweitert wird (Tiefen 40, 48, 56, 64) und erneut mit längeren Zeitlimits gelöst wird.
Solver-Diversität und Engineering: Die Kampagne nutzt eine SLURM-basierte Pipeline auf dem UMass Unity Cluster. Sie verwendet:
- CP-SAT (OR-Tools): Für den breiten Durchlauf und die rekursive Verfeinerung.
- HiGHS (MIP): Ein LP-Relaxations-basierter Solver, der eingesetzt wird, um die schwierigsten „UNKNOWN“-Chunks anzugreifen.
- CDCL/SAT (CaDiCaL): Wird verwendet, um Chunks anzugreifen, die gegen LP-Methoden resistent sind, wobei DRAT-Proofs für Unzulänglichkeit generiert werden.

Empirische Ergebnisse
Die Kampagne verarbeitete Millionen von Teilproblemen über den Tiefen-24-Sweep und verschiedene Verfeinerungsstufen hinweg.

Null zulässige Lösungen: Über alle getesteten Teilprobleme hinweg (breiter Durchlauf, Verfeinerungen, HiGHS und CDCL) wurden null zulässige 44-Element-Mengen gefunden. Dies liefert eine starke empirische Unterstützung für $r_3(212) = 43$ , stellt jedoch keinen formalen Beweis dar.
Impact der Window-Cardinality: Die Aktivierung der Window-Cardinality-Ungleichungen reduzierte die UNKNOWN-Rate in den breiten Durchläufen um etwa 28 Prozentpunkte (z. B. von ~30 % auf ~1,65 % in kontrollierten Batches), was sie zur effektivsten Pruning-Schicht macht.
Die strukturelle „Hard Pocket“:
- Aus einem 100.000-Chunk-Expansionsbatch lieferten 6.071 Chunks UNKNOWN.
- Eine 300-sekündige Rekapitulation einer Zufallsstichprobe dieser Chunks hinterließ 45 resistente Chunks (Tier T1).
- HiGHS Attack: Ein einstündiger HiGHS-Lauf schloss 0/45. Ein 8-stündiges Audit schloss 25/45, sodass 20 Chunks (Tier T1b) übrig blieben, deren duale Schranken bei 0,0 festgesetzt waren, was darauf hindeutet, dass die LP-Relaxation kein Zertifikat der Unzulänglichkeit lieferte.
- CDCL Attack: Ein reiner CDCL/SAT-Angriff auf die 20 T1b-Chunks schloss 18/20 und generierte unabhängig verifizierte DRAT-Proofs.
- Das Residuum (T1c): Zwei Chunks (IDs 40959 und 48895) blieben selbst nach 12-stündigen reinen CDCL-Läufen und 4-stündigen fensterbasierten CDCL-Diagnosen UNKNOWN. Diese zwei Chunks widerstehen CP-SAT, HiGHS (LP-MIP) und CDCL-Paradigmen.

Wesentliche Beiträge
Die Autoren rahmen ihren Beitrag explizit als methodisch und nicht als neuen exakten Wert für $r_3(212)$ ein. Die spezifischen Beiträge sind:

Architektur: Ein reproduzierbares Framework, das Witness-Splitting, Window-Cardinality-Pruning und rekursive Verfeinerung für die Suche nach exakten oberen Schranken kombiniert.
Empirischer Bericht: Eine detaillierte Analyse der $N=212, K=44$ Kampagne, einschließlich Solver-Trade-offs und der Nicht-Uniformität des Suchraums (z. B. sind „Middle-Out“-Chunks mit spezifischen Pin-Zuweisungen signifikant schwerer).
Charakterisierung der „Hard Pocket“: Identifizierung eines strukturellen Hindernisses (T1c), das über CP-SAT, HiGHS und CDCL-Paradigmen hinweg unter großzügigen Zeitlimits invariant bleibt.
Benchmark-Release: Ein gestuftes Release von Instanzen:
- T1a: 25 durch HiGHS geschlossene Chunks.
- T1b \ T1c: 18 durch CDCL mit DRAT-Proofs geschlossene Chunks.
- T1c: Die letzten 2 resistenten Chunks, die als das schärfste offene Problem formuliert sind.
- T2/T3: Die 6.071 breiten UNKNOWNs und der vollständige 12,5M Chunk-Generator für zukünftige Versuche.
Formalisierung: Eine Lean 4 Kodierung der T1c-Ziele für formale Beweissuchsysteme.

Bedeutung und Behauptungen
Die Autoren behaupten bescheiden, dass die Kampagne zwar die Vermutung $r_3(212) = 43$ stark stützt, dies jedoch aufgrund des ungelösten T1c-Residuums keinen formalen Beweis darstellt. Die Bedeutung liegt in der Isolierung der spezifischen computationalen Barriere:

Die Lücke zwischen den zertifizierten Schranken beträgt exakt eins ( $43 \le r_3(212) \le 44$ ).
Das Scheitern von LP-basierten Methoden (HiGHS) und der Teilerfolg von CDCL legen nahe, dass die Schwierigkeit nicht bloß ein Artefakt der Propagation ist, sondern eine strukturelle Eigenschaft, bei der die LP-Relaxationslücke eng ist und das ganzzahlige Unzulänglichkeitszertifikat kombinatorisch diffus ist.
Die Arbeit postuliert, dass das Schließen der Lücke entweder stärkere additive-kombinatorische Schranken (z. B. Fourier-analytische oder Multi-Window-Partition-Schranken) oder maßgeschneiderte Branch-and-Bound-Systeme erfordert, die problem-spezifische Symmetrien ausnutzen, welche von allgemeinen Solvern nicht erfasst werden.

Die Arbeit dient als Benchmark für die Fachwelt und bietet spezifische, verifizierte Instanzen (T1c), die die aktuelle Grenze allgemeiner kombinatorischer Optimierungslösungen für diese Klasse von Problemen darstellen.