Prime k-tuples

Chapter 20 Prime $k$ -tuples

This chapter begins the fifth part of the course, in which we combine material from previous parts to study gaps between primes.

🔗

In this chapter, we review the work of Gallagher [6] in the direction of the Hardy–Littlewood

k

-tuples conjecture, a vast (and quantitative) generalization of the twin primes conjecture.

🔗

Section 20.1 The Hardy–Littlewood $k$ -tuples conjecture

🔗

Let

H

denote a

k

-tuple of distinct integers. What does one expect about the distribution of the integers

n

such that

n + h

is prime for each

h \in H ?

🔗

Here is a rather simple-minded guess. The prime number theorem suggests that if one chooses a random integer of size

x,

it will be prime with probability

1 / (\log x) .

If one then chooses

k

distinct integers of size

x,

and there is no obvious reason why they cannot all be prime, then one might expect them to be simultaneously prime with probability

\log^{- k} x,

and the number of such tuples with terms bounded by

x

should be asymptotic to

x \log^{- k} x,

with the constant 1.

🔗

However, this turns out not to be the correct constant, as is easily verified against experimental evidence in the case of twin primes. The reason is perhaps obvious: the facts that the different

n + h

are coprime to a fixed prime

p

are not independent, and one needs to account for this. Here is the recipe for doing so proposed by Hardy–Littlewood.

🔗

Definition 20.1.

🔗

Fix a prime

p .

The probability that

k

randomly chosen integers are all not divisible by

p

(1 - 1 / p)^{k} .

On the other hand, the probability that the

n + h

are all coprime to

p

1 - v_{H} (p) / p,

where

v_{H} (p)

is the number of residue classes modulo

p

represented by elements of

H .

We thus set

S (H) := \prod_{p} (1 - \frac{v_{H} (p)}{p}) {(1 - \frac{1}{p})}^{- k}

🔗

(called the singular series, because it occurs in the Hardy–Littlewood circle method as a series summed over singularities of some integral) and make the following conjecture of Hardy–Littlewood [11]. (The infinitude of the set of primes in question had been previously conjectured by Dickson [4].)

🔗

Conjecture 20.2. Hardy–Littlewood $k$ -tuples conjecture.

Suppose that

v_{H} (p) < p

for all

p .

Then the number of integers

n \leq x

such that

n + h

is prime for each

h \in H

is asymptotic to

S (H) x \log^{- k} x .

🔗

Remark 20.3.

v_{H} (p) = 0

for some

p,

then there is a trivial obstruction created by divisibility mod

p,

so you only get finitely many prime

k

-tuples of that shape. On the other hand, if

v_{H} (p) < p

for all

p,

then the product converges absolutely and so

S (H) > 0;

so there is no inconsistency here.

🔗

Remark 20.4.

It will be convenient later to adopt the convention that the definition of

S (H)

remains unchanged if

H

does not have distinct entries, even though this carries no new information.

🔗

Section 20.2 $k$ -tuples and prime gaps

🔗

If one is only interested in looking for primes which are close together, without specifying exactly what the gaps are, one could go back to the probabilistic model (attributed to Cramér, more famous for his rule for solving linear systems). It suggests that the distribution of

π (n + h) - π (n),

for

n \leq N

and

h \sim λ \log N

with

λ

fixed, should approach a Poisson distribution with parameter

λ

N \to \infty .

(This is consistent with the observation that

li (x)

is a better approximation of to

π (x)

than

\frac{x}{\log x};

see Exercise 8.4.1.)

🔗

The fact that this prediction follows from a suitably uniform version of the

k

-tuples conjecture is due to Gallagher. The theorem asserts that the fudge factor

S (H)

between the probabilistic model and the Hardy–Littlewood prediction averages out to 1, so that the prediction based on the probabilistic model is consistent with Hardy–Littlewood. (Per Remark 20.4 we allow tuples with repeated entries, but their overall contribution is

O (x^{k - 1})

and so does not affect anything.)

🔗

Theorem 20.5. Gallagher.

For

k

fixed and

x \to \infty,

we have

\sum_{H \in {1, \dots, x}^{k}} S (H) \sim x^{k} .

🔗

Proof.

We sketch of Gallagher's proof modulo a few details left as exercises. Throughout, keep

k

fixed.

Put

\begin{aligned} a (p, m) & = (1 - \frac{m}{p}) {(1 - \frac{1}{p})}^{- k} - 1 \\ a_{H} (p) & = a (p, v_{H} (p)) \end{aligned}

so that

S (H) = \prod_{p} (1 + a_{H} (p)) .

Extend

a

by multiplicativity to squarefree arguments

d,

so that

S (H) = \sum_{d} a_{H} (d)

with the sum on the right being absolutely convergent.

We can truncate the sum over

d

because for fixed

ϵ > 0,

we have (by Exercise 20.3.3) that

\begin{matrix} (20.2.1) & \sum_{H \in {1, \dots, x}^{k}} S (H) = \sum_{d \leq y} \sum_{H} a_{H} (d) + O (x^{k} (x y)^{ϵ} / y) \end{matrix}

with the constant depending only on

k, ϵ

and not on

x, y .

For any given

d,

we can rewrite the inner sum of (20.2.1) as a sum

\sum_{v} (\prod_{p | d} a (p, v (p))) f_{d} (x, v),

where

v

runs over vectors indexed by the prime factors of

d,

with

v (p) \in {1, \dots, p}

for each

p | d,

and

f_{d} (x, v)

counts

k

-tuples

H \in {1, \dots, x}^{r}

which occupy exactly

v (p)

residue classes modulo

p

for each

p | d .

Write

{\binom{a}{b}}

for the number of partitions of an

a

-element set into

b

unordered parts (Stirling number of the second kind). If we set

\begin{aligned} A (d) & = \sum_{v} \prod_{p | d} a (p, v (p)) (\binom{p}{v (p)}) v (p)! {\binom{k}{v (p)}} \\ B (d) & = \sum_{v} \prod_{p | d} | a (p, v (p)) | (\binom{p}{v (p)}) v (p)! {\binom{k}{v (p)}} \\ C (d) & = \sum_{v} \prod_{p | d} | a (p, v (p)) |, \end{aligned}

then

\begin{matrix} (20.2.2) & \sum_{H} a_{H} (d) = (x / d)^{k} A (d) + O ((x / d)^{k - 1} B (d)) + O (x^{k - 1} C (d)) . \end{matrix}

From this, plus the identities

\begin{aligned} (20.2.3) & \sum_{v = 1}^{p} (\binom{p}{v}) v! {\binom{k}{v}} & = p^{k} \\ (20.2.4) & \sum_{v = 1}^{p} v (\binom{p}{v}) v! {\binom{k}{v}} & = p^{k + 1} - (p - 1)^{k} p \end{aligned}

(see Exercise 20.3.5), it is not difficult to finish (see Exercise 20.3.6).

🔗

Exercises 20.3 Exercises

🔗

1.

Let

p_{1}, p_{2}, \dots

be the sequence of primes in ascending order. Prove that for any positive integer

k,

for

n = π (k),

the tuple

H = (p_{n + 1}, \dots, p_{n + k})

satisfies

S (H) > 0 .

🔗

2.

Prove that for

k

a positive integer,

\int_{2}^{x} \log^{- k} t d t \sim x \log^{- k} x .

🔗

3.

Prove (20.2.1).

Hint.

See the hint for Exercise 20.3.6.

🔗

4.

Prove (20.2.2).

Hint.

It might help to think in terms of counting lattice points.

🔗

5.

Prove the identities (20.2.3), (20.2.4).

🔗

6.

Complete the proof of Theorem 20.5.

Hint.

First use (20.2.3) and (20.2.4) to calculate

A (d) .

Then estimate

B (d)

and

C (d)

using the bound

| a (p, m) | \leq {\begin{cases} c (k) (p - 1)^{- 2} & m = k \\ c (k) (p - 1)^{- 1} & m < k; \end{cases}

note that the constant

c (k)

depends on

k

but not on

p

m .

Finally, take

y = x^{1 / 2}

in (20.2.1).

🔗

7.

Use the Poisson distribution model to compute a predicted distribution for the ratio

(p_{n + 1} - p_{n}) / (\log p_{n}) .

Notes on analytic number theory

Search Results:

Chapter 20 Prime $k$ -tuples

Section 20.1 The Hardy–Littlewood $k$ -tuples conjecture

Definition 20.1.

Conjecture 20.2. Hardy–Littlewood $k$ -tuples conjecture.

Remark 20.3.

Remark 20.4.

Section 20.2 $k$ -tuples and prime gaps

Theorem 20.5. Gallagher.

Proof.

Exercises 20.3 Exercises

1.

2.

3.

4.

5.

6.

7.

Chapter 20 Prime k-tuples

Section 20.1 The Hardy–Littlewood k-tuples conjecture

Definition 20.1.

Conjecture 20.2. Hardy–Littlewood k-tuples conjecture.

Remark 20.3.

Remark 20.4.

Section 20.2 k-tuples and prime gaps

Theorem 20.5. Gallagher.

Proof.

Exercises 20.3 Exercises

1.

2.

3.

4.

5.

6.

7.

Chapter 20 Prime $k$ -tuples

Section 20.1 The Hardy–Littlewood $k$ -tuples conjecture

Conjecture 20.2. Hardy–Littlewood $k$ -tuples conjecture.

Section 20.2 $k$ -tuples and prime gaps