Asymptotics of characters of symmetric groups related to Stanley character formula

Valentin Féray; Piotr Śniady

doi:http://doi.org/10.4007/annals.2011.173.2.6

Abstract

We prove an upper bound for characters of the symmetric groups. In particular, we show that there exists a constant $a>0$ with a property that for every Young diagram $\lambda$ with $n$ boxes, $r(\lambda)$ rows and $c(\lambda)$ columns $$ \left| \frac{\mathrm{Tr}\, \rho^{\lambda}(\pi)}{\mathrm{Tr}\, \rho^{\lambda}(e)} \right| \leq \left[a \max\left(\frac{r(\lambda)}{n},\frac{c(\lambda)}{n},\frac{|\pi|}{n} \right)\right]^{|\pi|}, $$ where $|\pi|$ is the minimal number of factors needed to write $\pi\in S_n$ as a product of transpositions. We also give uniform estimates for the error term in the Vershik-Kerov’s and Biane’s character formulas and give a new formula for free cumulants of the transition measure.

Show/hide bibliography for this article

[Biane1997] $Go to document$ P. Biane, "Some properties of crossings and partitions," Discrete Math., vol. 175, iss. 1-3, pp. 41-53, 1997.

Show bibtex

@article {Biane1997, MRKEY = {1475837}, AUTHOR = {Biane, Philippe}, TITLE = {Some properties of crossings and partitions}, JOURNAL = {Discrete Math.}, FJOURNAL = {Discrete Mathematics}, VOLUME = {175}, YEAR = {1997}, NUMBER = {1-3}, PAGES = {41--53}, ISSN = {0012-365X}, CODEN = {DSMHA4}, MRCLASS = {05A18 (05C25 06A07)}, MRNUMBER = {1475837}, MRREVIEWER = {Konrad Engel}, DOI = {10.1016/S0012-365X(96)00139-2}, ZBLNUMBER = {0892.05006}, }
[Biane1998] $Go to document$ P. Biane, "Representations of symmetric groups and free probability," Adv. Math., vol. 138, iss. 1, pp. 126-181, 1998.

Show bibtex

@article {Biane1998, MRKEY = {1644993}, AUTHOR = {Biane, Philippe}, TITLE = {Representations of symmetric groups and free probability}, JOURNAL = {Adv. Math.}, FJOURNAL = {Advances in Mathematics}, VOLUME = {138}, YEAR = {1998}, NUMBER = {1}, PAGES = {126--181}, ISSN = {0001-8708}, CODEN = {ADMTA4}, MRCLASS = {05E10 (20C30 46L54)}, MRNUMBER = {1644993}, MRREVIEWER = {Dimitri Y. Shlyakhtenko}, DOI = {10.1006/aima.1998.1745}, ZBLNUMBER = {0927.20008}, }
[Biane2003] $Go to document$ P. Biane, "Characters of symmetric groups and free cumulants," in Asymptotic Combinatorics with Applications to Mathematical Physics, New York: Springer-Verlag, 2003, vol. 1815, pp. 185-200.

Show bibtex

@incollection {Biane2003, MRKEY = {2009840}, AUTHOR = {Biane, Philippe}, TITLE = {Characters of symmetric groups and free cumulants}, BOOKTITLE = {Asymptotic Combinatorics with Applications to Mathematical Physics}, VENUE={{S}t. {P}etersburg, 2001}, SERIES = {Lecture Notes in Math.}, VOLUME = {1815}, PAGES = {185--200}, PUBLISHER = {Springer-Verlag}, ADDRESS = {New York}, YEAR = {2003}, MRCLASS = {20C30 (05E10 46L54)}, MRNUMBER = {2009840}, MRREVIEWER = {Burkhard K{ü}lshammer}, DOI = {10.1007/3-540-44890-X_8}, ZBLNUMBER = {1035.05098}, }
[Dolega2010] $Go to document$ M. Dolega, V. Féray, and P. Śniady, "Explicit combinatorial interpretation of Kerov character polynomials as numbers of permutation factorizations," Adv. Math., vol. 225, pp. 81-120, 2010.

Show bibtex

@article{Dolega2010, author={Dolega, M. and Féray, V. and {\'S}niady, P.}, TITLE={Explicit combinatorial interpretation of {K}erov character polynomials as numbers of permutation factorizations}, JOURNAL={Adv. Math.}, VOLUME={225}, YEAR={2010}, PAGES={81--120}, DOI={10.1016/j.aim.2010.02.011}, }
[Feray2010] $Go to document$ V. Féray, "Stanley’s formula for characters of the symmetric group," Ann. Comb., vol. 13, pp. 453-461, 2010.

Show bibtex

@article{Feray2010, author={F{é}ray, V.}, TITLE={{S}tanley's formula for characters of the symmetric group}, JOURNAL={Ann. Comb.}, VOLUME={13}, YEAR={2010}, PAGES={453--461}, MRNUMBER = {2581097}, DOI = {10.1007/S00026-009-0038-5}, }
[GouldenJackson1992] $Go to document$ I. P. Goulden and D. M. Jackson, "The combinatorial relationship between trees, cacti and certain connection coefficients for the symmetric group," European J. Combin., vol. 13, iss. 5, pp. 357-365, 1992.

Show bibtex

@article {GouldenJackson1992, MRKEY = {1181077}, AUTHOR = {Goulden, I. P. and Jackson, D. M.}, TITLE = {The combinatorial relationship between trees, cacti and certain connection coefficients for the symmetric group}, JOURNAL = {European J. Combin.}, FJOURNAL = {European Journal of Combinatorics}, VOLUME = {13}, YEAR = {1992}, NUMBER = {5}, PAGES = {357--365}, ISSN = {0195-6698}, MRCLASS = {05E15 (05C25 20B30)}, MRNUMBER = {1181077}, MRREVIEWER = {Andrea Brini}, ZBLNUMBER = {0804.05023}, DOI = {10.1016/S0195-6698(05)80015-0}, }
[Kerov1993] S. Kerov, "The asymptotics of interlacing sequences and the growth of continual Young diagrams," Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI), vol. 205, iss. 13, pp. 21-29, 179, 1993.

Show bibtex

@article {Kerov1993, MRKEY = {1255301}, AUTHOR = {Kerov, S.}, TITLE = {The asymptotics of interlacing sequences and the growth of continual {Y}oung diagrams}, JOURNAL = {Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. {\rm (POMI)}}, FJOURNAL = {Rossiĭskaya Akademiya Nauk. Sankt-Peterburgskoe Otdelenie. MatematicheskiĭInstitut im. V. A. Steklova. Zapiski Nauchnykh Seminarov (POMI)}, VOLUME = {205}, YEAR = {1993}, NUMBER = {13}, PAGES = {21--29, 179}, ISSN = {0373-2703}, MRCLASS = {05E10 (60B99 60C05)}, MRNUMBER = {1255301}, ZBLNUMBER = {0804.33018}, }
[Kerov1999] S. Kerov, "A differential model for the growth of Young diagrams," in Proc. St. Petersburg Math. Soc., Vol. IV, Providence, RI: Amer. Math. Soc., 1999, vol. 188, pp. 111-130.

Show bibtex

@incollection{Kerov1999, author={Kerov, S.}, TITLE = {A differential model for the growth of {Y}oung diagrams}, BOOKTITLE={Proc. St. Petersburg Math. Soc., Vol. {\rm IV}}, SERIES={Amer. Math. Soc. Transl. Ser. 2}, VOLUME={188}, PUBLISHER={Amer. Math. Soc.}, ADDRESS={Providence, RI}, YEAR={1999}, PAGES={111--130}, MRNUMBER={1732430}, ZBLNUMBER = {0929.05090}, }
[MooreRussellSniady] $Go to document$ C. Moore, A. Russell, and P. Śniady, "On the impossibility of a quantum sieve algorithm for graph isomorphism," in STOC’07—Proceedings of the 39th Annual ACM Symposium on Theory of Computing, New York: ACM, 2007, pp. 536-545.

Show bibtex

@incollection {MooreRussellSniady, MRKEY = {2402479}, AUTHOR = {Moore, Cristopher and Russell, Alexander and {\'S}niady, Piotr}, TITLE = {On the impossibility of a quantum sieve algorithm for graph isomorphism}, BOOKTITLE = {{\rm S{TOC}'07}---{P}roceedings of the 39th {A}nnual {\rm ACM} {S}ymposium on {T}heory of {C}omputing}, PAGES = {536--545}, PUBLISHER = {ACM}, ADDRESS = {New York}, YEAR = {2007}, MRCLASS = {81P68 (05C60 05C85 68Q05)}, MRNUMBER = {2402479}, DOI = {10.1145/1250790.1250868}, ZBLNUMBER = {05485489}, }
[RattanSniady2008] $Go to document$ A. Rattan and P. Śniady, "Upper bound on the characters of the symmetric groups for balanced Young diagrams and a generalized Frobenius formula," Adv. Math., vol. 218, iss. 3, pp. 673-695, 2008.

Show bibtex

@article {RattanSniady2008, MRKEY = {2414318}, AUTHOR = {Rattan, Amarpreet and {\'S}niady, Piotr}, TITLE = {Upper bound on the characters of the symmetric groups for balanced {Y}oung diagrams and a generalized {F}robenius formula}, JOURNAL = {Adv. Math.}, FJOURNAL = {Advances in Mathematics}, VOLUME = {218}, YEAR = {2008}, NUMBER = {3}, PAGES = {673--695}, ISSN = {0001-8708}, CODEN = {ADMTA4}, MRCLASS = {20C30 (05E10)}, MRNUMBER = {2414318}, MRREVIEWER = {Mark J. Wildon}, DOI = {10.1016/j.aim.2008.01.008}, ZBLNUMBER = {1155.20011}, }
[Roichman1996] $Go to document$ Y. Roichman, "Upper bound on the characters of the symmetric groups," Invent. Math., vol. 125, iss. 3, pp. 451-485, 1996.

Show bibtex

@article {Roichman1996, MRKEY = {1400314}, AUTHOR = {Roichman, Yuval}, TITLE = {Upper bound on the characters of the symmetric groups}, JOURNAL = {Invent. Math.}, FJOURNAL = {Inventiones Mathematicae}, VOLUME = {125}, YEAR = {1996}, NUMBER = {3}, PAGES = {451--485}, ISSN = {0020-9910}, CODEN = {INVMBH}, MRCLASS = {20C30}, MRNUMBER = {1400314}, MRREVIEWER = {David Gluck}, DOI = {10.1007/s002220050083}, ZBLNUMBER = {0854.20015}, }
[SinaiSoshnikov1998] $Go to document$ Y. G. Sinai and A. B. Soshnikov, "A refinement of Wigner’s semicircle law in a neighborhood of the spectrum edge for random symmetric matrices," Funktsional. Anal. i Prilozhen., vol. 32, iss. 2, pp. 56-79, 96, 1998.

Show bibtex

@article {SinaiSoshnikov1998, MRKEY = {1647832}, AUTHOR = {Sinai, Ya. G. and Soshnikov, A. B.}, TITLE = {A refinement of {W}igner's semicircle law in a neighborhood of the spectrum edge for random symmetric matrices}, JOURNAL = {Funktsional. Anal. i Prilozhen.}, FJOURNAL = {Rossiĭskaya Akademiya Nauk. Funktsional\cprime nyĭAnaliz i ego Prilozheniya}, VOLUME = {32}, YEAR = {1998}, NUMBER = {2}, PAGES = {56--79, 96}, ISSN = {0374-1990}, MRCLASS = {82B41 (15A52 60F99)}, MRNUMBER = {1647832}, MRREVIEWER = {Boris A. Khoruzhenko}, DOI = {10.1007/BF02482597}, ZBLNUMBER = {0930.15025}, }
[Speicher1998] R. Speicher, "Combinatorial theory of the free product with amalgamation and operator-valued free probability theory," Mem. Amer. Math. Soc., vol. 132, iss. 627, p. x, 1998.

Show bibtex

@article {Speicher1998, MRKEY = {1407898}, AUTHOR = {Speicher, Roland}, TITLE = {Combinatorial theory of the free product with amalgamation and operator-valued free probability theory}, JOURNAL = {Mem. Amer. Math. Soc.}, FJOURNAL = {Memoirs of the American Mathematical Society}, VOLUME = {132}, YEAR = {1998}, NUMBER = {627}, PAGES = {x+88}, ISSN = {0065-9266}, CODEN = {MAMCAU}, MRCLASS = {46L50 (81S25)}, MRNUMBER = {1407898}, MRREVIEWER = {Hari Bercovici}, ZBLNUMBER = {0935.46056}, }
[Stanley2003/04] R. P. Stanley, "Irreducible symmetric group characters of rectangular shape," Sém. Lothar. Combin., vol. 50, p. 11, 2003/04.

Show bibtex

@article {Stanley2003/04, MRKEY = {2049555}, AUTHOR = {Stanley, Richard P.}, TITLE = {Irreducible symmetric group characters of rectangular shape}, JOURNAL = {Sém. Lothar. Combin.}, FJOURNAL = {Séminaire Lotharingien de Combinatoire}, VOLUME = {50}, YEAR = {2003/04}, PAGES = {11}, ISSN = {1286-4889}, MRCLASS = {20C30 (05E10)}, MRNUMBER = {2049555}, MRREVIEWER = {Christine Bessenrodt}, ZBLNUMBER= {1068.20017}, }
[Stanley-preprint] R. P. Stanley, A conjectured combinatorial interpretation of the normalized irreducible character values of the symmetric group, 2006.

Show bibtex

@misc{Stanley-preprint, author={Stanley, Richard P.}, TITLE = {A conjectured combinatorial interpretation of the normalized irreducible character values of the symmetric group}, NOTE={preprint}, YEAR={2006}, ARXIV={math.CO/0606467}, }
[VershikKerov1981] A. M. Vershik and S. V. Kerov, "Characters and factor representations of the infinite symmetric group," Dokl. Akad. Nauk SSSR, vol. 257, iss. 5, pp. 1037-1040, 1981.

Show bibtex

@article {VershikKerov1981, MRKEY = {0614033}, AUTHOR = {Vershik, A. M. and Kerov, S. V.}, TITLE = {Characters and factor representations of the infinite symmetric group}, JOURNAL = {Dokl. Akad. Nauk SSSR}, FJOURNAL = {Doklady Akademii Nauk SSSR}, VOLUME = {257}, YEAR = {1981}, NUMBER = {5}, PAGES = {1037--1040}, ISSN = {0002-3264}, MRCLASS = {20C32}, MRNUMBER = {0614033}, ZBLNUMBER = {0534.20008}, }
[VoiculescuDykemaNica1992] D. V. Voiculescu, K. J. Dykema, and A. Nica, Free Random Variables, Providence, RI: Amer. Math. Soc., 1992, vol. 1.

Show bibtex

@book {VoiculescuDykemaNica1992, MRKEY = {1217253}, AUTHOR = {Voiculescu, D. V. and Dykema, K. J. and Nica, A.}, TITLE = {Free Random Variables}, SERIES = {{\rm CRM} Monogr. Series}, VOLUME = {1}, NOTE = {A noncommutative probability approach to free products with applications to random matrices, operator algebras and harmonic analysis on free groups}, PUBLISHER = {Amer. Math. Soc.}, ADDRESS = {Providence, RI}, YEAR = {1992}, PAGES = {vi+70}, ISBN = {0-8218-6999-X}, MRCLASS = {46L50 (46L10 47B80 60H99)}, MRNUMBER = {1217253}, MRREVIEWER = {Roland Speicher}, ZBLNUMBER = {0795.46049}, }
[Zvonkin1997] $Go to document$ A. Zvonkin, "Matrix integrals and map enumeration: an accessible introduction," Math. Comput. Modelling, vol. 26, iss. 8-10, pp. 281-304, 1997.

Show bibtex

@article {Zvonkin1997, MRKEY = {1492512}, AUTHOR = {Zvonkin, A.}, TITLE = {Matrix integrals and map enumeration: an accessible introduction}, NOTE = {Combinatorics and physics (Marseilles, 1995)}, JOURNAL = {Math. Comput. Modelling}, FJOURNAL = {Mathematical and Computer Modelling}, VOLUME = {26}, YEAR = {1997}, NUMBER = {8-10}, PAGES = {281--304}, ISSN = {0895-7177}, CODEN = {MCMOEG}, MRCLASS = {81Q30 (05C30 81T18)}, MRNUMBER = {1492512}, MRREVIEWER = {R{\u{a}}zvan Gelca}, DOI = {10.1016/S0895-7177(97)00210-0}, ZBLNUMBER = {1185.81083}, }

Asymptotics of characters of symmetric groups related to Stanley character formula

Abstract

Authors