Recent developments in equiangular tight frames

Equiangular tight frames (ETFs) are optimal packings of lines through the origin. Last year, Matt and I tabulated all known existence results for ETFs. Since then, there have been a few interesting developments on the subject, so I’ll have to update the table soon. In the meantime, this blog entry covers the highlights.

First, some context: In the real case, ETFs are in one-to-one correspondence with certain strongly regular graphs (SRGs). Waldron’s paper on the subject is the standard modern treatment of this correspondence. SRGs have been an active area of research for a few decades, and Brouwer’s table provides a survey of the various known constructions. This suggests a straightforward program for constructing real ETFs: Go to Brouwer’s table, find an SRG of the requisite size, investigate the reference that constructs that graph, follow Waldron’s treatment to construct the corresponding Gram matrix, and then decompose the Gram matrix to get the desired ETF.

Now for the news:

1. Some real ETFs can be used to construct new SRGs

See this paper. The main idea is to consider a special class of ETFs with so-called centroidal symmetry, meaning the ETF vectors are all the same distance from their centroid. For such ETFs, one can construct an SRG in which each vertex corresponds to an ETF vector, and vertices are adjacent if the corresponding ETF vectors have a positive inner product. (This construction is different from the SRGs that are in one-to-one correspondence with real ETFs.) Goethals and Seidel use this basic idea to construct SRGs from what we now call real Steiner ETFs, but in the time since their paper, there have been various developments in the ETF literature. These ETFs then produce SRGs that have yet to be identified in Brouwer’s table. See this paper for a related pursuit.

2. There is no ETF of 76 vectors in

See this paper. This is the second nonexistence result for real ETFs that has gone beyond the necessary integrality conditions (see this paper for the first such result, which disproved the existence of an ETF of 1128 vectors in ). Both results actually come from the SRG community. For comparison, there is only one such nonexistence result for complex ETFs: This paper leverages various tricks from algebraic geometry to rule out ETFs of 8 vectors in . All of these results can be proved naively by running some sort of finite-time computation: For real ETFs, there are graphs on vertices, so one might check whether any of these adjacency matrices satisfies the requisite quadratic, and for complex ETFs, one can compute a Groebner basis in doubly exponential time to see if a certain complex variety (and therefore the real variety of ETF it contains) is empty. Since the naive approach is computationally burdensome, one must be clever to somehow reduce the desired result to a computationally feasible routine. I would be very interested to find new techniques for more nonexistence results.

3. There is a new infinite family of real ETFs (!)

See this paper. Considering SRGs have been actively investigated for decades, it’s somewhat surprising that certain constructions have yet to be discovered. The new construction is based on Example 7.10 in Tremain’s notes, which is colorfully depicted here:

It’s straightforward to verify that the columns of this matrix form an ETF. We generalize this construction by manipulating certain Steiner ETFs after embedding them in a higher-dimensional space, and then throwing in a lifted simplex for good measure. We call these Tremain ETFs. I’m puzzled by the number of “miracles” that make this construction work, as each of my (countless) attempts to further generalize it have failed. Perhaps this is why the construction eluded graph theorists for decades.