22 MULTIPLICATIONS, PAS UNE DE MOINS

Conflit d’intérêts. Les auteurs déclarent que des agents d’IA — Claude, d’Anthropic — ont écrit le code de recherche et les preuves Lean qui n’ont pas besoin d’un auditeur humain, sous leur direction, la partie qu’un humain doit vérifier ayant été conçue par les auteurs. Cet article est lui aussi rédigé par Claude.

Multiplier deux grilles carrées de nombres — des matrices — à la manière de l’école demande n³ multiplications pour des grilles de n lignes et n colonnes. Strassen a montré que deux matrices 2 × 2 se multiplient avec 7 multiplications au lieu de 8. L’astuce s’applique récursivement : on coupe une grande matrice en quatre blocs, on traite chaque bloc comme un seul nombre, et on recommence. Le coût croît alors comme n^2,807 au lieu de n³. Selon l’article, cette recette 2 × 2 a été prouvée optimale en 1971.

La même idée marche pour toute taille fixe. Une recette qui multiplie deux matrices 3 × 3 avec r multiplications, et qui marche encore quand les entrées sont des blocs, donne un coût qui croît comme n puissance log₃ r. Un calcul simple fixe l’enjeu : une telle recette bat Strassen exactement quand r vaut 21 ou moins, et perd à 22 ou plus. La meilleure recette 3 × 3 connue, due à Laderman, utilise 23 multiplications et n’a pas été améliorée depuis 1976.

Une porte restée entrouverte

Le meilleur nombre possible pour un problème donné s’appelle son rang. Les bornes inférieures du rang de la multiplication 3 × 3 ont progressé lentement : 19 en 2003, puis 20 en mars 2026, calculé par Wang dans un minuscule système de nombres réduit à 0 et 1, où 1 + 1 = 0. En septembre 2026, Wang et une équipe menée par Yang ont atteint 21 indépendamment, à dix jours d’intervalle. Mais 21 laissait encore la place à une recette 3 × 3 plus rapide que celle de Strassen.

Isaac Rudich, de Polytechnique Montréal et de l’université Carnegie Mellon, et Louis-Martin Rousseau, de Polytechnique Montréal, ont maintenant porté la borne à 22.

Théorème 1. Tout algorithme qui multiplie deux matrices 3 × 3 avec des constantes entières, et qui peut s’appliquer récursivement à des blocs de toute taille, utilise au moins 22 multiplications.

Aucun algorithme de ce type ne peut donc faire mieux qu’environ n^2,814 — et aucun ne peut battre la méthode 2 × 2 de Strassen.

496 énigmes plus petites

La preuve s’appuie sur une table imaginée par Wang, qui découpe le problème difficile en 496 problèmes plus faciles. Chacun ajoute des « conditions » sur la première matrice — par exemple, que certaines de ses entrées s’additionnent à zéro. Plus il y a de conditions, plus le problème est facile, jusqu’au cas trivial où la matrice ne contient que des zéros.

Les auteurs ont d’abord construit un programme de recherche exacte qui leur donnait la vraie réponse de chaque énigme avant qu’ils tentent de la prouver. Ces réponses ont servi de carte : elles montraient quelles bornes inférieures valaient la peine d’être poursuivies. Au final, leur preuve borne les 496 énigmes, en règle 359 exactement — contre 195 dans les derniers résultats de Wang — et relève la borne inférieure de 252. Un théorème de « collage » de leur cru combine les recettes de deux énigmes plus faciles en une recette pour une troisième ; il a fourni 145 des bornes supérieures.

Deux conditions comptent dans l’énoncé final. Constantes entières : une recette à constantes entières, lue dans le système à 0 et 1, reste une recette valable sans multiplication supplémentaire, donc la borne se transporte. Blocs : sans cette exigence, des raccourcis existent. L’algorithme 3 × 3 de Rosowski, cité dans l’article, n’utilise que 21 multiplications, mais il repose sur le fait que les nombres commutent et ne peut pas s’appliquer récursivement.

Une preuve vérifiée par une machine

La preuve est écrite en Lean, un langage de programmation dans lequel un théorème ne compile que si chaque étape est vérifiée. La preuve complète fait environ un million de lignes réparties en 3 521 modules, et sa vérification prend 11,1 heures sur un seul cœur de processeur. Personne n’a besoin de tout lire. Un auditeur lit une bibliothèque d’environ 1 000 lignes, écrite par les auteurs avant qu’aucune preuve n’existe, qui définit ce qu’est une recette de multiplication et énonce le théorème ; le noyau de Lean vérifie le reste, et un vérificateur indépendant peut rejouer le résultat.

Les auteurs signalent aussi que les agents d’IA ont fouillé la littérature : ils ont vérifié que chaque référence existe, « mais pas que chacune contient exactement l’idée qu’on lui attribue ».

Le dernier écart

Une question demeure : existe-t-il une recette 3 × 3 à 22 multiplications, ou les 23 de Laderman sont-elles le vrai minimum ? Les auteurs s’attendent à ce que l’écart soit comblé « de façon imminente », et publieront leur code de recherche à ce moment-là, ou quand l’article sera accepté pour publication. La borne laisse aussi de côté les recettes à constantes non entières.