\documentclass[12pt]{article}
\usepackage{amsmath}
\setlength{\textheight}{8.5in}
\setlength{\textwidth}{6.2in}
\setlength{\topmargin}{0.0in}
\oddsidemargin 0pt
\evensidemargin 0pt
\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics
\textbf{7}(2000),\#R55\hfill}
\thispagestyle{empty}
\begin{document}
\title
{Large equiangular sets of lines in Euclidean
space}
\author{D. de Caen \\ Department of Mathematics and Statistics \\ Queen's
University \\ Kingston, Ontario, Canada K7L 3N6\\
{\small\texttt{decaen@mast.queensu.ca}}}
\date{Submitted: May 27, 2000; Accepted: November 9, 2000}
\maketitle
\begin{center}
{\it In memory of Norman J. Pullman (1931-1999)}
\end{center}
\begin{abstract}
A construction is given of
$\frac{2}{9}(d+1)^2$ equiangular lines in
Euclidean $d$-space, when $d = 3 \cdot 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$ .
\end{abstract}
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 $\theta$ denote the
smallest eigenvalue of $S$, we see that $M:= I - \frac{1}{\theta}
S$ is positive semidefinite
of rank $d = n-m$ where $n$ is the number of vertices and $m$ is
the eigenvalue multiplicity of
$\theta$. Hence $M$ is representable as the Gram matrix of $n$
unit vectors $x_1, ..., x_n$ in
real
$d$-space, with $ = \pm \frac{1}{\theta}$ 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}{\theta})$.
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.
\bigskip
\noindent{\bf Theorem}. For each $d = 3 \cdot 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.
\bigskip
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 \rightarrow 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 $\chi(Q) = \pm1$, where $Q$ has exactly $2^{2t-1}+
\chi(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
non-singular for all $i \neq j$ then the set is called
non-singular. It is not hard to show that a
non-singular set has $r \leq 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 \neq B'$ and $\chi(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:
\begin{description}
\item $\theta_1 = 2^{3t-1} + 2^{2t} - 2^t - 1$; multiplicity one.
\item $\theta_2 = 2^{3t-1} - 2^t - 1$; multiplicity $2q-1$ where
$q:=2^{2t-1}$.
\item $\theta_3 = 2^{2t} - 2^t -1$; multiplicity $q-1$.
\item $\theta_4 = -2^t - 1$; multiplicity $(q-1)(2q-1)$.
\end{description}
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}$, $\theta = 2^t -1$ and $\tau = -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 $\theta =
\theta_4$ is the smallest
eigenvalue of $S(G_t)$ and it has very large multiplicity. Indeed
the rank of $M = I -
\frac{1}{\theta} 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\cdot 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 two-graph.
But so far (cf. [3], p.884)
constructions using regular two-graphs have yielded nothing better
asymptotically than a constant
times $d\sqrt{d}$.
\bigskip
\bigskip
\noindent{\bf Acknowledgement}\\
Financial support has been provided by a research grant from NSERC of Canada.
\begin{thebibliography}{2}
\bibitem[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.
\bibitem[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.
\bibitem[3]{} J. J. Seidel, ``Discrete Non-Euclidean Geometry",
pp.843-920 in Handbook of
Incidence Geometry (F. Buckenhout, ed.), Elsevier 1995.
\end{thebibliography}
\end{document}