Statistics of irreps of S_n that can be read off the Young diagram, and consequences of Kerov-Vershik - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T17:31:02Z http://mathoverflow.net/feeds/question/8776 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/8776/statistics-of-irreps-of-s-n-that-can-be-read-off-the-young-diagram-and-consequen Statistics of irreps of S_n that can be read off the Young diagram, and consequences of Kerov-Vershik JSE 2009-12-13T18:08:05Z 2009-12-25T22:10:46Z <p>Alexei Oblomkov recently told me about the beautiful theorem of Kerov and Vershik, which says that "almost all Young diagrams look the same." More precisely: take a random irreducible representation of S_n (in Plancherel measure, which assigns a probability of (dim chi)^2 / (n!) to an irrep chi) and draw its Young diagram, normalized to have fixed area. Rotate the diagram 45 degrees and place the vertex at the origin of the Cartesian plane, so that it lies above the graph of y = |x|. Then there is a fixed curve, with equation</p> <p>$$y = \left\{\begin{array}{ll} |x|, &amp; |x| > 2 \\ \frac 2\pi(x \arcsin\frac x2 + \sqrt{4-x^2}), &amp; |x| \leq 2 \end{array}\right.$$</p> <p>such that the normalized Young diagram is very close to the curve with probability very close to 1.</p> <p>My question: what asymptotic statements about irreducible characters of S_n can be "read off" the Kerov-Vershik theorem? In a sense, this isn't a question about Kerov-Virshik at all, but a question about which interesting statistics of irreducible characters can be read off the shape of the Young diagram. </p> <p>There are some tautological answers: for instance, if f(chi) is the height of the first column of chi, then I guess Kerov-Virshik shows that </p> <p>f(chi) / sqrt(n)</p> <p>is very probably very close to 2 as n gets large (if I did this computation right -- in any event it concentrates around a fixed value.) But I don't really have in mind any representation-theoretic meaning for f(chi).</p> http://mathoverflow.net/questions/8776/statistics-of-irreps-of-s-n-that-can-be-read-off-the-young-diagram-and-consequen/8778#8778 Answer by Greg Kuperberg for Statistics of irreps of S_n that can be read off the Young diagram, and consequences of Kerov-Vershik Greg Kuperberg 2009-12-13T18:21:37Z 2009-12-13T19:59:27Z <p>This isn't a very general answer, but it is a convenient and significant one. You can read off the typical dimension of a random representation, by the hook length formula. Of course it is not as simple as, oh here's a formula, because you have to check whether the formula is stable. However, the hook-length formula is a factorial divided by a product of hook lengths. So you can check that the logarithm of the formula is indeed statistically stable. Up to normalization, it limits to a well-behaved integral over the Kerov-Vershik shape.</p> <p><hr /></p> <p>The dimension of a group representation is of course $\chi(1)$, the trace of the identity. Given the nice behavior of this statistic in a random representation, it is natural to ask about the typical value of $\chi(\sigma)$ for some other type of permutation $\sigma$. Two problems arise. First, $\sigma$ isn't really one type of permutation, but rather some natural infinite sequence of permutations. Second, the Murnaghan-Nakayama formula for $\chi(\sigma)$, and probably any fully general rule, isn't statistically stable. The Murnaghan-Nakayama rule is a recursive alternating sum; in order to apply it to a large Plancherel-random representation you would have to know a lot about the local statistics of its tableau, and not just its shape. For instance, suppose that $\sigma$ is a transposition. Then the MN rule tells you to take a certain alternating sum over rim dominos of the tableau $\lambda$. (The sign is positive for the horizontal dominos and negative for the vertical dominos.) I suspect that there is a typical value for $\chi(\sigma)$ when $\sigma$ is a transposition, or probably any permutation of fixed type that is local in the sense that a transposition is local. But this would use an elaborate refinement of the Kerov-Vershik theorem, analogous to the local central limit theorem augmented by a local difference operator, and not just the original Kerov-Vershik.</p> <p>However, I did find another character limit in this spirit that is better behaved. <a href="http://www.springerlink.com/content/225u383111038061/" rel="nofollow">Fomin and Lulov</a> established a product formula for the number of $r$-rim hook tableaux, which is also $\chi(\sigma)$ when $\sigma$ is a "free" permutation consisting entirely of $r$-cycles (and no fixed points or cycle lengths that are factors of $r$). This includes the important case of fixed-point-free involutions. If $\sigma$ acts on $mr$ letters, then according to them, the number of these is $$\chi_\lambda(\sigma) = \frac{m!}{\prod_{r|h(t)} (h(t)/r)},$$ where $h(t)$ is the hook length of the hook at some position $t$ in the shape $\lambda$.</p> <p>Happily, this is just a product formula and not an alternating sum or even a positive sum. To approximate the logarithm of this character with an integral, you only need a mild refinement of Kerov-Vershik, one that says that the hook length $h(t)$ of a typical position $t$ is uniformly random modulo $r$. (So this is a good asymptotic argument when $r$ is fixed or only grows slowly.)</p> <p><hr /></p> <p><strong>Correction:</strong> JSE already thought of the first part of my answer, which I stated overconfidently. The estimate for $\log \chi(1)$ (and in the other cases of course) is an improper integral, I guess, so it does not follow just from the statement of Kerov-Vershik that the integral gives you an accurate estimate of the form $$\log \chi(1) = C\sqrt{n}(1+o(1)).$$ However, it looks like these issues have been swept away by later, stronger versions of the original Kerov-Vershik result. The arXiv paper <a href="http://arxiv.org/abs/math.CO/0304010" rel="nofollow">Kerov's central limit theorem for the Plancherel measure on Young diagrams</a> establishes not just a typical limit for the dimension (and other character values), but also a central limit theorem.</p> http://mathoverflow.net/questions/8776/statistics-of-irreps-of-s-n-that-can-be-read-off-the-young-diagram-and-consequen/8822#8822 Answer by Hugh Thomas for Statistics of irreps of S_n that can be read off the Young diagram, and consequences of Kerov-Vershik Hugh Thomas 2009-12-14T01:56:03Z 2009-12-14T01:56:03Z <p>There is a beautiful interpretation of f(chi) (that is to say, of the length of the first column of the partition), though it isn't very representation-theoretic. </p> <p>One way to generate Plancherel measure on partitions is to take uniformly at random a permutation of ${1,\dots,n}$ and apply Robinson-Schensted-Knuth to get a pair of Young tableaux of the same shape, and then take the partition encoded by that shape. </p> <p>The length of the first column in the shape corresponding to a permutation $\pi$ is the length of the longest decreasing sequence in $\pi$, while the length of the first row is the length of the longest increasing sequence in $\pi$. </p> <p>So Kerov-Vershik says (among other things) that the length of the longest decreasing sequence in a random permutation of ${1,\dots,n}$ is $2\sqrt{n}$. For more along these lines, see <a href="http://math.mit.edu/~rstan/papers/ids.pdf" rel="nofollow">Richard Stanley's 2006 ICM talk</a>.</p> http://mathoverflow.net/questions/8776/statistics-of-irreps-of-s-n-that-can-be-read-off-the-young-diagram-and-consequen/9755#9755 Answer by Richard Stanley for Statistics of irreps of S_n that can be read off the Young diagram, and consequences of Kerov-Vershik Richard Stanley 2009-12-25T22:10:46Z 2009-12-25T22:10:46Z <p>A good paper related to this question is P. Biane, Representations of symmetric groups and free probability , Advances in Mathematics 138, 126-181 (1998), item [4] at <a href="http://www.dma.ens.fr/~biane/publi.html" rel="nofollow">http://www.dma.ens.fr/~biane/publi.html</a>.</p>