Brun’s pure sieve

In the first quarter of the twentieth century Viggo Brun developedan extension of the sieve of Eratosthenes that yielded goodestimates on the number of elements of a set $𝒜$ thatare not divisible (http://planetmath.org/Divisibility) by any of the primes $p_1,\mathrm{\dots },p_k$ providedonly that $𝒜$ is “sufficiently regularly distributed”modulo these primes. That allowed him to prove that the sum ofreciprocals of twin primes converges (the limit is now known asBrun’s constant), and that every sufficiently large even number isa sum of two numbers each having at most $9$ prime factors. Inwhat follows we describe the simplest form of Brun’s sieve, knownas Brun’s pure sieve.

The sieve of Eratosthenes (http://planetmath.org/SieveOfEratosthenes2) isbased on the principle of inclusion-exclusion in the form

${\displaystyle \sum _{n\in 𝒜}}{\displaystyle \sum _{\begin{array}{c}{p}_1\nmid n\\ \mathrm{\dots }\\ p_k\nmid n\end{array}}}1$$={\displaystyle \sum _{n\in 𝒜}}{\displaystyle \sum _{(n,p_1\mathrm{\cdots }{p}_k)=1}}1={\displaystyle \sum _{n\in 𝒜}}{\displaystyle \sum _{d\mid (n,p_1\mathrm{\cdots }{p}_k)}}\mu (d)$

$={\displaystyle \sum _{d\mid p_1\mathrm{\cdots }{p}_k}}\mu (d){\displaystyle \sum _{\begin{array}{c}n\mid 𝒜\\ d\mid n\end{array}}}1={\displaystyle \sum _{d\mid p_1\mathrm{\cdots }{p}_k}}\mu (d)A_d$

$=A_1-{\displaystyle \sum _{p\mid p_1\mathrm{\cdots }{p}_k}}{A}_p+{\displaystyle \sum _{pq\mid p_1\mathrm{\cdots }{p}_k}}{A}_{pq}+\mathrm{\cdots }.$(1)

Brun’s sieve is based on the observation that the partial sumsof (1) alternatively overcount andundercount the number of elements of $𝒜$ counted by theleft side, that is,

$$\sum _{\begin{array}{c}d\mid p_1\mathrm{\cdots }{p}_k\\ \nu (d)\le 2h-1\end{array}}\mu (d)A_d\le \sum _{n\in 𝒜}\sum _{\begin{array}{c}{p}_1\nmid n\\ \mathrm{\dots }\\ p_k\nmid n\end{array}}1\le \sum _{\begin{array}{c}d\mid p_1\mathrm{\cdots }{p}_k\\ \nu (d)\le 2h\end{array}}\mu (d)A_d$$(2)

where $\nu (d)$ denotes the number of prime (http://planetmath.org/Prime) factors of $d$. Inapplications $A_d$ can usually be approximated by a multiple of amultiplicative function, that is,

$$A_d=Xw(d)/d+R_d$$

where $w(d)$ is some multiplicative function of $d$, and $R_d$ issmall compared to $Xw(d)/d$. Then the estimatein (2) takes the form

${\displaystyle \sum _{\begin{array}{c}d\mid p_1\mathrm{\cdots }{p}_k\\ \nu (d)\le t\end{array}}}\mu (d)A_d$$={\displaystyle \sum _{\begin{array}{c}d\mid p_1\mathrm{\cdots }{p}_k\\ \nu (d)\le t\end{array}}}\mu (d)(Xw(d)/d+R_d)$

$=X{\displaystyle \sum _{\begin{array}{c}d\mid p_1\mathrm{\cdots }{p}_k\\ \nu (d)\le t\end{array}}}\mu (d){\displaystyle \frac{w(d)}{d}}+O\left({\displaystyle \sum _{\begin{array}{c}d\mid p_1\mathrm{\cdots }{p}_k\\ \nu (d)\le t\end{array}}}{R}_d\right)$(3)

If the truncated sum is a good approximation to the full sum, thenthis formula is an improvement over thesieve of Eratosthenes (http://planetmath.org/SieveOfEratosthenes2) because the sum over errorterms $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 _{\begin{array}{c}d\mid p_1\mathrm{\cdots }{p}_k\\ \nu (d)\le t\end{array}}}\mu (d){\displaystyle \frac{w(d)}{d}}$$={\displaystyle \sum _{d\mid p_1\mathrm{\cdots }{p}_k}}\mu (d){\displaystyle \frac{w(d)}{d}}+O\left({\displaystyle \sum _{\begin{array}{c}d\mid p_1\mathrm{\cdots }{p}_k\\ \nu (d)>t\end{array}}}{\displaystyle \frac{w(d)}{d}}\right)$

$={\displaystyle \sum _{d\mid p_1\mathrm{\cdots }{p}_k}}\mu (d){\displaystyle \frac{w(d)}{d}}+O\left({\displaystyle \sum _{d\mid p_1\mathrm{\cdots }{p}_k}}{\displaystyle \frac{w(d)}{d}}{u}^{\nu (d)-t}\right)$

$={\displaystyle \sum _{d\mid p_1\mathrm{\cdots }{p}_k}}\mu (d){\displaystyle \frac{w(d)}{d}}+O\left(u^{-t}{\displaystyle \sum _{d\mid p_1\mathrm{\cdots }{p}_k}}{\displaystyle \frac{w(d)}{d}}{u}^{\nu (d)}\right)$

and since the sum of a multiplicative function can bewritten as an Euler product, we get

$={\displaystyle \prod _{p\in 𝒫}}\left(1-{\displaystyle \frac{w(p)}{p}}\right)+O\left(u^{-t}{\displaystyle \prod _{p\in 𝒫}}\left(1+u{\displaystyle \frac{w(p)}{p}}\right)\right)$

$={\displaystyle \prod _{p\in 𝒫}}\left(1-{\displaystyle \frac{w(p)}{p}}\right)+O\left(u^{-t}{\displaystyle \prod _{p\in 𝒫}}{\left(1+{\displaystyle \frac{w(p)}{p}}\right)}^u\right)$

to minimize the error term we choose$u=t/{\sum }_{p\in 𝒫}\log (1+\frac{w(p)}{p})$, and get

$={\displaystyle \prod _{p\in 𝒫}}\left(1-{\displaystyle \frac{w(p)}{p}}\right)+O{\left({\displaystyle \frac{1}{t}}{\displaystyle \sum _{p\in 𝒫}}{\displaystyle \frac{w(p)}{p}}\right)}^t$

Combining this with (3) and (2) weobtain

$$\sum _{n\in 𝒜}\sum _{\begin{array}{c}{p}_1\nmid n\\ \mathrm{\dots }\\ p_k\nmid n\end{array}}1=X\prod _{p\in 𝒫}\left(1-\frac{w(p)}{p}\right)+X\cdot O{\left(\frac{1}{t}\sum _{p\in 𝒫}\frac{w(p)}{p}\right)}^t+O\left(\sum _{\begin{array}{c}d\mid p_1\mathrm{\cdots }{p}_k\\ \nu (d)\le t\end{array}}{R}_d\right)$$(4)

provided that $u=t/{\sum }_{p\in 𝒫}\log (1+\frac{w(p)}{p})\ge 1$.

Example. (Upper bound on the number of primes.) If we set$𝒫$ to be all the primes less $y$, and$𝒜=\{1,2,\mathrm{\dots },x\}$, then the right hand sideof (4) provides an upper bound for the number ofprimes between $y$ and $x$.

We have that $w(d)=1$ and $R_d\le 1$. The second error termin (4) has at most $y^t$ summands, and the firsterror term is bounded by ${(\frac{c}{t}\log \log y)}^t$ by Merten’stheorem. Thus, the estimate (4) becomes

$$\pi (x)-\pi (y)\le 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 primesnot exceeding $x$ we have to minimize the right side of theinequality 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

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

This inequality is stronger than the one obtained by anapplication of the sieve of Eratosthenes (http://planetmath.org/SieveOfEratosthenes2).

Example. (Upper bound on the number of twin primes.) If and $p\mid n(n+2)$, then the integers $n$ and $n+2$ cannotboth be primes. Let $𝒫$ be as above, and set$𝒜=\{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

$${\pi }_2(x)-{\pi }_2(y)\le 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}$ weobtain

$${\pi }_2(x)\le O\left(\frac{x{(\log \log x)}^2}{{(\log x)}^2}\right).$$

This is the original result for which Viggo Brun developed thesieve now bearing his name. This result can be put in followingstriking form:

Theorem.

The sum

$$\sum _{p,p+2\mathit{\text{ primes}}}\left(\frac{1}{p}+\frac{1}{p+2}\right)$$

converges.

General combinatorial sieve

The inequality (2) was based on the observationthat

$$\sum _{d\mid n}\mu (d){\chi }_{-}(d)\le \sum _{d\mid n}\mu (d)\le \sum _{d\mid n}\mu (d){\chi }_{+}(d)$$(5)

where ${\chi }_{-}$ is the characteristic function of the set ofintegers with no more than $2h-1$ prime factors, and ${\chi }_{+}$ isthe characteristic function of the set of integers with no morethan $2h$ prime factors. It is possible to choose differentfunctions ${\chi }_{-}$ and ${\chi }_{+}$ that satisfy theinequality (5) to obtain bounds similarto (4). The problem of optimal choice of thesefunctions in general is very hard. For more detailed informationon Brun’s sieve and sieves in general one should consult themonographs[1, 2, 3].