Expanding groups with large diameter

1. Il Problema e il Contesto

Il lavoro si inserisce nel campo della teoria dei gruppi finiti e della teoria dei grafi di Cayley. L'obiettivo principale è rispondere a una domanda aperta sollevata da Pyber e Szabó (2013) riguardo alla relazione tra la proprietà di espansione (spectral gap) e il diametro di un grafo di Cayley al variare dell'insieme di generatori.

• Contesto: È noto che per gruppi infiniti, proprietà come la crescita, l'amenabilità e la proprietà (T) sono indipendenti dalla scelta dei generatori finiti. Tuttavia, per sequenze di gruppi finiti $(G_n)$, la situazione è diversa.
• La Domanda (Question 1.1): Se una sequenza di gruppi finiti ammette un insieme di generatori limitato $X_n$ tale che il grafo di Cayley $\text{Cay}(G_n, X_n)$ sia un espansore (cioè ha un spectral gap uniforme), è vero che ogni altro insieme di generatori $Y_n$ (di cardinalità limitata) produce un grafo con diametro polilogaritmico, ovvero $\text{diam}(\text{Cay}(G_n, Y_n)) \le C (\log |G_n|)^C$?
• Ipotesi precedente: Si sospettava che l'essere un "espansore" implicasse un diametro piccolo per qualsiasi insieme di generatori, rendendo il diametro polilogaritmico una proprietà intrinseca del gruppo.

2. Risultati Principali

Gli autori rispondono negativamente alla domanda di Pyber e Szabó, dimostrando che l'essere un espansore rispetto a un insieme di generatori non garantisce un diametro piccolo rispetto ad altri insiemi.

Teorema 1.2: Esistono costanti $\delta, \varepsilon > 0$ e una sequenza di gruppi finiti $(G_n)$ con $|G_n| \to \infty$, dotati di due insiemi di generatori limitati $X_n$ e $Y_n$, tali che:

1. $\text{Cay}(G_n, X_n)$ è un grafo $\varepsilon$-espansore (ha un spectral gap uniforme).
2. Il diametro rispetto a $Y_n$ è super-polilogaritmico:
   $$\text{diam}(\text{Cay}(G_n, Y_n)) \ge \exp(\delta \sqrt{\log |G_n|})$$
   Questo valore è esponenziale nella radice quadrata del logaritmo dell'ordine del gruppo, molto più grande di un polilogaritmo.

3. Metodologia e Costruzione

La costruzione si basa su un prodotto semidiretto specifico e su un'analisi combinatoria delle somme esponenziali.

La Struttura del Gruppo

Il gruppo è definito come:
$$G_n = V_0 \rtimes S_n$$
dove:

• $S_n$ è il gruppo simmetrico su $n$ elementi.
• $V = \mathbb{F}_p^n$ è uno spazio vettoriale su un campo finito.
• $V_0 \subset V$ è il modulo permutazionale cancellato (deleted permutation module) di dimensione $n-1$, definito come l'ortogonale del vettore $(1, \dots, 1)$.
• $p$ è un numero primo che cresce esponenzialmente con $n$ ($p \sim e^{cn}$).

L'ordine del gruppo è $|G_n| = p^{n-1} n! \approx \exp(c n^2)$.

Gli Insiemi di Generatori

Entrambi gli insiemi di generatori hanno la forma $\{v\} \cup T$, dove $v \in V_0$ e $T \subset S_n$.

1. Insieme $Y_n$ (Diametro Grande):

   • $v = (1, -1, 0, \dots, 0)$.
   • $T = \{(1, 2), (1, 2, \dots, n)\}$ (generatori standard per $S_n$).
   • Con questa scelta, il diametro è limitato inferiormente da $p/2$, che è esponenziale in $n$, soddisfacendo la condizione (b).

2. Insieme $X_n$ (Espansore):

   • $T$ è scelto come un insieme di generatori limitato per $S_n$ che è già un espansore (esistente grazie ai risultati di Kassabov).
   • $v$ è scelto in modo probabilistico (o deterministico tramite un argomento di switching) in $V_0$.
   • L'obiettivo è dimostrare che per una scelta appropriata di $v$, il grafo $\text{Cay}(G_n, X_n)$ ha un spectral gap uniforme.

Analisi Spettrale e Somma Esponenziale

La dimostrazione che $X_n$ genera un espansore si riduce allo studio degli autovalori dell'operatore di adiacenza. Poiché $V_0$ è abeliano, gli autovalori sono legati alle somme esponenziali permutazionali:
$$\lambda_{v,w} = \frac{1}{n!} \sum_{\sigma \in S_n} e_p(\langle v, w^\sigma \rangle)$$
dove $e_p(x) = \exp(2\pi i x / p)$ e $\langle \cdot, \cdot \rangle$ è il prodotto scalare standard.

Il problema si riduce al Teorema 1.3: Dimostrare che esiste un $v \in V_0$ tale che per ogni vettore non costante $w \in V$, il valore assoluto della somma esponenziale sia strettamente minore di 1 (in particolare $\le 1 - \varepsilon$).

4. Tecniche Chiave e Novità

La sfida principale è che $p$ è enorme (esponenziale in $n$), il che rende impossibile un semplice union bound su tutti i possibili vettori $w$ (ce ne sono troppo molti).

Gli autori risolvono il problema combinando due approcci:

1. Argomento Probabilistico (Lemma 4.1): Si mostra che per un $v$ scelto uniformemente a caso, la somma esponenziale è piccola per i vettori $w$ con supporto piccolo (in particolare per vettori del tipo $(u, 0, \dots, 0)$). Usando la disuguaglianza di Hoeffding, si dimostra che la probabilità che la somma sia grande è trascurabile.
2. Argomento Deterministico di Switching (Lemma 4.2): Per gestire i vettori $w$ con supporto grande, gli autori usano una disuguaglianza basata su Cauchy-Schwarz. Dimostrano che il massimo della somma esponenziale su tutti i $w$ non costanti può essere limitato in funzione del massimo delle somme esponenziali sui vettori a supporto singolo (quelli già controllati probabilisticamente).
   • L'idea è che se $w$ ha almeno due coordinate diverse ($w_1 \neq w_2$), si può "switchare" (scambiare) le coordinate tramite una trasposizione per ridurre il problema a una somma che coinvolge solo la differenza $u = w_1 - w_2$.

Questa combinazione permette di evitare un union bound su tutti i $p^n$ vettori, limitandosi a controllare un numero molto minore di casi critici.

5. Significato e Implicazioni

• Risoluzione di una Congettura: Il lavoro risponde negativamente alla domanda di Pyber e Szabó, dimostrando che la proprietà di avere un diametro polilogaritmico non è una proprietà del gruppo, ma dipende fortemente dalla scelta dei generatori.
• Distinzione tra Proprietà: Separa chiaramente la nozione di "gruppo espansore" (esistenza di alcuni generatori che danno un gap) dalla nozione di "diametro piccolo" (valido per tutti i generatori).
• Metodologia: Introduce una tecnica innovativa che combina probabilità e analisi combinatoria (switching argument) per gestire somme esponenziali in regimi dove il campo è molto grande rispetto alla dimensione del gruppo simmetrico.
• Confronto con Lavori Precedenti: Estende i risultati di Alon-Lubotzky-Wigderson e Kassabov, che avevano mostrato l'esistenza di gruppi con diametri diversi per diversi generatori, ma non avevano raggiunto la soglia di un diametro così grande (super-polilogaritmico) mantenendo la proprietà di espansore.

In sintesi, il paper dimostra che è possibile costruire gruppi che sono "espansori eccellenti" rispetto a una specifica scelta di generatori, ma che diventano "lenti" (diametro molto grande) rispetto ad altre scelte, sfatando l'idea che l'espansione garantisca una struttura geometrica compatta universale.