Sifting the Primes

Gihan Marasingha University of Oxford

18 March 2005 Irreducible forms:

q_{1}(x, y) := a_{1}x^{2} + 2b_{1}xy + c_{1}y^{2}, q_{2}(x, y) := a_{2}x^{2} + 2b_{2}xy + c_{2}y^{2},

a_{i}, b_{i}, c_{i} ∈ ℤ. Variety V defined by:

V : \begin{matrix}q_{1}(x, y) = u^{2} + v^{2} \\ q_{2}(x, y) = s^{2} + t^{2} \end{matrix}

The Sieve of Eratosthenes

2 3 4 5 6 7
8 9 10 11 12 13
14 15 16 17 18 19
20 21 22 23 24 25
26 27 28 29 30 31
32 33 34 35 36 37

� � � � �

� � � � � �

� � � Prime numbers n ≤ N. If n is composite, then it has a prime factor p with

p ≤ √n.

Thus, having struck out multiples of primes p ≤ √N, we’ve extinguished all the composite numbers less that N.

2-a

The Sieve of Eratosthenes–Legendre π(N) := the number of primes p ≤ N.

S(N, r) := #{n ≤ N : 2, 3, 5, …, p_{r} ∤ n}, where p_{r} < N is the r-th prime. Then we have the relationship:

π(N) ≤ p_{r} + S(N, r).

Reason: suppose p counted by π(N), so that p ≤ N. Either p ≤ p_{r} or p > p_{r}. In the first case, p ∈ {1, …, p_{r}}, so p is counted by p_{r}, otherwise p is counted by S(N, r). Define

N_{k} := #{n ≤ N : k|n},

then

S(N, r) = N − N_{2} − N_{3} − … − N_{p_{r}}
+ N_{6} + N_{10} + … + N_{p_{i}p_{j}}
− ∑ N_{p_{i}p_{j}p_{k}} + … ± N_{p_{1}...p_{r}}

Now N_{k} counts k, 2k, 3k, … qk where qk ≤ N < (q + 1)k, so

N_{k} ≤ \frac{N}{k} < N_{k} + 1.

S(N, r) = N − \frac{N}{2} − \frac{N}{3} − … − \frac{N}{p_{r}}

+ \frac{N}{6} + \frac{N}{10} + … + \frac{N}{p_{i}p_{j}}

− ∑ \frac{N}{p_{i}p_{j}p_{k}} + … ± \frac{N}{p_{1} … p_{r}} + error ,

where |error | ≤ 2^{r} ≤ 2^{p_{r}}. We’ll write error= O(2^{p_{r}}), where f(n) = O(g(n)) means that there exists a constant C such that |f(n)| ≤ Cg(n). In our case C = 1. So

S = N (1 − _{i≤r}^{∑} \frac{1}{p_{i}} + _{i≠j≤r}^{∑} \frac{1}{p_{i}p_{j}} − … ± \frac{1}{p_{1} … p_{r}} )

+ O(2^{p_{r}}).

= N r ; ∏ ; i=1 (1 − \frac{1}{p_{i}}) + O(2^{p_{r}})

Notation: f(n) ∼ g(n) means that f(n)/g(n) → 1 as n → ∞.

Fact: there is a constant C such that

_{p<z}^{∏} (1 − \frac{1}{p}) ∼ C \frac{1}{log z}.

Choose r such that p_{r} < log N ≤ p_{r+1} , then

S(N, r) = N _{p<log N}^{∏} (1 − \frac{1}{p}) + O(2^{log N})

∼ C \frac{N}{log log N} + N^{log 2}

= O(\frac{N}{log log N} + N^{0.7} )

= O(\frac{N}{log log N}).

Thus:

π(N) ≤ S(N, r) + p_{r} = O(\frac{N}{log log N} + log N)

= O(\frac{N}{log log N}).

Theorem (Hadamard, de la Vallée Poussin, 1896).

π(N) ∼ \frac{N}{log N} .

Theorem (Hadamard, de la Vallée Poussin, 1896).

π(N) ∼ \frac{N}{log N} .

Conjecture (Goldbach, 1750). Let N be an even number greater that 2, then

N = p + q,

for some primes p and q.

How many representations? That is what is

#{p ≤ N : N − p is prime }?

Heuristically, it’s

_{p≤N}^{∑} prob. that N − p is prime

≈ _{p≤N}^{∑} \frac{1}{log (N − p)}

≈ _{p≤N}^{∑} \frac{1}{log N}

≈ \frac{1}{log N} π(N) ∼ \frac{1}{log N} \frac{N}{log N} = \frac{N}{(log N)^{2}} .

Definition: We say n ∈ ℕ is a k-almost prime and write that n is P_{k} if n has at most k prime factors. Theorem (Chen Jing-Run, 1974). For all sufficiently large even N, one has that

N = p + P_{2},

for p a prime. More precisely, there exists a (computable) constant C such that for all sufficiently large even N,

|\{p : p ≤ N, N − p = P_{2}\}| > C \frac{N}{(log N)^{2}} .

Idea: Get a good lower bound for representations N = p+P_{3} then take away the representations N = p + p_{1}p_{2}p_{3} by deducing an upper bound. What’s left are the representations N = p + P_{2}.

Essentially, Chen is interested in calculating a lower bound for the number of 2-almost primes in the set

A := {N − p : p ≠ N},

much as in our heuristic development of the Goldbach conjecture. Chen’s primary innovation in the solution of this problem was the “reversal of rôles”, with which he relates |A| to |B|, where

B := { N − p_{1}p_{2}p_{3} : p_{1}p_{2}p_{3} < N,

N^{1/10} ≤ p_{1} < N^{1/3} ≤ p_{2} < p_{3}},

so that |B| refers to the number of representations of N − p as the sum of a prime and a product of exactly three primes.

It is an upper bound for the number of primes in B which is ‘taken away’ from the number of representations N = p + P_{3} to provide our lower bound for the number of almost prime in A.

Conjecture (Twin Primes). There exist infinitely many primes p such that p+2 is prime. Theorem (Chen Jing-Run, 1974). Let h be an even natural number. Then there exist infinitely many primes p such that

p + h = P_{2}.

Theorem (Brun, 1912). The sum

∑ ; \begin{matrix}p \\ p+2 prime \end{matrix} \frac{1}{p} + \frac{1}{p + 2}

is convergent, its value being referred to as Brun’s constant.

1995: Thomas Nicely computed prime twins up to 10^{14} , and found a bug in the Intel Pentium!

Conjecture (Euler, 1752). There exist infinitely many primes p of the form p = x^{2} +1. Theorem (Dirichlet, 1837). If a, b are coprime integers, then there exist infinitely many primes p of the form

p = ax + b.

Hypothesis H (Schinzel, Sierpinski, 1958). Let F_{1}(x), …, F_{n}(x) be distinct irreducible polynomials with integer coefficients, then under a certain condition on the product, there exist infinitely many x such that each F_{i}(x) is prime.

Eratosthenes–Legendre: primes in A := {n : n ≤ N}. Introduced N_{k} := |A_{k}| with A_{k} := {n ≤ N : k|n}. Approximated N_{k} by N/k and found R_{k} = N_{k} − N/k is bounded by |R_{k}| ≤ 1. Theorem (Halberstam & Richert, 1972). Let A be a set of integers with |A| ≈ X. Then, under certain conditions, one can find constants r ∈ ℕ, κ, δ > 0 and C ≥ 1 such that

|\{P_{r} : P_{r} ∈ A\}| ≥ δ\frac{X}{(log X)^{κ}} (1 − \frac{C}{√log X} ) .

The crucial condition in the determination of the least number of almost primes r is a good bound for the error term R_{k}. We look for a condition something like:

_{d<X^{α}}^{∑} |R_{k}| ≤ C \frac{X}{(log X)^{κ}} .

If we can find an estimate with a large value of α, then we may correspondingly use a small value of r.

Theorem (H&R, 1972). Let Q_{1}, Q_{2} be irreducible quadratic polynomials over the integers such that Q_{1}Q_{2} has no fixed prime divisor, then there exist infinitely many integers n such that

Q_{1}(n)Q_{2}(n) = P_{9}.

Theorem (Iwaniec, 1972). Let F (x, y) be a quadratic polynomial. Then, under a certain simple condition on the coefficients, the number of primes p ≤ N represented by F (x, y) is of order N/(log N)^{3/2} .

Theorem (M, 2005). Let q_{1}, q_{2} be irreducible binary quadratic forms over the integers, then subject to certain conditions on the forms, then there exist infinitely many pairs of integers (n, m) such that

q_{1}(n, m)q_{2}(n, m) = P_{6}.

Old problem: investigate the variety

V : \begin{matrix}q_{1}(x, y) = u^{2} + v^{2} \\ q_{2}(x, y) = s^{2} + t^{2} \end{matrix}

Count N(X), the points (x, y, u, v, s, t) ∈ ℤ^{6} with |x|, |y| < X, and derive asymptotic formula as X → ∞.

In calculating the asymptotic formula, one needs to evaluate quantities of the type

_{k<X}^{∑} |R_{k}|,

as in Halberstam and Richert’s theorem.

More Questions:

Extend results of Marasingha? Pairs of irreducible cubic forms? Triples of quadratic forms?

There are sieve methods for calculating π(N) in time O(N^{2/3+ϵ} ), which don’t require the computation of all the primes, but it seems that to compute π_{2}(N) := the number of twin primes ≤ N, we need to compute all the twin primes, taking time O(N). Can we improve on this?