\documentclass{amsart}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{geometry}
\geometry{left=2.5cm,right=2.5cm,a4paper}

\newcommand{\Z}{\mathbb{Z}}
\newcommand{\group}[1]{\Z / {#1} \Z}
\newcommand{\ifff}{\mbox { if }}
\newcommand{\qedsquare}{\hspace{\fill} \qedsymbol{}}
\newtheorem{lemma}{Lemma}
\newtheorem{theorem}{Theorem}

\vfuzz2pt % Don't report over-full v-boxes if over-edge is small
\hfuzz2pt % Don't report over-full h-boxes if over-edge is small

\title{Gauss Sums}
\author{Allan Lind Jensen}

\begin{document}
\maketitle

\section*{for Neil Koblitz: Introduction to Elliptic Curves and Modular Forms,
Chapter 4, Section 2}

\section*{Definitions and first results}
\noindent Let $n > 0$ be an odd integer. The Gauss sums are defined by
\begin{equation}
	S(n) = \sum_{j=1}^n \left( \frac{j}{n} \right) e^{2 \pi i j /n} ~.
\end{equation}
I will soon be proven, that is $n$ fails to be square-free, then $S(n) = 0$. Otherwise,
\begin{theorem}
	(Gauss) When $n$ is a square-free odd integer
	\begin{equation} \label{eq-Gauss}
		S(n) = \varepsilon_n \sqrt{n} ,
	\end{equation}
	where
	\begin{equation}
		\varepsilon_n = \left\lbrace 
			\begin{array}{ccl}
				1 & \mbox{if} & n \equiv 1 \mod 4 \\
				i & \mbox{if} & n \equiv 3 \mod 4
			\end{array} \right.
	\end{equation}
\end{theorem}

\medskip \noindent We need the more general sum
\begin{equation}
	S(n,l) = \sum_{j=1}^n \left( \frac{j}{n} \right) e^{2 \pi i l j/n} 
		= \sum_{j \in ~\group{n}} \left( \frac{j}{n} \right) e^{2 \pi i l j/n}.
\end{equation}

\medskip \noindent If $(l,n) = 1$, then the map $x \mapsto l x$ is $1-1$ in $\group{n}$. Thus
\begin{equation} \label{eq-Snl}
	S(n,l) = \left( \frac{l}{n} \right) \sum_{j \in ~\group{n}} \left( \frac{ l j}{n} \right) e^{2 \pi i l j/n}
		= \left( \frac{l}{n} \right) S(n,1) ~,
\end{equation}
or more generally, still assuming $(n,l)=1$
\begin{equation} \label{eq-Sn-al}
	S(n,l a) = \left( \frac{l}{n} \right) S(n,a) ~.
\end{equation}

To find the values of the Gauss sums for general $n$, we first reduce to prime powers.

\begin{theorem}
	Assume that $m$ and $n$ are coprime, $(m,n) = 1$. Then
	\begin{equation}
		S(m n,l) = \left( \frac{m}{n} \right) \left( \frac{n}{m} \right) S(m,l) S(n,l)
	\end{equation}
\end{theorem}

The idea of the proof is to parametrize $j = h m + k n$, where $h \in \group{n}$ and
$k \in \group{m}$. This works, because the map
$$ j \mapsto (j \bmod n, j \bmod m) \mapsto 
	(m^{-1} \bmod n, k^{-1} \bmod m) \times (j \bmod n, j \bmod m) $$
is $1-1$. The first is $1-1$ by the Chinese remainder theorem, the second, because $m \in (\group{n})^\times$
and vice versa.
\begin{eqnarray} \nonumber
	S(m n, l) & = & \sum_{j \in \group{m n}} \left( \frac{j}{m n} \right) e^{2 \pi i l j/ m n} \\
	\nonumber & = & \sum_{h \in \group{n}} \sum_{k \in \group{m}} 
		\left( \frac{h m + k n}{m} \right)  \left( \frac{h m + k n}{n} \right)
		e^{2 \pi i l (h m + k n)/ m n} \\
	\nonumber & = & \sum_{h,k} \left( \frac{k n}{m} \right)  \left( \frac{h m}{n} \right)
		e^{2 \pi i l h/n} e^{2 \pi i l k/m} \\
	\nonumber & = & \left( \frac{n}{m} \right) \left( \frac{m}{n} \right)
		\sum_h \left( \frac{h}{n} \right) e^{2 \pi i l h/n}
		\sum_k \left( \frac{k}{m} \right) e^{2 \pi i l k/m}
\end{eqnarray} \qedsquare

You can probably see, how this in conjuction with (\ref{eq-Gauss}) implies the quadratic
reciprocity theorem. Following this line of thought leads to
\begin{theorem}
	Let $m, n > 0$ be odd, positive integers, that are mutually prime. Then
	\begin{equation}
		S(m n,l) = \frac{S(m,l)}{\varepsilon_m} \cdot \frac{S(n,l)}{\varepsilon_n} \cdot
		\varepsilon_{m n} ~.
	\end{equation}
\end{theorem}

\section*{Prime powers}
\noindent Now, We are ready to work on $S(p^\nu,l)$. The case $\nu = 1$ is covered by
(\ref{eq-Snl}), which remains true even if $p | l$. In that case,
$S(p,l) = \sum_j \left( \frac{j}{p} \right) \cdot 1 = 0$.

Assume that $\nu \ge 2$. We parametrize $j = a p + b$, where
$0 \le a < p^{\nu-1}$ and $1 \le b \le p$, and compute
\begin{eqnarray} \nonumber
	S(p^\nu,l) & = & \sum_{a = 0}^{p^{\nu-1}-1} \sum_{b=1}^p \left( \frac{a p + b}{p} \right)^\nu
		e^{2 \pi i l a/p^{\nu-1}} e^{2 \pi i l b/p^\nu}	\\
	\nonumber & = & \sum_{a = 0}^{p^{\nu-1}-1} e^{2 \pi i l a/p^{\nu-1}}
		\sum_{b=1}^p \left( \frac{b}{p} \right)^\nu e^{2 \pi i l b/p^\nu} ,
\end{eqnarray}
Unless $p^{\nu-1} | l$, the first sum vanishes; if $p^{\nu-1} \nmid l$, then
$e^{2 \pi i l/p^{\nu-1}}$ is a non-trivial root of unity, and we sum over a number of full circles.

We have established,
\begin{equation} \label{eq-n-square}
	\mbox{If } \nu \ge 2 \mbox{ and } p^{\nu-1} \nmid l \mbox{, then } G(p^\nu,l) = 0 ~.
\end{equation}
As a special case $S(p^2) = S(p^2,1) = 0$, which implies that $S(n) = 0$,
if $n$ is divisible by an integral square.

Finally, write $l = \lambda p^{\nu-1}$, obtaining
$$ S(p^\nu, \lambda p^{n-1}) = \sum_{a=1}^{p^{\nu-1}} 1^{a \lambda} 
		\sum_{b=1}^p \left( \frac{b}{p} \right)^\nu e^{2 \pi i \lambda b/p} ~.$$

There is the special case $p | \lambda$, and we must distinguish between even and odd values of $\nu$.
The inner sum yields
\medskip \begin{center}
$\begin{array}{ccc}
	\sum_{b=1}^p \left( \frac{b}{p} \right)^\nu e^{2 \pi i \lambda b/p} & p|\lambda & p \nmid \lambda \\
	\hline
	2|\nu			& 	p - 1	&	-1 \\
	2 \nmid	\nu	& 	0		&	S(p,\lambda)
\end{array}$
\end{center}

\medskip \noindent and the Gauss sum of prime powers becomes
\medskip \begin{center}
\begin{equation} \label{eq-prime-power}
	\begin{array}{ccc}
		S(p^\nu , \lambda p^{\nu-1})	&	p|\lambda		&	p \nmid \lambda \\ \hline
		2|\nu						&	p^\nu - p^{\nu-1}	&	-p^{\nu-1} \\
		2 \nmid \nu					&	0					&	p^{\nu - 1} S(p,\lambda)
	\end{array}
\end{equation}
\end{center}
It turns out, that (\ref{eq-prime-power}) also holds for $\nu = 1$.

\section*{The Gauss sums needed in the book}

\noindent From now on, $n$ and $n_i$ represent odd integers.

The formula (\ref{eq-prime-power} can be reformulated the following way
\begin{equation} \label{eq-primpower-even}
	S(p^h,p^{2 \nu}) = \left\lbrace \begin{array}{ccc}
		0 					& \ifff 	& h > 2 \nu + 1 \\
		p^{2 \nu} S(p,1)	& \ifff		& h = 2 \nu + 1	\\
		0					& \ifff		& 0 < h < 2 \nu, \mbox{ odd} \\
		p^{h-1} \cdot (p-1)		& \ifff		& 0 < h \leq 2 \nu, \mbox{ even} \\
		1					& \ifff		& h = 0
	\end{array} \right.
\end{equation}
and
\begin{equation} \label{eq-primepower-odd}
	S(p^h,p^{2 \nu - 1}) = \left\lbrace \begin{array}{ccc}
		0					& \ifff 	& h > 2 \nu \\
		-p^{2 \nu - 1}		& \ifff		& h = 2 \nu	\\
		0					& \ifff		& 0 < h \leq 2 \nu -1, \mbox{ odd} \\
		p^{h-1} \cdot (p-1)	& \ifff		& 0 < h \leq 2 \nu -1, \mbox{ even} \\
		1					& \ifff		& h = 0
	\end{array} \right.
\end{equation}

\begin{lemma}
	(p. 188-9) If $l$ is squarefree, write $n= n_0 n_1^2$, where $n_0$ is squarefree. Then
	\begin{equation} \label{eq-l-squarefree}
		S(n,l) = \left\lbrace \begin{array}{cl}
			\varepsilon_n \left( \frac{l}{n_0} \right) \mu(n_1) \sqrt{n} & \ifff ~n_1 | l \\
			0	& \mbox{ otherwise,}
		\end{array} \right.
	\end{equation}
	where $\mu$ is the Möbius function.
\end{lemma}

Write $n_1 = \prod p_i^{\nu_i}$. Then
$$ S(n,l) \varepsilon_n^{-1}= S(n_0,l) \varepsilon_{n_0}^{-1}
	\prod S(p_i^{2 \nu_i},l) \varepsilon_{p_i^{2 \nu_i}}^{-1} ~.$$
Of course, $\varepsilon_{p_i^{2 \nu_i}} = 1$ and $\varepsilon_{n_0 n_1^2} = \varepsilon_{n_0}$.

If some $p_i \nmid l$ then $S(p_i^{2 \nu_i},l) = 0$. Since $l$ is squarefree, it also vanishes if
$\nu_i \ge 2$ It also vanishes, if $p_i | n_0$, but in that case $\left( \frac{l}{n_0} \right) = 0$.

In case $n_1 | l$, and no prime $p_i | n_0$, we apply $ S(p_i^2,l) = -p_i$, obtaining
$$S(n,l) = \left( \frac{l}{n_0} \right) \sqrt{n_0} ~\varepsilon_n \prod \left( -p_i \right) =
	\left( \frac{l}{n_0} \right) \varepsilon_n \sqrt{n_0} ~\mu(n_1) n_1 ~.$$
\qedsquare
\vfill

\section*{Computation of $b_{l_0 p^{2 \nu}} / b_{l_0}$}

\medskip \noindent The final challenge is to derive the expressions for $b_{l_0 p^{2 \nu}}/b_{l_0}$,
where $p \nmid l_0$ or $p || l_0$.

The easy case is $p = 2$. For odd $n$, formula (\ref{eq-Sn-al}) results in
\begin{equation}
	S(l_0 2^{2 \nu}) = \left( \frac{2^{2 \nu}}{n} \right) S(n,1_0) =
	\left( \frac{2^{\nu}}{n} \right)^2 S(n,1_0) = S(n,l_0) ~,
\end{equation}
Thus
$$ b_{l_0 4^\nu} = C \cdot l_0^{k/2 - 1} 2^{(k - 2) \nu} \sum_n \varepsilon_n n^{-k/2} S(n, -l_0)
	= 2^{(k - 2) \nu} b_{l_0}$$

\subsection*{The case: Odd $p || l_0$} \hfill

\medskip Write $l_0 = \tilde{l}_0 p$, so that $l = \tilde{l}_0 p^{2 \nu + 1}$, allowing $\nu = 0$.
In (2.7) we write $n = n_0 p^h$, where $p \nmid n_0$, so that
\begin{eqnarray}
	\nonumber b_{\tilde{l}_0 p^{2 \nu + 1}} & = &
	C \left(\tilde{l}_0 p^{2 \nu + 1} \right)^{\frac{k}{2} - 1} \sum_n \varepsilon_n^k 
		n^{-\frac{k}{2}} S(n,-l) \\
	\nonumber & = &
	C l_0^{\frac{k}{2} - 1} p^{\nu \cdot(ki-2)} \sum_{n_0, h} \varepsilon_{n_0 p^h}^k
		n_0^{-\frac{k}{2}} p^{-\frac{h k}{2}} S(n_0 p^h, -\tilde{l}_0 p^{2 \nu + 1}) \\
	\nonumber & = &
	C l_0^{\frac{k}{2} - 1} p^{\nu \cdot(ki-2)} \sum_{n_0, h} \varepsilon_{n_0 p^h}^{k+1}
		n_0^{-\frac{k}{2}}  p^{-\frac{h k}{2}} S(n_0, -\tilde{l}_0 p^{2 \nu + 1})
		S(p^h , -\tilde{l}_0 p^{2 \nu + 1}) \varepsilon_{p^h}^{-1} \varepsilon_{n_0}^{-1} \\
	\nonumber & = &
	C l_0^{\frac{k}{2} - 1} p^{\nu \cdot(ki-2)} \sum_{n_0} \left( \frac{p}{n_0} \right)
		\varepsilon_{n_0}^{-1} n_0^{-\frac{k}{2}} S(n_0,-\tilde{l}_0) \sum_h 
		\varepsilon_{n_0 p^h}^{k+1} \varepsilon_{p^h}^{-1} 
		p^{-\frac{h k}{2}} \left( \frac{-\tilde{l}_0}{p} \right)^h S(p^h, h^{2 \nu + 1})
\end{eqnarray}
The value of $S(p^h, h^{2 \nu + 1})$ is only non-zero, when $h$ is even. Thus
\begin{eqnarray}
	\nonumber b_{\tilde{l}_0 p^{2 \nu + 1}} & = &
	C l_0^{\frac{k}{2} - 1} p^{\nu \cdot(ki-2)} \sum_{p \nmid n} \left( \frac{p}{n} \right)
		\varepsilon_{n}^k n^{-\frac{k}{2}} \sum_h p^\frac{h k}{2} S(p^h, p^{2 \nu + 1}) \\
	\nonumber & = &
	C l_0^{\frac{k}{2} - 1} p^{\nu \cdot(ki-2)} \sum_{p \nmid n} \left( \frac{p}{n} \right)
		\varepsilon_{n}^k n^{-\frac{k}{2}} \cdot \left(
		1 + \sum_{j=1}^\nu p^{-k j} \cdot (p^{2 j} - p^{2 j -1}) + p^{-k(\nu + 1}(-p^{2\nu + 1})
		\right)
\end{eqnarray}
The parenthesis can be reduced to
$$ \sum_{j=0}^\nu p^{(2-k) j} - \sum_{j=1}^{\nu+1} p^{(2-k) j - 1} =
	p^{\nu \cdot(ki-2)} \left( 1 - p^{1-k} \right) \sum_{j=0}^\nu p^{(2-k)j} ~. $$
Finally, we obtain
\begin{equation}
	\frac{b_{l_0 p^{2\nu}}}{b_{l_0}} = p^{\nu \cdot(ki-2)} \sum_{j=0}^\nu p^{(2-k) j} =
	\sum_{j=0}^\nu p^{(k - 2)j} ~,
\end{equation}
which is the formula just above (2.24).
\newpage

\subsection*{The case: Odd $p \nmid l_0$} \hfill

\medskip We compute
\begin{eqnarray}
	\nonumber b_{l_0 p^{2 \nu}} & = & 
	C \left( l_0 p^{2 \nu} \right)^{\frac{k}{2}-1} \sum_{n_0,h} \varepsilon_{n_0 p^h}^k 
		(n_0 p^h)^{-\frac{k}{2}} S(n_0 p^h,-l_0 p^{2 \nu}) \\
	\nonumber & = &
	C l_0^{\frac{k}{2}-1} p^{(k-2) \nu} \sum_{n_0,h} \varepsilon_{n_0 p^h}^{k + 1}
		n_0^{-\frac{k}{2}} p^{-\frac{h k}{2}} S(n_0,-l_0 p^{2 \nu}) S(p^h,-l_0 p^{2 \nu})
		\varepsilon_{n_0}^{-1} \varepsilon_{p^h}^{-1} \\
	\nonumber & = &
	C l_0^{\frac{k}{2}-1} p^{(k-2) \nu} \sum_{n_0} \varepsilon_{n_0}^{-1}
		n_0^{-\frac{k}{2}} S(n_0,-l_0) \sum_h
		\varepsilon_{n_0 p^h}^{k + 1} p^{-\frac{h k}{2}} 
		\left( \frac{-l_0}{p} \right)^h S(p^h,p^{2 \nu}) \varepsilon_{p^h}^{-1}
\end{eqnarray}

There is only \textit{one} odd value of $h$ for which $S(p^h,p^{2 \nu}) \neq 0$, i.e. $h = 2\nu + 1$.
In the evaluation of this term we need the observation, that since $k+1$ is even, 
and $\lambda = \frac{k-1}{2}$, we can apply $\varepsilon_n^2 = \left(\frac{-1}{n}\right)$ to obtain
$$\varepsilon_{p n}^{k+1} = \left(\frac{-1}{p n}\right)^{\lambda+1} = 
	\left(\frac{-1}{p}\right)^{\lambda+1} \left(\frac{-1}{n}\right)^{\lambda+1} =
	\left(\frac{-1}{p}\right)^{\lambda+1}  \cdot \varepsilon_n^{k+1} ~.$$
The odd addend of the sum gives
$$ \varepsilon_{n_0 p}^{k + 1} p^{-k \nu - \frac{k}{2}}
	\left( \frac{-l_0}{p} \right) p^{2 \nu} \varepsilon_p \sqrt{p} \varepsilon_p^{-1} =
	\left( \frac{-1}{p} \right)^{\lambda+1} \varepsilon_{n_0}^{k+1} \left( \frac{-l_0}{p} \right)
	p^{-(k - 2) \nu - \lambda} = \varepsilon_{n_0}^{k+1} \chi(p) p^{-(k - 2) \nu - \lambda} ~. $$
where $\chi = \chi_{(-)^\lambda l_0}$. 
Including the even values leads to
\begin{equation}
	b_{\tilde{l}_0 p^{2 \nu}} = C l_0^{\frac{k}{2} - 1} p^{\nu \cdot(k-2)} \sum_{p \nmid n}
	\varepsilon_{n_0}^k n^{-\frac{k}{2}} S(n_0, -l_0) \left(
		1 + \chi(p) p^{-(k - 2) \nu - \lambda} + \sum_{j=1}^\nu p^{-k j} \left(p^{2 j} - p^{2 j - 1} \right) 
	\right)
\end{equation}
This is basically (2.28). We obtain
\begin{eqnarray}
	\nonumber \frac{b_{\tilde{l}_0 p^{2 \nu}}}{b_{\tilde{l}_0}} & = &
		\frac{p^{(k-2)\nu} \left(
		1 + \chi(p) p^{-\lambda} + \sum_{j=1}^\nu \left(p^{(2-k) j} - p^{(2-k) j - 1} \right) 
		\right)}{1 + \chi(p) p^{-\lambda}} \\
	\nonumber & = &
		\frac{\sum_{j=0}^\nu p^{(k-2)j} - \sum_{j=0}^{\nu - 1} p^{(k-2) j - 1} +
		\chi(p) p^{-\lambda}}{1 + \chi(p) p^{-\lambda}} \\
	\nonumber & = &
		\sum_{j = 0}^\nu p^{(k-2) j} - \chi(p) p^{\lambda - 1} \sum_{j = 0}^{\nu - 1} p^{(k-2) j}
\end{eqnarray}
The verification of the last expression is elementary, but not trivial. One needs 
the relation $k = 2 \lambda +1$.

\end{document}
