LA CONJECTURE DES TOURNESOLS TOMBE
Prenez les nombres de 1 à n et regardez toutes les façons d’en choisir quelques-uns : il y a 2ⁿ sous-ensembles. Choisissez maintenant quelques sous-ensembles qui partagent exactement la même partie commune, et rien d’autre. Les mathématiciens appellent cela un tournesol : la partie partagée est le cœur, et ce qui reste de chaque ensemble est un pétale qui ne touche aucun autre pétale.
Les tournesols sont un outil de base de la combinatoire. L’article cite des liens avec les limites de certains circuits logiques, le problème des « cap sets », la multiplication rapide de matrices et la théorie de l’information.
Une question de 1970
La question la plus naturelle à leur sujet remonte, selon les auteurs, à un article de Paul Erdős de 1970. Quelle taille peut atteindre une collection de sous-ensembles de {1, …, n} si aucun groupe de k de ses ensembles ne forme un tournesol ?
Dans les années 1970, Erdős et Endre Szemerédi ont conjecturé qu’une telle collection doit être exponentiellement plus petite que les 2ⁿ sous-ensembles possibles : au plus cⁿ, pour un nombre c strictement inférieur à 2.
Pendant des décennies, les meilleures bornes ne rognaient qu’un peu, jamais assez pour faire passer la base sous 2. Seul le cas à trois pétales (k = 3) était réglé, en 2016, grâce à la percée sur le problème des cap sets et à une réduction due à Alon, Shpilka et Umans.
La borne
Matija Bucić et Fankang He (université de Vienne) et Hyunwoo Lee (KAIST et Institut des sciences fondamentales, Corée du Sud) démontrent la conjecture pour tout k ≥ 3. Leur théorème principal : une collection sans tournesol à k pétales compte au plus
3 · (2 − 1/(16k³))ⁿ
membres. La base est juste sous 2, mais c’est un nombre fixe sous 2, et c’est exactement ce que demandaient Erdős et Szemerédi. Une construction de 1997 montre que, pour k grand, la vraie valeur ne peut pas être beaucoup plus basse.
Des ensembles aux vecteurs
La preuve passe par une version du problème avec des vecteurs. On découpe les nombres en n blocs de D éléments et on choisit un élément par bloc : chaque choix est un vecteur. Plusieurs vecteurs forment un tournesol quand, à chaque position, leurs valeurs sont soit toutes égales, soit toutes différentes.
Les auteurs construisent alors un « testeur de tournesol » : une fonction qui, sur une collection sans tournesol, n’est non nulle que si toutes ses entrées sont le même vecteur. L’ingrédient nouveau consiste à écrire cette fonction, pas à pas, avec des polynômes d’interpolation de faible degré. Compter ces polynômes borne la taille de la collection (leur théorème 2). Un argument probabiliste, avec des blocs tirés au hasard et une moyenne sur toutes les tailles d’ensembles, ramène la borne aux ensembles ordinaires.
Trouvée par une machine, contrôlée par une autre
La déclaration de l’article sur l’IA est d’une franchise inhabituelle. La preuve du théorème 2 a été trouvée par ChatGPT 6 Astra Pro, après une courte discussion qui commençait par lui demander de généraliser l’argument connu à trois pétales. Les auteurs avaient besoin de cette étape pour un autre objectif : une version « induite » d’un problème de graphes posé par Szemerédi, annoncée pour une note ultérieure.
Le modèle a écrit sa preuve dans le langage du « slice rank ». Les auteurs l’ont réécrite dans celui de la méthode polynomiale, plus abordable selon eux. Ils déclarent avoir vérifié chaque résultat et en assumer l’entière responsabilité, et précisent que la preuve a été vérifiée avec Lean 4.35, un logiciel de vérification de preuves ; la vérification sera publiée sur le dépôt Palomar.
Ce qui reste ouvert
Les auteurs n’ont pas cherché à optimiser la base. Pour trois pétales, elle ne bat pas la borne de Naslund et Sawin (2017), environ 1,89. Et le problème frère, plus fort, la conjecture des tournesols d’Erdős–Rado, reste ouvert : leurs bornes dépendent encore fortement de la taille des blocs D, exactement ce que ce problème interdit.