Some estimates due to Richard Brent applied to the “high jumpers” problem.

Rob Harley

December 1994

Abstract

We apply the prime k-tuples conjecture and related estimates to the “high-jumpers” problem on gaps between successive primes.

1 Motivation

The following problem was proposed at the 1993 Western Number Theory conference:

93:03 (John Conway & Andrew Odlyzko) Call d a high-jumper if d occurs most frequently as the difference of consective primes ≤ x for some x (there may be several high-jumpers for a given x).

Example: x = 11: 2, 3, 5, 7, 11 gives 1, 2, 2, 4, so C(11) = {2}.

Conjecture: the only high-jumpers are 4 and the prime factorials 2, 6, 30, 210, 2310, · · · . Can one prove that high-jumpers tend to infinity? That any prime p divides all high-jumpers for x ≥ x_{0}(p)?

Remarks: A paragraph of UPINT2 reads as follows:

Victor Meally used the phrase prime deserts. He notes that below 373 the commonest gap is 2; below 467 there are 24 gaps of each of 2, 4 and 6; below 563 the commonest gap is 6, as it is between 10^{14} and 10^{14} + 10^{8} and probably also from 2 to 10^{14}. He asks: when does 30 take over as the commonest gap?

Dan Goldston provides the references:

Harry Nelson, Problem 654, J. Recreational Math., 10(1977-78) 212.

P. Erdös & E. G. Straus, Remarks on the difference between consecutive primes, Elem. Math., 35(1980) 115-118.

Erdös & Straus assumed a version of the Hardy-Littlewood prime k-tuple conjecture to show that high-jumpers go to infinity. The proposers can almost certainly show that the conjecture is true if they assume a uniform version of the k-tuple conjecture. This has not been written down yet, though.

Figure 1: Counts of the gaps 2, 4 and 6 between successive primes.

2 Background

We follow the notation of [Bre74]. Let P_{N}(r) denote the number of primes p ≤ N such that p + 2r is also prime and let Q_{N}(r) denote the number of primes p ≤ N such that the smallest prime greater than p is p + 2r. For instance, figure 1 shows Q_{N} for N ≤ 1000 and r = 1, 2 and 3.

In [HL22], G. H. Hardy and J. E. Littlewood conjectured an asymptotic form of P_{N}(1) which generalises naturally to the following prime k-tuples conjecture. Let m_{i} be distinct positive integers for i = 1 to s. Then the number of primes p ≤ N for which p + 2m_{i} is also prime for all i ∈ [1..s] is:

P_{N}(m_{1}, ⋯, m_{s}) ∼^{c} C(m_{1}, ⋯, m_{s}).li_{s+1}(N) (H-L)

as N → ∞, where:

C(m_{1}, ⋯, m_{s}) = 2^{s} ∏_{q} \frac{1 − w_{m}(q)/q}{(1 − 1/q)^{s+1}} ,

q runs over odd primes and w_{m}(q) counts the distinct residues of 0, m_{1}, ⋯, m_{s} modulo q. The logarithmic integrals li_{n}(x) are defined for n > 1 by:

li_{n}(x) = ∫_{0}^{x} \frac{dx}{(ln x)^{n}}

The singularity in the integrand at x = 1 is treated by taking the limit of ∫_{0}^{1−ε} + ∫_{1+ε}^{x} as ε → 0 from above.

B. H. Mayoh ([May68]) suggested the use of inclusion-exclusion to write Q_{N} in terms of several P_{N}’s and thus obtain an asymptotic form for Q_{N} subject to H-L:

Q_{N}(r) = ∑_{k=1}^{r}(−1)^{k−1} ∑_{0<m_{1}<···<m_{k−1}<r} P_{N}(m_{1}, ⋯, m_{k−1}, r)

Thus:

Q_{N}(r) ∼^{c} ∑_{k=1}^{r} A_{r,k}li_{k+1}(N)

as N → ∞, where:

A_{r,k} = (−1)^{k−1} ∑_{0<m_{1}<···<m_{k−1}<r} C(m_{1}, ⋯, m_{k−1}, r)

Note that li_{n}(x) ∈ Θ(x/(ln x)^{n}) hence (subject to H-L):

Q_{N}(r) = A_{r,1}.li_{2}(N) + o(li_{2}(N))

and that:

A_{r,1} = C(r) = 2c_{2} ∏_{q|r}(q − 1)/(q − 2)

where c_{2} is the twin-prime constant (see below). Thus H-L implies that a gap 2r which is a prime factorial will eventually become more frequent than all smaller gaps. Furthermore the high-jumpers go to infinity, as found by Erdös and Straus.

3 Contribution

In [Bre74] Richard Brent compared Q_{N}(r) with its asymptotic form given above, for various r. He observed a good agreement and found that the lower order terms improve the agreement, at least in the range he examined i.e., N ≤ 10^{9}.

We estimate Q_{N}(r) using the asymptotic form. We first compute the Hardy-Littlewood constants:

c_{k} = ∏_{q>k} \frac{1 − k/q}{(1 − 1/q)^{k}}

where q runs over odd primes. John W. Wrench, Jr. showed in [Wre61] that this could be done for c_{2} with the prime zeta function P (s) = ∑_{p} p^{−s} where p runs over all primes. We generalise Wrench’s method in the obvious way:

ln c_{k} = − ∑_{j=2}^{∞} \frac{k^{j} − k}{j} (P (j) − ∑_{p≤k} p^{−j})

where again p runs over primes. Hans Riesel describes in [Rie94] how to compute the prime zeta function via Möbius inversion as:

P (s) = ∑_{k=1}^{∞} \frac{μ(k)}{k} ln ζ(ks)

Even with these formulae, the Hardy-Littlewood constants are rather difficult to compute. Nevertheless we obtained them to high precision (100 decimals) in a reasonable amount of time (about 2 minutes each on a Sparc v8) with the pari/gp calculator of Henri Cohen et al. Table 1 shows the results with 50 decimals.

Next we computed the integers T_{r,k} which relate the Hardy-Littlewood constants to the A_{r,k} as described by Brent.

Finally, we need to calculate the logarithmic integrals. We derived the following generalization of the known series for li_{1} by elementary methods (integration of a series term by term and use of a recursion found by partial integration):

li_{n}(x) = (γ − H_{n−1} + ln ln x)/(n − 1)! + ∑_{k≥0∧k≠n−1} \frac{(ln x)^{k−n+1}}{k!(k − n + 1)}

where γ is Euler’s gamma (≃ 0.577) and H_{n} is the harmonic sum ∑_{k=1}^{n} 1/k.

Now we can find for which N the estimate for Q_{N}(15) passes that for Q_{N}(3). We find that it occurs at approximately 1.7 ∗ 10^{35}. Note that this result is at best a “guesstimate” of where the gap 30 passes the gap 6, since error bounds on the estimates are not known.

Table 1: Hardy-Littlewood constants to 50 decimals

 c_{2} = 0.66016 18158 46869 57392 78121 10014 55577 84326 23360 28473+
 c_{3} = 0.63516 63546 04271 20720 66965 91272 52241 73420 65687 33237+
 c_{4} = 0.30749 48787 58327 09312 33544 86071 07685 30221 78519 95066+
 c_{5} = 0.40987 48850 88236 47447 87812 12337 95527 78963 58013 25495-
 c_{6} = 0.18661 42973 58358 39665 69248 47944 18833 78400 73944 94559-
 c_{7} = 0.36943 75103 86498 68932 31907 49876 75077 70553 72913 89303+
 c_{8} = 0.23241 93345 86716 54620 61302 12670 66423 16017 58032 64641-
 c_{9} = 0.12017 12067 74741 72146 99894 64638 47738 34654 94082 65088-
c_{10} = 0.04180 40508 12181 65710 39748 72842 46412 05882 81078 159110-
c_{11} = 0.09453 08285 13547 15843 37971 55991 07208 84456 47523 053632-
c_{12} = 0.03539 32598 44463 70442 74555 96801 94105 85290 48910 978298+
c_{13} = 0.11170 39095 63244 95377 12104 54656 08232 51503 03622 12159-
c_{14} = 0.06284 46339 43607 42176 34598 50911 39350 53388 62666 290321-
c_{15} = 0.02924 41621 25091 30867 18534 29424 46031 81891 89081 789260-
c_{16} = 0.00922 81011 53092 67664 26576 54374 72155 09035 30929 0851726-

References

[Bre74] Richard P. Brent. The Distribution of Small Gaps Between Successive Primes. Mathematics of Computation, 28:315–324, 1974.

[HL22] G. H. Hardy and J. E. Littlewood. Some Problems of ‘Partitio Numerorum’ III: On the Expression of a Number as a Sum of Primes. Acta Mathematica, 44:1–70, 1922.

[May68] B. H. Mayoh. The second Goldbach conjecture revisited. BIT, 8:128–133, 1968.

[Wre61] John W. Wrench, Jr. Evaluation of Artin’s constant and the twin-prime constant. Mathematics of Computation, 15:396–398, 1961.

[Rie94] Hans Riesel. Prime Numbers and Computer Methods for Factorization, 2nd edition. Birkhaüser, Boston, 1994.