Estimates of the Bounds of ?(x) and ?((x + 1)2) ? ?(x2)

Connor Paul Wilson; Connor Paul Wilson

doi:10.3998/umurj.1334

We show the following bounds on the prime counting function π(x) using principles from analytic number theory, giving an estimate

log 2 ≤ lim inf x → ∞ π (x) x / log x ≤ lim sup x → ∞ π (x) x / log x ≤ 2 log 2

We also conjecture about the bounding of π((x + 1)²) − π(x²), as is relevant to Legendre’s conjecture about the number of primes in the aforementioned interval such that:

⌊ 12 ((x + 1) 2 log (x + 1) − x 2 log x) − (log x) 2 log (log x) ⌋ ≤ π ((x + 1) 2) − π (x 2) ≤ ⌊ 12 ((x + 1) 2 log (x + 1) − x 2 log x) − log 2 x log log x ⌋

1. Introduction

Recall the definition:

π (x) : = ∑ p ≤ x p prime 1,

and let us define the following:

Θ (x) : = ∑ p ≤ x p prime log p,

Ψ (x) : = ∑ 1 ≤ n ≤ x Λ (n) = ∑ p m ≤ x m ≥ 1 p prime log p,

Λ (n) = {log p if n = p k for some prime p and integer k ≥ 1 0 otherwise .

The following are simple statements from real analysis that are required for rigorousness’ sake: let {x_n} be a sequence of real numbers and L be a real number with the following two properties: ∀ϵ > 0, ∃N such that x_n < L + ϵ, ∀n ≥ N. ∀ϵ > 0 ^ N ≥ 1, ∃n ≥ N with x_n > L – ϵ. We thus define L as:

lim sup n → ∞ x n = L

Thus on the contrary we must have:

lim inf n → ∞ x n = − lim sup n → ∞ − x n

2. Necessary Preliminary Results

Theorem 2.1. For all α ∈ (0, 1), and all x ≥ x₀:

Θ (x) log (x) ≤ Ψ (x) log (x) ≤ π (x) ≤ Θ (x) α log (x) + x α

Proof. Clearly Θ(x) ≤ Ψ(x), such that

lim sup n → ∞ Ψ (x) x ≥ lim sup n → ∞ Θ (x) x

Also, if p is a prime and p^m ≤ x < p^m+1, then log p occurs in the sum for Ψ(x) exactly m times. [1]

Ψ (x) = ∑ p m ≤ x p prime m ≥ 1 log p = ∑ p ≤ x p prime [log x log p] log p ≤ ∑ p ≤ x p prime log x = π (x) log x

lim sup x → ∞ Ψ (x) x ≤ lim sup x → ∞ π (x) x / log x

Now fix α ∈ (0, 1). Given x > 1,

Θ (x) = ∑ p ≤ x p prime log p ≥ ∑ x a < p ≤ x p prime log p .

It is clear that all p from the second sum satisfy: log p > α log x.

∴

Θ (x) > α log x ∑ x α < p ≤ x 1 = α log x (π (x) − π (x α)) > α log x (π (x) − x α)

϶

Θ (x) x > α π (x) x / log x − α log x x 1 − α

∀α ∈ (0, 1) we have:

lim x → ∞ α log x x 1 − α = 0.

Combining these we get:

lim sup x → ∞ Θ (x) x ≥ lim sup x → ∞ α π (x) x / log x

Once again, since our statement is true ∀α ∈ (0, 1),

lim sup x → ∞ Θ (x) x ≥ lim sup x → ∞ π (x) x / log x

Similarly:

lim inf x → ∞ Ψ (x) x ≥ lim inf x → ∞ Θ (x) x

lim inf x → ∞ π (x) x / log x ≥ lim inf x → ∞ Ψ (x) x

Once again, we apply the same method:

lim inf x → ∞ Θ (x) x ≥ lim inf x → ∞ π (x) x / log x,

and have thus proven Theorem 2.1. □

3. Main Result

Theorem 3.1. We have:

log 2 ≤ lim inf x → ∞ π (x) x / log x ≤ lim sup x → ∞ π (x) x / log x ≤ 2 log 2.

Proof. First the lower bound. Take:

S (x) : = ∑ 1 ≤ n ≤ x log n − 2 ∑ 1 ≤ n ≤ x / 2 log n .

Then,

∑ 1 ≤ d ≤ n d | n Λ (d) = ∑ p r | d d | n p prime log p = ∑ i = 1 l ∑ r = 1 e i log p i where n = p 1 e 1 ⋯ p l e l = ∑ i = 1 l e i log p i = log n

∴

S (x) = ∑ 1 ≤ n ≤ x ∑ d | n Λ (d) − 2 ∑ 1 ≤ n ≤ x / 2 ∑ d | n Λ (d)

Clearly {d, 2d, …, qd} is the set of n satisfying 1 ≤ n ≤ x and d | n (we can see this easily by writing x = r + qd with 0 ≤ r < d).

∴

S (x) = ∑ 1 ≤ d ≤ x Λ (d) [x d] − 2 ∑ 1 ≤ d ≤ x / 2 Λ (d) [x 2 d] = ∑ 1 ≤ d ≤ x / 2 Λ (d) ([x d] − 2 [x 2 d]) + ∑ (x / 2) < d ≤ x Λ (d) [x d] ≤ ∑ 1 ≤ d ≤ x / 2 Λ (d) + ∑ (x / 2) < d ≤ x Λ (d) = Ψ (x) .

So,

Ψ (x) x ≥ S (x) x = 1 x ∑ 1 ≤ n ≤ x log n − 2 x ∑ 1 ≤ n ≤ x / 2 log n .

log t is increasing,

∴

∫ 1 x + 1 log t d t ≥ ∑ 1 ≤ n ≤ x log n,

∫ 1 [x] log t d t ≤ ∑ 1 ≤ n ≤ x log n .

Actually, assuming $x ∈ ℤ +$ ,

S (x) x ≥ 1 x ∫ 1 x log t d t − 2 x ∫ 1 (x / 2) + 1 log t d t = 1 x (x log x − x + 1) − 2 x (x + 2 2 log (x + 2 2) − x + 2 2 + 1) = log x + 1 x − x + 2 x log (x + 2) + x + 2 x log 2 > log (x x + 2) − 2 x log (x + 2) + log 2

Using Theorem 2.1, we get:

lim inf x → ∞ π (x) x / log x = lim inf x → ∞ Ψ (x) x ≥ lim inf x → ∞ S (x) x > lim x → ∞ log (x / (x + 2)) − 2 x log (x + 2) + log 2 = log 2

To complete the proof, we will need some auxiliary results taken from Murty’s Analytic Number Theory [1] in the form of three lemmas:

Lemma 3.2.

ord p (m!) = ∑ r ≥ 1 [m p r], ∀ m ∈ ℤ +, p r i m e p

Proof. Fix an exponent r. The positive integers no larger than m that are multiples of p^r are

p r, 2 p r, …, [m p r] p r

and those that are multiples of p^r+1 are

p r + 1, 2 p r + 1, …, [m p r + 1] p r + 1

Thus there are precisely $[m / p] r − [m / p] r + 1$ positive integers n ≤ m with ord_p(n) = r.

∴

ord p (m!) = ∑ n = 1 m ord p (n) = ∑ r ≥ 1 ∑ 1 ≤ n ≤ m ord p (n) = r r = ∑ r ≥ 1 r ([m / p r] − [m / p r + 1]) = ∑ r ≥ 1 r [m / p r] − ∑ r ≥ 1 r [m / p r + 1] = ∑ r ≥ 1 r [m / p r] − ∑ r ≥ 1 (r − 1) [m / p r] = ∑ r ≥ 1 [m p r] □

Lemma 3.3. $∀ n ∈ ℤ +$ ,

2 2 n 2 n < (2 n 2) < 2 2 n 2 n + 1

Proof.

P n : = ∏ i ≤ n (2 i − 1) (2 i) = (2 n)! 2 2 n (n!) 2 = (2 n 2) 1 2 2 n

Since:

(2 i − 1) (2 i + 1) (2 i) 2 < 1

for all i ≥ 1.

∴

1 > (2 n + 1) P n 2,

giving the upper bound. For the lower bound:

1 − 1 (2 i − 1) 2 < 1

∀i ≥ 1, such that

1 > ∏ i = 2 n (1 − 1 (2 i − 1) 2) = ∏ i = 2 n (2 i − 1) 2 − 1 (2 i − 1) 2 = ∏ i = 2 n (2 i − 2) (2 i) (2 i − 1) 2 = 1 4 n P n 2

yielding our lemma. □

Lemma 3.4. $∀ n ∈ ℤ +$ ,

Θ (n) < 2 n log 2

Proof. By Lemma 3.3,

log ((2 n n) 12) = log ((2 n n)) − log 2 < 2 n log 2 − 12 log (2 n + 1) − log 2 = (2 n − 1) log 2 − 12 log (2 n + 1)

since

(2 n n) 12 = (2 n)! (n!) 2 n 2 n = (2 n − 1)! n! (n − 1)! = (2 n − 1 n − 1) .

by Lemma 3.2:

log ((2 n n) 12) = log (2 n − 1 n − 1) = ∑ p prime ord p ((2 n − 1)!) log p − ∑ p prime ord p ((n − 1)!) log p − ∑ p prime ord p (n!) log p = ∑ p prime log p ∑ r ≥ 1 [(2 n − 1) / p r] − [n / p r] ≥ ∑ p prime n < p ≤ 2 n − 1 log p = Θ (2 n − 1) − Θ (n)

Where

Θ (2 n − 1) − Θ (n) < (2 n − 1) log 2 − 12 log (2 n + 1)

We now proceed by induction. Proceeding from the trivialities, suppose m > 2 and the lemma is true for n < m,n, $m ∈ ℕ$ . If m is odd, then m = 2n – 1 for some integer n ≥ 2 since m > 2. Thus by induction,

Θ (m) = Θ (2 n − 1) < Θ (n) + (2 n − 1) log 2 − 12 log (2 n + 1) < 2 n log 2 + (2 n − 1) log 2 − 12 log (2 n) = (4 n − 1) log 2 − 12 log (2 n) ≤ (4 n − 2) log 2 (s i n c e n ≥ 2) = 2 m log 2

If m is even, then m = 2n for some integer n with m > n ≥ 2 and m is composite. Clearly Θ(m) = Θ(m − 1) and we know:

Θ (m) = Θ (m − 1) < 2 (m − 1) log 2 < 2 m log 2

Lemma 3.4 gives

2 log 2 ≥ lim sup x → ∞ Θ (x) x . □

The desired lower bound follows from Theorem 2.1 □

4. On Primes in the Gaps between Squares

The following is relatively aleatory compared to the previous workings, but it is worth mentioning considering the importance of the statement.

By Hassani [2], we have

⌊ 12 ((x + 1) 2 log (x + 1) − x 2 log x) − log 2 x log log x ⌋ ≤ π ((x + 1) 2) − π (x 2) 12 (x 2 log n − 32 log 3) − ∑ j = 3 x − 1 log 2 x log log k < π (x 2) − π (32)

And thus:

∑ j = 3 x − 1 ⌊ 12 ((j + 1) 2 log (j + 1) − j 2 log j) − log 2 j log log j ⌋ < ∑ j = 3 n − 1 π ((j + 1) 2) − π (j 2)

∴

⌊ 12 ((x + 1) 2 log (x + 1) − x 2 log x) − (log x) 2 log (log x) ⌋ ≤ π ((x + 1) 2) − π (x 2) .

And by the prime number theorem, which gives us the asymptotic estimate for some

F (x) : = π ((x + 1) 2) − π (x 2) ~ 12 ((x + 1) 2 log (x + 1) − x 2 log x)

We propose:

π ((x + 1) 2) − π (x 2) ≤ ⌊ 12 ((x + 1) 2 log (x + 1) − x 2 log x) + log 2 x log log x ⌋

by the same method.

References

1. Ram Murty, R., Problems in Analytic Number Theory, Second Edition — Graduate Texts in Mathematics, Springer, 2001.

2. Hassani, M., Counting primes in the interval (n2, (n + 1)2), AMS, 1997.