Upper Bounds for Prime Gaps Related to Firoozbakht’s Conjecture

Alexei Kourbatov 15127 NE 24th St., #578 Redmond, WA 98052 USA

                     akourbatov@gmail.com

Abstract We study two kinds of conjectural bounds for the prime gap after the kth prime p_{k}: (A) p_{k+1} < p_{k}^{1+1/k} and (B) p_{k+1} − p_{k} < log^{2} p_{k} − log p_{k} − b for k > 9. The upper bound (A) is equivalent to Firoozbakht’s conjecture. We prove that (A) implies (B) with b = 1; on the other hand, (B) with b = 1.17 implies (A). We also give other sufficient conditions for (A) that have the form (B) with b → 1 as k → ∞.

1 Introduction

In 1982 Firoozbakht proposed the following conjecture [6, p. 185]: Firoozbakht’s Conjecture. If p_{k} is the kth prime, the sequence (p_{k}^{1/k})_{k∈ℕ} is decreasing. Equivalently, for all k ≥ 1, the prime p_{k+1} is bounded by the inequality

p_{k+1} < p_{k}^{1+1/k}.  (1)

Several authors [7, 8, 10, 11] have observed that

• Firoozbakht’s conjecture (1) implies Cramér’s conjecture p_{k+1} − p_{k} = O(log^{2}p_{k}) [2].

• If conjecture (1) is true and k is large, then

p_{k+1} − p_{k} < log^{2} p_{k} − log p_{k}.  (2)

In Section 2 we prove that (1) implies a sharper bound than (2):

p_{k+1} − p_{k} < log^{2} p_{k} − log p_{k} − b for all k > 9,  (3)

with b = 1. If the exact value of k = π(p_{k}) is not available, then a violation of (2) or (3) might be used to disprove Firoozbakht’s conjecture (1). However, given a pair of primes p_{k}, p_{k+1}, the validity of (2) alone is not enough for the verification of (1). We discuss this in more detail in Section 3; see also [4]. In Section 4 we prove that (3) with b = 1.17 implies (1); we also give other sufficient conditions for (1). Probabilistic considerations [2, 3, 4, OEIS \underline{A235402}] suggest that bounds (1), (2), (3) hold for almost all maximal gaps between primes.

2 A corollary of Firoozbakht’s conjecture

Theorem 1. If conjecture (1) is true, then

p_{k+1} − p_{k} < log^{2} p_{k} − log p_{k} − 1 for all k > 9.

Proof. It is easy to check that

\frac{x + log^{2} x}{log x − 1 − \frac{1}{log x}} < \frac{x}{log x − 1 − \frac{1}{log x} − \frac{1}{log^{2} x}} for x ≥ 285967.  (4)

Let π(x) denote the prime-counting function. From Axler [1, Corollary 3.6] we have

\frac{x}{log x − 1 − \frac{1}{log x} − \frac{1}{log^{2} x}} < π(x) for x ≥ 1772201.  (5)

Taking the log of both sides of (1) we find that Firoozbakht’s conjecture (1) is equivalent to

k < \frac{log p_{k}}{log p_{k+1} − log p_{k}} .  (6)

Let k ≥ 133115. Then p_{k} ≥ 1772201. By setting x = p_{k} in (4) and (5), we see that inequalities (4), (5), (6) form a chain. Therefore, if Firoozbakht’s conjecture is true, then

\frac{p_{k} + log^{2} p_{k}}{log p_{k} − 1 − \frac{1}{log p_{k}}} < \frac{log p_{k}}{log p_{k+1} − log p_{k}} for p_{k} ≥ 1772201.  (7)

Cross-multiplying, we get

(log p_{k+1} − log p_{k})(p_{k} + log^{2} p_{k}) < log^{2} p_{k} − log p_{k} − 1.  (8)

We have

\frac{y}{x + y} < log(x + y) − log x  for every x, y > 0.  (9)

Setting x = p_{k} and y = p_{k+1} − p_{k}, we can replace the left-hand side of (8) by a smaller quantity (p_{k+1} − p_{k})(p_{k} + log^{2} p_{k})/p_{k+1} to obtain the inequality

\frac{(p_{k+1} − p_{k})(p_{k} + log^{2} p_{k})}{p_{k+1}} < log^{2} p_{k} − log p_{k} − 1,

which is equivalent to

(p_{k+1} − p_{k})(p_{k} + log^{2} p_{k}) < (p_{k} + (p_{k+1} − p_{k}))(log^{2} p_{k} − log p_{k} − 1),

p_{k+1} − p_{k} < \frac{p_{k}}{p_{k} + log p_{k} + 1}(log^{2} p_{k} − log p_{k} − 1).

This proves the theorem for every k ≥ 133115 because p_{k}/(p_{k} + log p_{k} + 1) < 1. Separately, for 9 < k < 133115 we verify the desired inequality by direct computation.

3 Does a given prime gap confirm or disprove Firoozbakht’s conjecture?

Given p_{k} and p_{k+1}, where the prime gap p_{k+1} − p_{k} is “large” and k = π(p_{k}) is not known, can we decide whether this gap confirms or disproves Firoozbakht’s conjecture? The answer is, in most cases, yes. We showed this in [4, Sect. 3] and established the following theorem:

Theorem 2. ([4, Sect. 4]). Firoozbakht’s conjecture (1) is true for all primes p_{k} < 4 × 10^{18}.

In the verification of (1) for p_{k} < 4 × 10^{18} we have not used bound (2) or (3); see [4]. Indeed, (2) is a corollary of (1); as such, (2) might be true even when (1) is false. Here is a more detailed discussion. Define (see Table 1):

f_{k} = p_{k}^{1+1/k} − p_{k}  (the upper bound for p_{k+1} − p_{k} predicted by (1));
ℓ_{k} = log^{2} p_{k} − log p_{k} (the upper bound for p_{k+1} − p_{k} predicted by (2)).

One can prove that f_{k} < ℓ_{k} when k → ∞; moreover, f_{k} = ℓ_{k} − 1 + o(1) (see Appendix). Computation shows that f_{k} < ℓ_{k} for p_{k} ≥ 11783 (k ≥ 1412). Suppose there is a prime q ∈ [p_{k} + f_{k}, p_{k} + ℓ_{k}]; for example, there is such a prime, q = 2010929, when p_{k} = 2010733 (see line 7 in Table 1). Now what if there were no other primes between p_{k} and q? Then we would have p_{k+1} = q, Firoozbakht’s conjecture (1) would be false, while (2) would still be true. So (2) is not particularly useful for verifying (1). On the other hand, any violation of (2) would immediately disprove Firoozbakht’s conjecture (1). Clearly, similar reasoning is valid for (3) with b ≤ 1. However, in the next section we prove that (3) with b = 1.17 is a sufficient condition for Firoozbakht’s conjecture (1). We will also give a few other sufficient conditions that have the form (3) with b → 1 as k → ∞.

\begin{matrix}k & p_{k} & p_{k+1} − p_{k} & f_{k} = p_{k}^{1+1/k}− p_{k} & ℓ_{k} = log^{2} p_{k} − log p_{k} \\ 6 & 13 & 4 & 6.934 & 4.014 \\ 9 & 23 & 6 & 9.586 & 6.696 \\ 30 & 113 & 14 & 19.286 & 17.621 \\ 217 & 1327 & 34 & 44.709 & 44.515 \\ 3385 & 31397 & 72 & 96.188 & 96.861 \\ 31545 & 370261 & 112 & 150.529 & 151.581 \\ 149689 & 2010733 & 148 & 194.972 & 196.142 \\ 1319945 & 20831323 & 210 & 265.959 & 267.137 \\ 1094330259 & 25056082087 & 456 & 548.237 & 549.389 \\ 94906079600 & 2614941710599 & 652 & 787.801 & 788.925 \\ 662221289043 & 19581334192423 & 766 & 904.982 & 906.097 \\ 6822667965940 & 218209405436543 & 906 & 1055.966 & 1057.071 \\ 49749629143526 & 1693182318746371 & 1132 & 1193.418 & 1194.516 \end{matrix}

Table 1: Upper bounds for prime gaps p_{k+1} − p_{k} predicted by (1) and (2); p_{k} ∈ \underline{A111943} [9]

4 Sufficient conditions for Firoozbakht’s conjecture

Theorem 3. If

p_{k+1} − p_{k} < log^{2} p_{k} − log p_{k} − 1.17 for all k > 9 (p_{k} ≥ 29),  (10)

then Firoozbakht’s conjecture (1) is true. Proof. From Axler [1, Corollary 3.5] we have

log x − 1 − \frac{1.17}{log x} < \frac{x}{π(x)} for every x ≥ 5.43.  (11)

Let k > 9. Multiplying both sides of (11) by log x, taking x = p_{k}, and using (10), we get

p_{k+1} − p_{k} < log^{2} p_{k} − log p_{k} − 1.17 < \frac{p_{k} log p_{k}}{k} for p_{k} ≥ 29;  (12)

therefore,

\frac{p_{k+1} − p_{k}}{p_{k}} < \frac{log p_{k}}{k} for p_{k} ≥ 29. (13)

We have

log(x + y) − log x < \frac{y}{x} for every x, y > 0.

Setting x = p_{k} and y = p_{k+1} − p_{k}, we can replace the left-hand side of (13) by a smaller quantity log p_{k+1} − log p_{k} to obtain the inequality

log p_{k+1} − log p_{k} < \frac{log p_{k}}{k} ,  (14)

which is equivalent to

log_{p_{k}} \frac{p_{k+1}}{p_{k}} < \frac{1}{k}.

Now, exponentiation with base p_{k} yields Firoozbakht’s conjecture (1) for p_{k} ≥ 29. This completes the proof since for small p_{k} conjecture (1) holds unconditionally [4].

Other sufficient conditions for (1). Based on the π(x) formula of Panaitopol [5], Axler gives a family of upper bounds for π(x) [1, Corollary 3.5]:

π(x) < \frac{x}{log x − 1 − \frac{1.17}{log x}}  for x ≥ 5.43,
π(x) < \frac{x}{log x − 1 − \frac{1}{log x} − \frac{3.83}{log^{2} x}}  for x ≥ 9.25,
π(x) < \frac{x}{log x − 1 − \frac{1}{log x} − \frac{3.35}{log^{2} x} − \frac{15.43}{log^{3} x}}  for x ≥ 14.36,
π(x) < \frac{x}{log x − 1 − \frac{1}{log x} − \frac{3.35}{log^{2} x} − \frac{12.65}{log^{3} x} − \frac{89.6}{log^{4} x}} for x ≥ 21.95.

Just as in Theorem 3, we can transform the above upper bounds into sufficient conditions for Firoozbakht’s conjecture (1) and obtain our next theorem.

Theorem 4. If one or more of the following conditions hold for all p_{k} > 4 × 10^{18} :

p_{k+1} − p_{k} < log^{2} p_{k} − log p_{k} − 1.17,
p_{k+1} − p_{k} < log^{2} p_{k} − log p_{k} − 1 − \frac{3.83}{log p_{k}} ,
p_{k+1} − p_{k} < log^{2} p_{k} − log p_{k} − 1 − \frac{3.35}{log p_{k}} − \frac{15.43}{log^{2} p_{k}} ,
p_{k+1} − p_{k} < log^{2} p_{k} − log p_{k} − 1 − \frac{3.35}{log p_{k}} − \frac{12.65}{log^{2} p_{k}} − \frac{89.6}{log^{3} p_{k}} ,

then Firoozbakht’s conjecture (1) is true.

In the statement of Theorem 4, we have taken into account that for p_{k} < 4 × 10^{18} conjecture (1) holds unconditionally [4]. We do not give a proof of Theorem 4; it is fully similar to the proof of Theorem 3. Remarks.

(i) In inequality (10) the right-hand side is an increasing function of p_{k}. Therefore, if (10) holds for a maximal prime gap with p_{k} = \underline{A002386}(n), then (10) must also be true for every p_{k} between \underline{A002386}(n) and \underline{A002386}(n + 1). So an easy way to prove Theorem 2 is to check (1) directly for all primes p_{k} ≤ 89, then verify (10) just for maximal prime gaps with p_{k} = \underline{A002386}(n) ≥ 89.

(ii) In Theorem 4, the coefficients of (log p_{k})^{−n} approximate the terms of OEIS sequence \underline{A233824}: a recurrent sequence in Panaitopol’s formula for π(x) [5].

5 Appendix: An asymptotic formula for p_{k}^{1+1/k} − p_{k}

Theorem 5. Let p_{k} be the k-th prime, and let f_{k} = p_{k}^{1+1/k} − p_{k}, then

f_{k} = log^{2} p_{k} − log p_{k} − 1 + o(1) as k → ∞ (cf. OEIS \underline{A246778}).

Proof. From Axler [1, Corollaries 3.5, 3.6] we have

\frac{x}{log x − 1 − \frac{1}{log x} − \frac{1}{log^{2} x}} < π(x) < \frac{x}{log x − 1 − \frac{1}{log x} − \frac{3.83}{log^{2} x}} for x ≥ 1772201. (15)

By definition of f_{k}, we have log_{p_{k}}(p_{k} + f_{k}) = 1 + 1/k, so k = π(p_{k}) = \frac{log p_{k}}{log(p_{k} + f_{k}) − log p_{k}} .

Therefore, for x = p_{k} ≥ 1772201, we can rewrite (15) as

\frac{p_{k}}{log p_{k} − 1 − \frac{1}{log p_{k}} − \frac{1}{log^{2} p_{k}}} < \frac{log p_{k}}{log(p_{k} + f_{k}) − log p_{k}} < \frac{p_{k}}{log p_{k} − 1 − \frac{1}{log p_{k}} − \frac{3.83}{log^{2} p_{k}}} . (16)

An upper bound for f_{k}. We combine (4) with the left inequality of (16) to get

\frac{p_{k} + log^{2} p_{k}}{log p_{k} − 1 − \frac{1}{log p_{k}}} < \frac{log p_{k}}{log(p_{k} + f_{k}) − log p_{k}} for p_{k} ≥ 1772201.  (17)

Cross-multiplying and using (9), similar to Theorem 1, we obtain

\frac{f_{k}(p_{k} + log^{2} p_{k})}{p_{k} + f_{k}} < (log(p_{k} + f_{k}) − log p_{k})(p_{k} + log^{2} p_{k}) < log^{2} p_{k} − log p_{k} − 1,

f_{k}(p_{k} + log^{2} p_{k}) < (p_{k} + f_{k})(log^{2} p_{k} − log p_{k} − 1),

f_{k} < \frac{p_{k}}{p_{k} + log p_{k} + 1}(log^{2} p_{k} − log p_{k} − 1) < log^{2} p_{k} − log p_{k} − 1.

A lower bound for f_{k}. From the right inequality of (16) we get

\frac{log^{2} p_{k} − log p_{k} − 1 − \frac{3.83}{log p_{k}}}{p_{k}} < log(p_{k} + f_{k}) − log p_{k} < \frac{f_{k}}{p_{k}} ,

log^{2} p_{k} − log p_{k} − 1 − \frac{3.83}{log p_{k}} < f_{k}.

Together, the upper and lower bounds yield the desired asymptotic formula for k → ∞.

6 Acknowledgments

The author expresses his gratitude to the anonymous referee for numerous useful suggestions, and to all contributors and editors of the websites OEIS.org and PrimePuzzles.net, particularly to Farideh Firoozbakht for proposing a very interesting conjecture. Thanks are also due to Christian Axler for proving the π(x) bounds [1] used in Theorems 1, 3–5.

References

[1] C. Axler, New bounds for the prime counting function π(x), preprint, 2014,

http://arxiv.org/abs/1409.1780.

[2] H. Cramér, On the order of magnitude of the difference between consecutive prime numbers, Acta Arith. 2 (1936), 23–46.

[3] A. Kourbatov, The distribution of maximal prime gaps in Cramér’s probabilistic model of primes, Int. J. Statistics and Probability 3 (2014), 18–29.

[4] A. Kourbatov, Verification of the Firoozbakht conjecture for primes up to four quintillion, Int. Math. Forum 10 (2015), 283–288.

[5] L. Panaitopol, A formula for π(x) applied to a result of Koninck-Ivić, Nieuw Arch. Wiskd. 5 (2000), 55–56.

[6] P. Ribenboim, The Little Book of Bigger Primes, New York, Springer, 2004.

[7] C. Rivera, ed., Conjecture 30: the Firoozbakht conjecture, 2002.

Available at http://www.primepuzzles.net/conjectures/conj_030.htm.

[8] N. K. Sinha, On a new property of primes that leads to a generalization of Cramér’s

conjecture, preprint, 2010, http://arxiv.org/abs/1010.1399.

[9] N. J. A. Sloane, ed., The On-Line Encyclopedia of Integer Sequences, 2015. Published

electronically at http://oeis.org/A111943.

[10] Z.-W. Sun, On a sequence involving sums of primes, Bull. Aust. Math. Soc. 88 (2013), 197–205.

[11] Z.-W. Sun, Various new observations about primes, talk given at Univ. of Illinois at Urbana-Champaign, August 28 2012. Available at

http://math.nju.edu.cn/~zwsun/ObservPrime.pdf.

2010 Mathematics Subject Classification: 11N05. Keywords: Cramér conjecture, Firoozbakht conjecture, prime gap.

(Concerned with sequences \underline{A002386}, \underline{A005250}, \underline{A111943}, \underline{A182134}, \underline{A182514}, \underline{A182519}, \underline{A205827}, \underline{A233824}, \underline{A235402}, \underline{A235492}, \underline{A245396}, \underline{A246776}, \underline{A246777}, \underline{A246778}, \underline{A246810}, \underline{A249669}.)

Received June 18 2015; revised versions received September 26 2015; October 1 2015. Published in Journal of Integer Sequences, November 24 2015.

Return to Journal of Integer Sequences home page.