How many subgroups of index three

Maximal subgroups are found by closure: take operations out of a group and see what still closes. That works, it produces Hermann’s theorem, and it answers a narrower question than it appears to.

Most subgroups are not maximal. A subgroup of index four is generally not maximal — there is something between it and the group — and closure has no way to reach it except by walking down a chain and hoping the chain passes through. What is wanted is a method that counts all the subgroups of a given index, and there is one.

Subgroups are actions #

A subgroup H of index n in G gives G an action: G permutes the n cosets of H, and the stabiliser of the coset H is H itself. The action is transitive because the cosets are one orbit.

That runs backwards too. Given any transitive action of G on n points, the stabiliser of a point is a subgroup of index n. So subgroups of index n correspond exactly to transitive actions on n points — and an action on n labelled points is a homomorphism G → Sₙ.

Each subgroup gives several labelled actions, because the point corresponding to H can be labelled 1 and the other n − 1 can be labelled in any order. So

$$\#\{\text{subgroups of index } n\} = \frac{\#\{\text{transitive homomorphisms } G \to S_n\}}{(n-1)!}.$$

And a homomorphism out of a presented group is a search. A plane group written as letters and relations is two, three or four generators and a handful of relators; a homomorphism is a choice of permutation for each generator such that every relator becomes the identity. For n ≤ 4 that is a search over at most 24⁴ tuples, which is finite, complete and takes milliseconds.

Nothing in that procedure knows what a lattice is, what a rotation is, or that the group has anything to do with the plane.

The zeros #

The striking entries in the table are the empty ones, and there are two kinds.

p3 has no subgroup of index two. A subgroup of index two is always normal, so it would give a surjection from p3 onto a group of order two — and every such surjection factors through the abelianisation, which for p3 is ℤ₃ ⊕ ℤ₃. A group in which every element has order dividing three has no quotient of order two. So the answer is zero for a reason that never mentions the plane, and the same argument gives zero at index two for exactly the groups whose abelianisation has odd order.

p4, p4m and p4g have no subgroup of index three. This one is more interesting, and there is a second reason for it that this collection already has the machinery for.

Suppose H has index three in p4. Three is coprime to the order of the point group, so the index has to be carried by the translations: H’s translation subgroup is a sublattice of index three in the square lattice, and it has to be carried onto itself by the four-fold rotation. There is no such sublattice. This site counts the sublattices of a square lattice that keep the four-fold symmetry, and their indices are exactly the numbers that are sums of two squares — 1, 2, 4, 5, 8, 9, 10, 13 — and three is not one of them.

So a fact about which integers are sums of two squares, and a search over triples of permutations of three points, give the same zero. That agreement is the pleasure of the whole exercise: the second calculation contains no arithmetic of any kind.

Twelve subgroups of p2, and what they are #

The largest count at index three is p2’s twelve, and it is worth unpacking because it shows what the permutation method is actually seeing.

p2 is generated by two translations and a half-turn. A subgroup of index three either contains the half-turn or does not. If the index is carried by the translations, the subgroup is p2 again on a sublattice of index three — and an oblique lattice has four sublattices of index three, which is σ(3), the sum of the divisors, so that is four of the twelve. The other eight come from subgroups whose translation part has index three and whose half-turn sits at a different centre, which is the same lattice arithmetic seen from a different origin.

The divisor sum is doing more work here than the arithmetic makes it look. σ(n) counts the sublattices of index n in any two-dimensional lattice, oblique or square or hexagonal, because it counts integer matrices in Hermite normal form and the shape of the cell never enters. What the shape decides is which of those sublattices the point group carries onto itself, and that is where the four-fold groups lose their index of three: all four sublattices of index three exist in a square lattice, and no four-fold rotation maps any of them to itself. So the same number appears twice with two different meanings — as the whole answer for p1, which has no point group to impose a condition, and as an upper bound everywhere else.

None of the twelve is normal. That is the surprise, and it is worth being clear about why it is one: at index two every subgroup is normal automatically, so the first index where non-normal subgroups can appear is three, and p2 uses the opportunity fully. Twelve subgroups, four conjugacy classes of three, none of them normal.

The conjugacy classes are the geometrically meaningful unit here. Three subgroups in one class are the same subgroup drawn at three different positions, related by an element of p2 that is not in any of them — so a reader looking at the patterns would see one pattern in three placements, which is precisely what a conjugacy class of subgroups is for.

What a count of subgroups is worth #

Subgroups of small index are not an abstract amusement in this subject; three of this collection’s other threads are exactly this count under other names.

Colour symmetry is index: a two-colouring of a pattern is a subgroup of index two together with a rule for which coset gets which colour, and the number of distinct two-colourings of a group is a count of its index-two subgroups. Three colours needs index three, and the table above says immediately which groups can be three-coloured at all — every group with a nonzero index-three entry, and no other.

Superstructures are index: an ordered alloy whose cell is n times the parent’s has a space group that is a subgroup of index n in the parent’s, and which superstructures are possible is a subgroup count.

Phase transitions are index: the descent of symmetry at a transition takes the group to a subgroup, and the index is the number of domains that appear.

And the three are not three readings of one number; they are two readings, and the split is computable. A subgroup of index two either keeps the whole lattice and gives up half the point group, or keeps every point operation and gives up half the lattice. The first is a transition with two domains in an unchanged cell; the second is a superstructure, whose doubled cell shows itself as a new set of reflections. For a prime index there is no third possibility, because the index has to be paid somewhere and there are only two places to pay it from. pgg and p4g pay only the first way and p1 only the second, having no point operations to surrender.

So the zeros in the table are physical statements. p4 has no subgroup of index three, so a crystal with p4 symmetry has no three-domain transition to a subgroup of that index, and no three-colouring. The number three is unavailable to it, and the reason is that three is not a sum of two squares.

Two checks with nothing in common #

An enumeration is worth what its checks are worth, and this one has two.

p1 against the divisor sum. The subgroups of index n in p1 are the sublattices of index n, whose number is σ(n), the sum of the divisors. Counting the same objects as pairs of commuting permutations gives 3, 4 and 7 at indices two, three and four — which are σ(2), σ(3) and σ(4). One calculation enumerates integer matrices in Hermite normal form; the other enumerates permutations. They have nothing in common except the group.

Every group at index two. The two-colourings of this site are built on an enumeration of index-two subgroups by closure, and that enumeration also reports which plane group each subgroup is. The permutation count agrees with it for all seventeen groups. Neither method was adjusted to make them agree: the closure enumeration was written to answer a question about colour and knows nothing about permutations.

How the counts grow #

Reading down the index-four column, the numbers are much larger and much less regular than the index-two ones: pmm has sixty-seven, p6m has five, p3 has four. That spread is not noise.

Four is the first composite index, so a subgroup of index four can arise by halving twice, and a group with many index-two subgroups has many ways to do it. pmm has fifteen subgroups of index two — the most of any plane group — and each of those has its own index-two subgroups, so the index-four count is large for the same reason the index-two count is.

The hexagonal groups go the other way. p3, p3m1, p31m and p6 each have exactly four subgroups of index four, all in one conjugacy class. Four is coprime to three, so the index has to be carried by the translations, and a hexagonal lattice’s sublattices of index four that keep the three-fold symmetry are few — the same argument that gave the zeros at index three for the four-fold groups, with the roles of three and four exchanged.

The arithmetic and the geometry are the same constraint seen twice, and the table is the shortest place on this site where that is visible in a single glance: every entry is a count of sublattices multiplied by a count of ways to place a point operation, and every zero is one of the two factors vanishing.

Conjugacy, and how many subgroups are really different #

A count of subgroups is not quite a count of kinds of subgroup, because conjugate subgroups are the same pattern placed differently.

Conjugating a subgroup corresponds to relabelling the points of its action, so the conjugacy classes are the orbits of Sₙ acting on the transitive homomorphisms by conjugating every generator’s image at once — which the enumeration computes directly.

The gap between the two counts is sometimes large. p2 has twelve subgroups of index three in four conjugacy classes; pmm has sixty-seven of index four in fifty-one classes. And at index two the two counts always agree, because an index-two subgroup is normal and a normal subgroup is its own conjugacy class.

Which of them are normal is the other column. A subgroup is normal exactly when its action’s image has order n — a transitive action whose image is no larger than the set it acts on is a regular one, and the stabiliser is then the kernel. For p2 at index three, none of the twelve is normal, which is a sharper statement than the conjugacy count and is what the four classes of three are recording.

What the round trip checked, and how #

A relator the group does not satisfy must reduce the count. Adding r² = 1 to p4 — false, since its rotation has order four — takes the number of homomorphisms to four points from 112 to 76. The first version of this test used three points and proved nothing: no element of S₃ has order four, so r² = 1 follows from r⁴ = 1 there and the extra relator is vacuous. A negative test on a set where the difference cannot appear is not a test, and this one had to be moved to four points to become one.

An intransitive action must be excluded. p2 has forty-six homomorphisms to S₃ and twenty-four transitive ones; the trivial homomorphism is among the twenty-two rejected, and if it were not the count would be wrong by an infinity.

The count must be a whole number. Every transitive count has to divide by (n − 1)! exactly, since each subgroup contributes that many labelled actions. A count that failed to would mean the correspondence had been misapplied.

And the two independent counts must agree, at p1 for every index and at index two for every group.

Who worked this out, and when #

The correspondence between subgroups and transitive actions is old and unattributed — it is the orbit–stabiliser theorem read one way — but turning it into an algorithm is twentieth-century computational group theory.

Todd and Coxeter published coset enumeration in 1936: given a presentation and a subgroup specified by generators, systematically fill in the table of cosets. It is used elsewhere in this collection to show that a plane group’s presentation has the right point group, and it answers the question this essay asks in reverse — it takes a subgroup and finds its index, rather than taking an index and finding the subgroups.

The low-index subgroup algorithm, due to Sims and others in the 1960s and 70s, does the forward direction properly: it searches over partially filled coset tables with backtracking, and reaches indices far past anything a brute-force search over Sₙ could. The method used here is the naive one, and it is used because at these indices it is complete, it is short enough to read, and being naive it shares no code with anything else on the site — which is what makes its agreement with the sublattice count meaningful rather than circular.

Reidemeister–Schreier rewriting is the third piece, and it is the one deliberately not used: given a subgroup as a coset table, it produces a presentation for that subgroup. It is what would turn the count of twelve into an identification of twelve, and it is a substantially larger piece of machinery.

Where the exactness stops #

The search is bounded by the size of Sₙ. At n = 5 there are 120 permutations and up to 120⁴ tuples, which is past what this runs comfortably; the real low-index subgroup algorithms search coset tables with backtracking and reach index twenty or more. Nothing here needs them, and the table stops at four rather than claiming a bound it does not have.

The method assumes the presentation is right. Everything counted here is counted in a finitely presented group, and if the presentation described a different group the counts would be counts of that group’s subgroups instead. This collection derives each presentation from the group’s own operations and checks it by coset enumeration, so the assumption is discharged elsewhere rather than here — but it is an assumption, and it is the reason the agreement with the sublattice count matters so much. That check compares an answer about permutations with an answer about integer matrices, and only the group they both describe could make them agree.

A count is not a classification. The enumeration says p2 has twelve subgroups of index three; it does not say what they are. Naming them would mean computing a presentation for each — Reidemeister–Schreier rewriting — which is a different piece of machinery, and the index-two enumeration by closure does name its subgroups precisely because it works with operations rather than with permutations. The two methods have opposite strengths.

The correspondence is exact and the arithmetic is not approximate anywhere, which is worth saying because almost every other count on this site is of geometric objects and this one is of nothing but symbols.

Where the ladder goes next #

The search above treats a group as letters with relations and never asks what a word means. The obvious next question is whether two words are the same element — which for a general finitely presented group is undecidable, and for these seventeen is not.

How fast the counts grow #

The table stops at index four, and the sequence it starts has a known character — one that separates these groups sharply from groups that look similar on paper.

The method here is Marshall Hall’s, published in 1949: count the homomorphisms into the symmetric group on $n$ letters, keep the transitive ones, divide by $(n-1)!$. It applies to any finitely presented group, and what it returns depends enormously on the presentation’s relations.

For a free group the counts explode. A free group on two generators has homomorphisms to $S_n$ given by any pair of permutations, so the number of them is $(n!)^2$, and the number of index-$n$ subgroups grows faster than $n!$. A free group has an enormous number of subgroups at every index.

For a plane group they grow polynomially. The relations cut the search down brutally: a rotation of order four must map to a permutation of order dividing four, two generators that commute must map to commuting permutations, and most candidate pairs fail. The number of index-$n$ subgroups of a plane group grows like a fixed power of $n$ rather than like a factorial.

The sublattices are the visible part of that. The subgroups of index $n$ inside the translations alone number $\sigma(n)$, the sum of the divisors — four at index three, seven at index four — which grows barely faster than $n$ itself. Everything else in the table is that count, multiplied by the finitely many ways the point operations can survive.

So the zeros are not anomalies in a wild sequence. They sit in a slow, arithmetic sequence whose entries are all small, and in a sequence like that an entry being zero is an ordinary event with a stateable reason — which is what the two arguments above supply.

What the tabulated subgroups are for #

Counting them is one question and knowing them is another, and the second is tabulated for every space group because a whole class of physical problems is a search through that list.

A phase transition is a group–subgroup relation. The high-symmetry phase has a group, the low-symmetry phase has a subgroup, and the index counts the domain states. Predicting which transitions a material can have means enumerating the subgroups of its group, at every index worth considering.

Which is why the relations are drawn as trees. A diagram with the parent at the top, its maximal subgroups below, theirs below that, and each edge labelled by its index and its kind is the standard way of laying out the possible descents — the whole path from a high-symmetry parent to an observed low-symmetry structure, factored into steps each of which is a maximal subgroup relation.

And a non-maximal subgroup is a path rather than an edge. The point this essay opens with — that closure finds only the maximal ones — is the reason such a diagram is worth drawing: every subgroup is reached, but as a chain, and the chain says which intermediate structures might exist between the two phases actually observed.