Optimal line packings from finite group actions

Posted on by Dustin G. Mixon

Joey Iverson recently posted our latest paper with John Jasper on the arXiv. This paper can be viewed as a sequel of sorts to our previous paper, in which we introduced the idea of hunting for Gram matrices of equiangular tight frames (ETFs) in the adjacency algebras of association schemes, specifically group schemes. In this new paper, we focus on the so-called Schurian schemes. This proved to be a particularly fruitful restriction: We found an alternate construction of Hoggar’s lines, we found an explicit representation of the “elusive” 7\times 36 packing from the real packings paper (based on a private tip from Henry Cohn), we found an 11\times 66 packing involving the Mathieu group M_{11} (this one beating the corresponding packing in Sloane’s database), we found some low-dimensional mutually unbiased bases, and we recovered nearly all small sized ETFs. In addition, we constructed the first known infinite family of ETFs with Heisenberg symmetry; while these aren’t SIC-POVMs, we suspect they are related to the objects of interest in Zauner’s conjecture (as in this paper, for example). This blog entry briefly describes the main ideas in the paper.

Let G act on the finite set X. This determines an action of G on X\times X, and each orbit \mathcal{O} of this action corresponds to an X\times X matrix A_\mathcal{O} of zeros and ones supported on \mathcal{O}. These matrices span the vector space of G-stable matrices, that is, the X\times X complex matrices M such that M_{g\cdot x,g\cdot y}=M_{x,y} for all g\in G and x,y\in X. If G acts transitively on X, then the adjacency matrices A_\mathcal{O} form a (not necessarily commutative) association scheme. Indeed, one of the adjacency matrices is identity since G acts transitively on X. Next, the orbits partition X\times X, and so the adjacency matrices sum to the all-ones matrix. The orbit of (x,y) is the transpose of the orbit of (y,x). Finally, G-stable matrices are closed under multiplication, regardless of whether the action is transitive (just write out the (g\cdot x,g\cdot y) entry of the product and perform a change of variables). The association schemes that arise in this way are called Schurian, and if the scheme is commutative, we say (G,H) is a Gelfand pair, where H is the stabilizer of some x_0\in X.

The spectral theorem affords any commutative association scheme with another useful basis: the orthogonal projections onto the common eigenspaces of the members of \mathcal{A}. Furthermore, every orthogonal projection in \mathcal{A} can be expressed as a sum of these “primitive” projections, meaning there are only finitely many Gram matrices of tight frames in \mathcal{A} to consider. In the case of a Schurian scheme, the primitive projections can be expressed in terms of the characters of G. In fact, one may construct projection matrices from the characters even in the noncommutative case, but they will no longer form a basis for \mathcal{A}.

In the past, folks have constructed so-called group frames by spinning a vector v with the representation of some group G. If H fixes v under this action, then you might reduce to a frame of size |G|/|H| by removing the copies, resulting in a homogeneous frame. It turns out that the corresponding Gram matrix is G-stable with X=G/H, and every positive semidefinite G-stable X\times X matrix is the Gram matrix of a homogeneous frame. One may also consider projective reduction, in which the span of v is invariant under the action of a subgroup K. Readers who are familiar with SIC-POVMs recognize projective reduction as naturally arising from scalars in the Heisenberg group. Overall, projective reduction ended up playing a key role in each of the new constructions we provide.

I’ll conclude with a brief description of our new infinite family of ETFs with Heisenberg symmetry. Let A be a finite abelian group of odd order, and define H to be the set A\times\hat{A}\times C_{\exp(A)}, where \exp(A) is the exponent of A. Then we may define multiplication in H using a symplectic form over K=A\times\hat{A} to obtain the Heisenberg group over A. The symplectic group \mathrm{Sp}(K) over A is the group of automorphisms of K that fix the symplectic form. In this paper, we prove that (H\rtimes\mathrm{Sp}(K),\mathrm{Sp}(K)) is a Gelfand pair, and we find Gram matrices of tight frames in the corresponding adjacency algebra whose projective reductions are ETFs. We conclude the paper with explicit constructions of the corresponding group frames. Again, we are very interested to find any relationship with SIC-POVMs, though it seems that any correspondence may require A to be cyclic.

Leave a comment