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

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 A_d=X w(d)/d+R_d$

$\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

for every

and every

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

, and $\mathcal{A}=\{1,2,\dotsc,x\}$ , then the right hand side of (4) provides an upper bound for the number of primes between

and

We have that

and $R_d\leq 1$ . The second error term in (4) has at most

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

$\displaystyle \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)$

$\displaystyle \pi(x)\leq O\left(\frac{x\log\log x}{\log x}\right).$

Example. (Upper bound on the number of twin primes.) If

and $p\mid n(n+2)$ , then the integers

and

cannot both be primes. Let $\mathcal{P}$ be as above, and set $\mathcal{A}=\{ n(n+1) : n\in [y..x]\}$ . Then

, and

. The remainder

does not exceed $2^{\nu(d)}$ . Like above we obtain

References

George Greaves.
Sieves in number theory.
Springer, 2001.
Zbl 1003.11044.

H. Halberstam and H.-E. Richert.
Sieve methods, volume 4 of London Mathematical Society Monographs.
1974.
Zbl 0298.10026.

C. Hooley.
Application of sieve methods to the theory of numbers, volume 70 of Cambridge Tracts in Mathematics.
Cambridge Univ. Press, 1976.
Zbl 0327.10044.

Gérald Tenenbaum.
Introduction to Analytic and Probabilistic Number Theory, volume 46 of Cambridge Studies in Advanced Mathematics.
Cambridge Univ. Press.
Zbl 0831.11001.

General combinatorial sieve

References