ON CLUSTER PRIMES

CHRISTIAN ELSHOLTZ

Abstract. In this note we prove a conjecture by Blecksmith, Erdős, and Selfridge on the number of cluster primes. A prime p is said to be a cluster prime if every positive even integer 2r ≤ p − 3 can be written as a difference of two primes, 2r = q − q′, where q′ ≤ q ≤ p. Let π_{C}(x) denote the number of cluster primes below x. Then the following estimate holds:

π_{C}(x) = O ( \frac{x}{exp( \frac{1}{60} (log log x)^{2})} ) .

1. Introduction

Blecksmith, Erdős and Selfridge [1] defined a prime p > 2 to be a cluster prime if every positive even integer 2r ≤ p − 3 can be written as a difference of two primes, 2r = q − q′, where q′ ≤ q ≤ p. It is an open question, whether there exists infinitely many cluster primes. Guy ([3], section C1) attributes this question to Erdős.

Blecksmith et. al. [1] proved that the counting function π_{C}(x) of cluster primes can be bounded from above: for all positive s,

π_{C}(x) = O_{s} (\frac{x}{(log x)^{s}} ) .

It is the purpose of this note to prove a better bound, i.e. that cluster primes are rare. This new bound was indeed conjectured by Blecksmith et. al. [1].

Theorem. The number π_{C}(x) of cluster primes below x is bounded by

π_{C}(x) = O (\frac{x}{exp(\frac{1}{60}(log log x)^{2})}) .

As Blecksmith, Erdős and Selfridge show, the problem is related to the prime k-tuple conjecture. It is proved that for a cluster prime p the interval [p−t, p) must contain sufficiently many primes, which explains the name cluster prime. This allows us to apply an upper bound sieve. In Blecksmith et.al. [1], Brun’s version of the small sieve is used. The principal problem is that the authors arrive at a constant M, of which the dependence on the sieve dimension s is not at all clear. This prohibits taking an increasing s.

Filaseta [2] mentioned that an application of Hooley’s almost pure sieve proves the result with s = ε log log log x, thus obtaining an upper bound of π_{C}(x) =

O (\frac{x}{exp(a loglog x logloglog x)}) for some positive constant a.

Date: TO BE FILLED.

1991 Mathematics Subject Classification. Primary 11N05, 11N36; Secondary 11A41.

Key words and phrases. Prime tuples, sieve methods.

In this note we apply the large sieve method, due to Montgomery [4]. In fact, we make use of the following lemma due to Vaughan [6], which is an elaborated version of the large sieve method, perfectly fitting to our application.

Lemma 1 (Montgomery [4], Vaughan [6]). Let P denote the set of primes and let ω : P → ℕ with 0 ≤ ω(p) ≤ p − 1. Let A ⊂ [1, N] denote a set of integers which lies outside ω(p) residue classes modulo the prime p. Then the number A(x) of elements n ∈ A, n ≤ x satisfies

A(x) ≤ \frac{2x}{L}, where L = ∑_{q≤x^{1/2}} μ^{2}(q) ∏_{p|q} \frac{ω(p)}{p − ω(p)}.

Moreover, for L the following estimate holds:

L ≥ max_{m∈ℕ} exp (m log (\frac{1}{m} ∑_{p≤x^{1/(2m)}} \frac{ω(p)}{p})) .

2. Proof of the Theorem

If p is a cluster prime, then the even integers like p−9 or p−15 are the difference of two primes with q, q′ ≤ p. In particular, there must be a prime in the interval [p − 6, p). More generally, an even integer 2r ∈ [p − t, p − 3] must be represented by a prime q ∈ [p − t, p] and a prime q′ ∈ [1, t]. By the prime number theorem the number of primes in [1, t] is (1 + o(1))\frac{t}{log t}. We see that for any ε > 0 there must be at least s := (\frac{1}{2} − ε) log t primes in [p − t, p).

Since the average gap between primes of size x is about log x we see that this is a useful criterion, for t = O ((log x)^{δ}) (with 0 < δ < 1). On the contrary, for sufficiently large t one expects that an interval of length t has about \frac{t}{log t} primes so that this criterion becomes useless.

There are (trivially) at most \binom{t}{s} possibilities to place s primes in an interval of length t. For any pattern of s primes in [p−t, p) we will give an upper bound on the number of prime s-tuples below x. This bound will not depend on the particular pattern. So, multiplying this bound by the upper bound for the number of patterns, \binom{t}{s}, gives an upper bound on the number of p ≤ x such that the interval [p − t, p) contains (at least) s primes.

We prove the following lemma:

Lemma 2. Let δ = \frac{1}{2e} and t = (log x)^{δ}. Let ε be a sufficiently small positive constant. Let A(x) denote the number of integers n ≤ x such that the interval [n − t, n) contains at least s = (\frac{1}{2} − ε) log t primes. Then the following estimate holds:

A(x) = O (\frac{x}{exp ((\frac{1}{4e^{2}} − ε)(log log x)^{2})}) .

We fix a particular pattern a_{1} < a_{2} < ⋯ < a_{s}. If all n − a_{i} are prime simultaneously, then the integers n avoid the residue classes a_{i} mod p for p ≤ n − t. If p > t, then the number of forbidden classes is ω(p) = s.

We choose m = ⌈δ^{2}(log log x)^{2}⌉, where x is large. With y = x^{1/(2m)} we have log log y = log log x − 2 log log log x + O(1). So we find that

∑_{p≤y} \frac{ω(p)}{p} ≥ ∑_{t≤p≤y} \frac{ω(p)}{p}

≥ s(log log y − log log t + o(1))

≥ (\frac{1}{2} − ε)δ(log log x)(log log x − 3 log log log x + O(1))

≥ (\frac{1}{2} − 2ε)δ(log log x)^{2}.

This implies the estimate

L ≥ exp (⌈δ^{2}(log log x)^{2}⌉ log (\frac{1}{⌈δ^{2}(log log x)^{2}⌉}δ(\frac{1}{2} − 2ε)(log log x)^{2}))

≥ exp (δ^{2}(log log x)^{2} log (\frac{1}{δ} (\frac{1}{2} − 3ε)))

≥ exp (δ^{2}(log log x)^{2} log(e − 6eε))

≥ exp (δ^{2}(1 − 7ε)(log log x)^{2})

≥ exp ((\frac{1}{4e^{2}} − ε) (log log x)^{2}) .

Therefore, for any fixed pattern a_{1} < a_{2} < ⋯ < a_{s} there are at most

\frac{2x}{exp((\frac{1}{4e^{2}} − ε)(log log x)^{2})}

values n ≤ x such that all n − a_{i} are prime. Thus the lemma is proved. To prove the theorem we only need to recall that

π_{C}(x) ≤ \binom{t}{s}\frac{2x}{exp(δ^{2}(1 − 7ε)(log log x)^{2})}.

Because of

\binom{t}{s} ≤ t^{s} ≤ exp ((\frac{1}{2} − ε)δ^{2}(log log x)^{2})

we find that

π_{C}(x) = O (\frac{x}{exp((\frac{1}{8e^{2}} − ε)(log log x)^{2})}) .

3. Further comments

No serious attempt has been made at optimizing the constant \frac{1}{60} or \frac{1}{8e^{2}} − ε that appears in the theorem. Some improvement is possible. We only mention the following: Vaughan’s argument in Lemma 1 can be refined to

L ≥ max_{m∈ℕ} exp (m log (\frac{e − ε_{m}}{m} ∑_{p≤x^{1/(2m)}} \frac{ω(p)}{p})) .

Here the ε_{m} are positive constants that tend to 0 as m goes to infinity. This allows to use c_{1} ≈ \frac{δ}{2} and δ ≈ \frac{1}{2} and proves the theorem with \frac{1}{8} − ε instead of \frac{1}{60}.

The author would like to thank the referees for helpful comments.

References

[1] Blecksmith, R.; Erdős, P.; Selfridge, J. L.: Cluster primes. Amer. Math. Monthly 106, (1999), 43-48.

[2] Elsholtz, C.: Combinatorial prime number theory - a study of the gap structure of the set of primes, Habilitationsschrift, Technische Universität Clausthal, 2002.

[3] Filaseta, M.: Review of [1] in the Mathematical Reviews: 2000a:11126.

[4] Guy, R.K.: Unsolved problems in number theory, 2nd edition, Springer 1994, New York, Berlin, Heidelberg.

[5] Montgomery, H. L., The analytic principle of the large sieve, Bull. Amer. Math. Soc. 84 (1978), 547–567.

[6] Peterson, I. The scarcity of cluster primes. Science News 6, February 1999, page 95.

[7] Vaughan, R. C., Some applications of Montgomery’s sieve, J. Number Theory 5 (1973), 64–79.

Institut für Mathematik, TU Clausthal, Erzstrasse 1, D-38678 Clausthal-Zellerfeld, Germany

 E-mail address: elsholtz@math.tu-clausthal.de