Two random shuffles reach every shuffle

Two random symmetries commute at most five times in eight, and for the rearrangements of many letters almost never. That was a question about how two elements of a group get along with each other. Here is a question about what two elements can do together.

Take two rearrangements of $n$ letters, $a$ and $b$, chosen at random, and allow them to be used as often as wanted in any order: $a$, then $b$, then $a$ twice, then $b$ backwards, and so on. Every rearrangement that can be produced this way is said to be generated by $a$ and $b$, and together they form a group, the subgroup that $a$ and $b$ generate. The question is how big it is. Can two arbitrary moves, chosen with no plan, shuffle the letters into every order there is?

The answer is that they almost always can, or nearly. Eugen Netto conjectured in 1882 that two random rearrangements generate either every rearrangement or exactly the even ones with probability tending to one as $n$ grows, and John Dixon proved it in 1969. The failures, when they happen, have a dull and specific cause, and it is the cause that makes the theorem easy to believe and hard to prove.

Four letters, every pair #

The rearrangements of four letters are few enough to test every pair.

The pattern has structure. Pairs involving the identity generate only what the other element generates on its own — a cycle, never the whole group — so the top row and left column are pale. Two 3-cycles never leave the even rearrangements, so the block of 3-cycles against 3-cycles is cool where it is not pale: two 3-cycles that move different triples of letters generate all twelve even rearrangements, and two that are powers of each other generate only a cycle of three. The whole group appears only when at least one of the pair is odd, and then often but not always: a swap and a 4-cycle generate everything if the swap is not across the cycle’s diagonal, and only the eight symmetries of a square if it is — the same group whose commuting pairs counted five-eighths.

Two hundred and sixteen pairs of 576 reach everything: exactly three-eighths. Another ninety-six reach the twelve even rearrangements. Together that is 0.542 — not overwhelming. Four letters is too few for the theorem to be visible, because the group of 24 has thirty subgroups to fall into and a random pair lands in a small one often.

Counting every pair up to six letters #

The same count can be done for a few more sizes before the pairs become too many.

The share reaching at least the even rearrangements dips at four letters and recovers: 0.722 at three, 0.542 at four, 0.633 at five, 0.589 at six. Five letters is better than four because the even rearrangements of five letters form a simple group, the rotations of the icosahedron, which has few subgroups compared with its size; the group of four letters has the even rearrangements of four letters inside it, which is not simple, and a normal subgroup of order four inside that, and every one of those subgroups is a trap.

From five letters on there is a second regularity. The cool share is almost exactly a third of the warm share. That has a two-line reason, and it is the first half of the theorem’s shape.

The quarter that parity takes #

Every rearrangement is either even or odd — a product of an even or an odd number of swaps — and the parity is a fixed property, the one invariant that survives every way of writing a rearrangement down. Composing two even rearrangements gives an even one. So if $a$ and $b$ are both even, everything they generate is even, and the most they can reach is the even half of the group. If either is odd, what they generate contains odd elements and cannot be confined to the even half.

Each of $a$ and $b$ is even with probability one half, independently, so both are even one time in four. That splits the theorem in two: as $n$ grows, two random rearrangements generate every rearrangement with probability tending to $\tfrac34$, and exactly the even ones with probability tending to $\tfrac14$. The exact counts already show it at six letters: 228,960 pairs reach everything and 76,320 reach the even half, a ratio of exactly three. The question that remains is only whether the pair reaches at least the even half, and the parity of the pair then says which.

Thirty letters, sampled #

Past six letters every pair cannot be checked. Instead pairs can be drawn at random and each tested — and the test needs care, because computing the group two permutations of thirty letters generate by listing its elements is impossible: there are $30!/2$ of them if the answer is yes.

The share climbs steadily: 0.795 at seven letters, 0.881 at ten, 0.948 at twenty, 0.966 at thirty. From about nine letters on the points sit on the curve $1 - 1/n - 1/n^2 - 4/n^3$, which is the beginning of an expansion Dixon established in 2005, refining his own theorem: the chance of failure is $1/n$ plus smaller terms. At thirty letters $1/n$ is 0.033, and the measured failure rate is 0.034.

The test behind the rings is the interesting part, and it is one-sided in a useful way. Three properties are checked in turn. First, whether the two permutations between them move every letter to every other — whether the group is transitive. Second, whether they preserve no system of blocks — no way of grouping the letters into equal clusters that every move keeps intact — which makes the group primitive. Third, whether some product of them, raised to a suitable power, is a single cycle of prime length at most $n - 3$. If all three hold, a theorem of Camille Jordan from 1873 says the group contains every even rearrangement, and the test has proved it without listing anything.

One word that certifies a pair #

Jordan’s theorem turns an impossible enumeration into a search for one short product.

Raising a permutation to a power that is a multiple of every other cycle length, but not of the chosen prime $p$, kills every other cycle and leaves a single $p$-cycle. Random permutations have a cycle of prime length with no other cycle of that length surprisingly often — a random permutation’s cycle lengths behave like independent counts with means 1, ½, ⅓, … — so a handful of random products almost always supplies one. In the run behind the figures, every transitive, primitive pair of fourteen letters or more produced a witness within a few hundred products; at nine to twelve letters a handful did not, and each of those was settled by computing its group directly — they were the genuine exceptions described below.

The theorem behind the witness is a statement about how primitive groups can contain small pieces. A primitive group is “glued together”: no clusters, every letter reachable from every other. Jordan showed that such a group cannot contain a short prime cycle without containing them all, and the three-cycles generate the even rearrangements. The witness is a local fact — one cycle — that a global property turns into a statement about the whole group.

Why the failures fail #

The second half of the theorem is the shape of the failures, and they have three possible causes.

The commonest cause by far is the plainest. If some letter is left in place by both $a$ and $b$, then nothing they generate moves it, and the group is stuck inside the rearrangements of the other $n - 1$ letters. Each permutation fixes a given letter with chance $1/n$, so both fix it with chance $1/n^2$, and there are $n$ letters: the expected number of shared fixed letters is $1/n$, and the chance of at least one is very nearly that. From twelve letters on, a shared fixed letter accounts for most of every failure, and the dashed curve $1/n$ is the failure rate almost exactly.

Other intransitive pairs split the letters into a larger orbit and a smaller one in some other way — a shared pair of letters swapped between themselves by both, for instance — and those are rarer by a further factor of $n$. Pairs that are transitive but keep blocks are rarer still: at eight letters, about one pair in forty keeps the letters in two blocks of four or four blocks of two; at fourteen and sixteen letters one pair in 3,000 did, and from twenty letters none. The third cause is the one the group theory was always about: a primitive group that is not the whole thing. At seven letters there are three of them that a random pair can land in — of orders 21, 42 and 168, the last being the symmetries of the seven-point plane — and they catch about three pairs in a hundred. At eight letters about as many pairs are caught, at nine letters thirteen in 3,000, at twelve letters one, and from fourteen letters none.

So the failures are local accidents, not structural traps. That is the content of Dixon’s theorem, and the reason a careful proof is still hard: it has to show that the third cause — landing in some primitive group other than the obvious ones — is negligible for every $n$, and that requires knowing that primitive groups other than $S_n$ and $A_n$ are small. Dixon’s original argument used older bounds on how large such groups can be. Later sharpenings, including the expansion drawn above, used the classification of finite simple groups, which makes the list of primitive groups explicit.

Adding up the traps #

The $1/n$ can be derived rather than observed, and the derivation is the skeleton of Dixon’s proof. Two elements fail to generate a group exactly when both lie in some maximal subgroup — a proper subgroup with nothing between it and the whole group. For a particular subgroup $M$, the chance that two random elements both land in it is $(|M|/|G|)^2$, the square of one over its index. Adding over every maximal subgroup gives an upper bound on the chance of failure, and for large groups the bound is close to the truth, because two different maximal subgroups rarely both contain a random pair.

For four letters the bound can be written out. The maximal subgroups of the 24 rearrangements are the even half (one of them, index 2), the rearrangements fixing one letter (four of them, index 4) and the symmetries of a square on the four letters (three, index 3). The bound is $1 \cdot \tfrac14 + 4 \cdot \tfrac1{16} + 3 \cdot \tfrac19 = 0.83$, against a true failure rate to reach everything of $1 - 0.375 = 0.625$: an overestimate, because a pair lying in two maximal subgroups at once — two of the double swaps, for instance, which lie in the even half and in a square’s symmetries — has been counted twice.

For $n$ letters, set the even half aside — it is the parity quarter already accounted for — and look at the rest. The subgroups fixing one letter are $n$ in number, each of index $n$, and contribute $n \cdot 1/n^2 = 1/n$. That is the whole leading term. The subgroups that keep two letters among themselves have index $\binom n2$ and number $\binom n2$, contributing about $2/n^2$; the block systems have indices that grow faster than any power of $n$; and the primitive maximal subgroups, by the theorems on how small such groups must be, contribute less than any power of $1/n$. So the chance of failure is $1/n$ plus terms of order $1/n^2$ — the curve the samples follow — and the whole difficulty of the proof sits in that last clause about primitive groups, which a picture can only illustrate by showing them disappearing.

What two moves cannot share #

A shuffled deck is the familiar setting. Two particular shuffles — a cut and a riffle, say — will usually generate every arrangement of the cards; the walk that repeats random shuffles is about how quickly a random product of them spreads over the group, and that question presupposes this one. The puzzles that are exactly half solvable are the parity half of the theorem made concrete: moves that are all even can never reach an odd arrangement, however many are combined, and that is the whole of their obstruction.

The theorem also says something about the rotations of a cube and other symmetry groups, by contrast. Those groups are tiny — twenty-four elements — and are generated by two well-chosen moves, but two random elements of them often fail to generate, because a small group has proportionately many small subgroups. Large symmetric groups are the opposite: they have relatively few subgroups for their size, and almost every pair escapes all of them.

Three thousand pairs stand in for all of them #

The exact counts up to six letters are complete, and every share in the first two figures is a count of every pair. Beyond six letters the shares are estimates from 3,000 pairs at each size, with sampling errors of about half a per cent; the theorem is that the true values tend to one, and no finite sample shows a limit.

The classification of each sampled pair is rigorous in one direction. When the test says a pair reaches at least the even rearrangements, it has proved it, by Jordan’s theorem at nine letters or more and by computing the group outright or by Bochert’s bound on primitive groups below that. When it says a pair fails, the reason it gives — two orbits, a block system, or a small primitive group closed and measured — is also a proof. The single pair of twelve letters that resisted the witness search was settled by computing its group outright: it stopped short of 100,000 elements, below the largest primitive group of degree twelve that falls short of the even rearrangements, so it is one of those small primitive groups and is counted as a failure. Nothing in the figures rests on a guess about what a pair generates.

What the figures cannot show is the expansion’s later terms. The curve $1 - 1/n - 1/n^2 - 4/n^3$ fits from nine letters, and at those sizes the next term is a fraction of a per cent — smaller than the sampling error. The coefficients beyond it are known from theory, not from anything drawn here.

Still open: how fast the rest of the group comes along #

For the symmetric groups the question is closed in its first form: two random elements generate, and the failure rate is $1/n$ to first order. The open questions are about other families and other counts. For every finite simple group, two random elements generate it with probability tending to one as the group grows — a theorem of Liebeck and Shalev and of Kantor and Lubotzky, from the 1990s, that again needs the classification — but how fast the probability tends to one, family by family, is understood only in part.

The question also has a converse shape: how many random elements are needed to generate a group that is not simple, such as a product of many copies of one group? There the answer is not “two”, and the number can jump without warning — Philip Hall’s computation for the icosahedral group is the classic case — and the expected number of random elements needed to generate a general finite group is bounded in terms of its structure in ways that are still being sharpened. Even for products of symmetric groups, the exact chance that two random elements generate is a sum over subgroups that nobody has evaluated in closed form.

A local accident, not a structural trap #

Two randomly chosen moves are enough to reach every arrangement of $n$ letters, apart from the parity they jointly carry, with probability tending to one. The number that is left over, $1/n$, is almost entirely the chance that both moves happen to leave the same letter alone. Everything else that could stop them — orbits, blocks, the small primitive groups — fades faster than that.

The proof needs more than the picture. It needs to know that the large symmetric groups contain no large primitive subgroups beyond the obvious ones, and that knowledge is among the deepest facts about finite groups. But the figures show the phenomenon the proof explains: generation is the rule, the failures are coincidences about single letters, and a single prime cycle in a short word is enough to certify that two random moves reach everything.