Five-eighths of the pairs, and no more

A square has eight symmetries: four turns, counting the one that does nothing, and four flips. Doing two of them one after the other gives a third, and the order usually matters. A quarter turn followed by a flip in the vertical axis is a flip in one diagonal; the flip followed by the quarter turn is a flip in the other diagonal. The two results differ, so the quarter turn and the vertical flip do not commute.

Some pairs do. Everything commutes with doing nothing, and the half turn commutes with everything, since turning a square through half a revolution and flipping it gives the same arrangement in either order. The question this essay asks is how many pairs commute, in the square’s group and in every other finite group, and it has an answer with a surprising ceiling. If two elements are chosen at random, independently and with every element equally likely, the chance that they commute is never more than five-eighths — unless the group commutes completely, in which case it is one. Nothing lies in between. The proof uses nothing beyond orbits and stabilisers and one short fact about the centre, and the figures below count everything they claim rather than taking it from the theorem.

Sixty-four pairs of the square’s motions #

There are sixty-four ordered pairs of elements in a group of eight, and each can be tested directly: compose them one way, compose them the other, compare the two permutations of the corners. The grid below does that for all sixty-four.

Forty squares are filled. The grid is symmetric about its diagonal, since “$a$ commutes with $b$” and “$b$ commutes with $a$” are the same statement, and the diagonal is full, since every element commutes with itself. Two rows are full: the identity and the half turn $r^2$. These two elements commute with everything, and together they form the centre of the group. Every other row has exactly four filled squares. The quarter turn commutes with the four turns and with none of the flips; each flip commutes with the identity, the half turn, itself, and the flip at right angles to it.

The fraction $40/64$ reduces to $5/8$. The figure has already found the number the essay is about, and it has found it by a plain enumeration that any group small enough to write down admits. What the enumeration does not show is why the number is five-eighths, why a row has four or eight filled squares and never five, or why no other group that fails to commute can fill more of its grid.

The row counts carry most of the explanation. The set of elements that commute with a given $g$ is its centraliser, written $C(g)$, and it is a subgroup: if $a$ and $b$ both commute with $g$ then so does $ab$. By Lagrange’s theorem its size divides eight. A row therefore has one, two, four or eight filled squares, and in the square’s group it never falls below four, because every element commutes with itself, with the identity and with the half turn, which already gives three elements of a subgroup, and a subgroup of three cannot sit inside a group of eight.

The triangle commutes exactly half the time #

The triangle has six symmetries: three turns, including the identity, and three flips, one in each axis through a corner. The same test gives a sparser grid.

Eighteen of thirty-six pairs commute, so the probability is one half. Only the identity commutes with everything: the triangle’s centre is trivial. The two turns commute with each other and with the identity, and with nothing else, which is a centraliser of three. Each flip commutes only with the identity and itself — a centraliser of two. No two different flips commute, which can be checked by hand: two flips in axes sixty degrees apart compose to a turn of one hundred and twenty degrees, and in the other order to a turn of one hundred and twenty degrees the other way.

Where the square had a centre of two, the triangle has a centre of one, and its probability is lower. That is the first sign of the mechanism. A large centre contributes whole rows; everything outside the centre contributes at most half a row. The centre is the lever, and the ceiling on the probability will turn out to be a ceiling on how large a centre can be while the group still fails to commute.

Counting a row is counting a stabiliser #

The row for $g$ in either grid counts the elements $x$ with $xg = gx$. Rewrite that as $xgx^{-1} = g$. The group acts on itself by conjugation — $x$ sends $g$ to $xgx^{-1}$ — and the elements that leave $g$ where it is are exactly the centraliser. In the language of the orbit–stabiliser theorem, the centraliser is the stabiliser of $g$, and the orbit of $g$ is its conjugacy class, the set of elements that are the same motion seen from a different position.

Orbit–stabiliser says that the size of the class times the size of the stabiliser is the size of the group. So within one class, every element has a centraliser of the same size, and the class’s bars add up to exactly $|G|$: two bars of four, or one bar of eight. That is what the figure checks, class by class. The total number of commuting pairs is then $|G|$ times the number of classes, and the probability of commuting is

$$P(G) = \frac{\#\{(a,b) : ab = ba\}}{|G|^2} = \frac{k(G)}{|G|},$$

where $k(G)$ is the number of conjugacy classes. For the square, five classes over eight elements; for the triangle, three over six.

The same identity is a special case of the orbit-counting rule that counted colourings of a square up to symmetry. There, the number of orbits was the average number of colourings each motion fixes. Here the things being moved are the group’s own elements, a motion $x$ fixes exactly the elements it commutes with, and the average number fixed is the average row of the grid — so the number of orbits, which is the number of classes, is the total of the grid divided by $|G|$. The grid, the class count and the probability are three readings of one table.

The formula makes the probability easy to compute for groups far too large to draw, provided their classes are known. It also turns the question of how often a group commutes into a question of how many classes it has for its size, which is the form most of the results below take.

Why no group gets past five-eighths #

William Gustafson published the bound in the American Mathematical Monthly in 1973: if a finite group is not commutative, $P(G) \le 5/8$. The argument has two steps.

The first is a fact about the centre $Z$. If the quotient $G/Z$ — the group with central elements treated as trivial — is cyclic, then $G$ is commutative. For if some $g$ generates $G/Z$, every element has the form $g^i z$ with $z$ central, and two elements of that form commute because powers of one element commute and central elements commute with everything. So a group that fails to commute has a non-cyclic $G/Z$, and a group of order one, two or three is cyclic. The index $|G : Z|$ is at least four: the centre of a non-commutative group is at most a quarter of it.

The second step is about everything else. An element outside the centre does not commute with everything, so its centraliser is a proper subgroup, and a proper subgroup is at most half the group. Now add up the rows. At most a quarter of the rows are central and full; every other row is at most half full.

In the picture, the grid has been rearranged into columns of width $1/|G|$, each shaded to its row’s fraction, so the shaded area is the probability. The dashed outline is the largest shape the two steps allow: full height across a quarter of the width, half height across the remaining three quarters. Its area is

$$\tfrac14 \cdot 1 + \tfrac34 \cdot \tfrac12 = \tfrac58 .$$

The square’s group fills that outline exactly, because it meets both steps with equality: its centre is exactly a quarter of it, and every other centraliser is exactly half. So the bound is not merely true but best possible, and the smallest group that could possibly show it is the first non-commutative group of order eight.

The other group of order eight that does not commute is the quaternion group, the eight units $\pm 1, \pm i, \pm j, \pm k$ under Hamilton’s multiplication. Its centre is $\pm 1$, and each of $\pm i$ commutes with $\pm 1$ and $\pm i$ and with nothing else, so it too meets both steps with equality and sits at five-eighths. The two groups are different — the quaternions have one element of order two and the square’s group has five — but the commuting probability cannot tell them apart. They have the same number of classes, and that is all the probability sees.

Far below the ceiling #

Most groups are nowhere near the outline. The twenty-four permutations of four letters have a trivial centre, and their centralisers are small.

Only the identity column is full. The eight three-cycles each commute with three elements, the six four-cycles and the six transpositions each with four, and the three double transpositions each with eight; the bars sort into those heights. The shaded area is $5/24$, because the group has five conjugacy classes — one for each shape of cycle — and twenty-four elements.

The picture shows where the slack in the bound lives. The first step gave the centre a quarter of the width; this group’s centre is one column in twenty-four. The second step gave every non-central column half the height; here the tallest non-central column reaches a third. Both inequalities are loose, and the product is a probability less than a third of the ceiling. In the square’s group both were tight. The bound is the product of two constraints that a group has to meet simultaneously, and meeting both takes a very particular shape.

Twelve groups against the line #

The table below runs the enumeration for twelve groups that fail to commute, from the six symmetries of the triangle to the hundred and twenty permutations of five letters, and checks for each that the pairs counted one by one equal the size times the number of classes.

Two groups touch the line and none crosses it. The dihedral groups — the symmetries of polygons — follow a formula that the table confirms for three, four, five, six and eight sides. A polygon with an odd number of sides $n$ has $(n+3)/2$ classes: the identity, the $(n-1)/2$ pairs of opposite turns, and all the flips in one class. With an even number it has $(n+6)/2$, because the half turn is central and the flips split into two classes. Dividing by $2n$ gives $(n+3)/4n$ or $(n+6)/4n$, which is $5/8$ at four sides, $1/2$ at three and six, $7/16$ at eight, and tends to $1/4$ as the polygon gains sides: in a polygon with many sides, half the elements are flips and a flip commutes with almost nothing.

The alternating group of five letters, the sixty rotations of an icosahedron and the smallest group that will not come apart into commutative layers, has only five classes, and commutes once in twelve. Robert Guralnick and Geoffrey Robinson showed in 2006 that this is the extreme case: a group that cannot be built from commutative layers commutes at most once in twelve, and reaches one in twelve only when it is this group, possibly alongside a commutative factor. The more a group resists being built from commutative pieces, the fewer classes it has for its size.

A sequence that closes in on one half #

Between the two groups at five-eighths and the dihedral groups at one half and below, the table has two entries marked P2 and P3. They are the start of a family built from the same ingredients as the square’s group.

The square’s group can be generated by two moves on a pair of signed labels: a flip that swaps two labels, and a sign change on one of them. These are the matrices usually written $X$ and $Z$, and they anticommute: $XZ = -ZX$. Take $q$ independent pairs of them, one on each of $q$ two-state systems, and let them generate a group. For $q = 1$ it is the square’s group again. For $q = 2$ it has thirty-two elements; for $q = 3$, a hundred and twenty-eight. These are the real forms of the Pauli groups of quantum information, whose elements are exactly the error operators that a quantum error-correcting code has to detect in its most common setting.

Every one of these groups has a centre of two, $\pm 1$, and any two elements either commute or anticommute. That makes the classes easy to see: each non-central element $g$ is conjugate only to $\pm g$, so there are $(|G| - 2)/2$ classes of two and two classes of one. With $|G| = 2 \cdot 4^q$ that is $4^q + 1$ classes, and the probability is

$$P = \frac{4^q + 1}{2 \cdot 4^q} = \frac12 + \frac{1}{2 \cdot 4^q}.$$

The enumeration confirms it for $q$ up to four, and the formula shows what the figure is drawing: an infinite sequence of groups that commute more than half the time, each less so than the last, approaching one half and never reaching it. The first step of Gustafson’s argument is loose for all of them after the first — their centres are a vanishing fraction — while the second is tight: every non-central element commutes with exactly half the group.

The values the probability can take #

Marking the computed values on one line from zero to one shows the shape of what is possible.

Three features stand out, and each is a theorem rather than an artefact of which groups happened to be drawn. The gap between five-eighths and one is Gustafson’s bound. The crowding just above one half is the Pauli family, and there are other families, such as the dihedral groups falling toward a quarter, which crowd in the same way at other points. And the values thin toward zero as groups become less commutative, with the simple groups sitting low.

David Rusin determined in 1979 every value the probability takes above $11/32$, together with the groups that take them, and Paul Lescot showed in 1995 that every group commuting at least half the time is equivalent, for this purpose, to a commutative group, to the triangle’s group, or to one of the Pauli-type groups. Above one half, the list is the values $\frac12 + \frac{1}{2\cdot 4^q}$ and nothing else, each taken by a group whose commutator subgroup has order two. So the crowding in the figure is not merely one family among possible others: above one half, it is everything.

Shuffles almost never commute #

At the other end, the permutations of $n$ letters get less commutative very fast. Their classes are the cycle shapes, and a cycle shape is a partition of $n$: three letters have three shapes, four have five, five have seven. The probability that two random shuffles of $n$ cards commute is therefore $p(n)/n!$, the number of partitions over the number of permutations.

The number of partitions grows roughly like $e^{\pi\sqrt{2n/3}}$, which is almost exponential in the square root, and the factorial grows faster than any exponential. So the curve on a logarithmic scale bends ever more steeply downward. For a pack of fifty-two cards the probability is about $2.8 \times 10^{5}$ divided by $8 \times 10^{67}$ — two random shuffles essentially never commute. Paul Erdős and Pál Turán noted the count $n!\,p(n)$ of commuting pairs in 1968, in the series of papers in which they began the statistical study of the symmetric group.

What the counting cannot see #

Every figure here is an enumeration of finite groups small enough to write out as permutations, and the checks are exact: each pair was composed both ways and compared, and each total was matched against the class count found independently. What the enumerations establish is the value for each group drawn. They do not establish the theorem. Five-eighths holding for twelve groups, or for twelve thousand, would say nothing about the next one; the bound comes from the two-step argument, and the figures show only that the argument’s two inequalities are tight in the square’s group and loose elsewhere.

Nor does the probability determine the group. The square’s group and the quaternions share it; so do the triangle’s group and the hexagon’s; so, for that matter, does every commutative group, at one. What it records is the ratio of classes to elements, and very different groups can have the same ratio. A group times any commutative group has the same probability as the group alone, since the classes and the elements both multiply by the same factor.

And the argument is for finite groups, where “random” means every element equally likely. For a compact group such as the rotations of space, the same argument goes through with the uniform measure on the group in place of counting, and the ceiling is again five-eighths — though for the rotations of space the answer is zero, since two random rotations almost never share an axis. For an infinite discrete group there is no uniform choice to make, and the question has to be asked of growing finite pieces instead, where it becomes a question about how the ball grows.

Still open: which fractions occur #

Every value of $P(G)$ is a fraction $k/|G|$, but not every fraction between zero and five-eighths is a value. Which ones are is not known.

Keith Joseph conjectured in 1977 that the set of values is well-ordered from above — that every set of values has a largest member — and that its limit points are all rational. Sean Eberhard proved both in 2015, by a structural argument: a group with commuting probability bounded away from zero is close to a commutative one in a precise sense, which is a theorem of Peter Neumann from 1989, and Eberhard sharpened that closeness enough to control the limits. Joseph’s third conjecture, that the set of values together with zero is closed — that every limit of values is itself a value — was left open by that work, and no proof of it has appeared since. The Pauli family shows why it is delicate: its values converge to one half, which happens to be a value, taken by the triangle’s group. Whether every such limit is similarly attained is the question.

What the five-eighths measures #

The probability started as a count of a grid, became a count of classes by the orbit–stabiliser theorem, and was capped by an argument that needs only two facts: the centre of a non-commutative group is at most a quarter of it, and a proper subgroup is at most half. Those two numbers multiply out to five-eighths, and the square’s group is the smallest group in which both are exact.

What the number measures is how far a group is from commuting, in a way the group’s size does not hide. A large group can be nearly commutative — a commutative group times the square’s group commutes five-eighths of the time however large it is — and a small one can be barely commutative at all. The gap between five-eighths and one says something stronger than the bound: there is no such thing as a group that almost commutes. Failing to commute anywhere costs at least three-eighths of the pairs.