Estimating Primes - Analytic Number Theory

1 Estimating Primes

Theorem (Euler). $\sum_{p} \frac{1}{p} = \infty$ .

Proof. Consider $p_{N} = \prod_{p}^{N} (1 + \frac{1}{p} + \frac{1}{p^{2}} + \dots + \frac{1}{p^{N}})$ , for $N \in ℕ = {1, 2, 3, \dots}$ . We have:

\begin{array}{l} p_{N} & \geq \sum_{n = 1}^{N} \frac{1}{n} \\ \geq \sum_{n = 1}^{N - 1} \int_{n}^{n + 1} \frac{d t}{t} \\ = \int_{1}^{N - 1} \frac{d t}{t} \\ = \log (N - 1) \end{array}

On the other hand, using $1 + x \leq e^{x}$ , so

\begin{array}{l} p_{N} & \leq \prod_{p \leq N} \exp (\frac{1}{p} + \frac{1}{p^{2}} + \dots + \frac{1}{p^{N}}) \\ = \exp (\sum_{p \leq N} (\frac{1}{p} + \frac{1}{p^{2}} + \dots + \frac{1}{p^{N}})) \\ \leq \exp (\sum_{p \leq N} (\frac{1}{p} + \frac{1}{p^{2} - p})) \\ \leq \exp (C + \sum_{p \leq N} \frac{1}{p}) \end{array}

Comparing these two bounds gives

\sum_{p \leq N} \frac{1}{p} \geq \log \log (N - 1) - C .

Then letting $N \to \infty$ gives the desired result. □

Theorem (Chebyshev’s Theorem).

π (x) \leq \frac{c x}{\log x}

(for $x \geq 2$ , where $c$ is an absolute constant).

Proof. Consider

\begin{array}{l} S_{N} & = (\binom{2 N}{N}) \\ = \frac{(2 N)!}{{(N!)}^{2}} \end{array}

for $N \in ℕ$ . We have

S_{N} \leq \sum_{j = 0}^{2 N} (\binom{2 N}{j}) = {(1 + 1)}^{2 N} = 4^{N} .

On the other hand,

S_{N} = \prod_{p \leq 2 N} p^{α^{p} (N)}

where $α_{p} (N)$ is the largest $j$ such that $p^{j} | (\binom{2 N}{N})$ . We have $α_{p} (N) = 1$ for $p \in (N, 2 N]$ . So

(\log 4) N \geq \sum_{N < p \leq 2 N} \log p .

Take $N = ⌈ \frac{x}{2} ⌉$ , for $x \geq 2$ . Hence

\sum_{x < p \leq 2 x} \log p \leq (\log 4) ⌈ \frac{x}{2} ⌉ + \log x \leq (\log 4) \frac{x}{2} + \log 4 + \log x .

Then

\begin{array}{l} \sum_{p \leq x} & \leq \sum_{0 \leq j \leq \frac{\log x}{\log 2}} ((\log 4) \frac{x}{2^{j + 2}} + \log x) & (telescoping summation, take \frac{x}{2}, \frac{x}{2^{2}}, \frac{x}{2^{3}}, \dots) \\ \leq (\log 4) x + {(\log x)}^{2} + 1 \end{array}

So for $x \geq 2$ and a suitable large enough constant $c^{'}$ , we have

\sum_{p \leq x} \leq (\log 4) x + c^{'} {(\log x)}^{2} .

Hence

\begin{array}{l} \sum_{\frac{x}{{(\log x)}^{2}} < p \leq x} \log p & \leq (\log 4) x + c^{'} {(\log x)}^{2} \\ ⟹ \log \frac{x}{{(\log x)}^{2}} (π (x) - π (\frac{x}{{(\log x)}^{2}})) & \leq (\log 4) x + c^{'} {(\log x)}^{2} \\ ⟹ π (x) & \leq \frac{x}{{(\log x)}^{2}} + (\log 4) \frac{x}{\log \frac{x}{{(\log x)}^{2}}} + c^{'} \frac{{(\log x)}^{2}}{\log \frac{x}{{(\log x)}^{2}}} \\ \leq (\log 4 + 𝜀) \frac{x}{\log x} \end{array}

for any $𝜀$ , as long as $x \geq x (𝜀)$ .

Take $𝜀 = 1$ . Choose $c > 0$ large enough. □

1.1 Asymptotic Notation

Definition 1.1 (Big $O$ and little $o$ notation). Let $f, g, h : S \to ℂ$ , $S \subseteq ℂ$ .

Write $f (x) = O (g (x))$ if there is $c > 0$ such that $| f (x) | \leq c | g (x) |$ for all $x \in S$ .

Write $f (x) = o (g (x))$ if for any $𝜀 > 0$ there is $x_{𝜀} > 0$ such that $| f (x) | \leq 𝜀 | g (x) |$ for $x \in S$ , $| x | \geq x_{𝜀}$ .

Write $f (x) = g (x) + O (h (x))$ if $f (x) - g (x) = O (h (x))$ and write $f (x) = g (x) + o (h (x))$ if $f (x) - g (x) = o (h (x))$ .

Definition 1.2 (Vinogradov notation). Let $f, g, h : S \to ℂ$ , $S \subseteq ℂ$ .

Write $f (x) ≪ g (x)$ or $g (x) ≫ f (x)$ if $f (x) = O (g (x))$ .

Example.

${(\log x)}^{1} 00 ≪ \exp (\sqrt{\log x}) ≪ x^{\frac{1}{100}}$ ( $x \leq 1$ ), since $\lim_{x \to \infty} \frac{{(\log x)}^{100}}{\exp (\sqrt{\log x})} = 0$ , $\lim_{x \to \infty} \frac{\exp (\sqrt{\log x})}{x^{\frac{1}{100}}} = 0$ .
$100 x + 100 ≪ x ≪ \frac{x}{100}$ (for $x \geq 1$ ).
$e^{x} = 1 + x + O (x^{2})$ for $x \in [- 10, 10]$ , since $e^{x} = 1 + x + \sum_{n = 2}^{\infty} \frac{x^{n}}{n!}$ .
$⌊ x ⌋ = x + O (1)$ for $x \in ℝ$ (since $⌊ x ⌋ \in (x - 1, x]$ ).
$\frac{x + 1}{x} = 1 + o (1)$ (for $x \geq 1$ ).

Lemma. Let $f, g, h, u : S \to ℂ$ .

(i) If $f (x) = O (g (x))$ and $g (x) = O (h (x))$ , then $f (x) = O (h (x))$ (transitivity).
(ii) If $f (x) = O (h (x))$ and $g (x) = O (u (x))$ , then $f (x) + g (x) = O (| h (x) | + | u (x) |)$ .
(iii) If $f (x) = O (h (x))$ and $g (x) = O (u (x))$ , then $f (x) g (x) = O (h (x) u (x))$ .

Proof. Follows from the definition in a straightforward way. Example:

(iii) $| f (x) | \leq c_{1} | h (x) |$ , $| g (x) | \leq c_{2} | u (x) |$ . Then $| f (x) g (x) | \leq c_{1} c_{2} | h (x) u (x) |$ , so $f (x) g (x) = O (h (x) u (x))$ . □

1.2 Partial Summation

Lemma 1.3 (Partial Summation). Assuming that:

${(a_{n})}_{n \in ℕ}$ are complex numbers
$x \geq y \geq 0$
$f : [y, x] \to ℂ$ is continuously differentiable

Then

\sum_{y < n \leq x} a_{n} f (n) = A (x) f (x) - A (y) f (y) - \int_{y}^{x} A (t) f^{'} (t) d t,

where for $t \geq 1$ , we define

A (t) = \sum_{n \leq t} a_{n} = \sum_{n = 1}^{⌊ t ⌋} a_{n} .

Proof. It suffices to prove the $y = 0$ case, since then

\sum_{y < n \leq x} a_{n} f (n) = \sum_{0 < n \leq x} a_{n} f (n) - \sum_{0 < n \leq y} a_{n} f (n) .

Suppose $y = 0$ . By the fundamental theorem of calculus,

f (n) = f (x) - \int_{n}^{x} f^{'} (t) d t = \int_{0}^{x} f^{'} (t) 𝟙_{[n, x]} (t) d t .

Summing over $n \leq x$ , we get

\begin{array}{l} \sum_{n \leq x} a_{n} f (n) & = A (x) f (x) - \int_{0}^{x} f^{'} (t) (\sum_{n \leq x} 𝟙_{[n, x]} (t) a_{n}) d t \\ = A (x) f (x) - \int_{0}^{x} f^{'} (t) A (t) d t □ \end{array}

Lemma. If $x \geq 1$ , then

\sum_{n \leq x} \frac{1}{n} = \log x + γ + O (\frac{1}{x}),

where $γ \in ℝ$ is Euler’s constant, which is given by $γ = \lim_{N \to \infty} \sum_{k = 1}^{N} \frac{1}{k} - \log N$ .

Proof. Apply Partial Summation with $a_{n} = 1$ , $f (t) = \frac{1}{t}$ , $y = \frac{1}{2}$ . Clearly $A (t) = ⌊ t ⌋$ . Then,

\begin{array}{l} \sum_{n \leq x} \frac{1}{n} & = \frac{⌊ x ⌋}{x} + \int_{1}^{x} \frac{⌊ t ⌋}{t^{2}} d t \\ = \frac{x + O (1)}{x} + \int_{1}^{x} \frac{t - {t}}{t^{2}} d t \\ = 1 + O (\frac{1}{x}) + \log x - \int_{1}^{x} \frac{{t}}{t^{2}} d t \\ = 1 + \log x - \int_{1}^{\infty} \frac{{t}}{t^{2}} d t + O (\frac{1}{x}) \end{array}

The last equality is true since $\int_{x}^{\infty} \frac{{t}}{t^{2}} d t \leq \int_{x}^{\infty} \frac{1}{t^{2}} d t = \frac{1}{x}$ .

Let $γ = 1 - \int_{1}^{\infty} \frac{{t}}{t^{2}} d t$ . Then we have the asymptotic equation as desired.

Taking $x \to \infty$ in the formula, we see that $γ$ is equal to the formula for Euler’s constant, as desired. □

Lemma. For $x \geq 1$ ,

\sum_{p \leq x} \frac{1}{p} = \int_{1}^{x} \frac{π (t)}{t^{2}} d t + O (1) .

Proof. Apply Lemma 1.3 with $a_{n} = 𝟙_{ℙ} (n)$ (where $ℙ$ is the set of primes), $f (t) = \frac{1}{t}$ , and $y = 1$ .

We get $A (t) = π (t)$ , and then

\begin{array}{l} \sum_{p \leq x} \frac{1}{p} & = \frac{π (x)}{x} + \int_{1}^{x} \frac{π (t)}{t^{2}} d t \\ = \int_{1}^{x} \frac{π (t)}{t^{2}} d t + O (1) □ \end{array}

1.3 Arithmetic Functions and Dirichlet convolution

Definition (Arithmetic function). An arithmetic function is a function $f : ℕ \to ℂ$ .

Definition (Multiplicative). An arithmetic function $f$ is multiplicative if $f (1) = 1$ and $f (m n) = f (m) f (n)$ whenever $m, n \in ℕ$ are coprime.

Moreover, $f$ is completely multiplicative if $f (m n) = f (m) f (n)$ for all $m, n$ .

Example.

$f (n) = n^{s}$ for $s \in ℂ$ is completely multiplicative.
Möbius function
$μ (n) = {\begin{matrix} 1 & n = 1 \\ {(- 1)}^{k} & if n is a product of k distinct primes \\ 0 & n is divisible by a square of a prime \end{matrix}$

This is multiplicative:
- If $μ (m n) = 0$ and $m$ , $n$ are coprime, then we must have had at least one of $μ (m) = 0$ or $μ (n) = 0$ .
- If $μ (m n) = 1$ , then say $m$ is a product of $k$ distinct primes and $n$ is a product of $l$ distinct primes. Then $μ (m n) = {(- 1)}^{k + l} = {(- 1)}^{k} {(- 1)}^{l} = μ (m) μ (n)$ .
- $τ (n) = \sum_{n = a b} 1$ (divisor function) and $τ_{k} (n) = \sum_{n = n_{1} n_{2} \dots n_{k}} 1$ (generalised divisor function). $τ$ and $τ_{k}$ are multiplicative.

On the space of arithmetic functions, we have operations:

\begin{array}{l} (f + g) (n) & = f (n) + g (n) \\ (f g) (n) & = f (n) g (n) \\ (f * g) (n) & = Dirichlet convolution \end{array}

Definition (Dirichlet convolution). For $f, g : ℕ \to ℂ$ , we define

(f * g) (n) = \sum_{d | n} f (d) g (\frac{n}{d}),

where $\sum_{d | n}$ means sum over the divisors of $n$ .

Lemma 1.4. The space of arithmetic functions with operations $+$ , $*$ is a commutative ring.

Proof. Since arithmetic functions with $+$ form an abelian group, it suffices to show:

(i) $(f * g) * h = f * (g * h)$
(ii) $f * g = g * f$
(iii) $f * I = f$
(iv) $f * (g + h) = f * g + f * h$

Proofs:

(i) Follows from $(f * g) (n) = \sum_{n = a b} f (a) g (b)$ .
(ii) Follows from $(f * g) (n) = \sum_{n = a b} f (a) g (b)$ .
(iii) Take
$I (n) = {\begin{matrix} 1 & n = 1 \\ 0 & n \neq 0 \end{matrix} .$

Then one can check that $f * I = f$ .
(iv) From definition. □

Lemma. The set of arithmetic functions $f$ with $f (1) \neq 0$ form an abelian group with operation $*$ .

Proof. Need $g$ such that $f * g = I$ .

(f * g) (1) = f (1) g (1) = 1 ⟹ g (1) = \frac{1}{f (1)} .

Assume $g (m)$ defined for $m < n$ . We will defined $g (n)$ .

\begin{array}{l} (f * g) (n) & = g (n) f (1) + \sum_{\begin{array}{c} d | n \\ d \neq 1 \end{array}} f (d) g (\frac{n}{d}) \\ ⟹ g (n) & = - \frac{1}{f (1)} \sum_{\begin{array}{c} d | n \\ d \neq 1 \end{array}} f (d) g \underset{< n}{\underset{⏟}{(\frac{n}{d})}} □ \end{array}

Lemma. Multiplicative arithmetic functions form an abelian group with $*$ . Moreover, for completely multiplicative $f$ , the Dirichlet inverse is $μ f$ .

Proof. For the first part, suffices to show closedness. Let $f, g : ℕ \to ℂ$ be multiplicative, and $m, n$ coprime.

If $m n = a b$ , we can write $a = a_{1} a_{2}$ , $b = b_{1} b_{2}$ where $a_{1} = (a, m)$ , $a_{2} = (a, n)$ , $b_{1} = (b, m)$ and $b_{2} = (b, n)$ . Therefore we have:

\begin{array}{l} (f * g) (m n) & = \sum_{m n = a b} f (a) g (b) \\ = \sum_{\begin{array}{c} m = a_{1} b_{1} \\ n = a_{2} b_{2} \end{array}} f (a_{1} a_{2}) g (b_{1} b_{2}) & (above observation) \\ = \sum_{\begin{array}{c} m = a_{1} b_{1} \\ n = a_{2} b_{2} \end{array}} f (a_{1}) f (a_{2}) g (b_{1}) g (b_{2}) & (by multiplicativity) \\ = (f * g) (m) (f * g) (n) \end{array}

(also need to check that inverses are multiplicative).

Now, remains to show that for completely multiplicative $f$ , $f * μ f = I$ .

Note that $f * μ f$ is multiplicative by the first part. So enough to show $(f * μ f) (p^{k}) = I (p^{k})$ for prime powers $p^{k}$ . Calculate:

\begin{array}{l} f * μ f (p) & = f (p) + μ f (p) \\ = f (p) - f (p) \\ = 0 \\ = I (p) \end{array}

and for $k \geq 2$ :

\begin{array}{l} f * μ f (p^{k}) & = f (p^{k}) + μ f (p) f (p^{k - 1}) \\ = f (p^{k}) - f (p) f (p^{k - 1}) \\ = f {(p)}^{k} - f (p) f {(p)}^{k - 1} \\ = 0 \\ = I (p^{k}) □ \end{array}

Example. $τ_{k} (n) = \sum_{n = n_{1} \dots n_{k}} 1$ . Then

τ_{k} = \underset{k times}{\underset{⏟}{1 * 1 * \dots * 1}} .

So $τ_{k}$ is multiplicative by the previous result.

Definition (von Mangoldt function). The von Mangoldt function $Λ : ℕ \to ℝ$ is

Λ (n) = {\begin{matrix} \log p & if n = p^{k} for some prime p \\ 0 & otherwise \end{matrix}

Then $\log = 1 * Λ$ since

\log n = \log \prod_{p | n} p^{α_{p} (n)} = \sum_{p | n} α_{p} (n) \log p = 1 * Λ (n) .

Since $μ$ is the inverse of $1$ , we have

\log * μ = 1 * Λ * μ = Λ * 1 * μ = Λ * I = Λ .

1.4 Dirichlet Series

For a sequence ${(a_{n})}_{n \in ℕ}$ , we want to associate a generating function that gives information of ${(a_{n})}_{n \in ℕ}$ . Might consider

{(a_{n})}_{n \in ℕ} \leftrightarrow \sum_{n = 1}^{\infty} a_{n} x^{n} .

If we do this, then $\sum_{p} x^{p}$ is hard to control. So this is not very useful.

The following series has nicer number-theoretic properties:

Definition (Formal series). For $f : ℕ \to ℂ$ , define a (formal) series

D_{f} (s) = \sum_{n = 1}^{\infty} f (n) n^{- s}

for $s \in ℂ$ .

Lemma. Assuming that:

$f : ℕ \to ℂ$ satisfying $| f (n) | \leq n^{o (1)}$

Then

D_{f} (s)

converges absolutely for

Re (s) > 1

and defines an analytic function for

Re (s) > 1

Proof. Let $𝜀 > 0$ (fixed), $n \in ℕ$ and $Re (s) > 1 + 2 𝜀$ .

Then

\begin{array}{l} \sum_{n = N}^{\infty} | f (n) n^{- s} | & = \sum_{n = N}^{\infty} | f (n) | n^{- Re (s)} \\ ≪ \sum_{n = N}^{\infty} n^{𝜀 - Re (s)} \\ \leq \sum_{n = N}^{\infty} n^{- 1 - 𝜀} \\ \leq N^{- 1 - 𝜀} + \sum_{n = N + 1}^{\infty} \int_{n - 1}^{n} t^{- 1 - 𝜀} d t \\ \leq N^{- 1 - 𝜀} + \int_{N}^{\infty} t^{- 1 - 𝜀} d t \\ ≪ N^{- 𝜀} \end{array}

Hence we have absolute convergence for $Re (s) > 1 + 2 𝜀$ . Also, $D_{f} (s)$ is a uniform limit of the functions $\sum_{n = 1}^{N} f (n) n^{- s}$ . From complex analysis, a uniform limit of analytic functions is analytic. Hence $D_{f} (s)$ is analytic for $Re (s) > 1 + 2 𝜀$ .

Now let $𝜀 \to 0$ . □

Theorem (Euler product). Assuming that:

$f : ℕ \to ℂ$ be bounded ( $| f (n) | ≪ 1$ ) and multiplicative

Then

D_{f} (s) = \prod_{p} (1 + \frac{f (p)}{p^{2}} + \frac{f (p^{2})}{p^{2 s}} + \dots),

for $Re (s) > 1$ . Furthermore, if $f$ is completely multiplicative, then

D_{f} (s) = \prod_{p} {(1 - \frac{f (p)}{p^{s}})}^{- 1},

for $Re (s) > 1$ .

Proof. Let $N \in ℕ$ , $Re (s) = σ > 1$ . Let

D_{f} (s, N) = \prod_{p \leq N} (1 + \frac{f (p)}{p^{s}} + \frac{f (p^{2})}{p^{2 s}} + \dots) .

Note that the series defining the factors are absolutely convergent, since

\sum_{k = 1}^{\infty} \frac{| f (p^{k}) |}{| p^{k s} |} ≪ \sum_{k = 1}^{\infty} \frac{1}{p^{k s}} < \infty

(geometric series).

Therefore, multiplying out,

D_{f} (s, N) = \sum_{n = 1}^{\infty} a (n, N) f (n) n^{- s}

where

a (n, N) = # {ways to write n as a product of prime powers, where the primes are \leq N} .

The fundamental theorem of arithmetic tells us that $a (n, N) \in {0, 1}$ and $a (n, N) = 1$ for $n \leq N$ .

Now,

\begin{array}{l} | D_{f} (S) - D_{f} (s, N) | & \leq \sum_{n = N + 1}^{\infty} | f (n) | | n^{- s} | \\ ≪ \sum_{n = N + 1}^{\infty} n^{- σ} \\ \overset{N \to \infty}{\to} 0 \end{array}

(since $\sum_{n = 1}^{\infty} n^{- σ} < \infty$ ). Hence $D_{f} (s) = \lim_{N \to \infty} D_{f} (s, N)$ .

Finally, for $f$ completely multiplicative, use geometric formula:

\sum_{k = 1}^{\infty} \frac{f {(p)}^{k}}{p^{k s}} = \frac{1}{1 - \frac{f (p)}{p^{s}}} . □

Lemma. Assuming that:

$f, g : ℕ \to ℂ$
$| f (n) |, | g (n) | \leq n^{o (1)}$

Then

D_{f * g} (s) = D_{f} (s) D_{g} (s)

for $Re (s) > 1$ .

Proof. We know $D_{f} (s)$ and $D_{g} (s)$ are absolutely convergent, so can expand out the product.

\begin{array}{l} D_{f} (s) D_{g} (s) & = \sum_{a, b = 1}^{\infty} f (a) g (b) {(a b)}^{- s} & = \sum_{n = 1}^{\infty} \sum_{n = a b} f (a) g (b) n^{- s} \\ = \sum_{n = 1}^{\infty} (f * g) (n) n^{- s} \\ = D_{f * g} (s) □ \end{array}

Definition (Riemann zeta function). For $Re (s) > 1$ , define

ζ (s) = \sum_{n = 1}^{\infty} n^{- s} .

Example.

$\sum_{n = 1}^{\infty} \frac{τ (n)}{n^{s}} = ζ {(s)}^{2}$ for $Re (s) > 1$ (since $τ = 1 * 1$ ).
$\sum_{n = 1}^{\infty} \frac{μ (n)}{n^{s}} = \frac{1}{ζ (s)}$ for $Re (s) > 1$ (since $μ$ is the Dirichlet inverse of $1$ , so $μ * 1 = I$ ).
$ζ^{'} (s) = - \sum_{n = 1}^{\infty} \frac{\log n}{n^{s}}$ for $Re (s) > 1$ , since $\frac{d}{d s} n^{- s} = - (\log n) n^{- s}$ . Can differentiate termwise, since if $F_{n}$ analytic and $F_{n} \to F$ uniformly, then $F$ is analytic and $F_{n}^{'} \to F^{'}$ . We know that $\sum_{n = 1}^{\infty} f (n) n^{- s}$ converges uniformly for $Re (s) > 1$ if $| f (n) | \leq n^{o (1)}$ .
$\frac{ζ^{'} (s)}{ζ (s)} = - \sum_{n = 1}^{\infty} \frac{Λ (n)}{n^{s}}$ for $Re (s) > 1$ . This is because $- \log = - 1 * Λ$ – see the definition of the von Mangoldt function.

Dirichlet hyperbola method

Problem: How many lattice points $(a, b) \in ℕ^{2}$ satisfy $a b \leq x$ ?

Note that this number is $\sum_{n \leq x} τ (n) = \sum_{a b \leq x} 1$ .

Dirichlet proved that for $x \geq 2$ ,

\sum_{n \leq x} τ (n) = x \log x + (2 γ - 1) x + O (x^{1 ∕ 2})

where $γ$ is Euler’s constant.

We will see a proof of this shortly.

Conjecture: Can have $O_{𝜀} (x^{\frac{1}{4} + 𝜀})$ . Current best exponent is $0.314$ .

First, we prove a lemma:

Lemma (Dirichlet hyperbola method). Assuming that:

$f, g : ℕ \to ℂ$
$x \geq y \geq 1$

Then

\sum_{n \leq x} (f * g) (n) = \sum_{d \leq y} f (d) \sum_{m \leq \frac{x}{d}} g (m) + \sum_{m \leq \frac{x}{y}} g (m) \sum_{y < d \leq \frac{x}{m}} f (d) .

Proof. $\sum_{n \leq x} (f * g) (n) = \sum_{d m \leq x} f (d) g (m)$ . Split this sum into parts with $d \leq y$ and $d > y$ to get the conclusion. □

Theorem 1.5 (Dirichlet’s divisor problem). For $x \geq 2$ ,

\sum_{n \leq x} τ (n) = x \log x + (2 γ - 1) x + O (x^{1 ∕ 2})

where $γ$ is Euler’s constant.

Proof. We use the Dirichlet hyperbola method, with $y = x^{\frac{1}{2}}$ . Note that $τ = 1 * 1$ . Then,

\begin{array}{l} \sum_{n \leq x} τ (n) & = \sum_{d \leq x^{\frac{1}{2}}} \sum_{m \leq \frac{x}{d}} 1 + \sum_{m \leq x^{\frac{1}{2}}} \sum_{x^{\frac{1}{2}} < d \leq \frac{x}{m}} 1 \\ = \sum_{x \leq x^{\frac{1}{2}}} (\frac{x}{d} + O (1)) + \sum_{m \leq x^{\frac{1}{2}}} (\frac{x}{m} - x^{\frac{1}{2}} + O (1)) \\ = x \sum_{d \leq x^{\frac{1}{2}}} \frac{1}{d} + x \sum_{m \leq x^{\frac{1}{2}}} \frac{1}{m} - \sum_{m \leq x^{\frac{1}{2}}} x^{\frac{1}{2}} + O (x^{\frac{1}{2}}) \end{array}

Recall from Lecture 2 that

\sum_{d \leq y} \frac{1}{d} = \log y + γ + O (\frac{1}{y}) .

Taking $y = x^{\frac{1}{2}}$ , the previous expression becomes

2 \times (\frac{1}{2} \log x + γ + O (\frac{1}{x^{\frac{1}{2}}})) - x + O (x^{\frac{1}{2}}) = x \log x + (2 γ - 1) x + O (x^{\frac{1}{2}}) . □