Chapter 14 Applying the Selberg sieve
Section 14.1 Bounding sums of multiplicative functions
When applying the Selberg sieve, we will frequently in the situation where \(f\) is a multiplicative function and we need to bound \(\sum_{n \leq x} f(n)\text{.}\) Here is an argument that does this for us (due to Wirsing) assuming some control over the values of \(f\) at prime powers.
Let \(e\) be the arithmetic function defined by the following identity of formal Dirichlet series:
\begin{equation*}
\sum_{n=1}^\infty e(n) n^{-s} = - \frac{d}{ds} \log \sum_{n=1}^\infty f(n) n^{-s}.
\end{equation*}
We derive a bound under the condition that for some \(\kappa > 0\text{,}\)
\begin{equation}
\sum_{n \leq x} e(n) = \kappa \log x + O(1)\tag{14.1.1}
\end{equation}
and
\begin{equation}
\sum_{n \leq x} |f(n)| = O(\log^{|\kappa|} x).\tag{14.1.2}
\end{equation}
(The superfluous absolute value in (14.1.2) is included because it actually suffices to take \(\kappa > -1/2\text{,}\) but we won’t use this.)
Define
\begin{equation*}
M_f(x) = \sum_{n \leq x} f(n),
\end{equation*}
which is what we want to estimate. We first obtain
\begin{equation}
(\kappa + 1) \sum_{n \leq x} f(n) \log n = \kappa M_f(x) \log x + O(\log^\kappa x)\tag{14.1.3}
\end{equation}
(exercise; see Exercise 14.4.1. Since
\begin{equation*}
\sum_{n \leq x} f(n) \log (x/n) = \int_1^x M_f(y) y^{-1}\,dy,
\end{equation*}
we obtain
\begin{equation*}
\Delta(x) = M_f(x) \log x - (\kappa + 1) \int_2^x M_f(y) y^{-1}\,dy = O(\log^\kappa x).
\end{equation*}
We next derive the following identity:
\begin{equation}
M_f(x) = \log^\kappa x \int_2^x -\Delta(y) d(\log y)^{-\kappa-1} + \Delta(x) \log^{-1} x\tag{14.1.4}
\end{equation}
(exercise; see Exercise 14.4.2). This implies
\begin{equation*}
M_f(x) = c_f \log^\kappa x + O(\log^{\kappa-1} x)
\end{equation*}
for
\begin{equation*}
c_f = -\int_2^\infty \Delta(y) d(\log y)^{-\kappa-1},
\end{equation*}
but it would be nice to be able to describe \(c_f\) more explicitly. Fortunately this is possible: we have
\begin{equation}
c_f = \frac{1}{\Gamma(\kappa+1)} \prod_p (1-p^{-1})^\kappa (1 + f(p) + f(p^2) + \cdots)\tag{14.1.5}
\end{equation}
(exercise; see Exercise 14.4.3).
Section 14.2 Bounding the main term
To get an upper bound on the main term \(XH^{-1}\text{,}\) we need a lower bound on \(H\text{.}\) A simple example occurs when \(g(d) = d^{-1}\text{;}\) see Exercise 14.4.4.
A more generic example occurs when we have
\begin{equation*}
\sum_{p \leq x} g(p) \log p = \kappa \log x + O(1)
\end{equation*}
for some \(\kappa > 0\text{,}\) and
\begin{equation*}
\sum_p g(p)^2 \log p \lt \infty.
\end{equation*}
For instance, this holds if \(g(p) = c/p\text{.}\) By Wirsing’s bound, we get
\begin{align*}
H \amp= c \log^\kappa \sqrt{y} (1 + O(\log^{-1} y))\\
c \amp= \frac{1}{\Gamma(\kappa+1)} \prod_p (1 - g(p))^{-1} (1 - p^{-1})^{\kappa}.
\end{align*}
This can be more usefully written as
\begin{equation}
H^{-1} = 2^\kappa \Gamma(\kappa+1) H_g \log^{-\kappa} y (1 + O(\log^{-1} y)),\tag{14.2.1}
\end{equation}
where
\begin{equation*}
H_g = \prod_p (1-g(p)) (1-p^{-1})^{-\kappa}.
\end{equation*}
Section 14.3 Bounding the error term
Suppose our function \(g\) satisfies the conditions
\begin{equation}
g(d) d \geq 1 \qquad (d | P(z))\tag{14.3.1}
\end{equation}
and
\begin{equation}
\sum_{y \leq p \leq x} g(p) \log p = O(\log (2x/y)).\tag{14.3.2}
\end{equation}
Suppose also that the individual error terms \(r_d\) are not too large:
\begin{equation}
|r_d(z)| \leq g(d) d \qquad (d | P(z)).\tag{14.3.3}
\end{equation}
Then it is straightforward to derive the bound
\begin{equation}
\left| \sum_{d | P(z)} \lambda^+(d) r_d(z) \right| \leq y \log^{-2} y\tag{14.3.4}
\end{equation}
(exercise; see Exercise 14.4.5).
Exercises 14.4 Exercises
2.
Prove (14.1.4).3.
Prove (14.1.5).Hint.
4.
In Theorem 13.1, prove that
\begin{equation*}
H > \log \sqrt{y}.
\end{equation*}
Moreover, if we instead take \(g(d) = d^{-1}\) and \(P\) to be the set of all primes, then
\begin{equation*}
H > \left(\log \sqrt{y} \right) \prod_{p|q} (1-g(p)).
\end{equation*}
5.
Prove (14.3.4) under the assumptions (14.3.1), (14.3.2), (14.3.3).Hint.
Exercise 13.3.2
\begin{equation*}
\left( \sum_{d \lt \sqrt{y}} |\rho_d| g(d) d \right)^2 \leq \left(
\frac{1}{H} \sum_{n \lt \sqrt{y}} h(n) \sigma(n) \right)^2,
\end{equation*}
\(\sigma\)
6.
Use Theorem 13.1 to prove that the number of twin primes \(p \leq x\) is \(O(x / \log^2 x)\text{.}\)Hint.
7. (Brun–Titchmarsh theorem).
Prove that for any \(\epsilon > 0\text{,}\) there exists \(x_0 = x_0(\epsilon)\) with the following property: for any positive integers \(m,N\) with \(\gcd(m,N) = 1\text{,}\) and any \(x \geq \max\{N, x_0(\epsilon)\}\text{,}\) the number of primes \(p \leq x\) with \(p \equiv m \pmod{N}\) is at most
\begin{equation*}
\frac{(2+\epsilon)x}{\phi(N) \log (2x/N)}.
\end{equation*}
This is one of several problems in which the Selberg sieve applies to give you a result which is off by a factor of 2 from the expected best result.8.
Prove that
\begin{equation*}
\sum_{n \leq x} \frac{n}{\phi(n)} = O(x),
\end{equation*}
then deduce by partial summation that
\begin{equation*}
\sum_{n \leq x} \frac{1}{\phi(n)} = O(\log x),
\end{equation*}
Hint.
9.
Use Exercise 14.4.7 and Exercise 14.4.8 to deduce that
\begin{equation*}
\sum_{p \leq x} d(p-1) = O(x),
\end{equation*}
where \(d(n)\) denotes the number of divisors of \(n\text{.}\)
