On the diameter of permutation groups

Harald A. Helfgott¹ ; Ákos Seress²

¹ École Normale Supérieure, Paris, France
² The University of Western Australia, Crawley, Australia and The Ohio State University, Columbus, OH

Annals of mathematics, Tome 179 (2014) no. 2, pp. 611-658.

Résumé

Given a finite group $G$ and a set $A$ of generators, the diameter
$\mathrm{diam}(\Gamma(G,A))$ of the Cayley graph $\Gamma(G,A)$ is the smallest $\ell$ such that every element of $G$ can be expressed as a word of length at most $\ell$ in $A \cup A^{-1}$. We are concerned with bounding $\mathrm{diam}(G):= \mathrm{max}_A\mathrm{diam}(\Gamma(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 $\sqrt{n \log n}$. We give a quasipolynomial upper bound, namely, \[\mathrm{diam}(G) = \mathrm{exp}\left(O((\log n)^4 \log\log n)\right) = \mathrm{exp}\left((\log \log |G|)^{O(1)}\right)\] for $G = \mathrm{Sym}(n)$ or $G = \mathrm{Alt}(n)$, where the implied constants are absolute. This addresses a key open case of Babai’s conjecture on diameters of simple groups. By a result of Babai and Seress (1992), our bound also implies a quasipolynomial upper bound on the diameter of all transitive permutation groups of degree $n$.

Détail

DOI : 10.4007/annals.2014.179.2.4