# hexacode

The hexacode is a 3-dimensional linear code of length (http://planetmath.org/LinearCode) 6, defined over the field $\mathbb{F}_{4}$, all of whose codewords have weight 0, 4, or 6. It is uniquely determined by these properties, up to monomial linear transformations (http://planetmath.org/MonomialMatrix) and in $\mathbb{F}_{4}$. The hexacode is crucial to the construction of the extended binary Golay code via Curtisβ Miracle Octad Generator. The exposition below follows ([1], Chapter 11). Another for the hexacode is ([2], Chapter 4).

## 1 Construction of the hexacode

There are several constructions of the hexacode, all leading to the same result. In the following, we write the elements of $\mathbb{F}_{4}$ as $\{0,1,\omega,\overline{\omega}\}$ where $\omega$ is a cube root of unity. We write elements of the hexacode as elements of $\mathbb{F}_{4}^{6}$, separated into three of two.

1. The span of the elements

 $\begin{array}[]{c}\omega\overline{\omega}\,\,\omega\overline{\omega}\,\,\omega% \overline{\omega}\\ \omega\overline{\omega}\,\,\overline{\omega}\omega\,\,\overline{\omega}\omega% \\ \overline{\omega}\omega\,\,\omega\overline{\omega}\,\,\overline{\omega}\omega% \\ \overline{\omega}\omega\,\,\overline{\omega}\omega\,\,\omega\overline{\omega}% \end{array}$

2. The elements of $\mathbb{F}_{4}^{6}$ of the form

 $(a,b,c,\phi(1),\phi(\omega),\phi(\overline{\omega}))$

where $a,b,c\in\mathbb{F}_{4}$ and $\phi(x)=ax^{2}+bx+c$.

3. The elements $ab\,\,cd\,\,ef$ of $\mathbb{F}_{4}^{6}$ which satisfy the three rules

 $\begin{array}[]{c}a+b=c+d=e+f=s\\ a+c+e=a+d+f=b+c+f=b+d+e=\omega s\\ b+d+f=b+c+e=a+d+e=a+c+f=\overline{\omega}s\end{array}$

Here $s$ is called the of the codeword.

An element of the hexacode is called a hexacodeword.

## 2 Justification of a hexacodeword

It is not difficult to show that all of the above constructions give the same 3-dimensional linear code of 6. However, it is somewhat tedious to use one of above constructions to determine whether a given element of $\mathbb{F}_{4}^{6}$ is in the hexacode. Instead, it is possible to show that an element of $\mathbb{F}_{4}^{6}$ is a hexacodeword if and only if it satisfies the shape and sign rules below. Using these rules, one can (with some practice) quickly distinguish hexacodewords from non-hexacodewords.

The shape rule says that, up to permutations of the three blocks and flips of the elements within a block, every hexacodeword has one of the shapes

 $\begin{array}[]{c}00\,\,00\,\,00\\ 00\,\,aa\,\,aa\\ 0a\,\,0a\,\,bc\\ bc\,\,bc\,\,bc\\ aa\,\,bb\,\,cc\end{array}$

where $a,b,c$ are $1,\omega,\overline{\omega}$ in some .

The sign rule says that in every hexacodeword, either:

• β’

all 3 blocks have sign 0, or

• β’

the product of the signs of the three blocks is positive.

The sign of a block is determined as follows:

• β’

+ for $0a$ or $ab$ where $b=a\omega$

• β’

- for $a0$ or $ab$ where $b=a\overline{\omega}$

• β’

0 for $00$ or $aa$

where $a\neq 0$.

For example,

• β’

$00\,\,11\,\,\omega\omega$ and $01\,\,0\omega\,\,1\overline{\omega}$ are not hexacodewords because they fail the shape rule.

• β’

$01\,\,01\,\,\omega\overline{\omega}$ satisfies the shape rule, and the signs are +β+β+, so it is a hexacodeword.

• β’

$1\omega\,\,\omega 1\,\,1\omega$ satisfies the shape rule, and the signs are +β-β+, so it is not a hexacodeword.

• β’

$00\,\,11\,\,11$ satisfies the shape rule, and the signs are 0β0β0, so it is a hexacodeword.

• β’

$\omega 0\,\,\omega 0\,\,\overline{\omega}1$ satisfies the shape rule, and the signs are -β-β+, so it is a hexacodeword.

## 3 Completion of a partial hexacodeword

The hexacode has the property that the following two problems always have a unique solution.

1. (3-problem) Given values in any 3 of the 6 positions, complete it to a full hexacodeword.

2. (5-problem) Given values in any 5 of the 6 positions, complete it to a full hexacodeword after possibly changing one of the given values.

Conway says that the best method for solving these is to simply βguess the correct answer, then justify itβ (using the shape and sign rules), though he also does give systematic algorithms for solving them.

Examples of 3-problems:

 $\begin{array}[]{c}01\,\,1?\,\,??\rightarrow 01\,\,10\,\,\overline{\omega}% \omega\\ ??\,\,1\overline{\omega}\,\,?0\rightarrow 0\omega\,\,1\overline{\omega}\,\,% \omega 0\\ 1?\,\,\omega\omega\,\,??\rightarrow 11\,\,\omega\omega\,\,\overline{\omega}% \overline{\omega}\end{array}$

Examples of 5-problems:

 $\begin{array}[]{c}00\,\,11\,\,\omega?\rightarrow 00\,\,11\,\,11\mbox{ (% position 5 changed)}\\ 0?\,\,1\overline{\omega}\,\,\omega\overline{\omega}\rightarrow 0\omega\,\,1% \overline{\omega}\,\,\omega 0\mbox{ (position 6 changed) }\\ 1\omega\,\,?1\,\,1\omega\rightarrow 1\omega\,\,\overline{\omega}1\,\,1\omega% \mbox{ (no position changed) }\end{array}$

## References

• 1 J. H. Conway and N. J. A. Sloane. Sphere Packings, Lattices, and Groups. Springer-Verlag, 1999.
• 2 Robert L. Griess, Jr. Twelve Sporadic Groups. Springer-Verlag, 1998.
Title hexacode Hexacode 2013-03-22 18:43:08 2013-03-22 18:43:08 monster (22721) monster (22721) 15 monster (22721) Definition msc 94B05 MiracleOctadGenerator BinaryGolayCode