INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 6 (2006), #A18

CHARACTER SUMS AND RAMSEY PROPERTIES OF GENERALIZED PALEY GRAPHS

Nicholas Wage

Appleton East High School, Appleton, WI 54915, USA

                             wageee@gmail.com

Received: 8/23/05, Revised: 5/16/06, Accepted: 5/26/06, Published: 6/1/06

Abstract

In a classic paper, Evans, Pulham, and Sheehan computed the number of complete graphs of size 4 for a special class of graphs called Paley Graphs. Here we consider analogous questions for generalized Paley-type graphs.

1. Introduction

The Ramsey number R(m) is the smallest positive integer such that any graph G with R(m) or more vertices contains a complete subgraph of size m or its complement G^{c} contains a complete subgraph of size m. The only values of m for which R(m) is known are m ≤ 4. We consider a natural extension of computing and estimating R(m). For a graph G, let k_{m}(G) denote the number of complete graphs of size m contained in G. Let

T_{m}(n) := min(k_{m}(G) + k_{m}(G^{c}))  (1)

as G ranges over all graphs with n vertices. Note that R(m) is the smallest n for which T_{m}(n) > 0. In [Erd62], Erdős conjectured that

lim_{n→∞} \frac{T_{m}(n)}{n^{m}} = \frac{1}{2^{\binom{m}{2}−1}m!}.  (2)

However, this is not quite correct. In [Tho97], Thomason showed that for m = 4, this limit is no more than 1/(33 · 4!), rather than 1/(32 · 4!) as the conjecture predicts.

For a prime p ≡ 1 (mod 4), let G(p) denote the Paley graph with p vertices, indexed 0 through p − 1. A Paley graph contains an edge x ↔ y if and only if ϕ(x − y) = 1, where ϕ(·) denotes the Legendre symbol (\frac{·}{p}). This notation assumes that the prime p will be clear from context. For example, the Paley graph G(5) is a pentagon. The Legendre symbol is multiplicative and ϕ(−1) = 1 if p ≡ 1 (mod 4). Therefore, ϕ(y − x) = ϕ(x − y). This equation implies that our definition is symmetric in x and y, so the edges are well defined.

For primes p ≡ 3 (mod 4), ϕ(−1) = −1, so ϕ(x − y) = −ϕ(y − x). In this case we define a generalized directed Paley graph. Note that since ϕ(−1) = −1 for every x and y, there is exactly one directed edge, creating a type of graph called a tournament.

Paley graphs have many interesting properties. They are both self-complementary and self-similar. Also, for the function k_{m}(G) + k_{m}(G^{c}) on graphs with p vertices, Paley graphs are minimal in certain ways. For example, the Ramsey number R(4) = 18; the Paley graph G(17) is the only graph (up to isomorphism) with 17 vertices such that k_{4}(G) + k_{4}(G^{c}) = 0.

This inspired Evans, Pulham, and Sheehan [EPS81] to compute the exact value of k_{4}(G(p)) + k_{4}(G(p)^{c}) using character sums. For m > 4, the character sums are difficult to determine explicitly. We prove an asymptotic result for all m.

Theorem 1. For primes p ≡ 1 (mod 4) and positive integers m

lim_{p→∞} \frac{k_{m}(G(p))}{p^{m}} = \frac{1}{2^{\binom{m}{2}}m!}.

Doubling this value to account for the complete graphs in its isomorphic complement, we see that the conjecture of Erdős, while false for general graphs, is true for the Paley graphs. Moreover, the conjectured bound is exactly achieved by these graphs.

For all primes p and integers |t| > 1 we define two other types of generalized Paley graphs, G_{t}(p) and G′_{t}(p). The graph G_{t}(p) has an edge x ↔ y if and only if both ϕ(x − ty) = 1 and ϕ(y − tx) = 1. The graph G′_{t}(p) has an edge x ↔ y if and only if at least one of these statements is true, that is ϕ(x − ty) = 1 or ϕ(y − tx) = 1. Note that G_{t}(p) is a subgraph of G′_{t}(p).

We now define two related generalized Paley graphs. Definition 1. For a prime p and integer t, let G_{t}(p) denote the graph with p vertices, indexed 0 through p − 1, which contains an edge x ↔ y if and only if ϕ(x − ty) = 1 and ϕ(y − tx) = 1. Similarly, let G′_{t}(p) denote the graph with p vertices, indexed 0 through p − 1, which contains an edge x ↔ y if either ϕ(x − ty) = 1 or ϕ(y − tx) = 1, and contains no edge x ↔ y if neither of these statements hold true.

We prove a similar result for these generalized graphs.

Theorem 2. Let m be a positive integer and t be an integer such that t ≢ −1, 0, 1 (mod p). Then, for primes p, and we have

lim_{p→∞} \frac{k_{m}(G_{t}(p)) + k_{m}(G_{t}(p)^{c})}{p^{m}} = \frac{1}{m!} ((\frac{1}{4})^{\binom{m}{2}} + (\frac{3}{4})^{\binom{m}{2}}) .

Similarly,

lim_{p→∞} \frac{k_{m}(G′_{t}(p)) + k_{m}(G′_{t}(p)^{c})}{p^{m}} = \frac{1}{m!} ((\frac{1}{4})^{\binom{m}{2}} + (\frac{3}{4})^{\binom{m}{2}}) .

Remark. After this work was completed, it was brought to the author’s attention that a paper of Graham, Chung, and Wilson, [CGW88], implies these limits because Paley graphs are examples of quasi-random graphs. However, we stress that the proofs in this paper are direct, and lead to stronger error terms in estimates. In other words, a careful analysis of these proofs leads to strong bounds for the errors between the limiting values and the actual values.

A key result in the work of Evans, Pulham and Sheehan is a formula that exactly computes the number of complete graphs of size 4 in a Paley graph, namely, they obtain

k_{4}(G(p)) = \frac{p − 1}{1536} (p ((p − 9)^{2} − 4x^{2}))  (3)

where x is an even integer such that p = x^{2} + y^{2}. It is known that for p ≡ 1 (mod 4), that x not only exists, but is unique (up to sign). Their proof essentially follows from an evaluation of the hypergeometric sum

3F_{2}(t) = \frac{ϕ(−1)}{p^{2}} ∑_{x∈ℤ/pℤ} ∑_{y∈ℤ/pℤ}ϕ(x)ϕ(y)ϕ(1 − x)ϕ(1 − y)ϕ(x − ty)  (4)

when t = 1. One should note that while it can be shown that this is equivalent to the definition of _{3}F_{2}(t), it is not a priori the definition. Similarly, we will require the sum

2F_{1}(t) = \frac{ϕ(−1)}{p} ∑_{x∈ℤ/pℤ}ϕ(x)ϕ(1 − x)ϕ(1 − tx).  (5)

In this paper we compute a graph theoretic result similar to that of Evans, Pulham, and Sheehan which would normally be intractable without the help of the special t evaluations of these character sums.

Theorem 3. Let p be a prime, and let t be a non-zero element of ℤ/pℤ whose multiplicative order is greater than 3. Let H_{t}(p) represent the directed graph where x → y is an edge if and only if ϕ(x) = ϕ(x − ty) = 1, and let C_{t}(p) denote the number of 3-cycles in H_{t}(p) (x → y → z → x). Then

C_{t}(p) = \frac{p − 1}{192}[90 − 3pϕ(t) + 12ϕ(t + t^{2}) + p^{2} − 14p + 48ϕ(−t) + 27ϕ(t) + 62ϕ(1 − t)
+ 6ϕ(1 − t^{3}) + 12ϕ(t − t^{3}) + 12ϕ(1 − t^{2}) + 12ϕ(−1) + 12ϕ(1 + t) + 24ϕ(t^{2} − t)
+ 6ϕ(t − t^{4}) + 12ϕ(t − t^{2}) + 3ϕ(t^{4} − t)p − 6pϕ(1 − t) − 3ϕ(−t)p + p^{2}_{3}F_{2}(t^{3})
− 6p(1 + ϕ(1 − t))_{2}F_{1}(t^{2}) − 3p(1 + ϕ(t))_{2}F_{1}(t^{3})].

Although this formula is difficult to grasp at first glance, we note that it simplifies dramatically for several special t. For example, we obtain formulas much like (3) in the following cases:

Corollary 1. If t = −2, and p is a prime congruent to 5 or 7 (mod 24), then

C_{t}(p) = \begin{cases}\frac{p−1}{192} (p^{2} − 6p + 4x^{2} + 1) & if p ≡ 5 (mod 24), x^{2} + y^{2} = p, and x odd, \\ \frac{p−1}{192} (p^{2} − 6p + 25) & if p ≡ 7 (mod 24). \end{cases}

Corollary 2. If t = −\frac{1}{2}, and p is a prime congruent to 7 or 13 (mod 24), then

C_{t}(p) = \begin{cases}\frac{p−1}{192}(p^{2} − 6p + 25) & if p ≡ 7 (mod 24), \\ \frac{p−1}{192}(p^{2} + 2p − 4x^{2} + 1) & if p ≡ 13 (mod 24), x^{2} + y^{2} = p, and x odd. \end{cases}

In Section 2 we state the tools that will be necessary in Section 3, where we will prove the main theorems.

2. Preliminaries

We will need the following facts for our proofs. The deepest result we require is due to Weil.

Weil’s Theorem. ([BEW98], pg. 183) If p is a prime, and f(x) ∈ ℤ[x] is a polynomial with degree n which is not congruent modulo p to cg^{2}(x) for any integer c and polynomial g(x) with integer coefficients, then

| ∑_{x∈ℤ/pℤ}ϕ(f(x))| < (n − 1)\sqrt{p}.

Remark. ¿From this point onward, we omit the summation indices with the understanding that all sums are over ℤ/pℤ unless indicated otherwise.

For small n, explicit evaluations of these sums are simple. Clearly, if n = 0,

∑_{x} ϕ(c) = ϕ(c)p.  (6)

Note that as x runs over all the elements of ℤ/pℤ, so does ax + b if a ≢ 0 (mod p). Using this fact, we can also compute the value for n = 1. Let q denote a non-zero, non-residue of ℤ/pℤ. Then

∑_{x} ϕ(ax + b) = ∑_{y=ax+b} ϕ(y)
= ∑_{z=q^{−1}y} ϕ(qz)
= ϕ(q) ∑_{z} ϕ(z)
= − ∑_{y} ϕ(y)
= − ∑_{x} ϕ(ax + b),

so

∑_{x} ϕ(ax + b) = 0.  (7)

Finally, we prove a formula for the case n = 2. Proposition 1. For any prime p and polynomial f(x) = ax^{2} + bx + c with roots r and s is ℤ/pℤ,

∑_{x} ϕ(ax^{2} + bx + c) = \begin{cases}(p − 1)ϕ(a) & if r ≡ s (mod p) \\ −ϕ(a) & if r ≢ s (mod p). \end{cases}

Proof.

∑_{x} ϕ(ax^{2} + bx + c) = ∑_{x} ϕ(a(x − r)(x − s))
= ϕ(a) ∑_{x} ϕ(x)ϕ(x − (s − r)).

Let t = s − r. Note that when t ≡ 0 (mod p), it is clear that ∑_{x} ϕ(x)^{2} = p − 1. When, t ≢ 0

(mod p),

∑_{x} ϕ(x)ϕ(x − t) = ∑_{tx} ϕ(tx)ϕ(t(x − 1)) = ∑_{x} ϕ(x)ϕ(x − 1),

so the summation is equivalent to the summation when t ≡ 1 (mod p). Thus, this is equivalent for all p − 1 non-zero values of t. Note that

∑_{t} ∑_{x} ϕ(x(x − t)) = ∑_{x} ϕ(x) ∑_{t} ϕ(x − t)
= ∑_{x} ϕ(x) ∑_{u=x−t} ϕ(u)
= ∑_{x} ϕ(x) · 0
= 0.

However, we can also show that

∑_{t} ∑_{x} ϕ(x(x − t)) = ∑_{x} ϕ(x)^{2} + (p − 1) ∑_{x} ϕ(x)ϕ(x − t)

= (p − 1) (1 + ∑_{x} ϕ(x)ϕ(x − t)) .

Equating these two expressions, we obtain

ϕ(a) ∑_{x} ϕ(x)ϕ(x − t) = −ϕ(a).

For n ≥ 3 there does not appear to be a general evaluation. However, with additional machinery, certain evaluations are possible. A character χ is a multiplicative function that maps the elements of (ℤ/pℤ)^{∗} to the complex roots of unity. Let χ̄ denote the conjugate character of χ, that is, χ̄(x) = 1/χ(x). By convention, we say that χ(0) = 0. The Legendre symbol is a simple example of a character. Another simple character is ϵ, the trivial character, for which ϵ(x) = 1 unless x ≡ 0 (mod p).

A Jacobi sum, for characters χ and ψ is

J(χ, ψ) := ∑_{x} χ(x)ψ(1 − x).  (8)

Additionally, we define the normalized Jacobi sum for characters A and B

\binom{A}{B} := \frac{B(−1)}{p}J(A, B̄).  (9)

Then, we define

n+1F_{n} ( \begin{matrix}A_{0}, & A_{1}, ...A_{n} \\ & B_{1}, ...B_{n} \end{matrix} |t) := \frac{p}{p − 1} ∑_{χ} \binom{A_{0}χ}{χ}\binom{A_{1}χ}{B_{1}χ} ⋯ \binom{A_{n}χ}{B_{n}χ}χ(t),  (10)

where the sum is over all χ with modulus p. Additionally, we define

n+1F_{n}(t) := _{n+1}F_{n} ( \begin{matrix}ϕ, & ϕ, ...ϕ \\ & ϵ, ...ϵ \end{matrix} |t) .  (11)

Although these functions are expressed in terms of Jacobi sums, it is known that the definitions in the introduction, (5) and (4), are equivalent (see [Ono04]). These objects allow us to find a general formula in terms of _{2}F_{1} when n = 3.

Proposition 2. For any prime p and third-degree polynomial with leading coefficient a and distinct roots q, r, s ∈ ℤ/pℤ, we have

∑_{x} ϕ(a(x − q)(x − r)(x − s)) = ϕ(−a)ϕ(q − s)_{2}F_{1} (\frac{r − s}{q − s}) p.

Proof. The proof of this is straightforward:

∑_{x} ϕ(a(x − q)(x − r)(x − s)) = ϕ(a) ∑_{x} ϕ(x(q − s − x)(r − s − x))
= ϕ(a)ϕ(q − s) ∑_{(q−s)x} ϕ(x)ϕ(1 − x)ϕ (1 − \frac{r − s}{q − s}x)

= ϕ(−a)ϕ(q − s)_{2}F_{1} (\frac{r − s}{q − s}) p.

3. Proof of the Theorems

Using Weil’s Theorem from the previous section, we will prove Theorem 1.

Proof of Theorem 1. The following is a proof by induction. For m = 1, k_{1}(G(p)) = p, so the theorem holds. Assume the theorem holds for m−1. For each prime p ≡ 1 (mod 4) we want to write k_{m}(G(p)) as a character sum. To count the number of complete m-subgraphs, we look at each possible set of m distinct points, and check to see if it is a complete subgraph. Since xy is an edge if and only if ϕ(x − y) = 1, then assuming x ≠ y the equation \frac{1+ϕ(x−y)}{2} conveniently returns 1 if x ↔ y is an edge, and 0 otherwise. Thus, if we take the product of this equation over all pairs selected from our m points, it will return 1 if we have a complete subgraph, and 0 otherwise. We need only sum this product over all possible sets of m distinct points to get k_{m}(G(p)). Therefore

k_{m}(G(p)) = ∑_{a_{1}<···<a_{m}} ( ∏_{0<i<j≤m} \frac{1 + ϕ(a_{i} − a_{j})}{2}) .

We will now manipulate this equation to make it easier to evaluate. First we can isolate the a_{m} terms into their own summation. Second, we can replace the condition that a_{m} is greater than a_{m−1} and simply require it to be distinct from each of the other a_{i}. Note that this will count each set of m vertices m times, once for each possible final term, so we must divide by m. Then, we can separate out the terms of the product not involving a_{m}, and pull out a 2^{1−m} term. The result of all these manipulations is

k_{m}(G(p)) =

∑_{a_{1}<...<a_{m−1}} [( ∏_{0<i<j<m} \frac{1 + ϕ(a_{i} − a_{j})}{2}) (\frac{1}{2^{m−1}m} ∑_{a_{m}≠a_{i}} ∏_{k=1}^{m−1} (1 + ϕ(a_{m} − a_{k})))] .

Note that the beginning of this equation resembles k_{m−1}(G(p)). If we bound

∑_{a_{m}≠a_{i}} ∏_{k=1}^{m−1} (1 + ϕ(a_{m} − a_{k}))

in terms of p and m, then we can pull it outside of the summation. Specifically, if we show that

p − 2^{m}m(\sqrt{p} + 2) ≤ ∑_{a_{m}≠a_{i}} ∏_{k=1}^{m−1} (1 + ϕ(a_{m} − a_{k})) ≤ p + 2^{m}m(\sqrt{p} + 1),  (12)

then

\frac{p − 2^{m}m(\sqrt{p} + 2)}{2^{m−1}m}k_{m−1}(G(p)) ≤ k_{m}(G(p)) ≤ \frac{p + 2^{m}m(\sqrt{p} + 1)}{2^{m−1}m}k_{m−1}(G(p)),

and by the inductive hypothesis we know that

lim_{p→∞} \frac{(p − 2^{m}m(\sqrt{p} + 2))k_{m−1}(G(p))}{p^{m}2^{m−1}m} = lim_{p→∞} \frac{p − 2^{m}m(\sqrt{p} + 2)}{2^{m−1}mp} · \frac{k_{m−1}(G(p))}{p^{m−1}}
= \frac{1}{2^{\binom{m}{2}}m!}.

The right hand bound evaluates to the same limit, and so

lim_{p→∞} \frac{k_{m}(G(p))}{p^{m}} = \frac{1}{2^{\binom{m}{2}}m!},

which proves our result.

All that remains is to prove the bound for (12). We start by multiplying out each product, getting 2^{m−1} terms. The first term is 1, which we sum over the p − (m − 1) possible values of a_{m}.

Now, consider an arbitrary term from the remaining 2^{m−1} terms. It is a product of Legendre symbols of the form ϕ(a_{m} − a_{i}). Since the Legendre symbol is multiplicative, we can form a single Legendre symbol, that is, write the term as ϕ(f(a_{m})) where f is a polynomial with coefficients in ℤ/pℤ. We know the roots of f are among the different a_{i} values, that f contains at least one such root, and, since all the a_{i} are distinct, f has no repeated roots. This means that it is not congruent (mod p) to cg(x)^{2} for any integer c and polynomial g with integer coefficients. Moreover, f has degree at most m − 1 so by Weil’s theorem, we have

−(m − 2)\sqrt{p} ≤ ∑_{a_{m}∈ℤ/pℤ}ϕ(f(a_{m})) ≤ (m − 2)\sqrt{p}.

Note that this sum, however, includes m − 1 terms which are not in the sum we wish to evaluate, namely a_{1}, …, a_{m−1}. Each of these terms is between −1 and 1, so removing them changes the sum by at most m − 1. Therefore,

−m(\sqrt{p} + 1) ≤ −(m − 1)(\sqrt{p} + 1) ≤ ∑_{a_{m}≠a_{i}} ϕ(f(a_{m})) ≤ (m − 1)(\sqrt{p} + 1) ≤ m(\sqrt{p} + 1).

This bound holds for each of the 2^{m−1} − 1 terms involving Legendre symbols, so

p − m + 1 − 2^{m−1}m(\sqrt{p} + 1) ≤ ∑_{a_{m}≠a_{i}} ∏_{k=1}^{m−1} (1 + ϕ(a_{m} − a_{k})) ≤ p − m + 1 + 2^{m−1}m(\sqrt{p} + 1),

which implies (12).

The proof of Theorem 2 is similar to the proof of Theorem 1. This time we examine k_{m}(G_{t}(p)) as a character sum and use Weil’s Theorem to estimate it.

Proof of Theorem 2. We first prove that

lim_{p→∞} \frac{k_{m}(G_{t}(p))}{p^{m}} = \frac{1}{m!} (\frac{1}{4})^{\binom{m}{2}} .  (13)

First consider x and y such that x ≢ y, ty, t^{−1}y, t^{2}y, t^{−2}y (mod p). There is an edge between x and y in G_{t}(p) if and only if ϕ(x − ty) = ϕ(y − tx) = 1. Thus,

\frac{(1 + ϕ(x − ty))}{2} \frac{(1 + ϕ(y − tx))}{2} = \begin{cases}1 & if x ↔ y is an edge, \\ 0 & otherwise. \end{cases}  (14)

As such, we define

h_{m}(p) := ∑_{\begin{matrix}a_{1}<...<a_{m} \\ a_{i}≢ta_{j},t^{2}a_{j} \end{matrix}} ( ∏_{\begin{matrix}0<i,j≤m \\ i≠j \end{matrix}} \frac{1 + ϕ(a_{i} − ta_{j})}{2}) .  (15)

This counts the number of complete subgraphs in G_{t}(p) that do not contain any edges where x ≡ t^{−2}y, t^{−1}y, t^{1}y, t^{2}y (mod p). However, each x ∈ ℤ/pℤ has at most 4 such edges, so there are at most 2p of these edges total since each edge is counted twice. Each such edge is a member of \binom{p−2}{m−2} subgraphs of size m, and so we are missing at most 2p\binom{p−2}{m−2} complete subgraphs of size m. Thus

h_{m}(p) ≤ k_{m}(G_{t}(p)) ≤ h_{m}(p) + 2p\binom{p − 2}{m − 2}.

We divide this equation by p^{m} and take the limit as p tends to infinity. The 2p\binom{p−2}{m−2} term has degree p^{m−1}, so it vanishes, making the left hand side and right hand side limits equal. Therefore

lim_{p→∞} \frac{k_{m}(G_{t}(p))}{p^{m}} = lim_{p→∞} \frac{h_{m}(p)}{p^{m}},

and all that remains is to evaluate (15). In particular, we will show that

lim_{p→∞} \frac{h_{m}(p)}{p^{m}} = \frac{1}{4^{\binom{m}{2}}m!}.

This will be proved by induction. If m = 1, it is clearly true. Otherwise, assume the claim is true for m − 1. Performing the same manipulations as in the proof of Theorem 1, we get

\begin{aligned}h_{m}(p) = ∑_{\begin{matrix}a_{1}<...<a_{m} \\ a_{i}≢ta_{j},t^{2}a_{j} \end{matrix}} & [( ∏_{\begin{matrix}0<i,j<m \\ i≠j \end{matrix}} \frac{1 + ϕ(a_{i} − ta_{j})}{2}) \\ & ×(\frac{1}{4^{m−1}m} ∑_{\begin{matrix}a_{m}≢t^{e}a_{i} \\ −2≤e≤2 \end{matrix}} ∏_{k=1}^{m−1} (1 + ϕ(a_{m} − ta_{k}))(1 + ϕ(a_{k} − ta_{m})))] . \end{aligned}

So, if we show that

| ∑_{\begin{matrix}a_{m}≢t^{e}a_{i} \\ −2≤e≤2 \end{matrix}} ∏_{k=1}^{m−1} (1 + ϕ(a_{m} − ta_{k}))(1 + ϕ(a_{k} − ta_{m})) − p| ≤ 4^{m−1}(2m\sqrt{p} + 5m),  (16)

then

\frac{p − 4^{m−1}(2m\sqrt{p} + 5m)}{4^{m−1}m}h_{m−1}(p) ≤ h_{m}(p) ≤ \frac{p + 4^{m−1}(2m\sqrt{p} + 5m)}{4^{m−1}m}h_{m−1}(p).

Applying the inductive hypothesis, we obtain

lim_{p→∞} \frac{(p − 4^{m−1}(2m\sqrt{p} + 5m))h_{m−1}(p)}{4^{m−1}mp^{m}} = lim_{p→∞} \frac{p − 4^{m−1}(2m\sqrt{p} + 5m)}{4^{m−1}mp} · \frac{h_{m−1}(p)}{p^{m−1}}
= \frac{1}{4^{\binom{m}{2}}m!}.

The right hand side limit evaluates to the same value and thus

lim_{p→∞} \frac{h_{m}(p)}{p^{m}} = \frac{1}{4^{\binom{m}{2}}m!}.  (17)

All that remains is to prove the bounds for (16). We multiply out the product, getting 4^{m−1} terms. The first term is simply 1. There are at most p choices for a_{m}, and at least p − 5m, so summing it over all of them returns a value between p − 5m and p.

Now, consider an arbitrary term out of the remaining 4^{m−1} − 1 terms. It is a product of Legendre symbols of the form ϕ(a_{m} − ta_{i}) and ϕ(a_{i} − ta_{m}). Since the Legendre symbol is multiplicative, we can form a single Legendre symbol, that is, write the term as ϕ(f(a_{m})) where f is a polynomial with coefficients in ℤ/pℤ. We know f has at least one root, and we know that each of the roots of f is either of the form ta_{i} or t^{−1}a_{i} for some i. Also, since t ≠ ±1, ta_{i} ≠ t^{−1}a_{i}, so if f had a repeated root r, we could write r = ta_{i} = t^{−1}a_{j}. However, this implies that a_{j} = t^{2}a_{i} and our summation requires that we choose a_{i} and a_{j} such that this is false. Thus, f has no repeated roots, and this means that it is not congruent modulo p to cg(x)^{2} for any integer c and polynomial g with integer coefficients. Moreover, f has degree at most 2m − 2, so by Weil’s theorem we have

|∑_{a_{m}} ϕ(f(a_{m}))| ≤ (2m − 3)\sqrt{p}.

Note that the above sum includes at most 5m terms that the summations in (16) excludes. Each of these terms is between −1 and 1, so removing them changes the sum by at most 5m. Therefore,

| ∑_{\begin{matrix}a_{m}≢t^{e}a_{i} \\ −2≤e≤2 \end{matrix}} ϕ(f(a_{m}))| ≤ 2m\sqrt{p} + 5m.

This bound holds for each of the 4^{m−1} − 1 terms involving Legendre symbols, so (16) holds.

The other three calculations of lim_{p→∞} k_{m}(·)/p^{m} are analogous. For x and y where x ≢

t^{−2}y, t^{−1}y, y, ty, t^{2}y, we replace (14) with

\frac{3 − ϕ(x − ty) − ϕ(y − tx) − ϕ(x − ty)ϕ(y − tx)}{4} for G_{t}(p)^{c};
\frac{3 + ϕ(x − ty) + ϕ(y − tx) − ϕ(x − ty)ϕ(y − tx)}{4}  for G′_{t}(p);
\frac{(1 − ϕ(x − ty))}{2} \frac{(1 − ϕ(y − tx))}{2} for G′_{t}(p)^{c}.

The calculations follow as above.

We now prove Theorem 3, the result expressing C_{t}(p) in terms of hypergeometric functions.

Proof of Theorem 3. The first step is to once again write our expression for C_{t}(p) as a character sum. No cycle can contain 0 because ϕ(0) = 0, and so 0 has no outgoing edges. So we look at each set of three distinct, non-zero points x, y, and z, and check for a cycle. Also, we may assume that x ≢ ty, y ≢ tz, and z ≢ tx, because if one of these is true, there is no cycle. Note that any such group of x, y, z the expression

(1 + ϕ (x) )(1 + ϕ (y) )(1 + ϕ (z) )(1 + ϕ (x − ty) )(1 + ϕ (y − tz) )(1 + ϕ (z − tx) )

returns 2^{6} if x, y, and z form a cycle, and 0 otherwise. If we sum this over each possible set, we count each cycle three times. Thus

\begin{matrix}3 · 2^{6} · C_{t}(p) = ∑_{z≢0} ∑_{\begin{matrix}y≢0,z, \\ tz \end{matrix}} ∑_{\begin{matrix}x≢0,y, \\ z,ty,t^{−1}z \end{matrix}} & ((1 + ϕ (x) )(1 + ϕ (y) )(1 + ϕ (z) ) \\ ×(1 + ϕ (x − ty) )(1 + ϕ (y − zt) )(1 + ϕ (z − tx) )). \end{matrix}

Since z ≢ 0, xz runs over ℤ/pℤ as x does, and yz runs over ℤ/pℤ as y does, so we can replace x by xz and y by yz. We can pull the (1 + ϕ(z)) term to the very front of the summation. Note that ϕ(z) ≠ 0, and when ϕ(z) = −1 and 1 + ϕ(z) = 0, the whole inner term is multiplied by 0, so its accuracy is irrelevant. Thus, assuming that ϕ(z) = 1 is always true within the inner summations does not change the value of the expression as a whole. Using this fact, we can entirely rid the inner summation of z and write

3 · 2^{6} · C_{t}(p) = c ∑_{z≢0} (1 + ϕ (z) ) = (p − 1)c.

where

c = ∑_{\begin{matrix}y≢0,1, \\ t \end{matrix}} ∑_{\begin{matrix}x≢0,1, \\ t^{−1},y,ty \end{matrix}} (1 + ϕ (x) )(1 + ϕ (y) )(1 + ϕ (y − t) )(1 + ϕ (1 − tx) )(1 + ϕ (x − ty) ).

The 5 values x does not take on are all distinct unless y = t^{−1} or y = t^{−2}. Thus

c = ∑_{\begin{matrix}y≢0,1, \\ t,t^{−1},t^{−2} \end{matrix}} ∑_{x} (1 + ϕ (x) )(1 + ϕ (y) )(1 + ϕ (y − t) )(1 + ϕ (1 − tx) )(1 + ϕ (x − ty) )

+ ∑_{\begin{matrix}x≢0,1 \\ t^{−1} \end{matrix}} (1 + ϕ (x) )(1 + ϕ (t) )(1 + ϕ (1 − tx) )(1 + ϕ (t − t^{3}) )(1 + ϕ (x − 1) )

+ ∑_{\begin{matrix}x≢0,1 \\ t^{−1},t^{−2} \end{matrix}} 2(1 + ϕ (x) )(1 + ϕ (1 − tx) )(1 + ϕ (1 − t^{3}) )(1 + ϕ (x − t^{−1}) )

− ∑_{\begin{matrix}y≢0,t^{−2} \\ t^{−1},1,t \end{matrix}} 2(1 + ϕ (y) )(1 + ϕ (y − t) )(1 + ϕ (−ty) )

− ∑_{\begin{matrix}y≢0,t^{−2} \\ t^{−1},1,t \end{matrix}} 2(1 + ϕ (y) )(1 + ϕ (y − t) )(1 + ϕ (1 − t) )(1 + ϕ (1 − ty) )

− ∑_{\begin{matrix}y≢0,t^{−2} \\ t^{−1},1,t \end{matrix}} (1 + ϕ (y) )(1 + ϕ (y − t) )(1 + ϕ (t) )(1 + ϕ (t^{−1} − ty) )

− ∑_{\begin{matrix}y≢0,t^{−2} \\ t^{−1},1,t \end{matrix}} (1 + ϕ (y) )^{2}(1 + ϕ (y − t) )(1 + ϕ (1 − ty) )(1 + ϕ (y − ty) )

− ∑_{\begin{matrix}y≢0,t^{−2} \\ t^{−1},1,t \end{matrix}} (1 + ϕ (y) )(1 + ϕ (y − t) )(1 + ϕ (ty) )(1 + ϕ (1 − t^{2}y) )

= S_{0} + S_{1} + S_{2} − S_{3} − S_{4} − S_{5} − S_{6} − S_{7},

where S_{i} corresponds to the term in the ith row. Note that since the order of t is greater than three, t ≢ 1, t^{−1}, t^{−2} so there is no double counting.

Now we wish to evaluate these 8 terms. Key to the simplification will be the following trick: if we have an expression of the form (1 + ϕ(α)) · (…), where we know α ≢ 0, then we may assume throughout the (…) that ϕ(α) = 1, because either this will be true, or the entire expression will be multiplied by 0 so it is irrelevant. We will also make use of equations (6) and (7), as well as propositions and outlined in the preliminaries. With these tools it is not difficult to reduce the expressions to closed forms in terms of _{2}F_{1} and 3F_{2} values. From this point on, all equations have been verified as accurate for small primes (less than 200) by direct computer calculations in order to prevent arithmetic errors during the manipulations.

For S_{0}, we pull the two terms involving just y out of the inner summation, and evaluate it. Then we switch the order of summation and solve the inner one. Thus

S_{0} = ∑_{\begin{matrix}y≢0,1, \\ t,t^{−1},t^{−2} \end{matrix}} ∑_{x} (1 + ϕ (x) )(1 + ϕ (y) )(1 + ϕ (y − t) )(1 + ϕ (1 − tx) )(1 + ϕ (x − ty) )

= ∑_{\begin{matrix}y≢0,t^{−2} \\ t^{−1},1,t \end{matrix}} (1 + ϕ (y) )(1 + ϕ (y − t) )(p − 1 − 2ϕ(−t) + ∑_{x} ϕ(x)ϕ(1 − tx)ϕ(x − ty))

= (p − 1 − 2ϕ(−t))(p − 8 − 2ϕ(t) − 2ϕ(1 − t) − 2ϕ(1 − t^{3}) − ϕ(−t) − ϕ(t − t^{3}) − ϕ(1 − t^{2}))

+ p^{2}_{3}F_{2}(t^{3}) + 3 + ϕ(t^{4} − t)p + ϕ(−t) + 2ϕ(−1) + 2ϕ(t^{3} − 1) − p(1 + ϕ (t) )(1 + ϕ (1 − t^{2}) )_{2}F_{1}(t) − 2p(1 + ϕ (1 − t) )_{2}F_{1}(t^{2})

− p(1 + ϕ (t) )_{2}F_{1}(t^{3}).

To evaluate S_{1}, we pull the terms independent of x to the front of the summation. Then since the expression is multiplied by 1 + ϕ(t), we may use the trick mentioned above to assume that ϕ(t) = 1 throughout the rest of the expression. Next, we take the summation over all x and subtract out the specific cases 0, 1, and t^{−1}. Then we multiply out the inside of the summation and evaluate it term by term. This shows that

S_{1} = (1 + ϕ (t) )(1 + ϕ (t − t^{3}) ) ∑_{\begin{matrix}x≢0 \\ t^{−1},1 \end{matrix}} (1 + ϕ (x) )(1 + ϕ (1 − tx) )(1 + ϕ (x − 1) )

= (1 + ϕ (t) )(1 + ϕ (1 − t^{2}) )(p + p_{2}F_{1}(t) − 2ϕ(−1) − 4ϕ(1 − t) − 2ϕ(−t) − 7).

The value of S_{2} is computed by noting that after pulling out a ϕ(−t) from the third term of the summand, it is similar to the second term and so we can pull a (1+ϕ(−t)) to the front using the trick above, and evaluate it in a fashion similar to S_{1}. The resulting expression can be simplified further using the trick mentioned above. Hence

S_{2} = 2(1 + ϕ (1 − t^{3}) ) ∑_{\begin{matrix}x≢0,t^{−2} \\ t^{−1},1 \end{matrix}} (1 + ϕ (x) )(1 + ϕ (1 − tx) )(1 + ϕ(−t)ϕ(1 − tx))

= 2(1 + ϕ (1 − t^{3}) )(1 + ϕ (−t) ) ∑_{\begin{matrix}x≢0,t^{−2} \\ t^{−1},1 \end{matrix}} (1 + ϕ (x) )(1 + ϕ (1 − tx) )

= 2(1 + ϕ (1 − t^{3}) )(1 + ϕ (−t) )(p − 8 − 4ϕ(1 − t) − ϕ(−1)).

We can use a similar trick in the evaluation of S_{3}. This shows that

S_{3} = ∑_{\begin{matrix}y≢0,t^{−2} \\ t^{−1},1,t \end{matrix}} 2(1 + ϕ (y) )(1 + ϕ (y − t) )(1 + ϕ (−ty) )

= 2(1 + ϕ (−t) )(p − 9 − 2ϕ(−1) − 2ϕ(1 − t^{3}) − 2ϕ(1 − t) − ϕ(t^{2} − 1) − ϕ(1 − t^{2})).

The evaluation of S_{4} involves the same manipulations as in S_{1}. These result in

S_{4} = 2(1 + ϕ (1 − t) ) ∑_{\begin{matrix}y≢0,t^{−2} \\ t^{−1},1,t \end{matrix}} (1 + ϕ (y) )(1 + ϕ (y − t) )(1 + ϕ (1 − ty) )

= 2(1 + ϕ (1 − t) ) (p + p_{2}F_{1}(t^{2}) − 15 − 6ϕ(−t) − 2ϕ(t) − 2ϕ(1 + t + t^{2})
−2ϕ(−t − t^{2} − t^{3}) − 2ϕ(1 + t) − 2ϕ(t + t^{2})).

Likewise, we obtain

S_{5} = (1 + ϕ (t) ) ∑_{\begin{matrix}y≢0,t^{−2} \\ t^{−1},1,t \end{matrix}} (1 + ϕ (y) )(1 + ϕ (y − t) )(1 + ϕ (1 − t^{2}y) )

= (1 + ϕ (t) ) (p + p_{2}F_{1}(t^{3}) − 11 − 4ϕ(−1) − 4ϕ(1 − t^{3})
− 4ϕ(1 − t) − 4ϕ(1 + t) − 4ϕ(1 − t^{2})).

To evaluate S_{6}, we simply pull terms to the front and notice a similarity to a previous term. We have

S_{6} = ∑_{\begin{matrix}y≢0,t^{−2} \\ t^{−1},1,t \end{matrix}} (1 + ϕ (y) )(1 + ϕ (y − t) )(1 + ϕ (y) )(1 + ϕ (1 − ty) )(1 + ϕ(y)ϕ(1 − t))

= 2(1 + ϕ (1 − t) ) ∑_{\begin{matrix}y≢0,t^{−2} \\ t^{−1},1,t \end{matrix}} (1 + ϕ (y) )(1 + ϕ (y − t) )(1 + ϕ (1 − ty) )

= S_{4}.

Similarly, we have

S_{7} = (1 + ϕ (t) ) ∑_{\begin{matrix}y≢0,t^{−2} \\ t^{−1},1,t \end{matrix}} (1 + ϕ (y) )(1 + ϕ (y − t) )(1 + ϕ (1 − t^{2}y) )

= S_{5}.

Adding this all up, we get

C_{t}(p) = \frac{(p − 1)}{192}[90 − 3pϕ(t) + 12ϕ(t + t^{2}) + p^{2} − 14p + 48ϕ(−t) + 27ϕ(t) + 62ϕ(1 − t)

+ 6ϕ(1 − t^{3}) + 12ϕ(t − t^{3}) + 12ϕ(1 − t^{2}) + 12ϕ(−1) + 12ϕ(1 + t) + 24ϕ(t^{2} − t) + 6ϕ(t − t^{4}) + 12ϕ(t − t^{2}) + 3ϕ(t^{4} − t)p − 6pϕ(1 − t) − 3ϕ(−t)p + p^{2}_{3}F_{2}(t^{3})

− 6p(1 + ϕ(1 − t))_{2}F_{1}(t^{2}) − 3p(1 + ϕ(t))_{2}F_{1}(t^{3})],

and this is the desired formula.

Proof of Corollaries 1 and 2. We begin by stating two well known facts about quadratic residues. First, ϕ(2) is 1 when p ≡ 1 or 7 (mod 8) and −1 when p ≡ 3 or 5 (mod 8). Second, ϕ(3) is 1 when p = 1 or 11 (mod 12) and is −1 when p ≡ 5 or 7 (mod 12). With these it is simple to show that if p ≡ 5 or 7 (mod 24) and t = −2 or p ≡ 7 or 13 (mod 24) and t = −1/2, then ϕ(t) = ϕ(1 − t) = −1. When these two facts hold, Theorem 3 simplifies to

C_{t}(p) = \frac{p − 1}{192}[p^{2} + p^{2}_{3}F_{2}(t^{3}) − 5p + 3pϕ(−1) (1 + ϕ (1 + t + t^{2})) + 13 − 12ϕ(−1)].

The claims follow from the fact that (see [Ono04], pg. 192) for p ≠ 2, 7 we have

3F_{2}(−8) = \begin{cases}−\frac{1}{p} & if p ≡ 3 (mod 4), \\ \frac{4x^{2}−p}{p^{2}} & if p ≡ 1 (mod 4), x^{2} + y^{2} = p, and x odd, \end{cases}

and that for p ≠ 2, 3 we have

3F_{2} (\frac{−1}{8}) = \begin{cases}−\frac{ϕ(2)}{p} & if p ≡ 3 (mod 4), \\ \frac{ϕ(2)(4x^{2}−p)}{p^{2}} & if p ≡ 1 (mod 4), x^{2} + y^{2} = p, and x odd. \end{cases}

Note that we cannot apply these facts in the single case p = 7 in Corollary 1. However, it is simple to check by hand that the formula still holds in this case.

Acknowledgments. This research was supported by the University of Wisconsin-Madison NSF Vigre REU program. The author would like to thank Ken Ono and Jeremy Rouse for their invaluable guidance. The author would also like to thank Karl Mahlburg for his help in proofreading, Sharon Garthwaite for her patience in helping me to use L^{A}TEX, and the referee for numerous helpful suggestions.

References

[BEW98] Bruce C. Berndt, Ronald J. Evans, and Kenneth S. Williams, Gauss and Jacobi sums, Canadian Mathematical Society Series of Monographs and Advanced Texts, John Wiley & Sons Inc., New York, 1998, A Wiley-Interscience Publication. MR MR1625181 (99d:11092)

[CGW88] F. R. K. Chung, R. L. Graham, and R. M. Wilson, Quasirandom graphs, Proc. Nat. Acad. Sci. U.S.A. 85 (1988), no. 4, 969–970. MR MR928566 (89a:05116)

[EPS81] R. J. Evans, J. R. Pulham, and J. Sheehan, On the number of complete subgraphs contained in certain graphs, J. Combin. Theory Ser. B 30 (1981), no. 3, 364–371. MR MR624553 (83c:05075)

[Erd62] P. Erdős, On the number of complete subgraphs contained in certain graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl. 7 (1962), 459–464. MR MR0151956 (27 #1937)

[Ono04] Ken Ono, The web of modularity: arithmetic of the coefficients of modular forms and q-series, CBMS Regional Conference Series in Mathematics, vol. 102, Published for the Conference Board of the Mathematical Sciences, Washington, DC, 2004. MR MR2020489 (2005c:11053)

[Tho97] Andrew Thomason, Graph products and monochromatic multiplicities, Combinatorica 17 (1997), no. 1, 125–134. MR MR1466580 (99i:05087)