Problème des Cap Set

Les 9 points et 12 lignes de $\mathbb {Z} _{3}^{2}$, et un Cap Set à 4 éléments (les quatre points jaunes) dans cet espace

En géométrie affine, un Cap Set est un sous-ensemble de l'espace affine $\mathbb {Z} _{3}^{n}$ (l' espace affine de dimension n sur le corps à trois éléments), où aucune somme de trois éléments ne représente le vecteur nul. Le Cap Set Problem consiste à déterminer le cardinal maximal d'un Cap Set, en fonction de $n$. Ces premières tailles de Cap Set sont 1, 2, 4, 9, 20, 45, 112, ... (suite A090245 de l'OEIS).

Exemple

Le jeu entier de SET, isomorphe à $\mathbb {Z} _{3}^{4}$. En considérant tout groupe de 3x3 cartes comme un plan aligné dans un espace de dimension 4, un set est une droite dans l’espace ainsi formé, en pouvant « dépasser par le bord » (comme dans Pac-man). Surlignées en jaune, 20 cartes formant un Cap Set maximal.

Un exemple de Cap Set émerge du jeu de cartes Set, où chaque carte possède quatre caractéristiques (son numéro, son symbole, son remplissage et sa couleur), chacune prenant une valeur parmi trois possibles. Les cartes de ce jeu peuvent être vues comme des points de l'espace affine à quatre dimensions $\mathbb {Z} _{3}^{4}$, où chaque coordonnée d'un point correspond à la valeur d'une des caractéristiques. Une droite de $\mathbb {Z} _{3}^{4}$ est un triplet de cartes qui, pour chaque caractéristique, sont toutes identiques ou toutes différentes. On appelle ces droites des "Sets". Le jeu consiste à trouver des sets, c'est-à-dire, parmi les cartes actuellement face visible, un triplet de cartes tel que décrit plus haut. Un Cap Set est un ensemble de cartes tel qu'aucun tel triplet ne puisse être trouvé.

Une façon de construire un grand Cap Set dans le jeu de cartes serait de choisir une des trois valeurs pour chacune des 4 caractéristiques, et de placer face visible toutes les cartes n'en utilisant aucune des 4. On obtient ainsi un Cap Set de 16 cartes. Plus généralement, la même stratégie conduirait à des Cap Set de cardinal $2^{n}$dans $\mathbb {Z} _{3}^{n}$. Cependant, en 1970, Giuseppe Pellegrino a prouvé que les Cap Set en quatre dimensions ont un cardinal maximal de 20. En termes de cartes, cela signifie qu'il existe des dispositions de 20 cartes ne contenant pas de Set, mais que chaque ensemble de 21 cartes en contient au moins un. Les dates sont correctes: le résultat prouvé par Pellegrino en 1970 est bien antérieur à la sortie du jeu Set en 1974.)

Taille maximale

Depuis la preuve de Pellegrino en 1971 et le travail de Tom Brown et Joe Buhler, qui ont prouvé en 1984 que les Cap Sets ne peuvent pas représenter une proportion constante de l'espace entier,des avancées significatives sur leur taille ont été entreprises et de nombreux résultats ont été prouvés.

Bornes inférieures

Le résultat de Pellegrino pour le Cap Set Problem de dimension 4 amène à des bornes inférieures plus grandes que $2^{n}$ en dimension supérieure, résultat ensuite amélioré en $2.2173^{n}$ par Edel (2004) puis en $2.2180^{n}$ par Tyrrell (2022). En Décembre 2023, une équipe de chercheurs de DeepMind (Google) ont publié un article dans lequel ils ont associé un Grand Modèle de Langage (LLM) à un évaluateur et ont réussi à améliorer la borne en $2.2202^{n}$.

Bornes supérieures

En 1984, Tom Brown et Joe Buhler ont prouvé que la taille maximale d'un Cap Set de $\mathbb {Z} _{3}^{n}$ est un $o(3^{n})$ quand $n$ grandit, et donc que les Cap Set sont de densité nulle. Péter Frankl, Ronald Graham et Vojtěch Rödl ont montré en 1987 que le résultat de Brown et Buhler découle facilement du lemme de suppression du triangle de Ruzsa - Szemerédi, et ont émis l'hypothèse de l'existence d'une constante $c<3$ de façon à ce que, pour $n$ suffisamment grand, tout Cap Set de $\mathbb {Z} _{3}^{n}$ soit de cardinal inférieur à $c^{n}$. Autrement dit, que $c$ soit telle que si une partie de $\mathbb {Z} _{3}^{n}$ est de cardinal supérieur à $c^{n}$, alors elle contient une droite affine. Cette question, nommée "Conjecture du Cap Set", est également apparue dans un article publié par Noga Alon et Moshe Dubiner en 1995. La même année, Roy Meshulam a démontré que la taille d'un Cap Set est inférieure à $2\cdot 3^{n}/n$. Michael Bateman et Nets Katz ont amélioré cette borne supérieure à $O(3^{n}/n^{1+\varepsilon })$, où $\varepsilon >0$.

Savoir si la borne trouvée par Meshulam peut être améliorée en $c^{n}$ où $c<3$ a été vu comme l'un des problèmes ouverts les plus questionnants de la combinatoire Additive et de la théorie de Ramsey pendant plus de 20 ans. On peut le voir, par exemple, à travers des articles à propos du Cap Set Problem publiés sur les blogs des lauréats de la médaille Fields Timothy Gowers et Terence Tao. Dans son article, Tao en parle comme de « peut-être [s]on problème ouvert préféré » et donne une ébauche de preuve de la borne exponentielle sur les Cap Set, à savoir que pour toute puissance première $p$, un sous-ensemble $S\subset F_{p}^{n}$ qui ne contient aucune progression arithmétique de longueur $3$ a une taille au plus $c_{p}^{n}$, où $c_{p}<p$.

La conjecture du Cap Set a été résolue en 2016 grâce à un enchaînement d'avancées dans la méthode polynomiale. Ernie Croot, Vsevolod Lev et Péter Pál Pach ont sorti une prépublication sur le problème proche de sous-ensembles de $\mathbb {Z} _{4}^{n}$ sans progression arithmétique, et leur méthode a été réutilisée par Jordan Ellenberg et Dion Gijswijt pour trouver une borne supérieure égale à $2.756^{n}$ sur les tailles maximales de Cap Set. En 2019, Sander Dahmen, Johannes Hölzl et Rob Lewis ont formalisé la preuve de cette borne supérieure grâce au logiciel d'aide à la preuve Lean.

En octobre 2025, la borne supérieure d'Ellenberg et Gijswijt n'a pour l'instant vu aucune amélioration exponentielle. Jiang a montré qu'en étudiant en détail les coefficients multinomiaux de la preuve d'Ellenberg et Gijswijt, on peut améliorer le résultat d'un facteur ${\sqrt {n}}$. Ce gain existe pour des raisons analogues au fait que ${1/{\sqrt {n}}}$ soit un facteur dans le coefficient binomial central.

Cap Sets Disjoints

En 2013, cinq chercheurs ont conjointement publié une étude des façons dont certains espaces de petite taille (inférieure à celle de $\mathbb {Z} _{3}^{4}$ ) peuvent être partitionnés en Cap Sets disjoints. Ils ont démontré que pour $n=4$, on peut exhiber quatre Cap Sets de disjoints de taille 20 dans $\mathbb {Z} _{3}^{4}$ qui, à eux 4, recouvrent 80 points différents: le point n'appartenant à aucun des Cap Sets est appelé l'ancre de chacun de ces ensembles. C'est le point unique qui, ajouté aux 20 points d'un Cap Set, crée une droite affine. Tous les Cap Sets d'une telle famille partagent la même ancre. Les mêmes problèmes en tailles supérieures sont encore ouverts en 2025.

Applications

Conjecture du tournesol

La solution au Cap Set Problem peut également être utilisée pour prouver un cas particulier de la conjecture du tournesol: si une famille de parties d'un ensemble à n éléments n'a pas trois éléments dont les trois intersections deux-à-deux sont égales, alors le cardinal de ladite famille est au plus $c^{n}$ où $c<2$.

Algorithmes de multiplication de matrices

Les bornes supérieures sur la taille des Cap Sets induisent des bornes inférieures sur les temps d'exécution de certains algorithmes de multiplication de matrices.