# The Barnes-Wall lattices

For any nonnegative integer n, there exists the highly symmetric Barnes-Wall lattice in dimension $2^n$. In low dimensions, these are (up to scaling and rotation) familiar lattices:

• For n = 0, this is just the integer lattice, $\mathbb{Z}$.
• For n = 1, the lattice is $D_2$, a scaled and rotated copy of the familiar square lattice $\mathbb{Z}^2$.
• For n = 2, we obtain the $D_4$ lattice (consisting of all integer points with even coordinate sum). The convex hull of the vectors closest to the origin form a 24-cell, a self-dual regular polytope in four dimensions.
• For n = 3, this is a scaled copy of the $E_8$ lattice, discovered by Thorold Gosset and proved by Maryna Viazovska to be the densest packing of unit spheres in eight-dimensional space.
• For n = 4, this is a scaled copy of the 16-dimensional laminated lattice, $\Lambda_{16}$, which again is the densest known lattice packing in its dimension. In Conway and Sloane’s Sphere Packings, Lattices and Groups, this is additionally described as a section of the Leech lattice.

We’ll describe a construction of the Barnes-Wall lattices that makes their full symmetry groups apparent (with the unavoidable exception of n = 3). Unlike the other simple constructions of the Barnes-Wall lattices, which involve quadratic fields, this construction only makes use of the classical integers $\mathbb{Z}$.

### The real Clifford group and the minimal vectors

Being slightly notationally liberal (denoting a Weyl group by the name of its Dynkin diagram), let $F_4 \subset O(4)$ be the symmetry group of a standard 24-cell. It has order 1152. In particular, it contains an index-3 subgroup consisting of the 384 signed permutation matrices; the remaining 768 elements are precisely the 4-by-4 Hadamard matrices (see previous post), appropriately scaled so as to be orthogonal matrices.

Being extremely notationally liberal, for n ≥ 3 we let $F_{2^n} \subset O(2^n)$ be generated by:

• the symmetric group $S_n$, which acts naturally on $\mathbb{R}^{2^n}$ when considered as an n-fold tensor product of $\mathbb{R}^2$ with itself;
• the group $F_4$, where we expand each of the $4 \times 4$ matrices to a $2^n \times 2^n$ matrix by taking the Kronecker product with a $2^{n-2} \times 2^{n-2}$ identity matrix.

Equivalently, in the language of minimalistic quantum computation, it’s the group generated by (real orthogonal) 2-qubit gates with dyadic rational entries. (These are exactly elements of F_4 conjugated by elements of S_n.)

Technically, we’ve only defined the groups $F_{2^n}$ for n ≥ 2. For completeness, we define F_1 and F_2 to be the groups of signed permutation matrices in dimensions 1 and 2, respectively. To cover these cases, we can amend the previous definition to:

For any nonnegative integer n, $F_{2^n} \subseteq O(2^n)$ is the group of n-qubit gates generated by the dyadic rational gates acting on at most 2 qubits.

Then the minimal vectors of the Barnes-Wall lattice in dimension $2^n$ are just the images of the all-ones vector (1, 1, …, 1) under the action of this real Clifford group $F_{2^n}$. The number of such vectors is given by A006088, and the Euclidean length of each vector is $\sqrt{2^n}$.

We can then simply define the Barnes-Wall lattice to be the lattice generated by these minimal vectors! The determinant of the lattice is $2^{n 2^{n-3}}$.

### The full symmetry group

Whenever n ≠ 3, the symmetry group of the lattice is exactly the real Clifford group described above, with order given in A014115.

When n = 3, however, the symmetry group of the lattice is 270 times larger! Rather than just being $F_8$, it additionally contains arbitrary permutations of the eight coordinates, and is the Weyl group of $E_8$.

### A generator matrix

It is convenient to have an integral basis of this lattice, compatible with the described construction. In particular, the basis vectors will be a convenient subset of the minimal vectors, and moreover will lie on the vertices of the cube $[-1, +1]^{2^n}$.

Greg Kuperberg describes an elegant construction of an integral basis of minimal vectors in a scaled and rotated copy of the Barnes-Wall lattice. In particular, he takes the (n-1)-fold tensor product of the matrix [[1, 1], [1, i]] and then replaces each of the resulting (complex) entries a + bi with a 2-by-2 real matrix [[a, b], [-b, a]].

We’ll modify this construction slightly by multiplying the (n-1)-fold tensor product by the scalar 1 + i. This corresponds to scaling and rotating the lattice such that it agrees with our construction, and has the elegant property that every entry of the resulting real matrix is ±1. We’ll also permute the rows so that the matrix is symmetric.

The first six generator matrices are shown below:

The code above uses the following equivalent formulation:

• Take an M-by-M array, where $M = 2^{n-1}$, and number the rows/columns in a 0-indexed fashion.
• Define the weight of the (i, j)th entry to be popcount(i & j). That is to say, we take the size of the intersection between the set of ‘1’-bits in the binary expansions of i and j.
• Populate the (i, j)th entry with a 2-by-2 symmetric matrix according to the weight modulo 4:
• if 0 modulo 4, use the matrix [[1, 1], [1, -1]];
• if 1 modulo 4, use the matrix [[-1, 1], [1, 1]];
• if 2 modulo 4, use the matrix [[-1, -1], [-1, 1]];
• if 3 modulo 4, use the matrix [[1, -1], [-1, -1]].

(These are precisely the four real symmetric 2-by-2 (±1)-matrices which square to 2I.)