On the diameter of permutation groups.

. We give a quasipolynomial upper bound, namely, [ ext{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

.

Review text

Given a finite group \(G\) and a set \(A\) of generators, the diameter of the Cayley graph \(\Gamma(G,A)\) is the least integer \(\ell\) such that every element in \(G\) is a word of length \(\leq\ell\) in \(A\cup A^{-1}\). The diameter \(\mathrm{diam}(G)\) of \(G\) is the maximum over all generating sets \(A\) of the diameter of \(\Gamma(G,A)\). In 1992 it was conjectured by L. Babai that \(\mathrm{diam}(G)\leq(\log|G|)^{O(1)}\) (all implied constants in this review are absolute) for all finite simple groups \(G\) (see [\textit{L. Babai} and \textit{Á. Seress}, Eur. J. Comb. 13, No. 4, 231-243 (1992; Zbl 0783.20001)]). The conjecture is of interest in the analysis of the complexity of group theoretic algorithms and has been extensively studied over the past 20 years, but still remains open. The main theorem of the present paper is that for the alternating group \(\mathrm{diam}(\mathrm{Alt}(n))\leq\exp(O(\log n)^4\log\log n)\). Whilst still not as strong as Babai's conjecture, namely, \(\mathrm{diam}(\mathrm{Alt}(n))=n^{O(1)}=\exp(O(\log n))\), this result is much stronger than the best previously known bound, namely, \(\mathrm{diam}(\mathrm{Alt}(n))\leq\exp((1+o(1))\sqrt{n\log n})\). Furthermore, in the paper referred to above, it was shown that for any transitive permutation group \(G\) of degree \(n\) we have \(\mathrm{diam}(G)\leq\exp(O(\log n)^{3})\cdot\mathrm{diam}(\mathrm{Alt}(k))\) where \(\mathrm{Alt}(k)\) is the largest alternating group which appears as a composition factor of \(G\). Hence as a corollary to their main theorem the authors obtain: \(\mathrm{diam}(G)\leq\exp(O(\log n)^4\log\log n)\) for any transitive permutation group \(G\) of degree \(n\). Further corollaries are also derived: a gap theorem on the difference between the first and second largest eigenvalues of the adjacency matrix for \(\Gamma(G,A)\); and a bound on the diameter of the directed Cayley graph (vertex set \(G\) with \((g,ga)\) (\(g\in G\), \(a\in A\)) as the directed edges) which has the same form as that for the undirected graph. The proof of the main theorem includes results of independent interest. As well as use of random walks and probabilistic arguments, a major theme is that it is often possible to translate combinatorial theorems on subgroups to theorems about subsets \(A\) which are slowly growing (for example, \(|A\cdot A\cdot A|\leq|A|^{1+\varepsilon}\)). See also [\textit{H. A. Helfgott}, J. Eur. Math. Soc. (JEMS) 13, No. 3, 761-851 (2011; Zbl 1235.20047)] and [\textit{E. Breuillard} et al., Geom. Funct. Anal. 21, No. 4, 774-819 (2011; Zbl 1229.20045)]; in the latter paper, slowly growing subsets are referred to as ``approximate groups.

Recommendations

Cites work

Cited in

(47)

This page was built for publication: On the diameter of permutation groups.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2445317)