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

- For n = 0, this is just the integer lattice, .
- For n = 1, the lattice is , a scaled and rotated copy of the familiar square lattice .
- For n = 2, we obtain the 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 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, , 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 .

### The real Clifford group and the minimal vectors

Being slightly notationally liberal (denoting a Weyl group by the name of its Dynkin diagram), let 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 be generated by:

- the symmetric group , which acts naturally on when considered as an n-fold tensor product of with itself;
- the group , where we expand each of the matrices to a matrix by taking the Kronecker product with a 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 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, is the group of n-qubit gates generated by the dyadic rational gates acting on

2 qubits.at most

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

We can then simply define the Barnes-Wall lattice to be the lattice generated by these minimal vectors! The determinant of the lattice is .

### 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 , it additionally contains arbitrary permutations of the eight coordinates, and is the Weyl group of .

### 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 .

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

### Related reading

Other constructions of the Barnes-Wall lattices appear in:

- Gabriele Nebe, E. M. Rains, and Neil Sloane, A Simple Construction for the Barnes-Wall Lattices (using the ring ).
- Daniele Micciancio and Antonio Nicolosi, Efficient Bounded Distance Decoders for Barnes-Wall Lattices (using the ring of Gaussian integers).
- Conway and Sloane,
*Sphere Packings, Lattices and Groups*(using Reed-Muller codes).

When I was young and naïve, I conjectured there was nothing special about the Euclidean metric. Why should the Lp exponent be 2, why shouldn’t it be arbitrary? Then I learned that 2 minimized the value of pi, which curved back toward 4 as you moved toward one or infinity. The more I learn the more naturally special 2, 3, and 4 dimensional spaces feel, and here yet again is a nugget of evidence that something happens in 3D that is absent elsewhere!

Very tangentially related, but letting the Lp metric exponent vary turned out to be a convenient way to animate a gameplay feature! (http://entropygames.net/files/shared/deformers/blockmath.gif) But there are probably lots of good ways to blend between spheres and cubes 🙂