% \documentstyle[a4,12pt]{article}
\documentclass[a4paper]{article}
\usepackage{a4}
\usepackage{latexsym}
\title{Locally Paley graphs}
\author{A.E. Brouwer}
\date{Sept. 1, 1999}
\begin{document}
\maketitle
\newtheorem{Theorem} {Theorem} [section]
\newtheorem{Proposition} [Theorem] {Proposition}
\newtheorem{Lemma} [Theorem] {Lemma}
\newtheorem{Corollary} [Theorem] {Corollary}
\newcommand{\Proof}{ \noindent{\bf Proof}\quad }
\newcommand{\qed  }{\hfill$\Box$\medskip}
\newcommand{\Ff}{{\bf F}}
\newcommand{\Rr}{{\bf R}}
% \newcommand{\exp}{{\rm exp}}
% \newcommand{\ln}{{\rm ln}}
\newcommand{\infinity}{{\infty}}
\newcommand{\adj}{\,\sim\,}
\newcommand{\nadj}{\,\not\sim\,}
\newcommand{\Aut}{\rm Aut\,}

\newcommand{\Paleyq}{\Pi^{(q)}}

\centerline{To Jaap Seidel on the occasion of his $80^{th}$ birthday}

\abstract{We conjecture that all locally Paley graphs are known.
For locally Paley($p$) with $p < 100000$ this is true.}

\section{Results}
Let $q = p^e = 4t+1$ be a prime power.
Let $\Pi = \Paleyq$ be the Paley graph of order $q$
(with as vertices the elements of $\Ff_q$, where two points
are adjacent when their difference is a nonzero square),
and let $Q = \Pi(0)$ be its first subconstituent
(the subgraph induced on the set of nonzero squares).
We want to find all locally $\Pi$ graphs.
In this note we show that

(i) If $\Aut Q$ is as expected, and $q > 41$, then we know all
locally $\Pi$ graphs (and for $q \ne 9$ there is a unique
connected one, on $2q+2$ vertices).

(ii) If $Q$ has primitive eigenvalues of multiplicity $2e$, and $p \ne 3$,
then $\Aut Q$ is as expected (namely, generated by the maps
$x \mapsto x^{-1}$ and $x \mapsto ax$ (for nonzero squares $a$)
and $x \mapsto x^\sigma$ (for field automorphisms $\sigma$)).

(iii) For all primes $q$ less than 100000, and all prime powers
$q \ne 9$ less than 200, $Q$ has primitive eigenvalues of multiplicity $2e$.

Thus, the smallest unsettled case is $q = 81$.


\section{Introduction}

Let $\Gamma$ be a graph (undirected, without loops or multiple edges),
and $P$ a graph property. The graph $\Gamma$ is said to be
{\em locally $P$} when for each vertex $x$ of $\Gamma$ the
local graph $\Gamma(x)$ induced by $\Gamma$ on the set of neighbours
of $x$ has property $P$. In particular, the graph $\Gamma$ is said to
be {\em locally $\Delta$}, for some graph $\Delta$, when for each $x$
the graph $\Gamma(x)$ is isomorphic to $\Delta$.
Our aim is to study locally Paley graphs. For undefined notions
and notation, see \cite{BCN}.

Clearly, since the disjoint union of locally $P$ graphs is again
locally $P$, we can restrict ourselves to the study of connected
locally Paley graphs. And since the Paley graph of order $q$ is regular
of valency $(q-1)/2$, the Paley graphs at adjacent vertices have
the same order, so that a locally Paley graph is locally $\Paleyq$
for some fixed $q$.

The locally Paley graphs for small $q$ were known already:
For $q = 5$ the Paley graph is the pentagon, and the unique
locally pentagon graph is the icosahedron.
For $q = 9$ the Paley graph is the $3\times3$ grid, and there are
precisely two locally $3\times3$ grid graphs, namely the Johnson graph
${6 \choose 3}$ on 20 vertices, and the complement of the $4\times4$
grid on 16 vertices (\cite{BCN}, p.~258).
Buset \cite{Bu} showed that there is a unique locally $\Paleyq$ graph
for $q = 13,17,25,29,37$ and $41$ as part of her thesis.

There is always at least one locally $\Paleyq$ graph
namely the Taylor graph  $\Gamma$ on $2q+2$ vertices
constructed by taking vertex set
$\{\infinity^+\} \cup F^+ \cup F^- \cup \{\infinity^-\}$, where
$F^+$ and $F^-$ are two copies of $\Ff_q$ and
$\infinity^+, \infinity^-$ are two symbols, making
$\infinity^\epsilon$ adjacent to all vertices of $F^\epsilon$
($\epsilon = +,-$), putting copies of $\Paleyq$ on $F^+$ and $F^-$,
and letting $x^+ \adj y^-$ whenever $x \nadj y$.
The resulting graph is distance-transitive, with
intersection array $\{q,(q-1)/2,1;1,(q-1)/2,q\}$
(an antipodal 2-cover of the complete graph $K_{q+1}$)
and with full automorphism group $2 \times P\Sigma L(2,q)$,
cf. \cite{BCN}, p.~15 and p.~228.

No doubt there are no other locally $\Paleyq$ graphs than those just
described.

\section{Paley graphs}
The graph $\Pi = \Paleyq$ is strongly regular with parameters
$(v,k,\lambda,\mu) = (4t+1,2t,t-1,t)$ and spectrum
$2t$ (with multiplicity 1), $(-1\pm\sqrt{q})/2$ (with multiplicity $2t$).
It has full group of automorphisms of order $eq(q-1)/2$ if $q = p^e$
consisting of the semilinear maps $x \mapsto ax^\sigma + b$ for
nonzero squares $a$, field automorphisms $\sigma$ and arbitrary field
elements $b$.

Let $Q = \Pi(0)$ be the first subconstituent of $\Pi$.
Then $Q$ has $(q-1)/2$ vertices and is regular of valency
$\lambda = (q-5)/4$.
Since this is larger than $(-1+\sqrt{q})/2$ for $q > 9$
it follows by interlacing that $Q$ is connected for $q > 9$,
so that its eigenvalue $(q-5)/4$ has multiplicity 1 for these $q$.
(If $q = 5$ then $Q$ consists of two isolated points
and has spectrum $0^2$. If $q = 9$ then $Q$ consists
of two isolated edges and has spectrum $1^2 (-1)^2$.)

The graph $Q$ inherits the automorphisms $x \mapsto ax^\sigma$
from $\Aut \Pi$, but has an additional automorphism $x \mapsto x^{-1}$.
We expect these to generate all of $\Aut Q$, so that
$\Aut Q$ has order $e(q-1)$ for $q > 9$.
For $q = 5$ and $q = 9$ the group is only half as large
because in the first case $x \mapsto x^{-1}$ is the identity,
while in the second case $x \mapsto x^{-1}$ is the field automorphism
$x \mapsto x^3$.
Our main result will be that if indeed $\Aut Q$ has order $e(q-1)$,
then there is a unique locally $\Pi$ graph.

Let $N = \Pi_2 (0)$ be the set of vertices of $\Pi$ at distance 2 from 0
(i.e., the set of nonsquares).

We shall need several consequences of the random-like structure of Paley graphs.
First of all, points in $N$ are uniquely determined by the intersection
of their neighbourhood with $Q$.

\begin{Lemma}
\label{distinct}
If $x,y$ are distinct points in $N$, then
$x^\perp \cap Q \ne y^\perp \cap Q$.
\end{Lemma}
\Proof
Since $\Pi$ has $\lambda = t-1$ and $\mu = t$ we see that
if $x^\perp \cap Q = y^\perp \cap Q$ then this set has size $t$,
and $x,y$ are nonadjacent. We have seen $t$ points adjacent to
all three of $0,x,y$, no points are adjacent to precisely two of $0,x,y$,
and $3t$ points are adjacent to precisely one of $0,x,y$, a contradiction
since $4t+3 > q$. \qed

Next, any four points have a common neighbour, if $q$ is not too small.
(If we prescribe adjacency or nonadjacency of vertices $x$ with each
of four given points, then we expect that about $q/16$ vertices satisfy
the requirement. And this is the truth, with an error term $O(\sqrt q)$.)

\begin{Lemma}
\label{common4}
Every set of four distinct vertices $a_1,a_2,a_3,a_4$ of $\Paleyq$ has
a common neighbour if and only if $q > 81$.
More generally, if $q > 81$ then given four vertices $a_i$ and numbers
$\epsilon_i = \pm1$ there exists a vertex $x$ such that $x \adj a_i$
if and only if $\epsilon_i = 1$ ($i = 1,2,3,4$).
\end{Lemma}
\Proof
Let $\chi$ be the quadratic residue character, and let $c$ be the number
of common neighbours of $a_1,a_2,a_3,a_4$ in $\Pi$. Then
$\sum_x \prod_i (1 + \epsilon_i\chi(x-a_i)) = 16c+8d$, where $d$ is the number of $i$
for which $a_i$ has the appropriate adjacencies to the other three $a_j$.
Now character sums are small, so this roughly says that $16c$ is about $q$,
as desired. More precisely: $\sum_x 1 = q$, and $\sum_x \chi(x-a) = 0$ for all $a$
and $\sum_x \chi((x-a)(x-b)) = -1$ for any two distinct $a,b$, and
$| \sum_x \chi((x-a)(x-b)(x-c)) | \le 2 \sqrt q$ for any three distinct $a,b,c$,
and $| 1 + \sum_x \chi((x-a)(x-b)(x-c)(x-d)) | \le 2 \sqrt q$ for any four
distinct $a,b,c,d$, see e.g. Schmidt \cite{S} p. 1 and p. 43.
Thus, $|(16c + 8d) - q| \le 10 \sqrt q + 7$, and if $c = 0$ then
$q \le 10 \sqrt q + 39$, and $q \le 169$.
We can check the small cases by explicit inspection. \qed

In fact we would like to have common neighbours for somewhat smaller $q$ also,
so have to specify the mutual position of the four points.
For $q = 81$ the only 4-sets without common neighbour are subsets
of $n \Ff_9$ for a nonsquare $n$, and hence are cocliques.
For $q = 73$ the only 4-sets without common neighbour are subsets
that induce $K_4$ minus one edge (with 5 edges).
For $q = 61$ the 4-sets without common neighbour carry 4 or 6 edges.
For $q = 53$ the 4-sets without common neighbour carry 3 or 5 edges.
For $q = 49$ the 4-sets without common neighbour carry 0 or 4 edges.
For $q = 41$ the 4-sets without common neighbour carry 0, 1, 3, 4 or 5 edges.

Below we shall also be interested in the pattern $-+++$ for a 4-path or
4-cycle. Inspection shows that such a pattern is always present for $q > 41$, $q \ne 53$,
while for $q = 53$ it is present for 4-cycles, but not for all 4-paths.

And we shall also need the pattern $-+++$ for a 4-set inducing one or two
disjoint edges. Inspection shows that such a pattern is always present for $q > 25$.

\begin{Lemma}
\label{common3}
Every set of three distinct vertices $a_1,a_2,a_3$ of $\Paleyq$ has
a common neighbour if and only if $q > 25$.
\end{Lemma}

This follows from the previous lemma and explicit inspection
of the small cases. For $q = 17$ and $q = 25$ every triple of vertices
without a common neighbour induces a triangle. For $q = 13$ every triple
of vertices without common neighbour carries at least two edges.



\section{Locally `half case' graphs}
Let $\Gamma$ be a locally $\Pi$ graph, and assume $q > 9$.
We shall first prove some things using only that $\Pi$ is a
strongly regular graph with parameters
$(v,k,\lambda,\mu) = (4t+1,2t,t-1,t)$ for some $t > 0$.

\begin{Lemma}
\label{L1}
Let $x,y$ be vertices at distance $2$ in $\Gamma$.
Then the graph on their common neighbours $\Gamma(x) \cap \Gamma(y)$
is regular of valency $t$ and hence has at least $t+1$ vertices.
\end{Lemma}

\begin{Lemma}
\label{L2}
Let $x,y$ be vertices at distance $2$ in $\Gamma$.
Then $y$ has at most one neighbour at distance $3$ from $x$.
\end{Lemma}
\Proof Suppose $y \adj u,v$ with $d(u,x) = d(v,x) = 3$.
In $\Gamma(y)$ the vertices $u,v$ have at least $t+1$ common
nonneighbours (namely the common neighbours of $x$ and $y$),
but in $\Pi$ two vertices have either $t-1$ or $t$ common
nonneighbours. \qed

\begin{Lemma}
\label{L3}
${\rm diam \,} \Gamma \le 3$.
\end{Lemma}
\Proof If $v \adj w \adj x \adj y \adj z$ is a geodetic, then
$x$ has at least $t+1$ common neighbours with $z$ and these
have all distance 3 to $v$. Contradiction. \qed

\begin{Lemma}
\label{L4}
$\Gamma_3(x)$ does not contain an edge.
\end{Lemma}
\Proof We may assume $t > 2$.
Suppose $u \adj v$, where $d(u,x) = d(v,x) = 3$.
Because of Lemma \ref{L2} all common neighbours of $u$ and $v$
lie in $\Gamma_3(x)$. But $\Pi$ is locally connected (for $t > 2$),
so $u$ has no neighbour at distance 2 to $x$, contradiction. \qed

\begin{Lemma}
\label{L5}
$| \Gamma_3(x) | \le 1$.
\end{Lemma}
\Proof Suppose $d(u,x) = d(v,x) = 3$.
Pick $y \adj x$. By Lemma \ref{L4} we have $d(u,y) = d(v,y) = 2$.
Now $\Gamma(y)$ contains precisely $2t$ vertices nonadjacent
to $x$, of which at least $t+1$ are adjacent to $u$, and at least
$t+1$ are adjacent to $v$. Thus, there is a common neighbour $w$
of $y,u,v$, contradicting Lemma \ref{L2}. \qed

These lemmata show what to expect in general: a graph of diameter 2 or 3
where each point has distance 3 to at most one other point.
Note that in the single exceptional example (for $q = 9$) the graph $\Gamma$
has diameter 2.
From now on we resume our full hypothesis, namely that $\Pi$ not only has
the parameters of a Paley graph, but actually is one.

\section{Locally Paley graphs}
Fix adjacent vertices $x,y$ of $\Gamma$.
Then $\Gamma(x)$ and $\Gamma(y)$ are isomorphic, and each has a transtive group,
so we can find an isomorphism $\phi_{xy} : \Gamma(x) \rightarrow \Gamma(y)$
mapping $y$ to $x$. Let $Q_{xy} = \Gamma(x) \cap \Gamma(y)$.
Then the restriction of $\phi_{xy}$ to $Q_{xy}$ is an automorphism.
Since we are assuming we know the automorphisms of the first subconstituent
of the Paley graph, we know this automorphism, and hence know how to join
the neighbourhoods of $x$ and $y$. The details will take a while.

Let us call our two adjacent vertices $\infinity$ and $0$, and put
$Q := \Gamma(\infinity) \cap \Gamma(0)$, and $\phi := \phi_{\infinity0}$.
By assumption the restriction of $\phi$ to $Q$ is of the form
$z \mapsto az^{\pm\sigma}$. But we can always compose with an automorphism
$z \mapsto az^\sigma$ of $\Gamma(\infinity)$, and we see
that there are only two different cases:
(i) the restriction of $\phi$ to $Q$ is of the form $z \mapsto z$, and
(ii) the restriction of $\phi$ to $Q$ is of the form $z \mapsto z^{-1}$.
Out aim is to prove that only the second case can occur.

Put $N = \Gamma(\infinity) \cap \Gamma_2(0)$ and
$N'= \Gamma_2(\infinity) \cap \Gamma(0)$.
If $\phi$ fixes $Q$ pointwise, the map $\phi_0 : N \rightarrow N'$
that it induces has the property that $n$ and $\phi_0(n)$ have
the same neighbours in $Q$ for all $n \in N$.
If on the other hand $\phi$ inverts the elements of $Q$, then
the sets ${\frac{1}{n}}^\perp \cap Q$ and $\phi_0(n)^\perp \cap Q$ are
complementary subsets of $Q$: we have
$\frac{1}{n} - \frac{1}{x} = \frac{x-n}{nx}$ so the nonneighbours
of $\frac{1}{n}$ in $Q$ are the inverses of the neighbours
of $n$ in $Q$, hence are the neighbours of $\phi_0(n)$ in $Q$.

Thus, in both cases we know the adjacencies between $N'$ and $Q$,
and we have shown:

{\em
Let $d(\infinity,a) = 2$ and let $\infinity \adj x \adj a$.
Then there is a point $a_x \in \Gamma(\infinity) \setminus \Gamma(x)$
such that either $\{\infinity,a,x\}^\perp = \{\infinity,a_x,x\}^\perp$ or
$\{\infinity,a,x\}^\perp = \{\infinity,x\}^\perp \setminus \{\infinity,a_x,x\}^\perp$.
}

We cannot have both cases simultaneously, otherwise the three vertices
$x,a,a'$ would have no common neighbour in $\Gamma(\infinity)$,
and by Lemma \ref{common3} and following discussion this is impossible for $q > 9$.

Note that if $x,y \in \{\infinity,a\}^\perp$ and $y = a_x$ then also $x = a_y$
and we have the same case for both $x$ and $y$.

Suppose the first case occurs: $\{\infinity,a,x\}^\perp = \{\infinity,a_x,x\}^\perp$,
and choose $p \in \{\infinity,a,x\}^\perp$. Then in $\Gamma(p)$ we see
that $\{\infinity,a,x\}^\perp = \{\infinity,a_x,x\}^\perp$, so that no
vertex is adjacent to $\infinity,a,x$ but not to $a_x$. For $q > 81$
that is impossible according to Lemma \ref{common4}, and the following
discussion shows that this pattern $-+++$ also occurs for $q = 49, 61, 73, 81$,
so that either $q \le 41$ or $q = 53$.

So, the first case does not occur unless perhaps for small $q$.
Let us assume that we are always in the second case:

{\em Given a 3-path $\infinity \adj x \adj a$ there is a unique vertex
$a_x \in \Gamma(\infinity) \setminus \Gamma(x)$ such that
$\{\infinity,a,x\}^\perp = \{\infinity,x\}^\perp \setminus \{\infinity,a_x,x\}^\perp$.
}

Now $a_x$ is independent of $x$. Indeed, suppose $x,y \in \{\infinity,a\}^\perp$
and $a_x \ne y,a_y$. We have
$\{\infinity,x,y\}^\perp \setminus \{\infinity,a_x,x,y\}^\perp =
\{\infinity,a,x,y\}^\perp = \{\infinity,x,y\}^\perp \setminus \{\infinity,a_y,x,y\}^\perp$
so that in $\Gamma(\infinity)$ the common neighbours of $x,y,a_x$ are the same
as the common neighbours of $x,y,a_y$, and no vertex has adjacency pattern $+++-$
to $x,y,a_x,a_y$. According to Lemma \ref{common4} this is impossible for $q > 81$.
Since $\Gamma(\infinity) \cap \Gamma(a)$ is connected (because it has valency $t$
which is larger than $(-1+\sqrt q)/2$ for $q > 5$) we may assume that $x \adj y$.
Since $x,y \nadj a_x,a_y$ the set $\{x,y,a_x,a_y\}$ induces
1 or 2 disjoint edges, and by the discussion following Lemma \ref{common4}
this pattern occurs for all $q > 25$.
This proves that $a_x = a_y$ unless $a_x = y$.
But if $a_x = y$ and $a_y = x$, then consider a third point $z \in \{\infinity,a\}^\perp$.
We cannot have $a_z = x$ otherwise $y = a_x = z$. So $a_z = a_x$, and similarly
$a_z = a_y$, contradiction.

We have shown (for $q > 25$):
{\em Given $a \in \Gamma_2 (\infinity)$ there is a unique point
$\bar{a} \in \Gamma(\infinity)$ such that $\Gamma(\infinity) \cap \Gamma(a) =
\Gamma(\infinity) \setminus \Gamma(\bar{a})$.
}

Now vary the point $a$. If $a,b \in \Gamma_2 (\infinity)$ are distinct,
then also $\bar{a} \ne \bar{b}$, otherwise we could pick
$p \in \{\infinity,a,b\}^\perp$ and see locally at $p$ that
$\{\infinity,a\}^\perp = \{\infinity,b\}^\perp$ contrary to Lemma \ref{distinct}.
So, by Lemma \ref{L5} $\Gamma$ has at most $1+q+q+1$ vertices.
If $\Gamma$ has precisely $1+q+q+1$ vertices, then each point $p$ has an antipode,
and each point at distace two from $p$ is adjacent to its antipode, and we find
that $\bar{a}$ is the antipode of $a$, and it quickly follows that $\Gamma$ is
the Taylor graph we wanted to find.

So, now assume that $\Gamma$ has at most $2q+1$ vertices, so that
$\Gamma_3(x) = \emptyset$ for all $x$. Then $\Gamma$ is strongly regular
with parameters $(v,k,\lambda,\mu) = (v,4t+1,2t,2t)$ but these parameters
are not feasible. Contradiction.

We showed

\begin{Theorem}
Let $q = 4t+1$ be a prime power with $q > 41$ and $q \ne 53$.
If the automorphism group of the first subconstituent of $\Paleyq$
is as expected, then there is a unique locally $\Paleyq$ graph,
a distance-regular antipodal $2$-cover of the complete graph $K_{q+1}$.
\end{Theorem}

Since Buset handled $q \le 41$ it would be a pity to leave $q = 53$.
So, suppose $q = 53$. Take again $a \in \Gamma_2(\infinity)$ and suppose that
$\{\infinity,a,x\}^\perp = \{\infinity,a_x,x\}^\perp$ for some
$x \in \{\infinity,a\}^\perp$. For each $p \in \{\infinity,a,x\}^\perp$
we see in $\Gamma(p)$ a 3-path or a quadrangle on $\{a,x,\infinity,a_x\}$
without vertex with adjacency pattern $-+++$. But for each quadrangle in $\Pi$
there is such a vertex. And up to translations $\Pi$ contains a unique 3-path
for which there is no such vertex, and this 4-set has 4 common neighbours.
This shows that the graph on the common neighbours of $x$ and $a_x$ in
$\Gamma(\infinity)$ is regular of valency 4. However, $\mu$-graphs in $\Pi$
are not regular, contradiction. This settles the case $q = 53$.


\section{Automorphisms of $Q$ and its spectrum}
Suppose $u$ is an eigenvector of a graph $Q$, and $\psi$ is an
automorphism of $Q$. Then the image of $u$ under $\psi$
(that is, the vector $v$ with $v_{\psi(x)} = u_x$) is also an eigenvector
of $Q$, with the same eigenvalue.
This observation gives strong information in case certain eigenspaces
have low dimension.

Our particular graph $Q$ is a circulant: if $\alpha$ is a primitive
element of $\Ff_q$ and $\beta = \alpha^2$, then the points of $Q$
are $1, \beta, \beta^2, ..., \beta^{m-1}$ where $m = (q-1)/2$.
This means that we know the eigenvectors and eigenvalues of $Q$:
these are $u(\omega) = (1,\omega,...,\omega^{m-1})^\top$ with
corresponding eigenvalue $\theta(\omega) = \sum \sigma_i \omega^i$
where $\omega$ runs through the $m$-th roots of unity, and
$\sigma_i = 1$ if $\beta^i - 1$ is a nonzero square in $\Ff_q$, and
$\sigma_i = 0$ otherwise.

Suppose $\omega \ne \pm1$, and suppose the $\theta$-eigenspace $S$ of $Q$
has dimension 2 for $\theta = \theta(\omega)$. Then the two vectors $u(\omega)$
and $u(\omega^{-1})$ span $S$. Now if $\psi$ is an automorphism of $Q$,
the image of $u(\omega)$ under $\psi$ lies in $S$ again, so is of the form
$\xi u(\omega) + \eta u(\omega^{-1})$. But all its entries are roots of unity,
while this latter vector has $i$-th entry with norm
$(\xi \omega^i + \eta \omega^{-i})(\bar{\xi} \omega^{-i} + \bar{\eta} \omega^i) =
\xi\bar{\eta} \omega^{2i} + (\xi\bar{\xi} + \eta\bar{\eta}) + \bar{\xi}\eta \omega^{-2i}$,
and this can only be independent of $i$ if either $\xi = 0$ or $\eta = 0$ or
$\omega^4 = 1$.
But if $\xi = 0$ or $\eta = 0$ then $\psi$ acts on $u(\omega)$
either as a cyclic shift (multiplication by a square) or as a cyclic shift
composed with $z \mapsto z^{-1}$.

We have shown:

{\em
Let $G_0$ be the permutation group on $Q$ generated by the maps
$z \mapsto a z ^{\pm 1}$ for nonzero squares $a$ in $\Ff_q$.
Suppose $\omega^4 \ne 1$. If the $\theta(\omega)$-eigenspace
of $Q$ has dimension $2$, then each $\psi \in \Aut Q$ can be written as
$\psi = \psi_0 \eta$ where $\eta \in G_0$ and $\psi_0$ fixes $u(\omega)$.
In particular, if $\omega$ is a primitive $m$-th root of unity, then
$\Aut Q = G_0$.
}

Now let us repeat this reasoning for the case where $q = p^e$.
Suppose the $2e$ numbers $\omega^{\pm p^j}$ ($j=0,...,e-1$) are distinct,
and suppose the $\theta$-eigenspace $S$ of $Q$ has dimension $2e$
for $\theta = \theta(\omega)$. Then the $2e$ vectors $u(\omega^{\pm p^j})$
span $S$. Now if $\psi$ is an automorphism of $Q$, we find that it
sends $u(\omega)$ to $\sum \xi_j u(\omega^{p^j}) + \eta_j u(\omega^{-p^j})$.
So, all entries of this vector are roots of unity and have norm 1, and we
find a polynomial of degree $4 p^{e-1}$ satsfied by $\omega^i$ for all $i$.
If $\omega$ has order larger than $4 p^{e-1}$ then the polynomial is identically 0
and only a single one among the $\xi_j$ and $\eta_j$ is nonzero, so that
$\psi$ is a known automorphism.

We have shown:

{\em
Let $G$ be the known part of $\Aut Q$, i.e., the group generated by the maps
$z \mapsto a z ^{\pm p^j}$ for nonzero squares $a$ in $\Ff_q$ and $0 \le j \le e-1$.
Suppose $\omega$ is a primitive $m$-th root of unity.
If the $\theta(\omega)$-eigenspace of $Q$ has dimension $2e$, then
$\Aut Q = G$.}

Hmm. Have we shown this? If $m \le 4 p^{e-1}$ we cannot take $\omega$
of large order, and this happens for $p \le 7$. Looking somewhat more
closely we see that we have a polynomial of degree $4 p^{e-1}$ in $\omega$
of which all terms have degree $2 p^{e-1} \pm p^i \pm p^j$ where
$0 \le i,j \le e-1$. If this is to be a polynomial multiple of $\omega^m - 1$,
then the highest exponent must be congruent mod $m$ to some other exponent,
that is, $2 p^{e-1} \mp p^i \mp p^j$ is divisible by $m = (p^e - 1)/2$.
For $p = 7$ this cannot happen. For $p = 5$ this happens only if $e = 2$.
But for $q = 25$, $m = 12$ we find that $Q$ has an easily described structure,
and the claim is true.
Thus, the above claim has been proved for $p > 3$.

\section{The spectrum of $Q$}
For all small $q$ it turns out that for a primitive $m$-th root of unity
$\omega$ the $\theta(\omega)$-eigenspace of $Q$ has dimension $2e$.
Moreover, there are always eigenspaces of dimension 2 if $q < 125$.

Let us list some explicit spectra.

$\begin{array}{ccl}
q=5 & m = 2 & 0^2 \\
q=9 & m = 4 & 1^2 (-1)^2 \\
q=13 & m = 6 & 2^1 1^2 (-1)^2 (-2)^1 \\
q=17 & m = 8 & 3^1 1^2 (-1+\sqrt 2)^2 (-1)^1 (-1-\sqrt 2)^2 \\
q=25 & m = 12 & 5^1 2^2 1^1 0^4 (-2)^2 (-3)^2 \\
\end{array}$

Since the spectra take too much room, let us only give multiplicities
and their frequencies:

\smallskip
$\begin{array}{cl|cl|cl|cl} \hline
q &  & q &  & q &  & q &  \\ \hline
5 & 2^1           & 41 & 1^2 2^9
& 97 & 1^2 2^{21} 4^1      & 149 & 1^2 2^{36} \\
9 & 2^2           & 49 & 1^1 2^3 4^3 5^1
& 101 & 1^2 2^{22} 4^1     & 157 & 1^1 2^{37} 3^1 \\
13 & 1^2 2^2      & 53 & 1^2 2^{12}
& 109 & 1^2 2^{26}         & 169 & 1^1 2^4 3^1 4^{15} 6^2 \\
17 & 1^2 2^3      & 61 & 1^1 2^{13} 3^1
& 113 & 1^2 2^{27}         & 173 & 1^2 2^{42} \\
25 & 1^2 2^3 4^1  & 73 & 1^2 2^{15} 4^1
& 121 & 1^1 2^3 4^{11} 9^1 & 181 & 1^2 2^{38} 4^3 \\
29 & 1^2 2^6      & 81 & 1^1 2^1 4^2 5^1 8^3
& 125 & 1^2 6^{10}         & 193 & 1^1 2^{44} 3^1 4^1 \\
37 & 1^1 2^7 3^1  & 89 & 1^2 2^{21}
& 137 & 1^2 2^33           & 197 & 1^2 2^{48} \\ \hline
\end{array}$
\smallskip

Looking at primes $q = p$ only, and disregarding the eigenvalues
corresponding to $\omega = \pm1$ we see that all multiplicities
are 2 for $p < 73$, but for $p = 73$ for the first time a multiplicity 4 occurs.
Clearly, most multiplicities are 2 when $q = p$, and indeed for $q = p < 100000$
there is always an eigenvalue of multiplicity 2.

Thus, for all primes $p < 100000$ we know the locally Paley graphs of degree $p$.

\begin{thebibliography}{BCN}

\bibitem[BCN]{BCN} A.E. Brouwer, A.M. Cohen \& A. Neumaier,
{\it Distance-regular graphs\/}, Springer, Heidelberg, 1989.

\bibitem[Bu]{Bu} D. Buset, letter dd 1996-08-11.

\bibitem[S]{S} W.M. Schmidt,
{\it Equations over finite fields},
Lecture Notes in Math. 536, Springer, Berlin, 1976.

\end{thebibliography}

\noindent
Spetses, 1996 -- Lhasa, 1999 -- Amsterdam
\end{document}
