Cutoff for Random Walks on Upper Triangular Matrices

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 \mathrm{\mid }G\mathrm{\mid }$ (ie $1 \ll k = |G|^{o(1)}$)\mathrm{.}AconjectureofAldousandDiaconis(1985)asserts,for$k\gg\log|G|$, that the random walk on this graph exhibits cutoff. When $\log k\lesssim \log \log \mathrm{\mid }G\mathrm{\mid }$ (ie $k=(\log \mathrm{\mid }G\mathrm{\mid }{)}^{\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$unituppertriangularmatriceswithintegerentriesmodulo$p$(prime),whichwedenote$U_{p,d}$,forfixed$d$or$d$ diverging sufficiently slowly. We allow $1\ll k\lesssim \log \mathrm{\mid }{U}_{p,d}\mathrm{\mid }$ as well as $k\gg \log \mathrm{\mid }{U}_{p,d}\mathrm{\mid }$. The cutoff time is $\max \{{\log }_k\mathrm{\mid }{U}_{p,d}\mathrm{\mid },s_{0}k\}$, where $s_0$ is the time at which the entropy of the random walk on $\mathbb{Z}$ reaches $(\log \mathrm{\mid }{U}_{p,d}^{\mathrm{a}\mathrm{b}}\mathrm{\mid })\mathrm{/}k$, where $U_{p,d}^$\mathrm{a}\mathrm{b}$ \cong \mathbb Z_p^{d-1}$istheAbelianisationof$U_{p,d}$\mathrm{.}When$1 \ll k \ll \log |U_{p,d}^$\mathrm{a}\mathrm{b}$|$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 $kgg\log \mathrm{\mid }G\mathrm{\mid }$, that the cutoff time should depend only on $k$ and $\mathrm{\mid }G\mathrm{\mid }$. 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$, $\mathrm{\mid }{U}_{p,d}\mathrm{\mid }=p^{d(d-1)\mathrm{/}2}$ and $\mathrm{\mid }{U}_{p,d}^{\mathrm{a}\mathrm{b}}\mathrm{\mid }=p^{d-1}$. We also show that all but $o(\mathrm{\mid }{U}_{p,d}\mathrm{\mid })$ 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 $\mathrm{\mid }{U}_{p,d}^{\mathrm{a}\mathrm{b}}\mathrm{\mid }=p^{d-1}$. Finally, we show that the diameter is also asymptotically $M$ when $k \gtrsim \log |U_{p,d}^$\text{ab}$|$and$d\asymp1$.