# Bounding the number of character degrees of a finite group in terms of the order of the group

Let $cd(G)$ be the set of degrees of irreducible complex characters of the finite group $G$ (so $cd(G) = \{\chi(1) | \chi\in Irr(G)\}$).

What bounds are known of the form $|cd(G)|\leq f(|G|)$ (ie, what functions $f$ are known which satisfies such an inequality)?

I can show that $|cd(G)|\leq \sqrt[3]{3|G|-7}$ and if $|G|$ is odd that $|cd(G)|\leq \sqrt[3]{\frac{12}{15}|G|}$. On the other hand, one clearly has $|cd(G)|\leq d(|G|)-1$ (where $d(n)$ is the number of divisors of $n$), and this is better asymptotically. There are two reasons for this question. One is that I am looking at certain inequalities which guarantee that a group will be solvable, and having a good bound on $|cd(G)|$ in terms of the order of the group would help. Also, the question is interesting when compared to the Taketa-inequality ($dl(G)\leq |cd(G)|$ which is conjectured to hold for all solvable groups), since clearly the derived length of a solvable group only grows logarithmically in the order of the group (being bounded by the sum of the exponents in the prime factorization of the order of the group).

-
I've taken the liberty of making the question more visible. I hope you don't mind. –  S. Carnahan Mar 16 '11 at 14:11
Not at all, thank you. I just realized that instead of $d(|G|)-1$ one can actually use $d(|G|)/2$ (and I have a feeling that equality is rare except when $G$ has prime order) –  Tobias Kildetoft Mar 17 '11 at 9:47

The number of divisors at least roughly resembles the best achievable lower bound. For each prime $p$, there is a group $G_p$ with $p^3$ elements which has an irreducible representation of dimension 1 (the trivial representation) and an irreducible representation of dimension $p$ (because it's non-abelian). Now let $p_n$ be the $n$th prime. The number $$P_n = p_1p_2\cdots p_n$$ is a type of number with a lot of divisors. If you likewise let $$H_n = G_{p_1} \times G_{p_2} \times \cdots \times G_{p_n},$$ then $H_n$ has an irreducible representation for every $d$ that divides $P_n$, and it has $P^3_n$ elements.

Now, it is not quite true that $P_n$ has more divisors than any $N < P_n$. It is a good strategy for making a number with many divisors, but soon enough it is better to add more factors of $p_1$, then eventually more factors of $p_2$, etc., than to keep adding new prime factors. To understand this situation better, we can make many numbers (but not all numbers) that have more divisors than their predecessors with the "threshold method". The idea is to optimize the ratio $\log(d(N))/\log(N)$ globally by optimizing it locally (with respect to prime factorization). Pick a constant $t > 0$, the threshold, and say that $N$ should have at least $k > 0$ factors of a prime $p$ if and only if $$\frac{\log(k+1) - \log(k)}{\log(p)} \ge t.$$ Then I think that $d(M) < d(N)$ when $M < N$.

In fact, finding large values of $cd(G)$ (which I will use to mean the cardinality of the character degrees rather than the set) is a very similar problem when $G$ is nilpotent. A finite group is nilpotent if and only if it is the product of its Sylow subgroups. The main idea of the construction above is that in this case $cd(G)$ is multiplicative, i.e., the product of its values for $p$-groups. Following the comment by Frieder Ladisch, $cd(G)$ is maximized for $p$-groups by $C_{p^m} \ltimes C_{p^{m+1}}$. (In the first version of the answer I used other $p$-groups that aren't as good.) I.e., this group has character degrees $1,p,\ldots,p^m$, and no $p$ group with $p^{2m}$ or fewer elements can have an irrep with $p^m$ elements. So you can find many record values of $cd(G)$ for nilpotent groups using instead the threshold formula $$\frac{\log(k+1) - \log(k)}{\min(4-k,2)\log(p)} \ge t.$$

Let's incorporate the concept of a "record value" by defining $d'(N)$ to be the maximum of $d(M)$ with $M \le N$. Likewise define $cd'(N)$ to be the maximum of $cd(G)$ with $|G| \le N$. Then I think that the above constructions show that $d'(N)$ and $cd'(N)$ are at least similar functions, and that $$d'(N) > cd'(N) > \sqrt[3]{d'(N)}$$ when $N$ is large enough. In fact I think that the exponent of the second inequality climbs from $1/3$ to some higher value, although for nilpotent groups one also has $$\sqrt{d'(N)} > cd'_{\text{nil}}(N).$$

Let me also mention that the bound $O(\sqrt[3]{|G|})$ follows immediately from the fact that $|G|$ is the sum of the squares of the dimensions of the irreducible representations --- maybe that's what you have in mind with your bound.

-
The order of your group $H_n$ has $4^n$ divisors, and there are $2^n$ different character degrees. In general, a nilpotent group of order $N=p_1^{e_1}\cdot \dotsm\cdot p_n^{e_n}$ has at most $d(N)2^{-n}$ character degrees. I guess that non-nilpotent groups of the same order might have more character degrees. –  Frieder Ladisch Mar 17 '11 at 20:20
By the way, the group $C_{p^{m}}\ltimes C_{p^{m+1}}$ has character degrees $1$, $p$, $\dotsc$, $p^m$. –  Frieder Ladisch Mar 17 '11 at 20:22
@F. Ladisch Thanks for these remarks. That makes the second part of the construction rather simpler. Clearly, then, the lower bound is at least the cube root of the upper bound asymptotically, if one regularizes to make the bounds monotonic. If you can find non-nilpotent examples that do better, cool. –  Greg Kuperberg Mar 17 '11 at 21:18
I don't have a series of non-nilpotent groups that do better, but I've made the observation that if there are non-nilpotent groups of some fixed order, then the maximum of $|cd(G)|$ for all groups of that order is usually obtained for a non-nilpotent group. I'm not sure however, if this makes any difference asymptotically. –  Frieder Ladisch Mar 18 '11 at 11:58