Séminaire Lotharingien de Combinatoire, 86B.79 (2022), 12 pp.
Be'eri Greenfeld and Hagai Lavner
Growth of Unbounded Sets in Nilpotent Groups and Random Mapping Statistics
Abstract.
For a group G, we asymptotically quantify the maximum number of length-n words over an arbitrary n-letter subset of G. If G is finitely generated and residually finite, then either this function is exponentially bounded, which happens if and only if G is virtually abelian, or else it is bounded from below by (e-1/4+o(1))nn; the latter bound cannot be improved, namely, it is attained for the Heisenberg group. For higher-step free nilpotent groups, the asymptotic behavior becomes (1-o(1))nn.
As a key ingredient in the proof, we calculate the number of pair histograms of functions f : [n] -> [n] and the probability that a random function f : [n] -> [n] can be uniquely determined by its pair histogram. A geometric interpretation of group laws of the Heisenberg group by means of closed paths attached to words in the free group and their projected oriented polygons is given.
Received: November 25, 2021.
Accepted: March 4, 2022.
Final version: April 1, 2022.
The following versions are available: