On the largest sum-free subset of the lattice cube

1. Énoncé du problème

L'article aborde le problème de la détermination de la densité asymptotique du plus grand sous-ensemble sans somme au sein d'un cube de réseau de dimension $d$.

• Définitions : Un sous-ensemble $S$ d'un groupe abélien est sans somme s'il n'existe aucun $x, y, z \in S$ tels que $x + y = z$. Les auteurs étudient des sous-ensembles du cube de réseau $[n+1]^d = \{0, 1, \dots, n\}^d$.
• Objectif : Déterminer la limite $c_d = \lim_{n \to \infty} \frac{|S|}{n^d}$, où $S$ est le plus grand sous-ensemble sans somme.
• Contexte :
  • Pour $d=1$, il est bien connu que $c_1 = 1/2$.
  • Pour $d=2$, Elsholtz et Rackham ont prouvé que $c_2 = 3/5$.
  • Pour $d=3, 4$, Lepsveridze et Sun ont récemment résolu ces cas.
  • La Conjecture : Il a été conjecturé que pour tout $d$, l'ensemble optimal est une « tranche » du cube définie par un hyperplan. Plus précisément, l'ensemble $S^* = \{x \in [n+1]^d \mid u \le \sum x_i < 2u\}$, où $u$ est choisi pour maximiser le volume de la tranche, produit la densité maximale.
  • Soit $c^*_d$ le volume maximal d'une telle tranche dans la limite continue $[0,1]^d$. La conjecture énonce que $c_d = c^*_d$.

2. Méthodologie

La preuve suit l'approche établie par Lepsveridze et Sun, utilisant une combinaison de dualité en programmation linéaire et de couplage probabiliste (mélangeabilité conjointe).

A. Réduction à la programmation linéaire

Le problème de la borne supérieure de $|S|$ est reformulé comme un programme linéaire (PL).

• Problème primal : Maximiser $\sum |S(x)|$ (où $S(x)$ sont les fibres de l'ensemble $S$) sous la contrainte que pour tout $x, y, z$ tels que $x+y=z$, $|S(x)| + |S(y)| + |S(z)| \le 2(n+1)$.
• Problème dual : Pour trouver une borne supérieure, il faut construire une solution réalisable (poids) pour le PL dual. L'existence de tels poids repose sur la capacité à coupler des distributions de probabilité spécifiques.

B. Mélangeabilité conjointe

L'innovation technique centrale est la preuve d'un résultat de mélangeabilité conjointe.

• Définition : Des distributions $\mu_1, \mu_2, \mu_3$ sont conjointement mélangables s'il existe un couplage $(X_1, X_2, X_3)$ avec ces marginales tel que $X_1 + X_2 + X_3 = \mathbb{E}[X_1] + \mathbb{E}[X_2] + \mathbb{E}[X_3]$ presque sûrement.
• Le théorème clé (Théorème 1.5) : Les auteurs prouvent que pour tout entier non négatif $r, s, t$ tels que $r+s+t = dn$, les distributions uniformes sur les tranches discrètes $L_d(r), L_d(s), L_d(t)$ (où $L_d(k) = \{x \in [n+1]^d : \sum x_i = k\}$) sont conjointement mélangables.
• Technique de preuve :
  • Induction sur $d$ : Le cas de base $d=2$ repose sur des résultats connus concernant les intervalles et les inégalités triangulaires.
  • Étape inductive ($d \ge 3$) : Les auteurs construisent un couplage pour les premières coordonnées en utilisant un argument de point fixe (théorème du point fixe de Brouwer ou Perron-Frobenius). Ils définissent une application sur l'espace des distributions de probabilité sur le support des premières coordonnées et montrent qu'un point fixe existe. Ce point fixe garantit que les marginales correspondent aux distributions uniformes requises sur les tranches, permettant d'appliquer l'hypothèse d'induction aux $d-1$ coordonnées restantes.

C. Construction des poids et estimations des tranches

Pour appliquer la mélangeabilité conjointe au PL dual :

1. Partitionnement : Le domaine $[n+1]^{d-1}$ est partitionné en cinq ensembles ($A, B, C, D, E$) basés sur la somme des coordonnées par rapport au paramètre de tranche optimal $u^*_d$.
2. Fonction de poids : En utilisant le résultat de mélangeabilité conjointe, les auteurs construisent une fonction de poids $w(x,y,z)$ supportée sur des triplets spécifiques de ces ensembles.
3. Estimations analytiques : Ils utilisent les propriétés de log-concavité de la fonction de densité de probabilité de la somme de variables aléatoires uniformes (distribution d'Irwin-Hall). Ils dérivent des bornes explicites sur les rapports des volumes de tranches (Lemme 3.1) pour garantir que les poids construits satisfont les contraintes duales.
   • Pour $d$ grand, ils utilisent des estimations de grandes déviations.
   • Pour $d$ petit ($5 \le d < 200$), ils vérifient les inégalités numériquement.

3. Contributions principales

1. Résolution de la conjecture pour tout $d$ : L'article prouve que $c_d = c^*_d$ pour toutes les dimensions $d \ge 1$. Cela confirme que le sous-ensemble sans somme optimal est bien la tranche définie par l'hyperplan $\sum x_i \in [u^*_d n, 2u^*_d n)$.
2. Théorème général de mélangeabilité conjointe : La preuve du Théorème 1.5 est une contribution significative à la théorie des probabilités et à la combinatoire. Elle établit que les distributions uniformes sur les tranches discrètes d'un hypercube sommant à une constante sont conjointement mélangables, un résultat qui généralise les découvertes précédentes pour des dimensions basses spécifiques.
3. Raffinement de l'approche Lepsveridze-Sun : Les auteurs généralisent la méthode utilisée pour $d=3,4$ à des dimensions arbitraires, surmontant la complexité de la construction de couplages en dimensions supérieures grâce à un argument rigoureux de point fixe par induction.

4. Résultats principaux

• Théorème 1.1 : Pour tout $d \ge 1$ et tout sous-ensemble sans somme $S \subseteq [n+1]^d$, la taille est bornée par :
  $$|S| \le c^*_d n^d + O(n^{d-1})$$
  où $c^*_d$ est le volume maximal de la tranche $S_d(u) = \{x \in [0,1]^d : u \le \sum x_i < 2u\}$.
• Corollaire : La densité limite est exactement le volume de la tranche optimale, résolvant la conjecture naturelle posée par Cameron, Green et d'autres.

5. Importance et extensions

• Théorie des nombres combinatoire : Ce résultat règle un problème ouvert de longue date concernant la structure des ensembles sans somme dans les réseaux de haute dimension. Il confirme que la construction par « tranche » est universellement optimale, et pas seulement pour les basses dimensions.
• Méthodes probabilistes : L'article démontre la puissance des techniques de mélangeabilité conjointe et de couplage pour résoudre des problèmes combinatoires extrémaux. La construction inductive de couplages via des théorèmes de point fixe est une technique nouvelle et robuste.
• Ensembles convexes généraux : Les auteurs discutent brièvement de savoir si cette optimalité par « tranche » vaut pour des ensembles convexes généraux. Ils fournissent un contre-exemple (Proposition 5.1) montrant que pour $d$ suffisamment grand, il existe des ensembles convexes où le plus grand sous-ensemble sans somme n'est pas une seule tranche définie par une fonctionnelle linéaire. Cela souligne que la symétrie de l'hypercube est cruciale pour l'optimalité des tranches.
• Problème ouvert : L'article laisse ouverte la question de savoir si l'optimalité des tranches vaut pour tous les ensembles convexes bornés en dimension $d=2$.

En résumé, cet article fournit une solution complète à la densité asymptotique du plus grand sous-ensemble sans somme dans un cube de réseau, unifiant les résultats partiels précédents et introduisant de puissants outils probabilistes pour traiter des dimensions arbitraires.