PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: High Entry average rating: No information on entry rating
Brun's pure sieve (Topic)

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.

The sieve of Eratosthenes is based on the principle of inclusion-exclusion in the form

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

Brun's sieve is based on the observation that the partial sums of (1) alternatively overcount and undercount the number of elements of $ \mathcal{A}$ counted by the left side, that is,
$\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)

where $ \nu(d)$ denotes the number of prime factors of $ d$. In applications $ A_d$ can usually be approximated by a multiple of a multiplicative function, that is,
$\displaystyle A_d=X w(d)/d+R_d$    

where $ w(d)$ is some multiplicative function of $ d$, and $ R_d$ is small compared to $ X w(d)/d$. Then the estimate in (2) takes the form
$\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)

If the truncated sum is a good approximation to the full sum, then this formula is an improvement over the sieve of Eratosthenes because the sum over error terms $ R_d$ is shorter.

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$    

Combining this with (3) and (2) we obtain
$\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)

provided that $ u=t/\sum_{p\in\mathcal{P}} \log(1+\frac{w(p)}{p})\geq 1$.

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

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

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
$\displaystyle \pi(x)\leq O\left(\frac{x\log\log x}{\log x}\right).$    

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

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

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
$\displaystyle \pi_2(x)\leq O\left(\frac{x(\log\log x)^2}{(\log x)^2}\right).$    

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:
Theorem 1   The sum
$\displaystyle \sum_{p,p+2\text{ primes}} \left(\frac{1}{p}+\frac{1}{p+2}\right)$    

converges.

General combinatorial sieve

The inequality (2) was based on the observation that
$\displaystyle \sum_{d\mid n}\mu(d)\chi_-(d)\leq \sum_{d\mid n} \mu(d)\leq \sum_{d\mid n}\mu(d)\chi_+(d)$ (5)

where $ \chi_-$ is the characteristic function of the set of integers with no more than $ 2h-1$ prime factors, and $ \chi_+$ is the characteristic function of the set of integers with no more than $ 2h$ prime factors. It is possible to choose different functions $ \chi_-$ and $ \chi_+$ that satisfy the inequality (5) to obtain bounds similar to (4). The problem of optimal choice of these functions in general is very hard. For more detailed information on Brun's sieve and sieves in general one should consult the monographs [1,2,3].

References

1
George Greaves.
Sieves in number theory.
Springer, 2001.
Zbl 1003.11044.
2
H. Halberstam and H.-E. Richert.
Sieve methods, volume 4 of London Mathematical Society Monographs.
1974.
Zbl 0298.10026.
3
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.
4
Gérald Tenenbaum.
Introduction to Analytic and Probabilistic Number Theory, volume 46 of Cambridge Studies in Advanced Mathematics.
Cambridge Univ. Press.
Zbl 0831.11001.



"Brun's pure sieve" is owned by bbukh.
(view preamble | get metadata)

View style:

See Also: principle of inclusion-exclusion, sieve of Eratosthenes, Brun's constant, Bonferroni inequalities

Also defines:  combinatorial sieve
Keywords:  inclusion-exclusion, twin primes, Bonferroni inequalities
Log in to rate this entry.
(view current ratings)

Cross-references: bounds, functions, characteristic function, remainder, integers, inequality, right, right hand side, upper bound, terms, approximation, multiplicative function, applications, factors, side, partial sums, principle of inclusion-exclusion, prime factors, even number, Brun's constant, limit, converges, twin primes, reciprocals, sum, primes, number, estimates, sieve of Eratosthenes, extension
There are 3 references to this entry.

This is version 8 of Brun's pure sieve, born on 2004-02-21, modified 2008-02-17.
Object id is 5608, canonical name is BrunsPureSieve.
Accessed 7192 times total.

Classification:
AMS MSC11N35 (Number theory :: Multiplicative number theory :: Sieves)
 11N36 (Number theory :: Multiplicative number theory :: Applications of sieve methods)

Pending Errata and Addenda
None.
[ View all 1 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add example | add (any)