Necklaces made of symmetries

The six symmetries of a triangle are three turns — doing nothing, a third of a turn, two thirds — and three flips. Six is two times three, and there is a symmetry of order two (any flip) and a symmetry of order three (either turn). Eight is a power of two, and the square has symmetries of order two — the half turn and all four flips. The twelve rotations of a tetrahedron, twelve being four times three, include half turns of order two and third turns of order three.

That every prime dividing a group’s size turns up as the order of an element is Cauchy’s theorem, proved by Augustin-Louis Cauchy in 1845. It is the part of the converse of Lagrange’s theorem that survives. The general converse fails — the tetrahedral group has twelve elements and no subgroup of six — but for a prime $p$ dividing the order there is always an element $g$ with $g^p = e$ and $g \ne e$, and the powers of that element are a subgroup of exactly $p$.

Cauchy’s own proof was long. In 1959 James McKay published one in the American Mathematical Monthly that fits in a paragraph and is a counting argument about necklaces.

The necklace #

Fix a prime $p$ dividing the order of a group $G$. Look at all ways of choosing $p$ elements in order, $(g_1, g_2, \ldots, g_p)$, such that doing them all in turn gives nothing: $g_1 g_2 \cdots g_p = e$.

The first $p - 1$ can be anything. The last is then forced: it has to be whatever undoes the product of the others. So the number of such tuples is $|G|^{p-1}$ — for the triangle and $p = 3$, that is $6^2 = 36$. Since $p$ divides $|G|$, the number of tuples is a multiple of $p$.

Now turn a tuple round: move the first element to the back, giving $(g_2, \ldots, g_p, g_1)$. Its product is still the identity. If $g_1 g_2 \cdots g_p = e$ then $g_2 \cdots g_p = g_1^{-1}$, and so $g_2 \cdots g_p\, g_1 = g_1^{-1} g_1 = e$. Turning is therefore a way of moving the tuples among themselves, and the tuples fall into rings — the orbits of turning.

The turning is a cyclic group of order $p$ acting on the tuples. By the orbit–stabiliser count, each ring’s size divides $p$, and because $p$ is prime, each ring has either one tuple or exactly $p$. A ring of one is a tuple that turning does not change, which means every entry equals the next: $(g, g, \ldots, g)$. And such a tuple has product $e$ precisely when $g^p = e$.

The count #

So the tuples split into rings of $p$ and singletons, and the singletons are the solutions of $g^p = e$. Write the count out:

$$|G|^{p-1} = (\text{number of solutions of } g^p = e) + p \times (\text{number of rings of } p).$$

The left side is a multiple of $p$ and so is the last term. So the number of solutions of $g^p = e$ is a multiple of $p$. It is at least one, because $e$ is a solution. A multiple of $p$ that is at least one is at least $p$, so there are at least $p - 1$ solutions besides $e$, and every one of them has order exactly $p$ — its order divides $p$ and is not 1.

That is the entire proof. For the triangle, the singletons are $(e, e, e)$, $(r, r, r)$ and $(r^2, r^2, r^2)$: three solutions, a multiple of three, and two of them are the turns of order three. The figure lists all thirty-six triples rather than trusting the count, and checks that every card’s triples really do have product $e$ and really are turns of one another.

The smallest case is worth seeing as well, because at $p = 2$ the argument becomes something familiar.

A pair with product $e$ is an element and its inverse, and turning a pair swaps them. The pairs that do not move are the elements that are their own inverses. So the argument at $p = 2$ says: pair every element of a group with its inverse, and the elements left over, each paired with itself, number an even amount when the group does. The identity is one of them, so there is another, and it has order two. Every group of even size has an element of order two, by the same pairing that shows a finite set with a fixed-point-free involution has even size.

The same beads, a second time #

The argument is the one that proves Fermat’s little theorem with necklaces, and the resemblance is exact rather than loose.

There, the beads were colours: strings of $p$ beads in $a$ colours, $a^p$ of them, turned round a loop. Rotation sorted them into rings of $p$ and singletons; the singletons were the $a$ strings of a single colour; so $a^p - a$ was a multiple of $p$. Here the beads are elements of a group, the strings are required to multiply to $e$, there are $|G|^{p-1}$ of them, and the singletons are the solutions of $g^p = e$. The two proofs share the one fact that makes both work: a cyclic group of prime order acting on anything has orbits of size 1 and $p$ and nothing else. Every conclusion either argument reaches is that fact read modulo $p$.

McKay’s proof also inherits the necklace proof’s peculiar character. It does not find an element of order $p$. It proves that the solutions of $g^p = e$ come in a multiple of $p$, and deduces from the arithmetic that there must be more than the obvious one. To produce the element, something still has to search — though the proof does say how many there are to find, modulo $p$. The same is true of the statement that a finite field’s non-zero elements are all powers of one of them: the count proves a generator exists and a search, guided by the count, is how one is actually found, as it is for the residues whose powers run through everything.

There is one further thing the count reveals. The elements of order exactly $p$ number one fewer than a multiple of $p$ — they leave remainder $p - 1$ on division by $p$. And they come in groups of $p - 1$ anyway, because an element of order $p$ generates a subgroup of order $p$ whose $p - 1$ non-identity elements all have order $p$ and generate the same subgroup. So the number of subgroups of order $p$ is (a multiple of $p$, minus one) divided by $p - 1$, which works out to leave remainder 1 on division by $p$.

Seven groups, counted without drawing #

For groups larger than a dozen elements the tuples are too many to draw, but the two numbers the argument turns on are still easy to count.

The rows repay reading down. The even symmetries of five letters — the rotation group of the icosahedron and dodecahedron, sixty elements — has $60^4 = 12{,}960{,}000$ tuples of five with product $e$, and 25 solutions of $g^5 = e$: the identity and 24 elements of order five, the fifth turns about the six axes through opposite corners of an icosahedron, four per axis. Twenty-five is a multiple of five. For $p = 3$ there are 21 solutions — the identity and twenty third-turns, two about each of ten axes — and 21 is a multiple of three. For $p = 2$ there are 16: the identity and fifteen half turns.

The last column is always one less than a multiple of the prime: 15, 20 and 24 for the sixty-element group, 9 and 8 for the twenty-four symmetries of four letters. That is the remainder $p - 1$ from the previous section, visible in every row.

The dihedral rows show the other thing the count guarantees and no more. The symmetries of a pentagon have five elements of order two and four of order five; the symmetries of a hexagon have seven of order two and two of order three. Cauchy’s theorem promises at least one element of each prime order and says nothing about how many beyond the congruence.

Why the length has to be prime #

Every step used that $p$ is prime at exactly one place: a ring’s size divides $p$, so it is 1 or $p$. Try the argument with a composite length and it breaks there.

Six divides six, the order of the triangle’s symmetry group, and the count $|G|^{n-1} = 6^5 = 7{,}776$ is a multiple of six as before. But now a tuple like $(e, r, e, r, e, r)$ — whose product is $r^3 = e$ — returns to itself after two turns rather than six, and sits in a ring of two; a tuple repeating a block of two elements three times is in a ring of two, and one repeating a block of three twice is in a ring of three. The singletons are still the tuples $(g, g, \ldots, g)$ with $g^6 = e$ — and every element of the triangle group satisfies $g^6 = e$, because every order divides six. Six singletons, a multiple of six, and not one element of order six. The group has elements of order one, two and three and nothing else.

That is not a failure of the counting. The count is true: the solutions of $g^6 = e$ do number a multiple of six. What fails is the deduction, since a solution of $g^6 = e$ other than $e$ need not have order six. With a prime, a solution that is not the identity has nowhere else to go.

Frobenius’s multiple #

The true count in that last figure is a theorem of its own, and a stronger one than Cauchy’s. In 1895 Georg Frobenius proved that for every divisor $d$ of a group’s order, the number of solutions of $x^d = e$ is a multiple of $d$.

The tetrahedral group gives 1, 4, 9, 4, 12 and 12 solutions for $d$ equal to 1, 2, 3, 4, 6 and 12, and each is a multiple of its $d$: 4 of 2, 9 of 3, 4 of 4, 12 of 6, 12 of 12. At $d = 4$ the solutions are exactly the solutions of $x^2 = e$, because nothing has order four — the identity and the three half turns about the axes through opposite edge midpoints — and four happens to be a multiple of four. The theorem holds whether or not an element of order $d$ exists, which is exactly why it cannot be used to find one.

For $d$ prime, Frobenius’s theorem is the McKay count. For composite $d$ the known proofs are longer, and none has been reduced to a paragraph about turning tuples: the necklace argument sees only rings, and at a composite length the rings of intermediate size carry information the argument has no way to read. The statement that the divisor counts are multiples is nevertheless of the same shape as everything else here — a count that has to come out divisible, forced by a structure the count itself does not display.

Where the counting leads: Sylow #

Cauchy’s theorem finds subgroups of prime order. The strongest form of the partial converse finds subgroups of the largest prime-power order dividing the group, and counts them.

Ludwig Sylow proved in 1872 that if $p^k$ is the largest power of $p$ dividing $|G|$, then subgroups of order $p^k$ exist; that they are all conjugate to one another; and that their number leaves remainder 1 on division by $p$ and divides $|G|/p^k$. The table checks all three on six groups. The sixty rotations of the icosahedron have five subgroups of order four, ten of order three and six of order five; five, ten and six leave remainder one on division by two, three and five respectively, and divide fifteen, twenty and twelve. The twelve rotations of the tetrahedron have a single subgroup of order four, which is therefore normal, and four of order three — one for each axis through a corner.

The remainder-one condition is the same arithmetic as the count of subgroups of order $p$ above, and Helmut Wielandt’s 1959 proof of the existence half is a relative of McKay’s: it lets the group act on its subsets of size $p^k$ and reads the orbit sizes modulo $p$. The restriction on the count is what makes Sylow’s theorems a tool rather than a curiosity. A group of fifteen elements must have exactly one subgroup of five, since the count divides three and is one more than a multiple of five; and exactly one of three, since it divides five and is one more than a multiple of three. Both are then normal, and from there the group can only be the cyclic one. That a group of every order $pq$ with $p < q$ and $q - 1$ not a multiple of $p$ is cyclic follows the same way, with no group ever written down.

What the figures cannot establish #

The two drawn figures list every tuple, and the tables count every solution by computing every power. That verifies the counts in the groups on the page and says nothing about any other group; the general statement is the argument in the second section, which uses only that turning a tuple preserves its product and that a group of prime order has orbits of sizes 1 and $p$.

The figures also do not show which element of order $p$ the argument promises. The proof is an existence proof by counting, and in a large group given only by a multiplication rule it gives no procedure better than searching the solutions of $g^p = e$ one at a time. It tells a search what to expect — a multiple of $p$ — without telling it where to look.

And the Sylow table found its subgroups by generating from pairs of elements, which is enough for every group on it but is not an argument that pairs always suffice. For the groups drawn, the counts were cross-checked against the conjugates of one subgroup, which is Sylow’s second theorem used as a test of the search rather than taken on trust.

Finally, a picture of tuples shows rings and singletons but not the reason turning preserves the product. That reason is a line of algebra — the product of the turned tuple is the old product conjugated by the element that moved — and it is the one step where the group’s structure enters at all. The rest of the proof would apply to any set of strings closed under turning.

Still open: a proof of Frobenius’s converse without the classification #

Frobenius asked the obvious next question in 1907. Suppose the equation $x^d = e$ has exactly $d$ solutions, the smallest number his theorem allows. Do those solutions then form a subgroup? For the cyclic groups it is true and easy. In general it was open for more than eighty years.

It was settled in 1991 by Nobuo Iiyori and Hiroyoshi Yamaki, and settled in the affirmative — but the proof depends on the classification of finite simple groups, the enormous enumeration completed in the 1980s across tens of thousands of pages. No proof is known that avoids it. A statement about counting solutions to one equation, whose weaker form yields to a paragraph about necklaces, needs for its converse the complete list of the pieces all finite groups are built from.

That gap is typical of where finite group theory now stands. Counting arguments of McKay’s kind reach remarkably far, and then stop at questions that seem no harder and turn out to require knowing every finite simple group by name. The smallest of those pieces that is not a cycle is the sixty-element group in the tables above, the group that will not come apart and the reason the quintic has no formula; the classification says every other piece belongs to one of eighteen infinite families or is one of twenty-six exceptions. Whether some argument about orbits and counting could reach Frobenius’s converse directly, as McKay’s reaches Cauchy’s theorem, nobody knows.

The shape of the argument #

The whole proof is a single move made twice in this subject. Take a set whose size is known to be a multiple of $p$. Let a cyclic group of order $p$ act on it. Read off that the fixed points are a multiple of $p$ as well. Then notice that the fixed points are something of interest — single-coloured necklaces in Fermat’s case, elements of order dividing $p$ in Cauchy’s.

The move is also the one behind the colourings nobody can tell apart, where the fixed points of each motion are counted and averaged, and behind the parity of permutations, where the crossings will not come out even for the same reason a count modulo two is fixed. In each case a small group acting on a large set is made to report a remainder.

The choice of set is where the ingenuity is. McKay’s set, the tuples with product $e$, is arranged so that its size is obviously $|G|^{p-1}$ and its fixed points are obviously the solutions of $g^p = e$; neither fact takes more than a line. The group of the triangle, turned three at a time, gave three singletons and eleven rings, and from that the triangle had to have a symmetry of order three — something anyone can see, reached by a route that works equally well for groups nobody can see.