Choc ! Choc ! J'ai appris hier qu'un problème ouvert sur lequel je travaillais depuis plusieurs semaines venait d'être résolu par Claude Opus 4.6 – le modèle de raisonnement hybride d'Anthropic publié trois semaines plus tôt ! Il semble que je vais devoir réviser mes opinions sur "l'IA générative" un de ces jours. Quelle joie d'apprendre non seulement que ma conjecture a une belle solution, mais aussi de célébrer cette avancée spectaculaire dans la déduction automatique et la résolution créative de problèmes. Je vais essayer de raconter brièvement l'histoire dans cette note.
Voici le problème, qui est apparu alors que j'écrivais sur les cycles hamiltoniens orientés pour un futur volume de The Art of Computer Programming :
Considérons le graphe orienté ayant m³ sommets ijk pour 0 ≤ i, j, k < m, et trois arcs depuis chaque sommet, à savoir vers i⁺jk, ij⁺k, et ijk⁺, où i⁺ = (i+1) mod m. Essayez de trouver une décomposition générale des arcs en trois cycles orientés de longueur m³, pour tout m > 2.
J'avais résolu le problème pour m = 3, et demandé une généralisation comme partie de la réponse à un exercice dans [3]. Mon ami Filip Stappers a relevé le défi, et a découvert empiriquement des solutions pour 4 ≤ m ≤ 16 ; par conséquent, il est devenu hautement probable que les décompositions souhaitées existent, sauf quand m ≤ 2.
En effet, c'est Filip qui a eu l'audace de poser cette question à Claude, en utilisant exactement le libellé ci-dessus. Il a également fourni des conseils et un coaching, en instruisant Claude de résumer sa progression en cours :
Et le plan d'attaque de Claude était tout à fait admirable. D'abord, il a reformulé le problème : "Il faut sigma : Zₘ³ → S₃, assignant une permutation de {0,1,2} à chaque sommet ; le cycle c au sommet v va dans la direction sigma(v)[c]. Chaque graphe fonctionnel résultant doit être un unique cycle hamiltonien." Ensuite, il a cherché une réponse simple : "Si sigma est cyclique, c.-à-d. f_c(v) = (c + g(v)) mod 3 pour une certaine fonction g: Zₘ³ → Z₃, alors on n'a besoin que d'une seule fonction g. Test de g linéaire (a·i + b·j + c·k) mod 3 et de variantes quadratiques. Aucune fonction g linéaire ou quadratique simple ne fonctionne."
La deuxième exploration de Claude fut ce qu'il a appelé une tentative de recherche DFS (parcours en profondeur) : "Tentative de recherche DFS par force brute sur les assignations sigma pour m = 3 (espace de recherche de 6²⁷). Trop lent sans un bon élagage."
Troisièmement, il a essayé ce qu'il a appelé une analyse serpentine 2D : "Résultat clé en 2D : Le motif [0^(m-1)1]^m donne un cycle hamiltonien dans Cay(Zₘ², {e₀, e₁}) pour m = 3. Son complément fonctionne aussi, donnant une décomposition 2D valide." C'est vraiment impressionnant ! D'abord, Claude a reconnu le graphe orienté comme un soi-disant graphe de Cayley avec deux générateurs, traditionnellement appelés e₀ et e₁ ; un mathématicien comprendra que les arcs agissent comme un groupe sur m² sommets, où e₀ incrémente la première composante tandis que e₁ incrémente la seconde. Ensuite, il a formulé le cycle symboliquement pour m général, bien que pour une raison quelconque, il ait encore dit qu'il ne regardait que m = 3. Et il a décidé d'appeler cela un "motif serpentin" !
L'exploration numéro 4 a construit le "motif serpentin 3D" [0^(m-1)1]^(m-1)[0^(m-1)2]^m. (C'est une erreur typographique pour [[0^(m-1)1]^(m-1)0^(m-1)2]^m. C'est une séquence classique appelée le "code Gray modulaire m-aire" à la page 299 de [2].) Après avoir supprimé ce cycle du graphe, Claude a examiné le graphe orienté 2-régulier restant et a constaté qu'il a une "structure rigide rendant la décomposition difficile."
Néanmoins, l'exploration numéro 5 a analysé ce graphe résiduel, trouvant quelques cycles. Malheureusement, ils n'ont pas fonctionné.
Retour à la planche à dessin. Plusieurs autres approches ont été essayées, par exemple en examinant les choix à faire aux sommets qui se trouvent sur l'hyperplan où i + j + k est congru à -1. Rien de prometteur n'est apparu jusqu'à l'exploration numéro 15, qui a introduit ce que Claude a appelé une décomposition en fibres : "L'application quotient γ(i,j,k) = i+j+k mod m envoie tous les arcs de la fibre F_s vers F_(s+1). Le graphe orienté est stratifié. En coordonnées de fibre (i,j) avec k = (s - i - j) mod m."
En utilisant ces coordonnées de fibre, le problème pouvait maintenant être reformulé comme le choix, pour chaque (i,j,s), d'une permutation des trois opérateurs qui décalent (i,j) par soit (1,0) soit (0,1) soit (0,0). "Essai de sigma dépendant
uniquement de l'indice de fibre s (rotation par s) : donne le motif (i+j+k) mod 3 qui ne fonctionne pas. Une recherche locale aléatoire a trouvé des solutions pour m = 3 mais aucun motif général n'a émergé."
L'exploration 18 "a implémenté le cadre complet des fibres en code exécutable. Retour arrière exhaustif pour m = 3 a trouvé une décomposition valide en 0,1s (10932 nœuds)." Dans cette solution, la permutation sigma était la même pour tous les (i,j) dans la fibre s = 0. Une fibre similairement "uniforme" a été trouvée pour m = 4 par recuit simulé, dans le cadre de l'exploration 20.
Dans l'exploration 21, Claude a réalisé que la fonction serpentine 2D "Q(i,j) = (i+1,j) si i+j ≠ m-1 mod m, sinon (i,j+1)" avait de bonnes propriétés. Elle semblait prometteuse lorsqu'un choix uniforme est fait à la fibre 0 et une version de la fonction serpentine à toutes les autres fibres, si et seulement si m est impair.
Cela a déclenché une série d'expériences avec du recuit simulé "à grande échelle", mais tout fut en vain. La conclusion après l'exploration 25 était "Le recuit simulé peut trouver des solutions mais ne peut pas donner une construction générale. Besoin de mathématiques pures."
Alors maintenant, Claude a mis une nouvelle casquette de réflexion. À un moment, il s'est dit : "Peut-être que le bon cadre est : ne pense pas en fibres, pense directement à ce qui rend un cycle hamiltonien."
Il y a eu un quasi-accident à l'exploration numéro 27. "Prendre le serpentin 3D pour le cycle 0, appliquer une rotation cyclique des coordonnées pour obtenir les cycles 1 et 2 : d₁(i,j,k) = (d₀(j,k,i)+1) mod 3 ; d₂(i,j,k) = (d₀(k,i,j)+2) mod 3 ; tous les trois sont individuellement hamiltoniens pour chaque m = 3 ... 9 testés ! Seulement 3(m-1) des m³ sommets ont des conflits. tous se trouvent sur l'hyperplan i+j+k = m-1 mod m."
Malheureusement, ces conflits n'ont pas pu être résolus. L'exploration 29 a prouvé que de nombreux scénarios plausibles étaient en fait impossibles. "Cela tue complètement l'approche 'hyperplan unique + rotation'. ... Nous devons permettre à la fonction de direction d'utiliser des valeurs différentes à travers une orbite de rotation."
Mais, aha. L'exploration 30 est revenue à la solution trouvée par recuit simulé dans l'exploration 20 et a remarqué que le choix à chaque fibre ne dépend que d'une seule coordonnée : s = 0 seulement de j ; s = 1 et s = 2 seulement de i. Cela a conduit à une construction concrète (exploration 31), sous la forme d'un programme Python, qui a produit des résultats valides pour m = 3, 5, 7, 9 et 11 – hourra ! "Les trois cycles sont hamiltoniens, tous les arcs sont utilisés, décomposition parfaite !"
Voici une simplification de ce programme Python, converti sous forme C :
Filip Stappers a testé le programme Python de Claude pour tous les m impairs entre 3 et 101, trouvant des décompositions parfaites à chaque fois. Il en a donc conclu, assez raisonnablement, que le problème était effectivement résolu pour les valeurs impaires de m. Et il m'a rapidement envoyé la nouvelle choquante.
Bien sûr, une preuve rigoureuse était encore nécessaire. Et la construction d'une telle preuve s'avère assez intéressante. Regardons, par exemple, le premier cycle qui est imprimé ; nous devons prouver qu'il a une longueur m³
La règle pour ce cycle n'est pas triviale, mais assez simple :
("Incrémenter" signifie "augmenter de 1, mod m".) Ainsi, dans le cas particulier m = 3, ce cycle est
Et dans le cas particulier m = 5, c'est
Les triplets pour la même valeur de s sont espacés exactement de m pas. Pour prouver que tous les m³ triplets apparaissent, nous devons prouver que les m² triplets pour une valeur donnée de s sont tous présents.
Remarquez que la première coordonnée, i, ne change que lorsque s = 0 et j = m-1. Ainsi, les m² triplets avec une valeur donnée de la première coordonnée i apparaissent tous consécutivement. (Nos exemples de cycles l'indiquent en commençant au sommet où i vient de changer à 0, au lieu de commencer au sommet 000.)
Remarquez que les éléments du cycle avec i = 0 doivent commencer en général par le sommet 0(m-1)2, car le sommet précédent devait avoir i = j = m-1 et s = 0. Et 0(m-1)2, qui a s = 1, est suivi en général par 002, 012, ..., 0(m-3)2, 0(m-3)3, nous ramenant à s = 0.
En général, 0(m-k)k est immédiatement suivi par 0(m-k)(k+1) quand 1 < k < m ; ensuite j augmente jusqu'à ce que nous atteignions 0(m-k-2)(k+1), dont le successeur est 0(m-k-2)(k+2). Ainsi, k est augmenté de 2, modulo m, chaque fois que nous atteignons un sommet avec s = 0. Puisque m est impair, nous finirons par atteindre 0(m-1)1 – moment auquel nous aurons vu tous les m² sommets de la forme 0jk. Et le successeur de 0(m-1)1 est 1(m-1)1.
Jusqu'ici tout va bien ! En général, les éléments du cycle dont la première composante i satisfait 0 < i < m-1 commenceront par i(m-1)(2-i), où 2-i est bien sûr évalué mod m. Si tout se passe bien, ces éléments devraient inclure tous les m² sommets qui commencent par i, se terminant par i(m-i)(1-i) – dont le successeur est (i+1)(m-1)(1-i). Et tout se passe bien : Nous avançons répétitivement la deuxième composante sauf quand s = 0 ; donc les sommets que nous voyons quand s = 0 sont i(m-2)(2-i), i(m-3)(3-i), ..., i0(m-i), i(m-1)(1-i).
Finalement, nous atteignons (m-1)(m-1)3, le premier sommet pour lequel i = m-1. Les règles locales changent à nouveau : Désormais, nous allons répétitivement avancer la troisième composante, sauf quand s = m-1. Les sommets que nous voyons quand s = 0 sont (m-1)01, (m-1)10, ..., (m-1)(m-1)2. CQFD.
Nous venons de prouver que le premier cycle (le cycle pour c = 0 dans le programme C) est hamiltonien. Des preuves similaires peuvent être effectuées pour les deux autres cycles. (Voir l'annexe.)
Pour le plaisir, considérons une classe plus large de cycles pour lesquels de telles preuves existent. En effet, il s'avère qu'il existe des centaines de façons de résoudre le problème de décomposition énoncé pour m impair ; Claude Opus 4.6 en a justement découvert une, en déduisant où chercher.
Nous dirons qu'un cycle hamiltonien C pour m = 3 est généralisable si la construction suivante produit un cycle hamiltonien pour tout m impair ≥ 3 : "Étant donné un sommet arbitraire IJK pour 0 ≤ I, J, K < m, soit i = I', j = J', s = S', et k = (s - i - j) mod 3, où S = (I + J + K) mod m, 0' = 0, (m-1)' = 2, et x' = 1 pour 0 < x < m-1. Obtenir le successeur de IJK en incrémentant la coordonnée que le cycle C incrémente pour former le successeur de ijk. Par exemple, si m = 5 et IJK = 301, nous avons i = 1, j = 0, S = 4, s = 2, k = 1. Donc le successeur de 301 sera soit 401, soit 311, soit 302, selon que C contient l'arc 101 → 201 ou 101 → 111 ou 101 → 102.
Le cycle de Claude dans l'exemple ci-dessus pour m = 3 est généralisable ; en effet, nous avons vu sa généralisation pour m = 5. Mais il est facile de trouver des cycles qui ne sont pas généralisables. Par exemple, si C est le cycle
(qui se trouve être le plus petit dans l'ordre lexicographique de tous les cycles hamiltoniens pour le cas m = 3), nous obtenons la "généralisation" suivante pour m = 5 :
Oups – ce cycle a une longueur de 75, pas de 125.
Il s'avère qu'il y a exactement 11502 cycles hamiltoniens pour m = 3, parmi lesquels exactement 1012 se généralisent en cycles hamiltoniens pour m = 5. De plus, exactement 996 d'entre eux se généralisent en cycles hamiltoniens à la fois pour m = 5 et m = 7. Et ces 996 sont en fait généralisables à tous les m impairs > 1.
Maintenant, voici le point essentiel : Disons qu'une décomposition est "à la Claude" si elle peut être générée par un programme C comme celui ci-dessus, dans lequel les permutations d de {0,1,2} ne dépendent que du fait que i, j et s sont 0 ou m-1 ou non. Aucun cas spécial autre que 0 et m-1 n'est autorisé à affecter le choix de d.
Théorème. Une décomposition à la Claude est valide pour tout m impair > 1 si et seulement si chacune des trois séquences qu'elle définit pour m = 3 est généralisable.
Preuve. Si ces trois séquences ne sont pas hamiltoniennes, ou si elles ne se généralisent pas en cycles hamiltoniens pour tout m impair > 1, elles ne définissent certainement pas une décomposition valide. Réciproquement, si ce sont des cycles hamiltoniens qui se généralisent en cycles hamiltoniens pour tout m impair > 1, elles sont certainement valides : Chaque sommet ijk apparaît dans chacun des trois cycles, et ses trois arcs sortants sont partitionnés correctement car d est une permutation.
En mettant en place un problème de couverture exacte, en utilisant les 11502 cycles hamiltoniens pour m = 3, nous pouvons déduire qu'il y a exactement 4554 solutions au problème de décomposition 3 × 3 × 3. Et de la même manière, si nous étudions toutes les façons de couvrir chaque arc en utilisant seulement trois des 996 cycles qui sont généralisables, nous trouvons qu'exactement 760 de ces 4554 solutions n'impliquent que des cycles généralisables – environ une sur six. Par conséquent, le théorème nous dit qu'exactement 760 décompositions à la Claude sont valides pour tout m impair > 1.
Peut-être que la décomposition que Claude a trouvée n'était pas la "plus belle" de ces 760. Pouvons-nous faire mieux ? J'en ai examiné plusieurs et j'ai constaté qu'elles ont des comportements quelque peu différents. Cependant, je n'en ai rencontré aucune qui était réellement plus agréable.
La dépendance en i, j et s signifie que ces décompositions n'ont pas de symétrie cyclique. J'ai néanmoins remarqué, à ma surprise, que 136 des 760 cycles généralisables 3 × 3 × 3 restent généralisables quand on applique la permutation circulaire ijk ↦ jki. Cependant, aucun n'est commun aux trois applications {ijk, jki, kij}.
Filip m'a dit que les explorations rapportées ci-dessus, bien qu'ultimement fructueuses, n'ont pas été vraiment fluides. Il a dû faire quelques redémarrages quand Claude s'arrêtait sur des erreurs aléatoires ; puis certains des résultats de recherche précédents étaient perdus. Après chaque exécution de deux ou trois programmes de test, il devait rappeler à Claude, encore et encore, qu'il était censé documenter soigneusement ses progrès.
Le succès délicieux pour m impair, à l'exploration numéro 31, est survenu environ une heure après le début de la session.
Ce problème de décomposition reste ouvert pour les valeurs paires de m. Le cas m = 2 a été prouvé impossible il y a longtemps [1]. Dans le cadre de l'exploration numéro 24, Claude a dit qu'il avait trouvé des solutions pour m = 4, m = 6, et m = 8 ; pourtant, il n'a vu aucun moyen de généraliser ces résultats.
Filip m'a également dit qu'il a demandé à Claude de continuer sur le cas pair après que le cas impair ait été résolu. "Mais passé ce point, après un certain temps, il a semblé se bloquer. Finalement, il n'était même plus capable d'écrire et d'exécuter correctement des programmes d'exploration, très étrange. J'ai donc arrêté la recherche."
Dans l'ensemble, cependant, c'était définitivement une histoire à succès impressionnante. Je pense que l'esprit de Claude Shannon est probablement fier de savoir que son nom est maintenant associé à de telles avancées. Chapeau bas à Claude !
Le deuxième cycle de Claude (c = 1) est régi par les règles suivantes :
Nous pouvons montrer que les sommets avec s = 0 sont vus dans l'ordre suivant, pour k = 0, 1, ..., m-1 : 0k(-k), (-2)(1+k)(1-k), (-4)(2+k)(2-k), ..., 2(-1+k)(-1-k). Et cela établira l'ordre dans lequel les sommets avec s = 1, 2, ..., m-1 sont vus.
Le troisième cycle de Claude (c = 2) est régi par des règles un peu plus complexes :
Les sommets avec s = 0 et j < m-1 sont vus dans l'ordre suivant : 0j(-j), 2j(-2 - j), 4j(-4 - j), ..., (-2)j(2 - j). Et les successeurs de ce dernier sommet sont (-1)j(2 - j), (-1)(j+1)(2 - j), (-1)(j+2)(2 - j), ..., (-1)(j-2)(2 - j), 0j(-2)(2 - j).
Mais les sommets avec s = 0 et j = m-1 sont vus ainsi : 0(-1)1, 1(-1)0, 2(-1)(-1), ..., (-1)(-1)2. Et les successeurs de ce dernier sommet sont (-1)(-1)3, (-1)03, (-1)13, ..., (-1)(-3)3, 0(-(-1)(-3)3, 0(-3)3.
Ainsi, dans chaque cas, la séquence de m sommets pour s = 0 et un j donné est suivie par la séquence pour s = 0 et j-2, modulo m.
Le 3 mars, Stappers m'a écrit ceci : "L'histoire a une petite suite. J'ai remis Claude Opus 4.6 au travail sur les cas m = pairs pendant environ 4 heures hier. Il a fait quelques progrès, mais pas de solution complète. Le programme final ... met en place une construction partielle par fibres similaire au cas impair, puis lance une recherche pour tout ajuster. ... Claude a passé la dernière partie du processus principalement à accélérer la recherche plutôt qu'à chercher une construction réelle. ... Il exécutait de nombreux programmes essayant de trouver des solutions en utilisant le recuit simulé ou le retour arrière. Après que j'aie suggéré d'utiliser ORTools CP-SAT [partie de la boîte à outils open source de Google, avec la contrainte AddCircuit] pour trouver des solutions, les progrès ont été meilleurs, car des solutions pouvaient désormais être trouvées en quelques secondes." Ce programme est [4].
Puis le 4 mars, un autre ami – Ho Boon Suan à Singapour – a écrit ceci : "J'ai du code généré par gpt-5.3-codex qui génère une décomposition pour les m pairs ≥ 8. ... Je l'ai testé pour tous les m pairs de 8 à 200 et un tas de valeurs paires aléatoires entre 400 et 2000, et cela semble bon. Il semble bien plus chaotique de prouver l'exactitude à la main ici cependant ; le motif est bien plus complexe." Ce programme est [5]. (Ouah. Le graphe pour m = 2000 a 8 milliards de sommets !)
Kevin Buzzard vient de me dire que Kim Morrison, de la communauté Lean, a rapidement formalisé ma preuve que la construction de Claude est correcte. En effet, Kim avait déjà mis en ligne sa vérification le 4 mars [6]. C'est bon à savoir, car je deviens plus sujet aux erreurs ces derniers temps.
Sur un autre front, Maximilian Reitbauer, alias "Exocija", a trouvé une nouvelle construction pour m impair qui est probablement la plus simple possible, du point de vue du calcul, bien qu'elle n'ait peut-être pas la preuve la plus simple : On peut obtenir une décomposition valide en remplaçant les lignes 8-10 du programme C par
remarquez que cette solution n'utilise que s et j, pas i. De plus, la permutation identité "012" est utilisée à presque chaque étape ! (J'aurais trouvé cette solution moi-même si j'avais pris le temps d'examiner attentivement les 760 solutions généralisables pour m = 3, car celle-ci est la #369 sur cette liste.) Il m'a dit le 6 mars qu'il a trouvé sa preuve [7] en faisant des copier-coller entre GPT 5.4 (Extended Thinking) et Claude 4.6 Sonnet (Thinking).
Le problème pour les valeurs paires de m n'est plus en doute ! D'abord, j'ai eu à nouveau des nouvelles de Ho Boon Suan, qui a exercé le nouveau GPT-5.4 Pro comme suit :
"Votre tâche est de prouver rigoureusement que l'algorithme donné dans [5] produit toujours trois cycles de longueur m³ chacun quand m est un nombre pair ≥ 8. Il serait bon de donner un aperçu de pourquoi cet algorithme fonctionne, ainsi que s'il existe des constructions plus simples. Pour le contexte, voir."
Le résultat fut un article de 14 pages magnifiquement formaté et apparemment impeccable [8], contenant l'exposé et la preuve souhaités. Ho affirma que cela était entièrement l'œuvre de la machine ; il n'avait eu à éditer l'article d'aucune manière. Et le compte-rendu fascinant de l'intégralité de l'interaction avec GPT-5.4 Pro est disponible en ligne [9].
Finalement, j'ai eu des nouvelles de Keston Aquino-Michaels, qui a mené ces études à une conclusion appropriée et les a fidèlement consignées dans [10]. Comme Reitbauer, il a interagi avec deux agents LLM partageant des données et possédant des compétences complémentaires, à savoir GPT et Claude. Le résultat fut une autre décomposition valide pour le cas de m impair, accompagnée d'une décomposition élégante pour le cas de m pair, considérablement plus simple que [5]. Entre autres, il a mis en lumière une référence pertinente [11] que j'avais manquée (bien qu'elle ne résolve pas le problème de décomposition).
Mieux encore, son article [12] inclut une analyse minutieuse du fonctionnement de cette interaction conjointe, avec des implications potentiellement significatives sur la manière dont de nouveaux problèmes pourront être abordés et résolus à l'avenir.
Cher lecteur, j'espère que vous avez pris au moins autant de plaisir à lire cette histoire que j'en ai eu à l'écrire. Nous vivons vraiment une époque passionnante.
Mais je vous en prie, ne m'écrivez pas pour partager vos réflexions sur les sujets abordés ici. Travaillez autant que possible avec des chercheurs partageant les mêmes idées, mais sans me mettre dans la boucle !
Je dois absolument retourner à l'écriture de [3], qui contiendra bientôt d'autres histoires d'un tout autre genre, des histoires pour lesquelles je suis bien plus qualifié que pour écrire sur les grands modèles de langage.
Que la force soit avec vous.