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
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
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.
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?
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.