Recent developments in equiangular tight frames, II

Equiangular tight frames (ETFs) are optimal packings of lines through the origin. At the moment, they are the subject of a rapidly growing literature. In fact, there have been quite a few updates since my last post on this subject (less than five months ago), and I’ve revamped the table of ETFs accordingly. What follows is a brief discussion of the various developments:

1. There is an ETF of 76 vectors in

See this paper. Last time, I mentioned a recent proof that there is no ETF of 76 vectors in . It turns out that a complex ETF of this size does exist. To prove this, it actually seems more natural to view the vectors as columns of a matrix whose row vectors sum to zero. As a lower-dimensional example, consider the following matrix:

Here, the columns are all possible vectors of s that sum to zero (modulo antipodes), and in this case, they happen to form an ETF for their span, namely, the orthogonal complement of the all-ones vector. ETFs like this (where the entires are all s and the row vectors sum to zero) are particularly well-suited as supersaturated designs. Unfortunately, the naive generalization of this construction fails to produce ETFs. However, a generalization of sorts does exist: There is a Steiner-type construction with the incidence matrix of any finite projective plane that contains something called a hyperoval, and one may apply a Kirkman-type rotation to make the entries all unimodular, if desired. This construction produces an infinite family of ETFs, but it’s only real in the case, which seems reasonable, considering the next example is of size , and no real ETF of this size exists.

2. Certain generalized quadrangles lead to new complex ETFs

See this paper. For this construction, first imagine taking any incidence matrix of a Steiner system, for example:

(The blank entries denote zeros.) Here, each of the 12 rows is the indicator function of a line containing 3 points, and there are a total of 9 points (columns). This particular example is the incidence matrix of an affine plane of order 3. Every point is contained in 4 lines, and so each column has squared norm 4. Also, two points determine a line, so the supports of every pair of columns overlap in exactly one entry. As such, you can think of the columns as being equal-norm and equiangular, even if you replace each 1 with an arbitrary unimodular constant. With this freedom, we can attempt to design unimodular constants in such a way that the columns of the resulting matrix form an ETF for their span. Amazingly, this is possible:

Indeed, the above columns form an ETF for a 6-dimensional subspace of . In general, one may remove the spread from something called an abelian generalized quadrangle and use the remaining incidence structure as instructions for producing such an ETF. This results in an infinite family of ETFs, most of which are real (and whose strongly regular graphs were previously discovered by Godsil). However, the complex ETFs in this infinite family are new.

3. There is no ETF of 96 vectors in

See this paper. Last time, I pointed to a similar paper which disproved the existence of real ETFs. This new paper uses similar techniques (and again, lots of computation) to establish that no real ETF exists. This is the third nonexistence result of real ETFs that goes beyond the necessary integrality conditions and Gerzon bound. Considering they are so hard to come by, I’m always happy to learn of new necessary conditions like this.

4. There are new line packings that meet the orthoplex and lifted Toth bounds (!)

See this paper and that paper. This is a slight stretch, since neither of these are ETF constructions, but they are similarly important because they are provably optimal packings of lines through the origin.

Recall that ETFs are known to be optimal line packings because they meet the Welch bound. There are actually a few lower bounds on coherence that packings might meet. For example, maximal mutually unbiased bases are known to be optimal packings because they meet the orthoplex bound. Recently, Bodmann and Haas used a completely different approach to find infinite families of packings that meet this bound in totally new dimensions. Their main idea is to take a large ETF with all unimodular entries and union it with an identity basis. Such a packing will be too large for the Welch bound be sharp (due to the Gerzon bound), but it is straightforward to show that the packing meets the orthoplex bound.

One way to prove the Welch and orthoplex bounds is to lift to the space of self-adjoint matrices, and then project onto the orthogonal complement of the identity matrix. Such a mapping will send each vector in to a “lifted traceless” real space of dimension , and the squared modulus of a given inner product in the original space can be expressed in terms of an inner product in the new space (no modulus). Through this mapping, line packings are converted into spherical codes, and so the Rankin bound may be applied to the lifted traceless space to produce bounds on line packings. In the special case where , the lifted traceless space is 3-dimensional, and spherical codes in this dimension also satisfy the so-called Toth bound. This bound is known to be sharp in the case of the equilateral triangle, the regular tetrahedron, the regular octahedron, and the regular icosahedron. Furthermore, each of these correspond to an optimal line packing in (the last of these was recently established by Casazza and Haas).