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

Related reading

Other constructions of the Barnes-Wall lattices appear in:

This entry was posted in Uncategorized. Bookmark the permalink.

One Response to The Barnes-Wall lattices

  1. jasonhise64 says:

    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! ( But there are probably lots of good ways to blend between spheres and cubes 🙂

Leave a Reply