A refined Brun sieve

We improve the Brun sieve from the previous post to allow us to consider almost primes of various forms. We will prove for example the result that there are infinitely many $n$ such that $n$ and $n+2$ both have at most $7$ prime factors, and that every large enough even integer is the sum of two numbers both having at most $7$ prime factors.

Basic Brun sieve

In this post, we derive a simple form of Brun's combinatorial sieve that is already superior to the Eratosthenes-Legendre sieve and is sufficient to prove for example that the sum of the reciprocals of twin prime converges. We will see, however, that this sieve gives upper bounds that are slightly weaker than the optimal ones, such as $\pi(x)\ll x\cdot \frac{\log \log x}{\log x}$. In a later post, we will derive a more powerful Brun sieve that enables us to get rid of the extra factors $\log \log x$ and allows us to choose the sieve parameter $z$ to be a fixed power of $x$.

Eratosthenes-Legendre sieve

In this post, we present the basic idea of sieve methods and derive the simple Eratosthenes-Legendre sieve. Subsequently, there will be posts about more advanced sieve topics and their applications in number theory. Sieve theory offers tools for estimating various quantities in number theory (and also other branches of mathematics), in particular ones related to primes. The first idea of sieve theory was already invented by Eratosthenes around 2200 years ago. He devised a simple but rather efficient algorithm for finding all the primes up to $x$. Unfortunately, Eratosthenes' algorithm is so famous that the generality of the idea behind it is often forgotten. The idea allows us to estimate theoretically the number of primes up to $x$, or more generally many other similar sets of numbers, instead of taking a fixed $x$ such as $10^{10}$ and doing a boring computation. The simple but important idea can be formulated as follows : If we want to compute the number of those elements of a set $A\subset \mathbb{Z_+}$ with $|A|=x$ that have no prime factors below $z$, we should first take all the $x$ numbers, then subtract the number of even ones, subtract the number of multiples of $3$, subtract the number of multiples of $5$, add the number of multiples of $6$ (they were discarded twice), and so forth. The process goes through all the numbers $d$ that divide the product of the primes up to $z$ and whether we subtract or add depends on the parity of the number of prime divisors of $d$. It was probably Legendre who first wrote down this observation as a formula $-$ around 2000 years after Eratosthenes' algorithm $-$ and it is essentially the principle of inclusion and exclusion from combinatorics. Below we briefly discuss sieve methods in general. Then we derive the Eratosthenes-Legendre sieve and present some applications of it.

Elementary estimates for prime sums

In this post, we prove several results about prime sums that are not much weaker than what follows from the prime number theorem, but the proofs are quite simple and use elementary methods (even the prime number theorem actually has a proof using elementary methods, by Selberg and Erdös, but the proof is not simple). One of the results we show is Chebychev's assertion that $\frac{\pi(x)\log x}{x}$ is bounded from below and above by positive constants (that are not very far from each other), and as a corollary we get Bertrand's postulate, telling that the interval $[n,2n]$ always contains a prime number. We also prove Mertens' three theorems about sums and products related to primes. These results are nearly as good as what the prime number theorem gives. We will need these results in later posts about sieve theory.