4
$\begingroup$

At children's school we learned about the Sieve of Eratosthenes for sieving our primes from an interval of natural numbers.

I was surprised to hear that "sieve methods" were used to make progress on the Twin Prime Conjecture, eg reading this Scientific American article (link).

Question: I can't seem to find an explanation (that I understand) of what these methods are, and how they have helped make progress in modern number theory.


Thoughts

The basic Sieve of Eratosthenes seems very intuitive but also impractical for deriving results about primes. So these other sieves must be meaningfully different. In that linked article they mention a modified sieve that only filters out numbers with large prime factors - again how and why is that helpful?

I am self-teaching and at the level of a first-year undergrad approx, so answers at that level would be helpful.

$\endgroup$
1

1 Answer 1

5
$\begingroup$

This is not at all my area but here is the very basic idea as I understand it; for more you can check out the Wikipedia article and Tao's expositions here or here.

"Sieve theory" refers to a collection of techniques in number theory that in some sense are extensions, variations, and generalizations of the sieve of Eratosthenes. But it would be more accurate to say that they are extensions, variations, and generalizations of the Legendre sieve, which is a quantitative refinement of the sieve of Eratosthenes.

Suppose we wanted to count the prime numbers between some large number $N$ and $2N$. If you wanted to use the sieve of Eratosthenes directly you'd have to write down all $2N$ integers between $1$ and $2N$, and then laboriously go through them one by one, and cross things out, etc. What the Legendre sieve does instead, effectively, is count how many integers in the interval $[N, 2N]$ are excluded by the sieve of Eratosthenes at each step. This gives us the freedom to take $N$ to be much larger than any number for which we could actually run the literal sieve of Eratosthenes itself.

For example, for any prime $p$, we can count how many numbers between $N$ and $2N$ are divisible by $p$; it is approximately $\frac{N}{p}$. So we can count how many numbers are not divisible by $p$, which is (approximately)

$$f_p(N) \approx \left( 1 - \frac{1}{p} \right) N + O(1)$$

where $O(1)$ means "up to a small constant error" (here, up to an error of at most $1$). What this says is that the probability that a random number between $N$ and $2N$ is not divisible by $p$ is approximately (if $p$ is not too large compared to $N$) $1 - \frac{1}{p}$, which should make sense.

Now we consider two distinct primes $p, q$. We can count how many numbers are divisible by $p$ as above, or by $q$. We can also count how many numbers are divisible by both $p$ and $q$ and it is approximately $\frac{N}{pq}$. By inclusion-exclusion it follows that we can count how many numbers are divisible by neither $p$ nor $q$, approximately:

$$\begin{align*} f_{p, q}(N) &\approx N - \frac{N}{p} - \frac{N}{q} + \frac{N}{pq} + O(1) \\ &\approx \left( 1 - \frac{1}{p} \right) \left( 1 - \frac{1}{q} \right) N + O(1) \end{align*}$$

where now the small constant error $O(1)$ is at most $3$. What this says is that the probability that a random number between $N$ and $2N$ is not divisible by $p$ or $q$ is approximately (if $p, q$ are not too large compared to $N$) $\left( 1 - \frac{1}{p} \right) \left( 1 - \frac{1}{q} \right)$, which should again make sense; this is saying that the events of a number being divisible by two distinct primes are independent in the statistical sense.

We can keep going like this with any fixed finite set $p_1, \dots p_k$ of primes and we'll get an expression that counts how many numbers between $N$ and $2N$ are not divisible by any of them, although the result involves many terms and because we haven't been careful about the error it could be as large as $2^k$. If $N$ is much larger than $p_1, \dots p_k$ and $2^k$ this is fine. But what we would really like to do in order to count primes is actually to take our set of primes to be all primes between $1$ and $N$ (really between $1$ and $\sqrt{2N}$ would do it), since then the numbers between $N$ and $2N$ relatively prime to all smaller primes would be exactly the primes. However this would make the error potentially much larger than $N$. This is not fine anymore!

But let's pretend it's still fine; what do we get? We get that the number of primes between $N$ and $2N$ is """approximately"""

$$f(N) \approx \prod_{p < N} \left( 1 - \frac{1}{p} \right) N + \text{???}$$

where the $???$ is to emphasize that we really have not controlled the error term at all so we have proven nothing, everything from here is heuristic. It's a nice calculation which I won't get into here to show that this product over primes grows roughly like $\frac{1}{\ln N}$, which gives """approximately"""

$$f(N) \approx \frac{N}{\ln N} + \text{???}$$

and what we get is an extremely sketchy heuristic version of the prime number theorem.

The amazing thing is that despite the fact that we've been so careless about the error terms in this argument it gave the correct asymptotic answer anyway. Moreover, much more careful, elaborate, subtle, general versions of this argument, with real estimates on the the error terms, do actually work and can be used to deduce highly nontrivial facts about primes and related sets like twin primes. And that's what sieve theory is, probably.

$\endgroup$
2
  • $\begingroup$ Thanks - this is very helpful. I will need to read more about the Legendre sieve. I do have a follow up question - how does one estimate the error term? Why is it "at most 1" and "at most 3" in the above examples? $\endgroup$
    – Penelope
    Commented Jun 27 at 10:53
  • 1
    $\begingroup$ @Penelope: you might need to restrict the interval to be $(N, 2N]$ to get those exact numbers (so that there are $N$ numbers in the interval). In the estimate above I said the number of integers in the interval divisible by $p$ is approximately $\frac{N}{p}$. That's correct if $p \mid N$. Otherwise, that isn't an integer but you can show that the right number must be either the integer right above it or the integer right below it, either of which differs from it by at most $1$. In the second estimate the same idea applies to each of the terms $\frac{N}{p}, \frac{N}{q}, \frac{N}{pq}$. $\endgroup$ Commented Jun 27 at 15:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .