\documentclass{article}
\usepackage{amssymb}
\newcommand{\Ff}{{\mathbb F}}
\newcommand{\Zz}{{\mathbb Z}}
\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 QED\medskip}
\newcommand{\adj}{\,\sim\,}
\newcommand{\tr}{{\rm tr}}
\newcommand{\mod}{{\rm mod}\ }
\newcommand{\eps}{\varepsilon}
\begin{document}
\author{A. E. Brouwer, R. M. Wilson \& Qing Xiang}
\title{Cyclotomy and Strongly Regular Graphs}
\maketitle

\begin{abstract}
We consider strongly regular graphs defined on a finite
field by taking the union of some cyclotomic classes as
difference set. Several new examples are found.
\end{abstract}

In this note we consider graphs $\Gamma$ that have
as vertices the elements of a finite field $\Ff_q$,
where two vertices are adjacent when their difference
belongs to $D$, a fixed subset of $\Ff_q$.
Note that such a graph will be undirected when $D = -D$,
and without loops if $0 \notin D$.

The case where $D$ is a union of cosets of a subgroup
of the multiplicative group of a field $\Ff_q$ was considered
in Van Lint \& Schrijver \cite{vLS}; see also
Calderbank \& Kantor \cite{CalderbankKantor} (9.2).
De Lange \cite{deLange} gave a few more examples of
strongly regular graphs obtained by cyclotomy.
Here, we give an `explanation' of one of his examples,
by showing how it fits into the general theory.
(There are still two more examples to be explained.)
As a result, we obtain infinitely many other examples.
The idea is to use a union of cosets of several subgroups
of the multiplicative group of $\Ff_q$.

We start by reviewing the classical stuff.
Let $q = p^\kappa$, $p$ prime and $e | (q-1)$, say $q = e m + 1$.
Let $K \subseteq \Ff_q^*$ be the subgroup of the $e$-th powers
(so that $| K | = m$).
Let $\alpha$ be a primitive element of $\Ff_q$.
For $J \subseteq \{ 0,1, ..., e-1 \}$ put $u := | J |$ and
$D := D_J := \bigcup \{ \alpha^j K \mid j \in J \} =
\{ \alpha^{ie+j} | j \in J , 0 \le i < m \}$.
Define a (directed)
graph $\Gamma = \Gamma_J$ with vertex set $\Ff_q$ and edges
$(x,y)$ whenever $y - x \in D$.
Note that $\Gamma$ will be undirected iff either $-1$
is an $e$-th power (i.e., $q$ is even or $e | (q-1)/2$) or
$J + (q-1)/2 = J$ (arithmetic in $\Zz_e$).

Let $A = A_J$ be the adjacency matrix of $\Gamma$
defined by $A (x,y) = 1$ if $(x,y)$ is an edge
of $\Gamma$ and $= 0$ otherwise.
Let us compute the eigenvalues of $A$.
For each (additive) character $\chi$ of $\Ff_q$ we have
$$
(A \chi ) (x) = \sum_{ y \adj x } \chi (y) =
( \sum_{ d \in D } \chi (d) ) \chi (x).
$$
Thus, each character gives us an eigenvector, and since these
are all independent we know all eigenvalues.
Their explicit determination requires some theory of Gauss sums.
Let us write $A \chi = \theta ( \chi ) \chi$.
Clearly, $\theta (1) = m u$, the valency of $\Gamma$.
Now assume $\chi \ne 1$. Then $\chi = \chi_g$ for some integer $g$,
where
$$
\chi_g ( \alpha^j ) = {\rm exp} ( { 2 \pi i \over p }
\tr ( \alpha^{j+g} ))
$$
and $\tr : \Ff_q \to \Ff_p$ is the trace function.

If $\mu$ is any multiplicative character of order $e$
(say, $\mu ( \alpha^j ) = \zeta^j$, where
$\zeta = {\rm exp} ( { 2 \pi i \over e } )$) then
$$
\sum_{i=0}^{e-1} \mu^i (x) = \left \{
\begin{array}{cl}
e & \mbox{\rm if $\mu(x) = 1$} \\
0 & \mbox{\rm otherwise.}
\end{array} \right .
$$
Thus,
$$
\theta ( \chi_g ) = \sum_{ d \in D } \chi_g (d) =
\sum_{ j \in J } \sum_{ u \in K } \chi_{j+g} (u) =
{1 \over e} \sum_{ j \in J } \sum_{ x \in \Ff_q^* }
\chi_{j+g} (x) \sum_{i=0}^{e-1} \mu^i (x) =
$$
$$
= {1 \over e} \sum_{ j \in J } ( -1 +
\sum_{i=1}^{e-1} \sum_{ x \ne 0 } \chi_{j+g} (x) \mu^i (x)
) = {1 \over e} \sum_{ j \in J } ( -1 +
\sum_{i=1}^{e-1} \mu^{-i} ( \alpha^{j+g} ) G_i )
$$
where $G_i$ is the Gauss sum
$\sum_{ x \ne 0 } \chi_0 (x) \mu^i (x)$.

In general, determination of Gauss sums seems to be complicated,
but there are a few explicit results. For our purposes the most
interesting is the following:

\begin{Proposition} {\rm (Stickelberger and Davenport \& Hasse,
see McEliece \& Rumsey \cite{McER72}, McEliece \cite{McE75})}
Suppose $e > 2$ and $p$ is semiprimitive $\mod e$, i.e.,
there exists an $l$ such that $p^l \equiv -1$ $(\mod e)$.
Choose $l$ minimal and write $\kappa = 2 l t$.
Then
$$ G_i = (-1)^{t+1} \eps^{it} \sqrt q , $$
where
$$
\eps = \left \{
\begin{array}{cl}
-1 & \mbox{\rm if $e$ is even and $(p^l + 1)/e$ is odd} \\
+1 & \mbox{\rm otherwise.}
\end{array} \right .
$$
\end{Proposition}

Under the hypotheses of this proposition, we have
$$
\sum_{i=1}^{e-1} \mu^{-i} ( \alpha^{j+g} ) G_i =
\sum_{i=1}^{e-1} \zeta^{-i(j+g)} (-1)^{t+1} \eps^{it} \sqrt q =
\left \{
\begin{array}{cl}
% (-1)^{t+1} \sqrt q ( {{r^e - 1} \over {r - 1}} - 1 ) =
(-1)^t \sqrt q & \mbox{\rm if $r \ne 1$,} \\
(-1)^{t+1} \sqrt q (e - 1) & \mbox{\rm if $r = 1$,}
\end{array}
\right .
$$
where $\zeta = {\rm exp} ( 2 \pi i / e )$ and
$r = r_{g,j} = \zeta^{-j-g} \eps^t$
(so that $r^e = \eps^{et} = 1$), and hence
$$
\theta ( \chi_g ) = {u \over e} ( -1 + (-1)^t \sqrt q ) +
(-1)^{t+1} \sqrt q . \#\{ j \in J | r_{g,j} = 1 \}.
$$
If we abbreviate the cardinality in this formula with \#, then:
If $\eps^t = 1$ then $\# = 1$ if $g \in - J$ $(\mod e)$, and $= 0$
otherwise.
If $\eps^t = -1$ (then $e$ is even and $p$ is odd) then
$\# = 1$ if $g \in \frac{1}{2} e - J$ $(\mod e)$, and $= 0$ otherwise.
We proved:

\begin{Theorem}
Let $q = p^\kappa$, $p$ prime and $e | (q-1)$,
where $p$ is semiprimitive $\mod e$, i.e.,
there is an $l > 0$ such that $p^l \equiv -1$
$\mod e$.
Choose $l$ minimal with this property and write
$\kappa = 2 l t$.
Choose $u$, $1 \le u \le e-1$ and assume that $q$ is even or $u$ is even
or $e | (q-1)/2$.
Then the graphs $\Gamma_J$ (where $J$ is arbitrary for $q$ even
or $e | (q-1)/2$ and satisfies $J + (q-1)/2 = J$ {\rm mod} $e$ otherwise)
are strongly regular with eigenvalues
$$
\begin{array}{cl}
k = {q-1 \over e} u & \mbox{ with multiplicity 1}, \\
\theta_1 = {u \over e} (-1 + (-1)^t \sqrt q ) &
\mbox{ with multiplicity } q-1-k, \\
\theta_2 = {u \over e} (-1 + (-1)^t \sqrt q ) + (-1)^{t+1} \sqrt q &
\mbox{ with multiplicity } k .
\end{array}
$$
(Obviously, when $t$ is even we have $r = \theta_1$, $s = \theta_2$,
and otherwise $r = \theta_2$, $s = \theta_1$, where, as usual, $r$
denotes the nontrivial positive eigenvalue, and $s$ the negative one.)
\end{Theorem}

Clearly, when $e | e' | (q-1)$ then the set of $e$-th powers
is a union of cosets of the set of $e'$-th powers, so when
applying the above theorem we may assume that $e$ has been chosen
as large as possible, i.e., $e = p^l + 1$.
Then the restriction `$q$ is even or $u$ is even or $e | (q-1)/2$'
is empty, and $J$ can always be chosen arbitrarily.

The above construction can be generalized.
Pick several values $e_i$ $(i \in I)$ with $e_i | (q-1)$.
Let $K_i$ be the subgroup of $\Ff_q^*$ of the $e_i$-th powers.
Let $J_i$ be a subset of $\{0,1,...,e_i-1\}$.
Let $D_i := D_{J_i} := \bigcup \{ \alpha^j K_i \mid j \in J_i \}$.
Put $D := \bigcup D_i$. If the $D_i$ are mutually disjoint,
then $D$ defines a graph of which we can compute the spectrum.

For example, let $p$ be odd, and take $e_i = p^{l_i} + 1$ $(i=1,2)$
and $q = p^\kappa$ where $\kappa = 4 l_i s_i$ $(i=1,2)$.
Pick $J_1$ to consist of even numbers only, and $J_2$ to consist
of odd numbers only. Then $D_1 \cap D_2 = \emptyset$ and
$g \in -J_i$ $(\mod e_i)$ cannot happen for $i=1,2$ simultaneously.
This means that the resulting graph will be strongly regular
with eigenvalues
$$
k=(|J_1|/e_1 +|J_2|/e_2)(q-1)
$$
and
$$
\theta ( \chi_g ) = ({|J_1| \over e_1} + {|J_2| \over e_2})( -1 + \sqrt q )
- \sqrt q . \delta(g \in -J_i (\mod e_i) \mbox{\rm {} for $i=1$ or $i=2$})
$$
(where $\delta(P) = 1$ if $P$ holds, and $\delta(P) = 0$ otherwise).
This generalizes the first construction of Wilson \& Xiang \cite{WilsonXiang}
(which is the special case $l_1 = 1$ and $J_1 = \{0\}$).
In the special case $p = 3$, $l_1 = 1$, $l_2 = 2$, $e_1 = 4$, $e_2 = 10$,
$J_1 = \{0\}$, $J_2 = \{1\}$, the difference set consists of the powers
$\alpha^i$ with $i \equiv 0$ $(\mod 4)$ or $i \equiv 1$ $(\mod 10)$,
i.e., is the set $\{1,\alpha,\alpha^4,\alpha^8,\alpha^{11},
\alpha^{12},\alpha^{16} \} \langle \alpha^{20} \rangle$,
and we find the first graph from De Lange \cite{deLange} again.
(It has parameters $(v,k,\lambda,\mu) = (6561,2296,787,812)$
and spectrum $2296^1$ $28^{4264}$ $(-53)^{2296}$.)

\begin{thebibliography}{99}

\bibitem{CalderbankKantor} R. Calderbank \& W. M. Kantor,
{\it The geometry of two-weight codes\/},
Bull. London Math. Soc. {\bf 18} (1986) 97--122.

\bibitem{deLange} C. L. M. de Lange,
{\it Some new cyclotomic strongly regular graphs\/},
J. Algebraic Combin. {\bf 4} (1995) 329--330.

\bibitem{vLS} J. H. van Lint \& A. Schrijver,
{\it Construction of strongly regular graphs,
two-weight codes and partial geometries by finite fields\/},
Combinatorica {\bf 1} (1981) 63--73.

\bibitem{McER72} R. J. McEliece \& H. Rumsey, jr.,
{\it Euler products, cyclotomy and coding\/},
J. Number Th. {\bf 4} (1972) 302--311.

\bibitem{McE75}  R. J. McEliece,
{\it Irreducible cyclic codes and Gauss sums\/},
pp. 183--200 in: Combinatorics (Proc. NATO Advanced Study Inst.,
Breukelen, 1974; M. Hall, Jr. and J. H. van Lint (eds.)),
Part 1, Math. Centre Tracts, No. 55, Math. Centrum,
Amsterdam, 1974.  Republished by Reidel, Dordrecht, 1975
(pp. 185--202).

\bibitem{WilsonXiang} R. M. Wilson \& Qing Xiang,
{Cyclotomy, Half Ovoids and Two-weight Codes\/},
Unpublished preprint, 1997.
\end{thebibliography}

\bigskip
\noindent{\bf A. E. Brouwer}
Department of Mathematics,
Eindhoven University of Technology,
P.O. Box 513, 5600 MB \ Eindhoven, The Netherlands.\\
 e-mail: aeb@cwi.nl

\bigskip
\noindent{\bf R. M. Wilson}
Department of Mathematics,
California Institute of Technology,
Pasadena, California 91125, USA.\\
 e-mail: rmw@cco.caltech.edu

\bigskip
\noindent{\bf Qing Xiang}
Department of Mathematical Sciences,
University of Delaware, Newark, DE 19716, USA.\\
 e-mail: xiang@cco.caltech.edu
\end{document}
