On the Paley graph of a quadratic character

Let $q=p^{n}$ be a prime power. The Paley graph $P_{q}$ is the graph with the following data

1. (1)

   The vertex set of $P_{q}$ is ${\mathbb{F}}_{q}$; here ${\mathbb{F}}_{q}$ is the finite field with $q$ elements;

2. (2)

   Two vertices $u,v$ are connected if and only $u-v$ a nonzero square in ${\mathbb{F}}_{q}$; i.e., $v-u$ is an element of the set

   $$S=\{x^{2}\mid x\in{\mathbb{F}}_{q},x\neq 0\}.$$

Let us recall the definition of the Caley graph $\Gamma(G,S)$ where $G$ is a group and a set $S$ is a subset of $G$ which has the property that $1\not\in S$. The vertices of $\Gamma(G,S)$ are elements of $G$ and the edges of $\Gamma(G,S)$ are given by

(See [6, 19]). We note that in [18, Definition 2.3.1], the author requires that $S$ is symmetric in the sense that $s\in S$ if and only if $s^{-1}\in S$ (this symmetric condition guarantees that $\Gamma(G,S)$ is an undirected graph). In the case $G={\mathbb{F}}_{q}$ as an additive group, we see that $P_{q}$ is exactly the Caley graph $\Gamma(G,S)$ with $S=({\mathbb{F}}_{q}^{\times})^{2}:=\{x^{2}\mid x\in{\mathbb{F}}_{q}^{\times}\}$. (Here we use the standard notation ${\mathbb{F}}_{q}^{\times}={\mathbb{F}}_{q}\setminus\{0\}$.) We remark that $-1\in S$ if and only if $q\equiv 1\pmod{4}.$ Therefore, $P_{q}$ is an undirected graph for $q\equiv 1\pmod{4}.$

The origin of Paley graphs can be traced back to Paley’s 1933 paper [27] in which he implicitly used them to construct Hadamard matrices. These graphs were later rediscovered by Carlitz in [5], though this time in a different context. Gareth A. Jones had the following remark in [16] about Paley graphs

Anyone who seriously studies algebraic graph theory or finite permutation groups will, sooner or later, come across the Paley graphs and their automorphism groups.

Due to its arithmetic and representation theoretic nature, we have various tools to study Paley graphs. Consequently, they have interesting properties that make them useful for graph theory and related fields. For example, Paley graphs have found applications in coding and cryptography theory (see [12, 14]).

In this article, we define and study generalized Paley graphs which are associated with general quadratic characters (we refer the reader to Section 2 for the precise definition of these graphs). The terminology ”generalized Paley graphs” was used earlier in some papers of C.E. Praeger and her collaborators. Their generalization of Paley graphs, however, went in another direction from our generalization (see [21]). Therefore a possible confusion is unlikely. Using the theory of Gauss sums and circulant matrices, we describe explicitly the spectrum of these generalized Paley graphs. We then give a complete answer to the following question: which generalized Paley graphs are Ramanujan? In the final section, we provide an effective upper bound for the Cheeger number of these generalized Paley graphs using special values of $L$-functions. As a by-product of our approach, we settle a question raised in [8, Section 2.2] about the size of this upper bound.

In closing the introduction, we remark that our interest in this topic arises naturally from our recent works on generalized Fekete polynomials (see [24, 23]), on the join of circulant matrices (see [7, 10]), and on some new constructions of Ramanujan graphs (see [11]).

In this section, we compute the spectrum of $P_{\Delta}$. By the Circulant Diagonalization Theorem (see [9]), the spectrum of $P_{\Delta}$ is given by

where $\omega$ runs over the set of all $D$th roots of unity. Note that for each $\omega$, there exists a unique positive integer $d|D$ such that $\omega$ is a primitive $d$th root of unity. We first recall the definition of the Möbius function

We also recall Ramanujan’s sum (see [13, Section 5.6]). Let $m,n$ be two positive integers. The Ramanujan sum $c_{n}(m)$ is defined as follow

If $\gcd(n,m)=a$ and $n=aN$ then by [13, Theorem 272], we have

In particular, when $m=1$ and $n=d$, we have (see [13, Equation 16.4.4])

We recall the theory of Gauss sum. Let $\zeta_{D}=\exp\left(\frac{2\pi i}{D}\right)$ be a primitive $D$th root of unity.

We recall the following fundamental property [1, Theorem 4.12, page 312]

Furthermore, by [1, Theorem 4.17], we have $G(1,\chi)=\sqrt{\Delta}$. Consequently $G(b,\chi)=\chi(b)\sqrt{\Delta}$. In particular, if $\omega$ is not a primitive $D$th root of unity then

On the other hand, if $\omega$ is a primitive $D$th root of unity, namely $\omega=\zeta_{D}^{b}$ with $\gcd(b,D)=1$ then

In summary, we have the following lemma.

We can now simplify $\lambda(\omega).$ In fact

We consider two cases.
Case 1. $\omega$ is a primitive $d$th root of unity with $d<D.$ In this case

and

Therefore

Case 2. $\omega=\zeta_{D}^{b}$ is a primitive $D$th root of unity; namely $\omega=\zeta_{D}^{b}$ with $\gcd(b,D)=1$. In this case, we have

and

Consequently

Let us write $[a]_{b}$ for the multiset $\{\underbrace{a,\ldots,a}_{\text{$b$ times}}\}$. By the above calculations, we have the following conclusion.

We discuss a corollary of this theorem. First, we recall that an undirected graph $G=(V,E)$ is called a bipartite graph if $V(G)$ can be decomposed into two disjoint sets such that no two vertices within the same set are adjacent. As explained in [26], if $G$ is regular of degree $r$ then $G$ is a bipartite graph if and only if $-r$ is an eigenvalue of $G.$

In this section, we investigate the following question: which $P_{\Delta}$ is a Ramanujan graph? For this question to make sense, we need to assume that $P_{\Delta}$ is an undirected graph. This requires $\chi_{\Delta}$ is an even character; or equivalently $\Delta>0.$ We first recall the definition of a Ramanujan graph (see [22, 26]).

It is well-known that $P_{\Delta}$ is a Ramanujan graph if $\Delta=p$, where $p$ is a prime number, which is congruent to 1 modulo 4. In fact, by Proposition 2.5, $P_{\Delta}$ is a regular graph of degree $r:=\dfrac{p-1}{2}$. By Theorem 3.5, the eigenvalues of the adjacency matrix of $P_{\Delta}$ which are smaller than $r$ are $\dfrac{\pm\sqrt{p}-1}{2}$. Because $p\equiv 1\pmod{4}$ we see that $p\geq 5$ and $\lambda(P_{\Delta})=\dfrac{\sqrt{p}+1}{2}<2\sqrt{r-1}=2\sqrt{\dfrac{p-3}{2}}$. When $D$ is not a prime number, we have the following.

Let $\chi=\chi_{\Delta}$ be an even quadratic character (in other words, $\Delta>0$) and $P_{\Delta}$ the corresponding generalized Paley graph. In this section, we provide an upper bound for the Cheeger number of $P_{\Delta}$ (also known by other names such as isoperimetric number or edge expansion ratio). Our estimation gives a natural generalization of the results in [8]. We also answer the authors’ suspicion about the relationship between the upper bounds that they used in this paper, namely the $\alpha$-bound and the $\dfrac{p-1}{4}$-bound (see [8, Section 2.2].) While our result is more general and explicit, we remark that our approach is inspired by the method in [8].

First, let us recall the definition of the Cheeger number of a graph. Let $G=(E,V)$ be an undirected graph. Let $F$ be a subset of $V$. For a subset $F\subseteq V$, the boundary of $F$, denoted by $\partial{F}$, is the set of all edges going from a vertex in $F$ to a vertex outside of $F$. The Cheeger number of $G$ is defined as