This is a well-known, easy group theory result that I just learned. I would like to explain it more slowly and gently, and I hope memorably, than I’ve seen it done.
It’s called the 5/8 theorem. Randomly choose two elements of a finite group. What’s the probability that they commute? If it exceeds 62.5%, the group must be abelian!
This was probably known for a long time, but the first known proof appears in a paper by Erdös and Turan.
It’s fun to lead up to this proof by looking for groups that are “as commutative as possible without being abelian”. This phrase could mean different things. One interpretation is that we’re trying to maximize the probability that two randomly chosen elements commute. But there are two simpler interpretations, which will actually help us prove the 5/8 theorem.
How big can the center be?
How big can the center of a finite group be, compared to the whole group? If a group is abelian, its center, say
is all of
But let’s assume
is not abelian. How big can
be?
Since the center is a subgroup of we know by Lagrange’s theorem that
is an integer. To make
big we need this integer to be small. How small can it be?
It can’t be 1, since then and
would be abelian. Can it be 2?
No! This would force to be abelian, leading to a contradiction! The reason is that the center is always a normal subgroup of
, so
is a group of size
. If this is 2 then
has to be
But this is generated by one element, so
must be generated by its center together with one element. This one element commutes with everything in the center, obviously… but that means
is abelian: a contradiction!
For the same reason, can’t be 3. The only group with 3 elements is
which is generated by one element. So the same argument leads to a contradiction:
is generated by its center and one element, which commutes with everything in the center, so
is abelian.
So let’s try There are two groups with 4 elements:
and
The second, called the Klein four-group, is not generated by one element. It’s generated by two elements! So it offers some hope.
If you haven’t studied much group theory, you could be pessimistic. After all, is still abelian! So you might think this: “If
the group
is generated by its center and two elements which commute with each other, so it’s abelian.”
But that’s false: even if two elements of commute with each other, this does not imply that the elements of
mapping to these elements commute.
This is a fun subject to study, but best way for us to see this right now is to actually find a nonabelian group with
. The smallest possible example would have
and indeed this works!
Namely, we’ll take to be the 8-element quaternion group
where
and multiplication by works just as you’d expect, e.g.
You can think of these 8 guys as the unit quaternions lying on the 4 coordinate axes. They’re the vertices of a 4-dimensional analogue of the octahedron. Here’s a picture by David A. Richter, where the 8 vertices are projected down from 4 dimensions to the vertices of a cube:
The center of is
and the quotient
is the Klein four-group, since if we mod out by
we get the group
with
So, we’ve found a nonabelian finite group with 1/4 of its elements lying in the center, and this is the maximum possible fraction!
How big can the centralizer be?
Here’s another way to ask how commutative a finite group can be, without being abelian. Any element
has a centralizer
consisting of all elements that commute with
How big can be? If
is in the center of
then
is all of
So let’s assume
is not in the center, and ask how big the fraction
can be.
In other words: how large can the fraction of elements of that commute with
be, without it being everything?
It’s easy to check that the centralizer is a subgroup of
So, again using Lagrange’s theorem, we know
is an integer. To make the fraction
big, we want this integer to be small. If it’s 1, everything commutes with
So the first real option is 2.
Can we find an element of a finite group that commutes with exactly 1/2 the elements of that group?
Yes! One example is our friend the quaternion group Each non-central element commutes with exactly half the elements. For example,
commutes only with its own powers:
So we’ve found a finite group with a non-central element that commutes with 1/2 the elements in the group, and this is maximum possible fraction!
What’s the maximum probability for two elements to commute?
Now let’s tackle the original question. Suppose is a nonabelian group. How can we maximize the probability for two randomly chosen elements of
to commute?
Say we randomly pick two elements Then there are two cases. If
is in the center of
it commutes with
with probability 1. But if
is not in the center, we’ve just seen it commutes with
with probability at most 1/2.
So, to get an upper bound on the probability that our pair of elements commutes, we should make the center as large as possible. We’ve seen that
is at most 1/4. So let’s use that.
Then with probability 1/4, commutes with all the elements of
while with probability 3/4 it commutes with 1/2 the elements of
So, the probability that commutes with
is
Even better, all these bounds are attained by the quaternion group 1/4 of its elements are in the center, while every element not in the center commutes with 1/2 of the elements! So, the probability that two elements in this group commute is 5/8.
So we’ve proved the 5/8 theorem and shown we can’t improve this constant.
Further thoughts
I find it very pleasant that the quaternion group is “as commutative as possible without being abelian” in three different ways. But I shouldn’t overstate its importance!
I don’t know the proof, but the website groupprops says the following are equivalent for a finite group :
• The probability that two elements commute is 5/8.
• The inner automorphism group of has 4 elements.
• The inner automorphism group of is
Examining the argument I gave, it seems the probability 5/8 can only be attained if
•
• for every
So apparently any finite group with inner automorphism group must have these other two properties as well!
There are lots of groups with inner automorphism group Besides the quaternion group, there’s one other 8-element group with this property: the group of rotations and reflections of the square, also known as the dihedral group of order 8. And there are six 16-element groups with this property: they’re called the groups of Hall–Senior class two. And I expect that as we go to higher powers of two, there will be vast numbers of groups with this property.
You see, the number of nonisomorphic groups of order grows alarmingly fast. There’s 1 group of order 2, 2 of order 4, 5 of order 8, 14 of order 16, 51 of order 32, 267 of order 64… but 49,487,365,422 of order 1024. Indeed, it seems ‘almost all’ finite groups have order a power of two, in a certain asymptotic sense. For example, 99% of the roughly 50 billion groups of order ≤ 2000 have order 1024.
Thus, if people trying to classify groups are like taxonomists, groups of order a power of 2 are like insects.
In 1964, the amusingly named pair of authors Marshall Hall Jr. and James K. Senior classified all groups of order for
They developed some powerful general ideas in the process, like isoclinism. I don’t want to explain it here, but which involves the quotient
that I’ve been talking about. So, though I don’t understand much about this, I’m not completely surprised to read that any group of order
has commuting probability 5/8 iff it has ‘Hall–Senior class two’.
There’s much more to say. For example, we can define the probability that two elements commute not just for finite groups but also compact topological groups, since these come with a god-given probability measure, called Haar measure. And here again, if the group is nonabelian, the maximum possible probability for two elements to commute is 5/8!
There are also many other generalizations. For example Guralnick and Wilson proved:
• If the probability that two randomly chosen elements of generate a solvable group is greater than 11/30 then
itself is solvable.
• If the probability that two randomly chosen elements of generate a nilpotent group is greater than 1/2 then
is nilpotent.
• If the probability that two randomly chosen elements of generate a group of odd order is greater than 11/30 then
itself has odd order.
The constants are optimal in each case.
I’ll just finish with two questions I don’t know the answer to:
• For exactly what set of numbers can we find a finite group where the probability that two randomly chosen elements commute is
If we call this set
we’ve seen
But does contain every rational number in the interval (0,5/8], or just some? Just some, in fact—but which ones? It should be possible to make some progress on this by examining my proof of the 5/8 theorem, but I haven’t tried at all. I leave it to you!
• For what properties P of a finite group is there a theorem of this form: “if the probability of two randomly chosen elements generating a subgroup of with property P exceeds some value
then
must itself have property P”? Is there some logical form a property can have, that will guarantee the existence of a result like this?
References
Here is a nice discussion, where I learned some of the facts I mentioned, including the proof I gave:
• MathOverflow, 5/8 bound in group theory.
Here is an elementary reference, free online if you jump through some hoops, which includes the proof for compact topological groups, and other bits of wisdom:
• W. H. Gustafson, What is the probability that two group elements commute?, American Mathematical Monthly 80 (1973), 1031–1034.
For example, if is finite simple and nonabelian, the probability that two elements commute is at most 1/12, a bound attained by
Here’s another elementary article:
• Desmond MacHale, How commutative can a non-commutative group be?, The Mathematical Gazette 58 (1974), 199–202.
If you get completely stuck on Puzzle 1, you can look here for some hints on what values the probability of two elements to commute can take… but not a complete solution!
The 5/8 theorem seems to have first appeared here:
• P. Erdös and P. Turán, On some problems of a statistical group-theory, IV, Acta Math. Acad. Sci. Hung. 19 (1968) 413–435.
The ratio 5/8 came up in my world recently in another problem dealing with ‘randomness’
(i am so far removed from the world of ‘group theory; that while i sort of remember what a ‘centralizer’ is , i’d have to go back to the definitions. Much of what i learned of group theory was from a review article by G S Mackey in Bull AMS 1980 ‘harmonic analyses as the exploitation of symmetry’ (free online) and much older stuff by Hermann Weyl ; i read these because i was trying to understand the quantum mechanics courses i was taking—those papers and books had a quite different view than what we learned in elementary quantum theory (where ‘groups’ were never mentioned–we just talked about hermite polynomials, spherical harmonics and such—Mackey explained these come out of group theory). )
This may not interest you but 5/8 comes out as one solution to the ‘wine / water paradox’ attributed to J M Keynes, Von Mises, van Frassen and ET Jaynes, and discussed by philosphers like J D Norton. . Its related to Bertrand paradox.
If you have a mixture of wine and water which you know has a ratio between 3 parts wine to 1 part water, or the reverse, what is the probability its at least 2 parts wine to 1 part water? The most common answer given is 5/8.
Some of the prominent authors also give answers like 15/16, 5/6, and on.
Thats why (like Bertrand paradox) its viewed as a paradox. They say the issue is use of the ‘principal of indifference’ (what i think is the same as the assumption of ‘equal a priori probability’ in statistical mechanics). My view is that ‘paradox’ is due to fact that people didnt define their terms well. 5/8 comes out due to an arithmetical mistake, which is repeated by all these very eminent people.
I retract that view thats its due to an arithmetical mistake–it may just be a matter of opinion(like differences between religions or intrepretations of quantum theory).
John. There is a MO question which is useful here:
• Measures of non-abelian-ness.
Des Mac Hale and his students in Cork had some fun with these problems. Des had a nice chatty article in Math Gazette (referenced in the MO answers) and one example of the sort of thing that can be said is in
• Stephen M. Buckley and Desmond MacHale, Groups with Pr(G) = 1/3.
and in
• R. Hefernan, D. MacHale and Á Ní Shé, Restrictions on commutativity ratios in finite groups.
Thanks! One interesting fact here is that the probability that two elements commute is an isoclinism invariant of finite groups.
Some of your questions might be answered (or at least partially addressed) in this paper of Sean Eberhard: https://arxiv.org/abs/1411.0848
Thanks! That paper has some fascinating results, some of which I’ll summarize below.
A couple of other ways in which quaternion groups are nigh-abelian:
If G is abelian, all its subgroups are normal. Conversely, if all of G’s subgroups are normal, then G is a product of an abelian group and a power of the quaternion 8-group.
Let G have order
. If G is cyclic, then for every smaller
, there is a unique subgroup of this order. Conversely, if there is some
for which there is a unique subgroup, then G is either cyclic or
and G is the generalized quaternion group
.
I like that first fact a lot! It reminds me of the classification of semisimple Lie algebras, where everything is the direct sum of some simple Lie algebras chosen from infinite series and some exceptional ones. The quaternion group is serving as an ‘exceptional finite cyclic group’.
Surely you don’t mean
in the example of a finite simple group, since
has a Klein-4 normal subgroup with
quotient. Probably you mean
?
Yes, I meant that
realizes the upper bound of 1/12 for the probability that two elements of a finite simple group commute.
This paper:
• W. H. Gustafson, What is the probability that two group elements commute?, American Mathematical Monthly 80 (1973), 1031–1034.
has a little list of such gems, near the end.
Here’s another: any group reaching the 5/8 bound is nilpotent.
Interesting. I always loved that the order of a subgroup divides the order of the group. This us there with that result.
Since nobody is tackling Puzzle 1, even though it’s probably easy to make incremental progress, let me start listing all the results I can find in papers. We started with this:
• The probability
that two elements of a finite group
commute is 
This paper:
• Desmond MacHale, How commutative can a non-commutative group be?, The Mathematical Gazette 58 (1974), 199–202.
has a couple more results:
• If
then
• The group
shows we can have 
• We cannot have
• The group
shows we can have 
Unfortunately the paper gives neither proof nor reference for the nontrivial facts here!
This paper:
• Sean Eberhard, Commuting probabilities of finite groups.
uses Egyptian fractions to prove two conjectures of Keith Joseph on the set
consisting of all numbers that are probabilities that two elements of some finite group commute:
• All the limit points of
are rational.
•
is well-ordered by the usual notion of 
• The order type of
is either
or 
Is there a similar notion in which some finite subgroup of Octonions might be the most Group-like Quasi-group?
Or how about somehow being simultaneously the “most abelian and group-like non-abelian Quasigroup”
In algebras we measure commutativity using
In groups we measure it using
Both of these are called the ‘commutator’.
In algebras we measure associativity using the associator
Is there a good analog for quasigroups? One could try 
If you fix a finite group
, you may wonder about the probability of getting
when uniform random elements of
are plugged into any word, not just the particular commutator word
. A beautiful result of Abert, Segal and Nikolov shows that this probability is bounded away from 0 precisely when
is solvable.
Thus, in a certain sense, solvable groups are just the groups in which it’s easy to solve equations of the form
(Full disclosure: I happened to have suggested this as a conjecture, which Abert and then Nikolov-Segal proceeded to solve.)
The Nikolov-Segal paper is here
A silly comment: you mean
everywhere you write
.
Not everywhere. For example, this is right:
But I indeed did get it backwards in a number of places, which I’ve endeavored to fix. Thanks!
Minor correction:
Each non-central element.
Right. I’ll fix that.
You wrote that you don’t know the proof of the claim from Groupprops that having a commuting probability of 5/8 is equivalent to having inner automorphism group
, but it’s actually almost immediate from what you’ve done here!
1) The inner automorphism group is, in general,
, since
is exactly the kernel of the action of
on itself by inner automorphisms. Thus inner automorphism group of order 4
.
2) By the argument you gave,
is never cyclic, so having order 4 is the same thing as being
.
3) In this situation, every
is noncentral, so its centralizer is not everything, but it properly contains
, since it contains both
and
. So the centralizer is a proper subgroup properly containing
. It must have index 2 since
has index 4. Thus every element commutes with exactly half the other elements.
Lol, the last sentence should read “every *noncentral element commutes with exactly half…”
So, here’s a question I’ve been wondering about along those lines. You linked that paper of Sean Eberhard above, that proves that the set of commuting probabilities is reverse well-ordered. I’ve been wondering if it’s possible to generalize this. Like, say we pick an arbitrary word (in the free group F_n), and consider (for each finite group G) the probability that a random n-tuple satisfies this word. So this theorem of Eberhard is the case when our word is aba^(-1)b^(-1). For any word we choose, will the resulting set of probabilities be be reverse well-ordered too?
(This problem was basically inspired by recalling this paper around the same time I first encountered Eberhard’s paper above…)
The obvious place to start is words in one letter, so you’re just counting elements of order dividing a fixed constant. But I have no idea if that goes anywhere. Like, it’s known that any finite group with more than 3/4 of its elements being involutions must have all elements involutions, but who knows if that’s the start of a well-ordering or not? And that’s just order 2! There’s some obvious trivial cases we can consider (the word “a”, for instance, or the identity word; or “ab”, or the analogue in any number of letters), and these aren’t counterexamples but they don’t tell us much of anything.
I’ve also wondered what might happen if you allow compact groups instead of just finite groups. Does that just add in 0, or is anything else gained?
Anyway, this is basically pure speculation on my part — I don’t actually intend to work on this problem. But it’s been bugging me all the same…
Hm, I tried to post a comment on this here but it seems to have been caught in spam or something for some reason?
It went to spam for some reason. Sorry. I rescued it!
Thank you!
I don’t think Erdos and Turan noticed the 5/8 upper bound (in print, anyway). They appear not to be interested. They certainly noticed the equality with
, where
is the number of conjugacy classes, and they looked at minimization rather than maximization.
Interesting. The 5/8 theorem is so easy I feel Erdos and Turan “could have” noticed it if they bothered. But I guess “could have” doesn’t mean much in math.
[…] as an alternative of “generate an Abelian group”, can breathe create in this weblog submit by John Baez, who attributes it to the essay “On some Problems of a Statistical Group-Theory, IV” by […]
[…] of G. It seems quit well known that the probability that they commute is at most Pr(G)≤58. Here is a nice reference if you like to know more about this cute result. Equality holds if and only if […]
[…] here for a proof, or here for a generalization to compact topological […]