In mathematics, the Barnes–Wall lattice B W 16 {\displaystyle BW_{16}} , discovered by Eric Stephen Barnes and G. E. (Tim) Wall, is the 16-dimensional positive-definite even integral lattice of discriminant 28 with no norm-2 vectors. It is the sublattice of the Leech lattice fixed by a certain automorphism of order 2, and is analogous to the Coxeter–Todd lattice. The automorphism group of the Barnes–Wall lattice has order 89181388800 = 221 35 52 7 and has structure 21+8 PSO8+(F2). There are 4320 vectors of norm 4 in the Barnes–Wall lattice (the shortest nonzero vectors in this lattice). The genus of the Barnes–Wall lattice was described by Scharlau & Venkov (1994) and contains 24 lattices; all the elements other than the Barnes–Wall lattice have root system of maximal rank 16. While Λ16 is often referred to as the Barnes-Wall lattice, their original article in fact construct a family of lattices of increasing dimension n=2k for any integer k, and increasing normalized minimal distance, namely n1/4. This is to be compared to the normalized minimal distance of 1 for the trivial lattice Z n {\displaystyle \mathbb {Z} ^{n}} , and an upper bound of 2 ⋅ Γ ( n 2 + 1 ) 1 / n / π = 2 n π e + o ( n ) {\displaystyle 2\cdot \Gamma \left({\frac {n}{2}}+1\right)^{1/n}{\big /}{\sqrt {\pi }}={\sqrt {\frac {2n}{\pi e}}}+o({\sqrt {n}})} given by Minkowski's theorem applied to Euclidean balls. This family comes with a polynomial time decoding algorithm.
Generating matrix The generator matrix for the Barnes-Wall Lattice B W 16 {\displaystyle BW_{16}} is given by the following matrix:
M B W 16 = 1 2 ( 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 2 0 0 0 0 0 2 0 0 0 2 0 2 0 0 0 0 2 0 0 0 0 2 0 0 0 2 0 0 2 0 0 0 0 2 0 0 0 2 0 0 0 2 0 0 0 2 0 0 0 0 2 0 0 2 0 0 0 0 0 2 2 0 0 0 0 0 0 2 0 2 0 0 0 0 0 2 0 2 0 0 0 0 0 0 2 2 0 0 0 0 0 0 2 2 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 2 0 2 2 0 0 0 0 0 0 0 0 0 0 2 0 2 0 2 0 2 0 0 0 0 0 0 0 0 0 0 2 2 0 0 2 2 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 ) {\displaystyle M_{BW_{16}}={\frac {1}{2}}\left({\begin{array}{cccccccccccccccc}1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1\\0&2&0&0&0&0&0&2&0&0&0&2&0&2&0&0\\0&0&2&0&0&0&0&2&0&0&0&2&0&0&2&0\\0&0&0&2&0&0&0&2&0&0&0&2&0&0&0&2\\0&0&0&0&2&0&0&2&0&0&0&0&0&2&2&0\\0&0&0&0&0&2&0&2&0&0&0&0&0&2&0&2\\0&0&0&0&0&0&2&2&0&0&0&0&0&0&2&2\\0&0&0&0&0&0&0&4&0&0&0&0&0&0&0&0\\0&0&0&0&0&0&0&0&2&0&0&2&0&2&2&0\\0&0&0&0&0&0&0&0&0&2&0&2&0&2&0&2\\0&0&0&0&0&0&0&0&0&0&2&2&0&0&2&2\\0&0&0&0&0&0&0&0&0&0&0&4&0&0&0&0\\0&0&0&0&0&0&0&0&0&0&0&0&2&2&2&2\\0&0&0&0&0&0&0&0&0&0&0&0&0&4&0&0\\0&0&0&0&0&0&0&0&0&0&0&0&0&0&4&0\\0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&4\end{array}}\right)}
For example, the lattice B W 16 {\displaystyle BW_{16}} generated by the above generator matrix has the following vectors as its shortest vectors.
v 1 = ( 1 2 , 1 2 , 1 2 , 1 2 , 1 2 , 1 2 , 1 2 , 1 2 , 1 2 , 1 2 , 1 2 , 1 2 , − 1 2 , − 1 2 , − 1 2 , − 1 2 ) v 2 = ( 0 , 1 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 0 ) {\displaystyle {\begin{aligned}v_{1}=&\left({\frac {1}{2}},{\frac {1}{2}},{\frac {1}{2}},{\frac {1}{2}},{\frac {1}{2}},{\frac {1}{2}},{\frac {1}{2}},{\frac {1}{2}},{\frac {1}{2}},{\frac {1}{2}},{\frac {1}{2}},{\frac {1}{2}},-{\frac {1}{2}},-{\frac {1}{2}},-{\frac {1}{2}},-{\frac {1}{2}}\right)\\v_{2}=&(0,1,1,0,0,0,0,0,0,0,0,0,0,1,1,0)\end{aligned}}}
The lattice spanned by the following matrix is isomorphic to the above. Indeed, the following generator matrix can be obtained as the dual lattice (up to a suitable scaling factor) of the above generator matrix.
M ~ B W 16 1 2 = ( 1 0 0 0 0 1 0 1 0 0 1 1 0 1 1 1 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 0 0 1 0 1 0 0 1 1 0 1 1 1 0 1 0 0 0 0 1 0 1 0 0 1 1 0 1 1 1 1 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 ) {\displaystyle {\widetilde {M}}_{BW_{16}}{\frac {1}{\sqrt {2}}}=\left({\begin{array}{cccccccccccccccc}1&0&0&0&0&1&0&1&0&0&1&1&0&1&1&1\\0&1&0&0&0&1&1&1&1&0&1&0&1&1&0&0\\0&0&1&0&0&0&1&1&1&1&0&1&0&1&1&0\\0&0&0&1&0&1&0&0&1&1&0&1&1&1&0&1\\0&0&0&0&1&0&1&0&0&1&1&0&1&1&1&1\\0&0&0&0&0&2&0&0&0&0&0&0&0&0&0&2\\0&0&0&0&0&0&2&0&0&0&0&0&0&0&0&2\\0&0&0&0&0&0&0&2&0&0&0&0&0&0&0&2\\0&0&0&0&0&0&0&0&2&0&0&0&0&0&0&2\\0&0&0&0&0&0&0&0&0&2&0&0&0&0&0&2\\0&0&0&0&0&0&0&0&0&0&2&0&0&0&0&2\\0&0&0&0&0&0&0&0&0&0&0&2&0&0&0&2\\0&0&0&0&0&0&0&0&0&0&0&0&2&0&0&2\\0&0&0&0&0&0&0&0&0&0&0&0&0&2&0&2\\0&0&0&0&0&0&0&0&0&0&0&0&0&0&2&2\\0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&4\\\end{array}}\right)}
Simple Construction of a Generating Matrix According to (Nebe, Rains & Sloane 2002), the generator matrix of B W 16 {\displaystyle BW_{16}} can be constructed in the following way. First, define the matrix
B = ( 2 0 1 1 ) . {\displaystyle B={\begin{pmatrix}{\sqrt {2}}&0\\1&1\end{pmatrix}}.}
Next, take its 4th tensor power:
B ⊗ 4 = B ⊗ B ⊗ B ⊗ B . {\displaystyle B^{\otimes 4}=B\otimes B\otimes B\otimes B.}
Then, apply the homomorphism of Abelian groups
ϕ : Z [ 2 ] → Z a + b 2