Skip to main content
SpringerLink
Log in

Characters of symmetric groups: sharp bounds and applications

  • Published:
Inventiones mathematicae Aims and scope

Abstract

We provide new estimates on character values of symmetric groups which hold for all characters and which are in some sense best possible. It follows from our general bound that if a permutation σ∈S n has at most n o(1) cycles of length <m, then |χ(σ)|≤χ(1)1/m+o(1) for all irreducible characters χ of S n . This is a far reaching generalization of a result of Fomin and Lulov.

We then use our various character bounds to solve a wide range of open problems regarding mixing times of random walks, covering by powers of conjugacy classes, as well as probabilistic and combinatorial properties of word maps.

In particular we prove a conjecture of Rudvalis and of Vishne on covering numbers, and a conjecture of Lulov and Pak on mixing times of certain random walks on S n .

Our character-theoretic methods also yield best possible solutions to Waring type problems for alternating groups A n , showing that if w is a non-trivial word, and n≫0, then every element of A n is a product of two values of w.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Arad, Z., Herzog, M. (eds.): Products of Conjugacy Classes in Groups. Springer Lect. Notes, vol. 1112. Springer, Berlin (1985)

  2. Bertram, E.: Even permutations as a product of two conjugate cycles. J. Comb. Theory, Ser. A 12, 368–380 (1972)

    Article  MATH  MathSciNet  Google Scholar 

  3. Biane, P.: Representations of symmetric groups and free probability. Adv. Math. 138(1), 126–181 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  4. Borel, A.: On free subgroups of semisimple groups. Enseign. Math. 29, 151–164 (1983)

    MATH  MathSciNet  Google Scholar 

  5. Brenner, J.L.: Covering theorems for finite nonabelian simple groups. IX. How the square of a class with two nontrivial orbits in S n covers A n . Ars Comb. 4, 151–176 (1977)

    MATH  MathSciNet  Google Scholar 

  6. Brenner, J.L., Riddell, J.: Covering theorems for finite nonabelian simple groups. VII. Asymptotics in the alternating groups. Ars Comb. 1, 77–108 (1976)

    MathSciNet  Google Scholar 

  7. Diaconis, P.: Group Representations in Probability and Statistics. Institute of Mathematical Statistics Lecture Notes – Monograph Series, vol. 11. Institute of Mathematical Statistics, Hayward, CA (1988)

    MATH  Google Scholar 

  8. Diaconis, P.: Random walks on groups: characters and geometry. In: Groups St. Andrews 2001 in Oxford, Vol. I. Lond. Math. Soc. Lect. Note Ser., vol. 304, pp. 120–142. Cambridge Univ. Press, Cambridge (2003)

    Google Scholar 

  9. Diaconis, P., Shahshahani, M.: Generating a random permutation with random transpositions. Z. Wahrsch. Verw. Geb. 57(2), 159–179 (1981)

    Article  MATH  MathSciNet  Google Scholar 

  10. Dixon, J.: The probability of generating the symmetric group. Math. Z. 110, 199–205 (1969)

    Article  MATH  MathSciNet  Google Scholar 

  11. Dixon, J.D., Pyber, L., Seress, Á., Shalev, A.: Residual properties of free groups and probabilistic methods. J. Reine Angew. Math. 556, 159–172 (2003)

    MATH  MathSciNet  Google Scholar 

  12. Ellers, E.W., Gordeev, N., Herzog, M.: Covering numbers for Chevalley groups. Isr. J. Math. 111, 339–372 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  13. Erdős, P., Turán, P.: On some problems of a statistical group theory. I. Z. Wahrsch. Verw. Geb. 4, 175–186 (1965)

    Article  Google Scholar 

  14. Fomin, S., Lulov, N.: On the number of rim hook tableaux. Zap. Nauchn. Semin. POMI 223, 219–226 (1995); Teor. Predstav. Din. Sistemy, Kombin. Algoritm. Metody. I, 219–226, 340 (translation in J. Math. Sci. (New York) 87(6), 4118–4123 (1997))

  15. Garion, S., Shalev, A.: Commutator maps, measure preservation, and T-systems. To appear in Trans. Am. Math. Soc.

  16. Gowers, W.T.: Quasirandom groups. Preprint (2007) (to appear)

  17. Hardy, G.H., Littlewood, J.E., Pólya, G.: Inequalities, 2nd edn. University Press, Cambridge (1952)

    MATH  Google Scholar 

  18. Husemoller, D.: Ramified coverings of Riemann surfaces. Duke Math. J. 29, 167–174 (1962)

    Article  MATH  MathSciNet  Google Scholar 

  19. James, G.D.: The representation theory of the symmetric groups. Lect. Notes Math., vol. 682. Springer, Berlin (1978)

    MATH  Google Scholar 

  20. Larsen, M.: Word maps have large image. Isr. J. Math. 139, 149–156 (2004)

    Article  MATH  Google Scholar 

  21. Larsen, M.: How often is a partition an n’th power? arXiv: math.CO/9712223

  22. Larsen, M., Shalev, A.: Word maps and Waring type problems. To appear in J. Am. Math. Soc. (2007)

  23. Lawther, R., Liebeck, M.W.: On the diameter of a Cayley graph of a simple group of Lie type based on a conjugacy class. J. Comb. Theory, Ser. A 83, 118–137 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  24. Liebeck, M.W., Shalev, A.: Diameter of simple groups: sharp bounds and applications. Ann. Math. 154, 383–406 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  25. Liebeck, M.W., Shalev, A.: Fuchsian groups, coverings of Riemann surfaces, subgroup growth, random quotients and random walks. J. Algebra 276, 552–601 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  26. Liebeck, M.W., Shalev, A.: Fuchsian groups, finite simple groups, and representation varieties. Invent. Math. 159, 317–367 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  27. Lubotzky, A.: Cayley graphs: eigenvalues, expanders and random walks. In: Surveys in Combinatorics, Stirling 1995. Lond. Math. Soc. Lect. Note Ser., vol. 218, pp. 155–189. Cambridge Univ. Press, Cambridge (1995)

    Google Scholar 

  28. Lulov, N.: Random walks on the symmetric groups. Ph.D. Thesis, Harvard University (1996)

  29. Lulov, N., Pak, I.: Rapidly mixing random walks and bounds on characters of the symmetric groups. J. Algebr. Comb. 16, 151–163 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  30. Müller, T.W., Schlage-Puchta, J.-C.: Character theory of symmetric groups, subgroup growth of Fuchsian groups, and random walks. Adv. Math. 213, 919–982 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  31. Nathanson, M.B.: Additive Number Theory: the classical bases. Grad. Texts Math., vol. 164. Springer, New York (1996)

    MATH  Google Scholar 

  32. Nica, A.: On the number of cycles of given length of a free word in several random permutations. Random Struct. Algorithms 5(5), 703–730 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  33. Nikolov, N., Pyber, L.: Product decompositions of quasirandom groups and a Jordan type theorem. Preprint (2007)

  34. Nikolov, N., Segal, D.: On finitely generated profinite groups. I. Strong completeness and uniform bounds. Ann. Math. 165, 171–238 (2007)

    MATH  MathSciNet  Google Scholar 

  35. Nikolov, N., Segal, D.: On finitely generated profinite groups. II. Products in quasisimple groups. Ann. Math. 165, 239–273 (2007)

    Article  MathSciNet  Google Scholar 

  36. Rattan, A., Śniady, P.: Upper bound on the characters of the symmetric groups for balanced Young diagrams and a generalized Frobenius formula. Adv. Math. 218(3), 673–695 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  37. Roichman, Y.: Upper bound on the characters of the symmetric groups. Invent. Math. 125(3), 451–485 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  38. Shalev, A.: Word maps, conjugacy classes, and a non-commutative Waring-type theorem. To appear in Ann. Math.

  39. Vishne, U.: Mixing and covering in the symmetric groups. J. Algebra 205, 119–140 (1998)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Indiana University, Bloomington, IN, 47405, USA

    Michael Larsen

  2. Einstein Institute of Mathematics, Hebrew University, Givat Ram, Jerusalem, 91904, Israel

    Aner Shalev

Authors
  1. Michael Larsen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Aner Shalev
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Michael Larsen.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Larsen, M., Shalev, A. Characters of symmetric groups: sharp bounds and applications. Invent. math. 174, 645–687 (2008). https://doi.org/10.1007/s00222-008-0145-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00222-008-0145-7

Keywords

Search

Navigation