Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

March 4, 2025

How Good are Permutation Represesentations?

Posted by John Baez

Any action of a finite group GG on a finite set XX gives a linear representation of GG on the vector space with basis XX. This is called a ‘permutation representation’. And this raises a natural question: how many representations of finite groups are permutation representations?

Most representations are not permutation representations, since every permutation representation has a vector fixed by all elements of GG, namely the vector that’s the sum of all elements of XX. In other words, every permutation representation has a 1-dimensional trivial rep sitting inside it.

But what if we could ‘subtract off’ this trivial representation?

There are different levels of subtlety with which we can do this. For example, we can decategorify, and let:

  • the Burnside ring of GG be the ring A(G)A(G) of formal differences of isomorphism classes of actions of GG on finite sets;

  • the representation ring of GG be the ring R(G)R(G) of formal differences of isomorphism classes of finite-dimensional representations of GG.

In either of these rings, we can subtract.

There’s an obvious map β:A(G)R(G)\beta : A(G) \to R(G) , since any action of GG on a finite set gives a permutation representation of GG on the vector space with basis XX.

So I asked on MathOverflow: is β\beta typically surjective, or typically not surjective?

In fact everything depends on what field kk we’re using for our vector spaces! For starters let’s take k=k = \mathbb{Q}.

Here’s a list of finite groups where the map β:A(G)R(G)\beta : A(G) \to R(G) from the Burnside ring to the representation ring is known to be surjective, taken from the nLab article Permutation representations:

  1. cyclic groups,

  2. symmetric groups,

  3. pp-groups (that is, groups whose order is a power of the prime pp),

  4. binary dihedral groups 2D 2n2 D_{2n} for (at least) 2n122 n \leq 12,

  5. the binary tetrahedral group, binary octahedral group, and binary icosahedral group,

  6. the general linear group GL(2,𝔽 3)GL(2,\mathbb{F}_3).

Now, these may seem like rather special classes of groups, but devoted readers of this blog know that most finite groups have order that’s a power of 2. I don’t think this has been proved yet, but it’s obviously true empirically, and we also have a good idea as to why:

So, the map β\beta from the Burnside ring to the representation ring is surjective for most finite groups!

David Benson has listed the orders for which there are groups where β\beta is not surjective, and how many such groups there are of these orders:

24: 2,

40: 2,

48: 7,

56: 1,

60: 2,

72: 8,

80: 8,

84: 1,

88: 2,

96: 45,

104: 2,

112: 5,

120: 13,

132: 1,

136: 3,

140: 2,

144: 39,

152: 2,

156: 1,

160: 12,

168: 12,

171: 1,

176: 7,

180: 6,

184: 1,

192: 423,

200: 8,

204: 2,

208: 8,

216: 35,

220: 1,

224: 28,

228: 1,

232: 2,

240: 90,

248: 1,

252: 4,

260: 2,

264: 10,

272: 12,

276: 1,

280: 12,

288: 256,

296: 2,

300: 8,

304: 7,

308: 1,

312: 16,

320: 532,

328: 3,

333: 1,

336: 76,

340: 2,

342: 2,

344: 2,

348: 2,

352: 41,

360: 51,

364: 2,

368: 5,

372: 1,

376: 1,

380: 2.

He adds:

This seems to represent quite a small proportion of all finite groups, counted by order, even ignoring the pp-groups.

All this is if we work over \mathbb{Q}. If we work over \mathbb{C} the situation flip-flops, and I believe β\beta is usually not surjective. It already fails to be surjective for cyclic groups bigger than /2\mathbb{Z}/2!

Why? Because /n\mathbb{Z}/n has a 1-dimensional representation where the generator acts as multiplication by a primitive nnth root of unity, and since this is not a rational number when n>2n > 2, this representation is not definable over \mathbb{Q}. Thus, one can show, there’s no way to get this representation as a formal difference of permutation representations, since those are always definable over \mathbb{Q}.

And this phenomenon of needing roots of unity to define representations is not special to cyclic groups: it happens for most finite groups as hinted at by Artin’s theorem on induced characters.

An example

Now, you’ll notice that I didn’t yet give an example of a finite group where the map β\beta from the Burnside ring to the representation ring fails to be surjective when we work over \mathbb{Q}.

In Serre’s book Linear Representations of Finite Groups, he asks us in Exercise 13.4 on page 105 to prove that /3×Q 8\mathbb{Z}/3 \times Q_8 is such a group. Here Q 8Q_8 is the quaternion group, an 8-element subgroup of the invertible quaternions:

Q 8={±1,±i,±j,±k} Q_8 = \{ \pm 1, \pm i , \pm j, \pm k \}

I couldn’t resist trying to understand why this is the counterexample Serre gave. First of all, /3×Q 8\mathbb{Z}/3 \times Q_8 looks like a pretty weird group — why does it work, and why did Serre choose this one? Secondly, it has 24 elements, and I love the number 24. Thirdly, I love the quaternions.

Benson’s calculations show that the two smallest groups where β\beta is non-surjective have 24 elements. Drew Heard checked that these groups are /3×Q 8\mathbb{Z}/3 \times Q_8 and the nontrivial semidirect product /3/8\mathbb{Z}/3 \rtimes \mathbb{Z}/8. But it’s still very interesting to do Serre’s exercise 13.4 and see why /3×Q 8\mathbb{Z}/3 \times Q_8 is such a group.

To do this exercise, Serre asks us to use exercise 13.3. Here is my reformulation and solution of that problem. I believe any field kk characteristic zero would work for this theorem:

Theorem. Suppose GG is a finite group with a linear representation ρ\rho such that:

  1. ρ\rho is irreducible and faithful

  2. every subgroup of GG is normal

  3. ρ\rho appears with multiplicity n2n \ge 2 in the regular representation of GG.

Then the map from the Burnside ring of GG to the representation ring R(G)R(G) of GG is not surjective.

Proof. It suffices to prove that the multiplicity of ρ\rho in any permutation representation of GG is a multiple of nn, so that the class [ρ]R(G)[\rho] \in R(G) cannot be in the image of R(G)R(G).

Since every finite GG-set is a coproduct of transitive actions of GG, which are isomorphic to actions on G/HG/H for subgroups HH of GG, every permutation representation of GG is a direct sum of those on spaces of the form k[G/H]k[G/H]. (This is my notation for the vector space with basis G/HG/H.) Thus, it suffices to show that the multiplicity of ρ\rho in the representation on k[G/H]k[G/H] is nn if HH is the trivial group, and 00 otherwise.

The former holds by assumption 3. For the latter, suppose HH is a nontrivial subgroup of GG. Because HH is normal by assumption 2, every element hHh \in H acts trivially on k[G/H]k[G/H]: we can see this by letting hh act on an arbitrary basis element gH=HgG/Hg H = H g \in G/H:

hHg=Hg. h H g = H g .

Since HH is nontrivial, it contains elements h1h \ne 1 that act trivially on k[G/H]k[G/H]. But no h1h \ne 1 can act trivially on ρ\rho because ρ\rho is faithful, by assumption 1. Thus ρ\rho cannot be a subrepresentation of k[G/H]k[G/H]. That is, ρ\rho appears with multiplicity 00 in k[G/H]k[G/H].   ▮

Serre’s exercise 13.4 is to show the group G=/3×Q 8G = \mathbb{Z}/3 \times Q_8 obeys the conditions of this theorem. As a hint, Serre suggests to embed /3\mathbb{Z}/3 and Q 8Q_8 in the multiplicative group of the algebra \mathbb{H}_{\mathbb{Q}} (the quaternions defined over \mathbb{Q}). By letting /3\mathbb{Z}/3 act by left multiplication and Q 8Q_8 act by right multiplication, one obtains a 4-dimensional irreducible representation ρ\rho of GG which appears with multiplicity n=2n = 2 in the regular representation. Furthermore ρ\rho is faithful and irreducible. Finally, every subgroup of GG is normal, because that’s true of /3\mathbb{Z}/3 and Q 8Q_8 — and since the orders of these groups are relatively prime, every subgroup of G=/3×Q 8G = \mathbb{Z}/3 \times Q_8 is a product of a subgroup of /3\mathbb{Z}/3 and a subgroup of Q 8Q_8.

More work on the question

Alex Bartel wrote:

To add to what others have said: you may be interested in this paper “Rational representations and permutation representations of finite groups” of mine with Tim Dokchitser, which, among other things, contains an overview of what is (or was in 2016) known about the question, describes the algorithm that is used in the magma programme (implemented by Tim Dokchitser) that Drew Heard mentions in his answer, gives a closed form formula for the cokernel in quasi-elementary groups, and exhibits a family of finite simple groups with unbounded cokernel, in fact even unbounded exponent of cokernel (to our knowledge, in all finite simple groups for which one had known this cokernel up to that point, the cokernel was trivial).

The particular interest in quasi-elementary groups stems from the fact that one can reduce the study of this cokernel in arbitrary finite groups to that of its quasi-elementary subgroups and the induction-restriction maps between them. Observations of this nature have been made repeatedly over the years. In our paper we make this reduction very explicit.

Edit. In response to a question in a comment thread, and as an example of an interesting quasi-elementary group: the other group of order 2424 with non-trivial cokernel is C 3C 8C_3\rtimes C_8 with the unique non-trivial action. The cokernel of β\beta here comes about in the following way: there is an index 22 subgroup C 3×C 4C 12C_3\times C_4\cong C_{12}. Take a faithful irreducible character of that, and induce up to the whole group. The resulting 22-dimensional representation of C 3C 8C_3\rtimes C_8 has field of character values (i)\mathbb{Q}(i): the cube roots of unity have “disappeared” in the course of the induction. It turns out that the sum of this degree 22 character and its Galois conjugate is realisable over \mathbb{Q}, but that it is not a virtual permutation representation. This is an illustration of Theorem 1.1 in my paper with Tim: ρ\rho is 44-dimensional, ψ^\hat\psi is the 22-dimensional irreducible rational representation of C 3C_3, the sum of the two faithful complex irreducible characters, and π^\hat{\pi} is the unique 44-dimensional irreducible rational representation of C 8C_8, the sum of all its faithful complex irreducible characters.

Posted at March 4, 2025 5:01 PM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/3592

9 Comments & 0 Trackbacks

Re: How Good are Permutation Represesentations?

Very interesting! How many remaining candidates of groups of order 24\leq 24 are there where we don’t know whether β\beta is surjective? And how feasible would it be to check these case by case?

Minor question: in the last paragraph, shouldn’t the multiplicity of ρ\rho in the regular representation be n=dim =4n=\dim\mathbb{H}_{\mathbb{Q}}=4? Or am I missing something? (Admittedly, my algebra is a bit rusty.)

Posted by: Paul Schwahn on March 4, 2025 10:28 PM | Permalink | Reply to this

Re: How Good are Permutation Represesentations?

Hi, Paul!

Paul wrote:

How many remaining candidates of groups of order 24\le 24 are there where we don’t know whether β\beta is surjective?

Since β\beta is surjective for groups of prime power order and David Benson says the first groups of order p2 np \cdot 2^n where β\beta is not surjective have order 24, the only groups we need to check are those of order 15, 18, and 21.

(Someone please check that list of numbers: it’s easy to check but I’m fallible.)

And how feasible would it be to check these case by case?

Incredibly feasible for someone who has the right software. After all, David Benson just told me that there are 532 groups of order 320 where β\beta is not surjective, and I see there’s a total of 1640 groups of order 320. So presumably the only reason he didn’t answer my question about groups of order <24\lt 24 is that he wanted to save some fun for the rest of us!

Minor question: in the last paragraph, shouldn’t the multiplicity of ρ\rho in the regular representation be n=dim n = \dim \mathbb{H}_{\mathbb{Q}}. Or am I missing something? (Admittedly, my algebra is a bit rusty.)

I was very confused about such things at first because I’m used to group representations over \mathbb{C}. This was one of the main benefits to me of thinking about this question: updating my knowledge base.

If kk has characteristic zero, its group algebra k[G]k[G] is semisimple by Maschke’s theorem. Thus by the Wedderburn–Artin theorem it is a finite product of matrix algebras M n(D)M_n(D) where DD is a division algebra over kk. There is one of these factors M n(D)M_n(D) for each irreducible representation of GG.

Now, if kk is not only of characteristic zero but also algebraically complete, which is the case you and I are used to, the only division algebras over kk are kk itself. In this case, each nn-dimensional irreducible representation of GG gives the group algebra k[G]k[G] a factor M n(k)M_n(k). This factor will be of dimension n 2n^2. So, the dimensions of all the irreducible representations of GG must have squares that sum to |G||G|.

If kk has characteristic zero but is not algebraically complete, everything I said in the last paragraph can fail!.

I think all this is correct, and thanks for giving me an excuse to say it!

Things get harder when Serre asks us to check that G=/3×Q 8G = \mathbb{Z}/3 \times Q_8 has an irreducible representation ρ\rho on \mathbb{H}_\mathbb{Q}, and that ρ\rho gives the group algebra [G]\mathbb{Q}[G] a factor isomorphic to M 2([ω])M_2(\mathbb{Q}[\omega]).

I want to be sure this is true and I understand it.

As a kind of warmup, Wikipedia shows that the group algebra of Q 8Q_8 over \mathbb{R} is

[Q 8] \mathbb{R}[Q_8] \cong \mathbb{H} \oplus \mathbb{R} \oplus \mathbb{R} \oplus \mathbb{R} \oplus \mathbb{R}

but over \mathbb{C} we get

[Q 8]M 2() \mathbb{C}[Q_8] \cong M_2(\mathbb{C}) \oplus \mathbb{C} \oplus \mathbb{C} \oplus \mathbb{C} \oplus \mathbb{C}

since the 4-dimensional real representation splits into two isomorphic 2-dimensional complex representations when you complexify it!

Posted by: John Baez on March 4, 2025 11:55 PM | Permalink | Reply to this

Re: How Good are Permutation Represesentations?

Drew Heard posted another answer (the one that Alex references) confirming that 24 is indeed the smallest order of a group that’s a counterexample over \mathbb{Q}.

Posted by: L Spice on March 5, 2025 1:56 AM | Permalink | Reply to this

Re: How Good are Permutation Represesentations?

My apologies for two comments; I was posting too quickly.

You say: “Now, these may seem like rather special classes of groups, but devoted readers of this blog know that most finite groups have order that’s a power of 2. I don’t think this has been proved yet, but it’s obviously true empirically, and we also have a good idea as to why: ….”

The lovely linked post definitely states the empirical fact, but I didn’t obviously see in the article itself, or a quick skim of the comments, an explanation for why. Did I miss it? Is it in one of the linked MO questions?

Posted by: L Spice on March 5, 2025 2:01 AM | Permalink | Reply to this

Re: How Good are Permutation Represesentations?

Apparently Sims showed that the number of groups of order p np^n grows like

p 2n 3/27+O(n 8/3) p^{{2n^3}/27+ O(n^{8/3})}

For finite groups of this sort it’s clear that you get the most of order N\le N if you take p=2p = 2.

It’s a lot more complicated when we consider finite groups of all kinds, but we can build all finite groups out of simple groups via composition series, i.e. iterated extensions described by cocycles in nonabelian cohomology. And it seems that when you do this, you get the most choices when you use lots of very small simple groups, and the smallest of all is /2\mathbb{Z}/2. This seems to be why most groups of order N\le N for large NN have orders of the form 2 k2^k. Then come groups of order 2 k32^k \cdot 3, and then probably 2 k52^k \cdot 5, but I don’t know which comes next 2 k72^k \cdot 7 or 2 k3 22^k \cdot 3^2.

Richard Borcherds briefly mentions this phenomenon here.

Posted by: John Baez on March 5, 2025 4:13 AM | Permalink | Reply to this

Re: How Good are Permutation Represesentations?

I’m curious how different the accounting would turn out for questions like these look if by phrases like “how many groups …” you implicitly meant something different from “how many distinct isomorphism classes of groups …”?

Like, say if a group has nontrivial automorphisms, and you think that each automorphism should count as a different group. Or maybe just for the inner automorphisms, or just the outer automorphisms.

And what if the “how many” part means something other than ordinary cardinality? Maybe each group GG should be counted according to its groupoid cardinality. Would that change things much? (Glancing at that paper about groups of order at most 2000, it looks like the domination by groups of order 1024 would still hold, just slightly less dramatically.)

Posted by: Mark Meckes on March 5, 2025 4:31 PM | Permalink | Reply to this

Re: How Good are Permutation Represesentations?

I believe the prevalence of groups whose order is a power of 2 is so crushing that even if you counted them using groupoid cardinality rather than ordinary cardinality, they would account for the vast majority of all finite groups — or more precisely, a fraction that tends to 1 as we consider groups of order N\le N and let NN \to \infty.

For what it’s worth, this is roughly what Richard Borcherds was saying in that remark on MathOverflow that I linked to a while back:

Higman and Sims showed that the number of groups of order pm is somewhere around p2m3/27, up to some smallish correction that I cant remember offhand. This is vastly bigger than the size of the typical automorphism group of such groups, so dividing by the automorphism group does not make much significant difference to this number.

The number of groups of order at most N is dominated by those of order a power of 2. (The next most common are those of order 3 times a power of 2). The number of groups of given order N has been worked out exactly for N up to about 2000.

I wish people would prove more theorems about the statistics of finite groups. It’s a bit shocking that in this day and age, nobody has yet proved that most groups have orders that are powers of 2. Then someone should prove a nice bound on the fraction of groups that don’t, and how many have orders of the form 32 n3 \cdot 2^n, etc.

For groups whose orders are prime powers, a lot of important work was done by Marshall Hall Jr. Apparently condemned by his name to forever seek a father figure, he teamed up with a guy named Senior and published that beloved page-turner The Groups of Order 2 n2^n (n<6n \lt 6), which you can buy for just $348 from a company owned by a billionaire. If I were infinitely wealthy I would buy a copy, and if I were immortal, I would definitely spend a chunk of time studying his paper “The classification of prime-power groups” — there must be really beautiful structures lurking here.

Posted by: John Baez on March 6, 2025 10:48 PM | Permalink | Reply to this

Re: How Good are Permutation Represesentations?

I think there may some confusion over Dave Benson’s computations reported on MathOverflow. Many people (including the OP and some following comments here) seem to be interpreting it as just listing some various orders of the form 2 np2^n\cdot p and how many of the relevant groups there are for these orders.

In fact, my understanding is that he checked all orders up to 220 (originally, and now 380). So Dave Benson’s answer already implied that Serre’s example was the smallest. Perhaps he didn’t phrase it very well.

(By the way, it’s easy to check that his list doesn’t only include numbers of the form 2 np2^n\cdot p, for example 60, etc…)

I just double checked the start of the computation using a variation of what Drew Heard posted. (You can play around with this here https://magma.maths.usyd.edu.au/calc/ if you don’t have a magma license.)

Posted by: Gabriel Verret on March 5, 2025 5:51 PM | Permalink | Reply to this

Re: How Good are Permutation Represesentations?

Gabriel wrote:

Many people (including the OP and some following comments here) seem to be interpreting it as just listing some various orders of the form 2 np2^n\cdot p and how many of the relevant groups there are for these orders.

Yes, that’s how I interpreted it! It’s his fault for writing: “But quite a lot of groups of order 2 np2^n \cdot p are examples where it isn’t [surjective]. There are 45 such groups of order 96, for example. Here is a list of the first few orders for which there are such groups, and how many there are…”

But if I’d been awake I would have noticed that 60, 120, etcetera are not numbers of that form! Thanks! And thanks for re-checking some of his calculations.

Posted by: John Baez on March 5, 2025 9:16 PM | Permalink | Reply to this

Post a New Comment