Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)

Request Permissions   Purchase Content 


Measure preserving words are primitive

Authors: Doron Puder and Ori Parzanchevski
Journal: J. Amer. Math. Soc. 28 (2015), 63-97
MSC (2010): Primary 20E05; Secondary 20E18, 20B30, 68R15, 06A11
Published electronically: April 17, 2014
MathSciNet review: 3264763
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [Abe06] 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 (2007j:20040),
  • [AL02] Alon Amit and Nathan Linial, Random graph coverings. I. General theory and graph connectivity, Combinatorica 22 (2002), no. 1, 1-18. MR 1883559 (2003a:05131),
  • [Alo86] Noga Alon, Eigenvalues and expanders, Combinatorica 6 (1986), no. 2, 83-96. Theory of computing (Singer Island, Fla., 1984). MR 875835 (88e:05077),
  • [AV11] Alon Amit and Uzi Vishne, Characters and solutions to equations in finite groups, J. Algebra Appl. 10 (2011), no. 4, 675-686. MR 2834108,
  • [BK13] 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,
  • [BS87] 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.
  • [Fri03] Joel Friedman, Relative expanders or weakly relatively Ramanujan graphs, Duke Math. J. 118 (2003), no. 1, 19-35. MR 1978881 (2004m:05165),
  • [Fri08] Joel Friedman, A proof of Alon's second eigenvalue conjecture and related problems, Memoirs of the AMS 195 (September 2008), no. 910.
  • [GAP4] The GAP Group, GAP - Groups, Algorithms, and Programming, Version 4.6.5 (2013).
  • [GS09] Shelly Garion and Aner Shalev, Commutator maps, measure preservation, and $ T$-systems, Trans. Amer. Math. Soc. 361 (2009), no. 9, 4631-4651. MR 2506422 (2010f:20019),
  • [KM02] Ilya Kapovich and Alexei Myasnikov, Stallings foldings and subgroups of free groups, J. Algebra 248 (2002), no. 2, 608-668. MR 1882114 (2003a:20039),
  • [LP10] Nati Linial and Doron Puder, Word maps and spectra of random graph lifts, Random Structures Algorithms 37 (2010), no. 1, 100-135. MR 2674623 (2011k:60026),
  • [LS08] Michael Larsen and Aner Shalev, Characters of symmetric groups: sharp bounds and applications, Invent. Math. 174 (2008), no. 3, 645-687. MR 2453603 (2010g:20022),
  • [LS09] Michael Larsen and Aner Shalev, Word maps and Waring type problems, J. Amer. Math. Soc. 22 (2009), no. 2, 437-466. MR 2476780 (2010d:20019),
  • [MVW07] 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 (2009f:20032),
  • [Nic94] 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 (95m:60017),
  • [PP12b] 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.
  • [PS13] Ori Parzanchevski and Gili Schul, On the Fourier expansion of word maps, Bull. London Math. Soc. 46 (2014), no. 1, 91-102.,
  • [Pud12] Doron Puder, Expansion of random graphs: New proofs, new results (2012). arXiv preprint arXiv:1212.5216.
  • [Pud13] Doron Puder, Primitive words, free factors and measure preservation, Israel Journal of Mathematics , posted on (2013).,
  • [PW14] Doron Puder and Conan Wu, Growth of primitives elements in free groups, Journal of London Mathematical Society (2014). arXiv:1304.7979, to appear.
  • [Seg09] Dan Segal, Words: notes on verbal width in groups, London Mathematical Society Lecture Note Series, vol. 361, Cambridge University Press, Cambridge, 2009. MR 2547644 (2011a:20055)
  • [Sha09] Aner Shalev, Word maps, conjugacy classes, and a noncommutative Waring-type theorem, Ann. of Math. (2) 170 (2009), no. 3, 1383-1416. MR 2600876 (2011e:20017),
  • [Sha13] 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.
  • [Sie12] Christian Sievers, Free Group Algorithms - a GAP package, Version 1.2.0 (2012).
  • [Sta83] John R. Stallings, Topology of finite graphs, Invent. Math. 71 (1983), no. 3, 551-565. MR 695906 (85m:05037a),
  • [Sta97] 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 (98a:05001)
  • [Tak51] Mutuo Takahasi, Note on chain conditions in free groups, Osaka Math. J. 3 (1951), 221-225. MR 0046362 (13,721e)
  • [Tur96] Edward C. Turner, Test words for automorphisms of free groups, Bull. London Math. Soc. 28 (1996), no. 3, 255-263. MR 1374403 (96m:20039),
  • [vLW01] Jacobus H. van Lint and Richard M. Wilson, A course in combinatorics, 2nd ed., Cambridge University Press, Cambridge, 2001. MR 1871828 (2002i:05001)
  • [Whi36a] John H. C. Whitehead, On Certain Sets of Elements in a Free Group, Proc. London Math. Soc. S2-41, no. 1, 48. MR 1575455,
  • [Whi36b] John H. C. Whitehead, On equivalent sets of elements in a free group, Ann. of Math. 37 (1936), 768-800.
  • [Wil98] John S. Wilson, Profinite groups, London Mathematical Society Monographs. New Series, vol. 19, The Clarendon Press Oxford University Press, New York, 1998. MR 1691054 (2000j:20048)

Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC (2010): 20E05, 20E18, 20B30, 68R15, 06A11

Retrieve articles in all journals with MSC (2010): 20E05, 20E18, 20B30, 68R15, 06A11

Additional Information

Doron Puder
Affiliation: Einstein Institute of Mathematics, Hebrew University, Jerusalem 91904, Israel

Ori Parzanchevski
Affiliation: School of Mathematics, Institute for Advanced Study, Princeton, New Jersey 08540

Received by editor(s): January 31, 2013
Received by editor(s) in revised form: October 15, 2013, and November 23, 2013
Published electronically: April 17, 2014
Article copyright: © Copyright 2014 American Mathematical Society

American Mathematical Society