Three-color van der Waerden numbers grow super-exponentially

Résumé technique : Les nombres de van der Waerden à trois couleurs croissent de manière super-exponentielle

Énoncé du problème
L'article traite du taux de croissance des nombres de van der Waerden, notés $w(k; r)$. Ce nombre est défini comme le plus petit entier $N$ tel que toute $r$-coloration de l'ensemble $\{1, 2, \dots, N\}$ contient une progression arithmétique monochromatique de longueur $k$. Bien que l'existence de ces nombres soit garantie par le théorème de van der Waerden, leur croissance asymptotique précise demeure un problème fondamental ouvert.

Historiquement, la croissance de $w(k; r)$ a fait l'objet de spéculations intenses. Pour un $r$ fixé, Erdős a conjecturé que $w(k; 2)$ croît de manière super-exponentielle (c'est-à-dire $\limsup_{k \to \infty} w(k; 2)^{1/k} = \infty$). À l'inverse, d'autres conjectures suggéraient une croissance exponentielle linéaire, spécifiquement $\lim_{k \to \infty} w(k; r)^{1/k} = r$. Avant ce travail, les meilleures bornes inférieures connues pour $w(k; r)$ étaient largement dérivées du lemme local de Lovász ou de constructions algébriques spécifiques, produisant des bornes de la forme $w(k; r) \geq r^{k-1}/(4k)$ ou, pour un $r \geq 5$ fixé, des bornes de la forme $(3r/3)^{(1-o(1))k}$. Les auteurs notent que si un résultat précédent de Hunter [20] a infirmé la conjecture de l'exponentielle linéaire pour $r \geq 5$, le cas pour $r=3$ (et le comportement général pour de petites valeurs de $r$ fixées) restait non résolu.

Méthodologie
Les auteurs développent une nouvelle construction probabiliste pour établir des bornes inférieures pour $w(k; r)$. La méthodologie repose sur trois composantes primaires :

1. Ensembles sans progressions denses dans les groupes cycliques :
   Les auteurs construisent des sous-ensembles très denses de groupes cycliques $\mathbb{Z}_N$ qui ne contiennent pas de progressions arithmétiques de longueur $k$ ($k$-AP). Ils utilisent une extension de la construction d'Erdős-Turán (ensembles d'entiers ne possédant aucun chiffre égal à $p-1$ en base $p$) adaptée aux groupes cycliques. Crucialement, ils prouvent l'existence d'« ensembles de frappe » (Hitting Sets) (Lemme 2.8) qui sont épars (densité $\leq \epsilon$) mais qui interceptent chaque $k$-AP dans un groupe avec une fraction constante de ses éléments. Ceci est réalisé en sélectionnant des classes de congruence aléatoires modulo un ensemble de nombres premiers.

2. Conséquences du Lemme Local de Lovász (LLL) :
   L'article emploie la version symétrique du lemme local de Lovász pour démontrer l'existence de colorations où aucune classe de couleur ne contient une « grande » fraction de n'importe quelle $k$-AP. Spécifiquement, le Corollaire 3.3 établit que pour des groupes d'ordre $N$ ne possédant pas de petits facteurs premiers, on peut assigner des sous-ensembles de couleurs aux sommets de telle sorte qu'aucune $k$-AP ne soit monochromatique ou presque monochromatique.

3. Constructions par produits décalés aléatoires :
   L'innovation technique centrale est une construction raffinée de « produit décalé aléatoire » (Lemmes 4.2 et 4.3). Contrairement aux colorations de produits standards qui multiplient le nombre de couleurs, cette méthode permet aux auteurs de combiner les colorations de groupes plus petits en un groupe plus grand tout en gardant le nombre de couleurs fixe (ou en les augmentant de manière contrôlée).

• Mécanisme : Étant donné une coloration $c_1$ de $H_1$ et une coloration $c_2$ de $H_2$, la construction définit une coloration sur $H_1 \times H_2$ en décalant indépendamment les fibres de la projection sur $H_2$ et en permutant les couleurs selon la couleur de l'élément de base dans $H_1$.
• Processus itératif : Les auteurs itèrent cette construction. À chaque étape, ils combinent une coloration d'un groupe $\mathbb{Z}_{n_{j-1}}$ avec une coloration d'un groupe cyclique d'ordre premier $\mathbb{Z}_{q_j}$. La construction augmente la taille du groupe par un facteur exponentiel en $k$, tout en subissant une perte « double exponentielle » du paramètre de densité de la classe de couleur « bonne ». En équilibrant soigneusement ces paramètres, le processus peut être itéré environ $(\log^* k)/2$ fois.

Contributions clés et résultats

• Croissance super-exponentielle pour trois couleurs :
  Le résultat principal (Théorème 1) prouve que pour $k$ suffisamment grand, le nombre de van der Waerden à trois couleurs satisfait :
  $$w(k; 3) > 2^{k(\log^* k)/4}$$
  Ceci établit que $w(k; 3)$ croît plus vite que toute fonction exponentielle de $k$, infirmant ainsi la conjecture selon laquelle $\lim_{k \to \infty} w(k; r)^{1/k} = r$ pour $r \geq 3$.

• Bornes inférieures pour de nombreuses couleurs :
  Le Théorème 2 fournit une borne inférieure pour le régime où le nombre de couleurs $r$ est grand par rapport à $k$ (spécifiquement $r \geq (\log k)^{3/\epsilon}$) :
  $$w(k; r) \geq r^{(1-\epsilon)k \log k}$$
  Ceci améliore les bornes précédentes dans le régime des « nombreuses couleurs ».

• Résolution du problème d'Erdős-Graham :
  Les auteurs traitent le nombre de van der Waerden canonique $H(k)$, défini comme le plus petit $N$ tel que toute coloration de $[N]$ contienne une $k$-AP monochromatique ou arc-en-ciel (rainbow). Erdős et Graham ont conjecturé si $H(k)^{1/k}/k \to \infty$. En utilisant leur borne inférieure améliorée sur $w(k; k-1)$, les auteurs prouvent (Théorème 3) que :
  $$H(k) \geq k^{(1-o(1))k \log k}$$
  Cela confirme que $H(k)$ croît de manière super-exponentielle, résolvant le problème ouvert posé par Erdős et Graham.

Signification
L'article affirme que la croissance des nombres de van der Waerden pour trois couleurs ou plus est super-exponentielle, un résultat qui modifie fondamentalement la compréhension de ces nombres combinatoires. La signification réside dans :

1. L'infirmation de la conjecture de l'exponentielle linéaire : Il démontre définitivement que $w(k; r)$ ne se comporte pas comme $r^k$ pour $r \geq 3$.
2. Avancée méthodologique : L'introduction de la construction de « produit décalé aléatoire » permet d'itérer des arguments probabilistes tout en maintenant un nombre de couleurs fixe, une technique que les auteurs notent être plus efficace que les versions précédentes utilisées pour $r \geq 5$.
3. Théorie de Ramsey canonique : Les résultats fournissent une résolution forte du problème d'Erdős-Graham concernant les nombres de van der Waerden canoniques, montrant que même en autorisant les progressions arc-en-ciel, le $N$ requis est bien plus grand que les bornes inférieures précédemment établies.

Les auteurs notent que bien que leurs techniques soient générales, l'application spécifique ici se concentre sur l'établissement de ces bornes inférieures. Ils suggèrent que ces constructions pourraient être applicables pour obtenir de nouvelles bornes pour d'autres nombres de Ramsey arithmétiques, un sujet qu'ils ont l'intention d'explorer dans une note complémentaire. L'article ne prétend pas déterminer le taux de croissance exact ou fournir des bornes supérieures, mais établit une borne inférieure nettement plus forte que ce qui était connu précédemment.