Nineteen copies and no more

Two random rearrangements of many letters almost always generate every rearrangement, and the failures can be bounded by adding up the chances of landing in each maximal subgroup. The bound is an overestimate, because some pairs lie in two maximal subgroups at once and are counted twice. For a group small enough to see whole, the double counting can be undone exactly, and the way to undo it is one of the most portable tools in combinatorics: inclusion and exclusion, done over every subgroup at once.

Philip Hall did it in 1936, in a paper with the plain title “The Eulerian functions of a group”. The group he used to show what the method could do was the rotation group of the icosahedron — sixty rotations, the same as the even rearrangements of five letters — and the answer he got for it, $19/30$, has a consequence nobody would guess: the number nineteen is the exact limit of something.

The 3,600 pairs #

Sixty rotations make 3,600 ordered pairs, few enough to close every one.

Two thousand two hundred and eighty pairs generate the whole group: nineteen pairs in thirty. The rest fall into the smaller subgroups, and the shading shows which. The pale corner at the top left is the identity and the fifteen half-turns: a pair of half-turns generates at most the symmetries of a polygon. The largest coloured blocks are the copies of the tetrahedral group inside the icosahedral one — five of them, one for each of the five tetrahedra that can be inscribed in a dodecahedron, the classical fact behind the five solids reduced to three groups.

A direct count is enough for one group. Hall’s question was whether the count could be obtained from the structure — from the list of subgroups — without closing any pairs at all.

Inclusion and exclusion over subgroups #

Every pair generates some subgroup. So the number of all pairs, $60^2$, is the sum over every subgroup $H$ of the number of pairs that generate exactly $H$:

$$|G|^2 = \sum_{H \le G} \phi(H),$$

where $\phi(H)$ counts the pairs of elements of $H$ that generate all of $H$. The same equation holds for every subgroup in place of $G$: the pairs inside $H$ number $|H|^2$, and each generates some subgroup of $H$. That is a triangular system — the count for each subgroup is determined by the counts for the subgroups below it — and it can be solved from the bottom up, or all at once by the device that solves every such system: the Möbius function of the ordering by inclusion. The same device inverts sums over divisors in number theory, where it gives the sums of primitive roots, and over subsets, where it is the alternating sum that counts derangements. Here it gives

$$\phi(G) = \sum_{H \le G} \mu(H, G)\, |H|^2 .$$

The smallest case by hand #

The system is easiest to trust on a group small enough to solve without a computer: the six symmetries of a triangle. Its subgroups are the trivial one, three of order two (the flips), one of order three (the turns) and the whole group. Work upwards. The trivial group is generated by its only pair, so $\phi(1) = 1$. A group of order two has four pairs, of which one — the identity twice — generates the trivial group, so $\phi = 3$. The group of three turns has nine pairs, one of them trivial, so $\phi = 8$. The whole group has thirty-six pairs; subtract the eight that generate the turns, the three for each of the three flips, and the one trivial pair, and $\phi(S_3) = 36 - 8 - 9 - 1 = 18$.

Eighteen in thirty-six is one half, which is what closing every pair found for the rearrangements of three letters. The bottom-up solution and Hall’s formula are the same computation organised differently. The Möbius values for the triangle’s group are $1$ for the whole group, $-1$ for each of the four maximal subgroups and, for the trivial subgroup, $-(1 - 4) = 3$, giving $36 - 9 - 4 - 4 - 4 + 3 = 18$. The formula’s advantage is that it needs only the lattice, not the counts beneath each node, and that most of its terms are zero in groups large enough to matter.

The fifty-nine subgroups, and their weights #

The Möbius values are $1$ for the whole group, $-1$ for each maximal subgroup — the five tetrahedral groups, the six pentagonal ones, the ten triangular ones — and for the smaller subgroups whatever is needed to correct the overcounting. A subgroup of order three lies in one triangular group and two tetrahedral ones and was subtracted three times, so it gets $+2$. A subgroup of order two lies in several maximal subgroups whose intersections overlap again, and the bookkeeping gives $+4$. The subgroups of orders four and five are each contained in only one maximal subgroup, and their value is nought: they drop out entirely. The trivial subgroup gets $-60$.

The sum is $3{,}600 - 720 - 600 - 360 + 180 + 240 - 60 = 2{,}280$. The two numbers agree, and they agree for a reason that has nothing to do with this group: inclusion–exclusion over the subgroup lattice is an identity. What makes it useful is that most terms vanish. Hall proved that $\mu(H, G)$ is zero unless $H$ is an intersection of maximal subgroups, so only the top of the lattice matters, and for large groups the top is all anyone can compute.

The first three terms alone are the union bound from Dixon’s theorem: subtract the pairs inside each maximal subgroup. As a probability that is $1 - 5/25 - 6/36 - 10/100 = 0.533$, against the true $0.633$. The remaining terms repair the overcounting, and for this group the repair is a tenth of the answer.

Nine groups, counted twice #

The method works for any finite group, and running it on several shows how the answer depends on the group.

Size is not what decides the share. The four-element group with two independent switches, $V_4$, is generated by only three-eighths of its pairs, because it has three subgroups of order two and any pair inside one of them fails; in general the two-dimensional space over a field of $p$ elements is generated by a fraction $(1 - 1/p)(1 - 1/p^2)$ of its pairs, and for $p = 2$ that is three-eighths. The group of rearrangements of four letters also manages three-eighths, and the group of five letters $0.475$. The two simple groups do best: the icosahedral group at $19/30$ and the group of 168 symmetries of the seven-point plane at $19/28$. A simple group has nowhere to hide a pair except in its maximal subgroups, and its maximal subgroups are few and small for the group’s size.

The tetrahedral group shows the mechanism in its simplest non-abelian form. Its twelve rotations have one subgroup of order four — the three half-turns with the identity — and four subgroups of order three, one for each vertex; those five are its maximal subgroups. A pair fails to generate exactly when both elements lie in one of them, and the subgroups of order three meet the subgroup of order four only in the identity, so almost nothing is counted twice: the chance of failure is $1/9 + 4/16$, less the pairs of identities counted five times, which comes to exactly one third. Two in three pairs generate. The group of order twelve does as well as the icosahedral group, and better than the group of order twenty-four that contains it, because what matters is how much of the group its largest proper subgroups cover, and a group with a subgroup of index two covers a quarter of its pairs with that subgroup alone.

The agreement between the two columns is not a formality. Closing 28,224 pairs of the 168-element group and solving Hall’s system over its 179 subgroups are entirely different computations, and they produce the same 19,152.

Where the formula is linear algebra #

For the groups $V_4$, $(\mathbb{Z}/3)^2$ and their relatives the count has a second meaning that needs no lattice. Such a group is a vector space over a finite field, and two vectors generate it exactly when they are linearly independent: the first must be non-zero, $p^2 - 1$ choices, and the second must avoid the line through the first, $p^2 - p$ choices. Divided by $p^4$ that is $(1 - 1/p^2)(1 - 1/p)$, the same product that decides when random equations can be solved in coding theory, there extended to many vectors. Hall’s sum reproduces it: the subgroups of the plane over $p$ elements are the plane, its $p + 1$ lines and the origin, with Möbius values $1$, $-1$ and $p$, and $p^4 - (p+1)p^2 + p = p(p-1)(p^2-1)$.

That agreement is what makes Hall’s function a generalisation rather than a trick. For the abelian groups it is counting independent vectors, a question with a classical answer; for the icosahedral group it is counting something with no linear-algebra meaning at all, and the same identity still applies.

The nineteen kinds of generating pair #

The number $2{,}280$ has a second reading. The icosahedral group has 120 symmetries of its own — its automorphisms, the rearrangements of five letters acting by conjugation — and a symmetry carries a generating pair to another generating pair.

No symmetry can fix a generating pair without fixing everything the pair generates — the whole group — so every class has exactly 120 pairs, and $2{,}280 / 120 = 19$. Each class is a genuinely different way of presenting the icosahedral group by two generators. The triple $(2, 3, 5)$ is the classical one: a half-turn about the axis through the midpoint of an edge, a third-turn about the axis through the centre of a face, and their product a fifth-turn about the axis through a vertex. It is the rotation group as a triangle group, the presentation $a^2 = b^3 = (ab)^5 = 1$ that every picture of the icosahedron’s symmetry mirrors. The other eighteen classes are less familiar, and three of the order triples occur twice: the same orders, not equivalent under any symmetry.

Twenty copies need three generators #

Here is the consequence. Put $k$ copies of the icosahedral group side by side — the group $A_5^k$, whose elements are $k$-tuples of rotations multiplied coordinate by coordinate — and ask whether two elements can generate it.

A pair of $k$-tuples generates the product when each coordinate is a generating pair of $A_5$ and no two coordinates are related by a symmetry: if two coordinates were related, the group generated would be confined to the tuples whose two coordinates are related in the same way, a “diagonal” subgroup much smaller than the product. That is Hall’s argument, and because $A_5$ is simple it is the only obstruction. So the count is $2{,}280 \times (2{,}280 - 120) \times (2{,}280 - 240) \times \cdots$, one class used up per coordinate. With nineteen classes, nineteen coordinates can be filled. The twentieth has none left.

$A_5^{19}$ is generated by two elements; $A_5^{20}$ needs three.

The reason the related coordinates are the only obstruction is a property of simple groups, and it is worth stating because it is where the icosahedral group’s refusal to come apart does its work. A subgroup of a product of two copies of a simple group that maps onto each copy is either the whole product or the graph of an isomorphism between the copies — Goursat’s lemma, specialised to a group with no normal subgroups to share. So the subgroup generated by a pair of tuples either is everything or is caught on a “diagonal” where two coordinates are tied together by a symmetry. Counting the tuples that avoid every diagonal is counting the classes, one per coordinate.

Nothing in the group’s appearance announces the jump. Its elements are $60^{19}$ in one case and $60^{20}$ in the other, both astronomically many, and in both cases two random elements look the same; but the first has two-element generating sets — about $10^{57}$ ordered pairs of them — and the second has none. The number of generators a product needs is set by a count of classes, not by size, and it rises only slowly: $A_5^k$ needs three generators until the classes of generating triples run out, and Hall’s sum with cubes in place of squares counts $200{,}160$ generating triples in $1{,}668$ classes — so three generators suffice up to $1{,}668$ copies.

Polygons, triangles and tetrahedra, closed by brute force #

Every count in the figures is exact. The 3,600 and 28,224 pairs were closed directly; the subgroup lists were built by closing every pair and keeping the distinct results, and Hall’s sum was evaluated over them and checked against the direct count for each of the nine groups. That check covers the one gap in the method: building subgroups from pairs finds only subgroups generated by two elements, and a group with a subgroup needing three would have a lattice with a missing node. For these groups no subgroup needs three, and the agreement of the two counts is the evidence that nothing was missed.

The product figure is computed from Hall’s formula, not by closing anything: $A_5^{19}$ has far too many elements to enumerate. Its correctness rests on Hall’s theorem that a pair of tuples generates the product exactly when its coordinates are pairwise inequivalent generating pairs — a theorem, not a measurement — and the nineteen classes that feed it were counted directly. The jump at twenty is therefore proved, and the figure is its arithmetic.

What no figure here shows is why the classes come out as nineteen rather than any other number. Hall’s sum computes it; it does not explain it, and the count for other simple groups follows no visible pattern: the 168 symmetries of the seven-point plane have 336 automorphisms, and their 19,152 generating pairs fall into $19{,}152 / 336 = 57$ classes, so fifty-seven copies of that group are generated by two elements and fifty-eight are not.

Still open: the exact count for families #

Hall’s method gives the number of generating pairs for any group whose subgroup lattice can be written down, and for many families of groups it has been carried out exactly: the groups $PSL(2, p)$ were done by Hall himself, and their Eulerian functions are polynomials in $p$. For most families it has not, because the top of the subgroup lattice — the maximal subgroups and their intersections — is not known in closed form. The probability that two random elements generate a finite simple group tends to one as the group grows, a theorem of Liebeck and Shalev that needs the classification of finite simple groups; the rate at which it does so, and the exact Möbius values that would give it, are known only family by family.

A sharper question concerns the product phenomenon. The largest $k$ for which $S^k$ is generated by two elements is the number of classes of generating pairs of $S$ under its automorphisms, and for the sporadic simple groups — the Monster among them — that number is enormous and its exact value generally unknown, because it requires the Möbius function of a lattice nobody has fully listed.

The question also has a practical side that keeps it alive. Algorithms that compute with large permutation groups — checking whether a puzzle position is reachable, finding a group’s order from a few generators — work by drawing random elements and assuming that a handful of them generate whatever they are drawn from. Hall’s numbers, and their asymptotic versions for the simple groups, are the guarantee behind that assumption: a constant fraction of pairs generate, so a few tries suffice. How large that fraction is for the groups that actually arise in such computations, which are rarely simple and often products, is exactly the Möbius sum that is hard to evaluate, and in practice it is estimated by sampling rather than computed.

A count that ends #

The question “how likely is it that two random elements generate this group” has, for the icosahedral group, the answer nineteen in thirty, and Hall’s method computes it without closing a single pair: weight every subgroup by its Möbius value and the square of its size, and add. Most weights are nought, and the rest repair the overcounting that a simple union bound commits.

The same number, read differently, is a count of the essentially different ways to generate the group with two elements — nineteen — and that count is a limit on products: nineteen copies of the icosahedral group can be driven by two elements, and the twentieth copy is one too many. It is a rare example of a structural fact about infinite-looking objects that can be read straight off a small, exact, finite sum.