Asymptotics of characters of symmetric groups related to Stanley character formula

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.

  • [Biane1997] Go to document P. Biane, "Some properties of crossings and partitions," Discrete Math., vol. 175, iss. 1-3, pp. 41-53, 1997.
    @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.
    @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.
    @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.
    @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.
    @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.
    @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.
    @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.
    @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.
    @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.
    @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.
    @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.
    @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.
    @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.
    @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.
    @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.
    @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.
    @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.
    @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},
      }

Authors

Valentin Féray

Université Bordeaux 1
Talence, France

Piotr Śniady

Polish Academy of Sciences
Warszawa, Poland

and

University of Wroclaw
Wroclaw
Poland