\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*{\im}{\Im}
\DeclareMathOperator*{\re}{\Re}
\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{\primes}{\mathbb{P}}
\newcommand{\rational}{\mathbb{Q}}
\newcommand{\real}{\mathbb{R}}
\newcommand{\rsphere}{\hat{\mathbb{C}}}
\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{\uhp}{\mathbb{H}}
\newcommand{\union}{\cup}
\newcommand{\units}[1]{{\left(#1\right)}^{\times}}
%%%

%%%local definitions
\newcommand{\bd}{\partial}
\newcommand{\e}{\epsilon}
\newcommand{\eqand}{\hspace{1pc}\text{and}\hspace{1pc}}
\newcommand{\gspan}[1]{{\langle{#1}\rangle}}
\newcommand{\ka}{\kappa}
\newcommand{\lle}{\ll_\epsilon}
\newcommand{\Los}{{\L o\'s}}
\newcommand{\LS}{{L\"{o}wenheim-Skolem }}
\newcommand{\sltwo}[4]{{\left(\begin{array}{cc}#1 & #2\\#3 & #4\end{array}\right)}}
\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}
\author{Dakota Blair}
\maketitle

\noindent  Let $\primes$ be the set of primes and for $p \in \primes$ let $\nu_p(n)$ be the $p$-adic valuation of $n$.

\section*{Homework 21}

\begin{hw}
Show $d(n) \lle n^\e$.
\end{hw}
\begin{proof}
\begin{comment}
For $\e > 0$ define $f_{\e}(n) = n^{-\e}d(n)$
Then
\[
f(p^m)
    = \frac{m+1}{p^{m \e}}
 \leq \frac{2m}{p^{m \e}}
    = \frac{2}{p^{m \e}}\frac{\log p^m}{\log p}
 \leq \frac{2}{\log 2}\frac{\log p^m}{p^{m \e}}.
\]
The final expression approaches $0$
as $m$ approaches infinity.
Thus $\displaystyle \lim_{n \to \infty} f(n) = 0$.
\end{comment}
Define $\nu(n) = \left|\set{p \in \primes}{p \div n}\right|$
and let $a_{\max} = \max_{p \in \primes} \nu_p(n)$ and
$p_0 \in \primes$ such that $\nu_{p_0}(n) = a_{\max}$.
A positive integer $n$ may be written as
\[
n = \prod_{p \in \primes} p^{\nu_p(n)}
\]
therefore
\[
d(n) = \sum_{d \div n} 1 = \prod_{p \in \primes} (\nu_p(n) + 1) < (a_{\max}+1)^{\nu(n)}.
\]
Further for any $p \in \primes$
\[
\nu_p(n) \leq \log_p(n) \leq \log_2(n)
\]
so $\nu_p(n) + 1 \lle \log_2(n)$.
From this $a_{\max} + 1 = \nu_{p_0}(n) + 1 \lle \log_2(n)$ hence
\[
d(n) < (a_{\max} + 1)^{\nu(n)} \lle (\log_2 n)^{\nu(n)} \lle n^\e
\]
and consequently
\[
d(n) \lle n^\e.
\]
\end{proof}
\pagebreak
\begin{hw}
Prove the fundamental domain of the modular group is
\[
D = \left\{z \left|
  |z| > 1 \text{ and } -\frac{1}{2} \leq \re(z) < \frac{1}{2} \text{ or }
  |z| = 1 \text{ and } \frac{\pi}{2} \leq \arg z \leq \pi \right\}\right.
\]
\end{hw}

\begin{proof}
Note that $D$ tiles the plane, that is $\Gamma D = \uhp.$
Define
\[
S = \sltwo{0}{-1}{1}{0}
\eqand
T = \sltwo{1}{1}{0}{1}
\]
Let $G' = \gspan{S, T}$ and $z \in \uhp$.
Let $g' = \sltwo{a}{b}{c}{d}$. Note that
\[
\im(g'z) = \frac{\Im(z)}{|cz + d|^2}
\]
and since $c, d \in \integer$ it is the case that
$|\set{(c, d)}{|cz+d|<A}|$ is finite.
Thus there exists a $g \in G'$ such that $\im(gz)$ is a maximum.
Choose $n$ such that $\re(T^n gz) \in (-\frac{1}{2},\frac{1}{2})$.
Then $z' = T^n gz \in D$.

Further this cover partitions the space,
that is if $\gamma_1, \gamma_2 \in \Gamma$ then $\gamma_1 D \neq \gamma_2 D$.
If $|z'| < 1$ then $\im(sz') > \im z'$ which contradicts our choice of $z'$.

\end{proof}
%%%

\section*{Homework 23}
\begin{lem}
\label{lem1}
If $f(n)$ is multiplicative then
\[
\sum_{n = 1}^\infty \frac{f(n)}{n^{-x}} = \prod_{p \in \primes} (1 + f(p)p^{-x} + f(p^2)p^{-2x} + \cdots )
\]
\end{lem}

\begin{lem}
\label{lem2}
Let $a_n$ and $b_n$ be two sequences then
\[
\left(\sum_{n=1}^\infty \frac{a_n}{n^s}\right)
\left(\sum_{n=1}^\infty \frac{b_n}{n^s}\right)
=
\sum_{n=1}^\infty \frac{\sum_{d \div n} a_d b_{\frac{n}{d}}}{n^s}
\]
\end{lem}

\begin{hw}
\[
\frac{1}{\zeta(s)} = \prod_{p \in \primes} (1 - p^{-s}) = \sum_{m=1}^\infty \frac{\mu(m)}{m^s}
\]
\end{hw}
\begin{proof}
From Lemma \ref{lem1} we see that
\begin{align*}
\sum_{m=1}^\infty \frac{\mu(m)}{m^s}
& = \prod_{p \in \primes} (1 + \mu(p)p^{-s} + \mu(p^2)p^{-2s} + \mu(p^3)p^{-3s} + \cdots ) \\
& = \prod_{p \in \primes} (1 + -p^{-s} + 0 p^{-2s} + 0 p^{-3s} + \cdots )\\
\sum_{m=1}^\infty \frac{\mu(m)}{m^s}
& = \prod_{p \in \primes} (1 - p^{-s}) = \frac{1}{\zeta(s)}
\end{align*}
\end{proof}

\begin{hw}
Let $\delta(m) = [m=1]$.
\[
\delta(m) = \sum_{d \div m} \mu(d)
\]
\end{hw}
\begin{proof}
From Lemma \ref{lem2} we see that
\[
\sum_{n=1}^\infty \frac{\delta(n)}{n^s}
= 1 = \zeta(s) \frac{1}{\zeta(s)} =
\left(\sum_{n=1}^\infty \frac{1}{n^s}\right)
\left(\sum_{n=1}^\infty \frac{\mu(n)}{n^s}\right)
= \sum_{n=1}^\infty \frac{\sum_{d \div n} \mu(d)}{n^s}
\]
and hence the assertion.
\end{proof}

\begin{hw}
\label{mob-inv}
For all $f, g : \natural \to \complex$
\[
\tag{3}
g(n) = \sum_{d \div n} f(d)
 \iff
f(n) = \sum_{d \div n} \mu(d) g\left(\frac{n}{d}\right)
\]
\end{hw}
\begin{proof}
Let 
\[
F(s) = \left(\sum_{n=1}^\infty \frac{f(s)}{n^s}\right)
\eqand
G(s) = \left(\sum_{n=1}^\infty \frac{1}{n^s}\right).
\]
Then by Lemma \ref{lem2}
\[
F(s)\zeta(s)
= \left(\sum_{n=1}^\infty \frac{f(n)}{n^s}\right)
  \left(\sum_{n=1}^\infty \frac{1}{n^s}\right)
= \sum_{n=1}^\infty \frac{\sum_{d \div n} f(d)}{n^s}
= \sum_{n=1}^\infty \frac{g(n)}{n^s}
= G(s)
\]
therefore, again by Lemma \ref{lem2},
\[
F(s) = \frac{1}{\zeta(s)}G(s)
= \left(\sum_{n=1}^\infty \frac{\mu(n)}{n^s}\right)
  \left(\sum_{n=1}^\infty \frac{g(n)}{n^s}\right)
= \sum_{n=1}^\infty \frac{
    \sum_{d \div n} \mu(d)g\left(\frac{n}{d}\right)
  }{n^s}
= \sum_{n=1}^\infty \frac{f(n)}{n^s}
.
\]
Hence
\[
g(n) = \sum_{d \div n} f(d)
 \iff
f(n) = \sum_{d \div n} \mu(d) g\left(\frac{n}{d}\right).
\]
\end{proof}

\begin{hw}
Let $\Lambda(n) = [\exists (p, \alpha) n = p^\alpha]\log p$,
\begin{align*}
  \log n
 & = \sum_{d \div n} \Lambda(d)\\
  \Lambda(n)
 & = \sum_{d \div n} \mu(d)\log \frac{n}{d}
   = -\sum_{d \div n} \mu(d) \log d\\
\end{align*}
\end{hw}
\begin{proof}
Note that $\log 1 = \Lambda(1) = 0$.
If $n > 1$ then
\[
n = \prod_{p \in \primes}p^{\nu_p(n)}
\]
therefore
\[
\log n = \sum_{p \in \primes} \nu_p(n) \log p
= \sum_{p \in \primes} \nu_p(n) \Lambda(p)
= \sum_{p \in \primes} \sum_{p^i \div n} \Lambda(p)
= \sum_{d \div n} \Lambda(d)
\]
hence by M\"{o}bius inversion (\ref{mob-inv})
\[
\Lambda(n)
 = \sum_{d \div n} \mu(d)\log \frac{n}{d}
 = -\sum_{d \div n} \mu(d) \log d.\\
\]
\end{proof}


%%%
\section*{Homework 24}

\begin{hw}
Prove that for four pairwise tangent circles
their respective curvatures are related by
\[
2(a_1^2 + a_2^2 + a_3^2 + a_4^2) = (a_1 + a_2 + a_3 + a_4)^2.
\]
\end{hw}
\begin{proof}
Let the circles be centered at $x_i$,
with radii $r_i$ and curvature $a_i$.
Without losing generality let $x_1 = (0,0)$.
Let $c_i$ be the vectors connecting $x_1$ to $x_i$.
This results in $3$ nonzero vectors in $\real^2$
therefore they are linearly dependent, that is
\[
\det((x_i x_j)) =
\left|
\begin{array}{ccc}
x_2 \cdot x_2 &
x_2 \cdot x_3 &
x_2 \cdot x_4 \\
x_3 \cdot x_2 &
x_3 \cdot x_3 &
x_3 \cdot x_4 \\
x_4 \cdot x_2 &
x_4 \cdot x_3 &
x_4 \cdot x_4
\end{array}
\right| = 0.
\]
But
\[
\det((x_i x_j)) =
\frac{4}{a_1 a_2 a_3 a_4}\left(
 \left(\sum a_i\right)^2 - 2\sum a_i^2 \right) = 0
\]
which is true if and only if
\[
\left(\sum a_i\right)^2 = 2\sum a_i^2
\]
as was claimed.
\end{proof}

\end{document}
