The only bit that survives

The sign of a permutation is a label — even or odd — that multiplies correctly: the sign of a composition is the product of the signs. It is the reason a sliding puzzle can be unsolvable and the reason a determinant can be written down at all.

The obvious next question is whether it is the only such label. Perhaps a finer one exists — a number out of three that also adds correctly under composition, or a residue out of four, carrying more information than a single bit and behaving just as well. It would be useful if one did.

None does, and this rung is the proof.

The question is not idle, and it has a practical form. A great deal of mathematics attaches numbers to permutations and then needs those numbers to behave when permutations are composed — determinants, orientations, signs in a Laplace expansion, the coefficient of a term in an alternating sum. If a richer well-behaved label existed, every one of those constructions would have a richer analogue. The theorem below says that none of them does, and that the poverty is a fact about the group rather than a failure to look.

What a well-behaved label is #

Make the question precise. A label is a function $\varphi$ from permutations to some commutative group, satisfying $\varphi(\sigma\tau) = \varphi(\sigma) + \varphi(\tau)$ — a homomorphism. The sign is one, with target the two-element group. The constant label sending everything to zero is another, and a trivial one.

The question is whether there are others: a homomorphism onto the three-element group, say, which would divide the permutations into three classes closed under composition in the way the even and odd ones are closed.

The answer has a mechanism, and the mechanism is the reason the answer is the same for every $n$ and for every target at once.

For any $\sigma$ and $\tau$, the commutator $\sigma\tau\sigma^{-1}\tau^{-1}$ has label $\varphi(\sigma) + \varphi(\tau) - \varphi(\sigma) - \varphi(\tau) = 0$, because the target is commutative and the terms cancel. So every label kills every commutator, whatever the label is. It therefore kills the whole subgroup the commutators generate, and is really a label on the group divided by that subgroup.

That reduces the question from “which labels exist” to “what is the subgroup generated by commutators” — a single object, computed once, that answers the question for every target.

It is worth noticing how strong that reduction is. There are infinitely many commutative groups to test, and infinitely many candidate functions into each. The commutator subgroup replaces all of it with one computation on one finite group, done once — and everything the question could have asked is then read off a single number, the size of the quotient. A uniqueness theorem of this kind is nearly always a computation of a quotient wearing a disguise.

The subgroup, computed #

The figure computes it by exhaustion: all $576$ commutators of the twenty-four permutations of four places, then the closure of that set under composition. The answer is twelve elements, and they are precisely the even permutations.

So the quotient has two elements, and every label whatever factors through a two-element group. The sign is not merely one label among many; it is the universal one, and every other is obtained from it by composing with something. A homomorphism to the three-element group must send the two-element quotient somewhere, and the only homomorphism from a group of order two to a group of order three is the trivial one, because two does not divide three.

The second half of each figure is a genuinely separate calculation and it is worth saying why it was worth doing. The argument above derives the answer from the commutator subgroup; the bars derive it by brute force, trying every possible assignment of values to the adjacent swaps and extending each one over the whole group, rejecting any that produces a clash. For four places and the cyclic group of order four that is sixty-four candidate assignments, of which two survive. The two routes agree, and the second route makes no use of the first.

Counting the labels into every target #

Once the quotient is known, the count of labels into any commutative group $A$ follows without further work, and it is worth doing because the answer is not always two.

A label is a homomorphism from the two-element quotient into $A$, and such a homomorphism is determined by where the non-identity element goes: to any element of $A$ whose double is the identity. So the number of labels is the number of elements of $A$ satisfying $2a = 0$, including the identity itself.

For the cyclic group of order $m$ that count is two when $m$ is even and one when $m$ is odd, which is exactly what the bars in the figures show. For the group of four elements in which everything doubles to zero, the count is four — three non-trivial labels and the trivial one.

That last case is worth not misreading. Four labels exist, and all four are the sign followed by a choice of where to send it; none of them separates two permutations of the same parity. The sign is still the only information available, and a larger target merely offers more names for it. The uniqueness is a statement about what a label can distinguish, not about how many labels can be written down.

Why the sign is a function of the shape #

There is a second way to see that the sign is forced, and it goes through conjugation rather than through commutators.

Conjugating $\sigma$ by $\gamma$ produces a permutation with the same cycle shape, relabelled. So the classes are exactly the cycle shapes, and there are as many of them as there are ways of writing $n$ as a sum of positive whole numbers — five for four places, seven for five.

Any label that multiplies correctly is constant on conjugacy classes, since $\varphi(\gamma\sigma\gamma^{-1}) = \varphi(\gamma) + \varphi(\sigma) - \varphi(\gamma) = \varphi(\sigma)$. So a label is really a function of the cycle shape. And the shapes compose in a way that forces the label: a transposition and a three-cycle multiply to something whose shape is determined, and following the constraints through leaves the sign as the only non-trivial solution.

The exact halving is worth one more sentence, because it is the shape of the quotient made visible. A subgroup of index two is what a two-element quotient means, and the pairing that establishes it — compose with a single transposition — is a bijection between the two halves. Nothing similar could pair the group into three parts, because no such bijection exists to build: composing with a fixed element can only produce a pairing, never a tripling.

Following the constraints through is short enough to do here, on four places. A label is constant on the five classes, so it is five numbers. The identity’s number is zero, since $\varphi(\iota) = \varphi(\iota) + \varphi(\iota)$. A three-cycle is the square of a three-cycle, so its number is twice something and also, since a three-cycle cubed is the identity, three times it is zero — so six times it is zero two ways, and in a group where the only constraint is what the composition forces, it must be zero. A double transposition is a product of two transpositions, so its number is twice a transposition’s. And a four-cycle is a transposition times a three-cycle, so its number is the transposition’s. That leaves one free choice — the transposition’s number $t$, with $2t = 0$ — and the label is determined by it.

The two routes — commutators and conjugacy classes — are related but not the same. Conjugation-invariance says a label is a function of the shape, which cuts the possibilities from $n!$ values to a handful. Killing commutators says which function, and there is only one non-trivial candidate.

One more reading of the class table, because it makes the composition constraint concrete. The class of double transpositions on four places has three members, and those three together with the identity are closed under composition — each is its own inverse, and any two of them compose to the third. So they are a group of four elements inside the twenty-four, and every element of it is even. A label constant on classes gives all three the same value $v$, and composing two of them gives the third, so $v + v = v$ and therefore $v = 0$. The label cannot see them at all, whatever it is.

The exception at four places, which is not an exception here #

Four places has a genuine peculiarity, and it is a good test of what the theorem says.

The even permutations of four places contain a normal subgroup of order four — the identity and the three double transpositions, visible in the table above as the class of size three plus the identity. So $A_4$ is not simple, and the permutations of four places have more normal subgroups than the pattern for larger $n$ would suggest.

That extra subgroup produces a quotient of order six, and the quotient is the permutations of three places, which is not commutative. So it supplies no new label. A homomorphism to a commutative group must still kill every commutator, and the commutator subgroup of the permutations of four places is all twelve even ones — as the figure computed — not the four-element subgroup.

A normal subgroup is not the same thing as an abelian quotient, and this is the smallest case where the difference is visible. The count of normal subgroups depends on $n$ in a complicated way; the count of homomorphisms to commutative groups does not depend on $n$ at all.

What the one bit is used for #

The uniqueness makes several familiar facts sharper than they look.

The general shape is this: whenever a construction sums over permutations with coefficients, and the construction is required to behave under composition, the coefficients are forced to be the sign. That is why alternating objects are everywhere — the antisymmetric part of a tensor, the determinant, the Pfaffian, the orientation of a simplex, the sign conventions in a wedge product — and why they all agree with one another. They are not a family of related conventions. They are one label, appearing wherever composition has to be respected.

The determinant is a sum over permutations with signs attached. Any other consistent scheme of coefficients would need a different multiplicative label, and there is none — so the alternating determinant is the only determinant-like function there can be, up to scaling.

The Legendre symbol read as the sign of a shuffle uses the same fact: multiplication by a fixed residue permutes the residues, and the sign of that permutation is the symbol. The symbol takes two values because the sign does, and not because two was convenient.

The resultant of two polynomials is another sum over permutations of a matrix’s entries, and it inherits the same signs for the same reason — it is a determinant, of a matrix built from the coefficients, and there was never a choice about the alternating pattern in it.

And the sliding puzzle’s unsolvable positions are unsolvable because a single bit is conserved. If a three-valued invariant existed, there would be positions unreachable for a finer reason, and the reachable set would be a third of the arrangements rather than half. It is exactly half, in every dimension of board, and the theorem here says it could not have been anything else.

One consequence is worth stating because it is a genuine limitation rather than an application. Since the only multiplicative label is a bit, no numerical invariant of permutations can measure “how far” a permutation is from the identity in a way that adds under composition. The number of inversions is a perfectly good measure of disorder and it does not add; the number of transpositions needed does not add either, only its parity does. So there is no additive complexity measure on shuffles, and anybody who wants one has to leave the group — which is exactly what the symmetry groups of shapes do when they attach lengths to generators and count them in a fixed generating set, at the cost of the answer depending on the generators chosen.

Where a whole number survives instead #

The situation is not universal, and the most instructive comparison is with a group that looks almost the same and is not.

A braid on $n$ strands is a permutation with the crossings remembered: which strand passed in front at each crossing, in what order. Forgetting that extra information gives a permutation, so braids map onto permutations.

Braids have a label that permutations do not: the sum of the crossing signs, an ordinary whole number that adds under composition. Its target is the integers, which are commutative, so by the argument above it must kill every braid commutator — and it does. The braid group’s commutator subgroup is smaller than its analogue among permutations, which leaves an infinite quotient rather than a two-element one.

The bit that permutations retain is what is left of the braid’s whole number after the crossings are forgotten. Reading the two together says what the sign is: not an arbitrary invariant that happens to work, but the shadow of a counting quantity, reduced modulo two by the act of forgetting which strand went over.

The comparison also shows what “forgetting” costs in general. Braids form an infinite group and permutations a finite one, and the map between them loses exactly the information that made the whole number possible. What survives a quotient is never more than what the quotient’s own commutators allow, and the exercise of computing that subgroup — which is what this rung is — is how anybody knows in advance how much can survive.

What this rung does not settle #

It says nothing about labels into non-commutative targets. A homomorphism from the permutations of four places onto the permutations of three exists — the quotient by the four-element subgroup — so there are non-trivial maps out of these groups; they simply do not produce numerical invariants that multiply, because their targets do not commute.

It says nothing about which subgroups are normal, which is a separate and much more delicate question — and the answer that matters most, that the even permutations of five or more places have none, belongs to a different ladder and is what makes the quintic unsolvable.

And it says nothing about why one would want more than a bit. The honest answer is that people repeatedly have: there is no shortage of proposed finer invariants of shuffles in the literature of recreational mathematics, and every one of them either fails to compose or turns out to be the sign with extra decoration.

There is one further limit worth stating, because it is the most common source of confusion about the sign. The theorem is about labels that respect composition. Plenty of useful functions on permutations respect nothing of the kind and are perfectly well defined — the number of inversions, the number of fixed points, the length of the longest cycle, the orbit counts a group action produces. Each of them distinguishes permutations the sign cannot. None of them multiplies, which is why none of them can play the sign’s role in a determinant or in a solvability argument, and why the uniqueness theorem coexists with an unlimited supply of other invariants.

Which is what a uniqueness theorem is for. The rung below shows the sign exists and is well defined, which stops one class of error. This one shows it is alone, which stops the other — the search for something better, in a place where nothing better can be.

It also says nothing about the groups this one sits inside. The symmetries of a square are eight of the twenty-four permutations of its corners, and asking which labels survive on a subgroup is a different question with different answers — a subgroup can have abelian quotients its parent does not, which is why the chain of subgroups a solvable group has is built out of exactly these quotients one level at a time.