5.5.3 Explicit estimates

Sometimes, it is useful to have explicit estimates for π(x), as well as related

functions, like ‘(x) and the nth prime function pn . The following theorem

presents a number of bounds that have been proved without relying on any

unproved conjectures.

Theorem 5.21. We have:

x 1 x 3

, for x ≥ 59;

(i) 1+ < π(x) < 1+

log x 2 log x log x 2 log x

(ii) n(log n + log log n ’ 3/2) < pn < n(log n + log log n ’ 1/2),

for n ≥ 20;

(iii) x(1 ’ 1/(2 log x)) < ‘(x) < x(1 + 1/(2 log x)), for x ≥ 563;

1 1

(iv) log log x + A ’ < 1/p < log log x + A + ,

2(log x)2 2(log x)2

p¤x

for x ≥ 286, where A ≈ 0.261497212847643;

B1 1 1 B1 1

1’ 1’

(v) < < 1+ ,

2(log x)2 2(log x)2

log x p log x

p¤x

for x ≥ 285, where B1 ≈ 0.561459483566885.

Proof. Literature”see §5.6. 2

5.5.4 Primes in arithmetic progressions

The arithmetic progression of odd numbers 1, 3, 5, . . . contains in¬nitely

many primes, and it is natural to ask if other arithmetic progressions do

as well. An arithmetic progression with ¬rst term a and common di¬erence

d consists of all integers of the form

md + a, m = 0, 1, 2, . . . .

92 The distribution of primes

If d and a have a common factor c > 1, then every term in the progression is

divisible by c, and so there can be no more than one prime in the progression.

So a necessary condition for the existence of in¬nitely many primes p with

p ≡ a (mod d) is that gcd(d, a) = 1. A famous theorem due to Dirichlet

states that this is a su¬cient condition as well.

Theorem 5.22 (Dirichlet™s theorem). For any positive integer d and

any integer a relatively prime to d, there are in¬nitely many primes p with

p ≡ a (mod d).

Proof. Literature”see §5.6. 2

We can also ask about the density of primes in arithmetic progressions.

One might expect that for a ¬xed value of d, the primes are distributed

in roughly equal measure among the φ(d) di¬erent residue classes [a]d with

gcd(a, d) = 1. This is in fact the case. To formulate such assertions, we

de¬ne π(x; d, a) to be the number of primes p up to x with p ≡ a (mod d).

Theorem 5.23. Let d > 0 be a ¬xed integer, and let a ∈ Z be relatively

prime to d. Then

x

π(x; d, a) ∼ .

φ(d) log x

Proof. Literature”see §5.6. 2

The above theorem is only applicable in the case where d is ¬xed and

x ’ ∞. But what if we want an estimate on the number of primes p up to

x with p ≡ a (mod d), where x is, say, a ¬xed power of d? Theorem 5.23

does not help us here. The following conjecture does, however:

Conjecture 5.24. For any real x ≥ 2, integer d ≥ 2, and a ∈ Z relatively

prime to d, we have

li(x)

¤ x1/2 (log x + 2 log d).

π(x; d, a) ’

φ(d)

The above conjecture is in fact a consequence of a generalization of the

Riemann hypothesis ”see §5.6.

Exercise 5.22. Assuming Conjecture 5.24, show that for all ±, , with 0 <

± < 1/2 and 0 < < 1, there exists an x0 , such that for all x > x0 , for all

d ∈ Z with 2 ¤ d ¤ x± , and for all a ∈ Z relatively prime to d, the number

of primes p ¤ x such that p ≡ a (mod d) is at least (1 ’ ) li(x)/φ(d) and at

most (1 + ) li(x)/φ(d).

It is an open problem to prove an unconditional density result analogous

5.5 The prime number theorem . . . and beyond 93

to Exercise 5.22 for any positive exponent ±. The following, however, is

known:

Theorem 5.25. There exists a constant c such that for all integer d ≥ 2

and a ∈ Z relatively prime to d, the least prime p with p ≡ a (mod d) is at

most cd11/2 .

Proof. Literature”see §5.6. 2

5.5.5 Sophie Germain primes

A Sophie Germain prime is a prime p such that 2p + 1 is also prime.

Such primes are actually useful in a number of practical applications, and

so we discuss them brie¬‚y here.

It is an open problem to prove (or disprove) that there are in¬nitely

many Sophie Germain primes. However, numerical evidence, and heuristic

arguments, strongly suggest not only that there are in¬nitely many such

primes, but also a fairly precise estimate on the density of such primes.

Let π — (x) denote the number of Sophie Germain primes up to x.

Conjecture 5.26. We have

x

π — (x) ∼ C ,

(log x)2

where C is the constant

q(q ’ 2)

≈ 1.32032,

C := 2

(q ’ 1)2

q>2

and the product is over all primes q > 2.

The above conjecture is a special case of a more general conjecture, known

as Hypothesis H. We can formulate a special case of Hypothesis H (which

includes Conjecture 5.26), as follows:

Conjecture 5.27. Let (a1 , b1 ), . . . , (ak , bk ) be distinct pairs of integers such

that ai > 0, and for all primes p, there exists an integer m such that

k

(mai + bi ) ≡ 0 (mod p).

i=1

Let P (x) be the number of integers m up to x such that mai + bi are simul-

taneously prime for i = 1, . . . , k. Then

x

P (x) ∼ D ,

(log x)k

94 The distribution of primes

where

’k

1 ω(p)

1’ 1’

D := ,

p p

p

the product being over all primes p, and ω(p) being the number of distinct

solutions m modulo p to the congruence

k

(mai + bi ) ≡ 0 (mod p).

i=1

The above conjecture also includes (a strong version of) the famous twin

primes conjecture as a special case: the number of primes p up to x such

that p + 2 is also prime is ∼ Cx/(log x)2 , where C is the same constant as

in Conjecture 5.26.

Exercise 5.23. Show that the constant C appearing in Conjecture 5.26

satis¬es

2

2C = B2 /B1 ,

where B1 and B2 are the constants from Exercises 5.14 and 5.15.