%
%
%
% The following slideshow was used in a presentation to the Analysis Seminar at Missouri S&T 24 Februrary 2012
%
% Title: Sketch of Dirichlet's Theorem on Arithmetic Progressions
% Speaker: Tom Cuchta
% Abstract: In 1737, Euler proved that there were infintely many primes by showing that the sum of the reciprocals of primes diverges. Legendre conjectured that given relatively prime integers h and k, that there are infinitely many primes in the progression hn+k, n=1,2,3,... In 1837, Dirichlet proved that statement in a way analogous to Euler's divergence proof. In this presentation, we sketch Tom Apostol's version of the proof.
%
%
% Copyright (C) 2012 Tom Cuchta
%
% This is free sourcecode: you can redistribute it and/or modify it under
% the terms of the GNU Public License, version 2 as published by the Free
% Software Foundation. This code is distributed in the hope that it will 
% be useful, but WITHOUT ANY WARRANTY; without even the implied warranty 
% of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU 
% General Public License for more details.
%
% To see a copy of this license, see <http://www.gnu.org/licenses/>.
%
%
% This file was modified from the template whose copyright appears below.
%
% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Copyright 2004 by Till Tantau <tantau@users.sourceforge.net>.
%
% In principle, this file can be redistributed and/or modified under
% the terms of the GNU Public License, version 2.
%
% However, this file is supposed to be a template to be modified
% for your own needs. For this reason, if you use this file as a
% template and not specifically distribute it as part of a another
% package/program, I grant the extra permission to freely copy and
% modify this file as you see fit and even to delete this copyright
% notice. 
 
% $Header$
\documentclass{beamer}

\usepackage{amssymb}
\usepackage{color}
\usepackage{graphicx}
\usepackage{subfig}
\usepackage{mathrsfs}
\usepackage{amsfonts,amsmath,amssymb,amsthm}
\usepackage{times}
\usepackage[T1]{fontenc}
\usepackage[english]{babel}
\usepackage[latin1]{inputenc}

\mode<presentation>
{
  \usetheme{Warsaw}
  \setbeamercovered{transparent}
}

\title[Dirichlet's Theorem] % (optional, use only with long paper titles)
{Sketch of Dirichlet's Theorem on Arithmetic Progressions}

\author[] % (optional, use only with lots of authors)
{Tom Cuchta}
% - Use the \inst{?} command only if the authors have different
%   affiliation.

\date[] % (optional)
{24 February 2012 / Analysis Seminar, Missouri S\&T}

\subject{Talks}
% This is only inserted into the PDF information catalog. Can be left
% out. 

% Delete this, if you do not want the table of contents to pop up at
% the beginning of each subsection:
\AtBeginSubsection[]
{
  \begin{frame}<beamer>{Outline}
    \tableofcontents[currentsection,currentsubsection]
  \end{frame}
}


% If you wish to uncover everything in a step-wise fashion, uncomment
% the following command: 

%\beamerdefaultoverlayspecification{<+->}


\begin{document}

\begin{frame}
  \titlepage
\end{frame}

\begin{frame}{Outline}
  \tableofcontents
  % You might wish to add the option [pausesections]
\end{frame}

\section{Introduction and Definitions}

%
%% introduce the theorem
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\textbf{Dirichlet's theorem:} Let $h$ and $k$ be relatively prime positive integers. Then there are infintiely prime numbers in the set

$$\{kn+h \colon n \in \mathbb{Z}^+ \}.$$

For example, if $h=2$ and $k=3$, we are focusing on these red numbers:

$$\{ {\color{red}5}, 8, {\color{red} 11}, 14, {\color{red} 17}, 20, {\color{red} 23}, 26, \ldots \},$$

and if $h=23$ and $k=10$, we are focusing on these red numbers:

$$\{ {\color{red} 33}, 56, {\color{red}79}, 102, 125, 148, 171, 194, 217, 240, {\color{red}263}, \ldots  \}.$$

We will prove prove this theorem by demonstrating

$$\displaystyle\sum_{p \equiv h(mod \hspace{3pt} k)} \frac{\log p}{p} = \infty.$$
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%
%% Euler's proof
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\textbf{Theorem (Euler):} $\displaystyle\sum_p \frac{1}{p} = \infty$

\textbf{Proof:} For $\Re(s) > 1$, $\zeta(s) = \displaystyle\sum_{n=1}^{\infty} \frac{1}{n^s} = \displaystyle\prod_p \frac{1}{1-p^{-s}}$, so

$$\log \zeta(s) = - \displaystyle\sum_p \log(1-p^{-s}).$$

\textit{Taylor series:} $-\log(1-x)= x + \mathscr{O}(x^2)$ for $x$ near $0$; so for $s > 1$ near $1$,

$$\log(\zeta(s)) = \displaystyle\sum_p ( p^{-s} + \mathscr{O}(p^{-2s})) = \displaystyle\sum_p \frac{1}{p^s} + \mathscr{O}(1),$$

since

$$\displaystyle\sum_p \frac{1}{p^{2s}} \leq \displaystyle\sum_p \left| \frac{1}{p^{2s}} \right| = \displaystyle\sum_p \frac{1}{p^{2 \Re(s)}} \leq \displaystyle\sum_{n=1}^{\infty} \frac{1}{n^{2 \Re(s)}}.$$

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%
%% Euler's proof
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\textbf{Theorem (Euler):} $\displaystyle\sum_p \frac{1}{p} = \infty$

\textbf{Proof:}Let $s \rightarrow 1^+$:

$$\displaystyle\lim_{s \rightarrow 1^+} \log(\zeta(s)) = \displaystyle\lim_{s \rightarrow 1^+} \displaystyle\sum_p \frac{1}{p^s} + \mathscr{O}(1),$$

and the result is

$$\begin{array}{ll}
\infty &= \displaystyle\lim_{s \rightarrow 1^+} \displaystyle\sum_p \frac{1}{p^s} + \mathscr{O}(1) \\
&= \displaystyle\sum_p \frac{1}{p} + \mathscr{O}(1), 
\end{array}$$

since $\zeta(1)$ is the harmonic series, which diverges. $\blacksquare$
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%
%% Unit group
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Define $U(k)$ to be the group of integer units modulo $k$ under multiplication; for example 

$$U(7) = \{1,2,\ldots,6\} \simeq \mathbb{Z}_7,$$ 

$$U(12) = \{1,5,7,11\} \simeq \mathbb{Z}_4,$$

$$U(20) = \{1,3,7,9,11,13,17,19\} \simeq \mathbb{Z}_8.$$ 

\hspace{1pt} \\

It is well known that the cardinality of $U(k)$ is given by the Euler totient function

$$\phi(k) = \displaystyle\sum_{n \leq k; (n,k)=1} 1,$$

where $(n,k)$ indicates $n$ is relatively prime to $k$.
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%
%% Other groups
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
We denote the $\mathbb{Z}/q\mathbb{Z}$ to be the integers modulo $q$. \\

\hspace{1pt} \\

It is well known that the $n$th roots of unity form a multiplicative subgroup of $\mathbb{C}$ of cardinality $n$. We will denote the set of $n$th roots of unity as $R(n)$. 

\hspace{1pt} \\

A homomorphism $\chi \colon U(k) \rightarrow R(k)$ is called a character mod $k$. It is well known that there are $\phi(k)$ characters mod $k$.

\hspace{1pt} \\

We label the characters mod $k$ as

$$\{\chi_1, \chi_2, \ldots, \chi_{\phi(k)} \},$$

with $\chi_1$ called the principal character, which sends all elements of $U(q)$ to $1$ (all other characters are considered nonprincipal).
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%
%% Characters of U(k)
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Let $\hat{U}(k)$ denote the group of all $\phi(k)$ characters mod $k$ under the operation 

$$\chi_a \chi_b (\cdot) = \chi_a(\cdot) \chi_b(\cdot).$$

Define $L^2(U(k))$ to be the set of complex-valued functions on $U(k)$ with respect to the inner product

$$<f,g> = \frac{1}{\phi(k)} \displaystyle\sum_{m \in U(k)} f(m) \overline{g(m)}.$$

It is well-known that $\hat{U}(k)$ is an orthonormal basis of $L^2(U(k))$. Recall that $h$ is relatively prime to $k$ and define the characteristic function $\delta_h$

$$\delta_{h}(a) = \left\{ \begin{array}{ll} 
1 & \colon a \equiv h \mod k \\ 
0 & \colon otherwise 
\end{array} \right. .$$
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%
%% Characters of U(k)
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Now define

$$\begin{array}{ll} 
\hat{\delta_h}(\chi) &= < \delta_h , \chi > \\ 
&= \frac{1}{\phi(k)} \displaystyle\sum_{a \in G} \delta_{h}(a) \overline{\chi(a)} \\ 
&= \frac{1}{\phi(k)} \overline{\chi(h)}.
\end{array}$$

The following representation for $\delta_h$ is well known:

$$\delta_{h}(a) = \displaystyle\sum_{r=1}^{\phi_k} \hat{\delta_h}(\chi_r) \chi_r(a) = \frac{1}{\phi(k)} \displaystyle\sum_{r=1}^{\phi(k)} \overline{\chi_r(h)} \chi_r(a).$$
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%
%% Dirichlet Characters
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
We now trivially extend all characters $\chi_r$ mod $k$ to $\chi_r \colon \mathbb{Z}/k\mathbb{Z} \rightarrow R(k) \cup \{0\}$ by the following formula:

$$\chi_r(a) = \left\{ \begin{array}{ll} 
\chi_r(a) &\colon a \in U(k) \\ 
0 &\colon a \in \mathbb{Z}/k \mathbb{Z} \setminus U(k) 
\end{array} \right. .$$

\hspace{1pt} \\

Such an extended character is called a Dirichlet character mod $k$, and we label them $\{\chi_1, \ldots, \chi_{\phi(k)}\}$.
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%
%% Dirichlet series
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
A Dirichlet series is a generalization of the Riemann zeta function. Define a Dirichlet series $L_{\chi}$ by the formula, for $\Re(s) > 1$, 

$$L_{\chi}(s) = \displaystyle\sum_{n=1}^{\infty} \frac{\chi(n)}{n^s}.$$

\textit{Note that $\zeta(s) = L_{\chi_1}(s)$.} \\

\hspace{1pt} \\

It turns out that Dirichlet's theorem boils down to proving that $L_{\chi}(1) \neq 0$ for any nonprincipal character $\chi$ mod $k$.
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Some estimates}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
The Dirichlet product of $f$ and $g$ is defined to be $f*g$ and has formula

$$(f*g)(n) = \displaystyle\sum_{d | n} f(d) g \left( \frac{n}{d} \right).$$

Let $F$ be a complex-valued function which is defined on $(0, \infty)$ with $F(x)=0$ for $0 < x < 1$. The general convolution of $F$ and an arithmetic function $f$ is defined to be

$$(f \circ F)(x) = \displaystyle\sum_{n \leq x} f(n) F \left( \frac{x}{n} \right).$$

With a little algebra, can show for arithmetical functions $f$ and $g$, that

$$f \circ (g \circ F) = (f * g) \circ F.$$
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\textbf{Theorem:} If $h = f*g$, let

$$H(x) = \displaystyle\sum_{n \leq x} h(n), F(x) = \displaystyle\sum_{n \leq x} f(n), \textrm{\hspace{3pt} and \hspace{3pt}} G(x) = \displaystyle\sum_{n \leq x} g(n).$$

Then,

$$H(x) = \displaystyle\sum_{n \leq x} f(n) G \left( \frac{x}{n} \right) = \displaystyle\sum_{n \leq x} g(n) F \left( \frac{x}{n} \right).$$
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\textbf{Theorem:} $H(x) = \displaystyle\sum_{n \leq x} f(n) G \left( \frac{x}{n} \right) = \displaystyle\sum_{n \leq x} g(n) F \left( \frac{x}{n} \right).$

\textbf{Proof:} Define $U(x) = \left\{ \begin{array}{ll}
0 & \colon 0 < x < 1 \\
1 & \colon x \geq 1
\end{array} \right.$. Then, 

$$F(x) = \displaystyle\sum_{n \leq x} f(n) = \displaystyle\sum_{n \leq x} f(n) U \left( \frac{n}{x} \right) = (f \circ U)(x),$$

and similarly, $G = g \circ U$. So,

$$\displaystyle\sum_{n \leq x} g(n) F \left( \frac{x}{n} \right) = g \circ F = g \circ (f \circ U ) = (g * f) \circ U = H,$$

$$\displaystyle\sum_{n \leq x} f(n) G \left( \frac{x}{n} \right) = f \circ G = f \circ (g \circ U) = (f * g) \circ U = H. \blacksquare$$
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\textbf{Theorem:} $H(x) = \displaystyle\sum_{n \leq x} f(n) G \left( \frac{x}{n} \right) = \displaystyle\sum_{n \leq x} g(n) F \left( \frac{x}{n} \right).$

\hspace{1pt} \\

If we set $g(n)=1$ for all $n$, then $G(x) = [x]$. The theorem yields the following corollary:

\hspace{1pt} \\

\textbf{Corollary:} If $F(x) = \displaystyle\sum_{n \leq x} f(n)$, then

$$\begin{array}{ll}
\displaystyle\sum_{n \leq x} \displaystyle\sum_{d | n} f(d) &= \displaystyle\sum_{n \leq x} (f*g)(n) \\
&=  H(x) \\
&= \displaystyle\sum_{n \leq x} f(n) \left[ \frac{x}{n} \right] \\
&= \displaystyle\sum_{n \leq x} F \left( \frac{x}{n} \right). \blacksquare
\end{array}$$
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\textbf{Euler Summation formula:} if $f$ has continuous derivative $f'$ on the interval $[y,x],$ where $0 < y < x$, then

$$\displaystyle\sum_{y < n \leq x} f(n) = \displaystyle\int_y^x f(t) dt + \displaystyle\int_y^x (t - [t])f'(t) dt + f(x)([x]-x) - f(y)([y]-y).$$

Define the Mangoldt function 

$$\Lambda(n) = \left\{ \begin{array}{ll}
\log p & \colon n=p^m, p \textrm{\hspace{3pt} prime,} m \geq 1 \\
0& \colon \mathrm{otherwise}.
\end{array} \right.$$

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\textbf{Corollary:} $\displaystyle\sum_{n \leq x} \displaystyle\sum_{d | n} f(d) = \displaystyle\sum_{n \leq x} f(n) \left[ \frac{x}{n} \right] = \displaystyle\sum_{n \leq x} F \left( \frac{x}{n} \right).$

\hspace{1 pt} \\

\textbf{Theorem:} For $x \geq 1$ we have 

$$\displaystyle\sum_{n \leq x} \Lambda(n) \left[ \frac{x}{n} \right] = \log [x]!.$$

\textbf{Proof:} Use fundamental theorem of arithmetic to represent any $n$ as $n = \displaystyle\prod_{i=1}^k p_i^{e_i}$. Apply the corollary with $f(n) = \Lambda(n)$:

$$\displaystyle\sum_{n \leq x} \Lambda(n) \left[ \frac{x}{n} \right] = \displaystyle\sum_{n \leq x} \displaystyle\sum_{d | n} \Lambda(d) = \displaystyle\sum_{n \leq x} \left[ \displaystyle\sum_{i=1}^k e_i \log(p_i) \right] = \displaystyle\sum_{n \leq x} \log(n).$$

So $$\displaystyle\sum_{n \leq x} \Lambda(n) \left[ \frac{x}{n} \right] = \log([x]!). \blacksquare$$
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\textbf{Theorem:} If $x \geq 2$, we have 
$$\log([x]!) = x \log x + \mathscr{O}(x),$$ 
and hence
$$\displaystyle\sum_{n \leq x} \Lambda(n) \left[ \frac{x}{n} \right] = x \log x + \mathscr{O}(x).$$

\textbf{Proof:} Realize that $\displaystyle\int_1^x \frac{t-[t]}{t} dt = \mathscr{O}(\log x)$. Take $f(t) = \log t$ and apply Euler's summation formula to get 

$$\begin{array}{ll}
\hspace{-10pt} \log([x]!) = \displaystyle\sum_{1 < n \leq x} \log n &= \displaystyle\int_1^x \log t dt + \displaystyle\int_1^x \frac{t - [t]}{t} dt + ([x] - x) \log x \\
&= x \log x - x + 1 + \mathscr{O}(\log x) \\
&= x \log x + \mathscr{O}(x). \blacksquare
\end{array}$$
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\textbf{Theorem:} $\displaystyle\sum_{p \leq x} \left[ \frac{x}{p} \right] \log p = x \log x + \mathscr{O}(x)$

\textbf{Proof:} Since $\Lambda(n)=0$ unless $n = p^m$, we have

$$\displaystyle\sum_{n \leq x} \left[ \frac{x}{n} \right] \Lambda(n) = \displaystyle\sum_p \displaystyle\sum_{m=1}^{\infty} \left[ \frac{x}{p^m} \right] \Lambda(p^m) = \displaystyle\sum_p \displaystyle\sum_{m=1}^{\infty} \left[ \frac{x}{p^m} \right] \log p,$$

so since $p^m \leq x \rightarrow p \leq x$ and $\left[ \frac{x}{p^m} \right] = 0$ if $p > x$, we get

$$\displaystyle\sum_p \displaystyle\sum_{m=1}^{\infty} \left[ \frac{x}{p^m} \right] \log p = \displaystyle\sum_{p \leq x} \left[ \frac{x}{p} \right] \log p + \displaystyle\sum_{p \leq x} \displaystyle\sum_{m=2}^{\infty} \left[ \frac{x}{p^m} \right] \log p.$$

So,

$$\displaystyle\sum_{n \leq x} \left[ \frac{x}{n} \right] \Lambda(n) = \displaystyle\sum_{p \leq x} \left[ \frac{x}{p} \right] \log p + {\color{red} \displaystyle\sum_{p \leq x} \displaystyle\sum_{m=2}^{\infty} \left[ \frac{x}{p^m} \right] \log p}$$

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\textbf{Theorem:} $\displaystyle\sum_{p \leq x} \left[ \frac{x}{p} \right] \log p = x \log x + \mathscr{O}(x)$

Now the second term in the RHS is $\mathscr{O}(x)$:

$$\begin{array}{ll}
\displaystyle\sum_{p \leq x} \displaystyle\sum_{m=2}^{\infty} \left[ \frac{x}{p^m} \right] \log p &\leq \displaystyle\sum_{p \leq x} \log p \displaystyle\sum_{m = 2}^{\infty} \frac{x}{p^m} \\
&= x \displaystyle\sum_{p \leq x} \log p \displaystyle\sum_{m = 2}^{\infty} \left( \frac{1}{p} \right)^m \\
&= x \displaystyle\sum_{p \leq x} \log p \left( \frac{\frac{1}{p^2}}{1-\frac{1}{p}} \right) \\
&= x \displaystyle\sum_{p \leq x} \log p \left( \frac{1}{p(p-1)} \right) \\
&\leq x \displaystyle\sum_{n=1}^{\infty} \frac{\log n}{n(n-1)} = \mathscr{O}(x)
\end{array}$$
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\textbf{Theorem:} $\displaystyle\sum_{p \leq x} \left[ \frac{x}{p} \right] \log p = x \log x + \mathscr{O}(x)$

Now we have 

$$\begin{array}{ll}
\displaystyle\sum_{n \leq x} \left[ \frac{x}{n} \right] \Lambda(n) &= \displaystyle\sum_{p \leq x} \left[ \frac{x}{p} \right] \log p + {\color{red} \displaystyle\sum_{p \leq x} \displaystyle\sum_{m=2}^{\infty} \left[ \frac{x}{p^m} \right] \log p} \\
&= \displaystyle\sum_{p \leq x} \left[ \frac{x}{p} \right] \log p + \mathscr{O}(x).
\end{array}$$

From earlier, we know 

$$\displaystyle\sum_{n \leq x} \Lambda(n) \left[ \frac{x}{n} \right] = x \log x + \mathscr{O}(x).$$
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\textbf{Theorem:} $\displaystyle\sum_{p \leq x} \left[ \frac{x}{p} \right] \log p = x \log x + \mathscr{O}(x)$

Combining the formulas

$$\left\{ \begin{array}{l}
\displaystyle\sum_{n \leq x} \left[ \frac{x}{n} \right] \Lambda(n) = \displaystyle\sum_{p \leq x} \left[ \frac{x}{p} \right] \log p + \mathscr{O}(x) \\
\displaystyle\sum_{n \leq x} \left[ \frac{x}{n} \right] \Lambda(n) = x \log x + \mathscr{O}(x), \\
\end{array} \right.$$

implies

$$\displaystyle\sum_{p \leq x} \left[ \frac{x}{p} \right] \log p + \mathscr{O}(x) = x \log x + \mathscr{O}(x),$$

in other words

$$\displaystyle\sum_{p \leq x} \left[ \frac{x}{p} \right] \log p = x \log x + \mathscr{O}(x). \blacksquare$$

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\textbf{Shapiro's Tauberian Theorem:} Let $\{a(n)\}$ be a nonnegative sequence such that $\displaystyle\sum_{n \leq x} \left[ \frac{x}{n} \right] a(n) = x \log x + \mathscr{O}(x),$ for all $x \geq 1$. Then for $x \geq 1$ we have

$$\displaystyle\sum_{n \leq x} \frac{a(n)}{n} = \log x + \mathscr{O}(1).$$


If $n$ is prime, define $\Lambda_1(n) = \log p$. Otherwise, define $\Lambda_1(n)=0$. With this notation, we can write the theorem in the previous slide as

\textbf{Theorem (previous slide):} $\displaystyle\sum_{n \leq x} \left[ \frac{x}{n} \right] \Lambda_1(n) = x \log x + \mathscr{O}(x).$

Applying Shapiro's tauberian theorem to this yields


$$\displaystyle\sum_{p \leq x} \frac{\log p}{p} = \displaystyle\sum_{n \leq x} \frac{\Lambda_1(n)}{n} = \log x + \mathscr{O}(1).$$
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The Proof Sketch}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%% Sufficient to prove (*) to prove Dirichlet's theorem
%
\begin{frame}
To prove Dirichlet's theorem,

$$\displaystyle\sum_{p \equiv h(mod \hspace{3pt} k)} \frac{\log p}{p} = \infty,$$

it is sufficient to prove 

$$\displaystyle\sum_{p \leq x; p \equiv h(mod \hspace{3pt} k)} \frac{\log p}{p} = \frac{1}{\phi(k)} \log x + \mathscr{O}(1) \hspace{35pt} (*)$$

and then take the limit as $x \rightarrow \infty$, because that would yield

$$\displaystyle\lim_{x \rightarrow \infty} \displaystyle\sum_{p \leq x; p \equiv h(mod \hspace{3pt} k)} \frac{\log p}{p} = \displaystyle\lim_{x \rightarrow \infty} \frac{1}{\phi(k)} \log x + \mathscr{O}(1) = \infty.$$
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%
%% Setup for Lemma 7.4
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Now we can use our representation for $\delta_h$ and write 

$$\begin{array}{ll}
\hspace{-10pt} \displaystyle\sum_{p \leq x; p \equiv h(mod \hspace{3pt} k)} \frac{\log p}{p} &= \displaystyle\sum_{p \leq x} \frac{\delta_h(p) \log p}{p} \\
&= \displaystyle\sum_{p \leq x} \frac{\left( \frac{1}{\phi(k)} \displaystyle\sum_{r=1}^{\phi(k)} \overline{\chi_r(h)} \chi_r(p) \right) \log p}{p} \\
&= \frac{1}{\phi(k)} \displaystyle\sum_{r=1}^{\phi(k)} \overline{\chi_r(h)} \displaystyle\sum_{p \leq x} \frac{\chi_r(p) \log p}{p} \\
&= \frac{1}{\phi(k)} \displaystyle\sum_{p \leq x} \frac{\log p}{p} + \frac{1}{\phi(k)} \displaystyle\sum_{r=2}^{\phi(k)} \overline{\chi_r(h)} \displaystyle\sum_{p \leq x} \frac{\chi_r(p) \log p}{p}.
\end{array}$$
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%
%% Lemma 7.4 --> (*)
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
From earlier, we know

$$\displaystyle\sum_{p \leq x} \frac{\log p}{p} = \log x + \mathscr{O}(1),$$

so the previous slide yields

$$\displaystyle\sum_{p \leq x; p \equiv h(mod \hspace{3pt} k)} \frac{\log p}{p} = \log x + \frac{1}{\phi(k)} \displaystyle\sum_{r=2}^{\phi(k)} \overline{\chi_r(h)} \displaystyle\sum_{p \leq x} \frac{\chi_r(p) \log p}{p} + \mathscr{O}(1).$$

If we can prove 

$$\frac{1}{\phi(k)} \displaystyle\sum_{r=2}^{\phi(k)} \overline{\chi_r(h)} \displaystyle\sum_{p \leq x} \frac{\chi_r(p) \log p}{p}$$

remains bounded, then Dirichlet's theorem would follow by taking the limit as $x \rightarrow \infty$.
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%
%% 
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
By a technical lemma, 
$$\begin{array}{ll}
& \frac{1}{\phi(k)} \displaystyle\sum_{r=2}^{\phi(k)} \overline{\chi_r(h)}{\color{purple} \displaystyle\sum_{p \leq x} \frac{\chi_r(p)\log p}{p} } + \mathscr{O}(1) \\

=& \frac{1}{\phi(k)} \displaystyle\sum_{r=2}^{\phi(k)} \overline{\chi_r(h)}
{\color{red} \left[ {\color{blue} \left( \displaystyle\sum_{n=1}^{\infty} \frac{\chi_r(n) \log(n)}{n} \right)} \left( \displaystyle\sum_{n \leq x} \frac{\mu(n)\chi_r(n)}{n} \right) \right] } + \mathscr{O}(1),\\
\end{array}$$

where $\mu$ is the M\"{o}bius function defined by 

$$\mu(p_1^{e_1} \ldots p_k^{e_k}) = \left\{ \begin{array}{ll}
(-1)^k &\colon e_1=e_2=\ldots=e_k=1 \\
0 &\colon otherwise.
\end{array} \right.$$

So we will show that ${\color{blue} \displaystyle\sum_{n=1}^{\infty} \frac{\chi_r(n) \log(n)}{n}}$ converges and that ${\color{red} \displaystyle\sum_{n \leq x} \frac{\mu(n)\chi_r(n)}{n}} = \mathscr{O}(1)$. Then we are done. 
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\textbf{Theorem:} Let $\chi$ is nonprincipal character mod $k$, $f$ non-negative with continuous negative derivative for all $x \geq x_0$. Then if $y \geq x \geq x_0$ we have

$$\displaystyle\sum_{x < n \leq y} \chi(n) f(n) = \mathscr{O}(f(x)).$$

In addition, if $\displaystyle\lim_{x \rightarrow \infty} f'(x) = 0$, then $\displaystyle\sum_{n=1}^{\infty} \chi(n)f(n)$ converges and

$$\displaystyle\sum_{n \leq x} \chi(n) f(n) = \displaystyle\sum_{n=1}^{\infty} \chi(n) f(n) + \mathscr{O}(f(x)).$$

So with $f(x) = \frac{\log x}{x}$ we have $f'(x) = \frac{1-\log x}{x^2}$ and thus the sum ${\color{blue} \displaystyle\sum_{n=1}^{\infty} \frac{\chi_r(n) \log(n)}{n}}$ converges.
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%
%%
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
By another technical lemma, for $r \neq 1$,

$$L_{\chi_r}(1) \displaystyle\sum_{n \leq x} \frac{\mu(n)\chi_r(n)}{n} = \mathscr{O}(1),$$

So if we can always divide by $L_{\chi_{_r}}(1)$, we are done. This is why the proof of Dirichlet's theorem boils down to showing $L_{\chi}(1) \neq 0$ for any nonprincipal character $\chi$ mod $k$.
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%
%% for nonprincipal real-valued \chi, L_{\chi}(1) \neq 0
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\textbf{Theorem:} For $r > 1$ and real-valued $\chi_r$, $L_{\chi_r}(1) \neq 0$. \\

Define $A(n) = \displaystyle\sum_{d | n} \chi_r(d),$ and $B(x) = \displaystyle\sum_{n \leq x} \frac{A(n)}{\sqrt{n}}$. Then it is known that $\displaystyle\lim_{x \rightarrow \infty} B(x) = \infty$ and 

$$B(x) = 2\sqrt{x} L_{\chi_r}(1) + \mathscr{O}(1)$$

for all $x \geq 1$. 

\hspace{1pt} \\

Therefore, since $L_{\chi_r}(1)$ is the coefficient of $\sqrt{x}$ and $\displaystyle\lim_{x \rightarrow \infty} 2 L_{\chi_r}(1) \sqrt{x} = \infty,$ we have $L_{\chi_r}(1) \neq 0$. $\blacksquare$
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%
%% for nonprincipal non-real-valued \chi, L_{\chi}(1) \neq 0
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\textbf{Theorem:} For $r > 1$, non-real-valued $\chi_r$, $L_{\chi_r}(1) \neq 0$. \\

Let $N(k)$ denote the number of nonprincipal non-real-valued characters mod $k$ such that $L_{\chi_r}(1)=0$. Note that if $L_{\chi_r}(1)=0$, then $L_{\overline{\chi_r}}(1)=0$ as well, so $N(k)$ is an even number. By a technical lemma, if $L_{\chi_r}(1)=0$ then

$$\displaystyle\sum_{p \leq x; p \equiv 1 (mod k)} \frac{\log p}{p} = \frac{1-N(k)}{\phi(k)} \log x + \mathscr{O}(1).$$

So if $N(k) \geq 2$, the coefficient $\frac{1 - N(k)}{\phi(k)}$ will become negative. This is a contradiction, since all terms in the sum in the left hand side are positive. Thus $N(k)=0$. $\blacksquare$
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
In the last few slides, we have shown

$$\begin{array}{ll}
\displaystyle\sum_{p \leq x; p \equiv h(mod \hspace{3pt} k)} \frac{\log p}{p} \\
= \log x + \frac{1}{\phi(k)} \displaystyle\sum_{r=2}^{\phi(k)} \overline{\chi_r(h)} {\color{purple} \displaystyle\sum_{p \leq x} \frac{\chi_r(p) \log p}{p}} + \mathscr{O}(1) \\
= \log x + \frac{1}{\phi(k)} \displaystyle\sum_{r=2}^{\phi(k)} \overline{\chi_r(h)}
{\color{red} \left[ {\color{blue} \left( \displaystyle\sum_{n=1}^{\infty} \frac{\chi_r(n) \log(n)}{n} \right)} \left( \displaystyle\sum_{n \leq x} \frac{\mu(n)\chi_r(n)}{n} \right) \right] } + \mathscr{O}(1). \\
= \log x + \frac{1}{\phi(k)} \displaystyle\sum_{r=2}^{\phi(k)} \overline{\chi_r(h)} \\
= \log x + \mathscr{O}(1). \\
\end{array}$$
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
So, taking a limit yields

$$\displaystyle\lim_{x \rightarrow \infty} \displaystyle\sum_{p \leq x; p \equiv h(mod \hspace{3pt} k)} \frac{\log p}{p} = \displaystyle\sum_{p \equiv h(mod \hspace{3pt} k)} \frac{\log p}{p} = \displaystyle\lim_{x \rightarrow \infty} \log x + \mathscr{O}(1) = \infty.$$

Therefore there are infinitely many primes in the arithmetic progression $\{kn+h \colon n \in \mathbb{Z}\}$!
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Thank you for attending!

\vspace{20pt}

\underline{References} \\
\textit{ANONYMOUS ARTICLE. An introduction to analytic number theory.} \\

\textit{Apostol, Tom. Introduction to Analytic Number Theory. Springer-Verlag 1976.} \\
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}


