Optimal line packings from association schemes

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 $\{\varphi_{n}\}_{n=1}^{N}$ in $\mathbb{C}^{M}$ that achieves equality in the so-called Welch bound:

$\displaystyle{\max_{m\neq n}|\langle \varphi_{m},\varphi_{n}\rangle| \geq \sqrt{\frac{N-M}{M(N-1)}}.}$

One elegant construction of ETFs relies on a group theoretic/combinatorial object called a difference set. If $G$ is a finite group and $D\subset G$ , then we say that $D$ is a difference set if the cardinality of $\{(g,h)\in D^{2}: gh^{-1}=k\}$ is independent of the choice of $k\in G\setminus\{1\}$ .

The construction of so-called harmonic ETFs is as follows. Let $G$ be a finite abelian group, and let $\hat{G}$ be the group of characters on $G$ . If $D\subset\hat{G}$ is a difference set and $1_{D}\in L^{2}(\hat{G})$ is the indicator function of $D$ , then $\{\lambda(g)\check{1}_{D}\}_{g\in G}$ is an ETF for its span, where $\lambda(g)$ denotes the left regular representation, and $\check{f}$ is the inverse Fourier transform of $f$ . 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 $M^{2}$ vectors in $\mathbb{C}^{M}$ 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 $\hat{G}$ 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 $X=\{A_{0},\ldots,A_{d}\}$ is called an association scheme if the identity is in $X$ , $A_{0}+\cdots+A_{d}$ is the all ones matrix, and $X$ spans a commutative $\ast$ -algebra.

Given a finite abelian group $G$ we can construct an association scheme by taking $A_{g}$ to be the translation operator on $L^{2}(G)$ . We will refer to $\{A_{g}\}_{g\in G}$ 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 $\mathcal{A}$ is a commutative $\ast$ -algebra, by the spectral theorem there is another basis $\{E_{j}\}_{j=0}^{d}$ for $\mathcal{A}$ consisting of the projections onto the maximal eigenspaces in $\mathcal{A}$ . If we expand a given matrix $B\in \mathcal{A}$ in both bases

$\displaystyle{B=\sum_{i=0}^{d} f(i)A_{i} = \sum_{j=0}^{d}g(j)E_{j},}$

then we can think of $g\in L^{2}(\{0,\ldots,d\})$ as the Fourier transform of $f\in L^{2}(\{0,\ldots,d\})$ . For an abelian group scheme as described above the indexing sets of $\{A_{i}\}$ and $\{E_{j}\}$ can be taken to be $G$ and $\hat{G}$ 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 $\{A_{i}\}_{i=0}^{d}$ as playing the role of the group, and the projection matrices $\{E_{j}\}_{j=0}^{d}$ play the role of the dual group.

Since the set $\{E_{j}\}$ generates $\mathcal{A}$ , it naturally has the algebraic structure that $\hat{G}$ lacks when $G$ 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 $D\subset\{0,\ldots,d\}$ we define

$\displaystyle{\mathcal{G}_{D}:= \sum_{j\in D} E_{j}.}$

Since the projections $\{E_{j}\}$ are mutually orthogonal, it is immediate that $\mathcal{G}_{D}$ is a projection. If $\mathcal{G}_{D}$ is the Gram matrix of an ETF, then we call $D$ 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 $G$ , 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 $G$ be a finite group with irreducible characters $\chi_{0},\ldots,\chi_{d}$ , and degrees $d_{0},\ldots,d_{d}$ , respectively. Then, $D\subset\{0,\ldots,d\}$ is a hyperdifference set if and only if there is a constant $C$ such that

$\displaystyle{\Big|\sum_{j\in D}d_{j}\chi_{j}(g)\Big| = C \quad\text{for all } g\in G\setminus\{1\}.\qquad (*)}$

In this case, the matrix $\mathcal{G}_{D}$ is the Gram matrix of an ETF with $|G|$ vectors in a space of dimension $\sum_{j\in D}d_{j}^{2}$ .

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 $2^{2(2k+1)}$ vectors in a space of dimension $2^{2k}(2^{2k+1}-1)$ for any positive integer $k$ .

	Jaan Parts on Polymath16, seventeenth thread…
	Jaan Parts on Polymath16, seventeenth thread…
	Jaan Parts on Polymath16, seventeenth thread…
	Jaan Parts on Polymath16, seventeenth thread…
	Jaan Parts on Polymath16, seventeenth thread…
	Jaan Parts on Polymath16, seventeenth thread…
	Jaan Parts on Polymath16, seventeenth thread…
	Tom Sirgedas on Polymath16, seventeenth thread…
	Jaan Parts on Polymath16, seventeenth thread…
	Tom Sirgedas on Polymath16, seventeenth thread…
	Tom Sirgedas on Polymath16, seventeenth thread…
	Jaan Parts on Polymath16, seventeenth thread…
	Tom Sirgedas on Polymath16, seventeenth thread…
	Tom Sirgedas on Polymath16, seventeenth thread…
	Tom Sirgedas on Polymath16, seventeenth thread…

Share this:

Like this:

Related

Leave a Reply Cancel reply