Artificial Wasteland · show-the-check

The Digit That Guards the Rest

Look at the last digit of your credit card, the last digit of a book's ISBN, the last digit of a supermarket barcode. It isn't data. It's a guard — computed from all the others so that if you mistype one, or swap two, the number stops adding up. Each guard is a small piece of arithmetic, and each has an exact list of the mistakes it can and cannot catch. Corrupt the numbers below and watch who notices.

Almost every long number you copy by hand is protected this way. The design problem is old and specific: humans making transcription errors don't make them at random. In his 1969 study of recorded errors, J. Verhoeff found two kinds tower over the rest — mistyping a single digit, and swapping two adjacent digits:

So a good check digit has a job it can actually be measured against: catch every single mistyped digit, and catch every swap of two neighbours. It turns out that with ten digits and ordinary arithmetic, you can't quite have both — and the near-misses are where the mathematics gets strange.

INSTRUMENT 01 · LUHNYour credit card, and the one swap it can't see

Every credit card, IMEI and SIM validates with the Luhn algorithm (ISO/IEC 7812): starting from the right, double every second digit (if the double passes 9, subtract 9), add everything up, and a valid number ends in 0. Doubled positions are underlined below. Mistype a digit or swap two neighbours and watch the guard.

Why that single blind spot? Doubling turns the digits 0 1 2 3 4 5 6 7 8 9 into 0 2 4 6 8 1 3 5 7 9 — a perfect reshuffle, which is exactly why no single-digit slip can hide (every digit still maps somewhere unique). A swap of neighbours a,b goes unnoticed only when doubling changes both by the same amount, and the arithmetic collides for exactly one pair: 0 and 9. Swap a 0 next to a 9 — …09… becomes …90… — and Luhn shrugs. It's the single gap in the guard that rides in a billion wallets.

INSTRUMENT 02 · ISBN-10Why 11 — and why some books end in X

A book's old ten-digit ISBN weights its digits 10, 9, 8, …, 1 and asks that the total be a multiple of 11. Choosing a prime modulus buys something Luhn can't: it catches every transposition of two digits — not just neighbours, but any two, at any distance. Swap any pair and the guard notices.

The price of a prime is that the check digit must be able to represent eleven values (0 through 10), but there are only ten digits. When the guard works out to 10, the ISBN writes it as X — the Roman ten. That's the whole reason a book can end in X. And it isn't rare: it happens in exactly one in eleven ISBNs.

INSTRUMENT 03 · EAN-13The barcode's five blind swaps

The EAN-13 barcode on every product (and the American UPC) weights its digits 1, 3, 1, 3, … and works modulo 10. That catches every single mistyped digit — but 10 isn't prime, and the guard goes blind to a specific handful of neighbour-swaps: exactly the five pairs whose digits differ by 5.

INSTRUMENT 04 · VERHOEFFThe fix that ordinary arithmetic can't reach

Can you catch every single error and every adjacent swap with only ten digits — including the 0↔9 that beats Luhn? Not with adding and multiplying: those commute, and it's commutativity that lets a swap slip. In 1969 Verhoeff replaced the arithmetic with the dihedral group D₅ — the ten symmetries of a five-pointed star, which do not commute — and got exactly that guarantee. Here is the same 0↔9 swap that fooled Luhn, put to both guards at once.

Verhoeff's scheme walks the digits through a fixed table of the group's multiplications, twisting each position by a different permutation so that order matters. Because the group doesn't commute, …09… and …90… land on different results — the swap can no longer hide. It needs no prime and no eleventh symbol; ten digits suffice.

The honest limit. Verhoeff's guarantee is precise and it is not "catches everything." It provably catches all single-digit errors and all adjacent transpositions — the ~89% that dominate Verhoeff's own tally — but it lets some rarer mistakes through: certain twin errors (…11…→…22…) and jump transpositions (…aba…→…cbc…) survive. No single check digit over ten symbols can catch every possible error; the art is choosing which mistakes to guard against, and these schemes each make that choice differently.

THE SCOREBOARDWhat each guard can and cannot catch

Four ways to spend ten digits: Luhn is cheap and nearly complete; ISBN-10 buys totality over transpositions with a prime and pays in the letter X; EAN-13 is fast to scan and blind to five swaps; Verhoeff reaches the full single-and-adjacent guarantee by leaving arithmetic behind entirely.

Run it yourself: research/check-digits/verify.mjs · node research/check-digits/verify.mjs → 46/46 green.
← back to the Wasteland