Expanding groups with large diameter

1. Problem Statement and Context

The paper addresses a fundamental question in geometric group theory regarding the relationship between the spectral gap (expansion properties) and the diameter of Cayley graphs of finite groups.

• Background: For infinite groups, properties like growth type, amenability, and property (T) are independent of the choice of finite generating set. However, for sequences of finite groups, the situation is more complex. It is known that a group can be an expander with respect to one bounded generating set but not another (Alon, Lubotzky, Wigderson; Kassabov).
• The Specific Question: Pyber and Szabó (2013) asked whether the property of having a polylogarithmic diameter (i.e., $O(\log^C |G|)$) is intrinsic to the group if the group admits some bounded generating set that makes it an expander. Specifically, if $(G_n)$ is a sequence of finite groups where $\text{Cay}(G_n, X_n)$ is an expander for some bounded $X_n$, does it follow that for every bounded generating set $Y_n$, $\text{diam}(\text{Cay}(G_n, Y_n)) \leq C (\log |G_n|)^C$?
• The Conjecture: The prevailing intuition, supported by results on finite simple groups (Babai's conjecture), suggested that expanders generally have small (polylogarithmic) diameters regardless of the generating set.

2. Main Results

The authors answer the Pyber–Szabó question negatively. They construct a sequence of finite groups that are expanders with respect to one bounded generating set but have a super-polylogarithmic diameter with respect to another.

Theorem 1.2 (Main Result):
There exist constants $\delta, \varepsilon > 0$ and a sequence of finite groups $(G_n)_{n \geq 1}$ with $|G_n| \to \infty$ and bounded generating sets $X_n, Y_n \subseteq G_n$ such that:

1. $\text{Cay}(G_n, X_n)$ are $\varepsilon$-expander graphs (uniform spectral gap).
2. $\text{diam}(\text{Cay}(G_n, Y_n)) \geq \exp(\delta \sqrt{\log |G_n|})$.

Significance of the Bound:
The diameter bound $\exp(\delta \sqrt{\log |G_n|})$ is significantly larger than any polylogarithmic bound $(\log |G_n|)^C$, effectively disproving the idea that expansion implies small diameter for all generating sets.

3. Methodology and Construction

The construction relies on a specific semidirect product structure and a probabilistic argument involving exponential sums.

3.1 Group Construction

The group is defined as a semidirect product:
$$G_n = V_0 \rtimes S_n$$

• $S_n$: The symmetric group on $n$ elements.
• $V_0$: The "deleted permutation module" of dimension $n-1$ over the finite field $\mathbb{F}_p$, where $p$ is a prime such that $p \sim e^{cn}$ (exponentially large in $n$).
• Order: $|G_n| = p^{n-1} n! \approx \exp(cn^2)$.

3.2 Generating Sets

Both generating sets $X_n$ and $Y_n$ are of the form $\{v\} \cup T$, where $v \in V_0$ and $T \subset S_n$.

• The "Bad" Set ($Y_n$):

  • $T = \{(1, 2), (1, 2, \dots, n)\}$ (standard generators for $S_n$).
  • $v = (1, -1, 0, \dots, 0)$.
  • Result: The diameter is large because the element $v$ requires roughly $p/2$ steps to traverse the vector space component $V_0$ using the limited action of $T$. Thus, $\text{diam} \geq p \sim e^{cn}$.

• The "Good" Set ($X_n$):

  • $T$ is a bounded-size expanding generating set for $S_n$ (guaranteed by Kassabov's results).
  • $v$ is chosen randomly from $V_0$.
  • Goal: Show that for a random $v$, the spectral gap is bounded away from zero.

3.3 Analytical Framework

To prove $X_n$ yields an expander, the authors use Kazhdan constants ($\kappa$) and spectral gaps.

1. Reduction to Semidirect Products: Using Proposition 3.4, they relate the Kazhdan constant of $G = V_0 \rtimes S_n$ to the constants of the components:
   $$\kappa(G, X) \geq C \cdot \kappa(V_0, vS_n) \cdot \kappa(S_n, T)$$
   Since $\kappa(S_n, T)$ is bounded away from zero, the problem reduces to bounding the spectral gap of the action of $vS_n$ on $V_0$.
2. Spectral Analysis: The eigenvalues of the Cayley graph $\text{Cay}(V_0, vS_n)$ are determined by permutational exponential sums:
   $$\lambda_{v,w} = \frac{1}{n!} \sum_{\sigma \in S_n} e_p(\langle v, w^\sigma \rangle)$$
   where $w \in V_0$ is a non-trivial character vector, and $e_p(x) = \exp(2\pi i x / p)$.
   The graph is an expander if $|\lambda_{v,w}| \leq 1 - \varepsilon$ for all non-constant $w$.

4. Key Technical Innovation: The Exponential Sum Estimate

The core difficulty is that $p$ is exponentially large ($p \approx e^{cn}$), making a naive union bound over all vectors $w \in V_0$ impossible (the number of vectors is $p^{n-1}$, which is doubly exponential).

Theorem 1.3 (Exponential Sum Estimate):
There exist constants $\delta, \varepsilon > 0$ such that for $p \leq e^{\delta n}$, a random $v \in V_0$ satisfies:
$$\max_{w \in V \setminus \langle \mathbf{1} \rangle} |\lambda_{v,w}| \leq 1 - \varepsilon$$

Proof Strategy (Lemmas 4.1 & 4.2):

1. Probabilistic Step (Lemma 4.1): The authors first show that for "simple" vectors $w$ (specifically those with support 1, i.e., $w = (u, 0, \dots, 0)$), the sum $\lambda_{v,w}$ is small with high probability using Hoeffding's inequality. Since there are only $p$ such vectors, a union bound works here.
2. Deterministic Switching (Lemma 4.2): This is the novel contribution. They use a Cauchy-Schwarz switching argument to bound the general case by the simple case.
   • They show that for any $w$, $|\lambda_{v,w}|^2$ can be bounded by a convex combination involving $|\lambda_{v,u}|^2$ where $u$ is a difference of coordinates of $w$.
   • Specifically: $|\lambda_{v,w}|^2 \leq \frac{1}{2} + \frac{1}{2} \max_{u \neq 0} |\lambda_{v,u}|^2$.
   • This allows them to control the maximum over the vast space of all $w$ by controlling the maximum over the much smaller set of "support-one" vectors $u$.

By combining the probabilistic bound for support-one vectors with the deterministic reduction, they prove that a random $v$ works with high probability, even when $p$ is exponential in $n$.

5. Significance and Implications

1. Resolution of Pyber–Szabó Question: The paper definitively shows that having an expander generating set does not imply that all bounded generating sets yield polylogarithmic diameters. Expansion is not a "group property" in the sense of diameter bounds across all generating sets.
2. Optimality of Bounds: The construction highlights that while having polynomial diameter is a group property (almost flat groups), the transition from expander to large diameter can be extremely sharp.
3. Methodological Contribution: The technique of using a deterministic switching argument (Cauchy-Schwarz) to reduce a union bound over an exponentially large set to a smaller set is a powerful tool. It allows the authors to handle parameters ($p$) that were previously thought to be too large for such probabilistic constructions in group theory.
4. Connection to Additive Combinatorics: The work bridges spectral graph theory, representation theory, and exponential sums, demonstrating how tools from additive combinatorics can resolve structural questions in group theory.

In summary, Eberhard and Sabatini provide a counter-intuitive example where a group is "well-connected" (expander) under one set of rules but "slow to traverse" (large diameter) under another, fundamentally refining our understanding of the relationship between expansion and diameter in finite groups.