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|$ (ie $1 \ll k = |G|^{ o(1)}$). A conjecture of Aldous and Diaconis (1985) asserts, for $k\gg\log|G|$, that the random walk on this graph exhibits cutoff. When $\log k \lesssim \log\log|G|$ (ie $k = (\log |G|)^{ \mathcal O(1)}$), the only example of a non-Abelian group for which cutoff has been established is the dihedral group. We establish cutoff (as $p\to infty$) for the group of $d \times d$ unit upper triangular matrices with integer entries modulo $p$ (prime), which we denote $U_{ p,d}$, for fixed $d$ or $d$ diverging sufficiently slowly. We allow $1 \ll k \lesssim \log |U_{ p,d}|$ as well as $k\gg\log|U_{ p,d}|$. The cutoff time is $\max\{ \log_k |U_{ p,d}|, \: s_0 k\}$, where $s_0$ is the time at which the entropy of the random walk on $\mathbb Z$ reaches $(\log |U_{ p,d}^\mathrm{ ab}|)/k$, where $U_{ p,d}^\mathrm{ ab} \cong \mathbb Z_p^{ d-1}$ is the Abelianisation of $U_{ p,d}$. When $1 \ll k \ll \log |U_{ p,d}^\mathrm{ ab}|$ and $d \asymp 1$, we find the limit profile. We also prove highly related results for the $d$-dimensional Heisenberg group over $\mathbb Z_p$. The Aldous--Diaconis conjecture also asserts, for $k gg\log |G|$, that the cutoff time should depend only on $k$ and $|G|$. This was verified for all Abelian groups. Our result shows that this is not the case for $U_{ p,d}$: the cutoff time depends on $k$, $|U_{ p,d}| = p^{ d(d-1)/2}$ and $|U_{ p,d}^\mathrm{ ab}|=p^{ d-1}$. We also show that all but $o(|U_{ p,d}|)$ of the elements of $U_{ p,d}$ lie at graph distance $M \pm o(M)$ from the identity, where $M$ is the minimal radius of a ball in $\mathbb Z^k$ of cardinality $|U_{ p,d}^\mathrm{ ab}| = p^{ d-1}$. Finally, we show that the diameter is also asymptotically $M$ when $k \gtrsim \log |U_{ p,d}^\textrm{ ab}|$ and $d\asymp1$.
Categories: math.PR math.GR
