The blocks a subgroup cuts out

The eight symmetries of a square are found by testing every relabelling of its corners and keeping the ones that move no distance. Among those eight there are smaller collections that are closed on their own: perform two of them one after another and the result is back in the collection. The four turns are such a collection. So are the identity and the half turn, on their own.

Any such collection is a subgroup, and a subgroup does something to the group it sits inside that no amount of staring at a list of eight motions suggests.

Four blocks of two. The arithmetic in the caption is the whole of Lagrange’s theorem, and it holds for every subgroup of every finite group: the size of a subgroup divides the size of the group, because the subgroup cuts the group into blocks of its own size.

Where the blocks come from #

The construction is one line. Take the subgroup H, take any element g of the group, and form the collection of everything of the form g composed with a member of H. That collection is written gH and is called a left coset.

Two facts about it settle everything.

Every block is the size of H. Composing with g on the front is reversible — compose with g’s inverse to undo it — so different members of H give different members of gH. The block cannot be smaller, and it plainly cannot be bigger.

Two blocks that share anything are the same block. Suppose x lies in both gH and kH. Then x is gh and also kh′ for members h and h′ of H, so g is kh′h⁻¹, and every element gh″ of the first block equals k times something in H, which is a member of the second. The argument runs the other way too, so the two blocks are equal.

Blocks that are equal or disjoint, all of one size, and covering everything, because every element g lies in its own block gH. So the group is partitioned into blocks of size |H|, and the number of them — the index — multiplied by |H| gives the size of the group.

That is a counting argument of the same shape as several on this site: a set is counted twice, once as itself and once as a union of equal parts, and the identity falls out.

What it forbids #

Lagrange’s theorem is a restriction, and restrictions are more useful than they sound.

A group of eight elements cannot have a subgroup of three. A group with a prime number of elements has no subgroups at all except the trivial one and the whole thing — and since the collection of all powers of any element is a subgroup, every non-identity element must generate the entire group, so every group of prime size is a cycle. That is a complete classification of infinitely many groups, obtained from a counting argument in two lines.

The same restriction is what makes the order of an element meaningful. Compose a motion with itself repeatedly and it eventually returns to the identity; the number of steps is the size of the subgroup it generates, so it divides the size of the group. On the square, no motion has order three, and none ever will.

That last observation is the reason the argument feels like arithmetic on a group and not like geometry. The claim no symmetry of a square has order three refers to nothing about squares. It follows from eight having no factor of three, and it would apply equally to the symmetries of any object with eight of them. The same reasoning says that the group of a finite field’s non-zero elements has an element of every order dividing its size, and there the conclusion is about polynomials rather than about shapes.

Blocks that can be multiplied #

Having cut a group into blocks, the natural next move is to treat the blocks as objects in their own right and ask whether they can be composed. Take a block, take another, multiply a member of the first by a member of the second, and see which block the answer lands in.

The obvious worry is whether the answer depends on which members were picked. Sometimes it does not, and then the blocks form a group of their own.

The condition is exactly that the left blocks and the right blocks agree: gH and Hg must be the same collection for every g. A subgroup with that property is called normal, and the group of blocks is the quotient.

For the identity-and-half-turn subgroup of the square’s symmetries, the four blocks form a group in which every element is its own inverse. For the identity-and-one-reflection subgroup, the blocks are perfectly good blocks — four of them, two elements each, obeying Lagrange exactly as before — and they cannot be multiplied at all. The figure names the witness: composing on one side gives one block and on the other side gives a different one.

This is the first place in elementary group theory where a construction that looks automatic turns out to need a hypothesis, and the hypothesis is not decorative. Without normality the blocks are a partition and nothing more.

It is worth seeing why the failure has to be checked rather than felt. Both subgroups have two elements; both cut the group into four blocks; both satisfy Lagrange’s arithmetic exactly. Nothing about the sizes distinguishes them, and nothing about the drawing does either — four blocks of two look the same whichever subgroup produced them. The difference lives entirely in whether a particular pair of collections coincide, which is a question a reader can answer only by composing on both sides and comparing. The figure does that for all eight elements and reports the first element where the two disagree.

The oldest example, which is a clock #

Whole numbers under addition have a subgroup for every n: the multiples of n. Its blocks are the remainders, and there are exactly n of them.

Everything in the general theory is visible here in its simplest form. The blocks have equal size — infinitely many members each, which is why Lagrange’s counting version needs finiteness — and they can be multiplied, because addition of whole numbers does not care about order, so left and right blocks are trivially the same. Arithmetic modulo n is the quotient group, and it was in use for centuries before anybody described it that way.

The description earns its keep the moment a group is not commutative. On the square’s symmetries there is no way to guess from experience which subgroups will produce a working arithmetic, and the left-equals-right condition decides it.

It also explains a coincidence that looks like one until it is named. Two dials running at once — remainders modulo 3 and modulo 4 together — reproduce the remainders modulo 12 exactly, which is the Chinese remainder theorem drawn as a grid. In the language here, that is a statement that one quotient splits into two, and the condition for it is that the two subgroups meet only at zero and together generate everything. Written as a fact about clocks it is a curiosity; written as a fact about quotients it is the first case of a structure theorem.

What the blocks are for #

Two uses, and both are about replacing a hard question with an easier one.

Counting. Burnside’s average counts the arrangements a group cannot tell apart by averaging how many each motion fixes. The argument underneath it is a coset argument: the collection of motions fixing a given arrangement is a subgroup, its blocks correspond to the arrangements in the same class, and so the class size is the index. Orbits and stabilisers are cosets in different clothing.

Building. A quotient group is a smaller group that remembers only some of the structure, and the standard way to understand a complicated group is to find a normal subgroup, understand the quotient, and understand the subgroup — then ask how the two fit together. That is how the classification of finite simple groups came to be the central problem of the subject: a simple group is one with no normal subgroups to quotient by, so simple groups are the pieces from which every other finite group is assembled.

The same blocks, in two other subjects #

The construction is so plain that it turns up wherever a group is present at all, and two of its appearances on this site were made without the word being used.

Fermat’s little theorem is proved by threading beads onto a loop and noticing that the rotations sort the strings into groups of the same size. That is a coset argument on the rotation group: the strings that a rotation fixes form a subgroup’s worth of exceptions, everything else falls into blocks of size p, and the divisibility that the theorem asserts is the index arithmetic.

Syndrome decoding is the same idea in a different costume. A linear code is a subgroup of all possible words, its cosets are the sets of words differing by a codeword, and the syndrome of a received word is precisely a name for which coset it lies in. Correcting an error means picking the lightest member of that block. A decoder is a machine for reading off coset labels, and the reason it works at all is the two facts on this page: the blocks are the same size and they do not overlap.

The lesson is the standard one about abstraction and worth restating. Nobody set out to invent cosets in order to decode a message or count necklaces. The structure was there in both, unnamed and re-derived each time, and naming it turned two arguments into one.

What it costs #

Finding every subgroup of a group of n elements by the method the figure uses means testing every one of 2ⁿ subsets for closure, which is fine at eight and hopeless at fifty. The figure’s search over the square’s 256 subsets is small enough to be redone every time the picture is drawn, and it is worth doing that way rather than listing the ten by hand, because a hand-written list is a claim about the group rather than a measurement of it.

Better methods exist and they are what a computer algebra system does: build subgroups from generators, use the divisors of the group’s size to know which sizes to look for, and use Sylow’s theorems, which say a great deal more about subgroup sizes than Lagrange does. Lagrange says the size divides; Sylow says that for each prime power dividing the order, a subgroup of exactly that size exists — a converse that is false in general and true for prime powers.

The general converse is false, and the standard counterexample is a group of twelve elements with no subgroup of six. So the theorem is a one-way street: divisibility is necessary and not sufficient, which is the kind of gap that keeps a subject alive.

What the picture cannot show #

The blocks in these figures are drawn for one group of eight elements, and the theorem is about every finite group. Nothing in a drawing of eight motions establishes anything about a group of a million, and the argument that does is the two-line one above about reversibility and overlap.

The figures also show only left cosets, except in the panel where the distinction matters. For a commutative group the two are the same and the distinction is invisible; for the square’s symmetries it is the whole point, and drawing both would double every picture to make one panel’s point.

And there is a whole level the pictures pass over. A quotient group’s elements are sets, not motions, and no drawing of the square shows what it means to compose two sets. The table in the quotient figure is a table of names, and the arithmetic behind each entry is the check that the name does not depend on the representative — which is exactly what cannot be drawn and exactly what has to be verified.

The ladder from here #

Rungs above: Lagrange’s theorem proved for infinite groups, where the index survives and the counting does not. Normal subgroups characterised as kernels of homomorphisms, which is the definition that makes normality look inevitable rather than technical. The isomorphism theorems, which say what a quotient of a quotient is. Sylow’s three theorems and the constraints they put on group structure. Group actions, orbits and stabilisers as one theorem rather than three. Simple groups, and the century-long classification. And the same construction in other subjects: quotient spaces in topology, where a surface is a polygon with edges identified, and quotient rings, where modular arithmetic is done with polynomials instead of numbers.

The shape of the idea #

A partition is the plainest structure in mathematics: split a set into pieces so that everything is in exactly one piece. What makes cosets worth a name is that the pieces are all the same size and that the splitting was produced by a single small object rather than chosen.

Lagrange’s theorem then costs nothing. It is not a fact discovered about groups so much as a fact about partitions, applied to a partition that groups happen to produce for free. That pattern — arrange the argument so that the theorem becomes arithmetic — is what the whole of this site is about, and it is rarely as clean as it is here.

The sting is in the second half. Having cut the group into equal blocks, it is entirely natural to expect the blocks to behave like a group themselves, and for half the subgroups of the square they do not. The construction that looks automatic has a condition on it, the condition is checkable, and the figure that shows it failing is more informative than the one that shows it working.