The 5/8 Theorem

What is the probability that two group elements commute ? The $5/8$ Theorem gives us an upper bound, and seems to have first appeared in a paper by Erdös and Turán [1]. It can be stated as follows:

Theorem. Let $G$ be a finite non-abelian group and $\mathbb{P}(G)$ denote the probability that two randomly selected (with replacement) elements in $G$ commute. Then $$\mathbb{P}(G)\leq \frac{5}{8}.$$

Equivalently, the inner automorphism group of $G$ is $\mathrm{Inn}(G) = \mathbb{Z}_2\times\mathbb{Z}_2$, or $\left|\mathrm{Inn}(G)\right| = 4$.

Discussion

Suppose that we have a group $G$, and two randomly picked elements $g, h \in G$. There are two cases:

1. If $g$ is in the center of $G$ it commutes with everything, so the probability that $g$ commutes with $h$ is obviously 1.
2. If $g$ is not in the center of $G$, we must compute the maximum probability that it commutes with $h$.

Solution

Let $G$ be a finite group. If $G$ is non-abelian, its center $Z(G)$ is not the entire group, that is, $G$ has some element $g \not \in Z(G)$. Then $C_G(g)$, centraliser of $g$, also cannot be the entire group, as that would contradict $g \not \in Z(G)$.

Noting that $C_G(g)$ is a subgroup of $G$, and $Z(G)$ a subgroup of $C_G(g)$, we can then apply Lagrange's theorem twice to get

Now let $x$, $y$ be a random elements of $G$. We can bound the probability that they commute by

Examples

This bound is achieved by the quaternion group $\mathbf{Q}_8$, the dihedral group $\mathbf{D}_8$ as well as six groups of order $16$ called the groups of Hall-Senior class two. In fact, this bound is achieved by a group iff the group has center of index $4$.

References