\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P29}{20(1)}{2013}

\usepackage{amsmath,amssymb,bbm,theorem}

%%%%%%%%%% Start TeXmacs macros
\newcommand{\assign}{:=}
\newcommand{\tmmathbf}[1]{\ensuremath{\boldsymbol{#1}}}
\newcommand{\tmop}[1]{\ensuremath{\operatorname{#1}}}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}
\newenvironment{proof}{\noindent\textbf{Proof\ }}{\hspace*{\fill}$\Box$\medskip}

\begin{document}


\title{Integral Cayley graphs generated by distance sets\\
       in vector spaces over finite fields}
\author{
Nguyen Ngoc Dai\\
\small School of Applied Mathematics and Informatics \\[-0.8ex]
\small Hanoi University of Science and Technology\\
\small\tt nguyendai236@gmail.com\\
\and 
Nguyen Minh Hai\\
\small Faculty of Mathematics, Mechanics and Informatics\\[-0.8ex]
\small Hanoi University of Science\\[-0.8ex] 
\small Vietnam National University, Hanoi\\
\small\tt nguyenminhhai06@gmail.com\\
\and
Do Duy Hieu\\
\small Faculty of Mathematics, Mechanics and Informatics\\[-0.8ex]
\small Hanoi University of Science\\[-0.8ex] 
\small Vietnam National University, Hanoi\\
\small\tt duyhieua1t@gmail.com\\
\and
Le Anh Vinh\footnote{This research was supported by Vietnam National Foundation for Science and Technology Development grant 102.01-2012.29.}\\
\small University of Education\\[-0.8ex]
\small Vietnam National University, Hanoi\\
\small\tt vinhla@vnu.edu.vn
}
\date{\dateline{Sep 20, 2012}{Jan 23, 2013}{Feb 5, 2013}}

\maketitle

\begin{abstract}
Si Li and the fourth listed author (2008) considered unitary graphs attached to the vector spaces over finite rings using an analogue of the Euclidean distance. These graphs are shown to be integral when the cardinality of the ring is odd or the dimension is even. In this paper, we show that the statement also holds for the remaining case: the cardinality of the ring is even and the dimension is odd, by showing a sufficient condition for Cayley graphs generated by distance sets in vector spaces over finite fields to be integral.

\phantom{spacer}
\end{abstract}

\section{Introduction}

Let $\Gamma$ be an additive group. For $S \subseteq \Gamma$, $0 \not \in S$, and
$S^{- 1} =\{- s : s \in S\}= S$, the Cayley graph $G = C (\Gamma, S)$ is the
undirected graph where the vertex set $V (G) = \Gamma$ and the edge set $E (G) =\{(a,
b) : a - b \in S\}$. The Cayley graph $G = C (\Gamma, S)$ is regular of degree
$|S|$. For any positive integer $n > 1$, let $\mathbb{Z}_n =\mathbb{Z}/n\mathbb{Z}$ be the finite cyclic ring of $n$ elements. Notice that one can identify $\mathbb{Z}_n$
with $\{0, 1, \dots, n-1\}$. The unitary Cayley graph $X_n = C (\mathbbm{Z}_n,
\mathbbm{Z}_n^{*})$ is defined by the additive group of the ring $\mathbbm{Z}_n$ of integers modulo
$n$ and the multiplicative group $\mathbbm{Z}_n^{*}$ of its units. So $X_n$ has vertex set $V
(X_n) = \mathbbm{Z}_n =\{0, 1, \ldots, n - 1\}$ and edge set \[E (X_n) =\{(a, b) : a, b
\in \mathbbm{Z}_n, \gcd (a - b, n) = 1\}.\] The graph $X_n$ is regular of degree $|\mathbbm{Z}_n^{*} |
= \phi (n)$, where $\phi (n)$ denotes the Euler function. Unitary Cayley
graphs are highly symmetric and have some remarkable properties connecting
graph theory and number theory. More information about the unitary Cayley
graphs can be found in Berrizbeitia and Giudici \cite{berrizbeitia}, Dejter and Giudici \cite{dejter},
Fuchs \cite{fuchs 1}, and Klotz and Sander \cite{klotz}.

In \cite{si-vinh}, Si Li and the fourth listed author studied higher dimensional unitary Cayley graphs over 
$\mathbbm{Z}_n^d$ using an analogue of the Euclidean distance. Precisely, they
defined for positive integers $n$ and $d$ the unitary Euclidean graph $T_n^{(d)}$ with vertex
set $V (T_n^{(d)}) = \mathbbm{Z}_n^d$ and edge set
\begin{equation}
  E (T_n^{(d)}) = \left\{ (a, b) : d (a, b) = \sum_{i = 1}^d (a_i - b_i)^2 \in
  \mathbbm{Z}_n^{*} \right\}.
\end{equation}
Note that the Euclidean graph $E_R^{(d)}(r)$ over a finite ring $R$, $r \in R$, is the Cayley graph with vertex set $V(E_R^{(d)}(r)) = R^d$ and the edge set
\begin{equation*}
  E (E_R^{(d)}(r)) = \left\{ (a, b) : d (a, b) = \sum_{i = 1}^d (a_i - b_i)^2 = r\right\}.
\end{equation*}

In \cite{medrano 1}, Medrano, Myers, Stark and Terras studied the spectrum of the Euclidean graphs over finite fields and showed that these graphs are asymptotically Ramanujan graphs. In \cite{medrano 2}, these authors studied the same problem for the Euclidean graphs over rings $\mathbbm{Z}_q$ for an odd prime power $q$. They showed that over rings, except for the smallest case, the graphs (with unit distance parameter) are not (asymptotically) Ramanujan. 

In \cite{bannai}, Bannai, Shimabukuro and Tanaka showed that the Euclidean graphs over finite fields are always asymptotically Ramanujan for a more general setting (i.e. they replace the Euclidean distance by nondegenerated quadratic forms). The fourth listed author recently applied  these results to several interesting combinatorial problems, for example to the Erd\H{o}s distance problem \cite{vinh 1}, Szemeredi-Trotter type theorem and sum-product estimate \cite{vinh 2}, singular matrices with restricted entries over finite fields \cite{vinh-dm} and explicit constructions of existentially closed graphs \cite{vinh-dam}. 

Si Li and the fourth listed author \cite{si-vinh} showed that the spectrum of unitary finite-Euclidean graphs consists entirely of integers when $n$ is odd or the dimension $d$ is even. This property seems to be amazingly widespread among Cayley graphs on abelian groups. One of the first papers in this direction is due to L. Lov\'asz \cite{lovasz 1}, who proved that all Cayley graphs, (cube-like) graphs, on $\mathbbm{Z}_2^d$ are integral where $\mathbbm{Z}_n$ is the ring of integers modulo $n$. In this paper, we extend this result by showing a sufficient condition for Cayley graphs generated by distance sets in vector spaces over finite fields are integral. We would like to remark that our result is closely related to the result of W. So in \cite{so}.


\section{Cayley graphs generated by distance sets}

For any $\mathcal{U}\subseteq  \mathbb{Z}_n$, the distance graph generated by $\mathcal{U}$ over $\mathbb{Z}_n^l$, $G(\mathbb{Z}_n^l,\mathcal{U})$, is the undirected graph that has the vertex set $V(G)=\mathbb{Z}_n^l$ and
the edge set
\[E(G)=\{(\tmmathbf{a},\tmmathbf{b}): d(\tmmathbf{a},\tmmathbf{b})= \sum_{i=1}^{l}(a_i-b_i)^2 \in \mathcal{U}\}.\]
Let
\[S_{l,n}(\mathcal{U})=\{\tmmathbf{a}\in \mathbb{Z}_n^l: d(\tmmathbf{a},\tmmathbf{0}) = a_1^2 + \ldots + a_l^2 \in \mathcal{U} \}, \]
then the graph $G(\mathbb{Z}_n^l,\mathcal{U})$ is the Cayley graph $C(\mathbb{Z}_n^l,S_{l,n}(\mathcal{U}))$.
Recall that the eigenvalues of Cayley graphs of abelian groups can be computed easily in terms of the characters of the group. This is an old result and easy to prove: the characters of a finite abelian group are eigenfunctions for the convolution operators on the group (see also \cite{medrano 1}). This implies that the eigenvalues of the graph $G(\mathbb{Z}_n^l,\mathcal{U})$ are all the numbers
\begin{equation}
\lambda_{\tmmathbf{b}} = \sum_{\tmmathbf{x}\in S_{l,n}(\mathcal{U})} e_n (^t\tmmathbf{b} \cdot \tmmathbf{x}),
\end{equation}
where $\tmmathbf{b} \in \mathbbm{Z}_n^{l}$ and the exponential $e_n (z) = \exp \{2 \pi i z / n\}$. 

In particular, the unitary Euclidean graph $T_n^{(d)}$ is the Cayley graph generated by the distance set $\mathcal{U} = \mathbb{Z}_n^{\ast}$.  Using properties of Gauss and Ramanujan's sums over cyclic rings, Si Li and the fourth listed author \cite{si-vinh} showed that $T_n^{(d)}$ is an integral graph if $n$ is odd or $d$ is even.

\begin{theorem} \label{old-thm} (\cite[Theorem 3.6]{si-vinh})
  If $n$ is an odd integer or $d$ is an even integer then all eigenvalues of the unitary Euclidean graph $T_n^{(d)}$ are integers. 
\end{theorem}

They conjectured that the same result also holds in general. 

\begin{conjecture} \label{old-conj} (\cite[Conjecture 3.7]{si-vinh})
 For any positive integers $n$ and $d$ all eigenvalues of the unitary Euclidean graph $T_n^{(d)}$ are integers. 
\end{conjecture}

From Theorem \ref{old-thm}, the remaining open case of Conjecture \ref{old-conj} is: $n$ even and $d$ odd.  In this paper, we will give a simple proof of this conjecture. More precisely, we have the following sufficient condition for Cayley graphs generated by distance sets in vector spaces over finite fields are integral. We conjecture that the given condition is also the necessary condition. 


\begin{theorem} \label{main}
Suppose that $d_1,d_2,\dots,d_r$ are divisors of $n$. Let
\begin{equation} \label{e2} \mathcal{U}=\cup_{j=1}^{r}G_n(d_j),\end{equation}
where \[G_n(d_j)=\{ y \in \mathbb{Z}_n : gcd(n,y)=d_j \}.\] Then we have
$\lambda_{\mathcal{U}}(\tmmathbf{b})\in\mathbb{Z}$
for all $\tmmathbf{b} \in \mathbbm{Z}_n^l$.
\end{theorem}

\begin{proof}
Let $d$ be a divisor of $n$. Note that $\tmmathbf{x}\in S_{l,n}(G_n(d))$ then $k\cdot \tmmathbf{x}\in S_{l,n}(G_n(d))$ for any $k\in \mathbb{Z}_n^*$, and if $\tmmathbf{x}\not= \tmmathbf{x'}$ then $k\cdot\tmmathbf{x}\not=k\cdot \tmmathbf{x'}$ for every $k\in \mathbb{Z}_n^*$. Since $S_{d,n}(G_n(d))$ is finite, it follows that
\begin{equation*}
kS_{l,n}(G_n(d)) \equiv S_{l,n}(G_n(d)).
\end{equation*}
Hence, $k S_{l,n}(\mathcal{U}) \equiv S_{l,n}(\mathcal{U})$ when $\mathcal{U}$ is of the form (\ref{e2}).

We write $n = p_1^{r_1}\cdots p_t^{r_t}$ for the prime decomposition of $n$. For any nonempty subset $I \subseteq \{1,\dots,t\}$, set \[ p_I=\prod_{i\in I} p_i \,\,\, \mbox{and}\,\,\, n_I=n/p_I.\]
We have
\begin {eqnarray*}
\lambda_{\mathcal{U}}(\tmmathbf{b})&=&\sum_{\tmmathbf{x}\in S_{l,n}(\mathcal{U})}e_n(^t\tmmathbf{b}\cdot \tmmathbf{x})\\
&=&\frac{1}{|\mathbb{Z}_n^*|}\sum_{k\in \mathbb{Z}_n^*}\sum_{\tmmathbf{x}\in kS_{l,n}(\mathcal{U})}e_n(^t\tmmathbf{b}\cdot\tmmathbf{x})\\
&=&\frac{1}{|\mathbb{Z}_n^*|}\sum_{\tmmathbf{x}\in S_{l,n}(\mathcal{U})}\sum_{k\in \mathbb{Z}_n^*}e_n(k^t\tmmathbf{b}\cdot\tmmathbf{x})\\
&=&\frac{1}{|\mathbb{Z}_n^*|}\sum_{\tmmathbf{x}\in S_{l,n}(\mathcal{U}),^t\tmmathbf{b}\cdot\tmmathbf{x}=0}|\mathbb{Z}_n^*|+\frac{1}{|\mathbb{Z}_n^*|}\sum_{\tmmathbf{x}\in S_{l,n}(\mathcal{U}),^t\tmmathbf{b}\cdot\tmmathbf{x}\not=0}\sum_{k\in \mathbb{Z}_n^*}e_n(k^t\tmmathbf{b}\cdot\tmmathbf{x})\\
&=& \#\{ \tmmathbf{x}\in S_{l,n}(\mathcal{U}),^t\tmmathbf{b}\cdot\tmmathbf{x}=0\} \\ && +\frac{1}{|\mathbb{Z}_n^*|}\sum_{\tmmathbf{x}\in S_{l,n}(\mathcal{U}),^t\tmmathbf{b}\cdot\tmmathbf{x}\not=0} \sum_{k\in\mathbb{Z}_n}e_n(k^t\tmmathbf{b}\cdot\tmmathbf{x})\\
&& + \frac{1}{|\mathbb{Z}_n^*|}\sum_{\tmmathbf{x}\in S_{l,n}(\mathcal{U}),^t\tmmathbf{b}\cdot\tmmathbf{x}\not=0}\sum_{I\subseteq\{1,\dots,t\}}(-1)^{|I|}\sum_{s\in\mathbb{Z}_{n_I}}e_n(p_Is^t\tmmathbf{b}\cdot\tmmathbf{x}).
\end{eqnarray*}

Since $^t\tmmathbf{b}\cdot\tmmathbf{x}\not=0$, from the orthogonality of exponential sums, we have 
\[\sum_{s\in\mathbb{Z}_{n_I}}e_n(p_Is^t\tmmathbf{b}\cdot\tmmathbf{x})=1\] 
 if $n=p_1\cdots p_t$ and $I=\{1,2,\dots,t\}$; and
\[\sum_{s\in\mathbb{Z}_{n_I}}e_n(p_Is^t\tmmathbf{b}\cdot\tmmathbf{x})=0\]
otherwise.
This implies that $\lambda_{\mathcal{U}}(\tmmathbf{b})\in \mathbb{Q}$ for any $\tmmathbf{b}\in\mathbb{Z}_n^l$.
Furthermore, the characteristic polynomial of the adjacency matrix of $G(\mathbb{Z}_n^l,\mathcal{U})$ is monic with integer coefficients, so $\lambda_{\mathcal{U}}(\tmmathbf{b})\in\mathbb{Z}$ for any $\tmmathbf{b}\in\mathbb{Z}_n^l$. This concludes the proof of the theorem.
\end{proof}

Note that Theorem \ref{main} implies Conjecture \ref{old-conj} by setting $r = 1$ and $d_1 = 1$. 

\begin{remark} 
For any distance function $f : \mathbb{Z}_n^l \times \mathbb{Z}_n^l \rightarrow \mathbb{Z}_n$ and the distance set $\mathcal{U} \subset \mathbb{Z}_n$, define the generating set 
\[S_{l,n}(f,\mathcal{U})=\{\tmmathbf{a}\in \mathbb{Z}_n^l: f(\tmmathbf{a},\tmmathbf{0}) \in \mathcal{U} \}.\]
The above proof of Theorem \ref{main} works transparently for any distance function $f$ that satisfies the condition $k S_{l,n}(\mathcal{U}) \equiv S_{l,n}(\mathcal{U})$ when $\mathcal{U}$ is of the form (\ref{e2}). For example, Theorem \ref{main} still holds if we use the distance function $d(\tmmathbf{a},\tmmathbf{b})= \sum_{i=1}^{l}(a_i-b_i)^h$ for any $h \ge 1$. Let $l = h = 1$, we obtain alternative proofs of \cite[Theorem 16]{klotz} and \cite[Corollary 4.5]{so}.

\end{remark}

\begin{thebibliography}{99}



\bibitem{angle} J. Angle, B. Shook, A. Terras, C. Trimble and E. Velasquez, Graph spectra for finite upper half planes over rings, \textit{Linear Algebra Applications}, \textbf{226-228} (1995), 423--457.



\bibitem{bannai}
E. Bannai, O. Shimabukuro and H. Tanaka, Finite Euclidean graphs and Ramanujan graphs, \textit{Discrete Mathematics} (to appear).


\bibitem{berrizbeitia} P. Berrizbeitia and R. E. Giudici, On cycles in the sequence of unitary Cayley graphs, \textit{Discrete Mathematics} \textbf{282} 1-3 (2004), 239--243.

\bibitem{berndt} B. C. Berndt, R. J. Evans and K. S. Williams, \textit{Gauss and Jacobi Sums}, Canadian Mathematical Society Series of Monographs and Advanced Texts \textbf{21}, John Wiley \& Sons (1998).

\bibitem{dejter} I. J. Dejter and R. E. Giudici, On unitary Cayley graphs, \textit{J. Combin. Math. Combin. Comput.}, \textbf{18} (1995), 121--124.



\bibitem{fuchs 1} E. D. Fuchs, Longest induced cycles in circulant graphs, \textit{The Electronic Journal of Combinatorics}, \textbf{12} (2005), 1-12. 


\bibitem{klotz} W. Klotz and T. Sander, Some properties of unitary Cayley graphs, \textit{The Electronic Journal of Combinatorics}, \textbf{14} (2007), R45. 

\bibitem{si-vinh} S. Li and L. A. Vinh, On the spectrum of unitary Euclidean graphs, \textit{Ars Combinatoria} (to appear), eprint arxiv.org/abs/0802.1231 

\bibitem{lovasz 1} L. Lov\'asz, Spectra of graphs with transitive groups, \textit{Periodica Mathematica Hungarica}, \textbf{6} (1975), 191-195.



\bibitem{mccarthy} P. J. McCarthy, \textit{Introduction to arithmetical functions}, Universitext. Springer-Verlag, New York, 1994.



\bibitem{medrano 1} A. Medrano, P. Myers, H. M. Stark and A. Terras, Finite analogues of Euclidean space, \textit{Journal of Computational and Applied Mathematics}, \textbf{68} (1996), 221--238.



\bibitem{medrano 2} A. Medrano, P. Myers, H. M. Stark and A. Terras, Finite Euclidean graphs over rings,
\textit{Proceedings of the American Mathematics Society}, \textbf{126}  (1998), 701--710.



\bibitem{so}
W. So, Integral circulant graphs, \textit{Discrete Mathematics}, \textbf{306} (2006), 153-158.


\bibitem{vinh 1}
L. A. Vinh, Explicit Ramsey graphs and Erd\H{o}s distance problem over finite Euclidean and non-Euclidean spaces, \textit{The Electronic Journal of Combinatorics}, \textbf{15} (1), 2008, R5. 



\bibitem{vinh 2}
L. A. Vinh, Szemeredi-Trotter type theorem and sum-product estimate in finite fields, \textit{The European Journal of Combinatorics}, \textbf{32}(8), 1177-1181 (2011)

\bibitem{vinh-dm} L. A. Vinh, Singular matrices with restricted rows in vector spaces over finite fields, \textit{Discrete Mathematics} \textbf{312}(2), 413--418 (2012).

\bibitem{vinh-dam} L. A. Vinh, An explicit construction of $(3,k)$-existentially closed graphs, \textit{Discrete Applied Mathematics} (to appear).


\end{thebibliography}




\end{document}
