Spectral properties of generalized Paley graphs and their associated irreducible cyclic codes

Abstract

For $q=p^m$ with $p$ prime and $k\mid q-1$, we consider the generalized Paley graph $\Gamma (k,q)=Cay({\mathbb{F}}_q,R_k)$, with $R_k=\{x^k:x\in {\mathbb{F}}_q^{\ast }\}$, and the irreducible $p$-ary cyclic code $\mathcal{C}(k,q)=\{({\text{Tr}}_{q/p}(\gamma {\omega }^{ik}{)}_{i=0}^{n-1}){\}}_{\gamma \in {\mathbb{F}}_q}$, with $\omega$ a primitive element of ${\mathbb{F}}_q$ and $n=\frac{q-1}{k}$. We first express the spectra of $\Gamma (k,q)$ in terms of Gaussian periods. Then, we show that the spectra of $\Gamma (k,q)$ and $\mathcal{C}(k,q)$ are mutually determined by each other if further $k\mid \frac{q-1}{p-1}$. We give $Spec(\Gamma (k,q))$ explicitly for those graphs associated with irreducible 2-weight cyclic codes in the semiprimitive and exceptional cases. We also compute $Spec(\Gamma (3,q))$ and $Spec(\Gamma (4,q))$.

We have improved Definition 3.1 and the comments before it. We have improved Theorem 4.1 (now a complete characterization of Ramanujan graphs) and give a complete proof. 22 pages, 6 tables