Cutoff for random Cayley graphs of nilpotent groups

To motivate our investigation, let us consider for now the scenario where $G$ is a finite group, $k$ is an integer (allowed to depend on $G$) and $\mathcal{G}_{k}$ denotes the Cayley graph of $G$ with respect to $k$ independently and uniformly chosen random generators. These are elements of $G$ that will generate $G$ with high probability when $k$ is sufficiently large and hence, with slight abuse of language, will be referred to as generators of $G$. We consider values of $k$ with $1\ll\log k\ll\log|G|$ for which $\mathcal{G}_{k}$ is connected with high probability, that is, with probability tending to 1 as $|G|\to\infty$.

Aldous and Diaconis [1] introduced the term “cutoff phenomenon”, which describes the phenomenon where the total variation distance (TV) between the distribution of a random walk and its equilibrium distribution sharply decreases from nearly 1 to nearly 0 within a time interval of smaller order than the mixing time. The material in this paper is motivated by their conjecture on the “universality of cutoff” for the RW on the random Cayley graph $\mathcal{G}_{k}$ given in [1].

Additionally, a secondary aspect of the conjecture suggests that the cutoff time does not rely on the algebraic structure of the group, but rather it can be expressed solely as a function of $k$ and $|G|$.

This conjecture has sparked a substantial body of research, see e.g., [11, 12, 22, 23, 24, 30, 33]. The curious reader is referred to Section 1.3.1 in [17] for a detailed exposition on the literature regarding the progress on the Aldous-Diaconis university conjecture. In this context, we provide a more condensed overview of literature related to this conjecture, which serves as motivations for our work.

In [11, 12], Dou and Hildebrand confirmed the Aldous-Diaconis universality conjecture for all abelian groups. Additionally, their upper bound on the mixing time holds true for all groups. Furthermore, when $\log k\gg\log\log|G|$, this upper bound matches the trivial diameter lower bound of $\log_{k}|G|$, confirming the aforementioned secondary aspect of the conjecture. Hermon and and Olesker-Taylor [17, 18, 20, 21] extend this conjecture to the regime $1\ll k\lesssim\log|G|$ for abelian groups, establishing cutoff under the condition $k-r(G)\gg 1$, where $r(G)$ is the minimal size of a generating subset of $G$. Moreover, when $k-r(G)\asymp k\gg 1$, the cutoff time is given by

where $t_{0}(k,|G|)$ is the time at which the entropy of the rate 1 random walk $W$ on $\mathbb{Z}^{k}$ is $\log|G|$. Due to this definition $t_{0}(k,|G|)$ is also referred to as the entropic time (see Definition 3). Their work confirms that for abelian groups the cutoff time of RW only depends on $|G|$ and $k$.

Building upon this point, the next natural step is to explore the mixing behavior of random walks on nilpotent groups (see Section 1.4.1 for a brief overview of the literature concerning this topic). Hermon and Olesker-Taylor [19] study two canonical families of nilpotent groups: the $d\times d$ unit-upper triangular matrices $U_{m,d}$ with entries in $\mathbb{Z}_{m}$ and the $d$-dimensional Heisenberg group $H_{m,d}$ over $\mathbb{Z}_{m}$ where $m\in\mathbb{N}$ (the results hold under certain assumptions on $m$ depending on the regimes of $k$). Let $G$ be either $U_{m,d}$ or $H_{m,d}$ and $G_{\mathrm{ab}}:=G/[G,G]$ its abelianization. They prove that for $1\ll\log k\ll\log|G|$ the random walk on the Cayley graph $\mathcal{G}_{k}$ exhibits cutoff with high probability at time

where $t_{0}(k,|G_{\mathrm{ab}}|)$ is the time at which the entropy of the rate 1 random walk $W$ on $\mathbb{Z}^{k}$ is $\log|G_{\mathrm{ab}}|$. We compare (2) with (1), the latter of which gives the characterization of cutoff time for abelian groups. Indeed, $t_{0}(k,|G_{\mathrm{ab}}|)$ can be interpreted as the time at which the projection of the walk on $G$ onto the abelianization $G_{\mathrm{ab}}$ exhibits cutoff. This characterization of the cutoff time for random walks on $U_{m,d}$ and $H_{m,d}$ raises a natural question: does (2) characterize the cutoff time for random walks on nilpotent groups in general? This question will be explored in our investigation.

Another natural extension of the current research on random walks on groups involves extending the choice of generators. Rather than requiring the $k$ generators to be chosen independently and uniformly at random from the group $G$, the aim is to advance our understanding to encompass scenarios involving arbitrary choices of generators.

More often than not, the analysis of the mixing of the random walk heavily replies on the specific selection of generators. For example, there is a line of research focusing on understanding the mixing properties of random walks on the unit upper triangular matrix group $U_{p,d}$ with $p$ prime, wherein the set of generators is either $\{I\pm E_{i,i+1}:1\leq i\leq d-1\}$ or $\{I+aE_{i,i+1}:1\leq i\leq d-1,a\in\mathbb{Z}_{p}\}$, where $E_{i,j}$ represents the $d\times d$ matrix with 1 at the entry $(i,j)$ and 0 elsewhere. See Section 1.4.1 for an overview of existing research. The current analysis critically hinges on the fact that an operation $I+aE_{i,i+1}$ corresponds to a row addition/subtraction, allowing the decomposition of the walk’s mixing behavior into the first row and the remaining part of the matrix, the latter of which can be regarded as a $(d-1)\times(d-1)$ matrix. However, such methodologies become inapplicable when dealing with arbitrary generators. It is hence of interest to develop techniques that enable the study of mixing properties of random walks on Cayley graphs using a wider range of prescribed generators.

When $G$ is a nilpotent group and $S$ is a symmetric set of generators consisting of i.i.d. uniform random elements of $G$, we shall see in Theorem 1 that the mixing time of the RW is determined by the abelianization $G_{\mathrm{ab}}$ of $G$, given by the expression (2).

When the generator set is predetermined, in many instances it has also been demonstrated that the mixing time of random walks on groups is primarily determined by the abelianization of the group. In a recent and notable study, Diaconis and Hough [9] introduced a novel approach to establishing a central limit theorem for random walks on unipotent matrix groups driven by a probability measure $\mu$, under certain general constraints. It is worth noting that their methodology applies to various choices of generators. For unit-upper triangular matrices $U_{p,d}$, it has been established that an individual coordinate on the $k$-th diagonal mixes in order $p^{2/k}$ steps, implying the leading role of abelianization (which corresponds to the first diagonal) in the mixing process of this random walk.

Nestoridi and Sly [27] studied the mixing behavior of the rate 1 RW on $U_{m,d}$ under the canonical set of generators $\{I\pm E_{i,i+1}:i\in[d-1]\}$. In their analysis, it is proved that the mixing time of the RW on $U_{m,d}$ is bounded by $O(m^{2}d\log d+d^{2}m^{o(1)})$, where the former term vaguely characterizes the mixing behavior of the RW on the abelianization. This observation becomes clearer when we consider the projected walk on the abelianization, which, under the canonical set of generators, can be viewed as a product chain on $\mathbb{Z}_{m}^{d-1}$ and thus has mixing time of order $m^{2}d\log d$. Essentially, when $m$ is considerably larger than $d$, this upper bound is predominantly dictated by the mixing on the abelianization.

One might naturally inquire about the extent to which the abelianization dictates the mixing time of the RW on a general group. In addition, there is interest in explicitly identifying the dependence of the mixing time on the abelianization, which leads to our next motivation.

As previously discussed, although the entropic time is the mixing time for “most” choice of generators (when $1\ll k\lesssim\log|G|$) for abelian groups and nilpotent groups, finding an explicit choice of generators which gives rise to cutoff at the entropic time is still open — even for the cyclic group of prime order. Part of our motivation is to understand the extent to which this paradigm applies for a given set of generators.

It is worth pointing out that for general non-random choice of generators, the cutoff time is not necessarily given by the entropic time. For instance, Hough [24, Theorem 1.11] shows that for the cyclic group $\mathbb{Z}_{p}$ of prime order the choice of generators $S:=\{0\}\cup\{\pm 2^{i}:0\leq i\leq\lfloor\log_{2}p\rfloor-1\}$, which he describes as “an approximate embedding of the classical hypercube walk into the cycle”, gives rise to a random walk on $\mathbb{Z}_{p}$ that ehxibits cutoff, where the cutoff time is not the entropic time.

A minimal set of generators is a set of elements that generates the group which is minimal in terms of size. For $p$-groups, it is known that the minimal sets of generators can be described by the Frattini subgroup $\Phi=\Phi(G)$ in the sense that any set $\{x_{1},\dots,x_{r}\}\subseteq G$ such that the cosets $\{\Phi x_{i}:1\leq i\leq r\}$ form a basis of $G/\Phi$ gives a generating set of $G$. See, e.g., Diaconis and Saloff-Coste [10, Section 5.C]. A random walk supported on the minimal set of generators is thus referred to as a Frattini walk. Examples of such walks are discussed in Section 5.C of [10]. For the Heisenberg group $H_{p,3}$ with prime $p$, it can be shown that all minimal sets of generators are equivalent from a group theory approach.

Diaconis and Saloff-Coste additionally remarked that based on their experience with the circle and symmetric group, if the number of generators is fixed, most sets of generators should lead to the same convergence rate for the random walk. Motivated by these examples, they ask the following open question (see Remark 2 on Page 23 of [10]): to what extent does the choice of generators effect the mixing behavior?

We give a neat partial answer to this question in Theorem 3. Suppose that $G$ is a $p$-group with $G_{\mathrm{ab}}\cong\mathbb{Z}_{p^{\alpha_{1}}}\oplus\cdots\oplus\mathbb{Z}_{p^{\alpha_{r}}}$ or that $G_{\mathrm{ab}}\cong\mathbb{Z}_{m}^{r}$ for some $m\in\mathbb{N}$. Under very mild assumptions on the rank and step of $G$, for all minimal (symmetric) sets of generators, the corresponding mixing times on $G$ are the same up to smaller order terms and the corresponding relaxation times are the same.

Motivated by the questions discussed in the preceding section, our primary focus in this paper is as follows.

We thank Péter Varjú for suggesting us the problem of extending the analysis from [19] to other¹¹1Namely, the case that $G$ is step 2 and $G_{\mathrm{ab}}\cong\mathbb{Z}_{p}^{r}$, i.e., $G_{\mathrm{ab}}$ is elementary abelian. We also wish to thank him for providing invaluable insights regarding how certain components of the argument from [19] could be interpreted in terms of the general theory of nilpotent groups. nilpotent groups.

In essence, our objective is to develop techniques for studying the mixing properties of random walks, applicable not only under arbitrary choices of generators but also for general groups, without dependence on specific group structures.

We use standard notation and definitions for mixing and cutoff, see e.g. [32, §4 and §18].

In other words, $(X_{N})_{N\in\mathbb{N}}$ is said to exhibits cutoff when the TV distance of the distribution of the chain from equilibrium drops from close to 1 to close to 0 in a short time interval of smaller order than the mixing time.

As briefly discussed in Section 1.1.1, there has been considerable interest in studying the cutoff behavior of random walks on groups. Our goal is to generalize the characterization of cutoff time as $\max\{\log_{k}|G|,t_{0}(k,|G_{\mathrm{ab}}|)\}$ to general nilpotent groups (for random i.i.d. generators).

We now give the formal definition of the entropic time $t_{0}:=t_{0}(k,|G_{\mathrm{ab}})$ and the proposed mixing time.

The entropic time $t_{0}(k,|G_{\mathrm{ab}}|)$ is identified as the cutoff time for the projected random walk $Y_{t}:=G_{2}X_{t}$ on $G_{\mathrm{ab}}$, see [17], which is naturally a lower bound on the mixing time of the RW $X_{t}$ on $G$. To offer insight into the definition of the cutoff time, note that we need to run the RW sufficiently long to ensure that all elements of the group can be reached with reasonable probability, which leads to a lower bound of $\log_{k}|G|$.

Our first result establishes cutoff around time $t_{*}(k,G)$ for the random walk $X$ on $\text{Cay}(G,S)$ where $S$ consists of i.i.d. uniform generators.

For a nilpotent group $G$ and any symmetric set of generators $S\subseteq G$ whose size satisfies an upper bound, we show that the mixing time of the random walk on $G$ is completely determined (up to smaller order terms) by the mixing time of the projected walk on $G_{\mathrm{ab}}$.

As a direct consequence of the proof of Theorem 2, we establish that under the same conditions, the spectral gap of the random walk on $G$ is likewise determined by the spectral gap of its projection onto $G_{\mathrm{ab}}$.

As a consequence of the above results, we can see that for a class of nilpotent groups $G$ whose abelianization has a unique representation, with a symmetric set of generators $S$ of minimal size, the mixing time and the relaxation time (inverse of the spectral gap) of the random walk do not depend on the choice of $S$. In this case, the choice of generators do not effect the mixing behavior. This provides a partial answer to the open question posed in Section 1.1.1.

The mixing property of the random walk $X_{t}$ on the Cayley graph of $G$ is closely related to that of the projected random walk on the Cayley graph of $G_{\mathrm{ab}}$. More precisely, denoting by $Y_{t}:=G_{2}X_{t}$ the projected RW on $G_{\mathrm{ab}}$ and starting with the walk $X_{t}$ being uniform over $G_{2}$, one can observe (see Lemma 3.1) that

As suggested by the following triangle inequality

if the total variation distance between $\mathbb{P}_{\mathrm{id}}(X_{t}=\cdot)$ and $\mathbb{P}_{\pi_{G_{2}}}(X_{t}=\cdot)$ can be nicely controlled then the mixing property of $X_{t}$ is primarily characterized by the mixing of its projection on the abelianization, which we refer to as the reduction to abelianization.

We will prove in Lemma 3.2 that indeed $\|\mathbb{P}_{\mathrm{id}}(X_{t}=\cdot)-\mathbb{P}_{\pi_{G_{2}}}(X_{t}=\cdot)\|_{\mathrm{TV}}$ decays exponentially fast in time with rate at least $(|S|\cdot\mathrm{Diam}_{S}(G_{2})^{2})^{-1}$, where $\mathrm{Diam}_{S}(G_{2})$ is the diameter of $G_{2}$ in $\text{Cay}(G,S)$. This provides a quantitive criterion to determine when the mixing of the walk $X_{t}$ is governed by its projection onto the abelianization. In particular, if the mixing of the projected walk $Y_{t}$ occurs after $\|\mathbb{P}_{\mathrm{id}}(X_{t}=\cdot)-\mathbb{P}_{\pi_{G_{2}}}(X_{t}=\cdot)\|_{\mathrm{TV}}$ had become vanishingly small then the mixing time of $X_{t}$ is roughly that of $Y_{t}$.

Due to the well known connection between the mixing time and the diameter of the graph, see, e.g., [25, Proposition 13.7], for our purpose it is sufficient to prove $\mathrm{Diam}_{S}(G_{2})$ is small enough compared to $\mathrm{Diam}_{S}(G_{\mathrm{ab}})$. Section 2 is devoted to proving an upper bound on $\mathrm{Diam}_{S}(G_{2})$ where the roles of $L$, $|S|$ and $\mathrm{Diam}_{S}(G_{\mathrm{ab}})$ are made explicit.

As a consequence, for any set of generators satisfying $|S|\leq\frac{\log|G|}{8Lr^{L}\log\log|G|}$, one has $\mathrm{Diam}_{S}(G_{2})\lesssim\mathrm{Diam}_{S}(G_{\mathrm{ab}})^{3/4}$ and hence the mixing of $X_{t}$ can be reduced to the mixing of its projection onto the abelianization.

We describe our methodology in relation to the objectives described in Section 1.1.2.

There has been some progress made towards treating general nilpotent groups. In [17, §6], partial results were obtained using a comparison between the mixing time of a general nilpotent group $G$ with a “corresponding” abelian group $\bar{G}:=\oplus_{\ell=1}^{L}G_{\ell}/G_{\ell+1}$ in [17, §6]. See Section 1.2 for the definition of $\{G_{\ell}\}_{\ell\in[L]}$. More specifically, denoting by $\mathcal{G}_{k}$ and $\bar{\mathcal{G}}_{k}$ respectively the random Cayley graphs generated by $k$ i.i.d. uniform generators in $G$ and $\bar{G}$, it is shown that $t_{mix}(\mathcal{G}_{k})/t_{mix}((\bar{\mathcal{G}})_{k})\leq 1+o(1)$ with high probability, thereby offering an upper bound on the mixing time on $\mathcal{G}_{k}$.

This comparison leads to a tight upper bound and thus establishes cutoff when $G$ is a nilpotent group when $G$ has a relatively small commutator subgroup $[G,G]$. Examples of such groups include $p$-groups with “small” commutators and Heisenberg groups of diverging dimension, see [17, Corollary D.1 and D.2]. However, for general nilpotent groups this comparison is not sharp.

While the comparison technique discussed in [17] may not ensure a sharp upper bound on the mixing time for general nilpotent groups, it underscores the approach of examining the mixing behavior in relation to each quotient group $\{G_{\ell}/G_{\ell+1}\}_{\ell\in[L]}$. To obtain the tight upper bound and establish cutoff, we give an accurate representation of the random walk dynamics through the lens of quotient groups.

To give a bit of intuition, let us consider the free nilpotent group of step 2 (i.e., $G_{3}=\{\mathrm{id}\}$). Let $S=\{Z_{i}^{\pm 1}:i\in[k]\}$ be a set of i.i.d. uniform generators. Let $W:=W(t)=(W_{1}(t),\dots,W_{k}(t))$ be an auxiliary process defined based on the random walk $X_{t}$ where $W_{i}(t)$ is the number of times generator $s_{i}$ has been applied minus the number of times $s_{i}^{-1}$ has been applied in the random walk $X:=X_{t}$. Through rearranging, we can express any word in the form

where $(m_{ba})_{a,b\in[k],a<b}$ results from the rearrangement of generators, see (30) for more details. Roughly speaking, $Z_{1}^{W_{1}}\cdots Z_{k}^{W_{k}}$ keeps track of the walk on $G_{\mathrm{ab}}=G/G_{2}$ whereas the term $\prod_{a,b\in[k]:a<b}[Z_{a},Z_{b}]^{m_{ba}}$, which belongs to $G_{2}$, corresponds to the mixing on the quotient group $G_{2}/G_{3}$.

We demonstrate in Section 4.3 that this line of reasoning applies to general nilpotent groups of step $L\geq 2$, see (33). Although the rearranging of generators leads to the presence of multi-fold commutators such as $[[Z_{1},Z_{2}],Z_{3}]$ when $L\geq 3$, we will argue, through a further careful simplification, that the presence of multi-fold commutators does not add to the complexity of the analysis, and one only needs to control the distribution of $\prod_{a,b\in[k]:a<b}[Z_{a},Z_{b}]^{m_{ba}}$ as with the case where $L=2$.

Theorem 2 further implies that for a certain class of nilpotent groups with specific structures in their abelianization, the mixing time remains the same (up to smaller order terms) regardless of the choice of a minimal-sized symmetric set of generators. See Theorem 3 for the precise statement.

Consider the group ${\displaystyle\mathbb{U}_{n}}$ of upper-triangular matrices with $1$’s along the diagonal, so they are the group of matrices

Then, a unipotent group can be defined as a subgroup of some ${\displaystyle\mathbb{U}_{n}}$. This includes the two families of nilpotent groups discussed earlier: the $d\times d$ unit-upper triangular matrices $U_{m,d}$ with entries in $\mathbb{Z}_{m}$ and the $d$-dimensional Heisenberg group $H_{m,d}$ over $\mathbb{Z}_{m}$ where $m\in\mathbb{N}$.

The exploration of random walks on unit upper triangular matrices has led to a substantial body of research. One avenue of investigation involves a simple walk on $U_{m,d}$, the $d\times d$ unit upper triangular matrix group with entries over $\mathbb{Z}_{m}$ for some $m\in\mathbb{N}$: a row is chosen uniformly and added to or subtracted from the row above. Ellenberg [15] studied the diameter of the associated Cayley graph, with $d$ growing, and subsequently improved this in Ellenberg and Tymoczko [16]. Stong [31] gave mixing bounds via analysis of eigenvalues. Coppersmith and Pak [8, 28] look directly at mixing. Further work along this line includes Peres and Sly [29], Nestoridi [26] and Nestoridi and Sly [27]. Notably, Nestoridi and Sly [27] are the first to optimize bounds for $m$ and $d$ simultaneously. Diaconis and Hough [9] introduced a new method for proving a central limit theorem for random walks on unipotent matrix groups.

In the context of i.i.d. uniformly chosen generators, Hermon and Olesker-Taylor [19] prove the characterization of the cutoff time as the entropic time of the projected walk onto the abelianization for the two families of nilpotent groups: the $d\times d$ unit-upper triangular matrices $U_{m,d}$ with entries in $\mathbb{Z}_{m}$ and the $d$-dimensional Heisenberg group $H_{m,d}$ over $\mathbb{Z}_{m}$ where $m\in\mathbb{N}$.

A common theme in the study of mixing times is that “generic” instances often exhibit the cutoff phenomenon. Moreover, this can often be handled via the entropic method, see, e.g., [3, 4, 5]. A more detailed exposition of the known literature can be found in a previous article of one of the authors, see [17, §1.3.5]. Additionally, the entropic method has been applied within the context of random walks on groups, as discussed in [17, 19], which we now explain in a little more depth.

The main idea is to relate the mixing of the random walk $X=X_{t}$ on $\text{Cay}(G,S)$ to that of an auxiliary process $W_{t}$ and study the entropy of $W_{t}$. Suppose $S=\{s_{i}^{\pm 1}:i\in[k]\}$ is given. The auxiliary process $W=W_{t}:=(W_{1}(t),\dots,W_{k}(t))$ is defined based on $X_{t}$ where $W_{i}(t)$ is the number of times generator $s_{i}$ has been applied minus the number of times $s_{i}^{-1}$ has been applied in the random walk $X_{t}$. The observation that $W$ is a rate 1 random walk on $\mathbb{Z}^{k}$ (whose entropy reveals information regarding the mixing of the walk $X$) leads naturally to the definition of the entropic times, see Definition 3. More specifically, the auxiliary process $W$ is related to the original random walk $X$ as follows. We sample two independent copies of the random walk and the auxiliary process, denoted by $(X,W)$ and $(X^{\prime},W^{\prime})$. By Cauchy-Schwarz inequality one has

which relates the mixing of $X$ to the hitting probability of $X$ and $X^{\prime}$, i.e., the probability that $X(X^{\prime})^{-1}=\mathrm{id}$, where the index $t$ is suppressed as it is clear from the context.

When the group $G$ is abelian, given the choice of generators $S$, the total variation distance is a function of $W_{t}$ alone, see [17]. When the group is not abelian, this is not the case. When $G$ is nilpotent, the auxiliary process $W_{t}$ still provides useful (albeit partial) information on $X_{t}$. In this case, to get a full picture of the mixing of the RW, we will combine the knowledge on the auxiliary process $W_{t}$ with further information obtained through analyzing the mixing on the quotient groups $\{Q_{\ell}\}_{\ell\in[L]}$ separately. See Section 4.6 and 4.8 for the complete discussion.