Cutoff for product replacement on finite groups (Q783793): Difference between revisions

Let \(G\) be a finite group, \([n]:=\{1,2,\cdots,n\}\), and \(G^n\) be the set of all functions \(\sigma: [n]\to G\). Denote by \(\mathcal{S}\) the space of generating \(n\)-tuples, i.e., the set of \(\sigma\) whose values generate \(G\) as a group: \[ \mathcal{S}:=\{\sigma\in G^n: \langle \sigma(1),\dots,\sigma(n)\rangle=G\}. \] Define the so-called product replacement chain \((\sigma_t)_{t\geq 0}\) on \(\mathcal{S}\) as follows: if we have a current state \(\sigma\), then uniformly at random, choose an ordered pair \((i,j)\) of distinct integers in \([n]\), and change the value of \(\sigma(i)\) to \(\sigma(i)\sigma(j)^{\pm 1}\), where the signs are chosen with equal probability. This paper shows that the total-variation mixing time of the chain has a cutoff at time \(\frac{3}{2}n\log n\) with window of order \(n\) as \(n\to \infty\). This extends a result of \textit{A. Ben-Hamou} and the first author [Electron. Commun. Probab. 23, Paper No. 32, 10 p. (2018; Zbl 1397.60096)] (who proved the result for \(G=\mathbb{Z}/2\)) and confirms a conjecture of \textit{P. Diaconis} and \textit{L. Saloff-Coste} [Invent. Math. 134, No. 2, 251--299 (1998; Zbl 0921.60003)] that for an arbitrary but fixed finite group, the mixing time of the product replacement chain is \(O(n\log n)\).