On the diameter of permutation groups. (Q2445317): Difference between revisions

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''.