Nearly orthogonal vectors and small antipodal spherical codes

arXiv:1803.02949v1 [math.CO] 8 Mar 2018

Boris Bukh∗

Christopher Cox†

March 9, 2018

Abstract
How can d + k vectors in Rd be arranged so that they are as close to orthogonal as possible? In
particular, deﬁne θ(d, k) := minX maxx6=y∈X |hx, yi| where the minimum is taken over all collections
of d + k unit vectors X ⊆ Rd . In this paper, we focus on the case where k is ﬁxed and d → ∞.
In establishing bounds on θ(d, k), we ﬁnd an intimate connection to the existence of systems of

k+1
equiangular lines in Rk . Using this connection, we are able to pin down θ(d, k) whenever
2
k ∈ {1, 2, 3, 7, 23} and establish asymptotics for general k. The main tool is an upper bound on
Ex,y∼µ |hx, yi| whenever µ is an isotropic probability mass on Rk , which may be of independent
interest. Our results translate naturally to the analogous question in Cd . In this case, the question
relates to the existence of systems of k 2 equiangular lines in Ck , also known as SIC-POVM in
physics literature.

1

Introduction

How can a given number of points be arranged on a sphere in Rd so that they are as far from each
other as possible? This is a basic problem in coding theory; for example, the book [10] is devoted
to this problem exclusively. Such point arrangements are called spherical codes. Most constructions
of spherical codes are symmetric. Here we consider the antipodal codes, in which the points come in
pairs x, −x. In other words, we seek arrangements of d + k unit vectors in Rd so that they are as
close to orthogonal as possible. We focus on the case when k is small.
As we will see, this question relates to the problem of the existence of large families of equiangular
lines in Rk . Similarly, the analogous question for unit vectors in Cd relates to equiangular lines in
Ck , which are the mathematical underpinning of symmetric informationally complete measurements
in quantum theory [19]. Because of this, we elect to treat the real and complex cases in parallel.
Henceforth, we denote by H the underlying ﬁeld, which can be either R or C.
For H ∈ {R, C}, deﬁne the parameter
θH (d, k) := min max |hx, yi|,
X x6=y∈X

∗

Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA, USA. bbukh@math.cmu.edu.
Supported in part by Sloan Research Fellowship and by U.S. taxpayers through NSF CAREER grant DMS-1555149.
†
Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA, USA. cocox@andrew.cmu.edu.
Supported in part by U.S. taxpayers through NSF CAREER grant DMS-1555149.

1

where the minimum is taken over all collections of d + k unit vectors X ⊆ Hd . In this paper, we prove
bounds on θH (d, k) when k is ﬁxed and d → ∞.
For a collection of vectors X = {x1 , . . . , xn } ⊆ Hk , the Gram matrix is the matrix A ∈ Hn×n where
Aij = hxi , xj i. It will be easier to work with the Gram matrices than with the vectors themselves.
For a matrix A ∈ Hn×n , deﬁne oﬀ(A) := maxi6=j |Aij |. By considering Gram matrices, one can
equivalently deﬁne θH (d, k) = minA oﬀ(A) where the minimum is taken over all A ∈ H(d+k)×(d+k) with
rk(A) = d where Aii = 1 for every i and A is Hermitian and positive semideﬁnite. Our techniques
are not specialized to Hermitian, positive semideﬁnite matrices, so we also deﬁne
oﬀ H (d, k) := min oﬀ(A),
A

where the minimum is taken over all A ∈ H(d+k)×(d+k) with rk(A) = d and Aii = 1 for every i. Note
that oﬀ H (d, k) ≤ θH (d, k).
In Section 2, we establish lower bounds on oﬀ H (d, k), and in Section 3, we give constructions
to yield upper bounds on θH (d, k). Throughout both of these sections, we will show an intimate
connection between determining these parameters and the existence of large systems of equiangular
lines in Hk .
Definition 1. A system of equiangular lines in Hk is a collection of unit vectors X ⊆ Hk so that
there is some β ∈ R where |hx, yi| = β for all x 6= y ∈ X.

It is known that if X ⊆ Rk is a system of equiangular lines, then |X| ≤ k+1
and if X ⊆ Ck is a
2
system of equiangular lines, then |X| ≤ k2 .
The main results of this paper are as follows:
Theorem 2.
(a) For positive integers d, k,
oﬀ R (d, k) ≥
where αk =

√
(k−1) k+2+2
.
k(k+1)

1
,
αk (d + k) − 1

If equality holds, then there exists a system of

over Rk and d ≡ −k (mod k+1
2 ).

(b) For positive integers d, k,

oﬀ C (d, k) ≥
√

α∗k (d

k+1
2

equiangular lines

1
,
+ k) − 1

where α∗k = (k−1) k2k+1+1 . If equality holds, then there exists a system of k2 equiangular lines
over Ck and d ≡ −k (mod k2 ).
This is an improvement over the previously-known bound (which is recalled as Theorem 7 below)
when k ≤ O(d1/2 ).
The above theorem will follow as a corollary of Theorems 10 and 15, which will be proved in
Section 2. Furthermore, the following theorem, which will be proved in Section 3, will show that
equality does, in fact, hold under the stated conditions.
2

Theorem 3.
(a) If there is a system of

where αk =

k+1
2

equiangular lines in Rk and d ≡ −k (mod
oﬀ R (d, k) = θR (d, k) =

√
(k−1) k+2+2
.
k(k+1)

1
,
αk (d + k) − 1

k+1
2 ),

then

(b) If there is a system of k2 equiangular lines in Ck and d ≡ −k (mod k2 ), then
oﬀ C (d, k) = θC (d, k) =
where α∗k =

√
(k−1) k+1+1
.
k2

1
,
α∗k (d + k) − 1

The usual way of proving bounds on codes is to use linear programming. In the context of spherical
codes, the relevant linear program ﬁrst appeared in the work of Delsarte and Goethals and Seidel [9].
See [10, Chapter 2] for the general exposition, and [2] for the case of few vectors.
In contrast, we establish Theorem 2 by relating the problem to that of bounding the ﬁrst moment
of isotropic measures.
Definition 4. For H ∈ {R, C}, a probability mass µ on Hk is called isotropic if Ex∼µ|hx, vi|2 = k1 kvk2
for every v ∈ Hk . Equivalently, µ is isotropic if Ex∼µ xx∗ = k1 Ik .
We show the following:
Lemma 5.
(a) If µ is an isotropic probability mass on Rk , then
√
(k − 1) k + 2 + 2
,
Ex,y∼µ |hx, yi| ≤
k(k + 1)
with equality if and only if there exists X ⊆ Rk , a system of

satisfies µ(x) + µ(−x) = 1/ k+1
for every x ∈ X.
2



k+1
2

equiangular lines, and µ

(b) If µ is an isotropic probability mass on Ck , then

√
(k − 1) k + 1 + 1
Ex,y∼µ |hx, yi| ≤
,
k2
with equality if and only if there exists X ⊆ Ck , a system of k2 equiangular lines, and µ satisfies
µ(x) + µ(−x) = 1/k 2 for every x ∈ X.
Theorem 15 shows the connection between the above lemma and Theorem 2.

As there are systems of k+1
equiangular lines over Rk whenever k ∈ {1, 2, 3, 7, 23}, we can give
2
tight answers for inﬁnitely many d in these cases; see Corollary 17 for the exact values. See [13, 21]
for the known bounds of the size of the largest system of equiangular lines in Rk .
3

Even in the cases not covered by Theorem 3, we will still show that Theorem 2 is asymptotically
tight.
Theorem 6. Let H ∈ {R, C}. For every ǫ > 0, there is an integer k0 so that for any fixed k ≥ k0 ,
√
 (1 + ǫ) k
θH (d, k) ≤ 1 + o(1)
,
d

where o(1) → 0 as d → ∞.

that
The above theorem
√
√ will be established in multiple parts. First, Theorem 21 will show
2 k+1
k+4
θR (d, k) ≤ (1 + o(1)) d whenever k is a power of 4 and show that θR (d, k) ≤ (1 + o(1)) d for
general k. Theorem 22 will establish Theorem 6 in the case of complex numbers and show that in
this case we can take k0 = O(ǫ−40/19 ). Finally, Theorem 6 will be established fully in the case of the
reals by Theorem 26.
Acknowledgments. We thank William Martin for inspiring discussions. We also thank organizers
of the Ninth Discrete Geometry and Algebraic Combinatorics Conference, where these discussions
took place. The conference was supported by NSF grant DMS-162360.

2

Lower bounds

Basic bound and the case k = 1. We begin with a simple lower bound which has been noticed
various places in the literature, for example [1, Lemma 2.2] and [14, Lemma 3.2]. We give a proof for
completeness.
q
k
Theorem 7. For H ∈ {R, C}, if d, k are positive integers, then oﬀ H (d, k) ≥ d(d+k−1)
.
Proof. Let A ∈ H(d+k)×(d+k) with 1’s on the diagonal and rk(A) ≤ d. Then
X
X
tr(A∗ A) =
|Aij |2 = (d + k) +
|Aij |2 ≤ (d + k) + (d + k)(d + k − 1) oﬀ(A)2 .
i,j

i6=j

On the other hand, tr(A∗ A) ≥ | tr(A)|2 / rk(A) (see Proposition 12 for a proof), so
(d + k) + (d + k)(d + k − 1) oﬀ(A)2 ≥ tr(A∗ A) ≥
Rearranging these inequalities yields oﬀ(A) ≥

q

k
d(d+k−1) ,

| tr(A)|2
(d + k)2
=
.
d
d

so the same bound holds for oﬀ H (d, k).

Before moving on, we note that the above observation suﬃces to determine oﬀ H (d, 1) and θH (d, 1).
Corollary 8. For H ∈ {R, C} and for any positive integer d, oﬀ H (d, 1) = θH (d, 1) = d1 .
Proof. The lower bound follows from Theorem 7. For the upper bound, let x1 , . . . , xd+1 be the vertices
of a unit regular simplex in Rd centered at the origin. Then for all i 6= j, we have hxi , xj i = − 1d , so
θR (d, 1) ≤ 1d . As θC (d, 1) ≤ θR (d, 1), this establishes the claim.
4

Connection to isotropic measures. We now turn our attention to the general case. Throughout
the following, whenever we discus a probability mass µ on Hk , µ will be assumed to be Borel. For such
a µ, we use Ex∼µ f (x) to denote the expected value of the function f where x is distributed according
to µ. We also use Ex,y∼µ f (x, y) := Ex∼µ Ey∼µ f (x, y). When the probability mass µ is understood, we
will omit writing it. Recall that the support of µ, denoted supp(µ), is the collection of all x ∈ Hk for
which every ball centered at x has positive mass.
The following parameter will play a crucial role in our bounds.
Definition 9. For H ∈ {R, C}, let µ be a nonzero probability mass on Hk and deﬁne
LH (µ) :=

inf

y∈supp(µ)\{0}

inf

v∈Hk \{0}

Ex∼µ |hv, xi|
.
|hv, yi|

We care about the parameter LH (µ) only when µ is of a certain form. Deﬁne PH (d, k) to be the
collection of all probability masses µ on Hk for which there is a (multi)set X of d + k vectors over
Hk with span(X) = Hk and µ is the uniform distribution over X. In other words, PH (d, k) is the
collection of all probability masses µ where supp(µ) is ﬁnite, supp(µ) spans Hk and (d + k)µ(x) ∈ Z
for all x ∈ supp(µ).
We then deﬁne
SLH (d, k) := sup LH (µ).
µ∈PH (d,k)

Proposition 14 will show that we may replace the above supremum with a maximum.
Theorem 10. For H ∈ {R, C}, if d, k are positive integers, then
oﬀ H (d, k) ≥

1
.
SLH (d, k)(d + k) − 1

Proof. Let A ∈ H(d+k)×(d+k) with 1’s on the diagonal and rk(A) ≤ d. Thus dim ker A ≥ k, so there
is some N ∈ H(d+k)×k with rk(N ) = k and AN = 0. Let yi be the ith row of N , so we have
T
hv, y1 i, hv, y2 i, . . . , hv, yd+k i ∈ ker A for every v ∈ Hk . Thus, for any ﬁxed i ∈ [d + k],
X
X
0=
Aij hv, yj i = hv, yi i +
Aij hv, yj i,
j

so,
|hv, yi i| =

j6=i

X
j6=i

Aij hv, yj i ≤ oﬀ(A)

Solving for oﬀ(A), if hv, yi i =
6 0,
oﬀ(A) ≥ P

|hv, yi i|
=
j6=i |hv, yj i|



X
j6=i

|hv, yj i|.

−1
X
1
.
|hv, yj i| − 1
|hv, yi i|
j

As this bound holds for all i ∈ [d + k] and v ∈ Hk with hv, yi i 6= 0, if µ is the uniform distribution
over the (multi)set {y1 , . . . , yd+k }, we have

−1
Ex |hv, xi|
1
=
oﬀ(A) ≥
sup
sup
(d + k) − 1
.
|hv,
yi|
L
(µ)(d
+ k) − 1
H
y∈supp(µ)\{0} v∈Hk \{0}
5

Finally, as {y1 , . . . , yd+k } ⊆ Hk and rk(N ) = k, we know that span{y1 , . . . , yd+k } = Hk , and so
µ ∈ PH (d, k). As such, LH (µ) ≤ SLH (d, k), implying
oﬀ(A) ≥

1
,
SLH (d, k)(d + k) − 1

which yields the same lower bound on oﬀ H (d, k).
Thus, in order to obtain lower bounds on oﬀ H (d, k), it suﬃces to establish upper bounds on SLH (d, k).
For a matrix Q ∈ GLk (H) and a probability mass µ on Hk , let Qµ be the probability mass deﬁned
by Qµ(S) := µ(Q−1 S) for every Borel set S. Recalling that µ is isotropic if Ex∼µ xx∗ = k1 Ik , it is not
diﬃcult to see that if µ is a probability mass on Hk , then supp(µ) spans Hk if and only if there is
some Q ∈ GLk (H) for which Qµ is isotropic.
The following proposition shows that, when considering LH (µ), we may always suppose that µ is
isotropic.
Proposition 11. If µ is a probability mass on Hk and Q ∈ GLk (H), then LH (µ) = LH (Qµ).
Proof. For any y ∈ supp(Qµ) \ {0} and v ∈ Hk \ {0}, we ﬁnd
Ex∼µ |hQx, vi|
Ex∼µ |hx, Q∗ vi|
Ex∼Qµ|hx, vi|
=
=
.
|hy, vi|
|hQQ−1 y, vi|
|hQ−1 y, Q∗ vi|
As supp(Qµ) = Q supp(µ), this establishes the claim.
First moment of isotropic measures. We now focus on proving Lemma 5, which will be key in
establishing upper bounds on SLH (d, k). To do so, we will need two facts about “inﬁnite matrices”.
Let Ω be a set and f : Ω2 → H. The rank of f , denoted rk(f ), is deﬁned to be the smallest r for
P
which there are functions gi , hi : Ω → H, i ∈ [r], so that f (x, y) = ri=1 gi (x)hi (y) for every x, y ∈ Ω.
If there is no such r, deﬁne rk(f ) = ∞. Notice that if |Ω| < ∞, then the rank of f is the rank of
the matrix A deﬁned by Axy = f (x, y). Let f ∗ be deﬁned by f ∗ (x, y) = f (y, x) and f be deﬁned by
f (x, y) = f (x, y). The following inequality will be essential in the proof of Lemma 5.
Proposition 12. For H ∈ {R, C}, let f : Ω2 → H and µ be a probability mass on Ω. If rk(f ) < ∞,
then
|Ex∼µ f (x, x)|2
.
Ex,y∼µ f ∗ (x, y)f (x, y) ≥
rk(f )
Proof. For completeness, we ﬁrst give a proof when |Ω| < ∞ and µ is the uniform distribution over Ω.
In this case, let A be the matrix with Ax,y = f (x, y). Let λ1 , . . . , λrk(A) be the nonzero eigenvalues of
Prk(A)
Prk(A)
A and σ1 , . . . , σrk(A) be the nonzero singular values of A. It is well-known that i=1 |λi | ≤ i=1 σi
(see [6, Eq. (II.23)]). Therefore, by Cauchy–Schwarz,
rk(A)
∗

tr(A A) =

X
i=1

σi2

1
≥
rk(A)

rk(A)
X
i=1

σi

2

6

1
≥
rk(A)

rk(A)
X
i=1

2
| tr(A)|2
.
|λi | ≥
rk(A)

Now, for a general Ω and µ, let x1 , . . . , xn be independent samples from Ω according to µ. If f ′
denotes the restriction of f to {x1 , . . . , xn }2 , then certainly rk(f ′ ) ≤ rk(f ). Hence, from above,
2
1 X ∗
1
1X
f (xi , xj )f (xi , xj ) ≥
f (xi , xi ) .
n2
rk(f ) n
i,j

i

Taking the expectation of both sides over the random choice of the samples x1 , . . . , xn , and using that
E[X 2 ] ≥ E[X]2 for any random variable X, we obtain
n−1
1
1
2
Ex,y∼µ f ∗ (x, y)f (x, y) + Ex∼µ |f (x, x)|2 ≥
Ex∼µ f (x, x) .
n
n
rk(f )
Taking the limit n → ∞ establishes the claim.
We will require also the following observation, which generalizes the corresponding property of
Hadamard products.

Proposition 13. For H ∈ {R, C}, let f : Ω2 → H. If rk(f ) = r, then rk(f 2 ) ≤ r+1
and rk(f f ) ≤ r 2 .
2
P
Proof. Let gi , hi : Ω → H, i ∈ [r], be such that f (x, y) = ri=1 gi (x)hi (y) for every x, y ∈ Ω. As such,
X
X
′
f (x, y)2 =
gi (x)gj (x)hi (y)hj (y) =
gij
(x)h′ij (y),
i,j

i≤j

′ = 1 g g and h′ = 1 h h . Therefore, rk(f 2 ) ≤
where gii′ = gi2 , h′ii = h2i , and for i < j, gij
ij
2 i j
2 i j
Similarly,
X
X
′
f (x, y)f (x, y) =
gi (x)gj (x)hi (y)hj (y) =
gij
(x)h′ij (y),
i,j


.

r+1
2

i,j

′ = g g and h′ = h h , so rk(f f ) ≤ r 2 .
where gij
i j
i j
ij

Proof of Lemma 5. We ﬁrst establish the upper bound. For H ∈ {R, C}, let µ be an isotropic probability mass on Hk . The cases where H = R and H = C will be almost identical. We will break into
cases when necessary.
As a technical detail, we must ﬁrst assure that Prµ [x = 0] = 0. To do this, set p = 1 − Prµ [x = 0]
and notice that p > 0 as supp(µ) spans Hk . Let µ′ be the probability mass which is µ conditioned on
the event {x 6= 0}. We notice that
Ex∼µ′ |hx, vi|2 =

1
Ex∼µ|hx, vi|2 for every v ∈ Hk ,
p

and

Ex,y∼µ′ |hx, yi| =

1
Ex,y∼µ|hx, yi|.
p2

√
Therefore, if Q = pIk , then Qµ′ is isotropic and Ex,y∼Qµ′ |hx, yi| = p1 Ex,y∼µ |hx, yi|. If p < 1, then
Ex,y∼Qµ′ |hx, yi| > Ex,y∼µ|hx, yi|, and so we may replace µ by Qµ′ and upper bound Ex,y∼Qµ′ |hx, yi|.
Hence, we may assume that Prµ [x = 0] = 0 in what follows.
From now on, we will compress notation and write Ex in lieu of Ex∼µ . Set
α := Ex,y |hx, yi|.

7

For β ≥ 0, we will establish upper and lower bounds on

2
p
|hx, yi|
M (β) := Ex,y p
− β kxkkyk ,
kxkkyk

which is well-deﬁned since Pr[x = 0] = 0. For the upper bound, we begin by expanding
M (β) = Ex,y

|hx, yi|2
− 2βEx,y |hx, yi| + β 2 Ex,y kxkkyk.
kxkkyk

By Cauchy–Schwarz, recalling that Ex |hx, yi|2 = k1 kyk2 for any y ∈ Hk , we obtain
s
s
s
s
|hx, yi|2
|hx, yi|2
|hx, yi|2
1
1 kxk2 1 kyk2
Ex,y
≤ Ex,y
=
Ex
Ey
= .
Ex,y
kxkkyk
kxk2
kyk2
k kxk2 k kyk2
k
Therefore,
M (β) ≤
For the lower bound, we ﬁrst write,

2
1
− 2βα + β 2 Ex kxk .
k



M (β) = Ex,y p

|hx, yi|2 − β 2 kxk2 kyk2

(1)

(2)


kxkkyk |hx, yi| + βkxkkyk


|hx, yi|2 − β 2 kxk2 kyk2 2
≥ Ex,y
,
(1 + β)kxk3/2 kyk3/2

2
(3)

by Cauchy–Schwarz.
Set Ω = Hk \ {0}, and deﬁne f : Ω2 → H by
f (x, y) :=

|hx, yi|2 − β 2 kxk2 kyk2
.
(1 + β)kxk3/2 kyk3/2

The above shows that M (β) ≥ Ex,y f ∗ (x, y)f (x, y). We wish to apply the inequality in Proposition 12,
so we will need an upper bound on rk(f ). Deﬁne b : Ω2 → H by
b(x, y) :=

|hx, yi|2
.
kxk3/2 kyk3/2

We ﬁrst argue that rk(f ) ≤ rk(b).
Set r = rk(b) (it is clear that r < ∞), and let gi , hi : Ω → H, i ∈ [r], be functions so that
P
b(x, y) = ri=1 gi (x)hi (y). Now, deﬁne functions si , ti by

si (x) := gi (x) + β · k 1/2 · kxk1/2 · Ez kzk3/2 gi (z) , and

ti (y) := hi (y) − β · k1/2 · kyk1/2 · Ez kzk3/2 hi (z) .

We start by noting that for any ﬁxed x, y,




r
r
X
X

3/2
1/2
1/2
3/2
gi (x) kyk · Ez kzk hi (z) = kyk Ez kzk
gi (x)hi (z)
i=1

i=1

=

8

kyk1/2

kxk3/2

Ez |hx, zi|2 =

1
kxk1/2 kyk1/2 ,
k

as µ is isotropic. Similarly,
r
X
i=1




1
hi (y) kxk1/2 Ez kzk3/2 gi (z) = kxk1/2 kyk1/2 .
k

Using this, we calculate,
r
X
i=1

si (x)ti (y) =

r
X
i=1

2

1/2

gi (x)hi (y) − β kkxk
2

1/2

= b(x, y) − β kkxk

1/2

kyk

= b(x, y) − β 2 kxk1/2 kyk1/2

1/2

kyk



r
X
3/2
3/2
Ez,w kzk kwk
gi (z)hi (w)
i=1

2

Ez,w |hz, wi|

= (1 + β)f (x, y).

Hence, rk(f ) ≤ r = rk(b), so we only need an upper bound on rk(b). Here, we break into cases
depending on whether H = R or H = C. Deﬁne c : Ω2 → H by
c(x, y) :=

hx, yi
,
kxk3/4 kyk3/4

which has rk(c) = k.
Case 1. H = R. In this case, b = c2 , so by Proposition 13, we have rk(b) ≤
same inequality on rk(f ). Thus, applying Proposition 12, we bound
 


|hx, xi|2 − β 2 kxk2 kxk2 2  k + 1
M (β) ≥ Ex
2
(1 + β)kxk3/2 kxk3/2

2 

2
kxk(1 − β )  k + 1
= Ex
1+β
2




k+1
2
2
= (1 − β) Ex kxk
.
2



k+1
2

, which gives the

Combining this lower bound on M (β) with the upper bound in Equation (2), we have


2
1
(1 − β)2
2
2βα ≤ + β − k+1
Ex kxk ,
k
2
√
for all β ≥ 0. Selecting β = 1/ k + 2, we calculate
√


2
1
1
2α
2( k + 2 − 1)2
√
≤ +
−
Ex kxk
k
k + 2 k(k + 1)(k + 2)
k+2
√
1
1
2( k + 2 − 1)2
≤ +
−
,
k k + 2 k(k + 1)(k + 2)

where the last line holds because
for α in this expression yields

1
k+2

≥

√
2( k+2−1)2
k(k+1)(k+2)

2
for all k ≥ 1 and Ex kxk ≤ Ex kxk2 = 1. Solving

√
(k − 1) k + 2 + 2
.
Ex,y |hx, yi| = α ≤
k(k + 1)
9

Case 2. H = C. Here we have b = cc, so by Proposition 13, we know that rk(b) ≤ k2 . Applying
Proposition 12 and following the same steps as in Case 1 shows


2
2 2
(1 − β)2
1
2
2
Ex kxk .
M (β) ≥ (1 − β) Ex kxk /k =⇒ 2βα ≤ + β −
2
k
k
√
In this case, we select β = 1/ k + 1, which yields
√


2
1
2α
1
( k + 1 − 1)2
√
≤ +
−
Ex kxk
k
k+1
k(k + 1)
k+1
√
1
1
( k + 1 − 1)2
≤ +
−
,
k k+1
k(k + 1)
and solving for α gives

√
(k − 1) k + 1 + 1
.
Ex,y |hx, yi| = α ≤
k2

We now look at the
√
√ case of equality. √
(k−1) k+1+1
(k−1) k+2+2
k+1
.
Also
let
α(C)
=
Let α(R) =
,
β(R)
=
1/
,
k
+
2
and
N
(R)
=
2
k(k+1)
k2
√
2
β(C) = 1/ k + 1 and N (C) = k . The proof is identical over R and C except for the values of these
parameters, so for H ∈ {R, C}, set α = α(H), β = β(H) and N = N (H). Notice that α = β+(1−β)/N .
First, we establish the “if” direction. Let X be a system of N equiangular lines in Hk . It is
known1 that for any x 6= y ∈ X, |hx, yi| = β. Will show in the proof of Theorem 3, in Equation (4),
that any probability mass µ on Hk with µ(x) + µ(−x) = 1/N for all x ∈ X is indeed isotropic. Fix
such a mass µ. We calculate,
Ex,y |hx, yi| = β + (1 − β) Pr[x ∈ {±y}] = β +

1−β
= α.
N

Now, for the “only if” direction, suppose that µ is isotropic and Ex,y |hx, yi| = α. Thus, every
inequality in the proof of the upper bound must hold with equality. From these equalities, we know
the following:
• Pr[x = 0] = 0, otherwise we could construct an isotropic probability mass µ′ with Ex,y∼µ′ |hx, yi| >
Ex,y∼µ |hx, yi|, as we showed at the beginning of the proof.
• If equality holds in Equation (1), then it must be the case that kxk = kyk for µ-a.e. x, y ∈ Hk .
As µ is isotropic, we have Ex kxk2 = 1, so we know that kxk = 1 for µ-a.e. x ∈ Hk .
• If equality holds in Equation (3), then it must be the case that for µ-a.e. x, y ∈ Hk , we have
|hx, yi| ∈ {kxkkyk, βkxkkyk}. Since kxk = 1 for µ-a.e. x ∈ Hk , it follows that for µ-a.e. x, y ∈ Hk ,
|hx, yi| =
1

(
1

β

if x ∈ {±y},

otherwise.

See, for instance, [16]. We will also re-derive this in the proof of Theorem 3; see Equation (5).

10

Therefore, supp(µ) ⊆ X ∪ (−X) where X ⊆ Hk is a system of equiangular lines with |hx, yi| = β
for all x 6= y ∈ X; in particular, |X| ≤ N .
Recalling that α = β + 1−β
N ,
β+

1−β
1−β
= Ex,y |hx, yi| = β + (1 − β) Pr[x ∈ {±y}] ≥ β +
.
N
|X|

Therefore, |X| ≥ N as well, so X is a system of N equiangular lines over Hk . Additionally, as
|X| = N , this means that the inequality above is in fact equality, so µ(x) + µ(−x) = 1/N for every
x ∈ X, as claimed.
Putting everything together. We are now ready to give upper bounds on SLH (d, k) and analyze
the case of equality. To do this, it will be important to know that SLH (d, k) is actually achieved.
Proposition 14. For H ∈ {R, C} and all positive integers d, k, there is some µ ∈ PH (d, k) with
LH (µ) = SLH (d, k).
Proof. Let {µn ∈ PH (d, k) : n ∈ Z+ } be such that SLH (d, k) ≤ LH (Xn ) + 1/n for every n ∈ Z+ .
By Proposition 11, we may suppose that µn is isotropic for all n ∈ Z+ . As µn ∈ PH (d, k), let
Xn = {xn1 , . . . , xnd+k } be a (multi)set so that µn is the uniform distribution over Xn . Since µn is
1 Pd+k
n 2
2
n 2
isotropic, we know that d+k
i=1 kxi k = Ex∼µn kxk = 1, so it must be the case that kxi k ≤ d + k
for every i ∈ [d + k] and n ∈ Z+ . As such, for each i ∈ [d + k], the sequence {xni }∞
n=1 is bounded,
so it has a convergent subsequence. Hence, without loss of generality, we may suppose that {xni }∞
n=1
converges for every i ∈ [d + k] and set xi = limn→∞ xni . Let X = {x1 , . . . , xd+k } and let µ be the
uniform distribution over X. We claim that µ is isotropic. Indeed, as each µn is isotropic, for any
v ∈ Hk , we have
1
Ex∼µ |hv, xi|2 = lim Ex∼µn |hv, xi|2 = kvk2 .
n→∞
k
As µ is isotropic, it must be the case that supp(µ) spans Hk , so as X is a (multi)set of d + k vectors,
we have µ ∈ PH (d, k). Now, ﬁx any i ∈ [d + k] so that xi 6= 0 and any v ∈ Hk \ {0}. We ﬁnd


Ex∼µ |hv, xi|
Ex∼µn |hv, xi|
1
= lim
≥ lim LH (µn ) ≥ lim SLH (d, k) −
= SLH (d, k).
n→∞
n→∞
n→∞
|hv, xi i|
|hv, xni i|
n
Thus LH (µ) = SLH (d, k).
With this out of the way, we are ready to bound SLH (d, k).
Theorem 15.
(a) For positive integers d, k,

√
(k − 1) k + 2 + 2
,
SLR (d, k) ≤
k(k + 1)

and if equality holds, then there exist k+1
equiangular lines in Rk and d ≡ −k (mod
2

11


).

k+1
2

(b) For positive integers d, k,

√
(k − 1) k + 1 + 1
SLC (d, k) ≤
,
k2

and if equality holds, then there exist k 2 equiangular lines in Ck and d ≡ −k (mod k2 ).
In Section 4, we give a very diﬀerent proof that SLR (d, 2) ≤ 32 , which may be of separate interest.
This alternative proof works by circumscribing an aﬃne copy of a regular hexagon and does not use
Lemma 5.
Proof. Let H ∈ {R, C} and suppose SLH (d, k) = α. By Proposition 14, we can ﬁnd µ ∈ PH (d, k)
with LH (µ) = α; we may suppose µ is isotropic by Proposition 11. As LH (µ) = α, for every v ∈ Hk
and y ∈ supp(µ), we must have Ex |hx, vi| ≥ α|hy, vi|. By selecting v = y and averaging over all
y ∈ supp(µ), this implies that
Ex,y |hx, yi| ≥ αEy |hy, yi| = αEy kyk2 = α,
where the last equality follows from the fact that µ is isotropic. Lemma 5 then gives the upper bound
on α = SLH (d, k).

If H = R and equality holds, then as µ is isotropic, by Lemma 5, there is a system of k+1
2

equiangular lines X ⊆ Rk so that µ(x) + µ(−x) = 1/ k+1
for every x ∈ X, in particular, such a
2
system of equiangular lines must exist. Since µ ∈ PR (d, k), we know that (d + k)µ(x) ∈ Z for all


x ∈ Rk , so we must have (d + k)/ k+1
∈ Z, so d ≡ −k (mod k+1
2
2 ).
The claim is established similarly when H = C.
Theorem 2 follows by combining Theorems 10 and 15.

3

Upper bounds

In this section, we present constructions that yield upper bounds on θH (d, k).
We start by proving a general theorem which shows that in order to upper bound θH (d, k) it
suﬃces to ﬁnd an appropriate matrix. For a Hermitian matrix C, denote the largest eigenvalue of C
by λmax (C).
Lemma 16. For H ∈ {R, C}, Let C ∈ Hn×n be Hermitian with Cii = 1 and |Cij | ≤ 1 for all i, j.
If λmax (C) has multiplicity k and d ≡ −k (mod n), then
θH (d, k) ≤

n
.
λmax (C) · (d + k) − n

1
, so
Proof. As d ≡ −k (mod n), let b be so that d = nb − k. Set λ = λmax (C) and set ǫ = bλ−1
1 + ǫ = ǫbλ. It is important to note that ǫ > 0. Indeed, if C 6= In , then as tr(C) = n, we must have
λmax (C) > 1. If it happens to be the case that C = In , then k = n, so as d > 0, we have b ≥ 2.
Consider the matrix A := (1 + ǫ)Inb − ǫ(C ⊗ Jb ), where ⊗ is the Kronecker/tensor product and Jb
is the b × b all-ones matrix. Note that A is Hermitian, and A ∈ H(d+k)×(d+k) .

12

As λ = λmax (C) has multiplicity k, let N ∈ Hn×k have rk(N ) = k and CN = λN . Thus N ⊗ Jb
also has rank k and
A(N ⊗ Jb ) = (1 + ǫ)(N ⊗ Jb ) − ǫ(C ⊗ Jb )(N ⊗ Jb ) = (1 + ǫ − ǫbλ)(N ⊗ Jb ) = 0,
by the choice of ǫ. As such, rk(A) ≤ nb − k = d. Furthermore, as λ = λmax (C), we observe that A is
positive semideﬁnite. Additionally, as Cii = 1 and |Cij | ≤ 1 for all i, j, we have Aii = 1 and |Aij | ≤ ǫ
for all i 6= j. Therefore,
θH (d, k) ≤ oﬀ(A) ≤ ǫ =

n
1
=
.
bλ − 1
λ · (d + k) − n

Motivated by the reduction to isotropic measures in the previous section, our usage of Lemma 5
will roughly go as follows: we look for unit vectors x1 , . . . , xn ∈ Hk so that |hxi , xj i| is small for all
P
i 6= j and the vectors are, up to scaling, in isotropic position; that is to say i xi x∗i = λIk for some
λ ∈ R+ . In this case, if A = [x1 | · · · |xn ] ∈ Hk×n , we know that A∗ A has 1’s on the diagonal and
P
small entries oﬀ the diagonal. Furthermore, AA∗ = i xi x∗i = λIk , so A∗ A has eigenvalues λ, with
multiplicity k, and 0, with multiplicity n − k. We will then let C be an appropriately scaled version
of A∗ A and apply Lemma 16.
We will be able to execute this plan for only some values of d and k; we deal with the remaining
values using monotonicity of θ, that is θH (d, k) ≤ θH (d′ , k′ ) whenever d ≥ d′ and k ≤ k′ .
We can now apply this general construction to prove Theorem 3; namely, if large systems of
equiangular lines exist, then the lower bound in Theorem 2 is tight.
Proof of Theorem 3. Theorem 2 establishes the lower bound for all d, k, so we need establish only the
upper bound.

Let {x1 , . . . , xN } ⊆ Hk be a system of equiangular lines where N = k+1
(if H = R) or N = k2
2
(if H = C). From the Gerzon’s proof that there are at most N equiangular lines in Hk (c.f. [17,
Miniature 9]), we know that the projection matrices x1 x∗1 , . . . , xN x∗N span the space of all Hermitian
matrices in Hk×k as a vector space over R. Thus, there are constants c1 , . . . , cN ∈ R for which
P
Ik = i ci xi x∗i . Let β be the common inner product of {x1 , . . . , xN }, that is, |hxi , xj i| = β for all
i 6= j. For any ﬁxed j ∈ [N ],
1 = tr(xj x∗j ) = tr(Ik xj x∗j )
 X
X
∗
∗
ci xi xi xj xj =
ci |hxi , xj i|2
= tr
i

= cj +

X
i6=j

so for all j,

In particular, c1 = · · · = cN = c. Now,

i

2

2

ci β = (1 − β )cj +

X

ci β 2 ,

i

P
1 − β 2 i ci
.
cj =
1 − β2

X

cxi x∗i = cN,
k = tr(Ik ) = tr
i

13

so c =

k
N.

Hence,

X

xi x∗i =

i

and

P
1 − β2 N
k
i=1
=
N
1 − β2

k
N

N
Ik ,
k

(4)

=⇒ β =

r

N −k
.
kN − k

(5)

Now, let A = [x1 | · · · |xN ], so (A∗ A)ii = 1 and |(A∗ A)ij | = β for all i 6= j. Additionally,
P
N
N
∗
∗
AA∗ =
i xi xi = k Ik , so A A has eigenvalues k and 0, where the former has multiplicity k.
1
∗
N
×N
, which is Hermitian with Cii = 1 and |Cij | = 1 for all
Finally, set C := β (A A − IN ) + IN ∈ H

1 N
i, j. Furthermore, λmax (C) = β k − 1 + 1, which has multiplicity k.


(C)
= αk . By Lemma 16, if d ≡ −k (mod k+1
If H = R, substituting N = k+1
shows that λmax
N
2
2 ),
θR (d, k) ≤

1
N
=
.
λmax (C)(d + k) − N
αk (d + k) − 1

If H = C, substituting N = k2 shows that

λmax (C)
N

= α∗k . By Lemma 16, if d ≡ −k (mod k2 ),

1
N
= ∗
.
λmax (C)(d + k) − N
αk (d + k) − 1

For k ∈ {1, 2, 3, 7, 23}, there are in fact systems of k+1
equiangular lines over Rk , so in these
2
cases, we can pin down θR (d, k) precisely for inﬁnitely many values of d. We have previously mentioned
the value of θR (d, 1) in Corollary 8, so we do not restate it here.
θC (d, k) ≤

Corollary 17.
• If d ≡ −2 (mod 3), then oﬀ R (d, 2) = θR (d, 2) =

3
2d+1 .

• If d ≡ −3 (mod 6), then oﬀ R (d, 3) = θR (d, 3) =

6 √
√
.
( 5+1)d+3( 5−1)

• If d ≡ −7 (mod 28), then oﬀ R (d, 7) = θR (d, 7) =

14
5d+21 .

• If d ≡ −23 (mod 276), then oﬀ R (d, 23) = θR (d, 23) =

69
14d+253 .

Over C, the existence of k2 equiangular lines over Ck is known for numerous values of k. For
example, constructions exist for k ∈ {1, 2, . . . , 16, 19, 24, 28, 35, 48}, and, up to numerical precision,
all k ≤ 67 (see [20] for a survey). In fact, it is conjectured that there are k2 equiangular lines over Ck
for all k. Thus, conjecturally, we have the following:
Conjecture 18. For every positive integer k, if d ≡ −k (mod k2 ), then
θC (d, k) =
where α∗k =

√
(k−1) k+1+1
.
k2

1
,
α∗k (d + k) − 1

We now turn to upper bounds on θH (d, k) in the case when no system of equiangular lines of size
(if H = R) or k2 (if H = C) exists.

k+1
2

14

Definition 19. For H ∈ {R, C}, matrices B1 , . . . , Bℓ ∈ Hk×k are said to be mutually unbiased bases
√
of Hk if Bi∗ Bi = Ik for all i and every entry Bi∗ Bj has magnitude 1/ k for all i 6= j.
The following is known:
• If k is a power of 4, then there is a collection of

k
2

+ 1 mutually unbiased bases of Rk (see [7]).

• If k is a prime power, then there is a collection of k + 1 mutually unbiased bases of Ck (see [4]).
Lemma 20. For H ∈ {R, C}, if there exists a collection of ℓ mutually unbiased bases of Hk , then
whenever d ≡ −k (mod kℓ),
θH (d, k) ≤ √

kℓ
.

k(ℓ − 1) + 1 (d + k) − kℓ

Proof. Let B1 , . . . , Bℓ be a collection of mutually unbiased bases of Hk and consider the matrix
A = [B1 |B2 | · · · |Bℓ ]. From the properties of mutually orthogonal bases, we ﬁnd that AA∗ = ℓIk , so
A∗ A has eigenvalues ℓ and 0 where the former has multiplicity k. Furthermore, A∗ A has 1’s on the
√
√
diagonal and every oﬀ-diagonal entry is either 0 or has magnitude 1/ k. Set C = k(A∗ A−Ikℓ )+Ikℓ ,
so C ∈ Hkℓ×kℓ is a Hermitian matrix with Cii = 1 and |Cij | ≤ 1 for all i, j. Additionally, λmax (C) =
√
k(ℓ − 1) + 1, which has multiplicity k, so the claim follows by applying Lemma 16.
Using the above lemma, we can prove Theorem 6 over R for inﬁnitely many values of k and give
a bound that is oﬀ by a factor of at most 2 for general k.
Theorem 21. If k is a power of 4, then whenever d ≡ −k (mod k2 /2 + k),
p
k + 4 − Ω(k−1/2 )
.
θR (d, k) ≤
d
Additionally, for any fixed k,

√
2 k + 1
θR (d, k) ≤ 1 + o(1)
.
d

Proof. If k is a power of 4, then there is a collection of ℓ =
Thus, by Lemma 20, whenever d ≡ −k (mod k2 /2 + k),

k2 /2 + k

θR (d, k) ≤ 3/2
≤
k /2 + 1 (d + k) − k2 /2 − k

k
2

+ 1 mutually unbiased bases of Rk .

p

k + 4 − Ω(k−1/2 )
.
d

For a general k, let k′ be a power of 4 satisfying k ≤ k′ ≤ 4k. By monotonicity,
√
2 k + 1
′
,
θR (d, k) ≤ θR (d, k ) ≤ 1 + o(1)
d

as d → ∞.

In the case of complex numbers, we can establish Theorem 6 immediately.

15

Theorem 22. If q is a prime power, then whenever d ≡ −q (mod q 2 + q),
p
q + 2 − Ω(q −1/2 )
θC (d, q) ≤
.
d
Additionally, for any fixed k,

θC (d, k) ≤ 1 + o(1)

p

k + O(k21/40 )
.
d

Proof. If q is a prime power, then there is a collection of ℓ = q + 1 mutually unbiased bases of Ck .
Thus, whenever d ≡ −q (mod q 2 + q),
p
q + 2 − Ω(q −1/2 )
q2 + q

≤
θC (d, q) ≤ 3/2
d
q + 1 (d + q) − q 2 − q
For any k, since there is always some prime q satisfying k ≤ q ≤ k + O(k21/40 ) (see [3]), by
monotonicity, we have
p
 k + O(k21/40 )
,
θC (d, k) ≤ θC (d, q) ≤ 1 + o(1)
d

as d → ∞.

Notice that Theorem 22 implies that there is a constant c such that for any ǫ > 0, if k > cǫ−40/19 ,
then
√
 (1 + ǫ) k
,
θC (d, k) ≤ 1 + o(1)
d
which establishes Theorem 6 over the complex numbers.
We now present a more general construction of nearly orthogonal vectors which makes use of
Steiner systems and Hadamard matrices. This construction will allow us to establish Theorem 6 over
the real numbers.
Definition 23. A (2, n, ℓ)-Steiner system consists of n points and a collection of subsets of these
points, called blocks, where each block contains exactly ℓ points and any two points are contained
in exactly one block together.2 If k is the number of blocks and r is the degree of any point, it is
n−1
well-known that k = n(n−1)
ℓ(ℓ−1) and r = ℓ−1 .
Definition 24. For H ∈ {R, C}, a Hadamard matrix over H of order n is a matrix H ∈ Hn×n so that
for all i, j, |Hij | = 1 and H ∗ H = nIn . When H = C, Hadamard matrices of order n exists for all n.
When H = R, it is not known for which n Hadamard matrices of order n exist. It is known however
that such an n > 2 must be divisible by 4.
We merge Steiner systems and Hadamard matrices to obtain the following upper bound on
θH (d, k). The construction below is motivated by, and is very similar to the construction of equiangular lines given by Lemmens and Seidel [16, Theorem 3.1].
2

In standard notation, k is used in place of ℓ when discussing Steiner systems, but we opt to go against this in order
to stay consistent with the notation in this paper.

16

Lemma 25. Let H ∈ {R, C} and suppose there exists a (2, n, ℓ)-Steiner system with k blocks and
degree r. If, in addition, there exists a Hadamard matrix of order r + 1 over H, then whenever
d ≡ −k (mod n(r + 1)),
θH (d, k) ≤

n(r + 1)

.
ℓ(r + 1) − r + 1 (d + k) − n(r + 1)

Proof. Let S be a (2, n, ℓ)-Steiner system with k blocks and degree r. Let A be the point-block
incidence matrix S; that is, the rows of A are indexed by the points of S and the columns are indexed
by the blocks of S with Aij = 1 if and only if point i belongs to block j. Note, of course, that A has
n rows, each having exactly r 1’s, and k columns, each having exactly ℓ 1’s.
Also let H be a Hadamard matrix of order r + 1 over H, which is normalized so that the last
column is all 1’s. Let Hi denote the ith column of H.
From A, we construct the matrix B by replacing each 0 in A by a column vector of length r + 1
of 0’s and, for each row of A, replacing the ith 1 in that row by the column vector Hi . Note that B
is a n(r + 1) × k matrix.
We begin by noting that B ∗ B = ℓ(r + 1)Ik . Indeed, let Bi denote the ith column of B. As each
column of A contained exactly ℓ 1’s and each 1 was replaced by a column of H, Bi consists of exactly
ℓ(r + 1) entries with magnitude 1 and all other entries are 0. Thus hBi , Bi i = ℓ(r + 1). On the other
hand, for i 6= j, if A were to have a 1 in the same row in both column i and column j, then these 1’s
were replaced by different columns of H. As H is a Hadamard matrix, these columns are orthogonal,
so we also have hBi , Bj i = 0. Thus, B ∗ B = ℓ(r + 1)Ik as claimed.
On the other hand, BB ∗ has r’s on the diagonal and every oﬀ-diagonal entry has magnitude 1.
Indeed, let the rows of B be {bi,j : i ∈ [n], j ∈ [r + 1]} where bi,1 , . . . , bi,r+1 are the rows that were
formed by modifying the ith row of A. We ﬁrst note that for any i, j, bi,j consists of exactly r
entries with magnitude 1 and all other entries are 0, so hbi,j , bi,j i = r. Now, for j 6= j ′ , the rows
bi,j , bi,j ′ have all non-zeros in the same entries. Furthermore, these non-zeros correspond to two
diﬀerent rows of H ′ where H ′ is the matrix formed by deleting the last column of H (recall that we
normalized H so that the last column was all 1’s). If h′j denotes the jth row of H ′ , then we ﬁnd
that hbi,j , bi,j ′ i = hh′j , h′j ′ i = −1 as the jth and j ′ th rows of H are orthogonal. Finally, for i 6= i′ and
j, j ′ ∈ [r + 1], the ith and i′ th rows of A only had precisely one nonzero entry in common (as every
pair of points in S are contained in exactly one block together). Thus, bi,j , bi′ ,j ′ also share exactly one
nonzero entry in common, and these entries have magnitude 1, so |hbi,j , bi′ ,j ′ i| = 1. Thus, we have
(BB ∗ )ii = r and |(BB ∗ )ij | = 1 for all i 6= j, as claimed.
Set C = BB ∗ − (r − 1)In(r+1) , so C ∈ Hn(r+1)×n(r+1) is Hermitian with Cii = 1 and |Cij | ≤ 1 for
all i, j. Additionally, as B ∗ B = ℓ(r + 1)Ik , we know that λmax (C) = ℓ(r + 1) − (r − 1), which has
multiplicity k. Thus, the claim follows from Lemma 16.
Using Lemma 25, we can establish Theorem 6 in the case of the reals.
Theorem 26. For every ǫ > 0, there is a k0 so that whenever k ≥ k0 ,
√
 (1 + ǫ) k
.
θR (d, k) ≤ 1 + o(1)
d
17

In order to prove this, we require the following results:
Fact 1 (Prime number theorem for arithmetic progressions [8, Chapters 20,21]). For integers a, n
with gcd(a, n) = 1, there is a function fa,n with fa,n (x) → 0 as x → ∞ so that for any positive x,

there is a prime p ≡ a (mod n) satisfying x ≤ p ≤ 1 + fa,n (x) x.

Fact 2 (Keevash [15], Glock–Kühn–Lo–Osthus [11]). For any positive integer ℓ, there is some other
integer Nℓ so that if n ≥ Nℓ with (ℓ − 1) | (n − 1) and ℓ(ℓ − 1) | n(n − 1), then a (2, n, ℓ)-Steiner
system exists.

Fact 3 (Paley [18]). Let q be a prime power. If q ≡ 3 (mod 4), then a real Hadamard matrix of
order q + 1 exists.
Proof of Theorem 26. If we can locate a prime p ≡ 3 (mod 4) and a (2, n, ℓ)-Steiner system with
n−1
k = n(n−1)
ℓ(ℓ−1) blocks and degree ℓ−1 = p, then Fact 3 and Lemma 25 together imply that whenever
d ≡ −k (mod n(r + 1)), we have
n(r + 1)

ℓ(r + 1) − r + 1 (d + k) − n(r + 1)
1
n(r + 1)
≤
ℓ(r + 1) − r + 1 d

n n−1
ℓ−1 + 1 1
=
n+ℓ
d
s 

1
(n − ℓ)2 (n + ℓ − 1)
= k 1+
·
2
(n + ℓ) (n − 1)(ℓ − 1)
d
s 

1
1
≤ k 1+
· ,
ℓ−1
d

θR (d, k) ≤

where the last line follows as n ≥ ℓ.
Given an ǫ > 0, pick ℓ odd so that 1/(ℓ − 1) < ǫ. Consider any prime p so that p ≡ 3 (mod 4)
and p ≡ 1 (mod ℓ) and (ℓ − 1)p ≥ Nℓ , where Nℓ is as in Fact 2. Set n = 1 + (ℓ − 1)p.
n(n−1)
p−1 
′
is an integer by the choice of p.
We notice that n−1
ℓ−1 = p, and also that k := ℓ(ℓ−1) = p p − ℓ
By Fact 2, there exists a (2, n, ℓ)-Steiner system with k′ blocks and degree p. By Fact 1, for any
suﬃciently large k, we can ﬁnd a suitable prime p for which k ≤ k′ ≤ (1 + ǫ)k, so by monotonicity
and the remark above,
√
 (1 + ǫ) k
′
,
θR (d, k) ≤ θR (d, k ) ≤ 1 + o(1)
d
as d → ∞.

4

An alternative proof that SLR (d, 2) ≤

2
3

Here we present an alternative proof of the upper bound on SLR (d, 2). We have been unable to
generalize this proof to get a bound on SLR (d, k) for any other k.
The proof hinges on the following result, which was proved by Golab [12] and reﬁned by Besicovitch [5].
18

Lemma 27. If C ⊆ R2 is compact, convex and centrally-symmetric, and H is a centrally-symmetric
regular hexagon, then there is Q ∈ GL2 (R) so that QH circumscribes C.

Proof that SLR (d, 2) ≤ 32 . Suppose µ ∈ PR (d, 2), and let C be the convex hull of supp(µ)∪(− supp(µ)),
so as supp(µ) is ﬁnite, we know that C is compact, convex and centrally-symmetric. Let H be the
hexagon centered at the origin with distance 2 between its parallel edges, as shown in Figure 1. By the
lemma, there is Q ∈ GL2 (R) such that QH circumscribes C. We label the top three lines bounding
H as ℓ1 , ℓ2 , ℓ3 where ℓi = {x ∈ R2 : hx, vi i = 1}.
v2

ℓ2
v1

v3

Q−1

C′

C
QH

ℓ3

H

ℓ1

Figure 1: (Left) C circumscribed by QH. (Right) The result of applying Q−1 to C and QH. In this
image, v1 , v2 , v3 are unit vectors.
Set µ′ = Q−1 µ and C ′ = Q−1 C, so C ′ is the convex hull of supp(µ′ ) ∪ (− supp(µ′ )) and H
circumscribes C ′ . Now, consider the maximization problem:
max
x∈H

3
X
i=1

|hx, vi i|.

P
As 3i=1 |hx, vi i| is a convex function and H is also convex, the maximum occurs at a vertex of H.
Thus, if x
b denotes such an optimal solution, without loss, x
b ∈ ℓ1 ∩ ℓ2 , so hb
x, v1 i = hb
x, v2 i = 1 and
P3
hb
x, v3 i = 0. We conclude that i=1 |hx, vi i| ≤ 2 for every x ∈ H.
Therefore, as supp(µ′ ) ⊆ C ′ ⊆ H,
3
X
i=1

2
Ex∼µ′ |hx, vi i| ≤ 2 =⇒ Ex∼µ′ |hx, vi i| ≤ , for some i ∈ [3].
3

Without loss, suppose that Ex∼µ′ |hx, v1 i| ≤ 32 . Finally, as H circumscribes C ′ , for each edge of H,
there is some vertex of C ′ lying on this edge. In other words, there is some y ∈ supp(µ′ ) for which
|hy, v1 i| = 1, so
Ex∼µ′ |hx, v1 i|
2
≤ .
LR (µ) = LR (µ′ ) ≤
|hy, v1 i|
3

5

Concluding remarks and open problems

• Because we rely on the existence of designs, the dependence of k0 on ǫ in Theorem 26 is poor. It
would be of interest to improve this dependence.
19

• When considering upper bounds, we focused on θH (d, k) instead of oﬀ H (d, k). For constructions for
the latter, one could rephrase Lemma 16 to read: Let C ∈ Hn×n with Cii = 1 and |Cij | ≤ 1 for all
i, j and let λ be any eigenvalue of C with λ ∈ H. If λ has multiplicity k and d ≡ −k (mod n), then
oﬀ H (d, k) ≤

n
.
λ · (d + k) − n

This could lead to improved upper bounds on oﬀ H (d, k) which may not hold for θH (d, k).

• Suppose k is such that no system of k+1
equiangular lines exists in Rk ; by how much can the
2
lower bound in Theorem 2 be improved?
• What is θR (d, 4)? Theorem 21 shows that θR (d, 4) /
It would be interesting to close this gap.

2.4
d

and Theorem 2 shows that θR (d, 4) '

2.139
d .

• How small can ǫ be so that there is some set of 2d + k unit vectors X ⊆ Rd with hx, yi √
≤ ǫ for all
k/2

x 6= y ∈ X? Deﬁne θ ′ (d, k) to be this smallest ǫ. Certainly θ ′ (d, k) ≤ θR (d, ⌈k/2⌉) ≈ d for a
ﬁxed k; however, we have be unable to prove matching lower bounds. Using the linear programming
method of Delsarte, Goethals and Seidel [9], we can show that θ ′ (d, k) ≥ (1 − o(1)) dk2 for a ﬁxed k,
but it seems unlikely that such an approach will be able to improve this lower bound. Unfortunately,
the methods in this paper do not appear to be apt to approach this question either.

P
p 1/p , i.e. the Lp norm of the
• For a matrix A ∈ Hn×n and p > 0, deﬁne oﬀ p (A) :=
i6=j |Aij |
oﬀ-diagonal entries of A. We then deﬁne oﬀ pH (d, k) := minA oﬀ p (A) where the minimum is taken
over all A ∈ H(d+k)×(d+k) with Aii = 1 for all i and rk(A) = d. In this context, we can interpret
oﬀ H (d, k) as oﬀ ∞
H (d, k).
For 2 ≤ p ≤ ∞, by following the arguments in this paper, one can relate the problem of lowerbounding oﬀ pH (d, k) to ﬁnding upper bounds on Ex,y∼µ |hx, yi|q where 1p + 1q = 1 and µ is an isotropic
probability mass on Hk . We conjecture the following:

√
Conjecture 28. For a positive integer k, set β = 1/ k + 2 and N = k+1
2 . If 1 ≤ q ≤ 2 and µ is
an isotropic probability mass on Rk , then
Ex,y∼µ |hx, yi|q ≤ β q +

1 − βq
,
N

with equality if and only if there is X ⊆ Rk , a system of N equiangular lines, and µ satisfies
µ(x) + µ(−x) = 1/N for every x ∈ X.
We also conjecture the natural analogue when R is replaced by C.

References
[1] N. Alon. Perturbed identity matrices have high rank: proof and applications. Combinatorics,
Probability and Computing, 18(1-2):3–15, 2009.
[2] J. T. Astola. The Tietäväinen bound for spherical codes. Discrete Appl. Math., 7(1):17–21, 1984.
20

[3] R. C. Baker, G. Harman, and J. Pintz. The diﬀerence between consecutive primes. II. Proceedings
of the London Mathematical Society. Third Series, 83(3):532–562, 2001.
[4] I. Bengtsson. Three ways to look at mutually unbiased bases. In Foundations of probability and
physics—4, volume 889 of AIP Conf. Proc., pages 40–51. Amer. Inst. Phys., Melville, NY, 2007.
[5] A. S. Besicovitch. Measure of asymmetry of convex curves. Journal of the London Mathematical
Society. Second Series, 23:237–240, 1948.
[6] R. Bhatia. Matrix analysis, volume 169 of Graduate Texts in Mathematics. Springer-Verlag, New
York, 1997.
[7] P. J. Cameron and J. J. Seidel. Quadratic forms over GF (2). Nederl. Akad. Wetensch. Proc.
Ser. A 76=Indag. Math., 35:1–8, 1973.
[8] H. Davenport. Multiplicative number theory, volume 74 of Graduate Texts in Mathematics.
Springer-Verlag, New York, third edition, 2000. Revised and with a preface by Hugh L. Montgomery.
[9] P. Delsarte, J. M. Goethals, and J. J. Seidel. Spherical codes and designs. Geometriae Dedicata,
6(3):363–388, 1977.
[10] T. Ericson and V. Zinoviev. Codes on Euclidean spheres, volume 63 of North-Holland Mathematical Library. North-Holland Publishing Co., Amsterdam, 2001.
[11] S. Glock, D. Kühn, A. Lo, and D. Osthus. The existence of designs via iterative absorption.
2016. arXiv:1611.06827.
[12] S. Golab. Some metric problems of the geometry of Minkowski. Trav. Acad. Mines Cracovie,
6:1–79, 1932.
[13] G. Greaves, J. H. Koolen, A. Munemasa, and F. Szöllősi. Equiangular lines in Euclidean spaces.
J. Combin. Theory Ser. A, 138:208–235, 2016. arXiv:1403.2155.
[14] Y. Jain, D. Narayanan, and L. Zhang. Almost orthogonal vectors. http://deepakn94.github.
io/assets/papers/paper3.pdf, 2014.
[15] P. Keevash. The existence of designs. 2014. arXiv:1401.3665.
[16] P. W. H. Lemmens and J. J. Seidel. Equiangular lines. Journal of Algebra, 24:494–512, 1973.
[17] J. Matoušek. Thirty-three miniatures, volume 53 of Student Mathematical Library. American
Mathematical Society, Providence, RI, 2010. Mathematical and algorithmic applications of linear
algebra.
[18] R. Paley. On orthogonal matrices. Journal of Mathematics and Physics, 12(1-4):311–320, 1933.
[19] J. M. Renes, R. Blume-Kohout, A. J. Scott, and C. M. Caves. Symmetric informationally
complete quantum measurements. J. Math. Phys., 45(6):2171–2180, 2004.
[20] A. D. Wiebe. Constructions of Complex Equiangular Lines. PhD thesis, Simon Fraser University,
Dec 2013. http://summit.sfu.ca/item/13765.
[21] W.-H. Yu. New bounds for equiangular lines and spherical two-distance sets. SIAM J. Discrete
Math., 31(2):908–917, 2017. arXiv:1609.01036.

21

