\documentclass[12pt]{amsart}
\usepackage{amsmath, amsthm, amssymb, amsfonts}
\usepackage{enumerate}
\usepackage{verbatim}
%\numberwithin{equation}{section}

%%%Document Configuration
\pagestyle{headings}
%\addtolength{\topmargin}{-.5in}
\textwidth = 6in 
\oddsidemargin = .25in
\evensidemargin = .25in
\voffset = -1in
\textheight = 9.5 in
%\textwidth = 6in
%\parindent = 0in
%\headsep = 0in
\relpenalty = 9999
\binoppenalty = 9999
%linespacing
\renewcommand{\baselinestretch}{1.25}
\reversemarginpar     
%%%

%%%Theorem Configuration
\theoremstyle{plain}
\newtheorem*{main}{Main~Theorem}
\newtheorem{thm}{Theorem}[section]
\newtheorem*{thm*}{Theorem}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{exer}[thm]{Exercise}
\newtheorem{fact}[thm]{Fact}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{remark}[thm]{Remark}
\newtheorem{hw}[section]{}
%\newtheorem{hw}[section]{HW}
\newtheorem{dfn}{Definition}[section]
\newtheorem*{dfn*}{Definition}
%%%

%%%Bibliography Configuration
\bibliographystyle{plain}
%%%

%%%semantic definitions
\DeclareMathOperator*{\Aut}{Aut}
\DeclareMathOperator*{\Dom}{Dom}
\DeclareMathOperator*{\rnd}{Round}
\renewcommand{\div}{\mid}
\renewcommand{\emptyset}{\varnothing}
\renewcommand{\implies}{\Rightarrow}
\renewcommand{\natural}{\mathbb{N}}
\newcommand{\Acl}[1]{\obar{#1}}
\newcommand{\assign}{\leftarrow}
\newcommand{\ceil}[1]{\lceil{#1}\rceil}
\newcommand{\complex}{\mathbb{C}}
\newcommand{\field}{\mathbb{F}}
\newcommand{\floor}[1]{\lfloor{#1}\rfloor}
\newcommand{\integer}{\mathbb{Z}}
\newcommand{\intersect}{\cap}
\newcommand{\isomorphic}{\simeq}
\newcommand{\minus}{\setminus}
\newcommand{\nonnegative}{\mathbb{N}}
\newcommand{\obar}[1]{\overline{#1}}
\newcommand{\power}[1]{{\mathcal{P}}({#1})}
\newcommand{\rational}{\mathbb{Q}}
\newcommand{\real}{\mathbb{R}}
\newcommand{\sst}{{\big|}} %not semantic, but used for \set, \setBig
\newcommand{\sstBig}{{\Big|}}
\newcommand{\set}[2]{\left\{#1 \sst #2 \right\}}
\newcommand{\setBig}[2]{\left\{#1 \sstBig #2 \right\}}
\newcommand{\union}{\cup}
\newcommand{\units}[1]{{\left(#1\right)}^{\times}}
%%%

%%%local definitions
\newcommand{\bd}{\partial}
\newcommand{\e}{\epsilon}
\newcommand{\gspan}[1]{{\langle{#1}\rangle}}
\newcommand{\ka}{\kappa}
\newcommand{\Los}{{\L o\'s}}
\newcommand{\LS}{{L\"{o}wenheim-Skolem }}
\newcommand{\mathscr}[1]{{\mathcal{#1}}}
\newcommand{\monster}{{\mathbb{M}}}
\newcommand{\symAnd}{\mathop{\bigwedge}}
\newcommand{\symand}{\wedge}
\newcommand{\symimply}{\rightarrow}
\newcommand{\symiff}{\leftrightarrow}
\newcommand{\symnot}{\neg}
\newcommand{\symor}{\vee}
\newcommand{\tuple}[1]{\obar{#1}}
\newcommand{\0}{\textbf{0}}
\newcommand{\suc}{\textbf{S}}
\newcommand{\A}{\mathfrak{A}}
\newcommand{\B}{\mathfrak{B}}
\newcommand{\D}{\mathcal{D}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\NNN}{\mathfrak{N}}
\newcommand{\E}{\textbf{E}}
\newcommand{\res}{\upharpoonright}
%%%

\begin{document}

\title{Arithmetic Combinatorics Homework 2}
\author{Dakota Blair}
\maketitle

\noindent Let $e(x) = e^{2 \pi i x}$.

\begin{comment}
\begin{dfn*}[Kloosterman Sums]
A Kloosterman sum is a value of the form
\[
K(m,n,c) = \sum_{dd^{-1}_{(c)} \equiv 1 \bmod c}e\left(\frac{md + nd^{-1}_{(c)}}{c}\right)
\]
where $a, b, m$ and $n$ are integers such that $(m,n) = 1$
and $0 \leq d < c$.
\end{dfn*}

\begin{thm*}[Weil Bound]
\[
\label{wb}
\tag{WB}
|K(m,n,p)|
\leq 2 \sqrt{p}
\]
\end{thm*}

\begin{hw}
Let $c_1, c_2 \in \integer$.
\begin{enumerate}[(i)]
\item If $(c_1, c_2)$
then
\[
K(u,v,c_1c_2) = K(u,v{c_2}^{-2}_{(c_1)},c_1) = K(u,v{c_1}^{-2}_{(c_2)},c_2).
\]

\item For $k \geq 2$ and a prime $p$
\[
|K(v,v,p^k)| \leq 2p^{k/2}
\]

\item Combining these with (\ref{wb}), show that for fixed $m$
\[
|K(m,n,c)| = O_\e(c^{1/n + \e}).
\]
\end{enumerate}
\end{hw}

\begin{proof}
\end{proof}

\begin{dfn*}[$\nu_q$]
Let $q \in \integer$ and $S(q) = $. Then
\[
\nu_q(x) = \frac{1}{q-1} \sum_{y \in S(q)} \delta_x(y)
\]
where $\delta_x(y) = 1 $ if $y = x$ and $0$ otherwise.
\end{dfn*}

\begin{hw}
Show that
\[
\tag{*}
\label{hw2}
\frac{1}{q-1} K(a, b, q) = \nu_q(a,b).
\]
\end{hw}

\begin{proof}
\[
asdf
\]
\end{proof}
\end{comment}

\begin{thm*}[Weyl Criterion]
A sequence $\{a_n\}_{n \in \natural}$ is uniformly distributed
if and only if
for all nonzero $b \in \integer$
\[
\lim_{N \to \infty} \frac{1}{N}\sum_{n = 0}^{N-1} e(b a_n) = 0
\]
\end{thm*}

\begin{comment}
\begin{hw}
Let $\S(f) = \sup \set{ x \in T^2}{|f(x)| + |\partial_{xx}f(x)| + |\partial_{yy}f(x)| }$.
Show that (\ref{wb}), the Weyl criterion and (\ref{hw2}) implies
\[
|\nu_q(f) - \int_{T^2} f d\mu | \leq q^{-\ka} \S(f).
\]
\end{hw}
\end{comment}
\setcounter{section}{3}

\begin{hw}
Show the following:
\begin{enumerate}[(i)]
\item $|\sin \pi t| \leq \pi |t - \rnd(t)|$,
\item $|e(t) - 1| \leq 2 \pi |t - \rnd(t)|$.
\end{enumerate}
\end{hw}

\begin{proof}
Note that when $|t| < 1/2, \rnd(t)$ = 0
and $x^n < x^{n+1}$ when $x < 1$.
Thus if $|t| < 1/2$ then
\begin{align*}
|\sin \pi t |
& = |\pi t - (\pi t)^2 + (\pi t)^3 - \cdots|
  \leq |\pi t - (\pi t)^3 + (\pi t)^3 - \cdots| \\
|\sin \pi t |
& \leq \pi |t| = \pi |t - \rnd(t)|.
\end{align*}
Further $|\sin \pi t|$ is concave down and therefore
is less than $\pi |t - \rnd(t)|$ for $0 \leq t \leq \frac{\pi}{2}$.
Both functions are even about $t = \frac{\pi}{2}$
hence this inequality holds for all $t$.

Moreover,
\begin{align*}
|e(t) - 1|
 & = |\cos 2 \pi t - i \sin 2 \pi t - 1|
   = \left((\cos 2 \pi t - 1)^2 + \sin(2\pi t)^2)\right)^{1/2}\\
 & = \left(\cos^2 2\pi t  + \sin^2 2 \pi t + 1 - 2 \cos 2 \pi t\right)^{1/2}\\
 & = (2 - 2\cos \pi t)^{1/2} = \sqrt{2} \sin \pi t \leq 2\pi|t - \rnd(t)|\\
|e(t) - 1|
 & \leq 2\pi|t - \rnd(t)|.
\end{align*}

\end{proof}

\begin{hw}
Show that if $a_n = \alpha n + \beta$
then
\[
\sum_{n \leq N} e(b a_n) = e(b \beta) \sum_{n \leq N} e(b a_n)
 = e(b(\alpha + \beta)) \frac{e(b \alpha N) - 1}{e(b \alpha) - 1}.
\]
Further
\[
\left| \sum_{n \leq N} e(b a_n) \right|
\leq \frac{2}{e(b\alpha) - 1} = O_b(N)
\]
and hence $\{\alpha n + \beta | n \geq 1 \}$ is uniformly distributed modulo 1.
\end{hw}
\begin{proof}
Note that
\begin{align*}
\sum_{n \leq N} e(b a_n)
 & = \sum_{n \leq N} e(b\beta + b\alpha n)
   = \sum_{n \leq N} e(b\beta)e(b\alpha n)\\
 & = e(b \beta) \sum_{n \leq N} e(b \alpha n) \hspace{1 pc}
     \text{which is a geometric series with sum}\\
 & = e(b(\alpha + \beta)) \frac{e(b\alpha N) - 1}{e(b\alpha) - 1}.
\end{align*}
Then by the Weyl Criterion $a_n$ is uniformly distributed modulo 1 as
\[
\left| e(b(\alpha + \beta)) \frac{e(b\alpha N) - 1}{e(b\alpha) - 1}\right|
\leq \left|1 \cdot \frac{1 + 1}{e(b\alpha)-1}\right| = O_b(N).
\]
\end{proof}
\end{document}
