2011/09/16 by H. A. Helfgott, Harald A. Helfgott, Ákos Seress +3 · 1 citation
Computer Science · Mathematics · #05C25 #20B05 #20B30 #20D60 #20F69 #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Group Theory (math.GR) #Limits and Structures in Graph Theory #Number Theory (math.NT) #Probability (math.PR) #math.CO #math.GR #math.NT #math.PR #msc:05C25 #msc:20B05 #msc:20B30 #msc:20D60 #msc:20F69
paper · pdf · doi:10.48550/arxiv.1109.3550
42 pages. Minimal additions. Last version, to appear in Ann. of Math
openalex publication_date 2011/09/16 · arxiv created 2013/12/31 · arxiv updated 2014/01/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a finite group G and a set A of generators, the diameter diam(Γ(G,A)) of the Cayley graph Γ(G,A) is the smallest ℓ such that every element of G can be expressed as a word of length at most ℓ in A ∪ A-1. We are concerned with bounding diam(G):= maxA diam(Γ(G,A)). It has long been conjectured that the diameter of the symmetric group of degree n is polynomially bounded in n, but the best previously known upper bound was exponential in √(n log n). We give a quasipolynomial upper bound, namely, diam(G) = exp(O((log n)4 loglog n)) = exp((log log |G|)O(1)) for G = Sym(n) or G = \Alt(n), where the implied constants are absolute. This addresses a key open case of Babai's conjecture on diameters of simple groups. By standard results, our bound also implies a quasipolynomial upper bound on the diameter of all transitive permutation groups of degree n.