The nature of the spectrum of generalized Paley graphs and weak Waring numbers over finite fields

Abstract

We consider the family of generalized Paley graphs (GP-graphs for short) $\Gamma (k,q)=Cay({\mathbb{F}}_q,({\mathbb{F}}_q^{\ast }{)}^k)$, with $q=p^m$ and $p$ prime. We characterize all GP-graphs having real spectrum; namely, $Spec(\Gamma (k,q))\subset \mathbb{R}$ if and only if $\Gamma (k,q)$ is undirected. We then study conditions for integrality in the spectrum and give a general method to produce integral GP-graphs through cyclotomic polynomials. Using this, we construct several infinite families of integral GP-graphs. Next, we focus on directed GP-graphs (GP-digraphs). We show that GP-digraphs always have three or more eigenvalues, and then we prove that there is only one kind of GP-digraphs having three different eigenvalues: the oriented Paley graphs ${\vec{\mathcal{P}}}_q$ or disjoint unions of copies of them, ${\vec{\mathcal{P}}}_q\cup \cdots \cup {\vec{\mathcal{P}}}_q$. Then, we show that generically the GP-digraphs have period 1 (equivalently index of imprimitivity 1) except for $\Gamma (q-1,q)$ with $q$ odd, which is the disjoint union of oriented $p$-cycles, having period $p$. Finally, as an application, we study weak Waring numbers over finite fields through GP-graphs. In particular, we reduce the computation of the weak Waring numbers over finite fields to the computation of classic Waring numbers over finite fields, a result previously obtained by Cochrane and Cipra in 2012 by other means.

41 pages