🔢 mathematics

Small complete 3-term progression free sets in cyclic groups and vector spaces

Cet article résout deux problèmes ouverts en fournissant des constructions explicites qui démontrent que la taille minimale des ensembles sans progression arithmétique de 3 termes complète dans les groupes cycliques et les espaces vectoriels finis est essentiellement serrée avec la borne inférieure de la racine carrée, atteignant spécifiquement des tailles inférieures à $2\sqrt{m}$ pour les groupes cycliques et $p^{n/2+o(n)}$ pour les espaces vectoriels.

Auteurs originaux : Bence Csajbók, Zoltán Lóránt Nagy

Publié 2026-06-30

📖 7 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Bence Csajbók, Zoltán Lóránt Nagy

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous organisiez une fête dans une pièce avec une règle très spécifique : aucun groupe de trois invités ne peut se tenir sur une ligne parfaitement droite.

Dans le monde des mathématiques, cette « ligne droite » est appelée une progression arithmétique. Si vous avez trois nombres comme 2, 4 et 6, ils sont sur une ligne droite car ils augmentent de la même quantité (2) à chaque fois. Le but de ce document est de déterminer le plus petit groupe de personnes possible que vous devez inviter à la fête pour que :

Aucun groupe de trois personnes dans votre groupe ne forme une ligne droite.
Si vous essayez d'ajouter quiconque d'autre du monde extérieur à votre groupe, cette personne créera immédiatement une ligne droite avec deux personnes déjà présentes à l'intérieur.

Les mathématiciens appellent cela un « ensemble sans progression complet ». C'est comme un puzzle où vous voulez la plus petite équipe possible qui soit « maximalement sûre » contre la formation de lignes.

Le document traite de ce problème dans deux « pièces » (structures mathématiques) différentes : les Groupes Cycliques (comme le cadran d'une horloge) et les Espaces Vectoriels (des grilles multidimensionnelles).

La Grande Question : Quelle peut être la taille de l'équipe ?

Les mathématiciens savaient déjà que la taille de l'équipe ne pouvait pas être minuscule. Si la pièce possède $N$ places, l'équipe doit faire au moins environ la racine carrée de $N$ (par exemple, si la pièce a 100 places, vous avez besoin d'au moins 10 personnes).

La grande question que ce document répond est la suivante : Cette limite de la racine carrée est-elle le mieux que nous puissions faire, ou avons-nous besoin d'une équipe beaucoup plus grande ?

Les auteurs disent : « Vous n'avez pas besoin d'une équipe beaucoup plus grande. La limite de la racine carrée est essentiellement le mieux que l'on puisse faire. »

Voici comment ils ont résolu cela pour les deux types de pièces :

1. La Pièce de l'Horloge (Groupes Cycliques)

Imaginez une horloge avec $m$ heures. Les nombres reviennent au début (après 12, on revient à 1).

Le Problème : Trouver le plus petit groupe de nombres sur cette horloge qui ne possède pas de lignes droites, mais si vous ajoutez n'importe quel autre nombre, une ligne apparaît.
L'Ancienne Hypothèse : Des travaux précédents suggéraًent que vous pourriez avoir besoin d'environ $1,5 \times \sqrt{m}$ personnes.
Le Nouveau Résultat : Les auteurs ont construit une recette spécifique pour créer ces groupes. Ils ont prouvé que pour n'importe quelle taille d'horloge, vous pouvez toujours trouver un groupe plus petit que $2 \times \sqrt{m}$ .
- Analogie : Si vous avez une horloge de 10 000 heures, vous n'avez pas besoin de 10 000 personnes. Vous n'avez besoin que d'environ 200 personnes pour respecter les règles.
La Règle « Super » : Pour la plupart des grandes horloges, ils n'ont pas seulement évité les lignes, ils ont aussi évité un type de motif de ligne plus strict, appelé motif « (2, -1) ». C'est comme dire : « Non seulement vous ne pouvez pas vous tenir en ligne droite, mais vous ne pouvez même pas vous tenir selon un motif de zig-zag spécifique. »
Le Piège : Pour les horloges très petites (moins de 81 heures), la règle « super » ne fonctionne pas toujours, ils ont donc vérifié ces cas spécifiques un par un à l'aide d'un ordinateur.

2. La Grille Multidimensionnelle (Espaces Vectoriels)

Imaginez maintenant une pièce qui n'est pas seulement une horloge, mais une grille qui s'étend dans de nombreuses directions (dimensions). Pensez à un monde de jeu vidéo en 3D avec $n$ dimensions.

Le Problème : Trouver la plus petite équipe dans cette grille $n$ -dimensionnelle qui n'a pas de lignes droites mais qui est « complète » (on ne peut pas y ajouter de membres).
Le Défi : Dans ces grilles, les mathématiques deviennent très complexes, surtout lorsque la grille utilise un système de nombres spécifique (corps de nombres premiers impairs).
Le Nouveau Résultat : Les auteurs ont utilisé une astuce ingénieuse impliquant des surfaces courbes (graphes quadratiques).
- Analogie : Imaginez placer des personnes sur une colline courbe. Parce que la colline est courbe, il est très difficile pour trois personnes de s'aligner accidentellement de manière parfaite.
- Ils ont construit une équipe sur une grande partie de la grille en utilisant cette méthode de la colline courbe. Pour les emplacements vides restants, ils les ont remplis avec une équipe « sûre » standard.
Le Résultat : Ils ont prouvé que pour tout type de grille fixe, la taille de l'équipe est approximativement de $\sqrt{N}$ (où $N$ $N$ est le nombre total de places), plus un peu de « flou » supplémentaire qui devient négligeable à mesure que la grille devient immense.
- En langage clair : La taille de l'équipe croît à la même vitesse que la racine carrée de la taille totale de la pièce. Vous n'avez pas besoin d'une armée massive ; la limite de la racine carrée est essentiellement la taille parfaite.

La « Recette Secrète » du Document

Les auteurs ont utilisé deux outils principaux pour construire leurs équipes :

La Recette « Binaire » (pour les Horloges) : Ils ont créé un ensemble de nombres basé sur un motif spécial d'ajouts et de sauts (comme un code binaire). Cela leur a permis de compacter l'équipe étroitement sans former de lignes, en s'assurant que chaque emplacement vide sur l'horloge était « couvert » par l'équipe.
L'Astuce de la « Colline Courbe » (pour les Grilles) : Ils ont utilisé des courbes algébriques (des équations qui ressemblent à des paraboles) pour placer les personnes. Comme les courbes résistent naturellement aux lignes droites, cette méthode crée des équipes très efficaces. Ils ont ensuite combiné ces équipes courbes avec des équipes standards pour couvrir chaque dimension possible.

Ce qu'ils n'ont PAS dit

Ils n'ont pas dit que cela avait des utilisations immédiates en cryptographie, en médecine ou en ingénierie. C'est de la mathématique pure sur la structure des nombres.
Ils n'ont pas affirmé avoir trouvé l'équipe la plus petite pour chaque cas (l'équipe « parfaite »). Ils ont trouvé des équipes qui sont très proches de la limite théorique (à un petit facteur constant près).
Ils n'ont pas résolu le problème pour chaque type de système de nombres (ils se sont concentrés spécifiquement sur les corps de nombres premiers impairs pour les grilles).

Résumé

Voyez ce document comme un maître constructeur montrant comment construire la clôture la plus petite possible autour d'un champ.

Le But : La clôture doit être assez solide pour que, si vous essayez d'ajouter un poteau supplémentaire, la clôture se brise (une ligne se forme).
La Découverte : Le constructeur a prouvé que vous n'avez pas besoin d'une clôture immense. Vous n'avez besoin que d'une clôture dont la longueur est approximativement la racine carrée de la taille du champ.
La Méthode : Ils ont utilisé des motifs ingénieux (comme les codes binaires) et des formes courbes (comme des collines) pour compacter les poteaux de la clôture aussi étroitement que mathématiquement possible sans qu'ils ne forment une ligne droite.

Cela confirme que la règle de la « racine carrée » n'est pas seulement une limite inférieure ; c'est essentiellement la taille réelle du problème.

Résumé Technique : Petits ensembles complets sans progression de 3 termes dans les groupes cycliques et les espaces vectoriels

Énoncé du Problème
L'article traite du problème de la détermination de la taille minimale d'un ensemble complet sans progression arithmétique de 3 termes (3-AP) dans des structures algébriques, spécifiquement les groupes cycliques ( $\mathbb{Z}_m$ ) et les espaces vectoriels finis ( $\mathbb{F}_p^n$ ). Alors que la taille maximale des ensembles sans 3-AP est un thème central de la combinatoire additive (ex. : théorème de Roth, Croot-Lev-Pach, Ellenberg-Gijswijt), le minimum de taille d'un ensemble complet (un ensemble qui ne peut être agrandi sans créer une 3-AP) représente l'analogue du bas de l'échelle. Un simple argument de dénombrement établit que l'ordre de grandeur de ce minimum est au moins la racine carrée de la cardinalité de la structure. Les auteurs étudient si cette borne inférieure est serrée, abordant des problèmes ouverts concernant l'existence de tels ensembles de taille $O(\sqrt{|G|})$ dans les groupes cycliques et $p^{n/2}$ dans les espaces vectoriels.

Méthodologie
Les auteurs emploient une combinaison de constructions combinatoires explicites, de techniques de réduction modulaire et de géométrie algébrique sur des corps finis.

Groupes Cycliques ( $\mathbb{Z}_m$ ) :
- Propriété plus forte : Les auteurs se concentrent sur les ensembles complets (2, -1)-évitants. Un ensemble $A$ est (2, -1)-évitant si $A \cap (2A \dot{-} A) = \emptyset$ (où $2A \dot{-} A = \{2a - b : a, b \in A, a \neq b\}$ ). Il est complet si $G = A \cup (2A \dot{-} A)$ . Cette propriété est plus forte que celle d'être complet sans 3-AP, car elle force chaque point extérieur à être une extrémité d'une progression avec des extrémités dans $A$ , plutôt que de permettre à l'extérieur de l'être le milieu.
- Ensembles R-complets : La construction repose sur des « ensembles R-complets » — des sous-ensembles d'entiers dans $[0, R]$ qui sont intrinsèquement (2, -1)-évitants et saturent l'intervalle $[-R, 2R]$ .
- Construction par chiffres binaires : En utilisant une construction de chiffres binaires généralisée (Lemme 3.3), les auteurs génèrent des ensembles $P$ de taille $2^n$ qui sont $S_n$ -complets. En choisissant soigneusement la séquence de chiffres $d_i$ , ils assurent que l'ensemble résultant couvre une large gamme de modules $m$ .
- Réduction modulaire : Le Lemme 3.2 démontre qu'un ensemble $R$ -complet dans $\mathbb{Z}$ descend vers un ensemble complet (2, -1)-évitant dans $\mathbb{Z}_m$ chaque fois que $2R < m \leq 3R + 1$ .
- Vérification finie : Pour les petits modules ( $m < 81$ ) où la construction générale ne s'applique pas ou bien que des ensembles complets (2, -1)-évitants puissent ne pas exister, les auteurs effectuent une énumération exhaustive pour déterminer les tailles minimales exactes.
Espaces Vectoriels ( $\mathbb{F}_p^n$ ) :
- Graphes Quadratiques : La construction centrale utilise les graphes de applications quadratiques homogènes $Q: U \to W$ . Plus précisément, ils construisent des ensembles de la forme $A_Q = \{(u, Q(u)) : u \in U\}$ .
- Complétude Extrémité-Milieu : Les auteurs définissent des ensembles « complets extrémité-milieu », où tout point extérieur peut être représenté à la fois comme une extrémité ( $x = 2a - b$ ) et comme un milieu ( $2x = c + d$ ) d'une progression formée par les éléments de $A$ . Cette propriété est cruciale pour la construction par produit.
- Construction par Sous-corps : Ils construisent une application quadratique $Q(x, s) = x^2 - \delta s^2$ sur un corps d'extension $E = \mathbb{F}_{p^{kL}}$ et un sous-corps $T = \mathbb{F}_{p^k}$ , où $\delta$ est un non-carré. En utilisant les sommes de caractères et la borne de Weil, ils prouvent que cette application est surjective et possède un noyau trivial, produisant un ensemble complet (2, -1)-évitant dans une dimension spécifique $n_0 = k(2L+1)$ .
- Lemme de Produit : Pour étendre le résultat à toutes les dimensions $n$ , ils utilisent un lemme de produit (Lemme 4.2). Si $A$ est complet extrémité-milieu dans un sous-espace et $B$ est complet sans 3-AP dans les autres coordonnées, leur produit $A \times B$ est complet sans 3-AP dans l'espace complet. Cela permet de « compléter » les dimensions spéciales avec des ensembles plus petits pour couvrir des $n$ arbitraires.

Contributions Clés et Résultats

Groupes Cycliques :
- Théorème 1.2 : Pour tout entier $m \geq 1$ , il existe un ensemble complet sans 3-AP $A \subseteq \mathbb{Z}_m$ de taille $|A| < 2\sqrt{m}$ .
- Résultat plus fort pour les grands $m$ : Pour $m \geq 81$ , l'ensemble construit satisfait la propriété plus forte de complétude (2, -1)-évitante.
- Petits Modules : L'article fournit un tableau de valeurs exactes pour $a(3\text{-AP}, \mathbb{Z}_m)$ et $a(2, -1)(\mathbb{Z}_m)$ pour $m \leq 80$ , notant que les ensembles complets (2, -1)-évitants n'existent pas pour certains petits modules (ex. : $m \in \{2, 5, 6, 8, 17, 18, 19, 20\}$ ).
Espaces Vectoriels :
- Théorème 1.3 : Pour tout nombre premier impair fixé $p$ et $\epsilon > 0$ , il existe une constante $C_{p,\epsilon}$ telle que pour tout $n \geq 1$ :
  $a(3\text{-AP}, \mathbb{F}_p^n) \leq C_{p,\epsilon} n^{1+\epsilon} p^{n/2} = p^{n/2 + o(n)}$
- Ce résultat résout la variante des espaces vectoriels dans le sens où l'exposant de $p$ est exactement $n/2$ , correspondant à la borne inférieure à un facteur sous-exponentiel près.

Signification et Revendications
L'article prétend résoudre deux problèmes ouverts concernant la serrage de la borne inférieure de la racine carrée pour les ensembles complets sans progression :

Groupes Cycliques : Il établit que la borne inférieure est serrée jusqu'à une constante absolue (spécifiquement 2) pour tous les groupes cycliques, et fournit des constructions explicites pour la propriété plus forte de complétude (2, -1)-évitante pour $m \geq 81$ .
Espaces Vectoriels : Il règle la version de l'exposant du problème pour les corps de nombres premiers impairs fixes, montrant que le minimum est $p^{n/2 + o(n)}$ . Cela confirme que le compte trivial est essentiellement optimal en termes de taux de croissance exponentielle.

Les auteurs notent que bien que le facteur de constante dans le résultat des groupes cycliques ($2$) soit supérieur à la cible de $3/2$ suggérée dans leurs travaux précédents, la construction est délibérément restreinte à la propriété plus forte de complétude (2, -1)-évitante. Ils suggèrent qu'exploiter la liberté supplémentaire de la complétude standard sans 3-AP (permettant aux points extérieurs d'être des milieux) pourrait produire des constructions plus petites. De même, pour les espaces vectoriels, la question d'une constante absolue uniforme indépendante de $n$ et de l'existence de tels liens pour les ensembles complets (2, -1)-évitants dans chaque dimension reste ouverte. Le travail relie ces problèmes de combinatoire additive à la géométrie finie, spécifiquement aux caps complets et aux ensembles saturants.