← L'année où l'IA change les maths

Cap sets : quand ce sont les humains qui ont eu l'éclair

L'essence du problème

Dans l'espace F₃ⁿ — les suites de n symboles valant 0, 1 ou 2 — une « droite » est un triplet de points dont la somme, coordonnée par coordonnée, est nulle modulo 3. Un cap set est un ensemble de points ne contenant aucune droite. Les joueurs de SET connaissent ce problème sans le savoir : les cartes du jeu vivent dans F₃⁴, une « droite » y est exactement un set valide, et le plus grand paquet de cartes sans set compte 20 cartes. L'illustration montre la dimension 3 : les trois grilles sont les trois couches d'un cube 3×3×3, les 9 points bleus forment un cap maximal (calculé pour l'occasion), le pointillé rouge est une droite interdite. La grande question : quand n grandit, la taille maximale d'un cap set croît-elle comme 3ⁿ (à peine moins que tout l'espace), ou exponentiellement moins vite ? La « conjecture des cap sets » pariait sur la seconde réponse.

Les pas humains

Roy Meshulam (1995) obtient la borne 3ⁿ/n — puis plus rien pendant vingt ans, malgré l'acharnement des meilleurs combinatoriciens. En mai 2016, Ernie Croot, Vsevolod Lev et Péter Pach publient une idée neuve, la « méthode polynomiale » version croisière, sur un problème cousin. En quelques jours, Jordan Ellenberg et Dion Gijswijt, chacun de leur côté, l'adaptent aux cap sets et démontrent une borne en (2,756)ⁿ : la conjecture est résolue, par des humains, dans l'une des accélérations collectives les plus spectaculaires de l'histoire récente des mathématiques. La preuve tient en quelques pages lisibles par un étudiant.

Ce qu'a fait l'IA

L'IA est entrée par l'autre porte : la construction. En décembre 2023, FunSearch (DeepMind) — un moteur de recherche évolutionnaire dont les mutations sont proposées par un modèle de langage — découvre en dimension 8 des cap sets de 512 points, les plus grands connus, améliorant la borne inférieure du problème. C'est la première découverte mathématique nouvelle attribuée à un grand modèle de langage, et elle a un charme particulier : FunSearch ne livre pas un ensemble de points, mais un petit programme lisible qui l'engendre — un objet que les mathématiciens peuvent étudier. En 2026, de nouveaux records sur les constantes du problème sont encore tombés par IA (travaux de Hametner et Tyrrell). Le tableau d'ensemble est instructif : l'éclair conceptuel reste humain, l'IA excelle en exploratrice systématique de l'espace des exemples — et les deux se nourrissent.

Les visages

Ernie Croot Jordan Ellenberg

Portraits : Wikimédia Commons — cliquer sur un visage pour la page correspondante.

Pour aller plus loin

• Le billet de Gil Kalai à chaud, en 2016 — la semaine où tout a basculé.
• FunSearch — le billet de DeepMind (et l'article dans Nature, 2023).
• Cap set — Wikipédia (en anglais), avec l'historique des bornes.
• Past and future of the cap set problem — un survol par des spécialistes (arXiv) · copie locale (PDF, licence CC BY 4.0).