Sixteen of five hundred and seventy-six

Every previous rung of this ladder put a Latin square next to something — another square, a plane, a count. This one takes the square on its own and asks what kind of object it already is.

Read the row label as a left operand, the column label as a right operand, and the entry as their product. Any square then defines a multiplication on its symbols, and the Latin condition says something exact about that multiplication: because each symbol appears once in row $a$, the equation $a \cdot x = b$ has exactly one solution; because each appears once in column $a$, so does $y \cdot a = b$. A set with a multiplication in which those two equations are always uniquely solvable is a quasigroup, and a Latin square is precisely a finite quasigroup’s table.

That is a complete dictionary, and it prompts the obvious question. The group axioms are unique solvability plus associativity. So how many of the tables associate?

Sixteen #

The count is sixteen, and it can be arrived at twice — which is what makes it worth trusting.

The figure gets it by exhaustion. All $576$ squares of order four are generated, each is checked against $4^3 = 64$ triples $a(bc) = (ab)c$, and the survivors are counted. Nothing about groups goes into that computation; it is a filter applied to a list.

The second route is by counting labellings. There are two groups of order four up to isomorphism — the cyclic group and the Klein four-group — and a table is a group with its elements named. The number of ways to name the elements of a group of order $n$ is $n!$, but namings that differ by an automorphism give the same table, so the number of tables is $n!$ divided by the size of the automorphism group. The cyclic group of order four has two automorphisms and the Klein group has six, so

$$\frac{24}{2} + \frac{24}{6} = 12 + 4 = 16.$$

The two numbers agree, and the split agrees as well: the exhaustive search finds twelve tables with an element of order four and four in which everything is its own inverse. This is the orbit-counting habit applied to tables rather than to colourings, and it is the reason a count of labelled objects nearly always has a factorial over a symmetry in it.

Associativity is not a small extra condition #

Sixteen out of five hundred and seventy-six is one in thirty-six. At order three it is three out of twelve, one in four. At order five there is one group, with four automorphisms, so there are $120 / 4 = 30$ group tables against $161{,}280$ squares — one in five thousand three hundred and seventy-six.

The collapse continues and accelerates. The number of Latin squares grows like $(n/e^2)^{n^2}$; the number of labelled group tables is at most $n!$ times the number of groups of order $n$, which is minute by comparison. So among quasigroups, groups are vanishingly rare — and the fact that essentially every multiplication table anybody meets in ordinary mathematics is associative says something about which structures get names, not about which are common.

That inversion is the point of counting at all. Associativity is usually presented as the mild axiom, the one nobody bothers to check, with commutativity the interesting one that fails for matrices. The count says the opposite: unique solvability is the cheap condition and associativity is the expensive one, and asking a random table for it is asking for a coincidence.

There is a fair objection to that framing, and it is worth answering rather than ignoring. Counting labelled tables weights every square equally, and nobody meets multiplication tables by drawing them uniformly at random; the operations that occur in practice arrive with a reason attached, and the reason usually supplies associativity — composing functions is associative because composition of anything is, and most operations are secretly compositions. So the rarity above is a fact about the space of tables rather than about mathematical life. What it does establish is that associativity carries real information: a condition satisfied by one table in thirty-six at order four, and one in five thousand at order five, is not a formality, and the theorems that use it are using something.

The identity nobody put in #

Something is missing from the account above, and its absence is a small theorem.

The group axioms are usually given as associativity, an identity element and inverses. The tests in the figure asked only for associativity, on top of the Latin condition — no identity was required and none was assumed. Yet every one of the sixteen surviving tables has one, and the figure asserts it rather than hoping for it.

The reason is short. In a quasigroup, pick any element $a$ and let $e$ be the unique solution of $a \cdot e = a$. For any other $b$, unique solvability gives a $c$ with $c \cdot a = b$, and then

$$b \cdot e = (c \cdot a) \cdot e = c \cdot (a \cdot e) = c \cdot a = b,$$

where the middle step is the only place associativity is used. So $e$ is a right identity for everything, and the mirror argument gives a left identity, and the two must coincide. Inverses then follow from solvability: the $x$ with $a \cdot x = e$ is an inverse.

So an associative quasigroup is a group, with no further axioms — which means the sixteen tables were not selected by a definition with three clauses. They were selected by one clause, and the other two arrived by themselves.

The argument is worth reading twice, because it fails the moment the set is infinite in the wrong way. Unique solvability is what produced $e$, and unique solvability is exactly what a Latin square encodes; drop it and keep associativity and the result is a semigroup, where identities and inverses genuinely have to be demanded. The finite case has a second route to the same place — in a finite semigroup with cancellation, the map $x \mapsto a \cdot x$ is injective and therefore surjective, which is where the solvability comes back from — and that route is a pigeonhole argument rather than an algebraic one. Two proofs, one from the square’s shape and one from the finiteness, and the square’s shape is the one that says why the table is the right object to look at.

The rows, read as permutations #

There is a way of looking at a Latin square that makes the rarity of groups structural rather than statistical, and it costs nothing to set up.

Each row of a square is a permutation of the symbols — that is the Latin condition — and no two rows agree in any column, since a column also holds each symbol once. So a Latin square of order $n$ is a set of $n$ permutations, any two of which disagree everywhere: a sharply transitive set. Nothing has been added; the square has simply been read a row at a time.

Now ask what associativity says in that language. Row $a$ of a group’s table is the map $x \mapsto a \cdot x$, and composing two such maps gives $x \mapsto a\cdot(b \cdot x)$, which associativity turns into $x \mapsto (a\cdot b)\cdot x$ — row $ab$. So

a group table is a Latin square whose rows are closed under composition.

That is the whole difference. A general square is a set of $n$ permutations sitting inside the $n!$ available with no relation to each other; a group table is a set that happens to be a subgroup of the symmetric group, acting so that exactly one member sends any given symbol to any other. Composing two rows of an arbitrary square produces a permutation, and there is no reason for it to be one of the rows — five hundred and sixty of the order-four squares are exactly the cases where it is not.

Read that way the count stops being surprising. Choosing a group table means choosing a subgroup of $S_4$ of order four acting sharply transitively, and there are very few subgroups of anything; choosing a Latin square means choosing any set of mutually disagreeing permutations, and there are enormously many. The gap between “closed under an operation” and “merely a set” is the gap the count of sixteen against five hundred and seventy-six is measuring.

The same reading is Cayley’s theorem. Every finite group is isomorphic to a group of permutations — namely its own rows — so the table is not a representation of the group chosen for convenience; it is the group, acting on itself, written down. That is why the table determines everything and why an isomorphism of groups is a relabelling of a table.

It also explains why counting Latin squares is so much harder than counting groups. The totals are $1$, $2$, $12$, $576$, $161{,}280$, $812{,}851{,}200$ and then a number in the tens of trillions, and the sequence is known only to order eleven — every value past the smallest was obtained by a computation designed for that order alone. A set with no closure condition has no structure to count by, and the exhaustive search on this page is feasible at order four for the same reason the enumeration stops shortly afterwards.

Which of them has an orthogonal mate #

This ladder began with orthogonality, and the tables turn out to answer a question from that end too.

A square has an orthogonal mate only if it can be cut into transversals — one cell per row and column, all symbols different — since a mate’s symbol classes are exactly such a cutting. For a group’s table, a transversal is a bijection $\sigma$ making $i \mapsto i \cdot \sigma(i)$ a bijection as well: a complete mapping of the group. And whether a group has one is a question with a clean answer.

Hall and Paige conjectured in 1955 that a finite group has a complete mapping exactly when its Sylow 2-subgroup is trivial or is not cyclic. Order four is the smallest case where both possibilities occur: the cyclic group of order four is its own Sylow 2-subgroup and is cyclic, so it should fail; the Klein group is its own Sylow 2-subgroup and is not cyclic, so it should succeed. The exhaustion above finds exactly that, over twenty-four placements against sixteen tables.

The general statement was not proved until 2009, by Wilcox, Evans and Bray, and the proof runs through the classification of finite simple groups — a fifty-year gap between a conjecture that can be checked by hand at order four and a proof that needs the deepest theorem in the subject.

It also settles a case this ladder met at the very beginning. The cyclic square of order six has no transversal, which the first rung established by walking all $720$ placements. The cyclic group of order six has a cyclic Sylow 2-subgroup, so Hall–Paige says it cannot have one — and the exhaustion that opened this ladder is a single instance of a theorem that took half a century.

The tables that come from designs #

Groups are not the only quasigroups with a reason to exist, and the clearest example is one this collection has already built for a different purpose.

Take a schedule in which every pair of players meets exactly once — a Steiner triple system, a set of triples on $v$ points such that each pair lies in exactly one triple. Define a multiplication on the points: $a \cdot a = a$, and for $a \neq b$, let $a \cdot b$ be the third point of the unique triple containing $a$ and $b$. That is a quasigroup. Every row is a permutation, because for fixed $a$ the map $b \mapsto a \cdot b$ is its own inverse and therefore a bijection, and the table is a Latin square.

It is commutative, since the triple containing $a$ and $b$ does not care about the order, and idempotent, since every element squares to itself — which puts the symbols down the main diagonal, a shape no group table has except the trivial one. It is not associative: $(a \cdot b) \cdot b = a$ while $a \cdot (b \cdot b) = a \cdot b$, and those differ whenever $a \neq b$.

So the design and the quasigroup are one object described twice, in the same way that a complete family of squares and a plane were. The triple systems exist exactly when $v$ leaves a remainder of $1$ or $3$ on division by six, and that arithmetic condition — proved by counting pairs against triples — is simultaneously a statement about which orders carry a commutative idempotent quasigroup.

This is the general shape of the subject once orthogonality is set aside. A quasigroup with an extra condition imposed on it is a combinatorial design with a different name, and which orders admit one is an arithmetic question with an answer that has nothing to do with multiplication. Groups are the case where the extra condition is associativity; there are many others, and each picks out its own thin subset of the enormous list of tables.

Isotopy, and what it does not disguise #

Three operations leave the essential content of a table alone: permuting the rows, permuting the columns, and renaming the symbols. Applying different permutations to the three is an isotopy, and it is a weaker relation than isomorphism, because an isomorphism has to apply the same renaming everywhere.

At order four there are only two isotopy classes among the $576$ squares, and each contains one of the two groups. So every Latin square of order four is an isotope of a group — including the five hundred and sixty that fail associativity. Isotopy genuinely loses information: it can carry a group table to a table with no identity and no associativity at all.

What it cannot do is disguise a group as a different group. Albert’s theorem says that a quasigroup with an identity element that is isotopic to a group is isomorphic to that group, so among tables with an identity, isotopy and isomorphism agree. The looseness is entirely in the tables without one.

At order five the two isotopy classes behave differently: one contains the cyclic group’s table and the other contains no group at all. That is the first order at which a Latin square exists that is not a disguised group, which is a surprisingly late first appearance for an object there are eventually so many of.

What the exhaustion cannot show #

Every count on this page is an order-four count, or an order-three one. The list of $576$ squares is complete and the test on $64$ triples per square is complete, so the sixteen is exact — and it is exact about one order.

The claims that are not about one order are quoted rather than drawn: that associativity gets rarer, that the isotopy classes at order five behave as described, that Hall and Paige’s criterion holds for every finite group. The first is an asymptotic statement about two growth rates, the last is a theorem whose proof does not fit in any collection of pictures, and neither has a figure here that could be mistaken for evidence.

The other limitation is one the figure makes visible on purpose. A failing table fails at a triple, and the picture marks one. It cannot mark all of them, and there is no useful sense in which the number of failing triples measures how far from a group a quasigroup is — some tables fail almost everywhere and some fail at a handful of places, and neither is closer to being a group than the other, because being a group is not a matter of degree.

Where this anchor stands #

Five rungs, and the object has been four different things: an arrangement puzzle, a family built by a field, a geometry, a thing to be counted, and a multiplication table. None of those is a restatement of another, and the ladder ends where it does because the next questions belong to other collections — the cost of deciding whether a partial square completes, and the algebra of loops and Moufang systems, which is a subject rather than a rung.

Two questions this ladder raised and did not settle are worth naming. The first is order twelve: whether a plane of that order exists is the oldest open case, and no method anybody has works there. The second is smaller and sharper: the minimum number of entries that determine a square uniquely — a critical set — which is the question a Sudoku puzzle is a special case of, and which is unsolved even for small orders. Both are about squares that are nearly determined, which is the space between the free extension of a rectangle and the rigidity of a complete family.