Chapter 15 Applying the Selberg sieve
Section 15.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{15.1.1}
\end{equation}
and
\begin{equation}
\sum_{n \leq x} |f(n)| = O(\log^{|\kappa|} x).\tag{15.1.2}
\end{equation}
(The superfluous absolute value in (15.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{15.1.3}
\end{equation}
(exercise; see Exercise 15.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{15.1.4}
\end{equation}
(exercise; see Exercise 15.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{15.1.5}
\end{equation}
(exercise; see Exercise 15.4.3).
Section 15.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 15.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{15.2.1}
\end{equation}
where
\begin{equation*}
H_g = \prod_p (1-g(p)) (1-p^{-1})^{-\kappa}.
\end{equation*}
Section 15.3 Bounding the error term
Suppose our function \(g\) satisfies the conditions
\begin{equation}
g(d) d \geq 1 \qquad (d | P(z))\tag{15.3.1}
\end{equation}
and
\begin{equation}
\sum_{y \leq p \leq x} g(p) \log p = O(\log (2x/y)).\tag{15.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{15.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{15.3.4}
\end{equation}
(exercise; see Exercise 15.4.5).
Exercises 15.4 Exercises
2.
Prove (15.1.4).3.
Prove (15.1.5).
Hint.
Write \(\sum_{n=1}^\infty f(n) n^{-s}\) in terms of \(c_f\) by partial summation, then multiply by \(\zeta(s+1)^\kappa\) and compare to the Euler product.
4.
In Theorem 14.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 (15.3.4) under the assumptions (15.3.1), (15.3.2), (15.3.3).
Hint.
First use Exercise 14.3.2 to bound the sum on the left by
\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*}
where \(\sigma\) is the usual sum-of-divisors function. Then apply the prime number theorem plus partial summation to control this.6.
Use Theorem 14.1 to prove that the number of twin primes \(p \leq x\) is \(O(x / \log^2 x)\text{.}\)
Hint.
Put \(f(n) = 1\) if \(n = m(m+2)\) for some \(m\) and \(f(n) = 0\) otherwise, then apply the Selberg sieve with \(z = x^{1/4}\text{.}\)
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.
First prove that the sum \(\sum_n 1/(n \gamma(n))\) converges, where \(\gamma(n) = \prod_{p|n} p\text{.}\)
9.
Use Exercise 15.4.7 and Exercise 15.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{.}\)
