Large equiangular sets of lines in Euclidean space

D. de Caen Department of Mathematics and Statistics Queen’s University Kingston, Ontario, Canada K7L 3N6

                            decaen@mast.queensu.ca

Submitted: May 27, 2000; Accepted: November 9, 2000

In memory of Norman J. Pullman (1931-1999)

Abstract

A construction is given of \frac{2}{9}(d + 1)^{2} equiangular lines in Euclidean d-space, when d = 3 · 2^{2t−1} − 1 with t any positive integer. This compares with the well known “absolute” upper bound of \frac{1}{2}d(d + 1) lines in any equiangular set; it is the first known constructive lower bound of order d^{2} .

For background and terminology we refer to Seidel [3]. The standard method for obtaining a system of equiangular lines in Euclidean space is as follows. Let G be a graph, with Seidel adjacency matrix S, i.e. S_{xy} = −1 if vertices x and y are adjacent, S_{xy} = 1 if x and y are distinct and non-adjacent, S_{xx} = 0 for all x. Letting θ denote the smallest eigenvalue of S, we see that M := I − \frac{1}{θ}S is positive semidefinite of rank d = n − m where n is the number of vertices and m is the eigenvalue multiplicity of θ. Hence M is representable as the Gram matrix of n unit vectors x_{1}, ..., x_{n} in real d-space, with < x_{i}, x_{j} >= ±\frac{1}{θ} whenever i and j are distinct. Thus the lines (1-dimensional subspaces) spanned by these x_{i}’s have constant pairwise angle arccos (\frac{1}{θ}).

It is not hard to see that the above process is reversible, so that finding a large equiangular set of lines in Euclidean space amounts to finding a graph whose Seidel adjacency matrix has smallest eigenvalue of large multiplicity.

Theorem. For each d = 3 · 2^{2t−1} − 1, with t any positive integer, there exists an equiangular set of \frac{2}{9}(d + 1)^{2} lines in Euclidean d-space.

In order to describe the graphs relevant to this construction, we need to recall some terms and facts from the theory of quadratic forms over GF (2); a convenient reference is [1], which contains everything we need here as well as some pointers to earlier literature.

Let V be a vector space over GF (2). If Q : V → GF (2) is a quadratic form, then its polarization B(x, y) := Q(x + y) + Q(x) + Q(y) is an alternating bilinear form. Note that B can be non-singular only if V has even dimension; so we will assume that dim(V) = 2t for some positive integer t. If Q polarizes to a non-singular B, then Q must be of one of two types χ(Q) = ±1, where Q has exactly 2^{2t−1} + χ(Q)2^{t−1} zeroes. Next, let {B_{1}, B_{2}, ..., B_{r}} be a set of alternating bilinear forms on V; if B_{i} + B_{j} is nonsingular for all i ≠ j then the set is called non-singular. It is not hard to show that a non-singular set has r ≤ 2^{2t−1}; when equality holds it is called a Kerdock set. Such maximal non-singular sets do exist for all t.

We may now describe the graphs occurring in our construction of equiangular lines. Let K be a Kerdock set of alternating forms on V, where dim(V) = 2t as above. The graph G_{t} will have as vertex-set all pairs (B, Q) where B belongs to K and Q polarizes to B. Two vertices (B, Q) and (B′, Q′) are declared adjacent precisely when B ≠ B′ and χ(Q + Q′) = −1. Note that G_{t} is one of the two non-trivial relations in what is called the Cameron-Seidel 3-class association scheme in [1]. The eigenvalues of the Seidel adjacency matrix S(G_{t}) are as follows:

θ_{1} = 2^{3t−1} + 2^{2t} − 2^{t} − 1; multiplicity one.

θ_{2} = 2^{3t−1} − 2^{t} − 1; multiplicity 2q − 1 where q := 2^{2t−1}.

θ_{3} = 2^{2t} − 2^{t} − 1; multiplicity q − 1.

θ_{4} = −2^{t} − 1; multiplicity (q − 1)(2q − 1).

The foregoing spectral information can be derived from the (dual) eigenmatrix Q on page 326 of [2], by setting n = 2^{2t}, r = 2^{2t−1}, a = 2^{t+1}, θ = 2^{t} −1 and τ = −2^{t} −1 in that paper; the adjacency eigenvalues of G_{t} are then given by the fourth column of Q and the corresponding multiplicities by the first row of the P -matrix. Also please note that the Seidel matrix S and ordinary adjacency matrix A are related by S = J − I − 2A.

We now have the following situation. The eigenvalue θ = θ_{4} is the smallest eigenvalue of S(G_{t}) and it has very large multiplicity. Indeed the rank of M = I − \frac{1}{θ}S is d = 3q − 1 and the graph has 2q^{2} = \frac{2}{9}(d+1)^{2} vertices. From the standard procedure sketched earlier, we thus obtain an equiangular set of \frac{2}{9}(d + 1)^{2} lines in Euclidean d-space, whenever d = 3q − 1 = 3 · 2^{2t−1} − 1 for some positive integer t. This completes the presentation and verification of our construction, or in other words, the proof of our theorem.

The graphs G_{t} have already been known for over twenty-five years. It is perhaps surprising that their relevance to equiangular lines was not noticed before. A likely reason is that, generally speaking, the best constructions seem to come from regular two-graphs where the Seidel adjacency matrix has just two distinct eigenvalues; for example the absolute upper bound of \frac{1}{2}d(d + 1) can only be achieved by a regular twograph. But so far (cf. [3], p.884) constructions using regular two-graphs have yielded nothing better asymptotically than a constant times d\sqrt{d}.

Acknowledgement Financial support has been provided by a research grant from NSERC of Canada.

References

[1] D. de Caen and E. R. van Dam, “Association schemes related to Kasami codes and Kerdock sets”, Designs, Codes and Cryptography 18 (1999), 89-102.

[2] D. de Caen, R. Mathon and G. E. Moorhouse, “A family of antipodal distance-regular graphs related to the classical Preparata codes”, J. of Algebraic Combinatorics 4 (1995), 317-327.

[3] J. J. Seidel, “Discrete Non-Euclidean Geometry”, pp.843-920 in Handbook of Incidence Geometry (F. Buckenhout, ed.), Elsevier 1995.