×

Characters of symmetric groups: sharp bounds and applications. (English) Zbl 1166.20009

Authors’ summary: 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 \(\sigma\in S_n\) has at most \(n^{o(1)}\) cycles of length \(<m\), then \(|\chi(\sigma)|\leq\chi(1)^{1/m+o(1)}\) for all irreducible characters \(\chi\) 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\gg 0\), then every element of \(A_n\) is a product of two values of \(w\).

MSC:

20C30 Representations of finite symmetric groups
05E10 Combinatorial aspects of representation theory
20D60 Arithmetic and combinatorial problems involving abstract finite groups
20P05 Probabilistic methods in group theory
60G50 Sums of independent random variables; random walks
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arad, Z., Herzog, M. (eds.): Products of Conjugacy Classes in Groups. Springer Lect. Notes, vol. 1112. Springer, Berlin (1985) · Zbl 0561.20004
[2] Bertram, E.: Even permutations as a product of two conjugate cycles. J. Comb. Theory, Ser. A 12, 368–380 (1972) · Zbl 0238.20004 · doi:10.1016/0097-3165(72)90102-1
[3] Biane, P.: Representations of symmetric groups and free probability. Adv. Math. 138(1), 126–181 (1998) · Zbl 0927.20008 · doi:10.1006/aima.1998.1745
[4] Borel, A.: On free subgroups of semisimple groups. Enseign. Math. 29, 151–164 (1983) · Zbl 0533.22009
[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) · Zbl 0405.20006
[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) · Zbl 0335.20006
[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)
[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) · Zbl 1064.20071
[9] Diaconis, P., Shahshahani, M.: Generating a random permutation with random transpositions. Z. Wahrsch. Verw. Geb. 57(2), 159–179 (1981) · Zbl 0485.60006 · doi:10.1007/BF00535487
[10] Dixon, J.: The probability of generating the symmetric group. Math. Z. 110, 199–205 (1969) · Zbl 0176.29901 · doi:10.1007/BF01110210
[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) · Zbl 1027.20013 · doi:10.1515/crll.2003.019
[12] Ellers, E.W., Gordeev, N., Herzog, M.: Covering numbers for Chevalley groups. Isr. J. Math. 111, 339–372 (1999) · Zbl 0941.20050 · doi:10.1007/BF02810691
[13] Erdos, P., Turán, P.: On some problems of a statistical group theory. I. Z. Wahrsch. Verw. Geb. 4, 175–186 (1965) · Zbl 0137.25602 · doi:10.1007/BF00536750
[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)) · Zbl 0909.05046
[15] Garion, S., Shalev, A.: Commutator maps, measure preservation, and T-systems. To appear in Trans. Am. Math. Soc. · Zbl 1182.20015
[16] Gowers, W.T.: Quasirandom groups. Preprint (2007) (to appear) · Zbl 1191.20016
[17] Hardy, G.H., Littlewood, J.E., Pólya, G.: Inequalities, 2nd edn. University Press, Cambridge (1952) · Zbl 0047.05302
[18] Husemoller, D.: Ramified coverings of Riemann surfaces. Duke Math. J. 29, 167–174 (1962) · Zbl 0196.34001 · doi:10.1215/S0012-7094-62-02918-6
[19] James, G.D.: The representation theory of the symmetric groups. Lect. Notes Math., vol. 682. Springer, Berlin (1978) · Zbl 0393.20009
[20] Larsen, M.: Word maps have large image. Isr. J. Math. 139, 149–156 (2004) · Zbl 1130.20310 · doi:10.1007/BF02787545
[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) · Zbl 1206.20014
[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) · Zbl 0911.05035 · doi:10.1006/jcta.1998.2869
[24] Liebeck, M.W., Shalev, A.: Diameter of simple groups: sharp bounds and applications. Ann. Math. 154, 383–406 (2001) · Zbl 1003.20014 · doi:10.2307/3062101
[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) · Zbl 1068.20052 · doi:10.1016/S0021-8693(03)00515-5
[26] Liebeck, M.W., Shalev, A.: Fuchsian groups, finite simple groups, and representation varieties. Invent. Math. 159, 317–367 (2005) · Zbl 1134.20059 · doi:10.1007/s00222-004-0390-3
[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) · Zbl 0835.05033
[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) · Zbl 1012.05156 · doi:10.1023/A:1021172928478
[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) · Zbl 1173.20009 · doi:10.1016/j.aim.2007.01.016
[31] Nathanson, M.B.: Additive Number Theory: the classical bases. Grad. Texts Math., vol. 164. Springer, New York (1996) · Zbl 0859.11002
[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) · Zbl 0808.60018 · doi:10.1002/rsa.3240050506
[33] Nikolov, N., Pyber, L.: Product decompositions of quasirandom groups and a Jordan type theorem. Preprint (2007) · Zbl 1228.20020
[34] Nikolov, N., Segal, D.: On finitely generated profinite groups. I. Strong completeness and uniform bounds. Ann. Math. 165, 171–238 (2007) · Zbl 1126.20018 · doi:10.4007/annals.2007.165.171
[35] Nikolov, N., Segal, D.: On finitely generated profinite groups. II. Products in quasisimple groups. Ann. Math. 165, 239–273 (2007) · Zbl 05157394 · doi:10.4007/annals.2007.165.239
[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) · Zbl 1155.20011 · doi:10.1016/j.aim.2008.01.008
[37] Roichman, Y.: Upper bound on the characters of the symmetric groups. Invent. Math. 125(3), 451–485 (1996) · Zbl 0854.20015 · doi:10.1007/s002220050083
[38] Shalev, A.: Word maps, conjugacy classes, and a non-commutative Waring-type theorem. To appear in Ann. Math. · Zbl 1203.20013
[39] Vishne, U.: Mixing and covering in the symmetric groups. J. Algebra 205, 119–140 (1998) · Zbl 0940.20007 · doi:10.1006/jabr.1997.7366
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.