💻 computer science

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

Cet article présente un cadre de calcul reproductible combinant la division de témoins (witness-splitting), l'élagage par cardinalité de fenêtre (window-cardinality pruning) et des solveurs hybrides SAT/MIP pour étudier rigoureusement la borne supérieure de $r_3(212)$ , éliminant avec succès la plupart des ensembles de 44 candidats tout en isolant deux cas structurels résistants qui demeurent non prouvés malgré des efforts de vérification intensifs.

Auteurs originaux : Mehmet Ergezer

Publié 2026-06-04

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Mehmet Ergezer

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous essayez de préparer une valise (les nombres de 1 à 212) avec autant d'articles que possible, mais avec une règle très stricte : vous ne pouvez pas choisir trois articles qui forment un motif arithmétique parfait.

Par exemple, si vous choisissez le nombre 2, vous ne pouvez pas aussi choisir 4 et 6, car $2, 4, 6$ est un motif où chaque nombre est augmenté de 2 par rapport au précédent. Cela s'appelle une « progression arithmétique à 3 termes ».

Pour une valise de taille 212, la grande question de ce document est : Pouvez-vous faire entrer 44 articles dans une valise de taille 212 ?

L'auteur, Mehmet Ergezer, ne s'est pas contenté de deviner ; il a construit une immense usine numérique pour essayer de prouver que 44 est impossible. Voici comment le document se décompose, en utilisant des analogies simples :

1. La stratégie : L'usine du « Witness Split » (Division par Témoin)

Essayer de vérifier toutes les combinaisons possibles de 44 nombres parmi 212, c'est comme essayer de trouver un grain de sable spécifique sur toutes les plages de la Terre. C'est trop vaste pour qu'un seul ordinateur puisse le gérer.

Ainsi, l'auteur a utilisé une astuce ingénieuse :

Le Témoin (The Witness) : Il est parti d'une liste « sûre » connue de 43 nombres qui fonctionne déjà.
La Division (The Split) : Il a pris les 24 nombres les plus « importants » de cette liste sûre et a demandé à l'ordinateur de vérifier tous les scénarios possibles de « Oui/Non » pour eux.
Le Résultat : Cela a divisé la montagne impossible de données en 12,5 millions de petits tas gérables (appelés « chunks » ou morceaux). L'ordinateur a ensuite essayé de résoudre chaque tas un par un.

2. Les outils : La « Fenêtre » et le « Raffinement »

Pour rendre l'ordinateur plus rapide, l'auteur a ajouté deux outils spéciaux :

La Carte Fenêtre (L'Élagueur) : Imaginez regarder à travers une fenêtre une petite section de la valise. Nous savons déjà, grâce à des mathématiques antérieures, qu'une petite fenêtre de taille 50 ne peut contenir, par exemple, que 10 articles. L'ordinateur utilise cette règle pour éliminer instantanément tout tas qui essaie de mettre 11 articles dans cette fenêtre. Ce fut l'outil le plus puissant, réduisant le nombre de tas difficiles de près de 30 %.
Le Raffinement (L'Immersion Profonde) : Si un tas était trop difficile à résoudre en 60 secondes, l'ordinateur n'abandonnait pas. Il prenait ce tas spécifique, y ajoutait de nouvelles règles, et réessayait avec un délai plus long. C'est comme prendre une boîte verrouillée, choisir une serrure spécifique, et réessayer avec une clé plus grande.

3. Les résultats : Le « Hard Pocket » (La Poche Difficile)

Après avoir fait tourner des millions de ces vérifications sur un cluster de supercalculateurs, voici ce qui s'est passé :

Zéro Succès : L'ordinateur n'a jamais trouvé de manière valide de compacter 44 articles. Chaque fois qu'il essayait, il se heurtait à un mur et disait : « Impossible ».
La Preuve : C'est une preuve solide que 44 est impossible, mais ce n'est pas encore une preuve formelle. Pourquoi ? Parce qu'il reste encore quelques tas tenaces que l'ordinateur n'a pas pu terminer à temps.

Le « Hard Pocket » (Les Chunks Résistants) :
Parmi les millions de tas, l'auteur a trouvé un petit groupe tenace de 45 tas qui ont refusé de se résoudre même après avoir reçu du temps supplémentaire et différents outils.

L'Attaque LP : Ils ont essayé un autre type de solveur mathématique (appelé HiGHS) qui traite le problème comme une courbe lisse. Cela n'a pas permis de résoudre les 45 tas.
L'Attaque CDCL : Ils ont essayé un troisième type de solveur (appelé CDCL) qui fonctionne comme un détective, apprenant de ses erreurs. Celui-ci a réussi ! Il a résolu 18 des 45 tas.
Les 2 Finaux : Cependant, 2 tas (étiquetés T1c) sont restés complètement non résolus. Ils ont résisté au premier solveur, au deuxième, et au troisième. Ils sont le « boss final » de ce problème.

4. La conclusion : Le « Unit Gap » (L'Écart d'Unité)

Le document conclut que :

Nous avons une liste vérifiée de 43 nombres qui fonctionne.
Nous avons des preuves solides que 44 est impossible, car l'ordinateur a essayé des millions de fois et a échoué.
Cependant, à cause de ces 2 derniers tas tenaces, nous n'avons pas encore de preuve mathématique à 100 %. L'écart entre 43 et 44 est techniquement encore ouvert.

5. Le cadeau à la communauté

Au lieu de simplement dire « J'abandonne », l'auteur publie toutes les données. Il remet les 2 tas tenaces au monde entier comme un défi.

Il fournit le code et les données exacts afin que d'autres mathématiciens puissent essayer de résoudre juste ces deux tas.
Il a même traduit le problème dans un langage pour les systèmes de preuve formelle (Lean), invitant les informaticiens à essayer de le prouver en utilisant des moteurs de logique.

En bref : L'auteur a construit une immense machine numérique qui a tenté de battre le record de compaction de nombres sans motifs. La machine a échoué à trouver un moyen de battre le record, mais elle s'est bloquée sur deux puzzles minuscules et incroyablement difficiles. Le document dit : « Nous sommes sûrs à 99,9 % que la réponse est 43, mais voici les deux derniers puzzles que vous devez résoudre pour le prouver. »

Résumé Technique : Raffinement par Division de Témoin + Cardinalité de Fenêtre pour $r_3(212)$

Énoncé du Problème
Le document traite du calcul exact de $r_3(N)$ , défini comme la taille maximale d'un sous-ensemble de $[1, N]$ ne contenant aucune progression arithmétique de trois termes (3-AP) non triviale. Alors que le comportement asymptotique est bien étudié (ex. : théorème de Roth, Kelley–Meka), l'accent est mis ici sur la frontière finie à $N=212$ . D'après l'OEIS A003002, $r_3(211) = 43$ . Les auteurs étudient le problème de décision : Existe-t-il un ensemble de 44 éléments sans 3-AP dans $[1, 212]$ ?
Les auteurs ont vérifié de manière indépendante un témoin de 43 éléments, établissant que $r_3(212) \ge 43$ . La question de la borne supérieure est de savoir si $r_3(212) \le 43$ . Une condition nécessaire pour tout hypothétique ensemble de 44 éléments est qu'il doit contenir les deux extrémités, 1 et 212 ; sinon, il se traduirait par un ensemble de 44 éléments dans $[1, 211]$ , contredisant la valeur connue. Ainsi, le problème se réduit à prouver l'infaisabilité d'un ensemble de 44 éléments contenant $\{1, 212\}$ .

Méthodologie et Architecture
Les auteurs proposent un cadre de calcul reproductible combinant cinq composants pour rechercher un ensemble de 44 éléments faisable :

Modèle CP-SAT de Forme Décisionnelle : Le problème est encodé à l'aide de variables booléennes $x_i$ pour $i \in [1, 212]$ . Les contraintes incluent :
- Inégalités de 3-AP : $x_a + x_b + x_c \le 2$ pour tous les triplets $(a, b, c)$ formant une AP.
- Égalité de cardinalité : $\sum x_i = 44$ (plus serrée pour la propagation que l'inégalité).
- Forçage des extrémités : $x_1 = x_{212} = 1$ .
- Rupture de symétrie : Ordonnancement lexicographique pour éliminer la symétrie de réflexion.
Division de Témoin (Witness-Splitting) : Pour gérer l'espace de recherche, les auteurs utilisent un témoin de 43 éléments $A_{43}$ vérifié. Ils classent les éléments de $A_{43}$ par degré d'incidence de AP et sélectionnent les 24 premiers. L'espace de recherche est divisé en $2^{24}$ « blocs » en fixant les valeurs de ces 24 variables. De nombreux blocs sont élagués immédiatement si le préfixe fixé force une 3-AP.
Élagage par Cardinalité de Fenêtre : Une intervention critique consiste à ajouter des inégalités valides dérivées de l'OEIS A003002. Pour toute fenêtre $[a, a+L-1]$ , la somme des variables est bornée par $r_3(L)$ . Pour $N=212$ , cela ajoute 22 154 inégalités, renforçant considérablement le modèle au-delà des contraintes brutes de 3-AP.
Raffinement Récursif : Les blocs retournant UNKNOWN (inconnu) à la couche large (profondeur 24) sont affinés en étendant le préfixe fixé avec les variables de témoin à plus haut degré (profondeurs 40, 48, 56, 64) et en résolvant à nouveau avec des limites de temps plus longues.
Diversité des Solveurs et Ingénierie : La campagne utilise un pipeline basé sur SLURM tournant sur le cluster Unity de l'UMass. Elle emploie :
- CP-SAT (OR-Tools) : Pour le passage large et le raffinement récursif.
- HiGHS (MIP) : Un solveur basé sur la relaxation LP, utilisé pour attaquer les blocs « UNKNOWN » les plus difficiles.
- CDCL/SAT (CaDiCaL) : Utilisé pour ré-attaquer les blocs résistants aux méthodes LP, générant des preuves DRAT d'insatisfaisabilité.

Résultats Empiriques
La campagne a traité des millions de sous-problèmes à travers le balayage de profondeur 24 et diverses étapes de raffinement.

Zéro Solution Faisable : À travers tous les sous-problèmes testés (passage large, raffinements, HiGHS et CDCL), zéro ensemble de 44 éléments n'a été trouvé. Cela fournit un fort soutien empirique à la conjecture $r_3(212) = 43$ , bien que ce ne soit pas une preuve formelle.
Impact de la Cardinalité de Fenêtre : L'activation des inégalités de cardinalité de fenêtre a réduit le taux de UNKNOWN dans les passages larges d'environ 28 points de pourcentage (par exemple, de ~30 % à ~1,65 % dans des lots contrôlés), faisant de cette couche le mécanisme d'élagage le plus efficace.
Le Pocket de Difficulté Structurelle :
- À partir d'un lot d'expansion de 100 000 blocs, 6 071 blocs ont retourné UNKNOWN.
- Un récapitulatif de 300 secondes sur un échantillon aléeste de ces blocs a laissé 45 blocs résistants (Tier T1).
- Attaque HiGHS : Une exécution d'une heure de HiGHS a fermé 0/45. Un audit de 8 heures a fermé 25/45, laissant 20 blocs (Tier T1b) avec des bornes duales bloquées à 0.0, indiquant que la relaxation LP ne fournissait aucun certificat d'infaisabilité.
- Attaque CDCL : Une attaque pure CDCL/SAT sur les 20 blocs T1b a fermé 18/20, générant des preuves DRAT vérifiées de manière indépendante.
- Le Résiduel (T1c) : Deux blocs (IDs 40959 et 48895) sont restés UNKNOWN même après des exécutions CDCL pur de 12 heures et des diagnostics CDCL fenêtrés de 4 heures. Ces deux blocs résistent aux paradigmes CP-SAT, HiGHS (LP-MIP) et CDCL.

Contributions Clés
Le papier cadre explicitement sa contribution comme étant méthodologique plutôt qu'une nouvelle valeur exacte pour $r_3(212)$ . Les contributions spécifiques sont :

Architecture : Un cadre reproductible combinant division de témoin, élagage par cardinalité de fenêtre et raffinement récursif pour les recherches de bornes supérieures exactes.
Compte Rendu Empirique : Une analyse détaillée de la campagne $N=212, K=44$ , incluant les compromis entre solveurs et la non-uniformité de l'espace de recherche (ex. : les blocs « middle-out » avec des assignations de pins spécifiques sont nettement plus difficiles).
Caractérisation du Pocket de Difficulté : Identification d'une obstruction structurelle (T1c) qui est invariante à travers les paradigmes CP-SAT, HiGHS et CDCL sous des limites de temps généreuses.
Libération de Benchmarks : Une libération échelonnée des instances :
- T1a : 25 blocs fermés par HiGHS.
- T1b \ T1c : 18 blocs fermés par CDCL avec preuves DRAT.
- T1c : Les 2 derniers blocs résistants, présentés comme le problème ouvert le plus pointu.
- T2/T3 : Les 6 071 UNKNOWN larges et le générateur complet de 12,5M de blocs pour des tentatives futures.
Formalisation : Un encodage en Lean 4 des cibles T1c pour les systèmes de recherche de preuves formelles.

Signification et Revendications
Les auteurs affirment modestement que, bien que la campagne soutienne fortement la conjecture $r_3(212) = 43$ , elle ne constitue pas une preuve formelle en raison du résiduel T1c non résolu. La signification réside dans l'isolement de la barrière computationnelle spécifique :

L'écart entre les bornes certifiées est exactement de un ( $43 \le r_3(212) \le 44$ ).
L'échec des méthodes basées sur la LP (HiGHS) et le succès partiel de CDCL suggèrent que la difficulté n'est pas simplement un artefact de propagation mais une propriété structurelle où l'écart de relaxation LP est serré et le certificat d'infaisabilité entier est combinatoirement diffus.
Le papier postule que combler l'écart nécessite soit des bornes combinatoires additives plus fortes (ex. : limites de partition de type analyse de Fourier ou multi-fenêtres), soit des systèmes de branch-and-bound personnalisés qui exploitent les symétries spécifiques au problème non capturées par les solveurs généraux.

Ce travail sert de référence pour la communauté, offrant des instances spécifiques et vérifiées (T1c) qui représentent la limite actuelle des solveurs d'optimisation combinatoire à usage général pour cette classe de problèmes.