Packings in real projective spaces

There has been a lot of work recently on constructing line packings that achieve equality in either the Welch bound or the orthoplex bound. It has proven much harder to pack in regimes where these bounds are not tight. To help fill this void, about a month ago, I posted a new paper with Matt Fickus and John Jasper on the arXiv. We provide a few results to approach this case, which I outline below.

1. The minimal coherence of 6 unit vectors in $\mathbb{R}^4$ is 1/3.

The Welch bound is known to not be tight whenever $n$ lies strictly between $d+1$ and $d+\sqrt{2d+1/4}+1/2$ (see the next section for a proof sketch). As such, new techniques are required to prove optimality in this range. We leverage ideas from real algebraic geometry to show how to solve the case of $d+2$ vectors in $\mathbb{R}^d$ for all sufficiently small $d$ . For example, our method provides a new proof of the optimality of 5 non-antipodal vertices of the icosahedron in $\mathbb{R}^3$ , as well as the optimality of Sloane’s packing of 6 lines in $\mathbb{R}^4$ .

Our method hinges on an application of the Tarski–Seidenberg theorem, whose statement requires a definition: A semialgebraic set is any subset of a finite-dimensional real vector space that can be expressed in terms of a finite collection of polynomial equalities and inequalities. For example, the positive definite cone is semialgebraic by Sylvester’s criterion.

Tarski–Seidenberg Theorem. Any projection of a semialgebraic set is semialgebraic.

The proof of this theorem amounts to an explicit algorithm that finds the polynomial relations of the projection of a given semialgebraic set onto a hyperplane. One can then iterate this to project onto any lower-dimensional subspace. Notice that our packing problem is equivalent to finding the smallest $x$ for which there exists a Gram matrix $G$ of $n$ unit vectors in $\mathbb{R}^d$ such that the largest squared off-diagonal entry is at most $x$ . Since the set of all such $(G,x)$ forms a semialgebraic set, one may run the Tarski–Seidenberg theorem to project onto the $x$ coordinate. The projection will have the form $[B,\infty)$ , and so one may conclude that $\sqrt{B}$ is the tight lower bound on coherence in this case.

While this provides a finite-time algorithm for solving the packing problem, you wouldn’t want to solve the problem this way, since the Tarski–Seidenberg algorithm is way too slow. Instead, you’d use alternatives like cylindrical algebraic decomposition (CAD), but even this takes double exponential time in the number of variables. Considering our Gram matrix has $O(n^2)$ variables, we are inclined to use more information about our problem to decrease this number of variables. To this end, you can show that for an optimal packing, the locations in the Gram matrix that achieve coherence correspond to the adjacency matrix of a so-called $d$ -secure graph, which tend to have $\Omega(d^2)$ edges. When $n$ is close to $d$ , e.g., $n=d+2$ , this reduces the number of variables to $O(n)$ , which is far more palatable.

We used this technique to solve $(d,n)=(3,5)$ and $(4,6)$ . We applied Mathematica’s built-in implementation of CAD, and the code is available here and here. Both codes are fast, proving tight bounds in less than 30 seconds. We found that the runtime was extremely sensitive to the order of variables, and we didn’t have the patience to work out the case where $(d,n)=(4,6)$ . I mentioned this in a talk at SIAM AG17, and I was informed of even faster alternatives to CAD. We are currently investigating whether those alternatives will make larger cases more accessible.

2. The Welch bound is within a constant factor of optimal in the Gerzon range.

Recall that unit vectors achieve equality in the Welch bound only if they are equiangular. By lifting each vector $x$ to its outer product $xx^\top$ , one can see that the Gram matrix of these outer products is the entrywise square of the original Gram matrix. By equiangularity, the Gram matrix of the outer products has the form $aI+bJ$ , where $J$ is the matrix of all ones and $a,b>0$ (provided $d>1$ ). As such, the Gram matrix is positive definite, meaning the outer products are not linearly dependent. Since these outer products lie in the $d(d+1)/2$ -dimensional vector space of symmetric matrices, this then implies that the Welch bound is tight only if $n\leq d(d+1)/2$ . Considering Welch bound equality is closed under the Naimark complement, this then produces a lower bound on the number of vectors in the nontrivial case where $1<d<n-1$ . Combined, we get the so-called Gerzon range:

$d+\sqrt{2d+1/4}+1/2 \leq n \leq d(d+1)/2$

Even in this range, it is known that Welch bound equality is an uncommon occurrence since certain integrality conditions must be satisfied. As such, it is interesting to consider how close the bound is to being tight in this range. To this end, we provide a linear-time constant-factor approximation algorithm for packing. In particular, given any $(d,n)$ in the Gerzon range, we provide an explicit packing whose coherence is guaranteed to be no larger than 49 times the Welch bound. Our construction is based on the following complex construction, which in turn is based on a famous character sum estimate due to Andre Weil:

Theorem. Let $\psi$ be a nontrivial additive character of $\mathbb{F}_q$ . For each $f\in\mathbb{F}_q[x]$ , define

$\displaystyle{\varphi_f(x)=\frac{1}{\sqrt{q}}\cdot\psi(f(x)) \qquad \forall x\in\mathbb{F}_q.}$

For each $r<\mathrm{char}(\mathbb{F})$ , let $S(r)$ denote the $f$ ‘s such that $f(0)=0$ and $\mathrm{deg}(f)\leq r$ . Then

$\displaystyle{|\langle \varphi_f,\varphi_g\rangle| \leq \frac{r-1}{\sqrt{q}} \qquad \forall f,g\in S(r),~f\neq g.}$

We convert this packing to a real packing by replacing each complex entry with a 2-by-2 matrix involving its real and imaginary parts. This conversion doesn’t hurt the coherence. Also, in cases where $d$ is not twice a prime, we pad with zeros, but this doesn’t hurt too much thanks to Bertrand’s postulate. Surprisingly, it was hardest to analyze the left-most edge of the Gerzon range, and we had to play interesting games with Naimark complements to make good constructions.

We did not attempt to optimize our analysis, and judging by Sloane’s database, we suspect the optimal constant is less than 2. We think follow-on work along these lines would make a nice project for a student.

3. We found two new infinite families of locally optimal packings.

Since proving global optimality is so hard, we also looked into how to prove local optimality. We can reformulate the problem as minimizing $\|X-I\|_\infty$ subject to $X$ being in the manifold of Gram matrices of spanning $n$ -packings in $\mathbb{R}^d$ . To see how to prove local optimality of a given packing, considering the following illustration:

local

We want to show that $x$ is a local minimizer of $f$ subject to the manifold $\mathcal{M}$ . To this end, we can locally model the sublevel set and manifold (left) with the descent cone and tangent space (right). If 0 is the unique member of the intersection between the descent cone and the tangent space (which can be certified using the dual linear program provided the descent cone is a polytope), then $x$ is a local minimizer.

To use this theory, we studied the packings in Sloane’s database, and we observed some interesting patterns. For example, some of Sloane’s putatively optimal packings arise by removing a vector from an equiangular tight frame (ETF). Also, in the case where $n=2d$ , his putatively optimal packings are frequently orthobiangular, and can be constructed by lifting smaller ETFs. We show that all such packings are locally optimal by constructing the appropriate dual certificates. Furthermore, some of these packings beat Sloane’s putatively optimal packings. See Table 1 in the paper for the improvements (denoted by stars).

4. Many of Sloane’s putatively optimal packings are tight frames with few angles.

When looking through Sloane’s database, we found that surprisingly many of the packings happen to form tight frames. Furthermore, most of these tight frames have few angles. This suggests a generalization of the Welch bound in which equality is characterized by a generalization of ETFs. In the absence of this more general theory, we developed short descriptions of each of Sloane’s putatively optimal packings that happen to be tight with small angle sets. Most of these packings involve classical objects like polytopes or lattices, incidence structures like Steiner ETFs, or “marriages” likes those introduced by Bodmann and Haas.

We were able to generalize some of the constructions based on incidence structures to infinite families whose coherence is a factor of $1+o(1)$ away from the Welch bound. We were able to prove that these orthobiangular tight packings are optimal when restricting to packings that are orthobiangular and tight. It would be interesting to see some computational evidence of their optimality for larger dimensions than those investigated by Sloane.

	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