Cayley graphs of quasirandom groups

Luca Sabatini · 2026

Read Cayley graphs of quasirandom groups by Luca Sabatini (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-03801.txt.

Introduction

Sabatini proves that Cayley graphs of quasirandom groups expand well and stay small in diameter. A finite group is quasirandom when its nontrivial representations all have high degree. Expansion in such a group was tied to its simple quotients by recent work. That link drives the results here. The Bourgain-Gamburd expansion machine is simplified as a first payoff.

The product theorem drops out of the machine's assumptions. Crown theory then shows a sharp sampling result. Just over one over epsilon random elements yield an expander Cayley graph with high probability. Diameter results generalize work of Breuillard, Green, and Tao, and of Pyber and Szabó. Any connected Cayley graph of a quasirandom group has polylogarithmic diameter. Group theorists get cleaner expansion criteria and tight size bounds in one package.

Catalog record

CREATORLuca Sabatini
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE50 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.03801

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Cayley graphs of quasirandom groups Luca Sabatini Abstract . A finite group G G is ε \varepsilon -quasirandom if all its nontrivial irreducible complex representations have degree at least | G | ε |G|^{\varepsilon} . Building on recent work of Golsefidy–Srinivas, we prove that expansion in a quasirandom group is controlled by expansion in its simple quotients. As a consequence, we remove the product theorem from the hypotheses of the Bourgain–Gamburd expansion machine. Moreover, we combine this result with crown theory to deduce that 1 + ⌊ ε − 1 ⌋ 1+\lfloor\varepsilon^{-1}\rfloor random elements give an expander Cayley graph with high probability. Finally, generalizing results of Breuillard–Green–Tao and Pyber–Szabó, we prove that the diameter of any connected Cayley graph of a quasirandom group is polylogarithmic. 2020 Mathematics Subject Classification Primary: 20F69, 05C48 1. Introduction Expander graphs are highly connected sparse graphs and play a fundamental role in various areas of mathematics and computer science [ HLW06 , Lub12 ] . Among their remarkable properties, there is the fact that their diameter is logarithmic in the number of vertices. Several notable constructions of expanders involve Cayley graphs. In a spectacular breakthrough, Bourgain and Gamburd [ BG08 ] devised an ingenious method, starting from the so-called Sarnak–Xue trick [ SX91 ] , to show that 2 random elements in \mathop{\mathrm{SL}}_{2}(p) give an expander Cayley graph with high probability. Using the same strategy, the companion paper of Breuillard–Green–Guralnick–Tao [ BGGT15 ] generalized their theorem to all finite simple groups of Lie type of bounded rank. There are also weaker results that have the advantage of being valid for literally all generating sets. In a parallel development, Helfgott [ Hel08 ] proved that the diameter of every connected Cayley graph of \mathop{\mathrm{SL}}_{2}(p) is polylogarithmic, while Breuillard–Green–Tao [ BGT11 ] and Pyber–Szabó [ PS16 ] generalized his theorem to all finite simple groups of Lie type of bounded rank. The following property of finite simple groups of bounded Lie rank was first isolated by Gowers [ Gow08 ] , and plays a crucial role in the proofs of these results: Definition . Let \varepsilon>0 . A finite group G is \varepsilon -quasirandom if every nontrivial irreducible complex representation of G has degree at least |G|^{\varepsilon} . We are interested in this property when \varepsilon is fixed and G is large, so we simply refer to quasirandom group(s) in this case. Quasirandom groups have several characterizations [ BS25 , NP11 ] , and in the context of expansion and diameter bounds, they can be thought of as the groups where the “tricks” of Sarnak–Xue [ SX91 ] and Gowers [ NP11 ] are available efficiently. It is natural to ask: how far quasirandomness alone drives expansion phenomena? The present paper answers this question completely. Our first main result builds on the recent work of Golsefidy and Srinivas [ GS24 , GS25 ] . They study group extensions 1\to N\hookrightarrow G\twoheadrightarrow Q\to 1 where Q is quasirandom. In particular, they give hypotheses under which expansion in \mathop{\mathrm{Cay}}(G,S) follows from expansion in \mathop{\mathrm{Cay}}(G/N,S) (in fact, they first prove that such hypotheses induce quasirandomness to G itself). For instance, they require G to be a specific direct product of N and Q , or N to be small and abelian, or nilpotent of bounded class, together with suitable technical conditions on the conjugation action of G on N . We show that no additional hypothesis is needed when G is quasirandom: expansion in quasirandom groups is always controlled by expansion in the simple quotients. Theorem 1.1 . Let G be \varepsilon -quasirandom. If G=\langle S\rangle , then \mathop{\mathrm{gap}}(G,S)\>\gg_{\varepsilon,|S|}\>\min\{\mathop{\mathrm{gap}}(G/N,S):N~\text{a maximal normal subgroup of}~G\}. Here \mathop{\mathrm{gap}}(G,S) denotes the spectral gap of the Cayley graph. It is remarkable that Theorem 1.1 fails dramatically for non-quasirandom groups: a trivial example is a large cyclic 2 -group, but we refer the reader to Example 5.3 for a decisive example with a large unique simple quotient. The proof of Theorem 1.1 does not require a delicate analysis of random walks as in [ GS24 , GS25 ] . Instead, we use some of their results as a black box and proceed with a different strategy. A fundamental observation is that, by Grün’s lemma on perfect groups, we can implement a process where at each step we quotient the ambient group by its center and then by a non-central minimal abelian normal subgroup. This process stops when the solvable radical is trivial, and it lasts at most \varepsilon^{-1} steps by quasirandomness. To handle the non-central steps we combine a theorem in [ GS25 ] with the “affine conjugating trick” by Eberhard–Murphy–Pyber–Szabó [ EMPS25 ] . The case of central extensions requires a separate argument that relies on Kazhdan constants (Lemma 5.1 ). When the solvable radical is trivial, we actually have a direct product of simple groups by a result of Barbieri and the author [ BS25 ] . Finally, this situation can be handled by an iterative application of another theorem in [ GS25 ] . Theorem 1.1 has some applications that we now describe. To start, Theorems C, D and E in [ GS25 ] are not used in our proof and in fact can be considered special cases. Notably, it also allows us to remove the product theorem (Stage 2) from the hypotheses in the Bourgain–Gamburd expansion machine [ Tao15 , Theorem 1.4.2] (see Corollary 5.4 below). With some more work, we prove the following definitive version of Bourgain–Gamburd-type results: Theorem 1.2 . If G is \varepsilon -quasirandom, then 1+\lfloor\varepsilon^{-1}\rfloor random elements give an expander Cayley graph with high probability. The linear dependence on \varepsilon^{-1} is necessary, simply because an \varepsilon -quasirandom group may require so many elements to be generated (see Example 2.14 (c)). In fact, to obtain Theorem 1.2 from Theorem 1.1 and [ BGGT15 ] , it is sufficient to find a generating set. For this purpose, we use results of Detomi–Lucchini [ DL03 ] and Lucchini–Morini [ LM02 ] from crown theory to show that 1+\lfloor\varepsilon^{-1}\rfloor random elements generate G with high probability. A different application of Theorem 1.1 concerns uniform expansion. The following deep conjecture of Breuillard is reported as “folklore” in [ Bre14 , Conjecture 4.12] : If G is a finite simple group of Lie type of bounded rank, then all connected Cayley graphs of G are uniform expanders. Progress on this problem was made by Breuillard and Gamburd [ BG10 ] (see also Becker–Breuillard [ BB26 ] ), but the general conjecture remains open. By Theorem 1.1 , at least for sets of bounded cardinality, Breuillard’s conjecture is equivalent to a statement for all quasirandom groups. We push this analogy further and propose the following conjecture for all generating sets: Conjecture . If G is \varepsilon -quasirandom, then all connected Cayley graphs of G are \varepsilon -uniform expanders. This appears to be a very difficult problem. Using our methods we are able to prove a weaker, unconditional uniform result concerning diameters. Let us write \mathop{\mathrm{diam}}(G) for the maximum diameter over all connected Cayley graphs of G . Theorem 1.3 . If G is \varepsilon -quasirandom, then \mathop{\mathrm{diam}}(G)\leq(\log|G|)^{O_{\varepsilon}(1)} . This extends the aforementioned theorems of Breuillard–Green–Tao [ BGT11 ] and Pyber–Szabó [ PS16 ] . In

Read the complete text