PlanetMath: Brun's pure sieve

In the first quarter of the twentieth century Viggo Brun developed an extension of the sieve of Eratosthenes that yielded good estimates on the number of elements of a set $\mathcal{A}$ that are not divisible by any of the primes $p_1,\dotsc,p_k$ provided only that $\mathcal{A}$ is ``sufficiently regularly distributed'' modulo these primes. That allowed him to prove that the sum of reciprocals of twin primes converges (the limit is now known as Brun's constant), and that every sufficiently large even number is a sum of two numbers each having at most $9$ prime factors. In what follows we describe the simplest form of Brun's sieve, known as Brun's pure sieve.

$\displaystyle \sum_{n\in\mathcal{A}}\sum_{\substack{p_1\nmid n\\ \dots\\ p_k\nmid n}}1$	$\displaystyle =\sum_{n\in\mathcal{A}}\sum_{(n,p_1\dotsb p_k)=1} 1=\sum_{n\in\mathcal{A}} \sum_{d\mid (n,p_1\dotsb p_k)}\mu(d)$
	$\displaystyle =\sum_{d\mid p_1\dotsb p_k}\mu(d)\sum_{\substack{n\mid\mathcal{A}\\ d\mid n}}1=\sum_{d\mid p_1\dotsb p_k}\mu(d)A_d$
	$\displaystyle =A_1-\sum_{p\mid p_1\dotsb p_k} A_p+\sum_{pq\mid p_1\dotsb p_k} A_{pq}+\dotsb.$	(1)

$\displaystyle \sum_{\substack{d\mid p_1\dotsb p_k\\ \nu(d)\leq 2h-1}}\mu(d)A_d\... ...k\nmid n}}1\leq \sum_{\substack{d\mid p_1\dotsb p_k\\ \nu(d)\leq 2h}} \mu(d)A_d$

(2)

$\displaystyle \sum_{\substack{d\mid p_1\dotsb p_k\\ \nu(d)\leq t}} \mu(d)A_d$	$\displaystyle =\sum_{\substack{d\mid p_1\dotsb p_k\\ \nu(d)\leq t}} \mu(d)(X w(d)/d+R_d)$
	$\displaystyle =X\sum_{\substack{d\mid p_1\dotsb p_k\\ \nu(d)\leq t}} \mu(d) \fr... ...(d)}{d}+O\left(\sum_{\substack{d\mid p_1\dotsb p_k\\ \nu(d)\leq t}} R_d \right)$	(3)

Since $u^{\nu(d)-t}$ is greater than $1$ for every $u>1$ and every $d$ such that $\nu(d)>t$ , we have that

$\displaystyle \sum_{\substack{d\mid p_1\dotsb p_k\\ \nu(d)\leq t}} \mu(d) \frac{w(d)}{d}$	$\displaystyle =\sum_{d\mid p_1\dotsb p_k} \mu(d) \frac{w(d)}{d}+O\left(\sum_{\substack{d\mid p_1\dotsb p_k\\ \nu(d)> t}} \frac{w(d)}{d}\right)$
	$\displaystyle =\sum_{d\mid p_1\dotsb p_k} \mu(d) \frac{w(d)}{d}+O\left(\sum_{d\mid p_1\dotsb p_k} \frac{w(d)}{d}u^{\nu(d)-t}\right)$
	$\displaystyle =\sum_{d\mid p_1\dotsb p_k} \mu(d) \frac{w(d)}{d}+O\left(u^{-t}\sum_{d\mid p_1\dotsb p_k} \frac{w(d)}{d}u^{\nu(d)}\right)$
and since the sum of a multiplicative function can be written as an Euler product, we get
	$\displaystyle =\prod_{p\in \mathcal{P}} \left(1-\frac{w(p)}{p}\right)+O\left(u^{-t}\prod_{p\in \mathcal{P}} \left(1+u\frac{w(p)}{p}\right) \right)$
	$\displaystyle =\prod_{p\in \mathcal{P}} \left(1-\frac{w(p)}{p}\right)+O\left(u^{-t}\prod_{p\in \mathcal{P}} \left(1+\frac{w(p)}{p}\right)^u \right)$
to minimize the error term we choose $u=t/\sum_{p\in\mathcal{P}} \log(1+\frac{w(p)}{p})$ , and get
	$\displaystyle =\prod_{p\in \mathcal{P}} \left(1-\frac{w(p)}{p}\right)+O\left(\frac{1}{t}\sum_{p\in\mathcal{P}} \frac{w(p)}{p} \right)^t$

$\displaystyle \sum_{n\in\mathcal{A}}\sum_{\substack{p_1\nmid n\\ \dots\\ p_k\nm... ...right)^t+O\left(\sum_{\substack{d\mid p_1\dotsb p_k\\ \nu(d)\leq t}} R_d\right)$

(4)

Example. (Upper bound on the number of primes.) If we set $\mathcal{P}$ to be all the primes less $y$ , and $\mathcal{A}=\{1,2,\dotsc,x\}$ , then the right hand side of (4) provides an upper bound for the number of primes between $y$ and $x$ .

We have that $w(d)=1$ and $R_d\leq 1$ . The second error term in (4) has at most $y^t$ summands, and the first error term is bounded by $(\frac{c}{t}\log\log y)^t$ by Merten's theorem. Thus, the estimate (4) becomes \begin{equation*} \pi(x)-\pi(y)\leq x\frac{e^{-\gamma}+o(1)}{\log y}+x\cdot O\left(\frac{1}{t}\log\log y\right)^t+O(y^t) \end{equation*}In order to squeeze out the best upper bound on the number of primes not exceeding $x$ we have to minimize the right side of the inequality above. The nearly optimal choice is $t=c\log \log x$ , and $y=x^{1/2c\log\log x}$ for a sufficiently large constant $c$ . With this choice we obtain \begin{equation*} \pi(x)\leq O\left(\frac{x\log\log x}{\log x}\right). \end{equation*}This inequality is stronger than the one obtained by an application of the sieve of Eratosthenes.

Example. (Upper bound on the number of twin primes.) If $p<n$ and $p\mid n(n+2)$ , then the integers $n$ and $n+2$ cannot both be primes. Let $\mathcal{P}$ be as above, and set $\mathcal{A}=\{ n(n+1) : n\in [y..x]\}$ . Then $w(2)=1$ , and $w(p)=2$ if $p>2$ . The remainder $R_d$ does not exceed $2^{\nu(d)}$ . Like above we obtain \begin{equation*} \pi_2(x)-\pi_2(y)\leq x\frac{c}{(\log y)^2}+x\cdot O\left(\frac{1}{t}\log\log y\right)^t+O((2y)^t) \end{equation*}where $\pi_2(x)$ denotes the number of twin primes not exceeding $x$ . Upon setting $t=c\log \log x$ , and $y=x^{1/2c\log\log x}$ we obtain \begin{equation*} \pi_2(x)\leq O\left(\frac{x(\log\log x)^2}{(\log x)^2}\right). \end{equation*}This is the original result for which Viggo Brun developed the sieve now bearing his name. This result can be put in following striking form:

General combinatorial sieve

References