Cutoff for almost all random walks on Abelian groups

Abstract

Consider the random Cayley graph of a finite group $G$ with respect to $k$ generators chosen uniformly at random, with $1\ll \log k\ll \log |G|$; denote it by $G_k$. A conjecture of Aldous and Diaconis (1985) asserts, for $k\gg \log |G|$, that the random walk on this graph exhibits cutoff. Further, the cutoff time should be a function only of $k$ and $|G|$, to sub-leading order. This was verified for all Abelian groups in the ’90s. We extend the conjecture to $1\ll k\lesssim \log |G|$. We establish cutoff for all Abelian groups under the condition $k-d(G)\gg 1$, where $d(G)$ is the minimal size of a generating subset of $G$, which is almost optimal. The cutoff time is described (abstractly) in terms of the entropy of random walk on ${\mathbb{Z}}^k$. This abstract definition allows us to deduce that the cutoff time can be written as a function only of $k$ and $|G|$ when $d(G)\ll \log |G|$ and $k-d(G)\asymp k\gg 1$; this is not the case when $d(G)\asymp \log |G|\asymp k$. For certain regimes of $k$, we find the limit profile of the convergence to equilibrium. Wilson (1997) conjectured that ${\mathbb{Z}}_2^d$ gives rise to the slowest mixing time for $G_k$ amongst all groups of size at most $2^d$. We give a partial answer, verifying the conjecture for nilpotent groups. This is obtained via a comparison result of independent interest between the mixing times of nilpotent $G$ and a corresponding Abelian group $\overline{G}$, namely the direct sum of the Abelian quotients in the lower central series of $G$. We use this to refine a celebrated result of Alon and Roichman 1994: we show for nilpotent $G$ that $G_k$ is an expander provided $k-d(\overline{G})\gtrsim \log |G|$. As another consequence, we establish cutoff for nilpotent groups with relatively small commutator subgroup, including high-dimensional special groups, such as Heisenberg groups. The aforementioned results all hold with high probability over the random Cayley graph $G_k$.