Isomorphism between $E_8$ lattice and lattice defined by Extended Hamming Code

I have read that the following two lattices are isomorphic, and of course it seems believable, but it would be nice to have a sketch of how to construct the bijection.

Let $C$ be some extended $(8,4,4)$ Hamming Code. For example, let it be generated by:

$$G = \left(\begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ {\bf 1} & {\bf 1} & {\bf 1} & {\bf 0}\end{array}\right)$$

Let $L$ be the lattice defined as containing all points in $\mathbb{Z}^8$ such that reduction modulo $2$ component-by-component ($\phi$) gives you a codeword, or in other words, $L = \{x \in \mathbb{Z}^8: \phi(x) \in C\}$.

It is well-known and pretty easy to show that the minimum norm is $2$. These minimum norm vectors of norm $2$ corresponding to weight $0$ codewords have a $\pm 2$ in one of the $8$ entries, so there are $2 \times 8 = 16$ of these. The vectors of norm $2$ corresponding to weight $4$ codewords have a $\pm 1$ in four digits. There are $14$ weight $4$ codewords, so there are $14 \times 2^4$ of these. Then there are $2^4 + 14 \times 2^4 = 15 \times 16 = 240$ vectors of minimum norm $2$.

Let $E$ by the $E_8$ lattice with the even construction so that the parity is even and all points are either all integral or all half-integral. By a similar argument, there are also $240$ vectors of minimum norm $\sqrt{2}$. But these look different. For example, any vectors with a $1$ in two of the eight positions has minimum norm $2$, and each of these you can permute the signs to give ${{8}\choose{2}} \times 4$ of them. Any half-integer vector of minimum norm $2$ must have all $\frac{1}{2}$ with an even number of positive (or negative) entries, so there are ${{8}\choose{2}} \times 4 + \left({{8}\choose{8}} + {{8}\choose{6}} + {{8}\choose{4}} + {{8}\choose{2}} + {{8}\choose{0}}\right) = 112 + 2^7 = 240$ total minimum norm $\sqrt{2}$.

My problem is that the vectors of minimum norm in $L$ and $E$ are totally different, even after rescaling. In $L$, there are vectors with $1$ and $4$ nonzero entries, while in $E$ there are vectors with $2$ and $8$ nonzero entries. Plus, the way that the minimum norm vectors are counted doesn't give a lot of insight. How do you get from $E$ to $L$ (and vice-versa)?

Solution 1:

Here's a recipe to identify any even unimodular lattice $L$ of rank $8$ with $E_8$. To go in reverse, just use the inverse matrix. I'll illustrate it with your $L$ (which must use the inner product $(x,y) = \frac12 \sum_{i=1}^8 x_i y_i$ to give $E_8$).

Step 1: choose some vector of norm $4$ in $L$. Write it as $2 e_8$ for some half-lattice unit vector $e_8$. The choice doesn't matter because all $2160$ vectors of this norm are equivalent under the isometry group. We can use $e_8 = \frac12(1,1,1,1,1,1,1,1)^t$ ("t" for transpose since you're using column vectors).

Step 2: Any of the $240$ vectors $v$ of norm $2$ has inner product $0$, $\pm 1$, or $\pm 2$ with $2 e_8$. Each of the extreme values $\pm 2$ occurs only $14$ times, in $7$ pairs $\{v,e_8-v\}$ or $\{v,-e_8-v\}$ according to the choice of sign. Choose one of each of the seven pairs with inner product $+1$. Subtract $e_8$ from each of these seven vectors to get a half-lattice vector $e_i$ ($i=1,\ldots,7$) of norm $1$ orthogonal to $e_8$. The $i$th pair is then $e_8 \pm e_i$, so choosing the other vector in each pair just changes $e_i$ to $-e_i$. In our setting, the fourteen $v$'s are 0,1 vectors coming from the fourteen word of weight $4$ in $C$, with complementary words forming pairs. Choose one from each pair, and obtain unit vectors $e_i = \frac12(\pm1, \pm1, \pm1, \pm1, \pm1, \pm1, \pm1, \pm1)^t$, each with four plus and four minus signs.

Step 3: At this point $L$ contains all the vectors $\pm e_i \pm e_j$. I claim that the $e_i$ ($i=1,\ldots,7$) are orthogonal not just to $e_8$ but also to each other. Indeed $(e_i,e_j) = (e_i+e_8, e_j+e_8) - 1$ is an integer, and cannot be $\pm 1$ unless $i = j$ because by Cauchy-Schwarz $(e_i,e_j) = \pm 1$ implies $e_j = \pm e_i$. So in our setting the $\pm1$ matrix with columns $2e_1,\ldots,2e_8$ is a Hadamard matrix.

Step 4: We have found a sublattice of index 2 in $L$ consisting of the even-sum linear combinations of the $e_i$ and thus isomorphic with $D_8$. To recover $L$, we put in one of the two vectors $\frac12(e_1 + e_2 + \cdots + e_7 \pm e_8)$ generating the nontrivial even cosets of $D_8$ in its dual. Try the plus sign, and check whether the resulting vector is in $L$. If yes, we have our isomorphism with $E_8$. If not, we get the isomorphism by changing $e_8$ to $-e_8$. For your lattice, the change-of-basis matrix from $E_8$ to $L$ is $1/2$ times a Hadamard matrix $H$, so the inverse map is $2H^{-1} = H^t/4$. If I did this right, one choice for $H$ is $$ \left( \begin{array}{cccccccc} + & + & + & + & + & + & + & + \\ + & + & + & - & - & - & - & + \\ + & - & - & + & + & - & - & + \\ - & + & - & + & - & + & - & + \\ - & + & - & - & + & - & + & + \\ - & - & + & + & - & - & + & + \\ - & - & + & - & + & + & - & + \\ + & - & - & - & - & + & + & + \end{array} \right) \ \; . $$

As a bonus we can counting the choices we've made along the way to find (by taking $L$ to be $E_8$ itself) that $E_8$ has $7! 2^6 2160 = 696729600$, which agrees with the known size of the Weyl group $W(E_8)$.