3
$\begingroup$

The question

What is the order of magnitude for the function $n\mapsto |{\rm cd}(S_n)|$?

The motivation

In my research on character degrees of finite groups, I have in recent years been focusing on symmetric groups as a test bed for general conjectures. Among my more recent investigations, I have come up with (what is to me, at least) an interesting reduction: I can prove a statement true regarding the full set ${\rm cd}(S_n)$ of degrees of irreducible, complex-valued characters on the symmetric group of degree $n$ (for a fixed $n$) by showing a statement is true regarding the set of primes $\{p\leq n\mid p~{\rm is~prime}\}$. What I would like is to develop a feeling for just how much of a reduction this is. Obviously, the prime counting function is approximated by $n/\ln n$, but I don't have a feel for, as a function of $n$, how quickly the function $|{\rm cd}(S_n)|$ grows. I have a reduction in effort to a sublinear function, and I would like to know what that reduction is from. Is it quadratic, is it exponential?

The (failed) searches

As an aside, I admit that part of my problem is knowing how to conduct the research. For example, if I do a Google search for "how quickly does |cd(Sn)| grow", I get results pertaining to cancer. If I add "math:" at the beginning, the returns are from freshmen calculus involving convergence of sequences. When I write things out in words using no symbols, other issues become evident. Such searches, when correctly limited to math, are further complicated by the dual use of the word "degree" in this context, the degree of the permutation group versus the degrees of the representations. Furthermore, results abound on the maximal norm of character values and asymptotics related to those values. But, results on the order of magnitute for the function $n\mapsto |{\rm cd}(S_n)|$ are at the very least very well hidden. (OK, not so much; a comment below points out there is an OEIS entry).

$\endgroup$
  • 4
    $\begingroup$ What does $cd(S_n)$ mean? $\endgroup$ – Sam Hopkins Apr 9 at 14:43
  • $\begingroup$ Explained in "motivation". Actually John, there's a problem there with "cd" which is not at all something standard. That's why your Google etc. searches failed, I guess. $\endgroup$ – Richard Apr 9 at 15:09
  • $\begingroup$ @Teo: I have a feel for how standard "cd" is/is not, and point out that, two sentences later, mentioned performing searches with no notations. These are examples, not an exhaustive list of what all I did. $\endgroup$ – John McVey Apr 9 at 15:30
  • $\begingroup$ Can you calculate your function for a few small values of $n$ and then look it up at oeis.org? $\endgroup$ – Gerry Myerson Apr 9 at 22:41
  • 1
    $\begingroup$ It's tabulated out to $n=49$ at oeis.org/A060437 $\endgroup$ – Gerry Myerson Apr 9 at 22:52
3
$\begingroup$

If $cd(S_n)$ is the set of degrees of irreducible, complex-valued characters on the symmetric group $S_n$, then by the basic representation theory of the symmetric group this is the same as the set $\{f^{\lambda}\colon \lambda\vdash n\}$, where for a partition $\lambda\vdash n$, $f^{\lambda}$ is the number of Standard Young Tableaux of shape $\lambda$, which by the hook-length formula has the explicit form $f^{\lambda}=n! \cdot \prod_{u \in \lambda}\frac{1}{h_u!}$. I would imagine that the number of pairs of partitions $\lambda,\nu \vdash n$ with $f^{\lambda}=f^{\nu}$ is very small as a fraction of all pairs of partitions of $n$. And probably that would not be hard to formally establish (for instance using the hook-length formula). So the size $|cd(S_n)|$ of the set of degrees of irreps should be basically the same as the number of partitions on $n$. This is a very famous quantity whose asymptotics are well-understood (in particular the partition number is known grow super-polynomially; for a starting point see e.g. the Wikipedia entry https://en.wikipedia.org/wiki/Partition_function_(number_theory)).

EDIT: As pointed out in the comments below, there are some collisions you do have to worry about if you want to understand precise asymptotics (e.g. a partition and its transpose have the same number of SYT), but nevertheless if you just want to establish that $|cd(S_n)|$ grows super-polynomially, surely this naive reasoning should be enough.

EDIT 2: In the comments a heuristic why there should be few collisions was requested. A simple heuristic why there should be few collisions of values of $f^\lambda$ is that the maximum value of $f^\lambda$ over $\lambda \vdash n$ is on the order of $\sqrt{n!}e^{-\alpha\sqrt{n}}$ (see e.g. https://arxiv.org/abs/1804.04693), while $f^\lambda$ can be as small as one, so the range of values taken on by $f^\lambda$ is quite large (compared to say the number of partitions of $n$).

$\endgroup$
  • 2
    $\begingroup$ There is at least the transpose, which causes collisions. $\endgroup$ – Phil Tosteson Apr 9 at 16:01
  • $\begingroup$ @PhilTosteson: ah, good point. $\endgroup$ – Sam Hopkins Apr 9 at 16:02
  • 2
    $\begingroup$ The main result of this paper: arxiv.org/abs/0709.0897 seems to be that there are arbitrarily large sets of partitions yielding the same irr. character degree, if $n$ is "large enough". $\endgroup$ – Frieder Ladisch Apr 9 at 16:24
  • 1
    $\begingroup$ "...if you want to establish that $|\text{cd}(S_n)|$ grows exponentially..." But of course $p(n)$ itself does not grow exponentially. $\endgroup$ – Sean Eberhard Apr 9 at 17:52
  • $\begingroup$ Okay, is "super-polynomially" better? $\endgroup$ – Sam Hopkins Apr 9 at 17:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.