Cutoff for almost all random walks on Abelian groups

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