Expanding groups with large diameter

Titel: Expanderende Groepen met Grote Diameter

Auteurs: Sean Eberhard en Luca Sabatini

---

1. Probleemstelling en Achtergrond

Het artikel onderzoekt de relatie tussen de spectrale gap (eigenschap van expanderende grafen) en de diameter van Cayley-graaf van een eindige groep $G$, afhankelijk van de keuze van de genererende verzameling $S$.

• Bekende feiten: Voor oneindige groepen zijn eigenschappen zoals groei, hyperbolisiteit en amenabiliteit onafhankelijk van de keuze van de eindige genererende verzameling. Voor eindige groepen is dit echter anders.
• Eerdere resultaten: Alon, Lubotzky en Wigderson (1991) en Kassabov (2005) toonden aan dat er eindige groepen bestaan die expanderend zijn ten opzichte van de ene begrende genererende verzameling, maar niet ten opzichte van een andere.
• De centrale vraag (Pyber & Szabó, 2013): Als een rij eindige groepen $(G_n)$ expanderende Cayley-graaf heeft voor een rij van begrende genererende verzamelingen $(X_n)$, geldt dan dat de diameter voor elke andere rij van genererende verzamelingen $(Y_n)$ polylogaritmisch is? Dat wil zeggen: is $\text{diam}(\text{Cay}(G_n, Y_n)) \leq C (\log |G_n|)^C$?
• Hypothese: Veel onderzoekers vermoedden dat "polylogaritmische diameter" een groepsinvariant zou kunnen zijn voor expanderende groepen (verwant aan de Babai-conjectuur voor eindige simpele groepen).

2. Hoofdbijdrage en Resultaten

De auteurs beantwoorden de vraag van Pyber en Szabó negatief. Ze construeren een tegenvoorbeeld waarbij een groep expanderend is voor de ene genererende verzameling, maar een super-polylogaritmische (zelfs exponentiële) diameter heeft voor een andere.

Hoofdstelling (Theorema 1.2):
Er bestaan constanten $\delta, \varepsilon > 0$ en een rij eindige groepen $(G_n)$ met $|G_n| \to \infty$ en begrende genererende verzamelingen $X_n, Y_n$ zodanig dat:

1. $\text{Cay}(G_n, X_n)$ $\varepsilon$-expanderende grafen zijn (d.w.z. ze hebben een uniforme spectrale gap).
2. De diameter $\text{diam}(\text{Cay}(G_n, Y_n)) \geq \exp(\delta \sqrt{\log |G_n|})$.

Dit betekent dat de diameter kan groeien als een exponentiële functie van de wortel van de logaritme van de orde van de groep, wat veel groter is dan polylogaritmisch.

3. Methodologie en Constructie

De constructie maakt gebruik van een semidirect product van een vectorruimte en een symmetrische groep.

De Groepstructuur

De groepen zijn gedefinieerd als:
$$G_n = V_0 \rtimes S_n$$
waarbij:

• $S_n$ de symmetrische groep op $n$ elementen is.
• $V = \mathbb{F}_p^n$ een vectorruimte is over een eindig veld met een groot priemgetal $p$.
• $V_0 \subset V$ de "deleted permutation module" is (de deelruimte van vectoren met som 0, dimensie $n-1$).
• De grootte van de groep is $|G_n| = p^{n-1} n!$.
• Het priemgetal $p$ is exponentieel groot in $n$ ($p \sim e^{cn}$).

De Genererende Verzamelingen

Er worden twee verzamelingen gedefinieerd, beide van de vorm $\{v\} \cup T$, waarbij $v \in V_0$ en $T \subset S_n$:

1. De "slechte" verzameling ($Y_n$):
   • $v = (1, -1, 0, \dots, 0)$.
   • $T = \{(1, 2), (1, 2, \dots, n)\}$ (standaard generatoren voor $S_n$).
   • Resultaat: De diameter is groot ($\geq p/2$) omdat het element $v$ alleen via herhaaldelijk optellen van de componenten in $V_0$ kan worden gegenereerd, wat $O(p)$ stappen vereist.
2. De "goede" verzameling ($X_n$):
   • $T$ is een begrende genererende verzameling voor $S_n$ die bekend staat als expanderend (bestaan bewezen door Kassabov).
   • $v$ is een speciaal gekozen vector in $V_0$.
   • Doel: Bewijzen dat er een $v$ bestaat zodat $\text{Cay}(G_n, X_n)$ een spectrale gap heeft.

4. Technische Analyse en Bewijsstrategie

Het bewijs van de expanderende eigenschap voor $X_n$ reduceert tot het schatten van permutational exponential sums.

Reductie tot Exponentiële Sommen

De spectrale gap van de Cayley-graaf hangt af van de eigenwaarden van de adjacentie-operator. Voor de abelse deelgroep $V_0$ worden deze eigenwaarden geassocieerd met irreducibele karakteristieken, geïdentificeerd met vectoren $w \in V$.
De eigenwaarden worden gegeven door:
$$\lambda_{v,w} = \frac{1}{n!} \sum_{\sigma \in S_n} e_p(\langle v, w^\sigma \rangle)$$
waarbij $e_p(x) = \exp(2\pi i x / p)$ en $\langle \cdot, \cdot \rangle$ het inproduct is.
Om een spectrale gap te garanderen, moet men aantonen dat er een $v$ bestaat zodat voor alle niet-constante $w$:
$$|\lambda_{v,w}| \leq 1 - \varepsilon$$

Probabilistische Methode en Deterministische Schakeling

De grootste uitdaging is dat $p$ exponentieel groot is, waardoor een naïeve unie-bounds (union bound) over alle vectoren $w$ faalt (er zijn te veel vectoren).

De auteurs gebruiken een tweestapsbenadering:

1. Probabilistische stap (Lemmas 4.1): Ze tonen aan dat voor een willekeurig gekozen $v$, de som $\lambda_{v,u}$ klein is voor vectoren $u$ met slechts één niet-nul component (support-one). Dit wordt bewezen met Hoeffding's ongelijkheid. Omdat $p$ exponentieel is, is de kans dat dit faalt voor alle $u$ klein, mits $p$ niet te groot is ten opzichte van $n$ (specifiek $p \leq e^{\delta n}$).
2. Deterministische schakelstap (Lemma 4.2): Ze gebruiken een "switching argument" gebaseerd op de ongelijkheid van Cauchy-Schwarz. Ze tonen aan dat als de sommen voor support-one vectoren klein zijn, dan zijn de sommen voor alle niet-constante vectoren $w$ ook klein.
   • Door een transpositie $\tau$ toe te passen op $w$, kunnen ze $|\lambda_{v,w}|^2$ relateren aan $|\lambda_{v, u}|^2$ voor een vector $u$ met support 1.
   • Dit elimineert de noodzaak voor een unie-bounds over de enorme ruimte van alle $w$.

Conclusie van het bewijs (Theorema 1.3): Er bestaan constanten $\delta, \varepsilon$ zodat voor $p \leq e^{\delta n}$ er een $v$ bestaat die voldoet aan de vereiste ongelijkheid.

5. Betekenis en Impact

• Beantwoording van een open vraag: Het artikel sluit definitief af dat de eigenschap "expanderend" voor een groep niet impliceert dat de diameter voor alle genererende verzamelingen polylogaritmisch is.
• Scheiding van concepten: Het toont aan dat de spectrale gap (een lokale eigenschap gerelateerd aan menging) en de diameter (een globale eigenschap) sterk kunnen divergeren afhankelijk van de generatoren, zelfs binnen dezelfde groep.
• Technische innovatie: De combinatie van probabilistische methoden met een deterministische Cauchy-Schwarz schakelargument biedt een nieuwe aanpak voor het hanteren van grote parameters in combinatorische problemen, specifiek bij het vermijden van union bounds in hoge dimensies.
• Optimaliteit: De auteurs merken op dat het een interessant open probleem blijft om de optimale ondergrens voor de diameter in (b) te vinden, aangezien hun constructie een diameter van $\exp(\delta \sqrt{\log |G|})$ geeft, terwijl polynoom-diameter een groepsinvariant is ("almost flat").

Samenvattend weerlegt dit werk de vermoeden dat expanderende groepen per definitie een kleine diameter hebben voor elke genererende verzameling, en biedt het een krachtige constructie en analytische methode om dit te demonstreren.