ATRACTOR

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 app.

But what are the major advantages of this system?