## Identification numbers with check digit algorithms

### An optimal system

Let us look now at an "excellent" error-detecting code based on Verhoeff ideas and Group Theory.

Consider a regular pentagon. It is easy to verify that the set of all symmetries of a regular pentagon has just $$10$$ elements ($$5$$ rotations and $$5$$ reflections).

Let us identify each symmetry by a number, in the following way:

 $$0$$ Identity (0 degrees rotation) $$1$$ Rotation (angle: $$\frac{1}{5} \times 2\pi$$) $$2$$ Rotation (angle: $$\frac{2}{5} \times 2\pi$$) $$3$$ Rotation (angle: $$\frac{3}{5} \times 2\pi$$) $$4$$ Rotation (angle: $$\frac{4}{5} \times 2\pi$$) $$5$$ Reflection with respect to $$r_{1}$$ $$6$$ Reflection with respect to $$r_{2}$$ $$7$$ Reflection with respect to $$r_{3}$$ $$8$$ Reflection with respect to $$r_{4}$$ $$9$$ Reflection with respect to $$r_{5}$$

We will also define an operation in this set of symmetries. Suppose we want to operate $$4$$ with $$8$$. For this, we apply first symmetry $$4$$ to our pentagon [ABCDE], obtaining pentagon [BCDEA]:

Then, we apply symmetry $$8$$ to [BCDEA], and obtain finally pentagon [DCBAE]:

But there is a symmetry in our table that enables to "go straight" from the pentagon [ABCDE] to the pentagon [DCBAE]: it is symmetry $$7$$. Therefore, we say that $$4$$ operated with $$8$$ is equal to $$7$$. We may this way define a kind of multiplication between pentagon symmetries. We denote it by *, and write $$4 *8 = 7$$.

If we do this for any pair of symmetries we will eventually get the following table for the operation *:

Table of the dihedral group $$D_{5}$$

The set of all symmetries of a regular pentagon, with operation *, is usually referred to as the dihedral group $$D_{5}$$.

Note that this operation is quite different from the usual arithmetic operations such as addition and multiplication: it is not a commutative operation.

We may use this group to design an error-detecting code for identification numbers with $$8$$ digits, $x_{1}x_{2}x_{3}x_{4}x_{5}x_{6}x_{7}x_{8}$ (in fact, one can even design similar systems for numbers with more than $$8$$ digits).

Let $$C$$ be the check digit given by the rule $C=\theta(x_{1})*x_{2}*\theta(x_{3})*x_{4}*\theta(x_{5})*x_{6}*\theta(x_{7})*x_{8}$ where $$\theta$$ is the anti-symmetric permutation $\theta=(14)(23)(58697).$

For those not familiar with the abbreviated cycle notation for permutations, $$\theta$$ is the function defined by $$\theta(1)=4$$, $$\theta(2)=3$$, $$\theta(3)=2$$, $$\theta(4)=1$$, $$\theta(5)=8$$, $$\theta(6)=9$$, $$\theta(7)=5$$, $$\theta(8)=6$$ and $$\theta(9)=7$$.

For example, take the identification number $$12345678$$. Its check digit will be: $C=\theta(x_{1})*x_{2}*\theta(x_{3})*x_{4}*\theta(x_{5})*x_{6}*\theta(x_{7})*x_{8}=$ $=\theta(1)*2*\theta(3)*4*\theta(5)*6*\theta(7)*8=4*2*2*4*8*6*5*8$

Using the table of the dihedral group $$D_{5}$$, we get $$4 * 2 = 1$$ and, therefore, the check digit will be $C=1*2*4*8*6*5*8.$

Proceeding in a similar way, we get $C=3*4*8*6*5*8=2*8*6*5*8=5*6*5*8=4*5*8=9*8=1.$

Try to compute the check digit of other identification numbers, and confirm your results with this applet.