2019/11/07 by Jonathan Hermon, Hermon, Jonathan, Sam Olesker-Taylor +1 · 1 citation
Mathematics · #05C12 #05C80 #05C81 #20D15 #60B15 #60C05 #60J27 #60K37 #FOS: Mathematics #Geometric and Algebraic Topology #Graph theory and applications #Group Theory (math.GR) #Markov Chains and Monte Carlo Methods #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.1911.02974
openalex publication_date 2019/11/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Consider the random Cayley graph of a finite group G with respect to k generators chosen uniformly at random, with 1 ≪ log k ≪ log |G| (ie 1 ≪ k = |G|o(1)). A conjecture of Aldous and Diaconis (1985) asserts, for k≫log|G|, that the random walk on this graph exhibits cutoff. When log k \lesssim loglog|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→ infty) for the group of d × d unit upper triangular matrices with integer entries modulo p (prime), which we denote Up,d, for fixed d or d diverging sufficiently slowly. We allow 1 ≪ k \lesssim log |Up,d| as well as k≫log|Up,d|. The cutoff time is max\logk |Up,d|, s0 k\, where s0 is the time at which the entropy of the random walk on \mathbb Z reaches (log |Up,dab|)/k, where Up,dab ≅ \mathbb Zpd-1 is the Abelianisation of Up,d. When 1 ≪ k ≪ log |Up,dab| and d \asymp 1, we find the limit profile. We also prove highly related results for the d-dimensional Heisenberg group over \mathbb Zp. The Aldous--Diaconis conjecture also asserts, for k gglog |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 Up,d: the cutoff time depends on k, |Up,d| = pd(d-1)/2 and |Up,dab|=pd-1. We also show that all but o(|Up,d|) of the elements of Up,d lie at graph distance M ± o(M) from the identity, where M is the minimal radius of a ball in \mathbb Zk of cardinality |Up,dab| = pd-1. Finally, we show that the diameter is also asymptotically M when k \gtrsim log |Up,d^\textrmab| and d\asymp1.