Graham conjecture on small sets in abelian groups

Résumé Technique : Conjecture de Graham sur les petits ensembles dans les groupes abéliens

1. Problématique et Contexte

L'article s'intéresse à la séquenceabilité des sous-ensembles finis d'un groupe abélien $(G, +)$.

• Définitions clés :
  • Un ordre $a_1, \dots, a_{|A|}$ d'un ensemble $A$ est valide si toutes ses sommes partielles $p_i = \sum_{j=1}^i a_j$ sont distinctes.
  • Un ordre est une séquence (ou sequencing) s'il est valide et si aucune somme partielle $p_i$ (pour $1 \le i \le |A|-1$) n'est égale à l'élément neutre $0$.
  • Un ensemble $A$ est dit séquenceable s'il admet une telle séquence.
• Conjectures principales :
  • Conjecture de Graham/Alspach (Conjecture 1.1) : Tout sous-ensemble $A \subseteq G \setminus \{0\}$ est séquenceable.
  • Conjecture CMPP (Conjecture 1.2) : Tout sous-ensemble $A \subseteq G \setminus \{0\}$ dont la somme des éléments est nulle ($\sum_{x \in A} x = 0$) et qui ne contient aucune paire d'inverses $\{x, -x\}$ est séquenceable.
• État de l'art :
  • La conjecture a été prouvée pour des nombres premiers $p$ suffisamment grands (Pham et Sauermann, combiné à des résultats antérieurs).
  • Pour les groupes abéliens génériques, les meilleurs résultats connus avant cet article se limitaient à des ensembles de taille $|A| \le 9$ (Alspach et Liversidge) ou $|A| \le 12$ dans le cas de $\mathbb{Z}_p$ (via le Nullstellensatz combinatoire).
  • L'objectif de cet article est d'étendre ces bornes pour les petits ensembles dans des groupes abéliens génériques.

2. Méthodologie

Les auteurs développent une approche hybride combinant théorie des groupes, algèbre polynomiale et recherche algorithmique exhaustive.

A. Approche Réursive (Lemme Récurif)
Le cœur de la méthode repose sur un lemme permettant de réduire la taille du problème :

• Principe : Pour un ensemble $A$, il est possible de trouver deux éléments distincts $x_1, x_2 \in A$ tels que leur somme $x_1 + x_2$ soit non nulle et n'appartienne pas à $A \setminus \{x_1, x_2\}$.
• Opération de fusion : On peut alors remplacer $\{x_1, x_2\}$ par l'élément unique $x_1 + x_2$, créant un nouvel ensemble $A'$ de taille $|A|-1$. Si $A'$ est séquenceable, cela permet de reconstruire une séquence pour $A$.
• Preuve du lemme :
  1. Cas $\mathbb{Z}_p$ : Utilisation du Nullstellensatz combinatoire d'Alon. Les auteurs construisent un polynôme homogène $F_k$ et montrent, via des calculs informatiques (Mathematica), que pour $10 \le k \le 23$, il existe un monôme de coefficient non nul garantissant l'existence des éléments $x_1, x_2$ à fusionner.
  2. Cas général : Une preuve directe basée sur la caractérisation des sous-ensembles fermés sous l'addition d'éléments distincts (théorème 2.4). Ils démontrent que si une telle fusion est impossible, alors $A \cup \{0\}$ doit être un sous-groupe de $G$, cas déjà résolu par la littérature.

B. Approche Algorithmique (Recherche Arborescente)
Pour valider la séquenceabilité des ensembles réduits, les auteurs utilisent un algorithme de recherche par contradiction :

• Hypothèse : On suppose qu'un ensemble $A$ de taille $k$ est un contre-exemple (aucune séquence n'existe).
• Arbre de recherche :
  • Les nœuds représentent un ordre partiel $\omega$ et une matrice de contraintes $C$ (vecteurs d'incidence de blocs consécutifs dont la somme est nulle).
  • L'algorithme explore les permutations en ajoutant des contraintes de collision de sommes partielles.
• Certificats de terminaison (Contradictions) : L'arbre s'arrête si la matrice de contraintes $C$ engendre l'une des relations suivantes, prouvant que l'hypothèse de contre-exemple est fausse :
  1. Certificat zéro : Une combinaison linéaire donne $a_i = 0$ (impossible car $A \subseteq G \setminus \{0\}$).
  2. Certificat d'égalité : Une combinaison donne $a_i = a_j$ (impossible car les éléments sont distincts).
  3. Certificat de compression : Utilisation du lemme récurif. Si l'ensemble réduit $A'$ est séquenceable, cela impose des contraintes sur les blocs interdits. Si la matrice $C$ force une violation de ces contraintes, contradiction.
• Implémentation : Code écrit en Python, exécuté sur un serveur haute performance (128 cœurs CPU, 2 To de RAM).

3. Résultats Principaux

Grâce à la combinaison du lemme récurif et de la recherche exhaustive, les auteurs améliorent considérablement les bornes connues :

• Théorème 1.4 (Cas général) : Tout sous-ensemble $A \subseteq G \setminus \{0\}$ est séquenceable si $|A| \le 20$.
  • Amélioration : Passe de la borne précédente de 9 à 20.
• Théorème 1.5 (Cas somme nulle) : Si $\sum_{x \in A} x = 0$, alors $A$ est séquenceable si $|A| \le 22$.
• Théorème 1.6 (Conjecture CMPP) : Si $\sum_{x \in A} x = 0$ et que $A$ ne contient aucune paire $\{x, -x\}$, alors $A$ est séquenceable si $|A| \le 23$.

4. Contributions Clés

1. Extension des bornes : Passage de $|A| \le 9$ à $|A| \le 20$ pour le cas général, et jusqu'à 23 pour le cas CMPP.
2. Généralité : Les résultats s'appliquent à tout groupe abélien $G$, et non seulement aux groupes cycliques $\mathbb{Z}_p$.
3. Méthodologie hybride : Démonstration de l'efficacité de coupler des preuves théoriques (lemme de réduction) avec des preuves assistées par ordinateur (recherche de certificats linéaires).
4. Preuve du lemme récurif : Fourniture d'une preuve directe et générale du lemme de fusion, indépendamment du Nullstellensatz, ce qui élargit la portée théorique.

5. Signification et Impact

Cet article représente une avancée majeure dans la compréhension de la séquenceabilité des petits ensembles.

• Il comble le vide entre les résultats pour les très petits ensembles ($|A| \le 9$) et les résultats asymptotiques pour les grands ensembles (nombres premiers grands).
• Il valide la conjecture de Graham pour une plage de tailles d'ensembles beaucoup plus large que jamais auparavant dans le cadre des groupes abéliens génériques.
• La méthode proposée (réduction par fusion + vérification par arbre de contraintes) offre un cadre robuste pour attaquer d'autres problèmes de séquenceabilité ou de structures combinatoires dans les groupes.
• Les auteurs rendent leur code et leurs données accessibles, favorisant la reproductibilité et de futures extensions.

En conclusion, ce travail démontre que la structure des petits ensembles dans les groupes abéliens est suffisamment riche pour garantir l'existence de séquences, même sans hypothèses restrictives sur la taille du groupe, tant que la taille de l'ensemble reste inférieure à 20 (ou 23 sous conditions supplémentaires).