Growth of unbounded sets in nilpotent groups and random mapping statistics (Q6161702)

Let \(G\) be a finitely generated infinite group, and suppose that \[ \gamma_G^{\max}(n):=\sup_{S \subset G, |S|\leq n} |S^n| <n^n \] for some sufficiently large \(n\) (this condition is called \textit{collapsing} by \textit{J. F. Semple} and \textit{A. Shalev} [J. Algebra 157, No. 1, 43--50 (1993; Zbl 0814.20022) and \textit{A. Shalev} [J. Algebra 157, No. 1, 51--62 (1993; Zbl 0814.20023)]). The aim of the paper under review is to compare the growth of \(\gamma_G^{\max}(n)\) to that of \(n^n\). In particular, the authors prove that either \(\gamma_G^{\max}(n)\) is exponentially bounded (this happens if and only if \(G\) is virtually abelian) or \(\gamma_G^{\max}(n)\geq\big(e^{-\frac{1}{4}}+o(1)\big)n^n\) (see Theorem 1.1). The latter inequality cannot be improved since it becomes an equality when \(G\) is the integral Heisenberg group; it should be noted that if \(G\) is free nilpotent of class \(c>2\), then actually \(\gamma_G^{\max}(n)=\big(1-o(1)\big)n^n\) (see Theorem 1.2). A key step in the proof consists in showing that the number of pair histograms of functions \(f:[n]\rightarrow[n]\) is \(\big(e^{-\frac{1}{4}}+o(1)\big)n^n\) (see Theorem 1.4) and that the probability that a random function \(f:[n]\rightarrow[n]\) is uniquely determined by its pair histogram converges to \(e^{1/2}\) as \(n\to\infty\) (see Theorem 1.5). Recall that \([n]=\{1,\dots,n\}\) and that if \(f:[n]\to[n]\) is a function, then the \textit{pair histogram} of \(f\) is the data consisting of both tuples \[ \big(\#f^{-1}(a)\big)_{a\in[a]}\quad\text{ and }\quad\big(\#\{1\leq i<j\leq n: f(i)=a,\,f(j)=b\}\big)_{a,b\in[n]}. \]