Cutoff for Random Walks on Upper Triangular Matrices

MaRDI QIDQ6328737zbMATH OpenFDO

Authors Jonathan Hermon, Sam Olesker-Taylor

Publication date 7 November 2019

Mathematics Subject Classification ID

Distance in graphs (05C12) Random graphs (graph-theoretic aspects) (05C80) Random walks on graphs (05C81) Finite nilpotent groups, (p)-groups (20D15) Probability measures on groups or semigroups, Fourier transforms, factorization (60B15) Combinatorial probability (60C05) Continuous-time Markov processes on discrete state spaces (60J27) Processes in random environments (60K37)

Abstract: Consider the random Cayley graph of a finite group $G$ with respect to $k$ generators chosen uniformly at random, with $1lllogklllog|G|$ (ie $1llk=|G{|}^{o(1)}$). A conjecture of Aldous and Diaconis (1985) asserts, for $kgglog|G|$, that the random walk on this graph exhibits cutoff. When $logklesssimloglog|G|$ (ie $k=(log|G|{)}^{mathcalO(1)}$), the only example of a non-Abelian group for which cutoff has been established is the dihedral group. We establish cutoff (as $poinfty$) for the group of $dimesd$ 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 $1llklesssimlog|U_{p,d}|$ as well as $kgglog|U_{p,d}|$. The cutoff time is $maxlo{g}_k|U_{p,d}|,:s_{0}k$, where $s_0$ is the time at which the entropy of the random walk on $mathbbZ$ reaches $(log|U_{p,d}^{m}athrmab|)/k$, where $U_{p,d}^{m}athrmabcongmathbb{Z}_p^{d-1}$ is the Abelianisation of $U_{p,d}$. When $1llklllog|U_{p,d}^{m}athrmab|$ and $dasymp1$, 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 $kgglog|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}^{m}athrmab|=p^{d-1}$. We also show that all but $o(|U_{p,d}|)$ of the elements of $U_{p,d}$ lie at graph distance $Mpmo(M)$ from the identity, where $M$ is the minimal radius of a ball in $mathbb{Z}^k$ of cardinality $|U_{p,d}^{m}athrmab|=p^{d-1}$. Finally, we show that the diameter is also asymptotically $M$ when $kgtrsimlog|U_{p,d}^{e}xtrmab|$ and $dasymp1$.

This page was built for publication: Cutoff for Random Walks on Upper Triangular Matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6328737)