The best of thirty-four thousand scramblings

A check digit over ten symbols has to give up commutativity to catch every single wrong digit and every swap of neighbours. Jacobus Verhoeff’s scheme of 1969 does it by multiplying the digits in the group of the ten symmetries of a regular pentagon — five turns, five flips — after passing the digit in each position through a fixed scrambling permutation, once for the first position, twice for the second, and so on. Not every scrambling works: it must never let $x \cdot \sigma(y)$ equal $y \cdot \sigma(x)$ for two different symbols. Of the $3{,}628{,}800$ permutations of ten symbols, $34{,}040$ pass that test.

That count ended the comparison of check-digit schemes with a question: the permutation Verhoeff published is one of 34,040 that would serve, and what made him choose it is not something the swap condition can say. This essay answers by grading every one of them on the errors that are rarer than single digits and swaps but still made — and the answer is that he chose one of the best.

The rarer errors, made exact #

Verhoeff’s study of thousands of hand-copied numbers found that single wrong digits and swapped neighbours are most errors. The rest are a scatter of kinds, and four of them can be checked exactly:

• a twin error, a doubled digit replaced by another doubled digit: 22 written as 77;
• a jump transposition, two digits swapped across a third: 427 written as 724;
• a jump twin, the two outer digits of a triple both changed alike: 272 written as 979;
• a phonetic slip, thirteen heard as thirty: “1a” written as “a0”.

Each of these kinds is rare — in Verhoeff’s tallies, around one per cent of errors or less apiece — but together they are a few per cent of everything people get wrong, and a check digit that misses one of them in twenty lets a steady trickle of wrong numbers through. In the language of distances between words, a single wrong digit moves a number one step, and every one of these errors moves it two; a check digit cannot guarantee to notice every two-step move, because one extra symbol can separate a word from its neighbours at distance one but not at distance two. The best a code can be is limited by exactly this counting, and the census measures how close one symbol can come to doing a second symbol’s work for the particular two-step moves that people make.

Because the scrambling in each position is a power of one permutation, and each power is a rearrangement of the ten symbols, the first three are caught or missed in the same proportion in every position. A twin error is caught exactly when $x \cdot \sigma(x) \neq y \cdot \sigma(y)$; a jump transposition, when $x z \sigma^2(y) \neq y z \sigma^2(x)$ for every middle symbol $z$; a jump twin, when $x z \sigma^2(x) \neq y z \sigma^2(y)$. Counting over all pairs, and all middles, gives a score out of 90, 900 and 900. The phonetic slip involves the specific digits 0 and 1 and does depend on position, so it is averaged over a full cycle of the permutation.

What a scrambling has to do #

The scheme works like this. Write the number’s digits as symmetries of the pentagon, pass the digit in position $i$ through the scrambling $i$ times, and multiply the results in order; choose the check digit so that the whole product is the identity. A single wrong digit changes exactly one factor and so changes the product, whatever the scrambling — any group catches single errors. A swap of neighbours is where the scrambling earns its place. Swapping digits $a$ and $b$ in positions $i$ and $i + 1$ changes the product only if $\sigma^i(a)\,\sigma^{i+1}(b)$ differs from $\sigma^i(b)\,\sigma^{i+1}(a)$, and with $x = \sigma^i(a)$ and $y = \sigma^i(b)$ that is the condition $x\sigma(y) \neq y\sigma(x)$. In a commutative group with no scrambling the two sides would be equal for every pair, and every swap would slip through; that is the whole reason ten symbols need a symmetry that does not commute.

The rarer errors put further conditions on the same permutation, and the conditions pull in different directions. A twin error asks about $x\sigma(x)$, a jump transposition about $\sigma^2$, a phonetic slip about particular powers acting on particular digits. One permutation has to serve them all, and the census is simply the most direct way to see how well that can be done: list every candidate and score it.

Detection is all a single check digit can do. It cannot say which digit is wrong, let alone correct it; that needs several check symbols arranged so that their pattern points to the error, which is where the codes of this subject begin. A check digit is the smallest possible code — one redundant symbol — and the question here is how much one symbol can be made to notice.

Thirty-four thousand points #

The scramblings fall into a small number of classes by these scores — the twin scores take only six values, from 50 to 86 — and the plot is sparse at the top. The corner is empty: no scrambling catches every twin error, and none catches every jump transposition. The best on twins catch 86 of 90; the best on jump swaps catch 848 of 900; and the two bests can be had together. Verhoeff’s permutation sits on that corner.

That is not luck in the weak sense. Only 6,000 of the 34,040 reach 86 on twins, only 200 reach 848 on jump swaps, and only forty reach both and the best score on jump twins as well. A scrambling chosen at random from the swap-proof ones has about one chance in eight hundred of landing there.

Why no scrambling catches every twin #

The empty corner is not a limit of the search. It is a theorem.

To catch every twin error, the ten products $x \cdot \sigma(x)$ would all have to be different — the map $x \mapsto x \sigma(x)$ would have to be a rearrangement of the group. A permutation with that property is a complete mapping of the group, and it is the same thing as a transversal of the group’s multiplication table: a choice of one cell in each row and each column, all with different entries. Which group tables have transversals is a question met before among Latin squares, and Marshall Hall and Lowell Paige proved in 1955 that a group whose largest subgroup of order a power of two is cyclic and not trivial has none. The pentagon’s group has subgroups of order two and nothing larger of that kind, so it has no complete mapping, and no scrambling can catch every twin.

For this group the obstruction has a two-line form. Call a symmetry odd if it is a flip; a product is odd exactly when one of its two factors is. Add up the oddness of all ten products $x\sigma(x)$: each $x$ contributes its own oddness and that of $\sigma(x)$, and since $\sigma$ is a rearrangement, the total counts every symbol twice — an even number. But if the ten products were all different, they would be the ten symmetries themselves, five of which are flips — an odd total. So two products must coincide. Hall and Paige’s theorem is this parity argument made general.

A search confirms it without the theorem: running through every permutation of the ten symbols — all 3,628,800, discarding a partial one as soon as two products coincide — finds none that keeps the ten products apart. Hall and Paige’s conjecture that this obstruction is the only one, for every finite group, was proved by Stewart Wilcox, Anthony Evans and John Bray in 2009 using the classification of finite simple groups. The question of whether a square has a mate runs into the same transversals, which is why the same theorem appears there.

Where Verhoeff’s twins slip through #

For Verhoeff’s permutation the map $x \mapsto x\sigma(x)$ is as close to a rearrangement as the group allows: eight of the ten products are distinct, two pairs of symbols share a product, and two products are missed. Each shared product is a pair of doubled symbols the scheme cannot tell apart, in both orders — four of the ninety twin errors. No swap-proof scrambling does better than two collisions; whether some scrambling that lets swaps through could manage a single collision is a separate question the census does not ask.

Forty that are best at once #

The forty jointly best scramblings share a shape: each is an eight-cycle on eight of the symbols and a swap of the remaining two, which is the shape of Verhoeff’s own, $(0\,1\,5\,8\,9\,4\,2\,7)(3\,6)$ in his numbering of the symbols. Among them, their rates on the spoken slip spread from 80 to 95 per cent, and Verhoeff’s reaches the top value, 95.3 per cent, shared with four others. Five scramblings out of 34,040 are as good as his on all four rarer kinds of error at once. The shape has a practical side as well. A permutation made of an eight-cycle and a two-cycle has order eight, so its powers repeat only every eight positions, and in a number of up to eight digits every position is scrambled differently. A scrambling of smaller order would repeat sooner, and positions that share a power would be indistinguishable to errors that move a digit between them; the census’s rates do not see this, because they score one pair of positions at a time, but the forty best are all of the largest order their shape allows.

How Verhoeff arrived at his permutation is not something a census can tell. What it shows is that whatever process he used found the corner, and that a choice made by hand, before computers could list the alternatives in a fraction of a second, is as good as any of the 34,040.

A slip caught always, at a price #

The phonetic slip is the one kind that some scramblings catch completely.

Three hundred and eighty-five scramblings catch every spoken slip of the form “1a” for “a0” in every position. None of them is among the jointly best: the best of them catches 828 jump transpositions, twenty fewer than the corner, though some still reach 86 twins. So the design of a single check digit over ten symbols involves a genuine trade, and the choice of what to give up is a judgement about which errors the people writing the numbers actually make. Verhoeff’s own tallies of copying errors put jump transpositions slightly ahead of phonetic slips in frequency, and his choice gives up a few of the slips.

The census, and what it stands on #

Every number in the figures is a count over every case: all 34,040 scramblings, found by a search that rejects a partial permutation the moment a pair of symbols fails the swap condition, and for each one all 90 twin errors and all 900 of each jump error. The phonetic rates average over a full cycle of each permutation’s powers, which is every position a long number can have up to the scheme’s own period. The count of 34,040 agrees with the count recorded when the dihedral scheme was introduced, and the search of all 3,628,800 permutations for a complete mapping found none, as Hall and Paige’s theorem requires.

The rates treat every pair of symbols as equally likely to be involved in an error, which real numbers do not: an account number’s digits are not uniform, and a person’s slips depend on the digits. And the census covers only Verhoeff’s form of scheme — the pentagon’s group with powers of one scrambling. Other schemes, such as Damm’s quasigroups of 2004, are built differently and are not on these plots.

Eleven symbols would make it easy #

The difficulty is particular to ten. With eleven symbols — the digits and an extra one, as the old ten-digit book numbers had in their final X — a weighted sum modulo eleven, with different weights in different positions, catches every single error and every swap, and with suitable weights every jump transposition as well, because eleven is prime and every non-zero difference has an inverse. Nothing needs to be scrambled, and no group needs to be non-commutative. The cost is the eleventh symbol, which does not fit on a numeric keypad or in a field that holds only digits, and that cost is why decimal schemes exist at all.

The comparison shows what the census is measuring. Over a prime number of symbols the arithmetic of a field catches error after error by the same mechanism. Over ten, the only structures that catch swaps are non-commutative or not groups at all, and each additional kind of error caught is paid for in the choice of a permutation, with the group’s own structure — its parity, its lack of complete mappings — setting a ceiling that no choice can lift.

The same objects as Euler’s officers #

The complete mappings that the pentagon’s group lacks are a familiar object in another guise. A complete mapping of a group is a transversal of its multiplication table, and a Latin square has an orthogonal mate exactly when it can be cut into disjoint transversals. So the multiplication table of the pentagon’s group has no orthogonal mate — not because of anything about check digits, but by Hall and Paige’s theorem — and the twin errors that every Verhoeff scheme misses are, in this sense, the same phenomenon as the square of order ten that has no mate.

The coincidence runs deeper than vocabulary. The swap condition itself, $x\sigma(y) \neq y\sigma(x)$, says that a certain table built from the group and the permutation has no repeated entries off its diagonal — a property of Latin squares called anti-symmetry — and the totally anti-symmetric quasigroups behind Damm’s scheme are Latin squares with that property built in. Check digits over ten symbols are, at bottom, a question about Latin squares of order ten, and order ten is where Latin squares are hardest to search.

Still open: check digits beyond the pentagon #

The census settles the best possible scheme of Verhoeff’s form, but not the best possible check digit. Schemes built on quasigroups — tables that need not come from a group at all — include Damm’s, which catches every single error and every swap with no scrambling needed, and the number of totally anti-symmetric quasigroups of order ten is far too large to search the way the scramblings were. Whether some quasigroup scheme catches every twin error as well — something no group scheme over ten symbols can do — is a question about Latin squares with an extra property, and only partial searches have been made.

There is also the question of scoring. A single number for a scheme requires weighting the error kinds by how often they occur, and the weights come from studies of human errors that are decades old, made on numbers written by hand. Errors made on keyboards and phone keypads have different frequencies — adjacent keys, repeated presses — and a census like this one could be redone for any set of weights, but which weights describe current practice is an empirical question the mathematics cannot settle.

Verhoeff’s corner #

A check digit over ten symbols built on the pentagon’s group must scramble its digits, and 34,040 scramblings catch every swap. Graded on the rarer errors, they spread out, and the theory of complete mappings closes the top corner: no scrambling catches every twin error, because the group’s table has no transversal. The best possible — 86 of 90 twins, 848 of 900 jump swaps and as many jump twins — is reached by forty scramblings, all of one shape, and only five of those are also best on spoken slips. Verhoeff’s 1969 permutation is one of the five.