Equiangular lines and spherical codes in Euclidean space

Abstract

A family of lines through the origin in Euclidean space is called equiangular if any pair of lines defines the same angle. The problem of estimating the maximum cardinality of such a family in $\mathbb {R}^n$ was extensively studied for the last 70 years. Motivated by a question of Lemmens and Seidel from 1973, in this paper we prove that for every fixed angle $\theta$ and sufficiently large $n$ there are at most $2n-2$ lines in $\mathbb {R}^n$ with common angle $\theta$. Moreover, this bound is achieved if and only if $\theta = \arccos \frac{1}{3}$. Indeed, we show that for all $\theta \ne \arccos {\frac{1}{3}}$ and and sufficiently large n, the number of equiangular lines is at most 1.93n. We also show that for any set of k fixed angles, one can find at most $O(n^k)$ lines in $\mathbb {R}^n$ having these angles. This bound, conjectured by Bukh, substantially improves the estimate of Delsarte, Goethals and Seidel from 1975. Various extensions of these results to the more general setting of spherical codes will be discussed as well.

1 Introduction

A set of lines through the origin in $n$-dimensional Euclidean space is called equiangular if any pair of lines defines the same angle. Equiangular sets of lines appear naturally in various areas of mathematics. In elliptic geometry, they correspond to equilateral sets of points, or, in other words, to regular simplexes. These simplexes were first studied 70 years ago [14], since the existence of large regular simplexes leads to high congruence orders of elliptic spaces, see [4, 15, 20]. In frame theory, so-called Grassmannian frames “are characterised by the property that the frame elements have minimal cross-correlation among a given class of frames” [16]. It turns out that optimal Grassmannian frames are equiangular; hence searching for equiangular sets of lines is closely related to searching for optimal Grassmannian frames, see [16]. In the theory of polytopes, the convex hull of the points of intersection of an equiangular set of lines with the unit sphere is a spherical polytope of some kind of regularity, see [7].

It is therefore a natural question to determine the maximum cardinality $N(n)$ of an equiangular set of lines in $\mathbb {R}^n$. This is also considered to be one of the founding problems of algebraic graph theory, see e.g. [13, p. 249]. While it is easy to see that $N(2) \le 3$ and that the three diagonals of a regular hexagon achieve this bound, matters already become more difficult in 3 dimensions. This problem was first studied by Haantjes [14] in 1948, who showed that $N(3) = N(4) = 6$ and that an optimal configuration in 3 (and 4) dimensions is given by the 6 diagonals of a convex regular icosahedron. In 1966, van Lint and Seidel [20] formally posed the problem of determining $N(n)$ for all positive integers $n$ and furthermore showed that $N(5) = 10$, $N(6) = 16$ and $N(7) \ge 28$.

A general upper bound of $\genfrac(){0.0pt}1{n+1}{2}$ on $N(n)$ was established by Gerzon (see [19]). Let us outline his proof. Given an equiangular set of m lines in $\mathbb {R}^n$, one can choose a unit vector $x_i$ along the ith line to obtain vectors $x_1, \dots , x_m$ satisfying $\left\langle x_i, x_j \right\rangle \in \{-\alpha ,\alpha \}$ for $i \ne j$. Consider the family of outer products $x_ix_i^\intercal$; they live in the $\genfrac(){0.0pt}1{n+1}{2}$-dimensional space of symmetric $n\times n$ matrices, equipped with the inner product $\left\langle A, B \right\rangle = \text { tr }(A^\intercal B)$. It is a routine calculation to verify that , which equals $\alpha ^2$ if $i\ne j$ and 1 otherwise. This family of matrices is therefore linearly independent, which implies $m \le \genfrac(){0.0pt}1{n+1}{2}$.

In dimensions 2 and 3 this gives upper bounds of 3 and 6, respectively, matching the actual maxima. In $\mathbb {R}^7$, the above bound shows $N(7) \le 28$. This can be achieved by considering the set of all 28 permutations of the vector $(1,1,1,1,1,1,-3,-3)$, see [20, 27]. Indeed, one can verify that the dot product of any two distinct such vectors equals either $-8$ or 8, so that after normalising the vectors to unit length this constitutes an equiangular set of lines. Since the sum of the coordinates of each such vector is 0, they all live in the same 7-dimensional subspace. It is also known that there is an equiangular set of 276 lines in $\mathbb {R}^{23}$, see e.g. [19], which again matches Gerzon’s bound. Strikingly, these four examples are the only known ones to match his bound [2]. In fact, for a long time it was even an open problem to determine whether $n^2$ is the correct order of magnitude. In 2000, de Caen [6] constructed a set of $2(n+1)^2/9$ equiangular lines in $\mathbb {R}^n$ for all $n$ of the form $3\cdot 2^{2t-1}-1$. Subsequently, several other constructions of the same order were found [2, 12, 17]. For further progress on finding upper and lower bounds on $N(n)$ see e.g. [2] and its references.

Interestingly, all the above examples of size $\Theta (n^2)$ have a common angle on the order of $\arccos (1/\sqrt{n})$. On the other hand, all known construction of equiangular lines with a fixed common angle have much smaller size. It is therefore natural to consider the maximum number $N_{\alpha }(n)$ of equiangular lines in $\mathbb {R}^n$ with common angle $\arccos \alpha$, where $\alpha$ does not depend on dimension. This question was first raised by Lemmens and Seidel [19] in 1973, who showed that for sufficiently large $n$, $N_{1/3}(n) = 2n- 2$ and also conjectured that $N_{1/5}(n)$ equals $\lfloor 3(n-1)/2 \rfloor$. This conjecture was later confirmed by Neumaier [23], see also [12] for more details. Interest in the case where $1/\alpha$ is an odd integer was due to a general result of Neumann [19, p. 498], who proved that if $N_{\alpha }(n) \ge 2n$, then $1/\alpha$ is an odd integer.

Despite active research on this problem, for many years these were the best results known. Recently, Bukh [5] made important progress by showing that $N_{\alpha }(n) \le c_{\alpha }n$, where $c_\alpha = 2^{O(1/\alpha ^2)}$ is a large constant only depending on $\alpha$. Our first main result completely resolves the question of maximising $N_{\alpha }(n)$ over constant $\alpha$. We show that for sufficiently large $n$, $N_{\alpha }(n)$ is maximised at $\alpha = \frac{1}{3}$.

Theorem 1.1

Fix $\alpha \in (0,1)$. For $n$ sufficiently large relative to $\alpha$, the maximum number of equiangular lines in $\mathbb {R}^{n}$ with angle $\arccos \alpha$ is exactly $2n-2$ if $\alpha = \frac{1}{3}$ and at most $1.93n$ otherwise.

A more general setting than that of equiangular lines is the framework of spherical L-codes, introduced in a seminal paper by Delsarte et al. [9] in 1977 and extensively studied since.

Definition 1.2

Let $L$ be a subset of the interval $[-1,1)$. A finite non-empty set $C$ of unit vectors in Euclidean space $\mathbb {R}^n$ is called a spherical L-code, or for short an L-code, if $\left\langle x, y \right\rangle \in L$ for any pair of distinct vectors x, y in $C$.

Note that if $L= \{-\alpha ,\alpha \}$, then an $L$-code corresponds to a set of equiangular lines with common angle $\arccos \alpha$, where $\alpha \in [0,1)$. For $L= [-1,\beta ]$, finding the maximum cardinality of an $L$-code is equivalent to the classical problem of finding non-overlapping spherical caps of angular radius $\tfrac{1}{2}\arccos \beta$; for $\beta \le 0$ exact formulae were obtained by Rankin [25]. Generalising Gerzon’s result, Delsarte et al. [8] obtained bounds on the cardinality of sets of lines having a prescribed number of angles. They proved that, for $L= \{ -\alpha _1, \dots , -\alpha _k, \alpha _1, \dots , \alpha _k\}$ and $\alpha _1, \dots , \alpha _k \in [0,1)$, spherical $L$-codes have size at most $O(n^{2k})$. They subsequently extended this result to an upper bound of $O(n^s)$ on the size of an $L$-code when $L$ has cardinality s, see [9]. A short proof of this estimate based on the polynomial method is due to Koornwinder [18].

Bukh [5] observed that, in some sense, the negative values of $L$ pose less of a constraint on the size of $L$-codes than the positive ones, as long as they are separated away from 0. Specifically, he proved that for $L= [-1,-\beta ] \cup \{\alpha \}$, where $\beta \in (0,1)$ is fixed, the size of any $L$-code is at most linear in the dimension. Motivated by the above-mentioned work of Delsarte et al. [8] he made the following conjecture.

Conjecture 1.3

Let $\beta \in (0,1)$ be fixed and let $\alpha _1, \dots , \alpha _k$ be any k reals. Then any spherical $[-1,-\beta ] \cup \{\alpha _1, \dots , \alpha _k\}$-code in $\mathbb {R}^n$ has size at most $c_{\beta ,k}n^k$ for some constant $c_{\beta ,k}$ depending only on $\beta$ and k.

We verify this conjecture in the following strong form.

Theorem 1.4

Let $L = [-1, -\beta ] \cup \{ \alpha _1, \ldots , \alpha _k \}$ for some fixed $\beta \in (0,1]$. Then there exists a constant $c_{\beta , k}$ such that any spherical L-code in $\mathbb {R}^n$ has size at most $c_{\beta , k} n^k$. Moreover, if $0 \le \alpha _1< \cdots<\alpha _k < 1$ are also fixed then such a code has size at most

$$\begin{aligned} 2^k(k-1)!\Bigl ( 1 + \frac{\alpha _1}{\beta } \Bigr )n^k + o(n^k). \end{aligned}$$

In particular, if $\alpha _1, \dots , \alpha _k$ are fixed this substantially improves the aforementioned bound of Delsarte et al. [8, 9] from $O(n^{2k})$ to $O(n^k)$. We furthermore show that the second statement of Theorem 1.4 is tight up to a constant factor.

Theorem 1.5

Let n, k, r be positive integers and $\alpha _1 \in (0,1)$ with k and $\alpha _1$ being fixed and $r \le \sqrt{n}$. Then there exist $\alpha _2, \ldots , \alpha _k$, $\beta = \alpha _1 / r - O(\sqrt{\log (n) / n})$ and a spherical L-code of size $(1 + r) \left( {\begin{array}{c}n\\ k\end{array}}\right)$ in $\mathbb {R}^{n + r}$ with $L = [-1, -\beta ] \cup \{ \alpha _1, \ldots , \alpha _k \}$.

This also resolves another question of Bukh, who asked whether the maximum size of a spherical $[-1,0)\cup \{\alpha \}$-code in $\mathbb {R}^n$ is linear in $n$. By taking $\beta$ to be say $\log (n) / \sqrt{n}$, our construction demonstrates that this is not the case.

The rest of this paper is organised as follows. In Sect. 2 we give a construction of an equiangular set of $2n-2$ lines in $\mathbb {R}^n$ and prove Theorem 1.1. In Sect. 3 we prove a special case of Theorem 1.4, namely the case $k=1$. We provide the construction which shows that our bounds are asymptotically tight in Sect. 4. In Sect. 5, we prove Theorem 1.4. The last section of the paper contains some concluding remarks and open problems.

1.1 Notation

We will always assume that the dimension $n \rightarrow \infty$ and write $f = o(1)$, respectively $f = O(1)$ to mean $f(n) \rightarrow 0$ as $n \rightarrow \infty$, respectively $f(n) \le C$ for some constant C and n sufficiently large. We will say $\gamma$ is fixed to mean that it does not depend on n.

Let $C = \{v_1, \ldots , v_m\}$ be a spherical L-code in $\mathbb {R}^n$. We define $M_C$ to be the associated Gram matrix given by $(M_C)_{i,j} = \left\langle v_i, v_j \right\rangle$. We also define an associated complete edge-labelled graph $G_C$ as follows: let C be its vertex set and for any distinct $u,v \in C$, we give the edge uv the value $\gamma$ iff $\left\langle u, v \right\rangle = \gamma$. We also say that uv is a $\gamma$-edge and for brevity, we sometimes refer to $\gamma$ as the “angle” between u and v, instead of the “cosine of the angle”. For $\beta > 0$, we slightly abuse our notation and say that uv is a $\beta$-edge if $\left\langle u, v \right\rangle \le - \beta$. We call a subset $S \subset G_C$ a $\gamma$-clique if uv is a $\gamma$-edge for all distinct $u,v \in S$. For any $x \in G_C$ we define the $\gamma$-neighbourhood of x to be $N_\gamma (x) = \{ y \in G_C : xy \text { is a } \gamma \text {-edge} \}$. Furthermore, we define the $\gamma$-degree $d_\gamma (x) = | N_\gamma (x) |$ and the maximum $\gamma$-degree $\Delta _\gamma = \max _{x \in G}{d_\gamma (x)}$.

We denote the identity matrix by I and denote the all 1’s matrix by J, where the size of the matrices is always clear from context. Let Y be a set of vectors in $\mathbb {R}^n$. We define $\text {span}(Y)$ to be the subspace spanned by the vectors of Y and for a subspace U, define $U^{\perp } = \{x \in \mathbb {R}^n : \left\langle x, y \right\rangle = 0 \text { for all } y \in U\}$ to be the orthogonal complement. For all $x \in \mathbb {R}^n$ define $p_Y(x)$ to be the normalised (i.e. unit length) projection of x onto the orthogonal complement of $\text {span}(Y)$, provided that the projection is nonzero. That is, if we write $x = u+v$ for $u \in \text {span}(Y)^\perp$, $v \in \text {span}(Y)$ and $u \ne 0$, then $p_Y(x) = u/\Vert {u}\Vert$. More generally, for a set of vectors S we write $p_Y(S) = \{ p_Y(x) : x \in S\}$.

2 Equiangular lines

Suppose that we are given a set of equiangular lines in $n$-dimensional Euclidean space $\mathbb {R}^{n}$ with common angle $\arccos \alpha$. By identifying each line with a unit vector along this line, we obtain a set of unit vectors with the property that the inner product of any two vectors equals either $\alpha$ or $-\alpha$. As we have already mentioned in the introduction, we will refer to such a set as a $\{-\alpha ,\alpha \}$-code. Given a $\{-\alpha ,\alpha \}$-code C, we call an $\alpha$-edge of $G_C$ positive and a $-\alpha$-edge negative.

Van Lint and Seidel [20] observed that a particular set of equiangular lines corresponds to various $\{-\alpha ,\alpha \}$-codes, depending on which of the two possible vectors we choose along each line. Conversely, this means that we can negate any number of vectors in a $\{-\alpha ,\alpha \}$-code without changing the underlying set of equiangular lines. In the corresponding graph, this means that we can switch all the edges adjacent to some vertex from positive to negative and vice versa.

The proof of Theorem 1.1 builds on several key observations. The first is that we can use Ramsey’s theorem to find a large positive clique in $G_C$. We then negate some vertices outside of this clique, in order to obtain a particularly advantageous graph, for which we can show that almost all vertices attach to this positive clique entirely via positive edges. We then project this large set onto the orthogonal complement of the positive clique. Next we observe that the resulting graph contains few negative edges, which implies that the diagonal entries of the Gram matrix of the projected vectors are significantly larger in absolute value than all other entries. Combining this with an inequality which bounds the rank of such matrices already gives us a bound of $(2 + o(1))n$. To prove the exact result, we use more carefully the semidefiniteness of the Gram matrix together with some estimates on the largest eigenvalue of a graph.

We finish this discussion by giving an example of an equiangular set of $2n-2$ lines with common angle $\arccos \tfrac{1}{3}$ in $\mathbb {R}^n$, first given by Lemmens and Seidel [19]. This is equivalent to constructing a spherical $\{-\tfrac{1}{3}, \tfrac{1}{3}\}$-code C of size $2 n- 2$. For any such code C, observe that the Gram matrix $M_C$ is a symmetric, positive-semidefinite $(2n-2) \times (2n-2)$ matrix with 1s on the diagonal and rank at most $n$. Conversely, if M is any matrix satisfying all properties listed, then M is the Gram matrix of a set of $2n-2$ unit vectors in $\mathbb {R}^{n}$, see e.g. [13, Lemma 8.6.1]. Thus it suffices to construct such a matrix. To that end, consider the matrix M with $n-1$ blocks on the diagonal, each of the form

$$\begin{aligned} \left( \begin{matrix} 1 &{}\quad -\frac{1}{3}\\ -\frac{1}{3} &{}\quad 1 \end{matrix} \right) , \end{aligned}$$

and all other entries $\frac{1}{3}$. Clearly M is a $(2n-2) \times (2n-2)$ symmetric matrix, so we just have to verify that it is positive-semidefinite and of rank $n$. To do so, we need to show that M has smallest eigenvalue 0 with multiplicity $n-2$. This is a routine calculation.

2.1 Orthogonal projections

Before we can delve into the proof of Theorem 1.1, we will set the ground by providing some necessary lemmas. We start with a well-known upper bound on the size of a negative clique, which will guarantee us a large positive clique using Ramsey’s theorem. For later purposes, the lemma is stated in some more generality.

Lemma 2.1

Let $0< \alpha < 1$ and let C be a spherical $[-1,-\alpha ]$-code in $\mathbb {R}^{n}$. Then $|C| \le \alpha ^{-1} + 1$.

Proof

Let $v = \sum _{x \in C} x$. Then, since every $x \in C$ is a unit vector and $\left\langle x, x' \right\rangle \le - \alpha$ for $x \ne x'$,

$$\begin{aligned} 0 \le \Vert {v}\Vert ^2 = \sum _{x \in C} \Vert {x}\Vert ^2 + \sum _{\begin{array}{c} x,x'\in C \\ x\ne x' \end{array}} \left\langle x, x' \right\rangle \le |C| - \alpha |C|(|C|-1), \end{aligned}$$

which we can rewrite into the desired upper bound on |C|. $\square$

Remark 2.2

We note that equality in the above lemma occurs only if the vectors of C form a regular simplex.

As indicated above, this lemma enables us to find a large positive clique in our graph. The next step is to understand how the remaining vertices attach to this clique. A key tool towards this goal is orthogonal projection. We will first need a lemma that lets us compute the inner product between two vectors in the span of a clique in terms of the inner products between the vectors and the clique. Because we will need it again in a later section, we state it in some generality.

Lemma 2.3

Let $-1 \le \gamma < 1$ and $t \ne -1/\gamma + 1$. Suppose Y is a spherical $\{\gamma \}$-code of size t and V is the matrix with Y as column vectors. Then for all $v_1, v_2 \in \text {span}(Y)$ we have

$$\begin{aligned} \left\langle v_1, v_2 \right\rangle = \frac{s_1^{\intercal } s_2 - \left( \frac{\gamma }{1 + \gamma (t - 1)} \right) s_1^{\intercal } J s_2 }{1 - \gamma },\end{aligned}$$

where $s_i = V^\intercal v_i$ for $i = 1, 2$ are the vectors of inner products between $v_i$ and Y.

Proof

Let us first prove that Y is linearly independent. Suppose that $\sum _{y \in Y} c_y y = 0$ for some reals $c_y$. Taking the inner product with some $y'\in Y$ gives

$$\begin{aligned} 0 = \sum _{y \in Y} c_y \left\langle y, y' \right\rangle = (1 - \gamma )c_{y'} + \gamma \sum _{y \in Y} c_y. \end{aligned}$$

Since this equation is true for all $y' \in Y$ and $\gamma \ne 1$, all $c_y$ are identical. Unless they equal 0, this implies that $1 + (t-1) \gamma = 0$, a contradiction.

By passing to a subspace, we may assume that $Y \subset \mathbb {R}^t$, so that $V^{\intercal }$ is invertible and we have $v_i = (V^\intercal )^{-1} s_i$. Thus

$$\begin{aligned} \left\langle v_1, v_2 \right\rangle = ((V^{\intercal })^{-1} s_1)^{\intercal } (V^{\intercal })^{-1} s_2 = s_1^{\intercal } V^{-1} (V^{\intercal })^{-1} s_2= s_1^{\intercal } (V^{\intercal } V)^{-1} s_2. \end{aligned}$$

To obtain the result, we observe that $V^\intercal V$ is the Gram matrix of Y, so that $V^\intercal V = (1 - \gamma ) I + \gamma J$ and moreover

$$\begin{aligned} (V^\intercal V)^{-1} = \frac{I - \frac{\gamma }{1 + \gamma (t-1)} J}{1 - \gamma }. \end{aligned}$$

$\square$

The following lemma shows how the angle between two vectors changes under an appropriate projection. Recall that $p_Y(x)$ denotes the normalised projection of x onto the orthogonal complement of $\text {span}(Y)$.

Lemma 2.4

Let $-1< \gamma < 1$ and let $Y\cup \{x_1,x_2\}$ be a set of unit vectors in $\mathbb {R}^{n}$ so that all pairwise inner products, except possibly $\left\langle x_1, x_2 \right\rangle$, equal $\gamma$. Suppose additionally that Y has size 1 if $\gamma$ is negative. Then $p_Y(x_1)$ and $p_Y(x_2)$ are well-defined and we have

$$\begin{aligned} \left\langle p_Y(x_1), p_Y(x_2) \right\rangle = \frac{\left\langle x_1, x_2 \right\rangle - \gamma }{1-\gamma } + \frac{\gamma (1 - \left\langle x_1, x_2 \right\rangle )}{(1+ \gamma |Y|)(1-\gamma )}. \end{aligned}$$

(1)

Proof

For $i = 1, 2$, write $x_i = u_i + v_i$ where $v_i \in \text {span}(Y)$ and $u_i \in \text {span}(Y)^{\perp }$. Let V be the matrix with Y as columns and observe that $s_i = V^\intercal v_i = V^\intercal (x_i - u_i) = (\gamma , \ldots , \gamma )^\intercal$. Let $t = |Y|$ and observe that $t \ne -1/\gamma + 1$ and $t \ne -1 / \gamma$, so we can apply Lemma 2.3 to obtain

$$\begin{aligned} \left\langle v_1, v_2 \right\rangle = \left\langle v_1, v_1 \right\rangle = \left\langle v_2, v_2 \right\rangle = \frac{t \gamma ^2 - \frac{\gamma }{1 + \gamma (t-1)} (t\gamma )^2}{1 - \gamma } = \frac{t \gamma ^2}{1 + \gamma (t-1)} < 1. \end{aligned}$$

Thus using the fact that $x_i$ is a unit vector and $u_i,v_i$ are orthogonal, we have $||u_i||^2 = 1 - ||v_i||^2 > 0$ for $i = 1, 2$. Since $p_Y(x_i) = u_i / ||u_i||$, we can finish the proof by computing

$$\begin{aligned} \frac{\left\langle u_1, u_2 \right\rangle }{\Vert {u_1}\Vert \Vert {u_2}\Vert }= & {} \frac{\left\langle x_1, x_2 \right\rangle - \left\langle v_1, v_2 \right\rangle }{\sqrt{1 - ||v_1||^2}\sqrt{1 - ||v_2||^2}} = \frac{\left\langle x_1, x_2 \right\rangle - \frac{t \gamma ^2}{1 + \gamma (t-1)}}{1 - \frac{t \gamma ^2}{1 + \gamma (t-1)}}\nonumber \\= & {} \frac{\left\langle x_1, x_2 \right\rangle - \gamma }{1-\gamma } + \frac{\gamma (1 - \left\langle x_1, x_2 \right\rangle )}{(1+ \gamma t)(1-\gamma )}. \end{aligned}$$

$\square$

Remark 2.5

Note that when the conditions of the lemma are met we have $\left\langle p_Y(x_1), p_Y(x_2) \right\rangle \le \left\langle x_1, x_2 \right\rangle$, which in particular implies that $p_Y(x_1) \ne p_Y(x_2)$ when $x_1 \ne x_2$. Note furthermore that if $|Y| = 1$, then the right-hand side of (1) simplifies to $(\left\langle x_1, x_2 \right\rangle -\gamma ^2)/(1-\gamma ^2)$ (this is most easily seen by looking at the second-to-last term in the final equation of the above proof) and that, for fixed $\left\langle x_1, x_2 \right\rangle$, the latter is a decreasing function in $\gamma ^2$.

In particular, after projecting onto a positive clique (i.e. $\gamma = \alpha$) of size t, an angle of $\alpha$ becomes $1/(t+ \alpha ^{-1})$ (that is, if $\left\langle x, x' \right\rangle = \alpha$, then $\left\langle p_Y(x), p_Y(x') \right\rangle = 1/(t + \alpha ^{-1})$) and an angle of $-\alpha$ becomes

$$\begin{aligned} -\frac{2\alpha }{1-\alpha } + \frac{1+\alpha }{(t + \alpha ^{-1})(1-\alpha )}. \end{aligned}$$

Since these two angles will frequently pop up, we will make the following definition.

Definition 2.6

For $\alpha \in (0,1)$ and $t \in \mathbb {N}$, let $L(\alpha ,t) = \{ - \sigma (1 - \epsilon ) + \epsilon ,\epsilon \}$, where $\epsilon = \epsilon (\alpha ,t)= 1/(t + \alpha ^{-1})$ and $\sigma = \sigma (\alpha ) = 2\alpha /(1-\alpha )$.

Note that $L(\alpha ,t)$ comprises the two possible angles after projecting onto a positive clique of size t. A set attached to a positive clique in a $\{-\alpha ,\alpha \}$-code entirely via positive edges therefore turns into an $L(\alpha ,t)$-code after projecting. When we project, we will continue to call edges positive or negative according to whether their original values are $\alpha$ or $-\alpha$. Note in particular that a positive edge may obtain a negative value after projection.

Equipped with this machinery to handle projections, the next lemma gives an upper bound on the number of vertices which are not attached to the positive clique entirely via positive edges. The result is analogous to Lemma 5 of Bukh [5].

Lemma 2.7

Let $X \cup Y \cup \{z\}$ be a $\{-\alpha ,\alpha \}$-code in $\mathbb {R}^{n}$ in which all edges incident to any $y \in Y$ are positive and all edges between X and z are negative. If $|Y|\ge 2/\alpha ^2$, then $|X| < 2/\alpha ^2$.

Proof

Let us first project $X \cup \{z\}$ onto the orthogonal complement of $\text {span}(Y)$, and let us denote $p_{Y}(X)$ by $X'$ and $p_{Y}(z)$ by $z'$. By Lemma 2.4 and the subsequent paragraph, we verify that $X' \cup \{z'\}$ is an $L(\alpha ,|Y|)$-code in which all edges incident to $z'$ are negative and have value $- \sigma (1-\epsilon ) + \epsilon$, which, by Remark 2.5, is at most $-\alpha$. The positive angles equal $\epsilon < 1/|Y|$ and since $|Y| \ge 2/\alpha ^2$ we get the bound $\epsilon \le \alpha ^2/2$. Let us now project $X'$ onto the orthogonal complement of $\text {span}(z')$. By Lemma 2.4 and Remark 2.5 we find that the positive angle becomes

(2)

and the negative angles become at most $\frac{-\alpha - (\sigma (1-\epsilon )-\epsilon )^2}{1 - (\sigma (1-\epsilon )-\epsilon )^2}$, which is at most (2). Furthermore, using $(\sigma ( 1- \epsilon )-\epsilon )^2 \ge \alpha ^2$ and Remark 2.5, (2) is at most $(\epsilon - \alpha ^2)/(1 - \alpha ^2)$. Since $\epsilon \le \alpha ^2/2$, this yields an upper bound of $-\alpha ^2/(2-2\alpha ^2)$ on all angles after projection. Therefore, after projecting $X'$ onto the orthogonal complement of $\text {span}(z')$, we obtain a spherical $[-1,-\alpha ^2/(2-2\alpha ^2)]$-code. By Lemma 2.1, it has size at most $(2-2\alpha ^2)/\alpha ^2+1 < 2/\alpha ^2$, concluding the proof of the lemma. $\square$

Using this lemma, we will see that, after appropriately negating some vertices, all but a fixed number of vertices are attached to the positive clique via positive edges. Hence Theorem 1.1 can be reduced to studying $L(\alpha ,t)$-codes, as follows.

Lemma 2.8

Let $\alpha \in (0,1)$ be fixed and let $t = \log {\log {n}}$. For all sufficiently large n and for any spherical $\{-\alpha ,\alpha \}$-code C in $\mathbb {R}^n$, there exists a spherical $L(\alpha ,t)$-code $C'$ in $\mathbb {R}^n$ such that $|C| \le |C'| + o(n).$

Proof

Recall that $G_C$ denotes the complete edge-labelled graph corresponding to C. From Lemma 2.1 we know that $G_C$ doesn’t contain a negative clique of size $\alpha ^{-1} + 2$. By Ramsey’s theorem there exists some integer R such that every graph on at least R vertices contains either a negative clique of size at least $\alpha ^{-1} + 2$ or a positive clique of size t. A well-known bound of Erdős and Szekeres [11] shows $R \le 4^t = o(n)$. Thus if $|C| < R$, then we are done by taking $C' = \emptyset$. Otherwise we have by Ramsey’s theorem that $G_C$ contains a positive clique Y of size t.

For any $T \subset Y$, let $S_T$ comprise all vertices v in $G_C {\setminus } Y$ for which the edge vy ($y\in Y$) is positive precisely when $y \in T$. Let us negate all vertices v which lie in $S_T$ for some $|T| < t/2$ and note that C remains a $\{-\alpha ,\alpha \}$-code. However, all sets $S_T$ for $|T| < t/2$ are now empty. Given some $T \subset Y$ with $t/2\le |T| <t$, pick a vertex $z \in Y{\setminus } T$ and consider the $\{-\alpha ,\alpha \}$-code $S_T \cup T \cup \{z\}$. Since any edge incident to T is positive, all edges between $S_T$ and z are negative and $|T| \ge t/2 > 2/\alpha ^2$ for n large enough, we can apply Lemma 2.7 to deduce that $|S_T| < 2/\alpha ^2$. Moreover, by Lemma 2.4 and Remark 2.5 we have that $C' = p_Y(S_Y)$ is an $L(\alpha , t)$-code with $|C'| = |S_Y|$. Thus we conclude

$$\begin{aligned} |C| = |S_Y| + \sum _{t/2< |T|< t}{|S_T|} + |Y| < |C'| + 2^{t+1}/\alpha ^2 + t = |C'| + o(n). \end{aligned}$$

$\square$

2.2 Spectral techniques

In view of Lemma 2.8, we just need to bound the size of $L(\alpha ,t)$-codes. Our main tool will be an inequality bounding the rank of a matrix in terms of its trace and the trace of its square. This inequality goes back to [3, p. 138] and its proof is based on a trick employed by Schnirelman in his work on Goldbach’s conjecture [26]. For various combinatorial applications of this inequality, see, for instance, the survey by Alon [1] and other recent results [10].

Lemma 2.9

Let M be a symmetric real matrix. Then $\text { rk }(M) \ge \text { tr }(M)^2/\text { tr }(M^2)$.

Proof

Let r denote the rank of M. Since M is a symmetric real matrix, M has precisely r non-zero real eigenvalues $\lambda _1,\dots ,\lambda _{r}$. Note that $\text { tr }(M) = \sum _{i=1}^r\lambda _i$ and $\text { tr }(M^2) = \sum _{i=1}^r \lambda _i^2$. Applying Cauchy–Schwarz yields $r\sum _{i=1}^r \lambda _i^2 \ge (\sum _{i=1}^r \lambda _i)^2$, which is equivalent to the desired inequality. $\square$

We use Lemma 2.9 to deduce the next claim.

Lemma 2.10

Let C be an $L(\alpha ,t)$-code in $\mathbb {R}^{n}$ and let $d$ denote the average degree of the graph spanned by the negative edges in $G_C$. Then $|C| \le (1 + \sigma ^2d)(n+1)$.

Proof

Recall that $L(\alpha ,t) = \{- \sigma (1 - \epsilon )+\epsilon ,\epsilon \}$. Every diagonal entry of $N = M_C - \epsilon J$ equals $1- \epsilon$ and N contains exactly $d|C|$ non-zero off-diagonal entries, each of which equals $-\sigma (1-\epsilon )$. Observe that $\text { rk }(N) \le \text { rk }(M_C) + \text { rk }(J) \le n+1$ by the subadditivity of the rank. Furthermore, $\text { tr }(N) = |C|(1-\epsilon )$ and $\text { tr }(N^2) = \sum _{i,j} N_{ij}^2$. By applying Lemma 2.9 to N we can therefore deduce

$$\begin{aligned} |C|^2(1-\epsilon )^2 \le \Bigl (|C|(1-\epsilon )^2 + |C|d\sigma ^2(1-\epsilon )^2\Bigr )(n+1), \end{aligned}$$

which is equivalent to the desired inequality after dividing by $|C|(1-\epsilon )^2$.   $\square$

It thus proves necessary to obtain upper bounds on the average degree d of the negative edges in $G_C$.

Remark 2.11

The proof of Lemma 2.7 provides us with a bound on d, and if we are a bit more careful, we already have enough to prove that for a fixed $\alpha$ and $t \rightarrow \infty$, any $L(\alpha ,t)$-code has size at most $2n + o(n)$. Indeed, suppose that C is an $L(\alpha ,t)$-code with $t \rightarrow \infty$. Let $z' \in C$ and let $X'$ be the vertices connected to $z'$ via negative edges. We project $X'$ onto the orthogonal complement of $z'$ and observe that since $t \rightarrow \infty$, $\epsilon \rightarrow 0$ and hence the positive angle (2) in Lemma 2.7 becomes $-\sigma ^2 / (1 - \sigma ^2) + o(1)$. Thus we obtain a $[-1, -\sigma ^2 / (1 - \sigma ^2) + o(1)]$-code which has size at most $(1 - \sigma ^2)/\sigma ^2 + 1 + o(1) = 1 / \sigma ^2 + o(1)$ by Lemma 2.1. Since this holds for all z, we have that $d \le 1 / \sigma ^2 + o(1)$ and hence applying Lemma 2.10 we conclude $|C| \le 2n + o(n)$.

The following lemma shows that it will be sufficient to find an upper bound on $d$ in terms of the largest eigenvalue of some fixed-size subgraph of C, by which we mean a subgraph of size O(1). Let us fix some standard notation. For a matrix A, we denote its largest eigenvalue by $\lambda _1(A)$. If H is a graph, then we can identify H with its adjacency matrix A(H), so that we will write $\lambda _1(H)$ to mean $\lambda _1(A(H))$. It is well-known that $\lambda _1$ is monotone in the following sense: if H is a subgraph of G, then $\lambda _1(H) \le \lambda _1(G)$ (see e.g. [21, chapter 11, exercise 13]).

Lemma 2.12

Let C be a fixed-size $L(\alpha ,t)$-code in $\mathbb {R}^{n}$ and assume that $t \rightarrow \infty$ as $n \rightarrow \infty$. Let H be the subgraph of $G_C$ containing precisely all negative edges. Then $\sigma \lambda _1(H) \le 1 + o(1)$.

Proof

The Gram matrix $M_C$ and $A = A(H)$ are related by the equation

$$\begin{aligned} M_C = I + \epsilon (J-I) - \sigma (1 - \epsilon )A, \end{aligned}$$

where J denotes the all-ones matrix. Let x be a normalised eigenvector of A with eigenvalue $\lambda _1(H)$. Since $M_C$ is positive-semidefinite, we deduce

$$\begin{aligned} 0\le & {} \left\langle M_Cx, x \right\rangle = 1 - \epsilon + \epsilon \left\langle Jx, x \right\rangle - \sigma (1-\epsilon ) \lambda _1(H) \nonumber \\\le & {} 1 - \sigma \lambda _1(H) + \epsilon (|C| +\sigma \lambda _1(H)), \end{aligned}$$

(3)

where $\left\langle Jx, x \right\rangle \le |C|$ follows from the fact that |C| is the largest eigenvalue of J. Since $\sigma , |C|$ and $\lambda _1(H)$ are all O(1) and $\epsilon = o(1)$, (3) yields the required $\sigma \lambda _1(H) \le 1 + o(1)$. $\square$

The following two lemmas are concerned with establishing a connection between the average degree of a graph and its largest eigenvalue. The first lemma and its proof are inspired by Nilli’s proof [24] of the Alon-Boppana bound on the second eigenvalue of a graph.

Lemma 2.13

Let G be a graph with minimum degree $\delta >1$. Let $v_0$ be some vertex of G and let H be the subgraph consisting of all vertices within distance $k$ of $v_0$. Then $\lambda _1(H) \ge 2(1 - 1/(k+1))\sqrt{\delta - 1}$.

Proof

For $0\le i \le k$, let $V_i$ denote the set of vertices at distance i from $v_0$ in H, let $e_i$ denote the number of edges in $H[V_i]$ and let $h_i$ denote the number of edges in $H[V_i, V_{i+1}]$, where we set $h_{k} = 0$ and, since we will need it later in the proof, $h_{-1} = 0$. Let us define a function $f$ on the vertices of H by $f(v) = (\delta -1)^{-i/2}$ if $v\in V_i$. Letting A denote the adjacency matrix of H, we have $\lambda _1(H) \ge \left\langle Af, f \right\rangle {/}\left\langle f, f \right\rangle$. In order to prove the desired bound on $\lambda _1(H)$, we therefore need to bound the quantity $\left\langle f, f \right\rangle$ from above in terms of $\left\langle Af, f \right\rangle$. We have

$$\begin{aligned} \left\langle f, f \right\rangle = \sum _{i=0}^{k} \frac{|V_i|}{(\delta -1)^i} \quad \text {and} \quad \left\langle Af, f \right\rangle = \sum _{i=0}^{k}\biggl ( \frac{2e_i}{(\delta -1)^i} + \frac{2h_i}{(\delta -1)^{i+1/2}}\biggr ). \end{aligned}$$

Note that for $0\le i\le k-1$, $h_{i-1} + 2e_i + h_i$ counts the sum of the degrees of all vertices in $V_i$ and is therefore of size at least $\delta |V_i|$. Moreover, since every vertex in $V_{i+1}$ is adjacent to some vertex in $V_i$ we have $|V_{i+1}| \le h_i$. Fix any j in the range $0\le j \le k$. Using the above two observations we find

$$\begin{aligned} \left\langle f, f \right\rangle \le \sum _{i=0}^{j-1} \frac{h_{i-1} + 2e_i + h_i}{\delta (\delta -1)^i} + \frac{|V_j|}{(\delta - 1)^{j}} + \sum _{i = j}^{k-1} \frac{h_i}{(\delta -1)^{i+1}}. \end{aligned}$$

(4)

Observe that $\delta \ge 2\sqrt{\delta - 1}$ and that we have the identity

$$\begin{aligned} \frac{1}{\delta (\delta -1)^i} + \frac{1}{\delta (\delta -1)^{i+1}} = \frac{1}{(\delta -1)^{i+1}}. \end{aligned}$$

Collecting terms belonging to the same $h_i$ in the first sum of (4) and using the estimate and identity of the previous sentence, we find

$$\begin{aligned} \left\langle f, f \right\rangle \le \sum _{i=0}^{k} \biggl (\frac{h_i}{(\delta -1)^{i+1}} + \frac{2e_i}{\delta (\delta -1)^i} \biggr ) + \frac{|V_j|}{(\delta - 1)^{j}} \le \frac{\left\langle Af, f \right\rangle }{2\sqrt{\delta - 1}} + \frac{|V_j|}{(\delta - 1)^j}. \end{aligned}$$

Averaging over all $0 \le j \le k$ yields

$$\begin{aligned} \left\langle f, f \right\rangle \le \frac{\left\langle Af, f \right\rangle }{2\sqrt{\delta - 1}} + \frac{\left\langle f, f \right\rangle }{k+1}, \end{aligned}$$

which is equivalent to the desired inequality. $\square$

Lemma 2.14

Let H be a connected graph on

• (i) $11$ vertices and $10$ edges. Then $\lambda _1(H) \ge 20/11$.

• (ii) k vertices and k edges. Then $\lambda _1(H) \ge 2$.

• (iii) 6 vertices and 5 edges, so that some vertex has degree 5. Then $\lambda _1(H) \ge 2.2$.

• (iv) 5 vertices and 5 edges so that some vertex has degree 4. Then $\lambda _1(H) \ge 2.25$.

• (v) 8 edges so that some vertex has degree 4. Then $\lambda _1(H) \ge 2.2$.

Proof

Let A denote the adjacency matrix of H and $\mathbbm {1}$ the all-ones vector of appropriate length. Note that $\lambda _1(H) \ge \left\langle A\mathbbm {1}, \mathbbm {1} \right\rangle /\left\langle \mathbbm {1}, \mathbbm {1} \right\rangle = d$, where d denotes the average degree of H. This is sufficient to establish (i) and (ii), since the average degree of the graphs is $20/11$ and 2, respectively.

Suppose that H is a star with 5 leaves, as in (iii). Let x be the vector giving weight $\sqrt{5}$ to its internal vertex and weight 1 to each leaf. Then $\left\langle x, x \right\rangle = 10$ and $\left\langle Ax, x \right\rangle = 10\sqrt{5}$ yielding the required $\lambda _1(H) \ge \sqrt{5} > 2.2$.

Suppose that H is as in (iv). Let x be the vector giving weight 1 to the vertex of degree 4 and 1 / 2 to the others. Then $\left\langle x, x \right\rangle = 2$ and $\left\langle Ax, x \right\rangle = 4.5$ yielding the required $\lambda _1(H) \ge 2.25$.

Finally, suppose that H is as in (v) and let v be the vertex of degree 4. If two of the neighbours of v are adjacent, we are done by (iv). Otherwise, let x be the vector giving weight 4 to v, weight $\sqrt{5}$ to its 4 neighbours and weight 1 to all other vertices. Then $\left\langle Ax, x \right\rangle = 40\sqrt{5}$ and $\left\langle x, x \right\rangle \le 40$ since there are at most 4 vertices of weight 1. Hence $\lambda _1(H) \ge \left\langle Ax, x \right\rangle /\left\langle x, x \right\rangle \ge \sqrt{5} > 2.2$. $\square$

The next lemma deals with $\{-\alpha ,\alpha \}$-codes in which the negative edges are very sparse. This will be the case when $\alpha$ is rather large.

Lemma 2.15

Let $\alpha \in (0,1){\setminus } \{ \frac{1}{3}\}$ and let C be an $L(\alpha ,t)$-code in $\mathbb {R}^{n}$. If the negative edges form a matching, then $|C| \le n+1$.

Proof

Recall that $L(\alpha , t) = \{-\sigma (1-\epsilon ) + \epsilon ,\epsilon \}$. Let J denote the all-ones matrix. Since the rank of matrices is subadditive, we have

$$\begin{aligned} \text { rk }(M_C-\epsilon J) \le \text { rk }(M_C) + \text { rk }(-\epsilon J) = \text { rk }(M_C) + 1 \le n+ 1. \end{aligned}$$

(5)

Since the negative edges of $G_C$ form a matching, the matrix $(M_C - \epsilon J)/(1-\epsilon )$ consists of m identical $2\times 2$ blocks with 1’s on the diagonal and $-\sigma$ off the diagonal, and $|C|-2m$ identical $1 \times 1$ identity matrices, where m denotes the number of negative edges. The former have determinant $1 - \sigma ^2$, the latter 1. Since $\alpha \ne \frac{1}{3}$, these quantities are non-zero, so that $M_C - \epsilon J$ has full rank, that is, $\text { rk }(M_C - \alpha J) = |C|$. Together with (5) this gives the desired inequality. $\square$

Remark 2.16

Note that one can also prove $|C| \le n$ with some more work.

2.3 Proof of the main result

In this section, we present the proof of Theorem 1.1. First, combining Lemma 2.10 with the newly gained information about the relation between $\sigma$, the largest eigenvalue of fixed-size graphs and $d$, we prove the following theorem about $L(\alpha , t)$-codes. This theorem will allow us to analyse equiangular lines for all angles except $\arccos \frac{1}{3}$.

Theorem 2.17

Let $\alpha \in (0,1){\setminus }\{\frac{1}{3}\}$ and $t \in \mathbb {N}$ so that $t\rightarrow \infty$ as $n \rightarrow \infty$. Let C be an $L(\alpha ,t)$-code in $\mathbb {R}^{n}$ for which every vertex is incident to at most O(1) negative edges. Then $|C| < 1.92n$ for sufficiently large $n$.

Proof

Recall that $L(\alpha ,t) = \{- \sigma (1 - \epsilon )+\epsilon ,\epsilon \}$, where $\epsilon = 1/(t + \alpha ^{-1})$ and $\sigma = 2\alpha /(1-\alpha )$; note that $\epsilon = o(1)$. Throughout the proof, let G denote the graph consisting only of the negative edges of the graph corresponding to C (that is, we delete from $G_C$ all positive edges to obtain G). We split the proof of this lemma into different regimes, depending on the value of $\sigma$.

Case 1, $\sigma \in [0.71, \infty )$: We will show that no two edges in G are adjacent. Together with Lemma 2.15 this will show that $|C| \le n+ 1$. Let $\beta = -\sigma ( 1- \epsilon ) + \epsilon$. If $\beta < - 1$, G cannot contain any edges and we are done. Otherwise, suppose to the contrary that x, y and z are unit vectors in C so that xy and xz are negative edges. Let us decompose y and z as $y = \beta x + u$ and $z = \beta x + v$, where u and v are orthogonal to x. Since x, y and z are unit vectors, taking norms on both sides of each equation and rearranging yields $1 - \beta ^2 =\Vert {u}\Vert ^2 = \Vert {v}\Vert ^2$. Since $\sigma \ge 0.71 > 1/\sqrt{2}$ and $\epsilon = o(1)$, we have $\beta ^2 > 1/2 + \epsilon$ for sufficiently large $n$ and hence t. Therefore, $\Vert {u}\Vert , \Vert {v}\Vert < 1/\sqrt{2}$. Furthermore, taking the inner product of y and z gives

$$\begin{aligned} \left\langle y, z \right\rangle = \beta ^2 + \left\langle u, v \right\rangle> \epsilon + 1/2 - \Vert {u}\Vert \Vert {v}\Vert > \epsilon , \end{aligned}$$

a contradiction to $\left\langle y, z \right\rangle \in L(\alpha ,t)$, finishing the proof of the first case.

Case 2, $\sigma \in [0.551, 0.71]$: We will prove that G decomposes into trees on at most $10$ vertices. Lemma 2.12 shows that G cannot contain a fixed-size subgraph H with $\lambda _1(H) > 1/0.55 = 20/11$. In particular, by Lemma 2.14, G doesn’t contain a subgraph on $11$ vertices and $10$ edges or a subgraph on k vertices and k edges for any $k \le 10$. Since any connected graph on at least 11 vertices contains a tree on 11 vertices, all components have at most 10 vertices, and since the only acyclic components are trees, all components are trees on at most $10$ vertices. The average degree of any component is therefore at most $18/10$ and hence so is the average degree of G. Applying Lemma 2.10 establishes the required bound

$$\begin{aligned} |C| \le (1 + 1.8 \sigma ^2)(n+ 1) < 1.92n. \end{aligned}$$

Case 3, $\sigma \in [0.47, 0.551]$: Lemma 2.12 implies that G cannot contain a fixed-size subgraph H with $\lambda _1(H)> 2.13 > 1/0.47$. We can therefore deduce from Lemma 2.14 that G doesn’t contain a vertex of degree higher than 4, that the neighbourhood of a vertex of degree 4 contains no edges and that the neighbourhood of a vertex of degree 4 is incident to at most 3 more edges. The latter two properties imply that each vertex of degree 4 is adjacent to a leaf. On the other hand, each leaf is adjacent to exactly one vertex (not necessarily of degree 4), so G contains no more vertices of degree 4 than leaves. Since G also doesn’t contain any vertices of higher degree than 4, the average degree of G is at most 3. Applying Lemma 2.10 establishes the required bound

$$\begin{aligned} |C| \le (1+ 3\sigma ^2) (n+1) < 1.92n. \end{aligned}$$

Case 4, $\sigma \in (0,0.47]$: Let d be the average degree of the negative edges in $G_C$ and suppose for the sake of contradiction that $|C| > 1.92n$. Combining this lower bound on |C| with the upper bound given by Lemma 2.10 yields $d> 0.92/\sigma ^2 - o(1) > 4$. Let l be the integer satisfying $2l< d\le 2l+2$; note that $d> 4$ implies $l\ge 2$. It is well known that a graph with average degree $d$ contains a subgraph with minimum degree at least $d/2$. Hence G contains a subgraph $G'$ with minimum degree at least $l+1$. Applying Lemma 2.13 to $G'$ for $k = 11$, we find that $G'$ contains a subgraph H with maximal eigenvalue $\lambda _1(H) > 1.83\sqrt{l}$ and, since the maximum degree of G is bounded by a constant independent of $n$, so is the size of H by construction. Lemma 2.12 then gives

$$\begin{aligned} \sigma ^2 \le \frac{1 + o(1)}{1.83^2l} < \frac{1}{3.34l}, \end{aligned}$$

which together with Lemma 2.10 and $l\ge 2$ yields the required

$$\begin{aligned} |C|< \biggl ( 1 + \frac{2(l+1)}{3.34l} \biggr )(n+1 ) < 1.92n. \end{aligned}$$

$\square$

Now that we have finished all the necessary preparation, we are ready to complete the proof of our first theorem.

Proof of Theorem 1.1

Let C be a $\{-\alpha ,\alpha \}$-code in $\mathbb {R}^n$ and let $t = \log \log n$. Suppose first that $\alpha \ne \frac{1}{3}$. Then by Lemma 2.8, there exists an $L(\alpha ,t)$-code $C'$ in $\mathbb {R}^n$ such that $|C| \le |C'| + o(n)$. By Theorem 2.17, we have $|C'| < 1.92n$ and hence $|C| \le 1.93n$ for n large enough.

Otherwise $\alpha = \frac{1}{3}$. For a detailed proof of the upper bound of $2n-2$, we refer the reader to [19]. Let us nonetheless sketch it for the sake of completeness. Note that what follows is only an outline; filling in all the details requires substantially more work. Instead of finding a large positive clique, we consider the largest negative clique M in any graph obtained from $G_C$ by switching any number of vertices. By Lemma 2.1, we have that $|M| \le 4$. We can then show that the cases $|M| \le 3$ are either straightforward or can be reduced to the case $|M|=4$. In the latter case, we can show that unless all vertices attach to M in the same way (that is, no two vertices outside the clique attach to some vertex within the clique differently), |C| is bounded from above by some constant independent of $n$. If they do all attach in the same way, then if we consider the projection $C' = p_M(C \backslash M)$ of $C \backslash M$ onto the orthogonal complement of $\text {span}(M)$, we obtain a $\{-1,0\}$-code. This means that any two distinct vectors of $C'$ are either orthogonal or lie in the same 1-dimensional subspace, so that $|C'| \le 2\text {dim}(C')$. Moreover, by Remark 2.2 M is a regular simplex so it lives in a 3-dimensional subspace, and hence $\text {dim}(C') = n-3$. Thus $|C| = |M| + |C'| \le 4 + 2(n-3) = 2n -2$, finishing the proof. $\square$

3 Spherical codes

Let us now turn our attention from equiangular sets of lines to the more general setting of spherical codes. Recall that a spherical $L$-code is a finite non-empty set $C$ of unit vectors in Euclidean space $\mathbb {R}^n$ so that $\left\langle x, y \right\rangle \in L$ for any pair of distinct vectors x, y in $C$. In this section, we prove Theorem 1.4 in the case $k = 1$, obtaining the asymptotically tight bound even when $\alpha$ is allowed to depend on n. The proof features all ideas central to the argument in the multi-angular case (which we will treat in detail in Sect. 5), without concealing them unnecessarily.

Theorem 3.1

Let $\beta \in (0,1]$ be fixed and $\alpha \in [-1, 1)$. Then any $[-1,-\beta ]\cup \{ \alpha \}$-code in $\mathbb {R}^n$ has size at most

$$\begin{aligned} 2 \Bigl ( 1 + \max \Bigl ( \frac{\alpha }{\beta }, 0 \Bigr )\Bigr ) n+ o(n). \end{aligned}$$

Since an equiangular set of lines corresponds to a $\{-\alpha ,\alpha \}$-code, this implies a weaker bound of $4n+ o(n)$ for equiangular sets. The reason for this is that we can’t switch edges from negative to positive any more, since a negative edge might not obtain value $\alpha$ after switching. Moreover, this is essentially tight because if we take our example of $2n-2$ lines with angle $\arccos \frac{1}{3}$ and take both unit vectors along each line, we get a $[-1, -\frac{1}{3}] \cup \{ \frac{1}{3} \}$-code of size $4n - 4$.

The beginning of the proof of Theorem 3.1 is along the lines of the proof of the corresponding theorem for equiangular sets of lines. We start by finding a large positive clique in $G_C$. Unlike before, however, a substantial portion of the vertices might not attach to this clique entirely via positive edges. In fact, almost all vertices attach either entirely via positive edges or mostly via negative ones. Similarly to before, we can bound the size of the set of vertices attaching positively to the clique by $2n+ o(n)$. Repeating this argument yields a set of positive cliques in such a way that almost all edges between these cliques are negative. This imposes a bound on the number of repetitions, which is enough to bound the size of the $L$-code.

We start by proving a lemma similar to Lemma 2.7, which enables us to analyse how vertices connect to a positive clique.

Lemma 3.2

Let $L = [-1, -\beta ] \cup \{ \alpha \}$ for some $\alpha , \beta \in (0,1)$ and suppose that $X \cup Y \cup \{z\}$ is an L-code in which all edges incident to any $y \in Y$ are positive edges and all edges between X and z are negative edges. Suppose furthermore that $|Y| > 1/\alpha ^2$. Then $|X| < 1/\beta ^2$.

Proof

Let $\alpha _X$ denote the average value of the edges in X and $-\beta _z$ the average value of the edges between X and z. Note that $\alpha _X \le \alpha$ and $\beta _z \ge \beta$. Let M be the Gram matrix of $X \cup Y \cup \{z \}$ and let $v = (x, \dots , x, y, \dots , y, \zeta )^\intercal$, where

$$\begin{aligned} x = 1/|X|, \quad y = -\frac{\alpha (1+\beta _z)/|Y|}{\alpha - \alpha ^2 + (1 -\alpha )/|Y|} \quad \text {and} \quad \zeta = \beta _z - y |Y|\alpha . \end{aligned}$$

Then

$$\begin{aligned} {\begin{matrix} \left\langle Mv, v \right\rangle &{}= \frac{(|X|^2-|X|)\alpha _X+|X|}{|X|^2} + 2y|Y|\alpha + y^2((|Y|^2-|Y|)\alpha \\ &{}\quad + |Y|) + 2\zeta (-\beta _z + y|Y|\alpha ) + \zeta ^2 \\ &{}= \frac{1-\alpha _X}{|X|}+\alpha _X -\beta _z^2 + 2y|Y|\alpha (1 + \beta _z) \\ &{}\quad + y^2|Y|^2\bigl (\alpha -\alpha ^2 + (1-\alpha )/|Y|\bigr ) \\ &{}= \frac{1-\alpha _X}{|X|}+\alpha _X -\beta _z^2 - \frac{\alpha ^2(1 + \beta _z)^2}{\alpha -\alpha ^2 + (1-\alpha )/|Y|} \\ &{}\le \frac{1-\alpha }{|X|}+\alpha -\beta _z^2 - \frac{\alpha ^2(1 + \beta _z)^2}{\alpha -\alpha ^2 + (1-\alpha )/|Y|}. \end{matrix}} \end{aligned}$$

Since $\left\langle M v, v \right\rangle \ge 0$ and $\beta _z^2 \ge \beta ^2$, it is therefore sufficient to prove that

$$\begin{aligned} \alpha -\beta _z^2 - \frac{\alpha ^2(1 + \beta _z)^2}{\alpha -\alpha ^2 + (1-\alpha )/|Y|} < -\beta _z^2(1-\alpha ). \end{aligned}$$

Using $|Y| > 1/\alpha ^2$ and rewriting the above inequality, it suffices to show that

$$\begin{aligned} \alpha (1-\beta _z^2) < \frac{\alpha (1+\beta _z)^2}{1-\alpha ^2}, \end{aligned}$$

which is clearly true since $\alpha , \beta _z > 0$. $\square$

Remark 3.3

The v in the above proof is chosen so as to minimise $\left\langle M v, v \right\rangle \!/ ||v||^2$. An appropriate projection also minimises this quantity and so the above argument could also be done using projections. Indeed, this minimisation is precisely why projections are so useful for us.

After projecting onto a large $\alpha$-clique, the new $\alpha$ will become o(1). In this case, the next lemma gives a bound on the values of the negative edges incident to a fixed vertex.

Lemma 3.4

Let $L= [-1, - \beta ] \cup \{\alpha \}$ and let C be an $L$-code. If $\alpha = o(1)$ and $-\beta _1, \dots , -\beta _{N}$ are the values of the negative edges incident to some vertex x in $G_C$, then $\alpha N = o(1)$ and $\sum _{i = 1}^{N} \beta _i^2 \le 1 + o(1)$.

Proof

We will first derive the upper bound on N. Let $C = N_\beta (x) \cup \{x\}$ and $M = M_C$. If we let $v = (1, \dots , 1, \beta N)^\intercal$, then we have

$$\begin{aligned} 0 \le \left\langle M v, v \right\rangle = \sum _{1\le i,j \le N} M_{ij} - 2 \beta N \sum _{i=1}^N \beta _i+\beta ^2 N^2 \le N + o(1)N^2 - \beta ^2N^2, \end{aligned}$$

which implies $N \le (1 + o(1))\beta ^{-2}$ and therefore establishes the claimed $\alpha N \le (1+o(1))\alpha \beta ^{-2} = o(1)$. Now if we let $w = (\beta _1, \dots , \beta _N, 1)^\intercal$, then we obtain

$$\begin{aligned} \left\langle Mw, w \right\rangle= & {} 1 - \sum _{i=1}^N \beta _i^2 + \sum _{\begin{array}{c} 1\le i,j \le N \\ i \ne j \end{array}} \beta _i\beta _j M_{ij} \le 1 - \sum _{i=1}^N \beta _i^2 + \sum _{1\le i,j \le N} \beta _i\beta _j \alpha \\\le & {} 1 - \sum _{i=1}^N \beta _i^2 + \alpha N \sum _{i=1}^N \beta _i^2, \end{aligned}$$

where the last step follows from Cauchy–Schwarz. Using $\left\langle Mw, w \right\rangle \ge 0$ and $\alpha N = o(1)$, we obtain the required $\sum _{i=1}^N \beta _i^2 \le 1 + o(1)$. $\square$

As we outlined above, when proving Theorem 3.1 we will obtain a multipartite graph which has mostly negative edges between its parts. The next lemma gives a bound on the number of parts of such a graph. Because we will consider more general spherical codes in a later section, we prove it in more generality.

Lemma 3.5

Let $\beta \in (0,1]$ be fixed, let $\alpha \in [-1, 1)$ and $L = [-1, -\beta ] \cup [\alpha , 1)$. Suppose $t \rightarrow \infty$ as $n \rightarrow \infty$ and let C be a spherical L-code such that $G_C$ is the disjoint union of $\ell$ $\alpha$-cliques $Y_1, \ldots , Y_{\ell }$ each of size t, such that the number of $\beta$-edges between any $Y_i$ and $Y_j$ is at least $t^2(1 - o(1))$. Then $\ell \le 1 + \alpha / \beta + o(1)$.

Proof

Let A be the number of $\alpha$-edges and B be the number of $\beta$-edges in $G_C$. Since the remaining $\left( {\begin{array}{c}|C|\\ 2\end{array}}\right) - A - B$ edges have value at most 1, we have as in the proof of Lemma 2.1 that

$$\begin{aligned} 0 \le \left\| {\sum _{x \in C}{x}}\right\| ^2 \le |C| - 2B \beta + 2 A \alpha + |C|(|C|-1) - 2B - 2A,\end{aligned}$$

which implies $2 B ( \beta + 1) + 2 A ( 1 - \alpha ) \le |C|^2$. Now observe that C has size $\ell t$, $\ell \left( {\begin{array}{c}t\\ 2\end{array}}\right)$ $\alpha$-edges inside the parts, and at least $\genfrac(){0.0pt}1{\ell }{2}t^2 (1 - o(1))$ $\beta$-edges between parts. Thus if we substitute these values into the above inequality and solve for $\ell$, we obtain the required

$$\begin{aligned} \ell \le \frac{ \beta + \alpha + \frac{1 - \alpha }{t} - o(1)(1 + \beta )}{\beta - o(1)(1 + \beta )} = 1 + \frac{\alpha }{\beta } + o(1). \end{aligned}$$

$\square$

Now we have all of the necessary tools to prove the main theorem of this section.

Proof of Theorem 3.1

Suppose first that $|\alpha | < 1/\log \log n = o(1)$. Let $Q= M_C - \alpha J$. By the subadditivity of the rank we have $\text { rk }(Q) \le \text { rk }(M_C) + \text { rk }(J) \le n+ 1$. Consider some $x \in C$. Let $N = d_{\beta }(x)$ and let $-\beta _1, \ldots , -\beta _N$ be the values of the negative edges incident to x. By Lemma 3.4 we have $\sum _{j=1}^N \beta _j^2 \le 1 + o(1)$ and $\alpha N = o(1)$. It follows that if i is the row corresponding to x in N, then

$$\begin{aligned} \sum _{j \ne i}{Q_{i,j}^2} = \sum _{j=1}^N{(\beta _j + \alpha )^2} \le \sum _{j=1}^N{\beta _j^2} + 2 |\alpha | N + \alpha ^2 N \le 1 + o(1). \end{aligned}$$

Noting that Q has $1 - \alpha$ on the diagonal, we obtain

$$\begin{aligned} \text {tr}(Q^2)= & {} \sum _{i = 1}^{|C|}{Q_{i,i}^2} + \sum _{i = 1}^{|C|}{\sum _{j \ne i}{ Q_{i,j}^2 }} \\\le & {} |C| (1 - \alpha ) + |C| \left( 1 + o(1)) \right) \le |C|(2 + o(1)). \end{aligned}$$

Thus applying Lemma 2.9 to Q yields

$$\begin{aligned} |C|^2(1-\alpha )^2 = \text { tr }(Q)^2 \le \text { tr }(Q^2) \text { rk }(Q) \le |C|(2 + o(1)) (n+ 1). \end{aligned}$$

After dividing by $|C|(1-\alpha )^2 = |C|(1-o(1))$, we obtain the required $|C| \le 2n+o(n)$.

We now prove the theorem for all remaining values of $\alpha$, that is, for all $\alpha$ satisfying $|\alpha | \ge 1/ \log \log n$. If $\alpha < 0$ we are done by Lemma 2.1. Suppose therefore that $\alpha >0$. Let $\ell = 1 + \alpha /\beta$ and $t = \tfrac{1}{4}\log n$. Suppose for the sake of contradiction that there exists some $\epsilon > 0$ so that for arbitrarily large $n$,

$$\begin{aligned} |C| > 2\ell (1 + 2\epsilon ) n. \end{aligned}$$

From Lemma 2.1 we know that $G_C$ doesn’t contain a negative clique bigger than $\beta ^{-1} + 2$. By Ramsey’s theorem, there exists some integer R so that every graph on at least R vertices contains either a negative clique of size at least $\beta ^{-1} + 2$ or a positive clique of size t. A well-known bound of Erdős and Szekeres [11] shows $R \le 4^t \le \sqrt{n} < |G_C|$. Therefore $G_C$ contains a positive clique Y of size t.

For any $T \subset Y$, let $S_T$ comprise all vertices v in $G_C {\setminus } Y$ for which vy ($y\in Y$) is an $\alpha$-edge precisely when $y \in T$. Given some $T \subset Y$ with $\sqrt{t} \le |T| <t$, pick a vertex $z \in Y{\setminus } T$ and consider the $[-1,-\beta ] \cup \{\alpha \}$-code $S_T \cup T \cup \{z\}$. Since any edge incident to T is an $\alpha$-edge, all edges between $S_T$ and z are $\beta$-edges and $|T| \ge \sqrt{t} > 1/\alpha ^2$, we can apply Lemma 3.2 to deduce that $|S_T| < 1/\beta ^2$. For $T=Y$, since $p_Y(S_Y)$ is a $[-1,-\beta ] \cup \{\alpha '\}$-code for $\alpha ' = 1/(t+1/\alpha ) < 1/\log \log n$, we infer $|S_Y| < (2+ \epsilon )n$ for sufficiently large $n$ from the first part of the proof. Now let

$$\begin{aligned} G' = G_C {\setminus } \biggl ( Y \cup \bigcup _{\begin{array}{c} T \subset Y \\ |T| > \sqrt{t} \end{array}}{S_T} \biggr ) \end{aligned}$$

and note that for all $x \in G'$, $|N_{\alpha }(x) \cap Y| = o(t)$. Applying the bounds derived above, we obtain

$$\begin{aligned} \left| Y \cup \bigcup _{\begin{array}{c} T \subset Y \\ |T| > \sqrt{t} \end{array}}{S_T} \right| \le t + 2^{t}/\beta ^2 + |S_Y| \le 2(1+\epsilon ) n. \end{aligned}$$

We can therefore iterate this procedure $\ell$ times to obtain $\ell$ disjoint $\alpha$-cliques $Y_1, \ldots , Y_{\ell }$ and a disjoint graph $G'$ of size at least $2\epsilon n > \sqrt{n}$, so that the number of $\alpha$-edges between $Y_i$ and $Y_j$ is $o(t^2)$ for distinct i and j. Since $|G'| > \sqrt{n}$, there exists an additional $\alpha$-clique $Y_{\ell + 1} \subset G'$ of size t, also with $o(t^2)$ edges to any $Y_i$. But then the induced subgraph on $Y_1 \cup \cdots \cup Y_{\ell + 1}$ contradicts Lemma 3.5, finishing the proof. $\square$

4 A construction

In this section we prove Theorem 1.5, which states that for any positive integers n, k, r and $\alpha _1 \in (0,1)$ with k and $\alpha _1$ fixed and $r \le \sqrt{n}$, there exist $\alpha _2, \ldots , \alpha _k$, $\beta = \alpha _1 / r - O(\sqrt{\log (n) / n})$ and a spherical L-code of size $(1 + r) \left( {\begin{array}{c}n\\ k\end{array}}\right)$ in $\mathbb {R}^{n + r}$ with $L = [-1, -\beta ] \cup \{ \alpha _1, \ldots , \alpha _k \}$. This construction shows that the second statement of Theorem 1.4 is tight up to a constant factor. It also answers a question of Bukh. In [5] he asked whether for fixed $\alpha$, any spherical $[-1, 0) \cup \{\alpha \}$-code has size at most linear in the dimension. Theorem 1.5 gives an example of such a code with size that is superlinear in the dimension. Indeed, for any $\alpha$ fixed, if we choose $r = \sqrt{n} / \log (n)$ then by Theorem 1.5, we obtain a $[-1, -\beta ] \cup \{\alpha \}$-code of size at least $r n = n^{3/2} / \log {n}$ in $\mathbb {R}^{(1+o(1))n}$, where $\beta > 0$ for n large enough.

Given vectors $u \in \mathbb {R}^n$ and $v \in \mathbb {R}^m$, we let (u, v) denote the concatenated vector in $\mathbb {R}^{n + m}$. We first give an outline of the construction. We start by finding a $\{0, 1/k, \ldots , (k-1)/k\}$-code C of size $\left( {\begin{array}{c}n\\ k\end{array}}\right)$, given by Lemma 4.1. We then take a regular r-simplex so that all inner products are negative. For each vector v of the simplex, we take a randomly rotated copy $C_v$ of C and attach a scaled $C_v$ to v by concatenation, and then normalise all vectors to be unit length. That is, for all $u \in C_v$ we take $(\lambda u,v) / \sqrt{\lambda ^2 + 1}$ where $\lambda$ is a scaling factor chosen so that the resulting code has the given $\alpha _1$ as one of its inner products. By randomly rotating the copies of C, we ensure that the inner products between vectors coming from different copies remain negative. This follows from the well-known fact that the inner product between random unit vectors is unlikely to be much bigger than $1/\sqrt{n}$, given by Lemma 4.2.

Lemma 4.1

For any positive integers n, k with $k \le n$, there exists a spherical $\{0, 1/k, \ldots , (k-1)/k\}$-code of size $\left( {\begin{array}{c}n\\ k\end{array}}\right)$ in $\mathbb {R}^n$.

Proof

Let C be the set of $\{0,1\}$-vectors in $\mathbb {R}^n$ having exactly k 1’s. Then $|C| = \left( {\begin{array}{c}n\\ k\end{array}}\right)$ and for any distinct $u, v \in C$, we observe that $\left\langle u, v \right\rangle \in \{0, 1, \ldots , k-1\}$. Since $\Vert {u}\Vert ^2= k$ for all $u \in C$, we thus obtain that $C / \sqrt{k}$ is a $\{0, 1/k, \ldots , (k-1)/k\}$-code. $\square$

The following lemma follows from the well known bound for the area of a spherical cap, which can be found in [22, Corollary 2.2].

Lemma 4.2

Let $u,u' \in \mathbb {R}^{n}$ be unit vectors chosen independently and uniformly at random. Then for all $t> 0$,

$$\begin{aligned} {{\mathrm{Pr\,}}}[ \left\langle u, u' \right\rangle \ge t ] < e^{- t^2 n / 2 }.\end{aligned}$$

We are now ready to prove Theorem 1.5.

Proof of Theorem 1.5

Let $L = \{0, 1/k, \ldots , (k-1)/k\}$ and let C be an L-code of size $\left( {\begin{array}{c}n\\ k\end{array}}\right)$, as given by Lemma 4.1. Let $\lambda = \sqrt{1/\alpha _1 - 1}$ and define

$$\begin{aligned} \alpha _i = \frac{\lambda ^2 (i-1)/k + 1}{\lambda ^2 + 1}\end{aligned}$$

for $2 \le i \le k$. Note that by the choice of $\lambda$, the above also holds for $\alpha _1$. Let $L' = \{\alpha _1, \ldots , \alpha _k\}$.

Let S be a set of $r+1$ unit vectors in $\mathbb {R}^r$ so that $\left\langle v, v' \right\rangle = - 1/r$ for all distinct $v,v' \in S$, i.e. S is a regular r-simplex. For each $v \in S$, let $C_v$ be an independent and uniformly random rotation of C in $\mathbb {R}^n$. We define

$$\begin{aligned} C' = \left\{ \frac{(\lambda u, v)}{\sqrt{\lambda ^2 + 1}} : v \in S, u \in C_v \right\} , \end{aligned}$$

and observe that $\Vert {(\lambda u, v)}\Vert ^2 = \lambda ^2 + 1$, so that $C'$ is indeed a set of unit vectors in $\mathbb {R}^{n+r}$ of size $(1+ r) \left( {\begin{array}{c}n\\ k\end{array}}\right)$. Moreover, for any $v \in S$ and distinct $u, u' \in C_v$, we have

$$\begin{aligned} \left\langle \frac{( \lambda u, v ) }{\sqrt{\lambda ^2 + 1}} , \frac{( \lambda u', v )}{\sqrt{\lambda ^2 + 1}} \right\rangle = \frac{\lambda ^2 \left\langle u, u' \right\rangle + 1}{\lambda ^2 + 1} \in L',\end{aligned}$$

since $\left\langle u, u' \right\rangle \in L$. Finally, suppose that $u \in C_v$ and $u' \in C_{v'}$ for distinct $v, v' \in S$. Observe that $u, u'$ are independent and uniformly random unit vectors in $\mathbb {R}^n$, so we may apply Lemma 4.2 with $t = \sqrt{\left( 4\log {\left( {\begin{array}{c}n\\ k\end{array}}\right) } +2\log n \right) /n}$ to obtain ${{\mathrm{Pr\,}}}[\left\langle u, u' \right\rangle \ge t] < e^{-t^2 n / 2} = n^{-1} \left( {\begin{array}{c}n\\ k\end{array}}\right) ^{-2}$. Now define $\beta = \frac{1/r - \lambda ^2 t}{\lambda ^2 + 1} = \alpha _1 / r - O(\sqrt{\log (n) / n})$ and observe that if $\left\langle u, u' \right\rangle < t$, then

$$\begin{aligned} \left\langle \frac{ (\lambda u, v) }{\sqrt{\lambda ^2 + 1}} , \frac{ ( \lambda u', v' ) }{\sqrt{\lambda ^2 + 1}} \right\rangle = \frac{\lambda ^2 \left\langle u, u' \right\rangle + \left\langle v, v' \right\rangle }{\lambda ^2 + 1} \le \frac{\lambda ^2 t - 1/r}{\lambda ^2 + 1} = - \beta .\end{aligned}$$

Thus it suffices to show that with positive probability, $\left\langle u, u' \right\rangle < t$ for all possible $u, u'$, since then $C'$ will be a $[-1, -\beta ] \cup L'$-code. To that end, we observe that there are $\left( {\begin{array}{c}|S|\\ 2\end{array}}\right) |C|^2 \le n \left( {\begin{array}{c}n\\ k\end{array}}\right) ^2$ such pairs $u, u'$ and so the result follows via a union bound. $\square$

5 Lines with many angles and related spherical codes

5.1 A general bound when $\beta$ is fixed

In this section we give a proof of Conjecture 1.3, i.e. the first statement of Theorem 1.4. To this end, we need a well-known variant of Ramsey’s theorem, whose short proof we include for the convenience of the reader. Let $K_n$ denote the complete graph on n vertices. Given an edge-colouring of $K_n$, we call an ordered pair (X, Y) of disjoint subsets of vertices monochromatic if all edges in $X \cup Y$ incident to a vertex in Y have the same colour. For the graph of a spherical code, we analogously call (X, Y) a monochromatic $\gamma$-pair if all edges incident to a vertex in Y have value $\gamma$.

Lemma 5.1

Let k, t, m, n be positive integers satisfying $n>k^{kt}m$ and let $f :E(K_n) \rightarrow [k]$ be an edge k-colouring of $K_n$. Then there is a monochromatic pair (X, Y) such that $|X|=m$ and $|Y|=t$.

Proof

Construct kt vertices $v_1,\dots ,v_{kt}$ and sets $X_1, \ldots , X_{kt}$ as follows. Fix $v_1$ arbitrarily and let $c(1) \in [k]$ be a majority colour among the edges $(v_1,u)$. Set $X_1=\{u: f(v_1,u)=c(1)\}$. By the pigeonhole principle, $|X_1| \ge \lceil (n-1)/k\rceil \ge k^{kt-1}m$. In general, we fix any $v_{i+1}$ in $X_i$, let $c(i+1) \in [k]$ be a majority colour among the edges $(v_{i+1},u)$ with $u \in X_i$, and let $X_{i+1}=\{u \in X_i: f(v_{i+1},u)=c(i+1)\}$. Then $|X_{i+1}| \ge \lceil (|X_i|-1)/k\rceil \ge k^{kt-i-1}m$, and for every $1 \le j \le i$ the edges from $v_j$ to all vertices in $X_{i+1}$ have colour c(j). Since we have only k colours, there is a colour $c \in [k]$ and $S \subset [kt]$ with $|S|=t$ so that $c(j) = c$ for all $j \in S$. Then $Y=\{v_j: j \in S\}$ and $X=X_{kt}$ form a monochromatic pair of colour c, satisfying the assertion of the lemma. $\square$

We will also need the following simple corollary of Turán’s theorem, which can be obtained by greedily deleting vertices together with their neighbourhoods.

Lemma 5.2

Every graph on n vertices with maximum degree $\Delta$ contains an independent set of size at least $\frac{n}{\Delta +1}$.

Finally, we will need the bound on the size of an L-code previously mentioned in the introduction, see [9, 18].

Lemma 5.3

If $L \subseteq \mathbb {R}$ with $|L|=k$ and C is an L-spherical code in $\mathbb {R}^n$ then $|C| \le \left( {\begin{array}{c}n+k\\ k\end{array}}\right)$.

Now we have the tools necessary to verify Conjecture 1.3.

Proof of first part of Theorem 1.4

We argue by induction on k. The base case is $k=0$, when $L = [-1,-\beta ]$, and we can take $c_{\beta ,0} = \beta ^{-1}+1$ by Lemma 2.1. Henceforth we suppose $k>0$. We can assume $n \ge n_0= (2k)^{2k\beta ^{-1}}$. Indeed, if we can prove the theorem under this assumption, then for $n<n_0$ we can use the upper bound for $\mathbb {R}^{n_0}$ (since it contains $\mathbb {R}^n$). Then we can deduce the bound for the general case by multiplying $c_{\beta , k}$ (obtained for the case $n \ge n_0$) by a factor $n_0^k=(2k)^{2k^2 \beta ^{-1}}$. Now suppose C is an L-code in $\mathbb {R}^n$, where $L = [-1,-\beta ] \cup \{\alpha _1,\dots ,\alpha _k\}$, with $\alpha _1<\cdots <\alpha _k$.

Consider the case $\alpha _k < \beta ^2/2$. We claim that $\Delta _{\beta } \le 2\beta ^{-2}+1$. Indeed, for any $y, x_1, x_2 \in G_C$ with $\left\langle y, x_1 \right\rangle , \left\langle y, x_2 \right\rangle \le - \beta$, we have by the proof of Lemma 2.4 that

$$\begin{aligned} \left\langle p_{y}(x_1), p_{y}(x_2) \right\rangle= & {} \frac{\left\langle x_1, x_2 \right\rangle - \left\langle y, x_1 \right\rangle \left\langle y, x_2 \right\rangle }{\sqrt{1- \left\langle y, x_1 \right\rangle ^2}\sqrt{1-\left\langle y, x_2 \right\rangle ^2}}\\\le & {} \frac{\alpha _k - \beta ^2}{\sqrt{1- \left\langle y, x_1 \right\rangle ^2}\sqrt{1-\left\langle y, x_2 \right\rangle ^2}} < -\beta ^2/2\,.\end{aligned}$$

Thus the projection of the $\beta$-neighborhood of y satisfies $|p_{y}(N_{\beta }(y))| \le 2\beta ^{-2}+1$ by Lemma 2.1, as claimed. By Lemma 5.2, the graph of $\beta$-edges in $G_C$ has an independent set S of size $|C|/(2\beta ^{-2}+2)$. Therefore S is an $\{\alpha _1,\dots ,\alpha _k\}$-code, so $|S| \le n^k+1 \le 2n^k$ by Lemma 5.3. Choosing $c_{\beta , k} > 4\beta ^{-2}+4$, we see that the theorem holds in this case. Henceforth we suppose $\alpha _k \ge \beta ^2/2$.

Next consider the case that there is $\ell \ge 2$ such that $\alpha _{\ell -1} < \alpha _\ell ^2/2$. Choosing the maximum such $\ell$ we have

$$\begin{aligned} \alpha _\ell ^2/2=2(\alpha _\ell /2)^2 \ge 2(\alpha _{\ell +1}/2)^4 \ge \cdots \ge 2(\alpha _k/2)^{2^{k-\ell +1}} \ge \beta ' := (\beta /2)^{2^k}.\nonumber \\ \end{aligned}$$

(6)

Note that by induction the graph of $\{\beta , \alpha _1, \ldots , \alpha _{\ell - 1}\}$-edges in $G_C$ contains no clique of order $c_{\beta , \ell - 1} n^{\ell - 1}$, so by Lemma 5.2 its complement has maximum degree at least $m = |C| / (2 c_{\beta , \ell - 1} n^{\ell - 1})$. Letting $y \in G_C$ be a vertex attaining this maximum degree in $\{\alpha _\ell , \ldots , \alpha _k\}$-edges, we have by the pigeonhole principle that there exists $J \subset G_C$ of size at least m / k, and an index $\ell \le s \le k$ such that $\left\langle x, y \right\rangle = \alpha _s$ for all $x \in J$. Now observe that for any $x_1, x_2 \in G_C$ with $\left\langle x_1, x_2 \right\rangle \in [-1, -\beta ] \cup \{\alpha _1, \ldots , \alpha _{\ell -1}\}$, we have by Lemma 2.4 and Remark 2.5 that

$$\begin{aligned} \left\langle p_{y}(x_1), p_{y}(x_2) \right\rangle =\frac{ \left\langle x_1, x_2 \right\rangle - \alpha _s^2 }{1-\alpha _s^2} \le \alpha _\ell ^2/2 - \alpha _\ell ^2 < -\alpha _\ell ^2/2 \le - \beta '.\end{aligned}$$

Furthermore, by Lemma 2.4 we have that $p_y(J)$ is an $L'$-code, where $L' = [-1,-\beta '] \cup \{\alpha '_\ell ,\dots ,\alpha '_k\}$, with $\alpha '_i = \frac{\alpha _i - \alpha _s^2}{1-\alpha _s^2}$ for $i \ge \ell$. By the induction hypothesis, we have $|J| \le c_{\beta ', k - \ell + 1} n^{k-\ell +1}$, so choosing $c_{\beta , k} > 2 k c_{\beta , \ell - 1} c_{\beta ', k - \ell + 1}$ the theorem holds in this case.

Now suppose that there is no $\ell >1$ such that $\alpha _{\ell -1} < \alpha _\ell ^2/2$. We must have $\alpha _1>0$. Let $t=\lceil 1/\beta ' \rceil$. We apply Lemma 5.1 to find a monochromatic pair (X, Y) with $|Y|=t$ and $|X|=m\ge (k+1)^{-(k+1)t} n$. Since $G_C$ has no $\beta$-clique of size t by Lemma 2.1, (X, Y) must be a monochromatic $\alpha _r$-pair for some $1 \le r \le k$. Let $X' = p_Y(X)$ be the projection of X onto the orthogonal complement of Y. By Lemma 2.4 and Remark 2.5, we have that $X'$ is a $[-1, \beta ] \cup \{\alpha _1', \ldots , \alpha _k'\}$-code, where

$$\begin{aligned} \alpha _i' = \frac{\alpha _i - \alpha _r}{1 - \alpha _r} + \frac{\alpha _r(1 - \alpha _i)}{(1 + \alpha _r t)(1 - \alpha _r)} \quad \text {for } 1 \le i \le k. \end{aligned}$$

We can assume $\alpha '_k \ge \beta ^2/2$, since otherwise choosing $c_{\beta , k} > (k+1)^{(k+1)t} (4\beta ^{-2}+4)$ we are done by the first case considered above. Since $\alpha '_r=(\alpha _r^{-1}+t)^{-1}<\beta '$, the computation in (6) implies that there exists $\ell >1$ such that $\alpha _{\ell -1} < \alpha _\ell ^2/2$. Choosing $c_{\beta , k} > (k+1)^{(k+1)t} 2 k c_{\beta , \ell - 1} c_{\beta ', k - \ell + 1}$ we are done by the second case considered above. $\square$

5.2 An asymptotically tight bound when $\beta , \alpha _1, \ldots , \alpha _k$ are fixed

The goal of this section will be to prove the second statement of Theorem 1.4. The case $k = 1$ is given by Theorem 3.1, so henceforth we assume that we are given a fixed $k \ge 2$.

Our general strategy will be to use projections in order to reduce the number of positive angles and then apply induction. When projecting onto the orthogonal complement of a large clique, Lemma 2.4 tells us that the new inner product will be some function of the old one plus o(1). In view of this, it will be convenient to prove the following, slightly more general version of Theorem 1.4.

Theorem 5.4

Let $\beta \in (0,1]$, $\alpha _1, \ldots , \alpha _k \in [0, 1)$ be fixed with $\alpha _1< \cdots < \alpha _k$ and let $n\in \mathbb {N}$. If C is a spherical $[-1, -\beta + o(1)] \cup \{ \alpha _1 + o(1), \ldots , \alpha _k + o(1)\}$-code in $\mathbb {R}^n$, then

$$\begin{aligned} |C| \le \left( 1 + \frac{\alpha _1}{\beta } \right) (k-1)!(2n)^k + o(n^k)\end{aligned}$$

for n sufficiently large.

Remark 5.5

We use $\gamma + o(1)$ to refer to a specific $\gamma ^* \in \mathbb {R}$ depending on n such that $\gamma ^* = \gamma + o(1)$, not a range of possible values near $\gamma$. We will still say $\gamma$-edge, $\Delta _\gamma$, etc. when we are referring to a $(\gamma + o(1))$-edge, $\Delta _{\gamma + o(1)}$, etc. in the graph $G_C$.

The case $k = 1$ of Theorem 5.4 follows by inserting o(1) terms into expressions in the proof of Theorem 3.1, and so we henceforth assume that it holds. Moreover, since we will be making use of induction, we also assume that Theorem 5.4 holds for all $k' < k$. Now let $\beta \in (0,1]$ and $\alpha _1, \ldots , \alpha _k \in [0, 1)$ be fixed with $\alpha _1< \cdots < \alpha _k$ and let $n \in \mathbb {N}$. Let C be a spherical $[-1, -\beta + o(1)] \cup \{ \alpha _1 + o(1), \ldots , \alpha _k + o(1)\}$-code in $\mathbb {R}^n$.

The argument will be a generalisation of the one used to prove Theorem 3.1 and so we will need to generalise some lemmas. Firstly, we will need the following generalisation of Lemma 3.2.

Lemma 5.6

Let $\alpha \in (0,1)$ and $\gamma \in [-1,1)$ be distinct reals. Let $X \cup Y \cup \{ z\}$ be a set of unit vectors in $\mathbb {R}^n$ so that $Y \cup \{z\}$ is an $\{\alpha \}$-code, that all edges inside X have value at most $\alpha$, that all edges between X and Y have value at least $\alpha$ and that all edges between X and z all have value at least $\gamma$ if $\gamma > \alpha$ and at most $\gamma$ if $\gamma < \alpha$. Suppose furthermore that $|Y| > 4/\bigl (\alpha (\gamma -\alpha )^2\bigr )$. Then $|X| < 1/(\gamma - \alpha )^2$.

Proof

Let $\alpha _X$ denote the average value of the edges inside X, $\alpha _Y$ the average value of the edges between X and Y and $\gamma _z$ the average value of the edges between X and z. Note that our assumptions imply $\alpha _Y \ge \alpha \ge \alpha _X$ and $|\gamma _z - \alpha | \ge |\gamma - \alpha |$. Let M be the Gram matrix of $X \cup Y \cup \{z \}$ and let $v = (x, \dots , x, y, \dots , y, \zeta )^\intercal$, where

$$\begin{aligned} x = 1/|X|, \quad y = -\frac{(\alpha _Y-\alpha \gamma _z)/|Y|}{\alpha - \alpha ^2 + (1 -\alpha )/|Y|} \quad \text {and} \quad \zeta = -(\gamma _z + y |Y| \alpha ). \end{aligned}$$

Then, similarly to the proof of Lemma 3.2,

$$\begin{aligned} {\begin{matrix} \left\langle Mv, v \right\rangle &{}= \frac{|X|+(|X|^2-|X|)\alpha _X}{|X|^2} + 2y|Y|\alpha _Y + y^2((|Y|^2-|Y|)\alpha + |Y|) \\ &{}\quad + 2\zeta (\gamma _z + y|Y|\alpha ) + \zeta ^2 \\ &{}= \frac{1-\alpha _X}{|X|}+\alpha _X -\gamma _z^2 + 2y|Y|(\alpha _Y- \alpha \gamma _z) \\ &{}\quad + y^2|Y|^2\bigl (\alpha -\alpha ^2 + (1-\alpha )/|Y|\bigr ) \\ &{}\le \frac{1-\alpha }{|X|}+\alpha -\gamma _z^2 - \frac{(\alpha _Y - \alpha \gamma _z)^2}{\alpha -\alpha ^2 + (1-\alpha )/|Y|}, \end{matrix}} \end{aligned}$$

where the last inequality uses $\alpha _X \le \alpha$. Note that $\alpha _Y \ge \alpha \ge \alpha \gamma _z$, so $(\alpha _Y-\alpha \gamma _z)^2 \ge \alpha ^2(1-\gamma _z)^2$. Since $\left\langle Mv, v \right\rangle \ge 0$ and $(\gamma _z - \alpha )^2 \ge (\gamma - \alpha )^2$, it is therefore sufficient to prove that

$$\begin{aligned} \alpha -\gamma _z^2 - \frac{\alpha ^2(1 - \gamma _z)^2}{\alpha -\alpha ^2 + (1-\alpha )/|Y|} < -(\gamma _z - \alpha )^2. \end{aligned}$$

As one can easily check, this can be rewritten as $|Y| \ge (1-\alpha )(1+\alpha - 2\gamma _z)/\alpha (\gamma _z-\alpha )^2$, which is true by assumption. $\square$

We will also need the following generalisation of Lemma 3.4.

Lemma 5.7

If $\alpha _1 = 0$, then $G_C$ has the following degree bounds:

• (i) $\Delta _{\alpha _i} \le \frac{1}{\alpha _i} (k-2)! (2n)^{k-1} + o(n^{k-1})$ for all $2 \le i \le k$.

• (ii) If $-\beta _1, \dots , -\beta _{N}$ are the values of the $\beta$-edges incident to some $x \in G_C$, then $N \le O(n^{k-1})$ and

  $$\begin{aligned} \sum _{i = 1}^{N} \beta _i^2 \le (k-1)! (2n)^{k-1} + o(n^{k-1}). \end{aligned}$$

Proof

Let $x \in C$ and let $C' = p_{x}(N_{\alpha _i}(x))$ be the normalised projection of the $\alpha _i$-neighbours of x onto $\text {span}(x)^{\perp }$. By Lemma 2.4, we see that $C'$ is a $[-1, -\beta ' + o(1)] \cup \{\alpha _1' + o(1), \ldots , \alpha _k' + o(1)\}$-spherical code for

$$\begin{aligned} \alpha _j' = \frac{\alpha _j - \alpha _i^2}{1 - \alpha _i^2} \text { for } 1 \le j \le k, \quad \beta ' = \frac{\beta + \alpha _i^2}{1 - \alpha _i^2}. \end{aligned}$$

In particular $\alpha _{1}' = \frac{ - \alpha _i^2}{1 - \alpha _i^2} < 0$. Now let $\ell$ be the largest integer such that $\alpha _{\ell }' < 0$ and observe that $C'$ is, in particular, a $[-1, \alpha _{\ell }' + o(1)] \cup \{\alpha _{\ell + 1}' + o(1), \ldots , \alpha _k' + o(1)\}$-code. If $\ell \ge 2$ then applying Theorem 5.4 by induction we obtain $|C'| \le O(n^{k-\ell })$, which trivially implies (i). Otherwise $\alpha _2' \ge 0$ and applying Theorem 5.4 by induction we obtain

$$\begin{aligned} |C'| \le \left( 1 + \frac{\alpha '_{2}}{-\alpha _{1}'} \right) (k-2)! (2n)^{k-1} + o(n^{k-1}). \end{aligned}$$

To verify (i), it suffices to observe that $1 - \alpha _2 '/ \alpha _1' = 1 + (\alpha _2 - \alpha _i^2) / \alpha _i^2 = \alpha _2 / \alpha _i^2 \le 1 / \alpha _i$.

Now we derive the upper bound on $N = d_{\beta }(x)$. Let $M = M_{N_{\beta }(x) \cup \{x\}}$ be the Gram matrix of $N_{\beta }(x) \cup \{x\}$ and let $v = (1, \ldots , 1, \beta N)^{\intercal }$. Then using (i) we conclude

$$\begin{aligned} {\begin{matrix} 0 &{}\le v^\intercal M v \\ &{}\le \sum _{1\le i,j \le N} M_{ij} - \left( \beta ^2 + o(1) \right) N^2 \\ &{}\le N \left( 1 + (\alpha _{1} + o(1)) N + \sum _{j=2}^k{(\alpha _j + o(1))\Delta _{\alpha _j}} \right) - \left( \beta ^2 + o(1) \right) N^2\\ &{}\le N \left( 1 + o(1) N + \sum _{j=2}^k{(\alpha _j + o(1) ) \left( \frac{1}{\alpha _j} (k - 2)! (2n)^{k-1} + o(n^{k-1}) \right) } \right) \\ &{}\quad - \left( \beta ^2 + o(1) \right) N^2\\ &{}\le N \left( 1 + (k-1)! (2n)^{k-1} + o(n^{k-1}) \right) - \left( \beta ^2 + o(1) \right) N^2, \end{matrix}} \end{aligned}$$

which implies $N \le \frac{1}{\beta ^2} (k-1)! (2n)^{k-1} + o(n^{k-1}) = O(n^{k-1})$.

Finally, let $-\beta _1, \dots , -\beta _{N}$ be the values of the $\beta$-edges incident to x and let $w = \left( \beta _1, \dots , \beta _N, \sum _{i=1}^N{\beta _i^2} \right) ^\intercal$. Then

$$\begin{aligned} {\begin{matrix} 0 \le w^\intercal M w&= - \left( \sum _{i=1}^N{\beta _i^2} \right) ^2 + \sum _{i=1}^N{\beta _i^2} + \sum _{\begin{array}{c} 1\le i,j \le N i \ne j \end{array}} \beta _i\beta _j M_{ij}\\ &{}\le - \left( \sum _{i=1}^N{\beta _i^2} \right) ^2 + \sum _{i=1}^N{\beta _i^2} + \sum _{r = 2}^k{ \alpha _r \left( \sum _{\begin{array}{c} i,j M_{i,j} = \alpha _r + o(1) \end{array}}{\beta _i \beta _j} \right) } \\ &{}\quad + o(1)\sum _{1 \le i,j \le N}{\beta _i \beta _j}. \end{matrix}} \end{aligned}$$

Applying Cauchy–Schwarz, we obtain

$$\begin{aligned} \sum _{1 \le i,j \le N}{\beta _i \beta _j} = \left( \sum _{i=1}^N{\beta _i} \right) ^2 \le N \sum _{i=1}^{N}{\beta _i^2} \le O(n^{k-1}) \sum _{i=1}^{N}{\beta _i^2}. \end{aligned}$$

Furthermore, for $2 \le r \le k$ we have

$$\begin{aligned} 0 \le \frac{1}{2} \sum _{\begin{array}{c} i,j A_{i,j} = \alpha _r + o(1) \end{array}}{(\beta _i - \beta _j)^2} \le \Delta _{\alpha _r} \sum _{i=1}^{N}{\beta _i^2} - \sum _{\begin{array}{c} i,j A_{i,j} = \alpha _r + o(1) \end{array}}{\beta _i \beta _j}, \end{aligned}$$

and thus we obtain

$$\begin{aligned} \alpha _r \sum _{\begin{array}{c} i,j A_{i,j} = \alpha _r + o(1) \end{array}}{\beta _i \beta _j} \le \left( (k-2)! (2n)^{k-1} + o(n^{k-1}) \right) \sum _{i=1}^{N}{\beta _i^2}. \end{aligned}$$

Combining these inequalities and dividing by $\sum _{i=1}^N{\beta _i^2}$ yields the desired (ii):

$$\begin{aligned} \sum _{i = 1}^{N} \beta _i^2 \le (k-1)! (2n)^{k-1} + o(n^{k-1}). \end{aligned}$$

$\square$

Finally, we will need a new lemma to deal with what happens if the clique we find via Ramsey’s theorem is an $\alpha _i$-clique for $i \ge 2$.

Lemma 5.8

Let $2 \le i \le k$ and suppose $X \cup Y$ is a $[-1, -\beta ] \cup \{ \alpha _1, \ldots , \alpha _k\}$-spherical code with $|Y| \rightarrow \infty$ as $n \rightarrow \infty$, such that all edges incident to any $y \in Y$ are $\alpha _i$-edges. Then $|X| \le O(n^{k-1})$.

Proof

Let $X' = p_Y(X)$ be the normalised projection of X onto $\text {span}(Y)^\perp$. By Lemma 2.4, we have that $X'$ is a $[-1, -\beta ' + o(1)] \cup \{ \alpha _1' + o(1), \ldots , \alpha _k' + o(1)\}$-code for

$$\begin{aligned} \alpha _j' = \frac{\alpha _{j} - \alpha _i }{1-\alpha _i} \text { for } 1 \le j \le k, \quad \beta ' = \frac{\beta + \alpha _i}{1-\alpha _i}. \end{aligned}$$

Observe that $\alpha _{i-1}' = (\alpha _{i-1} - \alpha _i) / (1 - \alpha _i) < 0$, so that $X'$ is, in particular, a $[-1, \alpha _{i-1}' + o(1)] \cup \{\alpha _{i}' + o(1), \ldots , \alpha _k' + o(1) \}$-code and hence we may apply Theorem 5.4 by induction to conclude $|X'| \le O(n^{k-i+1}) \le O(n^{k-1})$. $\square$

We now have all of the necessary lemmas to finish the proof of Theorem 5.4.

Proof of Theorem 5.4

Suppose first that $\alpha _1 = 0$. Let $Q = M_C - (\alpha _1 + o(1)) J$; by the subadditivity of the rank we have $\text { rk }(Q) \le \text { rk }(M_C) + \text { rk }(J) \le n + 1$. Now fix some $x \in C$, and let $N = d_{\beta }(x)$ and $\beta _1, \ldots , \beta _N$ be the values of the $\beta$-edges incident to x. Using parts (i) and (ii) of Lemma 5.7, it follows that if i is the row corresponding to x in Q then

$$\begin{aligned} {\begin{matrix} \sum _{j \ne i}{Q_{i,j}^2} &{}\le \sum _{j=1}^N{(-\beta _j - (\alpha _1 + o(1)))^2} + \sum _{r = 2}^{k}{(\alpha _r - \alpha _1 + o(1))^2 \Delta _{\alpha _r} }\\ &{}\le (1 + o(1) )\left( (k-1)! (2n)^{k-1} + o(n^{k-1}) \right) \\ &{}\quad + \sum _{r = 2}^{k}{ (k-2)! (2n)^{k-1} + o(n^{k-1}) } \\ &{}\le 2(k-1)! (2n)^{k - 1} + o(n^{k - 1}). \end{matrix}} \end{aligned}$$

Noting that Q has $1 - (\alpha _1 + o(1)) = 1 - o(1)$ on the diagonal, we obtain

$$\begin{aligned} \text {tr}(Q^2)= & {} \sum _{i = 1}^{|C|}{Q_{i,i}^2} + \sum _{i = 1}^{|C|}{\sum _{j \ne i}{ Q_{i,j}^2 }} \le |C| \left( 1 + 2(k-1)! (2n)^{k - 1} + o(n^{k - 1}) \right) . \end{aligned}$$

Thus applying Lemma 2.9 to Q yields

$$\begin{aligned} |C|^2(1-o(1))^2= & {} \text {tr}(Q)^2 \le \text {tr}(Q^2) \text { rk }(Q) \\\le & {} |C| \left( 1 + 2(k-1)! (2n)^{k - 1} + o(n^{k - 1}) \right) (n+1). \end{aligned}$$

Dividing by $|C|(1-o(1))^2$, we obtain the required $|C| \le (k-1)! (2n)^k + o(n^k)$.

We will now prove the theorem for $\alpha _1 > 0$. Let $t = \log {\log {n}}$, let $\epsilon \rightarrow 0$ sufficiently slowly as $n \rightarrow \infty$ and suppose for sake of contradiction that $|C| \ge (1 + \alpha _1 / \beta )(k-1)! (2n)^{k} + \epsilon n^{k}$. Let $m = \lceil |C|/(k+1)^{(k+1)t} - 1 \rceil$ so that $|C| > (k+1)^{(k+1)t}m$.

Regarding a $\gamma$-edge of C as an edge coloured with the colour $\gamma$, we deduce by Lemma 5.1 that there are some subsets X and Y of C so that $|X| = m$, $|Y| = t$ and (X, Y) is a monochromatic $\gamma$-pair for some $\gamma \in \{ \beta , \alpha _1, \ldots , \alpha _k\}$. Since $t > \frac{1}{\beta } +1$ for n sufficiently large, Y cannot be a $\beta$-clique by Lemma 2.1 and hence (X, Y) cannot be a monochromatic $\beta$-pair. Hence it must be a monochromatic $\alpha _i$-pair. If $2 \le i \le k$, then by Lemma 5.8 we conclude $\Omega ( n^k / (k+1)^{(k+1)t } ) \le m \le O(n^{k-1})$, a contradiction for n large enough by our choice of t. Hence, (X, Y) must be a monochromatic $\alpha _1$-pair and hence C contains an $\alpha _1$-clique Y of size t.

For each $T \subseteq Y$, let $S_T$ be the set of vertices $x \in G_C {\setminus } Y$ so that $N_{\beta }(x) \cap Y = Y {\setminus } T$. Now fix $T \subseteq Y$ and let $t_1, \dots , t_{|T|}$ be some ordering of the elements of T. For each pattern of the form $p \in [k]^{|T|}$, let $S_T(p)$ consist of all $x \in S_T$ for which $\langle x, t_i \rangle = \alpha _{p_i} + o(1)$ for all i.

Define $t^* = 4/\bigl (\alpha _1(\beta + \alpha _1)^2\bigr ) + o(1)$ and suppose first that $t^* \le |T| < t$. We claim that $S_T(p)$ does not contain an $\alpha _1$-clique of size larger than $1 / \beta ^2 + o(1)$ for any $p \in [k]^{|T|}$. To that end, fix some $z \in Y {\setminus } T$ and let X be an $\alpha _1$-clique in $S_T(p)$. Note that, for any $x \in X$, $\left\langle x, z \right\rangle < -\beta + o(1)$ and $|T| \ge t^* > 4/\bigl ((\alpha +o(1))(\beta +\alpha +o(1))^2\bigr )$, so that we may apply Lemma 5.6 to $X \cup T \cup \{z\}$ to conclude that $|X|< 1/(\beta +\alpha )^2 + o(1) < 1/ \beta ^2 + o(1)$.

Now let $m' = \lceil |S_T(p)|/(k+1)^{(k+1)t} - 1 \rceil$ so that $|S_T(p)| > (k+1)^{(k+1)t}m'$. Then by Lemma 5.1, $S_T(p)$ contains an $(X',Y')$ monochromatic pair with $|X'| = m'$ and $|Y'| = t$. Since $t > 1 / \beta ^2 + o(1)$ for n large enough, $Y'$ cannot be a monochromatic $\alpha _1$-clique or $\beta$-clique, and thus $(X',Y')$ is a monochromatic $\alpha _i$-pair for some $2 \le i \le k$. Thus by Lemma 5.8, we conclude that $m' \le O(n^{k-1})$. Since this holds for all p, we obtain

$$\begin{aligned} |S_T|= & {} \sum _{p \in [k]^{|T|}}{|S_T(p)|} \le k^{|T|} (k+1)^{(k+1)t} O \left( n^{k-1} \right) \\\le & {} (k+1)^{(k+2)t} O\left( n^{k-1} \right) .\end{aligned}$$

Now suppose that $T = Y$ and let $p \in [k]^{t} \backslash \{(1, \ldots , 1)\}$. We claim that $S_Y(p)$ does not contain an $\alpha _1$-clique of size larger than $1 / (\alpha _2 - \alpha _1)^2 + o(1)$. To that end, fix an index j such that $p_j \ge 2$ and let X be an $\alpha _1$-clique in $S_Y(p)$. Note that, for any $x\in X$, $\left\langle t_j, x \right\rangle = \alpha _{p_j}+o(1) \ge \alpha _2+o(1)$. Furthermore, for sufficiently large $n$, we have $t > 4 /\bigl (\alpha _1(\alpha _2 - \alpha _1 )^2\bigr ) + o(1)$. Therefore, we may apply Lemma 5.6, with $\alpha = \alpha _1 + o(1)$ and $\gamma = \alpha _2 + o(1)$, to $X \cup T' \cup \{z\}$, where $z = t_j$ and $T' = Y \backslash \{t_j\}$, to conclude that $|X| < 1/(\alpha _2 - \alpha _1)^2 + o(1)$.

As above, let $m' = \lceil |S_Y(p)|/(k+1)^{(k+1)t} - 1 \rceil$ and observe that by Lemma 5.1, $S_Y(p)$ contains an $(X',Y')$ monochromatic pair with $|X'| = m$ and $|Y| = t$. Since t is large enough, it cannot be a $\beta$ or $\alpha _1$-pair, so it must be a monochromatic $\alpha _i$ for some $2 \le i \le k$, and hence by Lemma 5.8, we conclude that $m' \le O(n^{k-1})$. Thus we obtain

$$\begin{aligned}&\sum _{p \in [k]^{t} \backslash \{(1, \ldots , 1)\}}{|S_Y(p)|} \\&\quad \le k^{|T|} (k+1)^{(k+1)t} O \left( n^{k-1} \right) \le (k+1)^{(k+2)t} O\left( n^{k-1} \right) . \end{aligned}$$

Finally, let $p = (1, \ldots , 1)$. and define $X' = p_{Y}(S_Y(1, \ldots , 1))$ to be the normalised projection of $S_Y(1,\ldots , 1)$ onto $\text {span}(Y)^{\perp }$. By Lemma 2.4 we have that $X'$ is a $[ -1, - \beta ' + o(1) ] \cup \{\alpha _1' + o(1), \ldots , \alpha _k' + o(1)\}$-spherical code for

$$\begin{aligned} \alpha _j' = \frac{\alpha _{j} - \alpha _1}{1-\alpha _1} \text { for } 1 \le j \le k, \quad \beta ' = \frac{\beta + \alpha _1}{1-\alpha _1}. \end{aligned}$$

Since $\alpha _1' = 0$, we can apply the previous case of Theorem 5.4 to obtain $|X'| \le (k-1)! (2n)^k + o(n^k)$. It follows that

$$\begin{aligned} |S_Y|= & {} |S_Y(1, \ldots , 1)| + \sum _{p \in [k]^{t} \backslash \{(1, \ldots , 1)\}}{|S_Y(p)|} \\\le & {} (k-1)! (2n)^k + o(n^k) + (k+1)^{(k+2)t} O \left( n^{k-1} \right) \\= & {} (k-1)! (2n)^k + o(n^k). \end{aligned}$$

Noting that $(k+1)^{(k+2)t} = o(n)$, we therefore obtain

$$\begin{aligned} \left| \bigcup _{T \subseteq Y, |T| \ge t^*}{S_T} \right|= & {} |S_Y| + \left| \bigcup _{T \subset Y, |T| \ge t^*}{S_T} \right| \\\le & {} (k-1)! (2n)^k + o(n^k) + 2^t(k+1)^{(k+2)t} O \left( n^{k-1} \right) \\= & {} (k-1)! (2n)^k + o(n^k). \end{aligned}$$

Thus if we define $G' = G_C \backslash \left( \bigcup _{T \subseteq Y, |T| \ge t^*}{S_T} \right)$ then $|G'| \ge (\alpha _1 / \beta )(k-1)!(2n)^k + (\epsilon - o(1))n^k$. Hence we can iterate the above procedure $\ell = \alpha _1 / \beta + 1$ times to obtain disjoint $\alpha _1$-cliques $Y_1, \ldots , Y_{\ell }$ and a disjoint graph $G'$ of size at least $(\epsilon - o(1))n^2$. By having $\epsilon \rightarrow 0$ slowly enough, we can apply Lemma 5.1 one more time to $G'$ to obtain a monochromatic $\alpha _1$-pair, which gives an additional $\alpha _1$-clique $Y_{\ell +1} \subseteq G'$ of size t. Note that by construction, the number of $\beta$-edges between $Y_i$ and $Y_j$ is at least $t(t - t^*) = t^2 ( 1 - o(1) )$ for distinct i and j. But then we can apply Lemma 3.5 to obtain $\ell + 1 \le \alpha _1 / \beta + 1 + o(1)$, a contradiction for n large enough. $\square$

6 Concluding remarks

In this paper, we showed that the maximum cardinality of an equiangular set of lines with common angle $\arccos \alpha$ is at most $2n-2$ for fixed $\alpha \in (0,1)$ and large $n$. Moreover, we proved that this bound is only attained for $\alpha = \frac{1}{3}$ and that we have an upper bound of $1.93n$ otherwise. In view of the result of Neumann [19, p. 498], it is not too surprising that $\limsup _{n \rightarrow \infty }{N_{\alpha }(n) / n}$ should be biggest when $1/\alpha$ is an odd integer. What is surprising, however, is that a maximum occurs at all and moreover that it happens when $\alpha$ is large. Indeed, the constructions of $\Omega (n^2)$ equiangular lines have $\alpha \rightarrow 0$, and so one might a priori expect that $\limsup _{n \rightarrow \infty }{N_{\alpha }(n) / n}$ should increase as $\alpha$ decreases.

If $\alpha = 1/(2r-1)$ for some positive integer r, an analogous construction as for $\alpha = \frac{1}{3}$ yields an equiangular set of $r\lfloor (n-1)/(r-1)\rfloor$ lines with angle $\arccos (1/(2r-1))$. Indeed, consider a matrix with $t = \lfloor (n-1)/(r-1)\rfloor$ blocks on the diagonal, each of size r, with 1 on the diagonal and $-\alpha$ off the diagonal; all other entries are $\alpha$. One can show that this is the Gram matrix for a set of rt unit vectors in $\mathbb {R}^n$. For n large enough and $r=2$ [20] and $r=3$ [23], it is known that this construction is optimal. This motivates the following conjecture, which was also raised by Bukh [5].

Conjecture 6.1

Let $r\ge 2$ be a positive integer. Then, for sufficiently large $n$,

$$\begin{aligned} N_{\frac{1}{2r-1}}(n) = \frac{r (n- 1)}{r-1} + O(1). \end{aligned}$$

If $\alpha$ is not of the above form, the situation is less clear but it is conceivable that $N_{\alpha }(n) = (1+o(1))n$.

We believe that the tools developed here should be useful to determine the asymptotics of $N_{\alpha }(n)$ for every fixed $\alpha$. If $\alpha$ is allowed to depend on n, then our methods work provided that $\alpha > \Theta (\log ^{-1}{n})$. The only place where this assumption is really necessary is our use of Ramsey’s theorem in order to obtain a large positive clique. However, it is conceivable that a large positive clique exists even when $\alpha < \Theta (\log ^{-1}{n})$, in which case our methods would continue to be effective.

We have also proved an upper bound of $O(n^k)$ for a set of lines attaining k prescribed angles. If the angles can tend to 0 together with $n$, however, this bound no longer applies and the general bound of $O(n^{2k})$ by Delsarte et al. [8] remains best possible. There are by now plentiful examples showing that for $k=1$ their bound gives the correct order of magnitude, but no such constructions are known for other values of k. So it would be interesting to determine whether the bound of Delsarte, Goethals and Seidel is tight for $k \ge 2$.