Return to Answer

Put $s

Source Link

edited Nov 25, 2019 at 17:19

If we have an alphabet of m symbols and we agree that our strings of symbols to be used all have n terms, say they are written as a_1a_2...a_n,$a_1a_2...a_n,$ introduce a set of weights w_1,...,w_n$w_1,...,w_n $ and a valid string is one where

w_1a_1 + ... + w_na_n = 0 mod m.$w_1a_1 + ... + w_na_n = 0 \mod m.$

In practice we take w_n = 1$ w_n = 1 $ or -1$-1 $ and the unique choice of a_n$a_n $ that fits the congruence given all the other data is the check digit.

Theorem 1: All single digit errors are caught iff (w_i,m) = 1$ (w_i,m) = 1 $ for all i.

Theorem 2: All adjacent transposition errors are caught iff (w_{i+1}-w_i,m) = 1$(w_{i+1}-w_i,m) = 1 $ for all i. (Wrap around when i = n.)

For example, say m = 10 (using the symbols 0,1,2,...,9). If all single digit errors are caught then each w_i$w_i $ has to be taken from {1,3,5,7}, but the difference of any two of these is even, so Theorem 2 won't apply.

Maybe you think we are just not being clever enough in our check digit protocol mod 10. For example, instead of those scaling operations a |---> w_ia$w_i$a which are put together by addition, we could just define in some other way a set of permutations s_i$s_i$ of Z/m and declare a string a_1....a_n$a_1....a_n$ to be valid when

s_1(a_1) + ... + s_n(a_n) = 0$s_1(a_1) + ... + s_n(a_n) = 0 $ mod m.

We can use this congruence to solve for a_n$ a_n $ given everything else, so we can make check digits this way too.

Answer: Yes, using the group D_5$ D_5$ (non-abelian of order 10) in place of Z/10.

This was found by Verhoeff in 1969. It has hardly been adopted anywhere, due to inertia perhaps, even though the mechanism of it would in practice always be hidden in computer code so the user wouldn't really need to know such brain-busting group theory like D_5$D_5$.

If we have an alphabet of m symbols and we agree that our strings of symbols to be used all have n terms, say they are written as a_1a_2...a_n, introduce a set of weights w_1,...,w_n and a valid string is one where

w_1a_1 + ... + w_na_n = 0 mod m.

In practice we take w_n = 1 or -1 and the unique choice of a_n that fits the congruence given all the other data is the check digit.

Theorem 1: All single digit errors are caught iff (w_i,m) = 1 for all i.

Theorem 2: All adjacent transposition errors are caught iff (w_{i+1}-w_i,m) = 1 for all i. (Wrap around when i = n.)

For example, say m = 10 (using the symbols 0,1,2,...,9). If all single digit errors are caught then each w_i has to be taken from {1,3,5,7}, but the difference of any two of these is even, so Theorem 2 won't apply.

Maybe you think we are just not being clever enough in our check digit protocol mod 10. For example, instead of those scaling operations a |---> w_ia which are put together by addition, we could just define in some other way a set of permutations s_i of Z/m and declare a string a_1....a_n to be valid when

s_1(a_1) + ... + s_n(a_n) = 0 mod m.

We can use this congruence to solve for a_n given everything else, so we can make check digits this way too.

Answer: Yes, using the group D_5 (non-abelian of order 10) in place of Z/10.

If we have an alphabet of m symbols and we agree that our strings of symbols to be used all have n terms, say they are written as $a_1a_2...a_n,$ introduce a set of weights $w_1,...,w_n $ and a valid string is one where

$w_1a_1 + ... + w_na_n = 0 \mod m.$

In practice we take $ w_n = 1 $ or $-1 $ and the unique choice of $a_n $ that fits the congruence given all the other data is the check digit.

Theorem 1: All single digit errors are caught iff $ (w_i,m) = 1 $ for all i.

Theorem 2: All adjacent transposition errors are caught iff $(w_{i+1}-w_i,m) = 1 $ for all i. (Wrap around when i = n.)

For example, say m = 10 (using the symbols 0,1,2,...,9). If all single digit errors are caught then each $w_i $ has to be taken from {1,3,5,7}, but the difference of any two of these is even, so Theorem 2 won't apply.

Maybe you think we are just not being clever enough in our check digit protocol mod 10. For example, instead of those scaling operations a |---> $w_i$a which are put together by addition, we could just define in some other way a set of permutations $s_i$ of Z/m and declare a string $a_1....a_n$ to be valid when

$s_1(a_1) + ... + s_n(a_n) = 0 $ mod m.

We can use this congruence to solve for $ a_n $ given everything else, so we can make check digits this way too.

Answer: Yes, using the group $ D_5$ (non-abelian of order 10) in place of Z/10.

Post Made Community Wiki

Source Link

created Jan 29, 2010 at 3:59

KConrad

50.6k
9
196
277

Here is a striking application of a particular finite non-abelian group.

Explain to your students the issue of check digits as an error-detecting device on credit cards, automobile identification numbers, etc. Two common errors in communicating strings of numbers is a single-digit error (...372... --> ...382...) or an adjacent transposition error (...32... ---> ...23...). We want to design a check digit protocol in such a way that these two common errors are both detected (though not necessarily corrected: an error sign may flash in practice and the person is just prompted to enter the numbers all over again). The simplest check digit protocol uses modular arithmetic, as follows.

w_1a_1 + ... + w_na_n = 0 mod m.

In practice we take w_n = 1 or -1 and the unique choice of a_n that fits the congruence given all the other data is the check digit.

Theorem 1: All single digit errors are caught iff (w_i,m) = 1 for all i.

That means if a valid string -- one satisfying the above congruence -- has a single term changed then the result will not satisfy the congruence and thus the error is detected.

Theorem 2: All adjacent transposition errors are caught iff (w_{i+1}-w_i,m) = 1 for all i. (Wrap around when i = n.)

The conclusion is that "no check digit protocol exists on Z/10 (for strings of length greater than 1) which detects all single digit errors and all adjacent transposition errors.

s_1(a_1) + ... + s_n(a_n) = 0 mod m.

We can use this congruence to solve for a_n given everything else, so we can make check digits this way too.

Theorem 3. When m = 10, or more generally when m is even, there is an adjacent transposition error -- and in fact a transposition error in any two predetermined positions for some string -- that won't be caught.

The proof is a clever argument by contradiction, but I won't type up the details here.

Since in practice we'd like to use 10 digits (or 26 letters -- still even) for codes, Theorem 3 is annoying. The book community with their ISBN code got around this by using m = 11 with a special check digit of X (a few years ago they switched to m = 13). It is natural to ask: is there some check digit protocol on 10 symbols?

Answer: Yes, using the group D_5 (non-abelian of order 10) in place of Z/10.

You can read about this by looking at

S. J. Winters, Error Detecting Schemes Using Dihedral Groups, The UMAP Journal 11 (1990), 299--308.

The only bad thing about this article by Winters is the funny use of the word scheme, e.g., the third section of the article is called (I am not making this up) "Dihedral Group Schemes". I recommend using the word "protocol" in place of "scheme" for this check digit business since it it more mathematically neutral.

By the way, Theorem 3 should not be construed as suggesting there is no method of using Z/10 to develop a check digit protocol which detects both of the two errors I'm discussing here. See, for example,

K. A. S. Abdel-Ghaffar, Detecting Substitutions and Transpositions of Characters, The Computer Journal 41 (1998) 270--277.

Section 3.4 is the part which applies to modulus 10. I have not read the paper in detail (since I'm personally not interested enough in it), but the end of the introduction is amusing. After describing what he will be able to do he says his method "is easier to understand compared to the construction based on dihedral groups". What the heck is so hard about dihedral groups? Sheesh.