## How small can a group with an n-dimensional irreducible complex representation be?

More precisely, what is the smallest exponent e such that, for every n, there exists a group of size at most Cn^e for some absolute constant C and with an n-dimensional irreducible complex representation?

I know that e ≤ 3. For various special values of n we can attain the lower bound e ≥ 2. For example, if n+1 = q is a power of a prime then the group of affine linear transformations ax + b on Fq is doubly transitive, so the linearization of this group action decomposes into the trivial representation and an irreducible representation.

Edit: Oops. Reading Noah's comment, I probably should've justified the upper bound. I hope this example is correct: let zeta be an nth root of unity and consider the group generated by the diagonal matrix (zeta, zeta, ... zeta), the diagonal matrix (1, zeta, zeta^2, ... zeta^{n-1}), and a cyclic permutation matrix of order n. It can be verified that this is a group of order n^3 and that its elements span M_n(C) , so the given representation is irreducible.

-
When you say size at most Cn^e, do you mean that is the order of the group, or the order of its image in GL_n(C)? – S. Carnahan Oct 14 2009 at 23:44
Just to rephrase the question. Suppose n is a really generic number that doesn't have any nice number theoretic properties. What's the smallest group you can construct with an irrep of dimension n? – Noah Snyder Oct 15 2009 at 0:57
It's not clear to me how you managed to get examples showing e=3. – Noah Snyder Oct 15 2009 at 1:19
Nice example. If I understand correctly as an abstract group your group is (Z/n x Z/n) semidirect Z/n where the semidirect product uses the action of Z/n by the 2x2 matrix (1 1)(0 1). – Noah Snyder Oct 15 2009 at 3:32
Here is a particular choice of n which seems hard to me: Wikipedia en.wikipedia.org/wiki/Linnik%27s_theorem suggests (but doesn't say) that there should be infinitely many primes p such that the first prime q which is 1 mod p is of order p^2. If n is such a p, can anyone beat e=3? – David Speyer Oct 15 2009 at 3:41
show 1 more comment

I posted a question about primes in arithmetic progressions and was told my understanding is wrong. Although proving this would be harder than the generalized Riemmann hypothesis, the expectation of experts is that, for any n, there is a prime q which is 1 mod n and is O(n^{1+ \epsilon}). In that case, Z/n acting on Z/q would achieve e = 2+\epsilon.

It seems like the best result we are likely to prove is that the only way to beat e=3 is to find a small prime power which is 1 mod n.

-

Here's half a proof:

The answer should be e=3. You've showed that's always realizable, so all I need to do is exhibit infinitely many n so that any group with an n-dim irrep has dimension at least c n^3, for some fixed constant c < 1/2. All the n's I exhibit will be prime, so let n=p. I also want that (p-1)/2 is prime.

Assume for contradiction a group G with #G smaller than p^3 and a p-dimensional irrep. Consider a p-Sylow subgroup of G. Clearly it has size p or p^2. In particular there are only three options: Z/p, Z/p^2, and Z/p x Z/p.

If #G_p is p^2, then the number of Sylow p subgroups is congruent to 1 and divides G/p^2 < p. Hence G_p is a normal subgroup. The dimension of any irrep of a group always divides the index of any normal abelian subgroup. Hence G has size at least p^3.

So G_p is Z/p. If G_p were normal, then by the above fact p would divide its index in G, which is nonsense. So G_p has kp+1 conjugates. So the normalizer of G_p has index kp+1. Now we use that (p-1)/2 is prime to conclude that either G_p is central in its normalizer, or else the normalizer has size at least p(p-1)/2. In the latter case the whole group has size at least p(p-1)(p+1)/2.

Therefore G_p=Z/p is central in its normalizer so by the Burnside normal complement theorem it has a normal complement and G = N \semidirect Z/p for some normal subgroup N. By the "transport de structure" theorem from Serre, any irrep of G is either induced from a representation of a proper subgroup H containing N, or else its restriction to N is isotypic. Since the index of N is p which is the dimension of the irrep, in the first case the rep is induced from a 1-dim irrep of N. In the latter case, since N has no p-dimensional irreps, the restriction of to N is p copies of a 1-dim irrep. But by Frobenius reciprocity the induction of this 1-dim rep would contain p copies of our irrep, which is ridiculous. So our irrep is induced from a 1-dim rep of N.

Now we can replace G with G/[N,N] (which makes sense because a characteristic subgroup of a normal subgroup is normal), and we still have a p-dim rep of G (given by the same induction), and we've shrunk the size. So we can assume that N is abelian. To finish the proof we need to use the right version of the number theory argument David suggested.

-
Ahh, great. Let me point out where I was heading with by Dirichlet's theorem comments above: Suppose that q is 1 mod p. Then Z/p acts on Z/q; the semi-direct product has order pq and an irrep of dimension p. I wanted to claim that we always were dealing with semidirect products where Z/p acts on something, but I didn't see the details. Noah, can you get to anything like that? – David Speyer Oct 15 2009 at 5:41
Yeah, getting that Z/p had a normal complement was my goal for that last paragraph, but I can't seem to get there yet. – Noah Snyder Oct 15 2009 at 5:47
You can't get a lower bound of precisely n^3, since the L_2 series (i.e., PSL(2,Fp)) is an infinite sequence of counterexamples. If p is 1 mod 4, the group has order (p^2-1)p/2, and irreps of dimension 1, p, p+1, p-1, and (p+1)/2. – S. Carnahan Oct 15 2009 at 15:47
It's basically the same prime powers q, but for q congruent to -1 mod 4, we get with (q-1)/2 instead of (q+1)/2. – S. Carnahan Oct 15 2009 at 15:59
So what if I take c < 1/2 and assume that (p-1)/2 is prime. Then either Burnside normal complement works, or else we know exactly what the normalizer of Z/p is. – Noah Snyder Oct 15 2009 at 17:11

It looks like you can get around Noah's use of the (ludicrously difficult) conjecture of the existence of infinitely many Sophie Germain primes by appealing to the classification of finite simple groups.

If |G| < cp^3, then (I haven't actually checked this but I believe it to be true) G cannot contain any nonabelian finite simple groups in its Jordan-Hölder decomposition.

Now we use 'transport de structure' (Serre - Linear Represenations of Finite Groups Prop 24). If G has a normal subgroup H of index coprime to p, then the restriction of this irrep to H must be isotypic, hence a sum of one dimensional irreps. This representation then factors through the commutator subgroup [H,H] and since the dimension of an irrep divides the index of a normal abelian subgroup, this implies p divides the index of G in H, a contradiction.

The fact that a cyclic group of order p must appear in the Jordan-Hölder decomposition now implies that a Sylow subgroup has a normal complement so we may rejoin the above argument.

Of course we still need to know how large the size of the smallest prime in an AP is.

-

Given a finite group, the sums of squares of dimensions of irreducible representations add up to the order of the group, so the dimension of an irreducible representation is at most the square root of the order of the group. If I understand your question correctly, this (together with your Frobenius group lower bound) implies e is 2. (Edit: My argument comes from a misreading of the question, but Noah's comment is sufficiently informative that I don't want to delete the post.)

Noah Snyder has a paper on near-extremal phenomena in this setting.

-
I think you misunderstood the question. Qiaochu is asking for a bound that works for every possible dimension of irrep. The Frobenius group case only covers n=p^k-1. For the exponent to move away from e=2 all you'd need is infinitely many bad dimensions. Whereas my paper studies what the "really really good" dimensions are. – Noah Snyder Oct 15 2009 at 0:51