The 5/8 Theorem

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 G is abelian, its center, say Z, is all of G. But let’s assume G is not abelian. How big can |Z|/|G| be?

Since the center is a subgroup of G, we know by Lagrange’s theorem that |G|/|Z| is an integer. To make |Z|/|G| big we need this integer to be small. How small can it be?

It can’t be 1, since then |Z| = |G| and G would be abelian. Can it be 2?

No! This would force G to be abelian, leading to a contradiction! The reason is that the center is always a normal subgroup of G, so G/Z is a group of size |G/Z| = |G|/|Z|. If this is 2 then G/Z has to be \mathbb{Z}/2. But this is generated by one element, so G must be generated by its center together with one element. This one element commutes with everything in the center, obviously… but that means G is abelian: a contradiction!

For the same reason, |G|/|Z| can’t be 3. The only group with 3 elements is \mathbb{Z}/3, which is generated by one element. So the same argument leads to a contradiction: G is generated by its center and one element, which commutes with everything in the center, so G is abelian.

So let’s try |G|/|Z| = 4. There are two groups with 4 elements: \mathbb{Z}/4 and \mathbb{Z}/2 \times \mathbb{Z}/2. 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, \mathbb{Z}/2 \times \mathbb{Z}/2 is still abelian! So you might think this: “If G/Z \cong \mathbb{Z}/2 \times \mathbb{Z}/2, the group G 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 G/Z commute with each other, this does not imply that the elements of G 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 G with G/Z \cong \mathbb{Z}/2 \times \mathbb{Z}/2. The smallest possible example would have \mathbb{Z}/2, and indeed this works!

Namely, we’ll take G to be the 8-element quaternion group

Q = \{ \pm 1, \pm i, \pm j, \pm k \}

where

i^2 = j^2 = k^2 = -1
i j = k, \quad j k = i, \quad k i = j
j i = -k, \quad k j = -i, \quad i k = -j

and multiplication by -1 works just as you’d expect, e.g.

(-1)^2 = 1

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 Q is Z = \{ \pm 1 \}, and the quotient Q/Z is the Klein four-group, since if we mod out by \pm 1 we get the group

\{1, i, j, k\}

with

i^2 = j^2 = k^2 = 1
i j = k, \quad j k = i, \quad k i = j
j i = k, \quad k j = i, \quad i k = j

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 G can be, without being abelian. Any element g \in G has a centralizer C(g), consisting of all elements that commute with g.

How big can C(g) be? If g is in the center of G, then C(g) is all of G. So let’s assume g is not in the center, and ask how big the fraction |C(g)|/|G| can be.

In other words: how large can the fraction of elements of G that commute with g be, without it being everything?

It’s easy to check that the centralizer C(g) is a subgroup of G. So, again using Lagrange’s theorem, we know |G|/|C(g)| is an integer. To make the fraction |C(g)|/|G| big, we want this integer to be small. If it’s 1, everything commutes with g. 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 Q. Each non-central element commutes with exactly half the elements. For example, i commutes only with its own powers: 1, i, -1, -i.

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 G is a nonabelian group. How can we maximize the probability for two randomly chosen elements of G to commute?

Say we randomly pick two elements g,h \in G. Then there are two cases. If g is in the center of G it commutes with h with probability 1. But if g is not in the center, we’ve just seen it commutes with h 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 Z \subset G as large as possible. We’ve seen that |Z|/|G| is at most 1/4. So let’s use that.

Then with probability 1/4, g commutes with all the elements of G, while with probability 3/4 it commutes with 1/2 the elements of G.

So, the probability that g commutes with h is

\frac{1}{4} \cdot 1 + \frac{3}{4} \cdot \frac{1}{2} = \frac{2}{8} + \frac{3}{8} = \frac{5}{8}

Even better, all these bounds are attained by the quaternion group Q. 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 G:

• The probability that two elements commute is 5/8.

• The inner automorphism group of G has 4 elements.

• The inner automorphism group of G is \mathbb{Z}/2 \times \mathbb{Z}/2.

Examining the argument I gave, it seems the probability 5/8 can only be attained if

• |Z|/|G| = 1/4

• |C(g)|/|G| = 1/2 for every g \notin Z.

So apparently any finite group with inner automorphism group \mathbb{Z}/2 \times \mathbb{Z}/2 must have these other two properties as well!

There are lots of groups with inner automorphism group \mathbb{Z}/2 \times \mathbb{Z}/2. 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 2^n 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 2^n for n \le 6. They developed some powerful general ideas in the process, like isoclinism. I don’t want to explain it here, but which involves the quotient G/Z 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 2^n 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 G generate a solvable group is greater than 11/30 then G itself is solvable.

• If the probability that two randomly chosen elements of G generate a nilpotent group is greater than 1/2 then G is nilpotent.

• If the probability that two randomly chosen elements of G generate a group of odd order is greater than 11/30 then G 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 p \in (0,1] can we find a finite group where the probability that two randomly chosen elements commute is p? If we call this set S we’ve seen

S \subseteq (0,5/8] \cup \{1\}

But does S 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 G with property P exceeds some value p, then G 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 G is finite simple and nonabelian, the probability that two elements commute is at most 1/12, a bound attained by \mathrm{A}_5.

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.

This entry was posted on Sunday, September 16th, 2018 at 4:27 am and is filed under mathematics. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

26 Responses to The 5/8 Theorem

  1. Ishi Crew says:
    16 September, 2018 at 5:17 am

    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.

    Reply
    • Ishi Crew says:
      17 September, 2018 at 8:06 am

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

      Reply
  2. Tim Porter says:
    16 September, 2018 at 6:14 am

    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.

    Reply
  3. Yemon Choi says:
    16 September, 2018 at 11:31 am

    Some of your questions might be answered (or at least partially addressed) in this paper of Sean Eberhard: https://arxiv.org/abs/1411.0848

    Reply
  4. allenknutson says:
    16 September, 2018 at 12:18 pm

    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 p^n. If G is cyclic, then for every smaller p^k, there is a unique subgroup of this order. Conversely, if there is some k for which there is a unique subgroup, then G is either cyclic or k=1,p=2 and G is the generalized quaternion group \langle \exp(2\pi i/2^{n-1}), j \rangle.

    Reply
    • John Baez says:
      17 September, 2018 at 1:59 am

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

      Reply
  5. Theo Johnson-Freyd says:
    16 September, 2018 at 6:09 pm

    Surely you don’t mean A_4 in the example of a finite simple group, since A_4 has a Klein-4 normal subgroup with Z/3 quotient. Probably you mean A_5?

    Reply
  6. ken abbott says:
    16 September, 2018 at 8:56 pm

    Interesting. I always loved that the order of a subgroup divides the order of the group. This us there with that result.

    Reply
  7. John Baez says:
    17 September, 2018 at 1:52 am

    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 p(G) that two elements of a finite group G commute is \le 5/8.

    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 p(G) > 1/2 then

    p(G) = \frac{1}{2} + \frac{1}{2^{2n+1}}

    • The group S_3 shows we can have p(G) = 1/2.

    • We cannot have

    \frac{7}{16} < p(G) < \frac{1}{2}

    • The group A_4 shows we can have p(G) = 1/3.

    Unfortunately the paper gives neither proof nor reference for the nontrivial facts here!

    Reply
  8. Kram Einsnulldreizwei says:
    17 September, 2018 at 11:15 am

    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”

    Reply
    • John Baez says:
      18 September, 2018 at 5:43 pm

      In algebras we measure commutativity using xy - yx. In groups we measure it using xyx^{-1}y^{-1}. Both of these are called the ‘commutator’.

      In algebras we measure associativity using the associator (xy)z - x(yz). Is there a good analog for quasigroups? One could try ((xy)z)(x(yz))^{-1}.

      Reply
  9. Alon Amit says:
    17 September, 2018 at 5:08 pm

    If you fix a finite group G, you may wonder about the probability of getting 1_G when uniform random elements of G are plugged into any word, not just the particular commutator word X^{-1}Y^{-1}XY. A beautiful result of Abert, Segal and Nikolov shows that this probability is bounded away from 0 precisely when G is solvable.

    Thus, in a certain sense, solvable groups are just the groups in which it’s easy to solve equations of the form w(x_1,\ldots,x_m)=1!

    (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

    Reply
  10. L Spice says:
    25 September, 2018 at 6:21 pm

    A silly comment: you mean \lvert G\rvert/\lvert Z\rvert everywhere you write \lvert Z\rvert/\lvert G\rvert.

    Reply
    • John Baez says:
      25 September, 2018 at 9:58 pm

      Not everywhere. For example, this is right:

      Since the center is a subgroup of G, we know by Lagrange’s theorem that |G|/|Z| is an integer. To make |Z|/|G| big we need this integer to be small. How small can it be?

      But I indeed did get it backwards in a number of places, which I’ve endeavored to fix. Thanks!

      Reply
  11. Ben Blum-Smith says:
    1 October, 2018 at 1:01 pm

    Minor correction:

    Yes! One example is our friend the quaternion group Q. Each non-identity element commutes with exactly half the elements. For example, i commutes only with its own powers: 1, i, -1, -i.

    Each non-central element.

    Reply
  12. Ben Blum-Smith says:
    1 October, 2018 at 1:16 pm

    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 \mathbb{Z}/2\times \mathbb{Z}/2, but it’s actually almost immediate from what you’ve done here!

    1) The inner automorphism group is, in general, G/Z, since Z is exactly the kernel of the action of G on itself by inner automorphisms. Thus inner automorphism group of order 4 \Leftrightarrow |Z|/|G| = 1/4.

    2) By the argument you gave, G/Z is never cyclic, so having order 4 is the same thing as being \mathbb{Z}/2\times\mathbb{Z}/2.

    3) In this situation, every g\in G\setminus Z is noncentral, so its centralizer is not everything, but it properly contains Z, since it contains both Z and g\notin Z. So the centralizer is a proper subgroup properly containing Z. It must have index 2 since Z has index 4. Thus every element commutes with exactly half the other elements.

    Reply
  13. sniffnoy says:
    22 February, 2019 at 4:38 am

    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…

    Reply
  14. sniffnoy says:
    22 February, 2019 at 4:53 am

    Hm, I tried to post a comment on this here but it seems to have been caught in spam or something for some reason?

    Reply

You can use Markdown or HTML in your comments. You can also use LaTeX, like this: $latex E = m c^2 $. The word 'latex' comes right after the first dollar sign, with a space after it.

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. ( Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. ( Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. ( Log Out /  Change )

Cancel

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.