Elementary Estimates for Primes - Analytic Number Theory

2 Elementary Estimates for Primes

Recall from Lecture 1:

$\sum_{p} \frac{1}{p} = \infty$ (Euler’s Theorem)
$π (x) ≪ \frac{x}{\log x}$ (Chebyshev’s Theorem)

2.1 Merten’s Theorems

Theorem 2.1 (Merten’s Theorem). Assuming that:

$x \geq 3$

Then

(i) $\sum_{p \leq x} \frac{\log p}{p} = \log x + O (1)$
(ii) $\sum_{p \leq x} \frac{1}{p} = \log \log x + M + O (\frac{1}{\log x})$ (for some $M \in ℝ$ )
(iii) $\prod_{p \leq x} (1 - \frac{1}{p}) = \frac{c + o (1)}{\log x}$ (for some $c > 0$ )

Remark. Can show $c = e^{- γ}$ .

Proof.

(i) Let $N = ⌊ x ⌋$ . Consider $N!$ . We have $\begin{array}{l} N^{N} & \leq N^{N} \\ N! & \geq N^{N} e^{- N} \end{array}$
(the second inequality cn be proved by induction, using ${(1 + \frac{1}{N})}^{N} \leq e$ ).

Let $v_{p} (k)$ be the largest power of $p$ dividing $k$ . Then
$\begin{array}{l} N! & = \prod_{p \leq N} p^{v_{p} (N!)} & (fundamental theorem of arithmetic) \\ ⟹ \log N! & = \sum_{p \leq N} v_{p} (N!) \log p \end{array}$
We have $v_{p} (N!) = \sum_{j = 1}^{\infty} ⌊ \frac{N}{p^{j}} ⌋$ . Indeed,
$\begin{array}{l} v_{p} (N!) & = \sum_{k = 1}^{N} v_{p} (k) \\ = \sum_{k = 1}^{N} \sum_{j = 1}^{\infty} 𝟙_{v_{p} (k) \geq j} \\ = \sum_{j = 1}^{\infty} \sum_{k = 1}^{N} 𝟙_{v_{p} (k) \geq j} \\ = \sum_{j = 1}^{\infty} ⌊ \frac{N}{p^{j}} ⌋ \end{array}$
Now,
$\begin{array}{l} \log N! & = \sum_{p \leq N} ⌊ \frac{N}{p} ⌋ \log p + \sum_{p \leq N} (\log p) \sum_{j = 2}^{\infty} ⌊ \frac{N}{p^{j}} ⌋ \\ = \sum_{p \leq N} (\frac{N}{p} + O (1)) \log p + O (\sum_{p \leq N} \frac{\log p}{p^{2}} \cdot N) & (geometric series) \\ = N \sum_{p \leq N} \frac{\log p}{p} + \underset{\leq (\log N) π (N) ≪ N (C h e b y s h e v)}{\underset{⏟}{O (\sum_{p \leq N} \log p)}} + O (N) & (since \sum_{p} \frac{\log p}{p^{2}} < \infty) \\ = N \sum_{p \leq N} \frac{\log p}{p} + O (N) \end{array}$
Combine with $\log N! = N \log N + O (N)$ to get
$N \log N + O (N) = N \sum_{p \leq N} \frac{\log p}{p} + O (N) .$

Divide by $N$ to get the result.
(ii) By Partial Summation, this is
$1 + O (\frac{1}{\log x}) + \int_{2}^{x} \frac{\sum_{p \leq t} \frac{\log p}{p}}{t {(\log t)}^{2}} d t .$

Writing $𝜀 (t) = \sum_{p \leq t} \frac{\log p}{p} - \log t$ , we get
$\begin{array}{l} 1 + O (\frac{1}{\log x}) + \int_{2}^{x} \frac{d t}{t \log t} + \int_{2}^{x} \frac{𝜀 (t)}{t {(\log t)}^{2}} d t \\ = 1 + O (\frac{1}{\log x}) + \log \log x - \log \log 2 + \int_{2}^{\infty} \frac{𝜀 (t)}{t {(\log t)}^{2}} d t + O (\int_{x}^{\infty} \frac{| 𝜀 (t) |}{t {(\log t)}^{2}} d t) \end{array}$
By part (i),
$\begin{array}{l} \int_{x}^{\infty} \frac{| 𝜀 (t) |}{t {(\log t)}^{2}} d t \\ ≪ \int_{x}^{\infty} \frac{1}{t {(\log t)}^{2}} d t \\ ≪ \frac{1}{\log x} \end{array}$
Take $M = 1 - \log \log 2 + \int_{2}^{\infty} \frac{𝜀 (t)}{t {(\log t)}^{2}} d t$ .
(iii) Use Taylor expansion
$\log (1 - y) = - \sum_{j = 1}^{\infty} \frac{y^{j}}{j}$

to get
$\begin{array}{l} \log \prod_{p \leq x} (1 - \frac{1}{p}) & = \sum_{p \leq x} \log (1 - \frac{1}{p}) \\ = - \sum_{p \leq x} \frac{1}{p} - \sum_{p \leq x} \sum_{j = 2}^{\infty} \frac{p - j}{j} \end{array}$
Write $H = \sum_{p} \sum_{j = 2}^{\infty} \frac{p - j}{j}$ . We get
$\begin{array}{l} = - \sum_{p \leq x} \frac{1}{p} - H + O (\sum_{p > x} \underset{≪ p^{- 2}}{\underset{⏟}{\sum_{j = 2}^{\infty} \frac{p - j}{j}}}) \\ = - \sum_{p \leq x} \frac{1}{p} - H + O (\frac{1}{x}) \\ \overset{(ii)}{=} - \log \log x - H + O (\frac{1}{x}) \end{array}$
Taking exponentials,
$\prod_{p \leq x} (1 - \frac{1}{p}) = \frac{c + o (1)}{\log x} . □$

2.2 Sieve Methods

General tools for estimating the number of primes (or products of a few primes in a set).
Need information on the distribution of the set in residue classes.

Definition (Sieve problem). Let $P \subseteq ℙ$ . Let

P (z) = \prod_{\begin{array}{c} p \in P \\ p \leq z \end{array}} p,

and let $A \subseteq ℤ$ . Denote

S (A, P, z) = | {n \in A : (n, P (z)) = 1} | .

Problem: Estimate $S (A, P, z)$ .

Note that if $A \subseteq [\frac{x}{2}, x] \cap ℤ$ ,

\begin{array}{l} S (A, ℙ, x^{\frac{1}{2}}) & = | A \cap ℙ | \\ S (A, ℙ, x^{\frac{1}{3}}) & = | A \cap (ℙ \cup {p_{1} p_{2} : p_{1} p_{2} > x^{\frac{1}{3}}}) | \end{array}

Sieve hypothesis: There exists a multiplicative $g : ℕ \to [0, 1]$ and $R_{d} \in ℝ$ such that

| {n \in A : n \equiv 0 (m o d d)} | = g (d) | A | + R_{d}

for all square-free $d$ (no repeated prime factors).

Example.

$A = [1, x]$ , $P = ℙ$ .

$| A_{d} | = ⌊ \frac{x}{d} ⌋ = \frac{x}{d} + O (1)$

Then $g (d) = \frac{1}{d}$ , $| R_{d} | ≪ 1$ .

$S (A, ℙ, x^{\frac{1}{2}}) = | {p \in ℙ : p \in [x^{\frac{1}{2}}, x]} | = π (x) + O (x^{\frac{1}{2}}) .$
$A = {n (n + 2) : n \leq x}$ , $P = ℙ$ . Let $d = p_{1} \dots p_{r}$ , where $p_{i}$ are distinct primes. Then
$\begin{array}{l} | A_{d} | & = | {n \leq x : n \equiv 0 or - 2 (m o d p_{i}) \forall i \leq r} | \\ = {\begin{matrix} \frac{2^{r}}{d} x & if d odd \\ \frac{2^{r - 1}}{d} x + O (2^{r}) & if d even \end{matrix} \end{array}$
(by Chinese Remainder Theorem).
$\begin{array}{l} S (A, ℙ, {(2 x)}^{\frac{n}{2}}) & = | {p \in ({(2 x)}^{\frac{1}{2}}, x] : p + 2 \in ℙ} | \\ = | {p \leq x : p + 2 \in ℙ} | + O (x^{\frac{1}{2}}) \end{array}$
Here,
$g (p) = {\begin{matrix} \frac{1}{p} & p = 2 \\ \frac{2}{p} & p > 2 \end{matrix}$

and $R_{d} = O (2^{w (d)})$ , where $w (d)$ is the number of prime factors of $d$ (distinct).

Lemma. We have

S (A, P, z) = \sum_{d | P (z)} μ (d) | A_{d} | .

Proof. Recall that

𝟙_{n = 1} = (μ * 1) (n)

(since $μ$ is the inverse of $1$ ). Hence,

\begin{array}{l} S (A, P, z) & = \sum_{n \in A} 𝟙_{(n, P (z)) = 1} \\ = \sum_{n \in A} \sum_{\begin{array}{c} d | P (z) \\ d | n \end{array}} μ (d) \\ = \sum_{d | P (z)} μ (a) | A_{d} | □ \end{array}

Example. Let

π (x, z) = | {n \leq x : (n, P (z)) = 1} | .

Let $P = ℙ$ . Let $A = [1, x] \cap ℤ$ . Then

| A_{d} | = \frac{x}{d} + O (1) .

By the previous lemma,

\begin{array}{l} π (x, z) & = S (A, ℙ, z) \\ = \sum_{d | P (z)} μ (d) (\frac{x}{d} + O (1)) \\ = x \sum_{d | P (z)} \frac{μ (d)}{d} + O (\sum_{d | P (z)} \underset{\leq 1}{\underset{⏟}{| μ (d) |}}) \\ = x \sum_{d | P (z)} \frac{μ (d)}{d} + O (2^{π (z)}) & P (z) = p_{1} \dots p_{π (2)} \\ = x \prod_{p \leq z} (1 + \underset{- 1}{\underset{⏟}{\frac{μ (p)}{p}}}) + O (2^{π (2)}) & fundamental theorem of arithmetic \\ = \frac{c + o (1)}{\log z} x + O (2^{z}) & Merten’s theorem, for some c > 0 \end{array}

For $2 \leq z \leq \log x$ ,

π (x, z) = \frac{c + o (1)}{\log z} x .

Theorem (Sieve of Erastothenes – Legendre). Assuming that:

$A \subseteq [1, x] \cap ℕ$
$2 \leq z \leq x$
Assume the Sieve Hypothesis

Then

\begin{array}{l} S (A, P, z) \\ = | A | \prod_{\begin{array}{c} p \leq 2 \\ p \in P \end{array}} (1 - g (p)) + O (x^{\frac{1}{2}} {(\log x)}^{\frac{1}{2}} 2^{- \frac{\log x}{4 \log z}} {(\sum_{\begin{array}{c} d \leq x \\ d | P (z) \end{array}} | R_{d} |^{2})}^{\frac{1}{2}} + | A | e^{\frac{\log x}{\log z}} \prod_{\begin{array}{c} p \leq z \\ p \in P \end{array}} {(1 + g (p))}^{e}) \end{array}

Proof. Recall from previous lecture that

\begin{array}{l} S (A, P, z) & = \sum_{\begin{array}{c} d | P (z) \\ d \leq x \end{array}} μ (d) | A_{d} | & (since A_{d} = \emptyset for d > x) \\ = \sum_{\begin{array}{c} d | P (z) \\ d \leq x \end{array}} μ (d) g (d) | A | + O (\sum_{\begin{array}{c} d \leq x \\ d | P (z) \end{array}} | R_{d} |) & (sieve hypothesis) \\ = | A | \sum_{d | P (z)} μ (d) g (d) + O (\sum_{\begin{array}{c} d \leq x \\ d | P (z) \end{array}} | R_{d} | + | A | \sum_{\begin{array}{c} d | P (z) \\ d > x \end{array}} g (d)) \\ = | A | \prod_{\begin{array}{c} p \leq z \\ p \in P \end{array}} (1 - g (p)) + O (\sum_{\begin{array}{c} d \leq x \\ d | P (z) \end{array}} | R_{d} | + | A | \sum_{\begin{array}{c} d | P (z) \\ d > x \end{array}} g (d)) \end{array}

We estimate the first error term using Cauchy-Schwarz:

\sum_{\begin{array}{c} d \leq x \\ d | P (z) \end{array}} | R_{d} | \leq {(\sum_{\begin{array}{c} d \leq x \\ d | P (z) \end{array}} | R_{d} |^{2})}^{\frac{1}{2}} {(\sum_{\begin{array}{c} d \leq x \\ d | P (z) \end{array}} 1)}^{\frac{1}{2}} .

Note that if $d | P (z)$ , $d > x^{\frac{1}{2}}$ , then

ω (d) \geq \frac{\log x^{\frac{1}{2}}}{\log z},

( $ω (d)$ – number of distinct prime factors of $d$ ), since $z^{ω (d)} \geq d \geq x^{\frac{1}{2}}$ .

Hence, $2^{ω (d)} \geq 2^{\frac{\log x}{2 \log z}}$ , $d | P (z)$ , $d > x^{\frac{1}{2}}$ .

Now we get

\begin{array}{l} \sum_{\begin{array}{c} d \leq x \\ d | P (z) \end{array}} 1 & \leq 2^{- \frac{\log x}{2 \log z}} \sum_{\begin{array}{c} d \leq x \\ d | P (z) \end{array}} \underset{= τ (d)}{\underset{⏟}{2^{ω (d)}}} \\ \leq 2^{- \frac{\log x}{2 \log z}} \sum_{d \leq x} τ (d) \\ ≪ 2^{- \frac{\log x}{2 \log z}} x \log x \end{array}

(the last step is by Dirichlet’s divisor problem: $\sum_{d \leq x} τ (d) = (1 + o (1)) \cdot x \log x$ ).

Substituting this in, the first error term becomes as desired.

Now we estimate the second error term. We have

\begin{array}{l} \sum_{\begin{array}{c} d | P (z) \\ d > x \end{array}} g (d) & \leq x^{- \frac{1}{\log z}} \sum_{d | P (z)} g (d) d^{\frac{1}{\log z}} & (since d > x in the sum: Rankin’s trick) \\ = x^{- \frac{1}{\log z}} \prod_{\begin{array}{c} p \leq z \\ p \in P \end{array}} (1 + g (p) \underset{\leq z^{\frac{1}{\log z}} = e}{\underset{⏟}{p^{\frac{1}{\log z}}}}) \\ \leq x^{- \frac{1}{\log z}} \prod_{\begin{array}{c} p \leq z \\ p \in P \end{array}} (1 + e g (p)) \\ \leq \underset{= e^{- \frac{\log x}{\log z}}}{\underset{⏟}{x^{- \frac{1}{\log z}}}} \prod_{\begin{array}{c} p \leq z \\ p \in P \end{array}} {(1 + g (p))}^{e} & (1 + e y \leq {(1 + y)}^{e}) \end{array}

Combining the error terms, the claim follows. □

Example. Take $A = [1, x] \cap ℤ$ , $P = ℙ$ . Then $g (d) = \frac{1}{d}$ , $R_{d} = O (1)$ , so the sieve gives us

\begin{array}{l} S (A, P, z) & = π (x, z) \\ = (x + O (1)) \prod_{p \leq z} (1 - \frac{1}{p}) \\ + O (x^{\frac{1}{2}} {(\log x)}^{\frac{1}{2}} 2^{- \frac{\log x}{4 \log z}} x^{\frac{1}{2}} + (x + O (1)) e^{- \frac{\log x}{\log z}} \prod_{p \leq z} {(1 + \frac{1}{p})}^{e}) \end{array}

By Merten’s Theorem,

\begin{array}{l} \prod_{p \leq z} (1 - \frac{1}{p}) & = \frac{C + o (1)}{\log z} \\ \prod_{p \leq z} (1 + \frac{1}{p}) & \leq \prod_{p \leq z} {(1 - \frac{1}{p})}^{- 1} \\ = (\frac{1}{C} + o (1)) \log z \end{array}

Hence,

π (x, z) = \frac{c + o (1)}{\log z} + O (x {(\log x)}^{\frac{1}{2}} 2^{- \frac{\log x}{4 \log z}} + x e^{- \frac{\log x}{\log z}} {(\log z)}^{e}) .

Hence, for $2 \leq z \leq \exp (\frac{\log x}{10 \log \log x})$ ,

π (x, z) = \frac{c + o (1)}{\log z} x .

This asymptotic in fact holds for $z \leq x^{o (1)}$ .

In particular, the Erastothenes-Legendre sieve gives

π (x) \leq π (x, z) + z ≪ \frac{x}{\log x} \log \log x

for $z = \exp (\frac{\log x}{10 \log \log x})$ . Not quite the Chebyshev bound $π (x) ≪ \frac{x}{\log x}$ .

2.3 Selberg Sieve

	asymptotes	good upper bound for primes

Erastothenes-Legendre	✓	✗

Selberg	✗	✓

Theorem 2.2 (Selberg sieve). Assuming that:

$z \geq 2$
$A \subseteq ℤ$ finite
$P \subseteq ℙ$
Assume the sieve hypothesis
$h : ℕ \to [0, \infty)$ be the multiplicative function supported on square-free numbers, given on the primes by

$h (p) = {\begin{matrix} \frac{g (p)}{1 - g (p)} & p \in P \\ 0 & p \notin P \end{matrix}$

Then

S (A, P, z) \leq \frac{| A |}{\sum_{d \leq z} h (d)} + \sum_{\begin{array}{c} d \leq z^{2} \\ d | P (z) \end{array}} τ_{3} (d) | R_{d} | .

Sieve hypothesis: There is a multiplicative $g : ℕ \to [0, 1]$ and $R_{d} \in ℝ$ such that

| A_{d} | = g (d) | A | + R_{d}

for all square-free $d \geq 1$ .

Proof. Let ${(ρ_{d})}_{d \in ℕ}$ be real numbers with

ρ_{1} = 1, ρ_{d} = 0, d > z (∗)

Then,

𝟙_{(n, P (z)) = 1} \leq {(\sum_{\begin{array}{c} d | n \\ d | P (z) \end{array}} ρ_{d})}^{2} .

(If $(n, P (z)) = 1$ , get $1 \leq ρ$ otherwise use $0 \leq x^{2}$ ).

Summing over $n \in A$ ,

\begin{array}{l} S (A, P, z) & = \sum_{n \in A} 𝟙_{(n, P (z)) = 1} \\ \leq \sum_{n \in A} {(\sum_{\begin{array}{c} d | n \\ d | P (z) \end{array}} ρ_{d})}^{2} \\ = \sum_{d_{1} d_{2} | P (z)} ρ_{d_{1}} ρ_{d_{2}} \sum_{\begin{array}{c} n \in A \\ [d_{1}, d_{2}] | n \end{array}} 1 \\ = | A | \sum_{d_{1}, d_{2} | P (z)} ρ_{d_{1}} ρ_{d_{2}} g ([d_{1}, d_{2}]) + \underset{E}{\underset{⏟}{\sum_{d_{1}, d_{2} | P (z)} ρ_{d_{1}} ρ_{d_{2}} R_{[d_{1}, d_{2}]}}} & (sieve hypothesis) \end{array}

( $[m, n]$ means $lcm (m, n)$ ).

We first estimate $E$ :

\begin{array}{l} E & \leq \max_{k} | ρ_{k} |^{2} \sum_{d_{1}, d_{2} | P (z)} | R_{[d_{1}, d_{2}]} | \\ = \max_{k} | ρ_{k} |^{2} \sum_{\begin{array}{c} d \leq z^{k} \\ d | P (z) \end{array}} \sum_{\begin{array}{c} d_{1}, d_{2} \in ℕ \\ [d_{1}, d_{2}] = d \end{array}} | R_{d} | & (d = [d_{1}, d_{2}]) \end{array}

We have

\begin{array}{l} \sum_{\begin{array}{c} d_{1}, d_{2} \in ℕ \\ d = [d_{1}, d_{2}] \end{array}} 1 & = \sum_{l \leq z} \sum_{\begin{array}{c} d_{1}^{'}, d_{2}^{'} \in ℕ \\ d = l d_{1}^{'} d_{2}^{'} \\ (d_{1}^{'}, d_{2}^{'}) = 1 \end{array}} 1 & (l = (d_{1}, d_{2}), d_{1}^{'} = d_{1} ∕ l, [d_{1}, d_{2}] = l d_{1}^{'} d_{2}^{'}) \\ \leq τ_{3} (d) \end{array}

Therefore

E \leq \sum_{\begin{array}{c} d \leq z^{z} \\ d | P (z) \end{array}} τ_{3} (d) | R_{d} | \cdot \max_{k} | ρ_{k} |^{2} .

Now it suffices to prove that there is a choice of ${(ρ_{d})}_{d \in ℕ}$ satisfying ( $*$ ) such that

Claim 1: $\sum_{d_{1}, d_{2} | P (z)} ρ_{d_{1}} ρ_{d_{2}} g ([d_{1}, d_{2}]) = \frac{1}{\sum_{d \leq z}} h (d)$ .

Claim 2: $| ρ_{k} | \leq 1$ for all $k \in ℕ$ .

Proof of claim 1:

We have, writing $k = (d_{1}, d_{2})$ , $d_{i}^{'} = \frac{d_{i}}{k}$ ,

\begin{array}{l} \sum_{d_{1}, d_{2} | P (z)} ρ_{d_{1}} ρ_{d_{2}} g ([d_{1}, d_{2}]) & = \sum_{k | P (z)} μ {(k)}^{2} \sum_{\begin{array}{c} d_{1}^{'}, d_{2}^{'} | \frac{P (z)}{k} \\ (d_{1}^{'}, d_{2}^{'}) = 1 \end{array}} ρ_{k d_{1}^{'}} ρ_{k d_{2}^{'}} g (k d_{1}^{'} d_{2}^{'}) \\ = \sum_{k | P (z)} μ {(k)}^{2} g (k) \sum_{\begin{array}{c} d_{1}^{'}, d_{2}^{'} | \frac{P (z)}{k} \\ (d_{1}^{'}, d_{2}^{'}) = 1 \end{array}} ρ_{k d_{1}^{'}} ρ_{k d_{2}^{'}} g (d_{1}^{'}) g (d_{2}^{'}) & (multiplicativity) \end{array}

We have

𝟙_{(d_{1}^{'}, d_{2}^{'}) = 1} = \sum_{\begin{array}{c} c | d_{1}^{'} \\ c | d_{2}^{'} \end{array}} μ (c)

(since $μ * 1 = I$ ) so the previous expression becomes

\begin{array}{l} \sum_{k | P (z)} μ {(k)}^{2} g (k) \sum_{c | \frac{P (z)}{k}} μ (c) \sum_{\begin{array}{c} d_{1}^{'}, d_{2}^{'} | P (z) \\ d_{1}^{'} \equiv 0 (mod () c) \\ d_{2}^{'} \equiv 0 (mod c) \end{array}} ρ_{k d_{1}^{'}} ρ_{k d_{2}^{'}} g (d_{1}^{'}) g (d_{2}^{'}) \\ = \sum_{k | P (z)} μ {(k)}^{2} g (k) \sum_{c | \frac{P (z)}{k}} μ (k) {(\sum_{\begin{array}{c} d | \frac{P (z)}{k} \\ d \equiv 0 (mod c) \end{array}})}^{2} \\ = \sum_{k | P (z)} μ {(k)}^{2} g {(k)}^{- 1} \sum_{c | \frac{P (z)}{k}} μ (c) {(\sum_{d^{'} | \frac{P (z)}{c k}} ρ_{c k d^{'}} g (c k d^{'}))}^{2} \\ = \sum_{n \leq z} h {(m)}^{- 1} {(\sum_{\begin{array}{c} d | P (z) \\ d \equiv 0 (mod n) \end{array}} ρ_{d} g (d))}^{2} \end{array}

(multiplicativity, $d = c d^{'}$ , $m = c k$ , $d = m d^{'}$ ) since $\frac{1}{h} = \frac{μ^{2}}{g} * μ$ (check on primes $\frac{1}{h (p)} = \frac{1}{g (p)} - 1$ ).

Now we get

\sum_{d_{1}, d_{2} | P (z)} ρ_{d_{1}} ρ_{d_{2}} g ([d_{1}, d_{2}]) = \sum_{m \leq z} h {(m)}^{- 1} ζ_{m}^{2}

where

ζ_{m} = \sum_{\begin{array}{c} d | P (z) \\ d \equiv 0 (mod m) \end{array}} ρ_{d} g (d) .

Want to minimise this subject to ( $*$ ).

We need to translate the condition $ρ_{1} = 1$ . Note that

\begin{array}{l} \sum_{\begin{array}{c} m \leq z \\ m \equiv 0 (mod c) \end{array}} μ (m) ζ_{m} & = \sum_{d | P (z)} ρ_{d} g (d) \underset{\sum_{m^{'} | \frac{d}{c}} μ (c) μ (m^{'}) = μ (d) 𝟙_{d = e}}{\underset{⏟}{\sum_{\begin{array}{c} m | d \\ c | m \end{array}} μ (m)}} \\ = μ (e) ρ_{e} g (e) \end{array}

Hence,

ρ_{e} = \frac{μ (e)}{g (e)} \sum_{\begin{array}{c} m \leq 2 \\ m \equiv 0 (mod c) \end{array}} μ (m) ζ_{m} .

Now,

ρ_{1} = 1 = \sum_{m \leq z} μ (m) ζ_{m} .

By Cauchy-Schwarz, we then get

(\sum_{m \leq z} h {(m)}^{- 1} ζ_{m}^{2}) (\sum_{m \leq z} μ {(m)}^{2} h (m)) \geq {(\sum_{m \leq z} μ (m) ζ_{m})}^{2} = 1 .

Hence

\sum_{m \leq z} h {(m)}^{- 1} ζ_{m}^{2} \geq \frac{1}{\sum_{m \leq z} μ {(m)}^{2} h (m)} = \frac{1}{\sum_{m \leq z} h (m)} .

Equality holds for $T_{m} = \frac{h (m)}{G (z)}$ , where $G (z) = \sum_{m \leq z} h (m)$ . We now check that with these $ζ_{m}$ , $ρ_{d} = 0$ for $d > z$ .

Note that

ρ_{c} = \frac{μ (c)}{g (c) G (z)} \sum_{\begin{array}{c} m \leq z \\ m \equiv (mod c) \end{array}} μ (m) h (m) .

Hence, $ρ_{c} = 0$ for $c > 2$ .

This proves Claim 1.

Now we prove Claim 2 ( $| ρ_{c} | \leq 1$ ).

Note that any $m$ has at most one representation as $m = e m^{'}$ , where $e | d$ , $(m^{'}, d) = 1$ (for any $d \in ℕ$ ).

Now,

\begin{array}{l} G (z) & \geq \sum_{c | d} \sum_{\begin{array}{c} m^{'} \leq \frac{z}{c} \\ (m^{'}, d) = 1 \end{array}} h (c m^{'}) \\ = \sum_{c | d} h (c) \sum_{\begin{array}{c} m^{'} \leq \frac{z}{c} \\ (m^{'}, d) = 1 \end{array}} h (m^{'}) \\ \geq \sum_{c | d} h (e) \sum_{\begin{array}{c} m^{'} \leq \frac{z}{d} \\ (m^{'}, d) = 1 \end{array}} h (m^{'}) \end{array}

Now,

ρ_{d} = \frac{μ {(d)}^{2} h (d)}{g (d) G (z)} \sum_{\begin{array}{c} m^{'} \leq \frac{z}{d} \\ (m^{'}, d) = 1 \end{array}} μ (m^{'}) h (m^{'}) .

Substituting the lower bound for $G (z)$ ,

| ρ_{d} | \leq \frac{h (d)}{g (d) \sum_{c | d} h (e)} = 1,

since $1 * h = \frac{h}{g}$ . □

Lemma 2.3. Assuming that:

$z \geq 3$
$g : ℕ \to [0, 1]$ multiplicative
for some $K, A \in ℝ$ we have
$\sum_{p \leq z} g (p) \log p \leq κ \log z + A .$

Then

\frac{1}{\sum_{m \leq z} h (m)} \leq 2 \prod_{p \leq z^{1 ∕ (e κ + 1)}} (1 - g (p)),

where $h$ is defined in terms of $g$ as in Selberg’s sieve.

Proof. Note that for any $c \in (0, 1)$ ,

\sum_{m \leq z} h (m) \geq \sum_{\begin{array}{c} m \leq z \\ m | P (z^{c}) \end{array}} h (m) = G (z, c) .

Then

\begin{array}{l} \prod_{\begin{array}{c} p \leq z^{c} \\ p \in P \end{array}} {(1 - g (p))}^{- 1} - G (z, c) & = \prod_{\begin{array}{c} p \leq z^{c} \\ p \in P \end{array}} (1 + h (p)) - \sum_{\begin{array}{c} m \leq z \\ m | P (z^{c}) \end{array}} h (m) \\ = \sum_{\begin{array}{c} m > z \\ m | P (z^{c}) \end{array}} h (m) \end{array}

By Rankin’s trick,

\begin{array}{l} 1 - \prod_{p \leq z^{c}} (1 - g (p)) G (z, c) & = \prod_{p \leq z^{c}} (1 - g (p)) \sum_{\begin{array}{c} m > z \\ m | P (z^{c}) \end{array}} h (m) \\ \leq \prod_{p \leq z^{c}} (1 - g (p)) z^{- \frac{λ}{\log z}} \sum_{m | P (z^{c})} h (m) m^{\frac{λ}{\log z}} & (for any λ > 0) \\ = \prod_{p \leq z^{c}} (1 - g (p)) e^{- λ} \prod_{p \leq z^{c}} (1 + h (p) p^{\frac{λ}{\log z}}) \\ = e^{- λ} \prod_{p \leq z^{c}} (1 - g (p) + g (p) p^{\frac{λ}{\log z}} \\ \leq e^{- λ} \exp (\sum_{p \leq z^{c}} \underset{\leq \frac{λ}{\log z} (\log p) p^{\frac{λ}{\log z}}}{\underset{⏟}{(p^{\frac{λ}{\log z}} - 1)}}) \\ \leq \exp (- λ + \frac{λ}{\log z} \sum_{p \leq z^{c}} g (p) (\log p) p^{\frac{λ}{\log z}}) & (1 + t \leq e^{t}) \\ \leq \exp (- λ + c e^{c λ} λ κ + λ e^{c λ} \frac{A}{\log z}) \end{array}

Choose $c = \frac{1}{λ}$ and $λ = e κ + 1$ to get the claim. □

The Brun-Titchmarsh Theorem

Theorem 2.4 (Brun-Titchmarsh Theorem). Assuming that:

$x \geq 0$ , $y \geq 2$
$𝜀 > 0$ and $y$ is large in terms of $𝜀$

Then

π (x + y) - π (x) \leq \frac{(2 + 𝜀) y}{\log y} .

Remark. We expect

π (x + y) - π (x) = \frac{(n + o (1)) y}{\log x}

in a wide range of $y$ (e.g. $y \geq x^{𝜀}$ for some $𝜀 > 0$ fixed). The prime number theorem gives this for $y ≫ x$ . The Brun-Titchmarsh Theorem gives an upper bound of the expected order for $y \geq x^{𝜀}$ .

Proof. Apply the Selberg sieve with $A = [x, x + y] \cap ℕ$ , $P = ℙ$ . Note that for any $d \geq 1$ ,

| {a \in A : a \equiv 0 (m o d d)} = \frac{y}{d} + O (1) .

Hence, the sieve hypothesis holds with $g (d) = \frac{1}{d}$ , $R_{d} = O (1)$ .

Now, the function $h$ in Selberg sieve is given on primes by

h (p) = \frac{g (p)}{1 - g (p)} = \frac{1}{p - 1} = \frac{1}{φ (p)},

where $φ$ is the Euler totient function. In general,

h (d) = μ {(d)}^{2} \cdot \frac{1}{φ (d)}

(since $φ$ is multiplicative). Now, for any $z \geq 2$ , Selberg sieve yields

S (A, ℙ, z) \leq \frac{y}{\sum_{d \leq z} \frac{μ {(d)}^{2}}{φ (d)}} + O (\sum_{d \leq z^{2}} τ_{3} (d)) .

By Problem 11 on Example Sheet 1, the error term is $O (z^{2} {(\log z)}^{2})$ .

Take $z = y^{\frac{1}{2} - \frac{𝜀}{10}}$ . Then

z^{2} {(\log z)}^{2} ≪ {(y^{\frac{1}{2} - \frac{𝜀}{10}})}^{2} {(\log y)}^{2} ≪ y^{1 - \frac{𝜀}{20}}

(for $y \geq y_{0} (𝜀)$ ). We estimate

\begin{array}{l} \sum_{d \leq z} \frac{μ {(d)}^{2}}{φ (d)} & = \sum_{d \leq z} \frac{μ {(d)}^{2}}{d} \frac{d}{φ (d)} \\ = \sum_{d \leq z} \frac{μ {(d)}^{2}}{d} \cdot \prod_{p | d} \underset{= \frac{p}{p - 1} = \frac{p}{φ (p)}}{\underset{⏟}{(1 + \frac{1}{p} + \frac{1}{p^{2}} + \dots)}} \\ \geq \sum_{n \leq z} \frac{1}{n} \end{array}

since any $n \leq z$ has at least one representation as

n = d p_{1}^{a_{1}} \dots p_{k}^{a_{k}},

where $d \leq z$ is square-free and $p_{i} | d$ are primes and $a_{1} \geq 0$ .

We have proved

\sum_{n \leq z} \frac{1}{n} = \log z + O (1) \geq (1 - \frac{1}{10}) \log z

for $z \geq z_{0} (𝜀)$ .

Putting everything together gives us

\begin{array}{l} π (x + y) - π (x) & \leq S (A, ℙ, z) + z \\ \leq \frac{y}{(1 - \frac{𝜀}{10}) \log z} + z + y^{1 - \frac{𝜀}{20}} \\ \leq \frac{(2 + 𝜀) y}{\log y} \end{array}

for $y \geq y_{0} (𝜀)$ . □