Measure preserving words are primitive

Puder, Doron; Parzanchevski, Ori

doi:10.1090/S0894-0347-2014-00796-7

Measure preserving words are primitive
HTML articles powered by AMS MathViewer

by Doron Puder and Ori Parzanchevski;

J. Amer. Math. Soc. 28 (2015), 63-97

DOI: https://doi.org/10.1090/S0894-0347-2014-00796-7

Published electronically: April 17, 2014

PDF | Request permission

Abstract:

We establish new characterizations of primitive elements and free factors in free groups, which are based on the distributions they induce on finite groups. For every finite group $G$, a word $w$ in the free group on $k$ generators induces a word map from $G^{k}$ to $G$. We say that $w$ is measure preserving with respect to $G$ if given uniform distribution on $G^{k}$, the image of this word map distributes uniformly on $G$. It is easy to see that primitive words (words which belong to some basis of the free group) are measure preserving w.r.t. all finite groups, and several authors have conjectured that the two properties are, in fact, equivalent. Here we prove this conjecture. The main ingredients of the proof include random coverings of Stallings graphs, algebraic extensions of free groups, and Möbius inversions. Our methods yield the stronger result that a subgroup of $\mathbf {F}_{k}$ is measure preserving if and only if it is a free factor.

As an interesting corollary of this result we resolve a question on the profinite topology of free groups and show that the primitive elements of $\mathbf {F}_{k}$ form a closed set in this topology.

References

Miklós Abért, On the probability of satisfying a word in a group, J. Group Theory 9 (2006), no. 5, 685–694. MR 2253960, DOI 10.1515/JGT.2006.044
Alon Amit and Nathan Linial, Random graph coverings. I. General theory and graph connectivity, Combinatorica 22 (2002), no. 1, 1–18. MR 1883559, DOI 10.1007/s004930200000
N. Alon, Eigenvalues and expanders, Combinatorica 6 (1986), no. 2, 83–96. Theory of computing (Singer Island, Fla., 1984). MR 875835, DOI 10.1007/BF02579166
Alon Amit and Uzi Vishne, Characters and solutions to equations in finite groups, J. Algebra Appl. 10 (2011), no. 4, 675–686. MR 2834108, DOI 10.1142/S0219498811004690
Tatiana Bandman and Boris Kunyavskiĭ, Criteria for equidistribution of solutions of word equations on $\rm SL(2)$, J. Algebra 382 (2013), 282–302. MR 3034482, DOI 10.1016/j.jalgebra.2013.02.031
Andrei Broder and Eli Shamir, On the second eigenvalue of random regular graphs, 28th Annual Symposium on Foundations of Computer Science, IEEE, 1987, pp. 286–294.
Joel Friedman, Relative expanders or weakly relatively Ramanujan graphs, Duke Math. J. 118 (2003), no. 1, 19–35. MR 1978881, DOI 10.1215/S0012-7094-03-11812-8
Joel Friedman, A proof of Alon’s second eigenvalue conjecture and related problems, Memoirs of the AMS 195 (September 2008), no. 910.
The GAP Group, GAP – Groups, Algorithms, and Programming, Version 4.6.5 (2013).
Shelly Garion and Aner Shalev, Commutator maps, measure preservation, and $T$-systems, Trans. Amer. Math. Soc. 361 (2009), no. 9, 4631–4651. MR 2506422, DOI 10.1090/S0002-9947-09-04575-9
Ilya Kapovich and Alexei Myasnikov, Stallings foldings and subgroups of free groups, J. Algebra 248 (2002), no. 2, 608–668. MR 1882114, DOI 10.1006/jabr.2001.9033
Nati Linial and Doron Puder, Word maps and spectra of random graph lifts, Random Structures Algorithms 37 (2010), no. 1, 100–135. MR 2674623, DOI 10.1002/rsa.20304
Michael Larsen and Aner Shalev, Characters of symmetric groups: sharp bounds and applications, Invent. Math. 174 (2008), no. 3, 645–687. MR 2453603, DOI 10.1007/s00222-008-0145-7
Michael Larsen and Aner Shalev, Word maps and Waring type problems, J. Amer. Math. Soc. 22 (2009), no. 2, 437–466. MR 2476780, DOI 10.1090/S0894-0347-08-00615-2
Alexei Miasnikov, Enric Ventura, and Pascal Weil, Algebraic extensions in free groups, Geometric group theory, Trends Math., Birkhäuser, Basel, 2007, pp. 225–253. MR 2395796, DOI 10.1007/978-3-7643-8412-8_{1}2
Alexandru Nica, On the number of cycles of given length of a free word in several random permutations, Random Structures Algorithms 5 (1994), no. 5, 703–730. MR 1300595, DOI 10.1002/rsa.3240050506
Ori Parzanchevski and Doron Puder, Stallings graphs, algebraic extensions and primitive elements in ${F}_2$, Mathematical Proceedings of the Cambridge Philosophical Society (2014). arXiv:1210.6574, to appear.
Ori Parzanchevski and Gili Schul, On the Fourier expansion of word maps, Bull. London Math. Soc. 46 (2014), no. 1, 91–102., DOI 10.1112/blms/bdt068
Doron Puder, Expansion of random graphs: New proofs, new results (2012). arXiv preprint arXiv:1212.5216.
Doron Puder, Primitive words, free factors and measure preservation, Israel Journal of Mathematics , posted on (2013)., DOI 10.1007/s11856-013-0055-2
Doron Puder and Conan Wu, Growth of primitives elements in free groups, Journal of London Mathematical Society (2014). arXiv:1304.7979, to appear.
Dan Segal, Words: notes on verbal width in groups, London Mathematical Society Lecture Note Series, vol. 361, Cambridge University Press, Cambridge, 2009. MR 2547644, DOI 10.1017/CBO9781139107082
Aner Shalev, Word maps, conjugacy classes, and a noncommutative Waring-type theorem, Ann. of Math. (2) 170 (2009), no. 3, 1383–1416. MR 2600876, DOI 10.4007/annals.2009.170.1383
Aner Shalev, Some results and problems in the theory of word maps (L. Lovász, I. Ruzsa, V.T. Sós, and D. Palvolgyi, eds.), Erdős Centennial (Bolyai Society Mathematical Studies), Springer, 2013.
Christian Sievers, Free Group Algorithms – a GAP package, Version 1.2.0 (2012).
John R. Stallings, Topology of finite graphs, Invent. Math. 71 (1983), no. 3, 551–565. MR 695906, DOI 10.1007/BF02095993
Richard P. Stanley, Enumerative combinatorics. Vol. 1, Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, Cambridge, 1997. With a foreword by Gian-Carlo Rota; Corrected reprint of the 1986 original. MR 1442260, DOI 10.1017/CBO9780511805967
Mutuo Takahasi, Note on chain conditions in free groups, Osaka Math. J. 3 (1951), 221–225. MR 46362
Edward C. Turner, Test words for automorphisms of free groups, Bull. London Math. Soc. 28 (1996), no. 3, 255–263. MR 1374403, DOI 10.1112/blms/28.3.255
J. H. van Lint and R. M. Wilson, A course in combinatorics, 2nd ed., Cambridge University Press, Cambridge, 2001. MR 1871828, DOI 10.1017/CBO9780511987045
J. H. C. Whitehead, On Certain Sets of Elements in a Free Group, Proc. London Math. Soc. (2) 41 (1936), no. 1, 48–56. MR 1575455, DOI 10.1112/plms/s2-41.1.48
John H. C. Whitehead, On equivalent sets of elements in a free group, Ann. of Math. 37 (1936), 768–800.
John S. Wilson, Profinite groups, London Mathematical Society Monographs. New Series, vol. 19, The Clarendon Press, Oxford University Press, New York, 1998. MR 1691054