Growth of unbounded subsets in nilpotent groups, word statistics and random polygons

Let $G$ be a group. Let $g(k,n)$ be the maximum number of length-n words over an arbitrary k-letter subset within $G$. How does $g(k,n)$ behave? Obviously $g(k,n)$ is at most $k^n$, and Semple-Shalev proved that if $G$ is finitely generated and residually finite then $g(k,n)<k^n$ (for some, and hence for all sufficiently large k,n) if and only if G is virtually nilpotent. In this case, it is natural to ask how far can g(k,n) be from $k^n$. For k fixed and n ending to infinity, $g(k,n)$ grows polynomially.

Our group-theoretic result is a quantification of the Semple-Shalev Theorem at the other extreme, where $k=\Theta(n)$. Specifically, for a finitely generated residually finite group G, $lim_{n\rightarrow \infty} g(n,n)/n^n$ is either zero, if and only if G is virtually abelian, or at least 4/5, which is sharp for G being (any) Heisenberg group; for higher free nilpotent groups, this limit is 1.

Along the way, we encounter the following combinatorial problem. The 'pair histogram' of a function $f\colon [n]\rightarrow [n]$ is the data consisting of the quantities $#\{(i,j)|i\leq j, f(i)=a, f(j)=b\}$ for each $a,b\in [n]$. What is the probability that a uniformly random function is uniquely determined by its pair histogram? The answer converges to 2/3, and we moreover calculate the limit distribution of the number of sources of pair histograms.

We also interpret our results by means of random lattice paths in $\mathbb{Z}^n$ and their projected polygons, and provide a model-theoretic characterization (by means of free submodels and polynomial identities) of having suboptimal $g(k,n)$, which is valid in various classes of algebraic structures.

This is a joint work with Hagai Lavner.

https://us02web.zoom.us/j/87856132062

Meeting ID: 878 5613 2062