Barnes–Wall lattice

Orthogonal projection of the 16-dimensional Barnes–Wall lattice ${\displaystyle BW_{16}}$ onto 2 dimensions.

In mathematics, the Barnes–Wall lattice ${\displaystyle BW_{16}}$, discovered by Eric Stephen Barnes and G. E. (Tim) Wall,^[1] is the 16-dimensional positive-definite even integral lattice of discriminant 2⁸ 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.^[2]

The automorphism group of the Barnes–Wall lattice has order 89181388800 = 2²¹ 3⁵ 5² 7 and has structure 2¹⁺⁸ PSO₈⁺(F₂). 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.^[3]

While Λ₁₆ is often referred to as the Barnes-Wall lattice, their original article in fact construct a family of lattices of increasing dimension n=2^k for any integer k, and increasing normalized minimal distance, namely n^1/4. This is to be compared to the normalized minimal distance of 1 for the trivial lattice ${\displaystyle \mathbb {Z} ^{n}}$, and an upper bound of ${\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.^[4]

Generating matrix

The generator matrix for the Barnes-Wall Lattice ${\displaystyle BW_{16}}$ is given by the following matrix: $${\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 ${\displaystyle BW_{16}}$ generated by the above generator matrix has the following vectors as its shortest vectors.

$${\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.

$${\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 ${\displaystyle BW_{16}}$ can be constructed in the following way.^[5]

First, define the matrix $${\displaystyle B={\begin{pmatrix}{\sqrt {2}}&0\\1&1\end{pmatrix}}.}$$ Next, take its 4th tensor power: $${\displaystyle B^{\otimes 4}=B\otimes B\otimes B\otimes B.}$$ Then, apply the ring homomorphism $${\displaystyle {\begin{aligned}\phi :\mathbb {Z} [{\sqrt {2}}]&\rightarrow \mathbb {Z} \\a+b{\sqrt {2}}&\mapsto a+b\end{aligned}}}$$ entrywise to the matrix ${\displaystyle B^{\otimes 4}}$. The resulting ${\displaystyle 16\times 16}$ integer matrix is a generator matrix for the Barnes–Wall lattice ${\displaystyle BW_{16}}$.^[5]

Lattice theta function

The lattice theta function for the Barnes Wall lattice ${\displaystyle BW_{16}}$ is known as $${\displaystyle {\begin{aligned}\Theta _{\Lambda _{\text{Barnes-Wall }}}(z)&=1/2\left\{\theta _{2}\left(q\right)^{16}+\theta _{3}\left(q\right)^{16}+\theta _{4}\left(q^{2}\right)^{16}+30\theta _{2}\left(q\right)^{8}\theta _{3}\left(q\right)^{8}\right\}\\&=1+4320q^{2}+61440q^{3}+\cdots \end{aligned}}}$$ where the thetas are Jacobi theta functions: $${\displaystyle {\begin{aligned}&\theta _{2}(q)=\sum _{n=-\infty }^{\infty }q^{(m+1/2)^{2}}\\&\theta _{3}(q)=\sum _{n=-\infty }^{\infty }q^{m^{2}}\\&\theta _{4}(q)=\sum _{n=-\infty }^{\infty }(-q)^{m^{2}}.\end{aligned}}}$$

The number of vectors of each norm in the ${\displaystyle BW_{16}}$

The number of vectors ${\displaystyle N(m)}$ of norm ${\displaystyle m}$, as classified by J. H. Conway,^[6] is given as follows.

m	N(m)	m	N(m)
0	1	32	8593797600
2	0	34	11585617920
4	4320	36	19590534240
6	61440	38	25239859200
8	522720	40	40979580480
10	2211840	42	50877235200
12	8960640	44	79783021440
14	23224320	46	96134307840
16	67154400	48	146902369920
18	135168000	50	172337725440
20	319809600	52	256900127040
22	550195200	54	295487692800
24	1147643520	56	431969276160
26	1771683840	58	487058227200
28	3371915520	60	699846624000
30	4826603520	62	776820326400

Notes

1. Barnes & Wall (1959).
2. Conway & Sloane (1999), section 4.10.
3. Scharlau & Venkov (1994).
4. Micciancio & Nicolesi (2008).
5. Nebe, Rains & Sloane (2002).
6. Conway & Sloane (1999), p. 130.

References

• Barnes, E. S.; Wall, G. E. (1959), "Some extreme forms defined in terms of Abelian groups", J. Austral. Math. Soc., 1 (1): 47–63, doi:10.1017/S1446788700025064, MR 0106893
• Conway, John Horton; Sloane, Neil J. A. (1999), Sphere Packings, Lattices and Groups, Grundlehren der Mathematischen Wissenschaften, vol. 290 (3rd ed.), Berlin, New York: Springer-Verlag, ISBN 978-0-387-98585-5, MR 0920369
• Scharlau, Rudolf; Venkov, Boris B. (1994), "The genus of the Barnes–Wall lattice.", Comment. Math. Helv., 69 (2): 322–333, CiteSeerX 10.1.1.29.9284, doi:10.1007/BF02564490, MR 1282375
• Micciancio, Daniele; Nicolesi, Antonio (2008), "Efficient bounded distance decoders for Barnes-Wall lattices", 2008 IEEE International Symposium on Information Theory, pp. 2484–2488, doi:10.1109/ISIT.2008.4595438, ISBN 978-1-4244-2256-2
• Nebe, G.; Rains, E. M.; Sloane, N. J. A. (2002). "A Simple Construction for the Barnes-Wall Lattices". arXiv. arXiv:math/0207186.

External links

• Barnes–Wall lattice – Sloane's lattice catalog