The last decade has seen a surge of progress in the line packing problem, where the objective is to pack n points in RP d-1 or CP d-1 so that the minimum distance is maximized. Indeed, while instances of this problem date back to Tammes [1] and Fejes Tóth [2], the substantial progress in recent days has been motivated by emerging applications in compressed sensing [3], digital fingerprinting [4], quantum state tomography [5], and multiple description coding [6]. Most progress in this direction has come from identifying new packings that achieve equality in the so-called Welch bound (see [7] for a survey), but last year, Bukh and Cox [8] discovered a completely different bound, along with a large family of packings that achieve equality in their bound.
Focusing on the complex case, let X = {x i } i∈[n] be a sequence of unit vectors in C d , and define coherence to be µ(X) := max 1≤i<j≤n | x i , x j |.
Then the Buhk-Cox bound guarantees
provided n > d. The Bukh-Cox bound is the best known lower bound on coherence in the regime where
While the other lower bounds can be proven using Delsarte's linear program [9], the proof of the Bukh-Cox bound is completely different: it hinges on an upper bound on the first moment of isotropic measures.
In the present paper, we provide an alternate proof of the Bukh-Cox bound. We start by isolating a lemma of Bukh and Cox that identifies a fundamental duality between the coherence of n = d + k unit vectors in d dimensions and the entrywise 1-norm of the Gram matrix of n k -tight frames of n vectors in k dimensions. Next, we illustrate the power of this lemma by using it to find a new proof of the Welch bound. Finally, we combine the lemma with ideas from Delsarte's linear program to obtain a new proof of the Bukh-Cox bound. This new proof helps to unify the existing theory of line packing, and hopefully, it will spur further improvements (say, by leveraging ideas from semidefinite programming [10]).
Let X = {x i } n i=1 denote any sequence in C d . By abuse of notation, we identify X with the d × n matrix whose ith column is x i . We say X is a c-tight frame if XX * = cI. Let N (d, n) denote the set of matrices in C d×n with unit norm columns, and let T (d, n) denote the set of matrices in C d×n corresponding to n d -tight frames. Define
(Indeed, the maximum exists by a compactness argument.) We say X ∈ N (d, n) is equiangular if there exists a constant c such that | x i , x j | = c for every 1 ≤ i < j ≤ n. With this nomenclature, we are ready to state the following lemma of Bukh and Cox:
Furthermore, X minimizes µ(X) over N (d, n) if X is equiangular and there exists
Bringing y i 2 2 to the left hand side of (2) and taking absolute values, we have that
where (3) uses the triangle inequality and ( 4) is by the definition of coherence. Using (4) and
Thus, we conclude that
This proves the bound. Considering (2), equality occurs in ( 3), ( 4) and ( 5) when X is equiangular and (i)-(iii) holds.
Theorem 2. For all Y ∈ T (k, n) we have
Equality is achieved if and only if Y is an equiangular tight frame.
Proof. First we separate the diagonal part of Y * Y 1 and use the Cauchy-Schwarz inequality,
Noting that the the sum in ( 7) is (almost) Y * Y 2 F and once again using the Cauchy-Schwarz inequality,
Putting this back into (7) we obtain the inequality Equality in (6) depends on the existence of equiangular tight frames of n vectors in C k . The Gerzon bound says that if Y forms an equiangular tight frame of n vectors in C k , then n ≤ k 2 [7]. This gives the bound k ≥ 1/2 + √ 1 + 4d/2 as a necessary condition for Y to be an equiangular tight frame. On the other hand, if Y in Lemma 1 is an equiangular tight frame, then X is also an equiangular tight frame since X and Y are Naimark complements [11]. In particular, this gives the upper bound k ≤ d 2 -d as a necessary condition for Y to be equiangular, because the Gerzon bound applied to X gives the requirement that n ≤ d 2 .
Being within the range
an open question. Some equiangular tight frames are known to exist, by construction, for certain values of n and k. An overview of the known constructions can be found in [7]. On the other hand, there are known values of n and k for which equiangular tight frames cannot exist. One such example is the case when n = 8 and k = 3 [12]. In particular, equality in the Welch bound is achieved for some values of n and k which satisfy k + 1 ≤ n ≤ k 2 , but not necessarily achieved at all values of n and k which satisfy that inequality.
By combining Lemma 1 with Theorem 2, we obtain
We now turn our attention to the range 1 ≤ k < 1/2 + √ 1 + 4d/2. Since the Gerzon bound prevents Y from being an equiangular tight frame in this range, equality in (6) cannot be achieved and a sharper bound can be obtained. The Bukh-Cox bound is an improvement in this range, and is sharp if Y is given by concatenated copies of k 2 vectors in C k which forms an equiangular tight frame. In order to apply Delsarte's linear programming ideas, we require the following special polynomials [9]:
Equality is achieved when
where Z ∈ C k×k 2 is an equiangular tight frame. 40}, along with the best known lower bounds. The black dots correspond to packings found in Sloane's database [13]. The Bukh-Cox bound is displayed in green, the Welch bound in blue, the orthoplex bound [14] in pink, and the Levenshtein bound [15] in red. In this setting, the Bukh-Cox bound is the best known lower bound for n = {8, 9}.
Proof. By continuity, we may assume y i = 0 for every i ∈ {1, • • • , n} without loss of generality. First, we normalize the columns of Y , {y i } n i=1 , by defining z i := y i / y i 2 . We obtain the desired bound considering the following linear program, inspired by Delsarte's LP bound,
Suppose we have a feasible (c 0 , c 1 , c 2 ). Then,
We now establish an upper bound for each innermost term for ∈ {0, 1, 2}. For = 0, since Q 0 (x) = 1, we have
For = 1, we have
To bound the first term of ( 16), we use Cauchy-Schwarz and the fact that Y is an n/k-tight frame:
Overall this gives the following bound for the = 1 case:
Last, we need a bound for the = 2 case. Let {e m } d2 m=1 be any orthonormal basis for the (finite) d 2 -dimensional vector space spanned by degree-4 projective harmonic polynomials in k variables. Then, by the addition formula, there is a constant C d2,k , which depends on d 2 and k, such that
Multiplying both sides of (19) by c 2 ≤ 0 then gives
Finally, returning to (13) we have
where we have used that S ≤ n 2 . The bound (12) comes from observing that the following choice of (c 0 , c 1 , c 2 ) is feasible:
This feasible choice comes from forcing f
, and solving for (c 0 , c 1 , c 2 ). Equality is achieved in inequalities ( 13), (18), (20), (21) when 1)
The proof of Theorem 4 actually generates a bound for any feasible (c 0 , c 1 , c 2 ) in the described linear program. Minimizing c 0 gives the best possible bound generated by this method. Computational experiments suggest that this particular feasible (c 0 , c 1 , c 2 ) gives the minimum c 0 . Although equality is achieved when Y is multiple copies of an equiangular tight frame of k 2 vectors in C k , the existence of such frames is an open question, and is known as Zauner's conjecture [16].
By combining Lemma 1 with Theorem 4, we obtain Bukh and Cox also provide a new bound for the case of n vectors in R d . For the real case, it suffices to adjust the special polynomials in the proof of Theorem 4 [9]. Q 0 (x) and Q 1 (x) remain the same, but Q 2 (x) is replaced with:
x + 3 (d + 2) (d + 4) .
This adjustment changes the feasible region for the linear program and leads to a different optimal (c 0 , c 1 , c 2 ), and thus a different bound for the R d case. Fig. 1 demonstrates the Bukh-Cox bound improvement over the Welch bound for small values of k in the case where the vectors are in R 6 . We illustrate the real case since, in this case, packing data is available and provided in [13].