Expanding groups with large diameter

1. Problématique et Contexte

L'article s'attaque à une question fondamentale en théorie des groupes et en théorie des graphes de Cayley : la relation entre la propriété d'être un graphe expansif (expander) et le diamètre du graphe, en fonction du choix de l'ensemble de générateurs.

• Contexte : Pour un groupe infini, des propriétés comme la croissance, l'hyperbolicité ou l'amenabilité sont intrinsèques au groupe et indépendantes du choix des générateurs. Cependant, pour une séquence de groupes finis, la propriété d'être un "expander" (c'est-à-dire avoir un écart spectral uniforme strictement positif) dépend fortement du choix de l'ensemble de générateurs.
• La question de Pyber et Szabó (2013) : Ils ont demandé si, pour une séquence de groupes finis $(G_n)$, l'existence d'un ensemble de générateurs $X_n$ de taille bornée rendant $Cay(G_n, X_n)$ expansif implique que tout autre ensemble de générateurs $Y_n$ (de taille bornée) donne un graphe de diamètre polylogarithmique (c'est-à-dire $O((\log |G_n|)^C)$).
• Hypothèse précédente : Il était soupçonné que les groupes simples finis et d'autres familles de groupes "expansifs" avaient un diamètre polylogarithmique pour tous les ensembles de générateurs bornés (conjecture de Babai pour les groupes simples).

2. Contribution Principale et Résultat

Les auteurs répondent négativement à la question de Pyber et Szabó. Ils démontrent qu'il existe des groupes qui sont des expanders pour un ensemble de générateurs donné, mais qui ont un diamètre super-polylogarithmique (voire exponentiel en racine carrée du logarithme de l'ordre du groupe) pour un autre ensemble de générateurs.

Théorème 1.2 (Résultat principal) :
Il existe des constantes $\delta, \varepsilon > 0$ et une suite de groupes finis $(G_n)$ avec $|G_n| \to \infty$, admettant deux ensembles de générateurs de taille bornée $X_n$ et $Y_n$ tels que :

1. $Cay(G_n, X_n)$ est un graphe $\varepsilon$-expansif (écart spectral uniforme).
2. Le diamètre de $Cay(G_n, Y_n)$ est borné inférieurement par $\exp(\delta \sqrt{\log |G_n|})$.

Cela montre que le diamètre polylogarithmique n'est pas une propriété intrinsèque du groupe, même si le groupe admet une structure d'expander pour certains générateurs.

3. Méthodologie et Construction

La construction repose sur un produit semi-direct spécifique et une analyse fine des sommes exponentielles permutées.

A. Structure du Groupe

Le groupe est défini comme suit :
$$G_n = V_0 \rtimes S_n$$

• $V = \mathbb{F}_p^n$ est un espace vectoriel sur un corps fini $\mathbb{F}_p$.
• $V_0$ est le module de permutation supprimé (deleted permutation module) de dimension $n-1$, défini comme l'orthogonal du vecteur $(1, 1, \dots, 1)$ dans $V$.
• $S_n$ est le groupe symétrique agissant sur $V$ par permutation des coordonnées.
• Contrainte sur $p$ : Le nombre premier $p$ est choisi très grand, de l'ordre de $p \sim e^{cn}$ (exponentiel en $n$). Cela est crucial car la taille du groupe est $|G_n| \approx p^{n-1} n! \approx \exp(cn^2)$.

B. Les Ensembles de Générateurs

Les deux ensembles de générateurs $X$ et $Y$ sont de la forme $\{v\} \cup T$, où $v \in V_0$ et $T \subset S_n$.

1. L'ensemble "mauvais" ($Y$) :

   • $v = (1, -1, 0, \dots, 0)$ et $T = \{(1, 2), (1, 2, \dots, n)\}$.
   • Ce choix est simple. La présence de $v$ avec des coefficients petits et la structure de $T$ permettent de montrer que le diamètre est au moins de l'ordre de $p/2$, soit $\sim e^{cn}$, ce qui est super-polylogarithmique par rapport à $\log |G_n| \sim n^2$.

2. L'ensemble "bon" ($X$) :

   • $T$ est un ensemble de générateurs borné pour $S_n$ qui rend $S_n$ expansif (existence garantie par le travail de Kassabov).
   • Le défi est de trouver un vecteur $v \in V_0$ tel que l'ajout de $v$ préserve l'expansion dans le produit semi-direct.

C. Réduction aux Sommes Exponentielles

Pour prouver que $Cay(G, X)$ est un expander, les auteurs utilisent la constante de Kazhdan $\kappa(G, X)$. Grâce à des inégalités reliant les constantes de Kazhdan des produits semi-directs (Lemme 3.2, Proposition 3.4), le problème se réduit à borner les valeurs propres de l'opérateur d'adjacence sur $V_0$.

Cela conduit au Théorème 1.3, qui est le cœur technique de l'article :
Il existe des constantes $\delta, \varepsilon > 0$ telles que pour tout $n$ et $p \le e^{\delta n}$, il existe un vecteur $v \in V_0$ tel que pour tout vecteur non constant $w \in V$ :
$$\left| \frac{1}{n!} \sum_{\sigma \in S_n} e_p(\langle v, w^\sigma \rangle) \right| \le 1 - \varepsilon$$
où $e_p(x) = \exp(2\pi i x / p)$ et $\langle \cdot, \cdot \rangle$ est le produit scalaire standard.

4. Preuve du Théorème 1.3 (Analyse Probabiliste et Déterministe)

La preuve combine une méthode probabiliste et un argument de commutation (switching argument) :

1. Approche Probabiliste (Lemme 4.1) :

   • Les auteurs montrent que si $v$ est choisi uniformément au hasard dans $V_0$, alors pour un vecteur $w$ très simple (de support 1, c'est-à-dire $w = (u, 0, \dots, 0)$), la somme exponentielle est petite avec une probabilité très élevée.
   • L'inégalité de Hoeffding est utilisée pour borner la probabilité que $|\lambda_{v, u}|$ soit grand.
   • Une union bound simple suffit pour les vecteurs de support 1, même si $p$ est grand, car il n'y a que $p$ tels vecteurs.

2. Argument de Commutation (Lemme 4.2) :

   • Le défi majeur est que le nombre total de vecteurs $w$ est $p^n$, ce qui rend une union bound directe impossible (l'erreur probabiliste serait trop grande).
   • Les auteurs utilisent une inégalité de Cauchy-Schwarz astucieuse (argument de "switching"). Ils montrent que le carré de la somme pour un vecteur $w$ arbitraire peut être majoré par une moyenne impliquant des sommes sur des vecteurs de support 1.
   • Plus précisément, ils démontrent que :
     $$\max_{w \in V \setminus \langle 1 \rangle} |\lambda_{v, w}|^2 \le \frac{1}{2} + \frac{1}{2} \max_{0 \neq u \in \mathbb{F}_p} |\lambda_{v, u}|^2$$
   • Cela permet de contrôler tous les vecteurs $w$ en ne contrôlant que les vecteurs de support 1, pour lesquels la probabilité de bonne concentration est suffisante.

3. Conclusion de la preuve :

   • En choisissant $\varepsilon$ et $\delta$ appropriés, la probabilité qu'un vecteur aléatoire $v$ échoue est strictement inférieure à 1. Cela garantit l'existence d'au moins un vecteur $v$ satisfaisant la condition requise pour l'expansion.

5. Signification et Implications

• Réponse à une question ouverte : L'article résout négativement la question de Pyber et Szabó et celle posée lors de la réunion d'Oberwolfach 2024. Il établit que le diamètre polylogarithmique n'est pas une propriété de groupe, même dans le contexte des expanders.
• Limites de l'expansion : Il montre que l'expansion spectrale (qui contrôle le mélange rapide) ne garantit pas un diamètre petit pour tous les ensembles de générateurs. Un mauvais choix de générateurs peut créer des "goulots d'étranglement" géométriques massifs.
• Nouveauté technique : L'utilisation de sommes exponentielles permutées avec un nombre premier $p$ exponentiellement grand par rapport à la dimension $n$ est une innovation. La méthode permet d'éviter les bornes union classiques qui échoueraient dans ce régime de paramètres.
• Comparaison avec les travaux antérieurs : Contrairement aux constructions d'Alon-Lubotzky-Wigderson ou de Kassabov qui utilisent des groupes avec des diamètres probablement polylogarithmiques, cette construction crée délibérément un déséquilibre extrême entre la structure spectrale et la géométrie du graphe.

En résumé, ce travail démontre que la propriété d'être un "groupe expansif" est subtile et dépendante du générateur, et que la géométrie (diamètre) peut être arbitrairement mauvaise même lorsque le spectre (expansion) est excellent.