Joey Iverson recently posted our paper with John Jasper on the arXiv. As the title suggests, this paper explains how to construct optimal line packings (specifically, equiangular tight frames) using association schemes. In particular, we identify many schemes whose adjacency algebra contains the Gram matrix of an ETF. This unifies several existing constructions, and also enabled us to construct the first known infinite family of ETFs that arise from nonabelian groups.
John is on the job market this year, and when reading his research statement, I was struck by his discussion of our paper, so I asked him to expand his treatment to a full blown blog entry. Without further ado, here is John’s guest blog post (which I’ve lightly edited for hyperlinks and formatting):
An equiangular tight frame (ETF) is a set of unit vectors in that achieves equality in the so-called Welch bound:
One elegant construction of ETFs relies on a group theoretic/combinatorial object called a difference set. If is a finite group and , then we say that is a difference set if the cardinality of is independent of the choice of .
The construction of so-called harmonic ETFs is as follows. Let be a finite abelian group, and let be the group of characters on . If is a difference set and is the indicator function of , then is an ETF for its span, where denotes the left regular representation, and is the inverse Fourier transform of . A frame generated by the orbit of a vector under the action of a group representation is called a group frame. (See this book chapter for more information about group frames.)
It is natural to ask whether nonabelian groups can be used in a similar way to construct ETFs. Indeed, the most famous open problem in the theory of ETFs, Zauner’s conjecture, asks for an ETF with vectors in given as a group frame under the action of the Heisenberg group. The main obstruction is the fact that for nonabelian groups, the Pontryagin dual does not naturally form a group. Thus, it is not immediately clear what could stand in for a difference set. Our approach involves generalizing beyond nonabelian groups to association schemes.
A collection of 0-1 matrices is called an association scheme if the identity is in , is the all ones matrix, and spans a commutative -algebra.
Given a finite abelian group we can construct an association scheme by taking to be the translation operator on . We will refer to as an abelian group scheme. Not all association schemes arise in this way, and thus association schemes can be seen as a generalization of abelian groups. Moreover, we can do harmonic analysis on association schemes, as we shall see.
Since is a commutative -algebra, by the spectral theorem there is another basis for consisting of the projections onto the maximal eigenspaces in . If we expand a given matrix in both bases
then we can think of as the Fourier transform of . For an abelian group scheme as described above the indexing sets of and can be taken to be and respectively. With this identification the current definition of the Fourier transform is identical to the usual one. Thus, in a general association scheme we can think of the 0-1 matrices as playing the role of the group, and the projection matrices play the role of the dual group.
Since the set generates , it naturally has the algebraic structure that lacks when is a nonabelian group. This allows us to define a hyperdifference set, which generalizes the concept of a difference set to the setting of association schemes. For any subset we define
Since the projections are mutually orthogonal, it is immediate that is a projection. If is the Gram matrix of an ETF, then we call a hyperdifference set. See our recent paper for all the details on the construction of ETFs from association schemes.
In the case of abelian group schemes, hyperdifference sets are exactly difference sets, but association schemes and hyperdifference sets generalizes more than just harmonic ETFs. Indeed, any real ETF with centroidal symmetry (see this paper) is an instance of this construction, as are the ETFs constructed by Renes and Strohmer. But our goal is to use nonabelian groups to make ETFs, so let’s get on with it.
Given a finite nonabelian group , one can construct an association scheme called the group scheme. This generalizes the above construction of abelian group schemes, but the construciton is more complicated. However, the group scheme allows us to generalize the construction of harmonic ETFs to nonabelian groups. Indeed, we have the following characterization of hyperdifference sets: Let be a finite group with irreducible characters , and degrees , respectively. Then, is a hyperdifference set if and only if there is a constant such that
In this case, the matrix is the Gram matrix of an ETF with vectors in a space of dimension .
There are several known infinite families of difference sets in abelian groups, and thus there are infinite families of harmonic ETFs. However, until our recent paper, there was no known infinite family of ETFs constructed as group frames generated by a nonabelian group. In our construction the groups are formed by a “twisted” cross product of two vector spaces over the field with two elements. It turns out that these are instances of Suzuki 2-groups (see this paper). We then construct a set of irreducible characters satisfying above, thus giving a hyperdifference set in the group scheme. In the end, this gives us ETFs with vectors in a space of dimension for any positive integer .