OP-00955 Open

Random generators of the alternating group give fast mixing

Fix $k$ and pick $x_1, \dots, x_k$ independently and uniformly at random from the alternating group $A_n$. Equidistribution of the random walk in time $O(n \log n)$ is one of the equivalent forms of the statement that $x_1, \dots, x_k$ form an expanding set of generators. It may even hold for $k = 2$, although it is not known for any pair of elements of $A_n$. A positive answer would imply that the diameter of $A_n$ with respect to these generators is $O(n \log n)$ with probability tending to $1$; the best known bound is $O(n^2 \log^C n)$, due to Helfgott, Seress and Zuk.

Problem. Is it true that, almost surely as $n \to \infty$, the random walk on $A_n$ with generators $x_1^{\pm 1}, \dots, x_k^{\pm 1}$ equidistributes in time $O(n \log n)$?

Source: B. Green, 100 open problems (version of January 2026), Problem 79.

Imported from people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf.

Classification

Primary: GR — Group Theory
Secondary: CO, PR
Keywords: alternating groups, Cayley graphs, expanders, mixing time, random walks on groups
Literature checked: Oct. 26, 2026 by clemens-admin

References

@article{helfgott2015random,
  author = {Helfgott, Harald A. and Seress, {\'A}kos and Zuk, Andrzej},
  title = {Random generators of the symmetric group: diameter, mixing time and spectral gap},
  journal = {Journal of Algebra},
  volume = {421},
  pages = {349--368},
  year = {2015},
  doi = {10.1016/j.jalgebra.2014.08.033},
  eprint = {1311.6742},
  archivePrefix = {arXiv}
}

@incollection{saloffcoste2004,
  author = {Saloff-Coste, Laurent},
  title = {Random walks on finite groups},
  booktitle = {Probability on Discrete Structures},
  series = {Encyclopaedia of Mathematical Sciences},
  volume = {110},
  pages = {263--346},
  publisher = {Springer},
  year = {2004},
  doi = {10.1007/978-3-662-09444-0_5}
}

@article{kassabov2007,
  author = {Kassabov, Martin},
  title = {Symmetric groups and expander graphs},
  journal = {Inventiones Mathematicae},
  volume = {170},
  number = {2},
  pages = {327--354},
  year = {2007},
  doi = {10.1007/s00222-007-0065-y},
  eprint = {math/0505624},
  archivePrefix = {arXiv}
}

@misc{breuillard2018lubotzky,
  author = {Breuillard, Emmanuel and Lubotzky, Alexander},
  title = {Expansion in simple groups},
  year = {2018},
  eprint = {1807.03879},
  archivePrefix = {arXiv}
}

@misc{green100open,
  author = {Green, Ben},
  title = {100 open problems},
  howpublished = {\url{https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf}},
  note = {Problem 79; version of January 2026, most recent update December 2025},
  year = {2026}
}

Citing this problem

This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.

OP-00955, "Random generators of the alternating group give fast mixing", clopen.solutions.