Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)?

share|improve this question
    
I recall having solved this problem at least twice by looking for a basis of lattice $L$ that is isometric (i.e. shares the lengths and inner products with) to a basis of $E_8$ consisting of the simple roots. Alas, I don't remember how it goes (and also depends on the chosen description of the Hamming code). –  Jyrki Lahtonen May 1 '13 at 6:17
add comment

1 Answer

up vote 10 down vote accepted
+50

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)$.

share|improve this answer
    
Just wanted to thank you again for a terrific answer. It's very helpful to beginners in algebra like myself –  tacos_tacos_tacos Mar 31 at 13:06
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.