Spectral properties of generalized Paley graphs

Abstract

We study the spectrum of generalized Paley graphs $\hat{I}“(k,q)=Cay({\mathbb{F}}_q,R_k)$, undirected or not, with $R_k=\{x^k:x\in {\mathbb{F}}_q^{\ast }\}$ where $q=p^m$ with $p$ prime and $k\mid q-1$. We first show that the eigenvalues of $\hat{I}“(k,q)$ are given by the Gaussian periods $\hat{I}{\cdot }_i^{(k,q)}$ with $0\le i\le k-1$. Then, we explicitly compute the spectrum of $\hat{I}“(k,q)$ with $1\le k\le 4$ and of $\hat{I}“(5,q)$ for $p\equiv 1(\mathrm{mod}5)$ and $5\mid m$. Also, we characterize those GP-graphs having integral spectrum, showing that $\hat{I}“(k,q)$ is integral if and only if $p$ divides $(q-1)/(p-1)$. Next, we focus on the family of semiprimitive GP-graphs. We show that they are integral strongly regular graphs (of pseudo-Latin square type). Finally, we characterize all integral Ramanujan graphs $\hat{I}“(k,q)$ with $1\le k\le 4$ or where $(k,q)$ is a semiprimitive pair.

32 pages, 2 tables. The old manuscript arXiv:1908.08097 has grown and we divided it into two different manuscripts with different names, this is the first half, and the other one is in progress. (This version with additions and corrections)