Ten digits need a symmetry that does not commute

The first essay on codes looked briefly at the check digit — the last digit of a bank account, a barcode or a book number, chosen so that a weighted sum of all the digits comes out to nought — and found that its quality turns on two properties of arithmetic. The weights must be such that a single wrong digit always changes the sum, and neighbouring positions must carry different weights, or swapping two neighbours changes nothing. Over a prime modulus both are easy: the ten-digit book number used weights $1$ to $10$ modulo $11$ and caught every single error and every swap of neighbours.

It paid for that with an eleventh symbol. A sum modulo $11$ can come out to ten, and the check digit then has to be written $X$, which is why old book numbers sometimes end in a letter. Every system that must stay within the ten decimal digits — barcodes, credit cards, serial numbers, national identity numbers — faces the question this essay is about. Can ten symbols do what eleven can?

The answer is that a weighted sum cannot, that nothing built on addition modulo ten can, and that something can — but it has to give up commutativity, the property that $a + b = b + a$, which every schoolchild’s arithmetic has and which turns out to be exactly what lets a swap through.

Why no pair of weights is enough #

The two grids in the figure are the whole of the weighted-sum question for alternating weights, and the argument that empties their intersection takes two sentences.

A single wrong digit in a position of weight $w$ changes the sum by $w$ times the change, and the change goes unnoticed when that product is a multiple of ten. For every possible change to be noticed, $w$ must share no factor with ten — it must be odd and not five. That is the left-hand grid’s dark rows and columns: weights $1$, $3$, $7$ and $9$.

A swap of neighbouring digits $a$ and $b$ in positions with weights $w_1$ and $w_2$ changes the sum by $(w_1 - w_2)(a - b)$, and for every swap to be noticed, $w_1 - w_2$ must likewise share no factor with ten. But if both weights are odd, their difference is even, and an even number shares the factor two with ten. So the two requirements contradict each other, and no square of the figure can be dark in both grids.

The best compromise is the one retail adopted. Weights $3$ and $1$ catch every single error and every swap except those of two digits five apart — $0$ and $5$, $1$ and $6$, and so on — because those are the swaps that change the sum by $2 \times 5 = 10$. Eight swaps in nine are caught. Every barcode on every product uses exactly this scheme, and in 2007 the book trade adopted it too: the thirteen-digit book number replaced the ten-digit one, and in doing so gave up the eleventh symbol and the guarantee that came with it.

Why eleven was easy #

It is worth being clear about what the prime modulus was doing, because the rest of the essay is a search for a substitute. Modulo eleven, the product of two numbers is zero only if one of them is: there are no zero divisors in arithmetic modulo a prime, so a weight times a nonzero change is never a multiple of the modulus, and a difference of two different weights times a nonzero change never is either. Every weight from one to ten is usable and every pair of different weights catches every swap. That is why the ten-digit book number could take the weights one to ten and stop worrying.

Modulo ten the zero divisors are two and five, and every failure in the two grids above is one of them: a weight that is a multiple of two or five misses some single errors, and a difference of weights that is a multiple of two misses the swaps of digits five apart. The grids are a map of where the zero divisors of ten sit. The interest of what follows is that the obstruction survives even when weights are abandoned altogether, and so cannot be blamed on the zero divisors alone.

Not just weights: no scheme built on adding modulo ten #

A weighted sum is a special case of something more general. Instead of multiplying the digit in position $i$ by a weight, the scheme could apply any scrambling of the ten digits — any permutation $\sigma_i$ — and require that $\sigma_1(d_1) + \sigma_2(d_2) + \cdots$ be a multiple of ten. Hans Peter Luhn’s scheme of 1954, still used on every credit card, is of this form: it doubles every second digit and adds the digits of the result, which scrambles $0, 1, \ldots, 9$ into $0, 2, 4, 6, 8, 1, 3, 5, 7, 9$.

A permutation catches every single error automatically, since it never sends two digits to the same place. The question is swaps. Swapping $a$ and $b$ in positions $i$ and $i + 1$ is caught unless $\sigma_i(a) + \sigma_{i+1}(b) = \sigma_i(b) + \sigma_{i+1}(a)$. Writing $\phi$ for the scramble that takes $\sigma_{i+1}$'s output back through $\sigma_i$, the scheme catches every swap exactly when $x \mapsto \phi(x) - x$ never takes the same value twice — when $\phi(x) - x$, like $\phi(x)$ itself, runs through all ten digits. Such a $\phi$ is called an orthomorphism, and the question becomes whether the integers modulo ten have one.

They do not, and the figure shows it is not a quirk of ten. A search through every scrambling of $n$ symbols finds swap-proof scrambles for every odd modulus — three for three symbols, fifteen for five, 133 for seven, 2,025 for nine, 37,851 for eleven, numbers that match the published counts — and none at all for any even one. The search is the evidence; the proof is a parity argument short enough to give in full. If $\phi(x) - x$ ran through all of $0, 1, \ldots, n - 1$, then adding up over all $x$,

$$\sum_x (\phi(x) - x) = \sum_x \phi(x) - \sum_x x = 0,$$

since $\phi$ only rearranges the symbols. But the left side is also $0 + 1 + \cdots + (n - 1) = n(n - 1)/2$, which for even $n$ is $n/2$ times an odd number and so not a multiple of $n$. Contradiction. For odd $n$ the same sum is a multiple of $n$, and the argument is silent; the census then supplies examples.

Luhn’s scheme therefore has to miss something, and what it misses is a single swap: $09$ and $90$, where the doubled nine and the plain nine happen to add the same. Every scheme of this shape over the integers modulo ten misses at least one kind of swap, and no amount of cleverness in the choice of scrambles can repair it.

The surprising connection: Euler’s officers #

The parity argument is not new, and its first appearance had nothing to do with digits.

In 1782 Leonhard Euler asked whether thirty-six officers — six ranks, six regiments — could be paraded in a six-by-six square with every rank and every regiment once in each row and column: whether there is a pair of orthogonal Latin squares of order six. Along the way he proved something easier. The addition table of the integers modulo $n$ is a Latin square, every symbol once in each row and column, and for even $n$ that square has no transversal — no way of choosing one cell from each row and each column with all $n$ symbols different. His proof was the sum above.

The two statements are the same statement. A transversal of the addition table picks, in row $x$, the column $\phi(x)$, with the entry $x + \phi(x)$ different in every row; that is a permutation $\phi$ with $x + \phi(x)$ also a permutation, which after a change of sign is exactly an orthomorphism. So the impossibility of a perfect check digit built on adding modulo ten is Euler’s theorem that the even cyclic squares have no transversal — the property that makes a Latin square one cell short of a mate. A question about bank-account numbers in the twentieth century and a question about parading officers in the eighteenth turn on one line of arithmetic about $0 + 1 + \cdots + 9 = 45$, which is not a multiple of ten.

The general version was a conjecture of Marshall Hall and Lowell Paige from 1955, that a finite group’s multiplication table has a transversal exactly when its subgroups of power-of-two order are trivial or not cyclic. It was proved in 2009, in a combination of work by Stewart Wilcox, Anthony Evans and John Bray that finished with the help of the classification of finite simple groups. The cyclic group of order ten has a cyclic subgroup of order two, and so fails.

A symmetry that does not commute #

The parity argument needs the sum of all the elements to be computable in two ways, and that needs the order of addition not to matter. Drop commutativity and the argument has nowhere to stand.

A regular pentagon can be turned through any multiple of $72°$ — five turns, counting the turn by nothing — or flipped over any of its five axes. That is ten symmetries, and they can be numbered $0$ to $9$ and combined by doing one after the other, which gives the table in the figure. Two turns combine in either order to the same turn, and so do the pale corner’s entries; but a turn and a flip, or two flips, usually give different answers in different orders. Sixty of the hundred pairs do not commute.

Why a turn and a flip do not commute is visible with a paper pentagon. Turn it a fifth clockwise and then flip it over the vertical axis, and the corner that started at the top ends at one place; flip first and then turn, and the flip reverses the sense of the turn, so the same corner ends at another. The symmetries form a group — every one can be undone, and combining is associative — but not a commutative one, and the turns sit inside it as a subgroup of index two, exactly as the even shuffles sit inside all shuffles.

Jacobus Verhoeff, in his doctoral thesis at the Mathematical Centre in Amsterdam in 1969, used this table in place of addition modulo ten. His scheme scrambles the digit in position $i$ by the $i$-th power of one fixed permutation of the ten symbols and combines the results with the pentagon’s table rather than by adding; the number is valid when the combination is the symmetry that does nothing. The parity obstruction is gone, because a sum of all ten symmetries does not have a well-defined value when the order of combining matters, and the census in the previous figure finds 34,040 swap-proof scrambles for the pentagon — Verhoeff’s among them, checked pair by pair.

Verhoeff’s scheme catches every single error and every swap of neighbours with ten symbols and no $X$. It was used for the serial numbers of the Deutsche Mark banknotes, and it is used today for the twelve-digit Aadhaar identity numbers of India — one of the largest deployments of a non-commutative group in everyday life, almost none of whose users know it is there.

A table that is not even a group #

Verhoeff’s construction might suggest that some algebraic structure is essential. In 2004 H. Michael Damm showed that very little is.

Damm’s table is a single ten-by-ten Latin square, used as a step rule rather than as an arithmetic: from the current value, the next digit selects a column, and the entry there is the new current value. The property that matters is that from any current value $c$, taking digit $x$ then $y$ never lands in the same place as taking $y$ then $x$, unless $x = y$ — Damm called such an operation totally anti-symmetric. The figure checks all 900 combinations. Single errors are caught because each row of a Latin square holds each value once, so a different digit always leads to a different place, and the zero diagonal makes the check digit easy to append: whatever the running value, appending it brings the walk home to $0$.

The table is not a group’s: 878 of its thousand triples fail the associative law, so it does not even compute anything that could be called a product of the digits. It needs only one property, and Damm showed that tables with it exist for every order except two and six — the same two exceptions as Euler’s officers, for related reasons.

Measured against the errors people make #

The schemes can now be compared on equal terms, and the comparison shows what each guarantee is worth.

The two columns that matter most are the first two. Verhoeff’s thesis classified the errors in thousands of numbers copied by hand, and reported that single wrong digits account for most of them — between 60 and 95 per cent depending on the setting — and swapped neighbours for most of the rest, around 10 to 20 per cent. Every other kind of error was a per cent or two. A scheme that catches the first two columns completely is catching nearly everything people actually do, and that is exactly the guarantee ten symbols can only buy by giving up commutativity.

The other columns show what is left. The weights $3$ and $1$ catch no swap across one digit at all, since positions two apart carry the same weight; Luhn’s doubling has the same blindness. The non-commutative schemes catch most of those, and most of the twin errors and the spoken slips, but not all: with ten symbols and one check digit, some error of some kind always gets through, because a single check digit can only distinguish ten outcomes, and the number of plausible errors of all kinds is far larger. Finding an error rather than detecting it needs more check symbols, and that is where the codes of the rest of this subject begin.

The search stops at eleven symbols, the proofs do not #

The census of swap-proof scrambles stops at eleven symbols. The figure establishes, by searching every scrambling, that the even moduli up to ten have none and the odd moduli up to eleven have some. That every even modulus has none is the parity argument, which is a proof; that every odd modulus has some is also true — the map $x \mapsto 2x$ works whenever $n$ is odd — but neither statement is something the bar chart can show beyond its last bar.

The error frequencies are Verhoeff’s, quoted, and the rates are measured on random numbers. Real numbers are not random — an account number has structure, and a person’s errors depend on the digits — and the catch rates for the rarer kinds depend somewhat on which digits occur. The guarantees in the first two columns do not depend on anything: they hold for every number, and the figure’s “all” is a statement about every case tried and about every case not tried.

The pentagon’s table is drawn; Verhoeff’s permutation is not. The scheme needs both the group and a scrambling permutation applied a different number of times in each position, and the figure verifies that the permutation lets no swap through without picturing it. The permutation is one of 34,040 that would serve, and what made Verhoeff choose his is not something any figure here can say.

Still open: the best one can do with a check digit #

For single errors and swaps the question is settled, and the answer is that ten symbols need a non-commutative structure, which exists. For the rarer errors the question of the best decimal scheme is less settled. Which further kinds of error a single decimal check digit can be made to catch completely, alongside every single error and every swap — twin errors, swaps across one digit, the spoken slips — has been studied scheme by scheme, by Verhoeff and by those who came after him, and the limits of what one check digit can achieve over ten symbols are not completely charted.

Behind it stands a question about Latin squares. A totally anti-symmetric table is a Latin square with a strong extra property, and the number of such tables of order ten — how many essentially different perfect check-digit operations exist — is not known exactly, any more than the number of orthogonal mates of a random square of order ten is known except by sampling. Ten is small enough that the tables can be written down and large enough that they cannot all be listed, which is the size at which this subject’s questions usually stay open.