\documentclass[12pt]{article}
\textwidth= 6.5in
\textheight= 9.0in
\topmargin = -20pt
\evensidemargin=0pt
\oddsidemargin=0pt
\headsep=25pt
\parskip=10pt
\font\smallit=cmti10
\font\smalltt=cmtt10
\font\smallrm=cmr9
\usepackage{amsmath,amssymb,amsthm,amscd,url}
\newtheorem{thm}{Theorem}[section]
\theoremstyle{definition}
\newtheorem*{ex}{Example}
\newtheorem{cor}{Corollary}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{conjec}[thm]{Conjecture}
\theoremstyle{remark}
\newtheorem*{rem}{Remark}
\theoremstyle{definition}
\newtheorem{defn}{Definition}[section]
\theoremstyle{definition}
\newtheorem*{ack}{Acknowledgments}
\newtheorem*{thm1}{Theorem 1}
\newtheorem*{thm2}{Theorem 2}
\newtheorem*{thm3}{Theorem 3}
\newtheorem*{cor1}{Corollary 1}
\newtheorem*{cor2}{Corollary 2}
\newtheorem*{prop1}{Proposition 1}
\newtheorem*{prop2}{Proposition 2}
\newtheorem*{Wthm}{Weil's Theorem}
\begin{document}
\vspace*{-40pt}
\centerline{\smalltt INTEGERS:
\smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 6
(2006), \#A18}
\vskip 40pt
\begin{center}
{\bf CHARACTER SUMS AND RAMSEY PROPERTIES OF GENERALIZED PALEY GRAPHS}
\vskip 20pt
{\bf Nicholas Wage}\\
{\smallit Appleton East High School, Appleton, WI 54915, USA}\\
{\tt wageee@gmail.com}\\
\end{center}
\vskip 30pt
\centerline{\smallit Received: 8/23/05, Revised: 5/16/06,
Accepted: 5/26/06,
Published: 6/1/06}
\vskip 30pt
\centerline{\bf Abstract}
\noindent
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.
\pagestyle{myheadings}
\markright{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL
OF COMBINATORIAL NUMBER THEORY \smalltt 6 (2006), \#A18\hfill}
\thispagestyle{empty}
\baselineskip=15pt
\vskip 30pt
%% Macros
\def\C{\mathbb{C}}
\def\Z{\mathbb{Z}}
\def\Q{\mathbb{Q}}
%\def\F{\mathbb{F}}
\def\Gal{{\rm Gal}}
\newcommand{\legen}[2]{\genfrac{(}{)}{}{}{#1}{#2}}
\def\ord{{\rm ord}}
\def\Tr{{\rm Tr}}
\def\d{d}
\def\const{\text{const}}
\def\SL{\textup{SL}}
\newcommand{\ed}[1]{\Big(1+\phi\left(#1\right)\Big)}
%\newcommand{\ed}[1]{(1+\phi(#1))}
\newcommand{\eds}[1]{\left(1+\phi\left(#1\right)\right)}
\newcommand{\su}[3]{\displaystyle\sum_{\substack{#1 \not\equiv #2 \\ #3}}}
\newcommand{\summ}[2]{\displaystyle\sum_{\substack{#1\\#2}}}
\newcommand{\prodd}[2]{\displaystyle\prod_{\substack{#1\\#2}}}
\newcommand{\pbox}[1]{#1\phantom{l^{l^{l}}}}
\def\nq{\not\equiv}
\def\f{{_2}F_1}
\def\F{{_3}F_2}
%\def\begin{equation}{\begin{equation}}
%\def\end{equation}{\end{equation}}
\def\({\left(}
\def\){\right)}
\def\B({\Big(}
\def\B){\Big)}
\renewcommand{\refname}{\normalsize References}
%\author{Nicholas Wage}
%\address{Appleton East High School, 2021 Emmers Drive, Appleton, WI, 54915}
%\email{wageee@gmail.com}
%\title[Properties of Generalized Paley Graphs]{Character sums and Ramsey properties of generalized Paley graphs}
%\date{\today}
%\document
%\centerline{\bf CHARACTER SUMS AND RAMSEY PROPERTIES OF GENERALIZED PALEY GRAPHS}
%\vskip 20pt
%\centerline{\smallit Nicholas Wage \footnote{any footnote here}, Appleton East High School, Appleton, WI 54915}
%\centerline{\tt wage@fas.harvard.edu}
%\vskip 30pt
%\centerline{\smallit Received:, Accepted:, Published}
%\vskip 30pt
%
%
%\centerline{\bf Abstract}
%
%
%\noindent
%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.
%
%\baselineskip=15pt
%\vskip 30pt
%\thanks{This research was supported by the REU component
% of the University of Wisconsin Madison NSF VIGRE program.
%The author is a high school student at Appleton East High
%School in Appleton, Wisconsin.}
%this command below puts section numbers with equations
%\numberwithin{equation}{section}
%\subjclass[2000]{FILL IN CLASSES Primary 11F25; Secondary 11F72.}
%\begin{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.
%\end{abstract}
%\maketitle
%\section{Introduction}
\section*{\normalsize 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
\leq 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
\begin{equation}
T_m(n) := \min(k_m(G)+k_m(G^c))
\end{equation}
as $G$ ranges over all graphs with $n$ vertices.
Note that $R(m)$ is the smallest $n$ for which $T_m(n) > 0$. In
\cite{erd}, Erd\H{o}s conjectured that
\begin{equation}
\displaystyle\lim_{n \rightarrow \infty} \frac{T_m(n)}{n^m} = \frac1{2^{{m \choose 2}-1}m!}.
\end{equation}
However, this is not quite correct. In \cite{thom},
Thomason showed that for $m = 4$, this limit is no more than
$1/(33\cdot4!)$, rather than $1/(32\cdot4!)$ as the conjecture predicts.
For a prime $p \equiv 1 \pmod{4}$, let $G(p)$ denote
the Paley graph with $p$ vertices, indexed $0$ through $p-1$. A Paley
graph contains an edge $x \leftrightarrow y$ if and only if $\phi(x-y) =
1$, where $\phi(\cdot)$ denotes the Legendre symbol
$\left(\frac{\cdot}{p}\right)$. 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 $\phi(-1) = 1$ if $p
\equiv 1 \pmod{4}$. Therefore, $\phi(y-x) = \phi(x-y)$. This equation
implies that our definition is symmetric in $x$ and $y$, so the edges are
well defined.
For primes $p \equiv 3 \pmod{4}$, $\phi(-1) = -1$,
so $\phi(x-y) = -\phi(y-x)$. In this case we define a generalized
directed Paley graph. Note that since $\phi(-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 \cite{EPS} 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$.
\begin{thm1}
\label{asymp}
For primes $p \equiv 1 \pmod{4}$ and positive integers $m$
\[
\lim_{p \rightarrow \infty} \frac{k_m\Big(G(p)\Big)}{p^m} = \frac{1}{2^{{m \choose 2}}m!}.
\]
\end{thm1}
Doubling this value to account for the complete graphs
in its isomorphic complement, we see that the conjecture of Erd\H{o}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 \leftrightarrow y$ if and only if both
$\phi(x-ty) = 1$ and $\phi(y-tx) = 1$. The graph $G_t'(p)$ has an edge
$x \leftrightarrow y$ if and only if at least one of these statements is
true, that is $\phi(x-ty) = 1$ or $\phi(y-tx) = 1$. Note that $G_t(p)$
is a subgraph of $G_t'(p)$.
We now define two related generalized Paley graphs.
\newline
{\bf 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
\leftrightarrow y$ if and only if $\phi(x-ty) = 1$ and $\phi(y-tx) = 1$.
Similarly, let $G_t'(p)$ denote the graph with $p$ vertices, indexed $0$
through $p-1$, which contains an edge $x \leftrightarrow y$ if either
$\phi(x-ty) = 1$ or $\phi(y-tx) = 1$, and contains no edge $x
\leftrightarrow y$ if neither of these statements hold true.
We prove a similar result for these generalized graphs.
\begin{thm2}
\label{asymp2}
Let $m$ be a positive integer and $t$ be an integer such that
$t \nq -1,0,1 \pmod{p}$. Then, for primes $p$, and we have
\[
\lim_{p \rightarrow \infty} \frac{k_m\Big(G_t(p)\Big)
+k_m\Big(G_t(p)^c\Big)}{p^m} =
\frac{1}{m!}\left(\left(\frac{1}{4}\right)^{{m \choose 2}} +
\left(\frac{3}{4}\right)^{{m \choose 2}}\right).
\]
Similarly,
\[
\lim_{p \rightarrow \infty} \frac{k_m\Big(G'_t(p)\Big)
+k_m\Big(G'_t(p)^c\Big)}{p^m} =
\frac{1}{m!}\left(\left(\frac{1}{4}\right)^{{m \choose 2}} +
\left(\frac{3}{4}\right)^{{m \choose 2}}\right).
\]
\end{thm2}
\begin{rem}
After this work was completed, it was brought to the author's
attention that a paper of Graham, Chung, and Wilson, \cite{CGW}, 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.
\end{rem}
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
\begin{equation}
\label{EPSTHM}
k_4\Big(G(p)\Big) = \frac{p-1}{1536}\left(p\left((p-9)^2-4x^2\right)
\right)
\end{equation}
where $x$ is an even integer such that $p = x^2 + y^2$.
It is known that for $p \equiv 1 \pmod{4}$, that $x$ not only exists, but
is unique (up to sign). Their proof essentially follows from an
evaluation of the hypergeometric sum
\begin{equation}
\label{3F2}
\F(t) = \frac{\phi(-1)}{p^2}\sum_{x \in \Z/p\Z}
\sum_{y \in \Z/p\Z} \phi(x)\phi(y)\phi(1-x)\phi(1-y)\phi(x-ty)
\end{equation}
when $t = 1$. One should note that
while it can be shown that this is equivalent to the definition of
$\F(t)$, it is not a priori the definition. Similarly, we will require
the sum
\begin{equation}
\label{2F1}
\f(t) = \frac{\phi(-1)}{p}\sum_{x \in \Z/p\Z} \phi(x)\phi(1-x)\phi(1-tx).
\end{equation}
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.
\begin{thm3}
\label{ucs}
Let $p$ be a prime, and let $t$ be a non-zero element of $\Z/p\Z$ whose multiplicative order is greater than $3$. Let $H_t(p)$ represent the directed graph where $x \to y$ is an edge if and only if $\phi(x) = \phi(x-ty) = 1$, and let $C_t(p)$ denote the number of $3$-cycles in $H_t(p)$ ($x \to y \to z \to x$). Then\footnotesize
\begin{eqnarray*}
C_t(p) &=& \frac{p-1}{192}\Big[90-3p\phi(t)+12\phi(t+t^2)+p^2-14p+48\phi(-t)+27\phi(t)+62\phi(1-t) \\
&&{} + 6\phi(1-t^3) + 12\phi(t-t^3) + 12\phi(1-t^2)+12\phi(-1)+12\phi(1+t)+24\phi(t^2-t) \\
&&{} + 6\phi(t-t^4)+12\phi(t-t^2)+3\phi(t^4-t)p-6p\phi(1-t)-3\phi(-t)p+p^2\F(t^3) \\
&&{} - 6p(1+\phi(1-t))\f(t^2) - 3p(1+\phi(t))\f(t^3)\Big].
\end{eqnarray*}
\normalsize
\end{thm3}
%This seemingly unwieldy formula simplifies dramatically for several special $t$. For example,
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 \eqref{EPSTHM} in the following cases:
\begin{cor1}
\label{special-2}
If $t = -2$, and $p$ is a prime congruent to $5$ or $7 \pmod{24}$, then
\[
C_t(p) =
\begin{cases}
\frac{p-1}{192}\(p^2 - 6p + 4x^2 + 1\)&\quad\text{ if } p \equiv 5 \pmod{24}, x^2+y^2=p \text{, and }x\text{ odd}, \\
\frac{p-1}{192}\(p^2-6p+25\)&\quad\text{ if } p \equiv 7 \pmod{24}.
\end{cases}
\]
\end{cor1}
\begin{cor2}
\label{special-12}
If $t = -\frac12$, and $p$ is a prime congruent to $7$ or $13 \pmod{24}$, then
\[
C_t(p) =
\begin{cases}
\frac{p-1}{192}(p^2-6p+25)&\quad\text{ if } p \equiv 7 \pmod{24}, \\
\frac{p-1}{192}(p^2+2p-4x^2+1)&\quad\text{ if } p \equiv 13 \pmod{24}, x^2+y^2=p \text{, and }x\text{ odd}.
\end{cases}
\]
\end{cor2}
In Section $2$ we state the tools that will be necessary in Section $3$,
where we will prove the main theorems.
\vskip 30pt
\section*{\normalsize 2. Preliminaries}
We will need the following facts for our proofs. The deepest result we require is due to Weil.
\begin{Wthm} (\cite{BEW}, pg. 183)
%% Need page number on this thingy ^ (Page #183).
If $p$ is a prime, and $f(x) \in \Z[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
\[
\left|\sum_{x \in \Z/p\Z} \phi\Big(f(x)\Big)\right| < (n-1)\sqrt{p}.
\]
\end{Wthm}
\begin{rem}
>From this point onward, we omit the summation indices with the understanding that all sums are over $\Z/p\Z$ unless indicated otherwise.
\end{rem}
For small $n$, explicit evaluations of these sums are simple. Clearly, if $n = 0$,
\begin{equation}
\label{0deg}
\sum_x \phi(c) = \phi(c)p.
\end{equation}
Note that as $x$ runs over all the elements of $\Z/p\Z$, so does $ax + b$ if $a \nq 0 \pmod{p}$. Using this fact, we can also compute the value for $n = 1$. Let $q$ denote a non-zero, non-residue of $\Z/p\Z$. Then
\begin{eqnarray*}
\sum_x \phi(ax+b) &=& \sum_{y=ax+b} \phi(y) \\
&=& \sum_{z=q^{-1}y} \phi(qz) \\
&=& \phi(q)\sum_z \phi(z) \\
&=& -\sum_y \phi(y) \\
&=& -\sum_x \phi(ax+b),
\end{eqnarray*}
so
\begin{equation}
\label{1deg}
\sum_x \phi(ax+b) = 0.
\end{equation}
Finally, we prove a formula for the case $n = 2$.
\begin{prop1}
\label{2deg}
For any prime $p$ and polynomial $f(x) = ax^2+bx+c$ with roots $r$ and $s$ is $\Z/p\Z$,
\[
\sum_x \phi(ax^2 + bx + c) =
\begin{cases}
(p-1)\phi(a) &\quad\text{ if } r \equiv s \pmod{p}\\
-\phi(a) &\quad\text{ if } r \nq s \pmod{p}. \\
\end{cases}
\]
\end{prop1}
\begin{proof}
\begin{eqnarray*}
\sum_x \phi(ax^2 + bx + c) &=& \sum_x \phi\Big(a(x-r)(x-s)\Big) \\
&=& \phi(a) \sum_x \phi(x)\phi\Big(x-(s-r)\Big).
\end{eqnarray*}
Let $t = s-r$. Note that when $t \equiv 0 \pmod{p}$, it is clear that $\displaystyle\sum_x \phi(x)^2 = p-1$. When, $t \nq 0 \pmod{p}$,
\[
\sum_x \phi(x) \phi(x-t) = \sum_{tx} \phi(tx)\phi(t(x-1)) = \sum_{x} \phi(x)\phi(x-1),
\]
so the summation is equivalent to the summation when $t \equiv 1 \pmod{p}$. Thus, this is equivalent for all $p-1$ non-zero values of $t$.
Note that
\begin{eqnarray*}
\sum_t \sum_x \phi\Big(x(x-t)\Big) &=& \sum_x \phi(x) \sum_t \phi(x-t) \\
&=& \sum_x \phi(x) \sum_{u = x-t} \phi(u) \\
&=& \sum_x \phi(x)\cdot0 \\
&=& 0.
\end{eqnarray*}
However, we can also show that
\begin{eqnarray*}
\sum_t \sum_x \phi\Big(x(x-t)\Big) &=& \sum_x \phi(x)^2 + (p-1)\sum_x \phi(x)\phi(x-t) \\
&=& (p-1)\(1+\sum_x \phi(x)\phi(x-t)\).
\end{eqnarray*}
Equating these two expressions, we obtain
\[
\phi(a) \sum_x \phi(x)\phi(x-t) = -\phi(a).
\]
\end{proof}
For $n \geq 3$ there does not appear to be a general evaluation. However, with additional machinery, certain evaluations are possible. A character $\chi$ is a multiplicative function that maps the elements of $(\Z/p\Z)^*$ to the complex roots of unity. Let $\bar{\chi}$ denote the conjugate character of $\chi$, that is, $\bar{\chi}(x) = 1/\chi(x)$. By convention, we say that $\chi(0) = 0$. The Legendre symbol is a simple example of a character. Another simple character is $\epsilon$, the trivial character, for which $\epsilon(x) = 1$ unless $x \equiv 0 \pmod{p}$.
A Jacobi sum, for characters $\chi$ and $\psi$ is
\begin{equation}
J(\chi,\psi) := \sum_x \chi(x)\psi(1-x).
\end{equation}
Additionally, we define the normalized Jacobi sum for characters $A$ and $B$
\begin{equation}
{A \choose B} := \frac{B(-1)}{p}J(A,\bar{B}).
\end{equation}
Then, we define
\begin{equation}
{{}_{n+1}F_{n}}\left( \begin{array}{cc}A_0,& A_1, ...A_n\\& B_1, ...B_n\end{array} | t\right)
:= \frac{p}{p-1}\sum_{\chi} {A_0 \chi \choose \chi}{A_1\chi \choose B_1\chi}\cdots{A_n\chi \choose B_n\chi}\chi(t),
\end{equation}
where the sum is over all $\chi$ with modulus $p$. Additionally, we define
\begin{equation}
{{}_{n+1}F_{n}}(t) := {{}_{n+1}F_{n}}\left( \begin{array}{cc} \phi,& \phi, ...\phi\\& \epsilon, ...\epsilon \end{array}| t\right).
\end{equation}
Although these functions are expressed in terms of Jacobi sums, it is known that the definitions in the introduction, \eqref{2F1} and \eqref{3F2}, are equivalent (see \cite{CBMS}).
%Although these equations are expressed as Jacobi sums, it turns out that (see \cite{CBMS})
%\[
%\f(t) = \frac{\phi(-1)}{p}\sum_x \phi(x)\phi(1-x)\phi(1-tx)
%\]
%and
%\[
%\F(t) = \frac{phi(-1)}{p^2}\sum_x \phi(x)\phi(1-x)\phi(y)\phi(1-y)\phi(x-ty).
%\]
These objects allow us to find a general formula in terms of $\f$ when $n = 3$.
\begin{prop2}
\label{3deg}
For any prime $p$ and third-degree polynomial with leading coefficient $a$ and distinct roots $q,r,s \in \Z/p\Z$, we have
\[
\sum_x \phi\Big(a(x-q)(x-r)(x-s)\Big) = \phi(-a)\phi(q-s)\f\left(\frac{r-s}{q-s}\right)p.
\]
\end{prop2}
\begin{proof}
The proof of this is straightforward:
\begin{eqnarray*}
\sum_x \phi\Big(a(x-q)(x-r)(x-s)\Big)% &=& \sum_x \phi\Big(a(x-q)(x-r)(x-s)\Big) \\
%&=& \sum_x \phi\Big(a(x-q)(x-r)(x-s)\Big) \\
&=& \phi(a) \sum_x \phi\Big(x(q-s-x)(r-s-x)\Big) \\
%&=& \phi(a)\phi(r-s) \sum_x \phi(x)\phi\left(x - \frac{q-s}{r-s}\right)\phi(x - 1) \\
&=& \phi(a)\phi(q-s) \sum_{(q-s)x} \phi(x)\phi(1-x)\phi\left(1 - \frac{r-s}{q-s}x\right) \\
&=& \phi(-a)\phi(q-s) \f\left(\frac{r-s}{q-s}\right)p.
\end{eqnarray*}
\end{proof}
\vskip 30pt
\section*{\normalsize 3. Proof of the Theorems}
Using Weil's Theorem from the previous section, we will prove Theorem 1.
\begin{proof}[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 \equiv 1 \pmod{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 $\phi(x - y) = 1$, then assuming $x \neq y$ the equation $\frac{1+\phi(x-y)}{2}$ conveniently returns $1$ if $x \leftrightarrow 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\Big(G(p)\Big) = \sum_{a_1<\dots