On the Largest Product of Primes with Bounded Sum

Marc Deléglise and Jean-Louis Nicolas Institut Camille Jordan Université de Lyon, CNRS F-69622 Villeurbanne Cedex France

                    m.h.deleglise@gmail.com
                       jlnicola@in2p3.fr

Abstract Let h(n) denote the largest product of primes whose sum is ⩽ n, and g(n) denote the Landau function, which is the largest product of powers of primes whose sum is ⩽ n. In this article, several properties of h(n) are given and compared to similar properties of g(n). Special attention is paid to the behavior of the largest prime factor of h(n).

1 Introduction

If n ⩾ 2 is an integer, let us define h(n) as the greatest product of a family of primes q_{1} < q_{2} < ⋯ < q_{j} the sum of which does not exceed n. Let ℓ be the additive function such that ℓ(p^{α}) = p^{α} for p prime and α ⩾ 1. In other words, if the standard factorization of M into primes is M = q_{1}^{α_{1}}q_{2}^{α_{2}} ⋯ q_{j}^{α_{j}} we have ℓ(M) = q_{1}^{α_{1}} + q_{2}^{α_{2}} + ⋯ + q_{j}^{α_{j}} and ℓ(1) = 0. If μ denotes the Möbius function, h(n) can also be defined by

h(n) = max_{{ℓ(M)⩽n \atop μ(M)≠0}} M.  (1)

Note that

ℓ(h(n)) ⩽ n.  (2)

Landau [11] introduced the function g(n) as the maximal order of an element in the symmetric group S_{n}; he showed that

g(n) = max_{ℓ(M)⩽n} M.  (3)

Sequences (h(n))_{n⩾1} and (g(n))_{n⩾1} are sequences \underline{A159685} and \underline{A000793} in the OEIS (On-line Encyclopedia of Integer Sequences).

From Eqs. (1) and (3), it follows that

h(n) ⩽ g(n), (n ⩾ 0).  (4)

In [5] we gave some properties of h(n) and an algorithm to compute h(n) for large values of n.

In Section 2 below, these properties of h(n) are recalled and compared to similar properties of g(n). We also explain how the algorithm given in [5] can be adapted to calculate h(n) for all n up to 10^{10}.

In Section 3, we recall various results about the distribution of primes.

Section 4 is devoted to effective and asymptotic estimates for log h(n), ω(h(n)) and the differences log g(n) − log h(n) and ω(h(n)) − ω(g(n)).

The last section, Section 6, studies the largest prime factor P^{+}(h(n)) of h(n). This study uses the same tool (the so-called G-sequences) introduced by Grantham [9], and developed in [5] to estimate P^{+}(g(n)). The G-sequences are described in Section 5. The last result of the paper is a comparison between P^{+}(h(n)) and log h(n).

1.1 Notation

1. p denotes a generic prime. For i ⩾ 1, p_{i} is the i^{th} prime.

2. π(x) = ∑_{p⩽x} 1 is the number of primes ⩽ x.

3. θ(x) is the Chebyshev function

θ(x) = ∑_{p⩽x} log p.  (5)

4. Θ is the least upper bound of the real parts of the zeros of the Riemann ζ function. Under the Riemann hypothesis Θ = 1/2.

5. log_{2} x represents the iterated logarithm log log x.

6. Li(x), the integral logarithm of x, is defined for x > 1 by

Li(x) = lim_{ε→0^{+}} ∫_{0}^{1−ε} + ∫_{1+ε}^{x} \frac{dt}{log t} = γ + log_{2} x + ∑_{n=1}^{+∞} \frac{(log x)^{n}}{n · n!} ,

where γ = 0.577 ⋯ is Euler’s constant.

7. For each integer N > 1, P^{+}(N) is the largest prime factor of N and ω(N) = ∑_{p|N} 1 is the number of prime factors of N.

Let us write σ_{0} = 0, N_{0} = 1, and, for j ⩾ 1,

N_{j} = p_{1}p_{2} ⋯ p_{j} and σ_{j} = p_{1} + p_{2} + ⋯ + p_{j} = ℓ(N_{j}).  (6)

For n ⩾ 0, let k = k(n) denote the integer k ⩾ 0 such that

σ_{k} = p_{1} + p_{2} + ⋯ + p_{k} ⩽ n < p_{1} + p_{2} + ⋯ + p_{k+1} = σ_{k+1}.  (7)

2 General properties of h(n)

2.1 Theoretical properties of h(n)

In this section we recall the properties of h(n) that we will use [5]. First of all (cf. [5, Prop 3.1]) for each nonnegative integer j,

h(σ_{j}) = N_{j}.  (8)

Proposition 1. Let n be a nonnegative integer and k = k(n). Then

log N_{k} = θ(p_{k}) ⩽ log h(n) ⩽ θ(p_{k+1}) = log N_{k+1}.  (9)

Proof. From the definition of k(n) we have σ_{k} ⩽ n < σ_{k+1}. Using Eq. (8) and the fact that h is nondecreasing, this gives N_{k} ⩽ h(n) ⩽ N_{k+1}. Taking logarithms, we get Eq. (9).

From Eq. (9) we have h(n) ⩾ N_{k} and, since h(n) is squarefree,

P^{+}(h(n)) ⩾ p_{k(n)}.  (10)

We also have h(n) = ∏_{p|h(n)} p ⩽ ∏_{p⩽P^{+}(h(n))} p and thus

log h(n) ⩽ θ(P^{+}(h(n))).  (11)

In [5, (1.9)], for n ⩾ 0, h_{j}(n) is defined for each integer j satisfying 0 ⩽ j ⩽ k(n) by:

h_{j}(n) = max_{\begin{matrix}ℓ(M)≤n \\ μ(M)≠0, ω(M)=j \end{matrix}} M,  (12)

where ω(M) is the number of prime factors of M. The result [5, Theorem 6.1] implies that, for each n, the sequence (h_{j}(n))_{0⩽j⩽k(n)} is increasing, and therefore,

h(n) = h_{k(n)}(n).

This result that could appear quite obvious at first sight, is not so easy to prove. It depends strongly on the distribution of prime numbers. It has an obvious consequence (cf. [5, corollary (6.1)]):

Theorem 2. The number of prime factors of h(n), ω(h(n)) is given by

ω(h(n)) = k(n),  (13)

where k(n) is defined in Eq. (7). Theorem 3. Let j be a nonnegative integer.

(i) We have h(σ_{j+1} − 1) = h(σ_{j+1} − 2) = N_{j+1}/2. (ii) If q ⩽ p_{j+1} is a prime, then h(σ_{j+1} − q) = N_{j+1}/q. (iii) If j ⩾ 1 and if a is an even number satisfying 4 ⩽ a < p_{j+1}, we have

h(σ_{j+1} − a) = h(σ_{j+1} − a − 1).  (14)

(iv) The number h(n) is odd when n = σ_{j+1} − 1 or n = σ_{j+1} − 2. It is even for σ_{j} ⩽ n ⩽

σ_{j+1} − 3.

(v) For n ⩾ 1 the inequality h(n) ⩽ 2h(n − 1) holds. (vi) We have

lim inf_{n→∞} \frac{h(n)}{h(n − 1)} = 1 and lim sup_{n→∞} \frac{h(n)}{h(n − 1)} = 2.

Proof. (i) is from [5, Proposition 5.3]. (ii) follows from [5, Eqs. (8.13) and (8.6)]. (iii) is [5, Proposition 5.1]. (iv) The first part is implied by (i). Now assume that σ_{j} ⩽ n ⩽ σ_{j+1} − 3. From Theorem 2

we know that ω(h(n)) = j. If 2 does not divide h(n) we would have

ℓ(h(n)) ⩾ 3 + 5 + ⋯ + p_{j+1} = σ_{j+1} − 2,

in contradiction with the inequality (2), which proves (iv).

(v) First let us consider the case h(n) even; we then have ℓ(h(n)/2) = ℓ(h(n))−2 ⩽ n−2, so that, by Eq. (1), h(n−1) ⩾ h(n)/2 holds. If h(n) is odd, from (iv), we have n = σ_{j+1}−1 or n = σ_{j+1}−2 for some j ⩾ 1 and, from (i) and (ii), h(σ_{j+1}−1) = h(σ_{j+1}−2) = N_{j+1}/2 and h(σ_{j+1}−3) = N_{j+1}/3, which completes the proof of (v). Note that h(n) = 2h(n−1) implies h(n − 1) odd and h(n) even. From (iv), this occurs if and only if n = σ_{j} for some j.

(vi) From the fact that h is nondecreasing we get h(n)/h(n − 1) ⩾ 1 while Eq. (14) shows that h(n) = h(n − 1) for infinitely many n, which gives the value of the lim inf. From (v) we have h(n)/h(n − 1) ⩽ 2 for all n ⩾ 1. Moreover, from Eq. (8) we have h(σ_{j+1}) = N_{j+1}, which, together with (i), shows that h(σ_{j+1})/h(σ_{j+1} − 1) = 2 holds for infinitely many j’s and the proof of (vi) is completed.

Remark 4. Properties (iv), (v) and (vi) of h(n) are analogous to the following properties of g(n).

(iv) g(n) is odd only for n ∈ {3, 8, 15} (cf. [16, p. 142]).

(v) For n ⩾ 1, we have g(n) ⩽ 2g(n − 1) (cf. [16, p. 143]).

(vi) lim_{n→∞} g(n)/g(n − 1) = 1 is proved in [17].

Proposition 5. For n ⩾ 1, let γ_{h}(n) denote the cardinality of the set {h(m); 1 ⩽ m ⩽ n}. Then, with k = k(n) defined by Eq. (7), we have

\frac{(k + 2)(k − 1)}{2} ⩽ γ_{h}(n) ⩽ n − \frac{σ_{k} − k}{2} ,  (15)

and, when n → ∞,

\frac{2n}{log n} ≲ γ_{h}(n) ≲ \frac{n}{2}.  (16)

Proof. First, we observe that γ_{h}(n) is the number of m ⩽ n such that h(m) > h(m − 1) holds. From Theorem 3 (ii), for 1 ⩽ i ⩽ j and m = σ_{j} − p_{i} we have ℓ(h(m)) = m and thus h(m) > h(m − 1) holds, so that

γ_{h}(n) ⩾ ∑_{j=2}^{k} (γ_{h}(σ_{j} − 1) − γ_{h}(σ_{j−1} − 1)) ⩾ ∑_{j=2}^{k} j = \frac{(k + 2)(k − 1)}{2}.

To prove the upper bound in Eq. (15), we note that n − γ_{h}(n) is the number of m ⩽ n such that h(m) = h(m − 1). From Theorem 3 (i) and (iii), for j ⩾ 2 and σ_{j} ⩽ m < σ_{j+1}, we have h(m) = h(m − 1) for σ_{j+1} − m ∈ {1, 4, 6, …, p_{j+1} − 1}, so that, as h(0) = h(1) = 1 < h(2) = 2 < h(3) = 3 = h(4) we get

n − γ_{h}(n) ⩾ 2 + ∑_{j=2}^{k−1} \frac{p_{j+1} − 1}{2} = 2 + \frac{σ_{k} − 5}{2} − \frac{k − 2}{2} ⩾ \frac{σ_{k} − k}{2} .

Finally, to prove (16), we use Lemma 9 below. We get σ_{k} = ∑_{p⩽p_{k}} p ∼ \frac{p_{k}^{2}}{2 log p_{k}} . But, from the

prime number theorem, we have p_{k} ∼ k log k so that log p_{k} ∼ log k,

σ_{k} ∼ \frac{k^{2} log k}{2} ∼ σ_{k+1}, n ∼ \frac{k^{2} log k}{2} , log k ∼ \frac{log n}{2} and k ∼ 2\sqrt{\frac{n}{log n}}

which, together with (15), proves (16).

Remark 6. The estimates for γ_{g}(n) are weaker (cf. [16, p. 162–164] and [18, p. 218]). However it seems difficult to show γ_{h}(n) ∼ n/2 which is probably true.

Proposition 7. Let k ⩾ 1 and n ⩾ 2 satisfy k(n) = k (defined by Eq. (7)), so that σ_{k} ⩽ n < σ_{k+1} holds.

(i) If σ_{k} ⩽ n < σ_{k} + p_{k+1} − p_{k}, then we have h(n) = h(σ_{k}) = N_{k} and P^{+}(h(n)) = p_{k}.

(ii) If σ_{k} + p_{k+1} − p_{k} ⩽ n < σ_{k+1}, then we have P^{+}(h(n)) ⩾ p_{k+1}.

Proof. From Theorem 3 (ii), we have

h(σ_{k} + p_{k+1} − p_{k}) = N_{k+1}/p_{k} > N_{k}.  (17)

From Eq. (13), we have ω(h(n)) = k, and from (10) we get P^{+}(h(n)) ⩾ p_{k}.

- If P^{+}(h(n)) = p_{k}, then we have h(n) = N_{k}, which, from Eqs. (17) and (1), implies

n < σ_{k} + p_{k+1} − p_{k}.
- If P^{+}(h(n)) ⩾ p_{k+1}, then, from Eq. (2), we have
n ⩾ ℓ(h(n)) ⩾ P^{+}(h(n)) + p_{1} + ⋯ + p_{k−1} ⩾ σ_{k} + p_{k+1} − p_{k}.

Corollary 8. There exist arbitrary long intervals on which h(n) is constant.

Proof. Since the difference p_{k+1} − p_{k} is not bounded, this follows from Proposition 7 (i) above. Nicolas proved a similar result for g(n) in [16, p. 158].

2.2 Computation of h(n)

The algorithm given in [5] was used to compute h(10^{k}) for 1 ⩽ k ⩽ 35. Let us recall a few facts.

Let k = k(n) be defined above by Eq. (7). The value h(n) may be written as the product of two terms:

h(n) = N_{k} · G(p_{k}, n − σ_{k}),

where G(p, m) is defined by

G(p, m) = max \frac{Q_{1}Q_{2} ⋯ Q_{s}}{q_{1}q_{2} ⋯ q_{s}} ,

the maximum being taken over the primes Q_{1}, Q_{2}, …, Q_{s}, q_{1}, q_{2}, …, q_{s}, s ⩾ 0, satisfying

2 ⩽ q_{s} < q_{s−1} < ⋯ < q_{1} ⩽ p < Q_{1} < Q_{2} < ⋯ < Q_{s} and ∑_{i=1}^{s}(Q_{i} − q_{i}) ⩽ m.

The algorithm given in [5] for computing an isolated value h(n) is composed of two steps.

(i) The first step is the computation of k = k(n), p_{k} and σ_{k}.

(ii) The second step is the computation of the fraction h(n)/N_{k} = G(p_{k}, n − σ_{k}),

When computing h(n) for an n larger than, say 10^{5}, most of the computation time is devoted to the first step.

In this article we needed to compute the values of h(n) for all n up to x, for some values x, the largest of them being x = 10^{10} (this computation took about 100 hours of one processor on an AMD Shanghai computer with 8 processors). In this case, the computation of p_{k} and σ_{k} is done once and for all for the n belonging to the same [σ_{k}, σ_{k+1}). So, working by slices on the successive [σ_{k}, σ_{k+1}), the time of computation is mostly devoted to the computation of G(p_{k}, n − σ_{k}).

3 About the distribution of primes

3.1 Some lemmas

Lemma 9. Let us write S(x) = ∑_{p⩽x} p. When x tends to infinity,

S(x) ∼ \frac{x^{2}}{2 log x}.  (18)

Proof. Massias et al. [12, Lemme B] proved that S(x) = Li(x^{2}) + O(x^{2}e^{−a\sqrt{log x}}) for some a > 0, which implies (18), since Li(t) ∼ t/ log t when t → ∞.

Lemma 10 below is [14, Lemma 2].

Lemma 10. Let a be a nonnegative real number and Φ = Φ_{a} the function defined by

Φ(x) = \sqrt{x log x} (1 + \frac{log_{2} x − a}{2 log x}) .

Then Φ is increasing and concave for x > 1.

Proposition 11 is from [14, Point (ii), Proposition 1, p. 672].

Proposition 11. For k ⩾ 4398, that is p_{k} ⩾ 42061, and b = 1.16, we have

θ(p_{k}) ⩾ Φ_{b}(σ_{k+1}) = \sqrt{σ_{k+1} log σ_{k+1}} (1 + \frac{log_{2} σ_{k+1} − b}{2 log σ_{k+1}}) .  (19)

3.2 The error term in the prime number theorem

Let θ be the Chebyshev function defined in (5).

(i) There is some a > 0 such that

θ(x) = x + O(xe^{−a\sqrt{log x}}) .  (20)

(ii) If Θ < 1, we have

θ(x) = x + O(x^{Θ} log^{2} x) .  (21)

(iii) Under the Riemann hypothesis, we have

|θ(x) − x| ⩽ \frac{1}{8π} \sqrt{x} log^{2} x,  x ⩾ 599.  (22)

Points (i) and (ii) may be found in [10] or [8], for instance. Point (iii) is proved in [21, p. 337].

3.3 Effective bounds

We shall use the following results of P. Dusart:

θ(x) < x for x ⩽ 8 · 10^{11} (cf. [7, Table 6.6])  (23)
θ(x) < x + \frac{x}{36 260} ⩽ 1.000 028 x (x > 0) (cf. [7, Proposition 5.1])  (24)
|θ(x) − x| ⩽ \frac{0.05 x}{log^{2} x} (x ⩾ 122 568 683) (cf. [7, Theorem 5.2])  (25)

3.4 Distances between primes

(i) Dusart [7, Proposition 6.8] has proved that, for x ⩾ 396 738, the interval

[x, x + \frac{x}{25 log^{2} x}]  (26)

contains a prime number. This implies, for p_{i} ⩾ 396 833 = p_{33 609},

p_{i+1} ⩽ p_{i} + \frac{p_{i}}{25 log^{2} p_{i}} .  (27)

(ii) Under the Riemann hypothesis, Formula (22) implies that, for x ⩾ 599, the interval [x − \sqrt{x} log^{2} x/(4π), x] contains a prime number.

Still under the Riemann hypothesis, Cramér [2] proved that there exists b such that the interval [x, x + b\sqrt{x} log x] contains a prime. Ramaré et al. [19, Th. 1] have made effective this result by proving that, for x ⩾ 2, the interval

[x − \frac{8}{5}\sqrt{x} log x, x]  (28)

contains a prime number, which implies that, for p_{i} ⩾ 3,

p_{i−1} ⩾ p_{i} − \frac{8}{5}\sqrt{p}_{i} log p_{i}.  (29)

In [2], the “Cramér Conjecture” is stated as

p_{i+1} − p_{i} = O(log^{2} p_{i}) .  (30)

This conjecture is supported by numerical computations (cf., for example, [15]).

3.5 The η_{k} functions

Let k ⩾ 1 be integer. By the prime number theorem, the quotient p_{i−k}/p_{i} tends to 1 when i → +∞. Thus, for i_{0} ⩾ k + 1 there is at most a finite number of i’s such that \frac{p_{i−k}}{p_{i}} ⩽ \frac{p_{i_{0}−k}}{p_{i_{0}}} < 1, and the following definition makes sense.

Definition 12. We define η_{k} on the interval [p_{k}, +∞) by

η_{k}(x) = min \{\frac{p_{i−k}}{p_{i}} | p_{i} > x\} .  (31)

From (31) we see that η_{k} is a nondecreasing and right-continuous step function whose discontinuity points are primes called η_{k}–champion numbers. By convention, p_{k} is considered as an η_{k}–champion. The following lemma is proved in [4, §2.4]

Lemma 13.

(i) Let x be ⩾ p_{k}. For all y ⩾ x, the interval (η_{k}(x)y, y] contains at least k prime numbers, and η_{k}(x) is the largest real number λ such that (λy, y] contains at least k prime numbers for all y ⩾ x.

(ii) Let p be an η_{k}–champion. Then for all x ⩾ p , η_{k}(x) ⩾ η_{k}(p), in particular, the interval (η_{k}(p)x, x] contains at least k prime numbers.

Tables of the first few η_{k}–champion numbers for k = 1, 2, 3, may be found in [4, Tables 3,4,5], or on [3] for more values. Proposition 14 (cf. [4, Proposition 2.1] for more details) recalls some results that we shall use later.

Proposition 14.

(i) From [1, p. 562] there exists a > 0 such that, for x ⩾ p_{k}, we have

η_{k}(x) ⩾ 1 − k \frac{a}{x^{0.475}} .

(ii) Let i_{0} be defined by i_{0} = 33 609. For i close to i_{0} the values of p_{i} are

\begin{matrix}i = & 33 608 & 33 609 & 33 610 & 33 611 & 33 612 \\ p_{i} = & 396 733 & 396 833 & 396 871 & 396 881 & 396 883 \end{matrix}

For x ⩾ p_{i_{0}+k−1} we have from Eq. (26) that

η_{k}(x) ⩾ 1 − \frac{k}{25 log^{2} x}.  (32)

(iii) Under the Riemann hypothesis, for x ⩾ max(p_{k}, e^{2}), we have from (28)

η_{k}(x) ⩾ 1 − \frac{8k}{5} \frac{log x}{\sqrt{x}}.  (33)

(iv) Under Cramér’s conjecture (30), there exists a > 0 such that, for x ⩾ max(p_{k}, e^{2})

η_{k}(x) ⩾ 1 − ka\frac{log^{2} x}{x}.  (34)

3.6 The θ_{min}, θ_{d}, and δ_{3} functions

In this subsection we introduce three functions, θ_{min}, θ_{d}, δ_{3}, defined on the real interval [1, +∞). More information about them can be found in [4, §2].

Definition 15. The function θ_{min} is the nondecreasing right-continuous step function defined by

θ_{min}(y) = inf_{x⩾y} \frac{θ(x)}{x} = inf_{p_{i}>y} \frac{θ(p_{i−1})}{p_{i}}.  (35)

A table of the first few θ_{min}–champion numbers p and their rounded-down records θ_{min}(p) may be found in [4, Table 1] or on the web pages of the first author [3, Tabulation de thetamin]. If p < q are two consecutive θ_{min}–champion numbers, then θ_{min} is constant on [p, q) and equal to θ_{min}(p) = θ(q^{−})/q where q^{−} is the prime preceding q. If x ⩾ p, then θ(x)/x ⩾ θ_{min}(p) holds.

Definition 16. Let us define θ_{d}(y) for y ⩾ 1 by

θ_{d}(y) = sup_{x⩾y} |\frac{θ(x)}{x} − 1| log^{2} x,

so that, for x ⩾ y, we have

|\frac{θ(x)}{x} − 1| ⩽ \frac{θ_{d}(y)}{log^{2} x}.  (36)

A table of the first few θ_{d}–champion numbers and records is given in [4, Table 2]. A more extensive table may be found in [3, Tabulation de thetad]. If p < q are two consecutive θ_{d}–champion numbers, we have θ_{d}(p) = (1 − θ(q^{−})/q) log^{2} q where q^{−} is the prime preceding q. For p ⩽ x < q, θ_{d}(x) = θ_{d}(p) and, for x ≠ 1, 1 − θ_{d}(p)/ log^{2}(x) ⩽ θ(x)/x.

Definition 17. Let us define the function δ_{3}, for y ⩾ p_{3} = 5, by

δ_{3}(y) = sup_{x⩾y}(1 − η_{3}(x)) log^{2} x.

For x ⩾ y, we have

1 − η_{3}(x) ⩽ \frac{δ_{3}(y)}{log^{2}(x)}.  (37)

A table of the first few δ_{3}–champion numbers is given in [4, Table 6]. A more extensive table may be found in [3, Tabulation de delta3]. If p < q are two consecutive δ_{3}–champion numbers, we have δ_{3}(p) = (1 − η_{3}(q^{−})) log^{2}(q) where q^{−} is the prime preceding q. For p ⩽ x < q, δ_{3}(x) = δ_{3}(p) and, for x ≠ 1, 1 − δ_{3}(p)/ log^{2}(x) ⩽ η_{3}(x) ⩽ 1.

4 Estimates for log h(n) and ω(h(n))

4.1 An asymptotic equivalent of log h(n)

Theorem 18. When n → +∞, log h(n) ∼ \sqrt{n log n}.

Proof. Let be k = k(n) defined by (7). From (9) it is sufficient to prove that, when n tends to

infinity, log N_{k} ∼ \sqrt{n log n}. When k → ∞, p_{k−1} ∼ p_{k}, and, from (18), σ_{k−1} ∼ σ_{k} ∼ \frac{p_{k}^{2}}{2 log p_{k}}.

With (7) this gives n ∼ \frac{p_{k}^{2}}{2 log p_{k}} , from which we infer

p_{k} ∼ \sqrt{n log n},

and, by the prime number theorem, log N_{k} = θ(p_{k}) ∼ p_{k} ∼ \sqrt{n log n}.

4.2 Effective estimates of log h(n)

Theorem 19. The assertion

n ⩾ n(b) ⟹ log h(n) > \sqrt{n log n} (1 + \frac{log_{2} n − b}{2 log n})  (38)

is true for the following pairs (b, n(b)) (where each n(b) is optimal):

\begin{matrix}b & 2.0 & 1.8 & 1.6 & 1.4 & 1.20 & 1.18 & 1.16 \\ n(b) & 19 491 & 57 458 & 201 460 & 1 303 470 & 29 696 383 & 44 689 942 & 77 615 268 \end{matrix}

Proof. First suppose that b = 1.16 and n ⩾ 87 179 593 = σ_{4398}. Let k = k(n) defined by (7) so that σ_{k} ⩽ n < σ_{k+1} holds. From (9), Inequality (19) and Lemma 10, we may write

log h(n) ⩾ θ(p_{k}) ⩾ Φ_{b}(σ_{k+1}) ⩾ Φ_{b}(n).

This proves that (38) is true for b = 1.16 with n(b) = 87 179 593.

The computation, by the method described in §2.1, of all the values h(n) for n ⩽ 87 179 592 gives, for each value of b the smallest value n(b) such that Eq. (38) holds.

Corollary 20. We have

log h(n) > \sqrt{n log n} for n ⩾ 7 387.  (39)

Proof. By using (38) with b = 2, if n ⩾ 19 491 we may write

log h(n) > \sqrt{n log n} (1 + \frac{log_{2} n − 2}{2 log n}) ⩾ \sqrt{n log n}

since log_{2} n ⩾ 2. By computing h(n) for 2 ⩽ n ⩽ 19 490, we prove that 7 386 is the largest integer such that log h(n) ⩽ \sqrt{n log n}.

Theorem 21. The following inequality is satisfied

log h(n) ⩽ \sqrt{n log n} (1 + \frac{log_{2} n − 0.975}{2 log n}) , n ⩾ 3.  (40)

Proof. This results from (4) and [14, Theorem 2].

Corollary 22. For each n ⩾ 2,

\frac{log h(n)}{\sqrt{n log n}} ⩽ 1.0482016 ⋯,  (41)

the upper bound being attained for n = 38343860 = σ_{2989} = ℓ(N_{2989}).

Proof. For n ⩾ n_{1} = 3.6 · 10^{9}, we have \frac{log_{2} n − 0.975}{2 log n} ⩽ 0.048. Thus, by (40), Inequality

(41) is satisfied for n ⩾ n_{1}. The computation of the values h(n) for n up to n_{1} shows that the maximum value is attained on n = σ_{2989}.

It is possible to shorten the computation by using the trick described in [13, §4]. Let us recall briefly how it works.

From Theorem 18 and Corollary 20, we know that there exists λ > 1 such that

∀n ⩾ 1, log h(n) ⩽ λ\sqrt{n log n},  (42)

with equality for some n = n_{0} ⩾ 2. Moreover, we have

ℓ(h(n_{0})) = n_{0}  (43)

since, if we should have ℓ(h(n_{0})) ⩽ n_{0} − 1, we would have h(n_{0} − 1) = h(n_{0}) and log(h(n_{0} − 1)/\sqrt{(n_{0} − 1) log(n_{0} − 1)} > λ, contradicting (42).

Now, let M ⩾ 1 be a squarefree integer. From (1.1) and (42), we have

log M ⩽ log h(ℓ(M)) ⩽ λ\sqrt{ℓ(M) log ℓ(M)}  (44)

and, by setting M_{0} = h(n_{0}), we get from (43)

log M_{0} = λ\sqrt{n_{0} log n_{0}} = λ\sqrt{ℓ(M_{0}) log ℓ(M_{0})}.  (45)

The function ϕ : t ⟶ t log t is a bijection from (1, +∞) to (0, +∞). Let us call ϕ^{−1} its inverse function. We set

u = u(M) = ϕ^{−1} ((\frac{log M}{λ} )^{2}) , u_{0} = u(M_{0}), ρ = \frac{2\sqrt{u_{0} log u_{0}}}{λ(1 + log u_{0})}.

We have

log M = λ\sqrt{ϕ(u)} = λ\sqrt{u log u}, log M_{0} = λ\sqrt{u_{0} log u_{0}}

so that (45) yields

u_{0} = ℓ(M_{0}).

Now, we set

f_{1} = ℓ(M) − u(M) and f_{2} = u(M) − ρ log M.  (46)

As ϕ is increasing, f_{1} ⩾ 0 is equivalent to ϕ(ℓ(M)) ⩾ ϕ(u(M)) which follows from (44). Therefore, we have

f_{1} = ℓ(M) − u(M) ⩾ 0 = ℓ(M_{0}) − u(M_{0}).  (47)

We have f_{2} = u − λρ\sqrt{u log u} which is convex on u > 1 and whose derivative vanishes for u = u_{0}, due to the choice of ρ. Therefore, we have

f_{2} ⩾ u_{0} − λρ\sqrt{u_{0} log u_{0}} = ℓ(M_{0}) − ρ log M_{0}.  (48)

By adding (47) to (48), we deduce from (46)

∀ squarefree M ⩾ 1,  ℓ(M) − ρ log M ⩾ ℓ(M_{0}) − ρ log M_{0}.  (49)

Let p be the largest prime factor of M_{0} and assume that a prime p′ < p does not divide M_{0}; then applying (49) for M = M_{0}/p and for M = M_{0}p′ yields respectively ρ ⩾ p/ log p and ρ ⩽ p′/ log p′ whence p/ log p < p′/ log p′. The function t ↦ t/ log t being minimal for t = exp(1), this is only possible if p = 3, p′ = 2 and M_{0} = 3, which is impossible since log 3 < \sqrt{3 log 3} holds. Therefore, there exists k ⩾ 1 such that M_{0} = N_{k}, ℓ(M_{0}) = σ_{k} and

λ = max_{j⩾1, σ_{j}⩽3.6 10^{9}} \frac{log N_{j}}{\sqrt{σ_{j} log σ_{j}}} .

4.3 An upper bound for log g(n) − log h(n)

Theorem 23. There exists C > 0 such that, for n ⩾ 1,

log g(n) − C(n log n)^{1/4} ⩽ log h(n) ⩽ log g(n).  (50)

We may choose C = 5.68.

Proof. Given (4), it is sufficient to prove the left inequality of (50). Let P = P^{+}(g(n)) be the largest prime factor of g(n). Then, by [4, Theorem 5.1], P ⩽ 1.27\sqrt{n log n}. By Bertrand’s postulate, there exists a prime q such that

P < q ⩽ 2.54\sqrt{n log n}.  (51)

Let us write

g(n) = ∏_{p⩽P} p^{a_{p}} where a_{p} = v_{p}(g(n)),

and

g(n) = A · B with A = ∏_{p⩽P, a_{p}⩾2} p^{a_{p}}, B = ∏_{p⩽P, a_{p}=1} p^{a_{p}}.

Then B divides g(n), so that ℓ(B) ⩽ ℓ(g(n)) and, from (3), ℓ(g(n)) ⩽ n, which implies ℓ(B) ⩽ n. As B is squarefree, it follows from (3) that h(n) ⩾ B = g(n)/A which implies

log h(n) ⩾ log g(n) − log A.  (52)

Let us find an upper bound for A. If a_{p} ⩾ 2, we have p^{a_{p}} ⩽ q+p^{a_{p}−1} (otherwise N′ = qg(n)/p would be such that N′ > g(n) and ℓ(N′) = ℓ(g(n)) + p^{a_{p}−1} + q − p^{a_{p}} < ℓ(g(n) ⩽ n, contradicting the definition of g(n)). This gives p^{a_{p}} ⩽ q/(1 − 1/p) ⩽ 2q and p ⩽ (2q)^{1/a_{p}} ⩽ \sqrt{2q}. From this we deduce A ⩽ (2q)^{π(\sqrt{2q})} and, by using the inequality π(t) ⩽ 1.26 t/ log t (cf. [20, (3.6)]) and (51), we get

log A ⩽ 1.26\begin{matrix}√ & \overline{2q} \\ log & \sqrt{2q} \end{matrix} log(2q) = 2.52\sqrt{2q} ⩽ 5.68(n log n)^{1/4},

which, with (52), ends the proof.

4.4 Study of ω(h(n)) − ω(g(n))

Theorem 24. There exists a constant C such that, for n ⩾ 2,

0 ⩽ ω(h(n)) − ω(g(n)) ⩽ C \frac{n^{1/4}}{(log n)^{3/4}} .  (53)

Proof. The lower bound: Let n be a positive integer, and define k = k(n) by (7). Therefore we have

σ_{k} ⩽ n < σ_{k+1}  (54)

and, by Theorem 2, ω(h(n)) = k. Further, from (3) and (54), we have

σ_{ω(g(n))} = p_{1} + p_{2} + ⋯ + p_{ω(g(n))} ⩽ ∑_{p|g(n)} p ⩽ ℓ(g(n)) ⩽ n < σ_{k+1}

whence ω(g(n)) ⩽ k = ω(h(n)) and the lower bound of (53) is proved.

The upper bound. Let x_{1} > 4 be a real number and, for i ⩾ 2, x_{i} be the unique number

such that \frac{x_{i}^{i} − x_{i}^{i−1}}{log x_{i}} = \frac{x_{1}}{log x_{1}} . The sequence (x_{i}) is decreasing and satisfies

x_{i} < x_{1}^{1/i}  (55)

so that x_{i} < 2 for i > I = ⌊\frac{log x_{1}}{log 2} ⌋. We set

N = N(x_{1}) = ∏_{i=1}^{I} ∏_{p⩽x_{i}} p.  (56)

Such an integer N is called in [6, §4] an ℓ–superchampion number associated with x_{1}. Let G denote the set of ℓ–superchampion numbers. If N ∈ G, the set {x_{1}; N(x_{1}) = N} is an interval of positive length. Thus we can choose a particular value of x_{1} such that, for i ⩾ 1, x_{i} is never prime (cf. [6, Lemma 4, 3.]). With such a value of x_{1} (56) becomes

N = N(x_{1}) = ∏_{i=1}^{I} ∏_{p<x_{i}} p.  (57)

Now, let us define k_{1} and k_{2} ⩽ k_{1} by

p_{k_{1}} < x_{1} < p_{k_{1}+1} and p_{k_{2}} < \sqrt{x_{1}} < p_{k_{2}+1}.  (58)

It follows from (57) and (55) that, for every prime p, we have

p^{v_{p(N)}} < x_{1} and v_{p}(N) = 1 for p_{k_{2}} < p ⩽ p_{k_{1}}.  (59)

Therefore, we get from (57) and (58)

σ_{k_{1}} = ∑_{p<x_{1}} p ⩽ ℓ(N) ⩽ k_{2}x_{1} + σ_{k_{1}} ⩽ σ_{k_{1}+k_{2}}.  (60)

Let n be an integer, n ⩾ 12, and N = N(x_{1}) < N′ = N′(x′_{1}) two consecutive ℓ–superchampion numbers such that

ℓ(N) ⩽ n < ℓ(N′).

Since N′/N is a prime p′ (cf. [6, Lemma 4, 4.(i)]), from (57), either p′ = p_{k+1} or x′_{1} < p_{k+1}, and, from (59), (p′)^{v_{_{p′} (N′)}} < x′_{1} < p_{k+1}. In both cases, ℓ(N′) ⩽ ℓ(N) + p_{k+1}. Therefore, from (60), we get

σ_{k_{1}} ⩽ ℓ(N) ⩽ n < ℓ(N′) ⩽ ℓ(N) + p_{k+1} ⩽ σ_{k_{1}+k_{2}+1},  (61)

and (13) from Theorem 2 yields

k_{1} ⩽ ω(h(n)) ⩽ k_{1} + k_{2}.

On the other hand, [12, Lemma E] gives

ω(g(n)) = ω(N) + O(\frac{\sqrt{x_{1}}}{log x_{1}} ) .

From (57) and (58), we get ω(N) = k_{1}, and from (58) and the prime number theorem, we have

k_{1} = π(x_{1}) ∼ \frac{x_{1}}{log x_{1}} and k_{2} = π(\sqrt{x_{1}}) ∼ \frac{2\sqrt{x_{1}}}{log x_{1}} .  (62)

Thus, we get

ω(h(n)) − ω(g(n)) ⩽ k_{1} + k_{2} − ω(N) + O(\frac{\sqrt{x_{1}}}{log x_{1}} )  (63)
= k_{2} + O(\frac{\sqrt{x_{1}}}{log x_{1}} ) = O(\frac{\sqrt{x_{1}}}{log x_{1}} ) .  (64)

Finally, from (62), we have k_{1} + k_{2} ∼ k_{1} ∼ O(\frac{x_{1}}{log x_{1}} ), which, with (61) and Lemma 9,

yields n ∼ ∑_{p⩽x_{1}} p ∼ \frac{x_{1}^{2}}{2 log x_{1}} . Therefore, x_{1} ∼ \sqrt{n log n} and log x_{1} ∼ (1/2) log n holds,

which completes the proof of Theorem 24.

4.5 Asymptotic estimates for log h(n) and ω(h(n))

Theorem 25. There exists a > 0 such that, when n → +∞,

log h(n) = \sqrt{Li^{−1}(n)} + O(\sqrt{n}e^{−a\sqrt{log n}}) .  (65)

If Θ > 1/2 and ξ < Θ, then

log h(n) = \sqrt{Li^{−1}(n)} + Ω_{±} ((n log n)^{ξ/2}) .  (66)

Under the Riemann hypothesis, i.e., Θ = 1/2, we have

log h(n) = \sqrt{Li^{−1}(n)} + O(((n log n)^{1/4})) .  (67)
log h(n) < \sqrt{Li^{−1}(n)} for n large enough.  (68)

Proof. The above theorem is proved in [12, Theorem 1] with g(n) instead of h(n), so that its proof follows from Theorem 23.

Theorem 26. There exists a > 0 such that, when n → +∞,

ω(h(n)) = Li (\sqrt{Li^{−1}(n)}) + O(\sqrt{n}e^{−a\sqrt{log n}}) .  (69)

If Θ > 1/2 and ξ < Θ, then

ω(h(n)) = Li (\sqrt{Li^{−1}(n)}) + Ω_{±} ((n log n)^{ξ/2}) .  (70)

Under the Riemann hypothesis, i.e., Θ = 1/2, we have

ω(h(n)) = Li (\sqrt{Li^{−1}(n)}) + O(n^{1/4}(log n)^{−3/4}) .

Proof. The proof follows from [12, Théorème 2] and from Theorem 24.

Note that the corollary of [12, p. 225] is also valid with g(n) replaced by h(n) to give an asymptotic expansion of log h(n) according to the powers of 1/ log n.

We hope to make more precise the behavior of h(n) and ω((h(n)) under the Riemann hypothesis in another paper.

5 G-sequences, a tool for bounding above P^{+}(h(n))

Lemma 27 is [4, Proposition 3.3]. Lemma 28 below is an obvious corollary.

Lemma 27. Let n ⩾ 2 be an integer and p, p′ be distinct primes such that p+p′ ⩽ P^{+}(h(n)). Then, at least one of p, p′ divides h(n).

Lemma 28. If q is a prime divisor of h(n), there exists at most one prime ⩽ q/2 that does not divide h(n).

Definition 29. Let γ, γ′ be such that 0 < γ < γ′ < 1 and γ′ < \frac{1 + γ^{2}}{2} . We define

α = 2γ′ − 1 and β = γ^{2}.  (71)

Then α < β and the pair of intervals (I, J) defined by

I(γ, γ′) = (α, β] and J(γ, γ′) = (γ, γ′] .

is called the G-pair associated with (γ, γ′).

Lemma 30 can be found in [9, Lemma 2]. (In [9], this result is enunciated in the case of the Landau function g(n).)

Let I be an interval and λ be a real number. Let us write λI = {λx; x ∈ I}.

Lemma 30. Let (I, J) be a G-pair, n ⩾ 2 and q a prime factor of h(n). If qI contains at least one prime divisor of h(n), then at most one prime in qJ fails to divide h(n).

Proof. Let us remark that γ = \sqrt{β} and γ′ = (1 + α)/2. By contradiction, let us suppose that p, p′ in qJ are distinct primes that do not divide h(n). Let q′ be a prime in qI dividing

h(n). Let M = \frac{pp′}{qq′} h(n). Then

ℓ(M) = p + p′ − q − q′ + ℓ(h(n)) ⩽ 2γ′q − q − αq + ℓ(h(n)) = ℓ(h(n)).

But pp′ − qq′ > (\sqrt{β}q)^{2} − q(βq) = 0, so M > h(n), giving a contradiction.

Definition 31. A G-sequence of length ℓ is a finite sequence (γ_{j})_{0⩽j⩽ℓ+1} satisfying γ_{0} = 0,

γ_{1} = \frac{1}{2} and, for 1 ⩽ j ⩽ ℓ

0 < γ_{j} < 1 and γ_{j} < γ_{j+1} < \frac{1 + γ_{j}^{2}}{2} .  (72)

Let us define I_{0} = (0, \frac{1}{4}] , J_{0} = (0, \frac{1}{2}] and, for 1 ⩽ j ⩽ ℓ, I_{j} and J_{j} by

α_{j} = 2γ_{j+1} − 1, β_{j} = γ_{j}^{2}, I_{j} = (α_{j}, β_{j}] and J_{j} = (γ_{j}, γ_{j+1}] .  (73)

From (73) we have that, for j ⩾ 1, the pair ((α_{j}, β_{j}] , (γ_{j}, γ_{j+1}]) is a G-pair.

In Section 5.2 we study the uniform G-sequences such that the quotient α_{j}/β_{j} is a constant.

Definition 32. Let Γ = (γ_{j})_{0⩽j⩽ℓ+1} be a G-sequence and y ⩾ 12. For 1 ⩽ i ⩽ ℓ we let m_{i} denote the cardinality of the set of indices j ∈ {0, 1, …, ℓ} such that I_{i} ∩ J_{j} ≠ ∅. The G-sequence Γ is y-admissible if, for every λ ⩾ y and each i, 1 ⩽ i ⩽ ℓ, the interval λI_{i} contains at least m_{i} + 1 primes.

Remark 33. For every G-sequence, by (73), I_{1} = (α_{1}, 1/4] ⊂ J_{0} = (0, 1/2]; thus m_{1} = 1. Therefore, if (γ_{j})_{0⩽j⩽ℓ+1} is admissible, the interval yI_{1} = (yα_{1}, y/4] contains at least m_{1}+1 = 2 primes. This needs y/4 ⩾ 3, i.e., y ⩾ 12.

Remark 34. By Lemma 13 (i), the G-sequence (γ_{j})_{0⩽j⩽ℓ+1} is y–admissible if and only, for 1 ⩽ j ⩽ ℓ, we have the inequality α_{j}/β_{j} ⩽ η_{m_{j}+1}(yβ_{j}).

Lemma 35. Let Γ = (γ_{j})_{0⩽j⩽ℓ+1} be a G-sequence of length ℓ and m an integer such that m ⩾ m_{j} + 1 for 1 ⩽ j ⩽ ℓ. Let us suppose that y is a real number such that,

α_{j}/β_{j} ⩽ η_{m}(yβ_{j}) for 1 ⩽ j ⩽ ℓ.  (74)

Then Γ is y–admissible.

Proof. Since (r, x) ↦ η_{r}(x) is nonincreasing in r, we may write

α_{j}/β_{j} ⩽ η_{m}(yβ_{j}) ⩽ η_{m_{j}+1}(yβ_{j})

and, by using the previous Remark 34, Γ is y–admissible.

Proposition 36. Let Γ = (γ_{j})_{0⩽j⩽ℓ+1} be a G-sequence of length ℓ, and q a prime factor of h(n). If Γ is q-admissible then, for all j, 0 ⩽ j ⩽ ℓ the interval qJ_{j} = q (γ_{j}, γ_{j+1}] contains at most one prime which does not divide h(n). Moreover

θ(qγ_{ℓ+1}) − ℓ log q < θ(qγ_{ℓ+1}) − ℓ log q − ∑_{j=1}^{ℓ+1} log γ_{j} ⩽ log h(n).  (75)

Proof. Let P(j) be the property that there exists at most one prime number in qJ_{j} that does not divide h(n).

If j = 0, by Lemma 28, qJ_{0} = (0, q/2] contains at most one prime which does not divide h(n). So P(0) is true.

By Remark 33, m_{1} = 1. Thus, by Definition 32, qI_{1} contains at least two primes, p, p′. Since the upper bound of qI_{1} is q/4, by Lemma 27 we have that p or p′ divides h(n), and, by Lemma 30, there is at most one prime in qJ_{1} which does not divide h(n). Thus P(1) is true.

Let j ∈ [2, ℓ] such that P(r) is true for r < j. The upper bound of I_{j} is β_{j} = γ_{j}^{2} < γ_{j}.

We thus have qI_{j} ⊂ (0, qγ_{j}] = ⋃_{r=0}^{j−1} qJ_{r}. By the induction hypothesis, each of the intervals qJ_{r},

(0 ⩽ r ⩽ j − 1), contains at most one prime number which does not divide h(n). Since qI_{j} intersects m_{j} of these intervals, it contains at most m_{j} primes not dividing h(n). But, by hypothesis, qI_{j} contains at least m_{j} + 1 primes. Thus, one of them divides h(n) and, by Lemma 30, this implies that qJ_{j} contains at most one prime which does not divide h(n). This is to say that P(j) is true.

So we have just proved that h(n) is divisible by all the primes in (0, qγ_{ℓ+1}], but at most one prime q_{j} ∈ q (γ_{j}, γ_{j+1}] for each j = 0, 1, 2, …, ℓ. Since q divides h(n) we have

h(n) ⩾ q \frac{∏_{p⩽qγ_{ℓ+1}} p}{∏_{j=0}^{ℓ} q_{j}} ⩾ q \frac{∏_{p⩽qγ_{ℓ+1}} p}{∏_{j=0}^{ℓ} qγ_{j+1}} .

Applying log, this gives the second inequality in (75). The first inequality comes from

∑_{j=1}^{ℓ+1} log γ_{j} < 0.

Proposition 37. Let n_{0}, y, a be positive real numbers such that

12 ⩽ y ⩽ a\sqrt{n_{0} log n_{0}}

and ℓ ⩾ 1, integer. We assume that Γ = (γ_{j})_{0⩽j⩽ℓ+1}, is a G-sequence y-admissible of length ℓ. Let us define

D_{ℓ} = γ_{ℓ+1}θ_{min}(yγ_{ℓ+1}) − \frac{ℓ log y + ∑_{j=1}^{ℓ+1} log γ_{j}}{y} ,  (76)

and let us suppose that D_{ℓ} > 0. Then, for n ⩾ n_{0}, we have

P^{+}(h(n)) ⩽ max(a, b)\sqrt{n log n} with b = \frac{1.0482017}{D_{ℓ}}.  (77)
P^{+}(h(n)) ⩽ max(a, b′)\sqrt{n log n} with b′ = \frac{1}{D_{ℓ}} (1 + \frac{log_{2} n_{0} − 0.975}{2 log n_{0}}) .  (78)

The second upper bound is better than the first one for n ⩾ 3 259 922 785. Proof. Let n be an integer, n ⩾ n_{0}. Let us set, for simplification, q = P^{+}(h(n)).

(i) If q < y, then, by hypothesis, we have

q < y ⩽ a\sqrt{n_{0} log n_{0}} ⩽ a\sqrt{n log n}.  (79)

(ii) If q ⩾ y, then qγ_{ℓ+1} ⩾ yγ_{ℓ+1}. With Equation (35) this gives θ(qγ_{ℓ+1}) ⩾ qγ_{ℓ+1}θ_{min}(yγ_{ℓ+1}). We remark that ∑_{j=1}^{ℓ+1} |log γ_{j}| ⩽ (ℓ + 1) log 2 ⩽ 2ℓ log 2

which implies that t ↦ (ℓ log t + ∑_{j=1}^{ℓ+1} log γ_{j})/t is decreasing for t ⩾ 4e. From this and

Equation (76) defining D_{ℓ}, we infer that

D_{ℓ} ⩽ \frac{θ(qγ_{ℓ+1})}{q} − \frac{ℓ log q + ∑_{j=1}^{ℓ+1} log γ_{j}}{q} .  (80)

Since q ⩾ y, the sequence Γ being y-admissible is a fortiori q–admissible. Then, by using Equation (75) of Proposition 36, Equation (80) gives 0 < qD_{ℓ} ⩽ log h(n), from which, by using (41) and (40) to get upperbounds for log h(n), we obtain

q = P^{+}(h(n)) ⩽ min(b, b′)\sqrt{n log n}.  (81)

Inequalities (77) and (78) follow from (79) and (81).

5.1 The optimal y-admissible G-sequence

The upper bound (75) in Proposition 36 leads us to construct y-admissible G-sequences with γ_{j} as large as possible. This is the subject of this section.

Let y be ⩾ 12 and (γ_{0} = 0, γ_{1} = 1/2, γ_{2}) be a G-sequence y–admissible of length 1.

By (73), γ_{2} = \frac{1 + α_{1}}{2} ; thus, the largest value of γ_{2} is obtained by giving to α_{1} the largest possible value. By Remark 33, we have m_{1} = 1 so that, by Remark 34, the sequence (γ_{0} = 0, γ_{1} = 1/2, γ_{2}) is y–admissible if and only if α_{1} ⩽ \frac{1}{4}η_{2}(\frac{y}{4}). So, we get the largest value for γ_{2} by setting α_{1} = \frac{1}{4}η_{2}(\frac{y}{4}) and γ_{2} = \frac{1+α_{1}}{2} .

Now let (γ_{j})_{0⩽j⩽ℓ+1} be a G-sequence y–admissible of length ℓ, that we want to extend.

Equation γ_{ℓ+1} = β_{ℓ+1}^{2} determines β_{ℓ+1}. Equality γ_{ℓ+2} = \frac{1 + α_{ℓ+1}}{2} shows that the largest value of γ_{ℓ+2} is got by choosing α_{ℓ+1} as large as possible. We set m = 1 and we try

α_{ℓ+1} = β_{ℓ+1}η_{m+1}(yβ_{ℓ+1}).  (82)

– If α_{ℓ+1} ⩽ α_{ℓ} our construction fails because it is not possible to satisfy γ_{ℓ+1} = \frac{1 + α_{ℓ}}{2} <

\frac{1 + α_{ℓ+1}}{2} = γ_{ℓ+2}.

– If α_{ℓ+1} > α_{ℓ} let us consider I_{ℓ+1} = (α_{ℓ+1}, β_{ℓ+1}]. If this interval meets at most m intervals among J_{0}, J_{1}, …, J_{ℓ}, we finish by choosing γ_{ℓ+2} = (1 + α_{ℓ+1})/2. If I_{ℓ+1} meets m′ > m intervals among J_{0}, J_{1}, …, J_{ℓ}, we have to choose again α_{ℓ+1} by using formula (82) with m replaced by m + 1.

More formally this construction is described in Algorithm 1. This algorithm is not guaranteed to terminate; however, for y = 1853.18, it gives the y–admissible G-sequence of length 10 which we will use in Section 6.1.

Algorithm 1 Computes α_{ℓ+1}, β_{ℓ+1}, γ_{ℓ+2} from γ_{ℓ+1}, α_{ℓ} and y β_{ℓ+1} = γ_{ℓ+1}^{2}, m = 1 Repeat

α_{ℓ+1} = β_{ℓ+1}η_{m+1}(yβ_{ℓ+1}) if α_{ℓ+1} ⩽ α_{ℓ} return FAIL else m = m + 1

until (α_{ℓ+1}, β_{ℓ+1}] meets at most m intervals (0, γ_{1}] , …, (γ_{ℓ}, γ_{ℓ+1}] γ_{ℓ+2} = (1 + α_{ℓ+1})/2

5.2 Uniform G-sequences

The theoretical study of optimal G-sequences does not seem easy. In this section we introduce the uniform G-sequences, less efficient for numerical computation, but simpler to study.

Definition 38. Let η be a real number, 0 < η < 1. We define γ_{0} = 0 and, for j ⩾ 1,

γ_{j} = γ_{j}(η) = \frac{1 + ηγ_{j−1}^{2}}{2} .  (83)

Remark 39. Let us note that γ_{j}(η) is an increasing function of j and η. Note also that

α_{j} = 2γ_{j+1} − 1 = ηγ_{j}^{2} = ηβ_{j}.  (84)

Lemma 40. With the notation of Definition 38, let us write ε = ε(η) = 1 − η, and L_{ε} = lim_{j→+∞} γ_{j}. then

L_{ε} = \frac{1}{1 + \sqrt{ε}} and, for j ⩾ 0, L_{ε} − γ_{j} ⩽ L_{ε}(1 − \sqrt{ε})^{j} ⩽ (1 − \sqrt{ε})^{j}.  (85)

For each integer ℓ ⩾ 1, the sequence (γ_{j}(η))_{0⩽j⩽ℓ+1} defined by (83) is a G-sequence. We call it the uniform G-sequence of parameter η and length ℓ.

Proof. The proof is by induction. We have γ_{0} = 0, γ_{1} = \frac{1 + ηγ_{0}^{2}}{2} = \frac{1}{2}, and, for j ⩾ 1,

γ_{j+1} = \frac{1 + ηγ_{j}^{2}}{2} < \frac{1 + γ_{j}^{2}}{2} .

Moreover γ_{j+1} = f(γ_{j}) with f = t ↦ (1 + (1 − ε)t^{2})/2. Function f is increasing for t ⩾ 0

and has two fix points which are \frac{1}{1 + \sqrt{ε}} and \frac{1}{1 − \sqrt{ε}}. Since γ_{0} < γ_{1}, the sequence (γ_{j}) is

increasing with limit L_{ε} = \frac{1}{1 + \sqrt{ε}}. Moreover, since f′ is increasing,

L_{ε} − γ_{j} = f(L_{ε}) − f(γ_{j−1}) < f′(L_{ε})(L_{ε} − γ_{j−1}) = (1 − \sqrt{ε})(L_{ε} − γ_{j−1})
⩽ (1 − \sqrt{ε})^{j}(L_{ε} − γ_{0}) = L_{ε}(1 − \sqrt{ε})^{j}.

For each ℓ ⩾ 1, the conditions of Definition 72 are satisfied and (γ_{j})_{0⩽j⩽ℓ} is a G-sequence.

Throughout this section η is a positive real number satisfying 0 < η < 1, ε = 1 − η, (γ_{j}) is the uniform G-sequence of parameter η, and I_{j} = (α_{j}, β_{j}], J_{j} = (γ_{j}, γ_{j+1}] are the intervals associated with this G-sequence (cf. Definition 72).

Lemma 41. Let us write u_{j} = L_{ε} − γ_{j}. Then (γ_{j+1} − γ_{j}) is a decreasing sequence, and, for every j we have

γ_{j+1} − γ_{j} = \sqrt{ε}u_{j} + \frac{u_{j}^{2}}{2} (1 − ε).

In particular \sqrt{ε}(L_{ε} − γ_{j}) < γ_{j+1} − γ_{j}.

Proof. Indeed, since γ_{j} = L_{ε} − u_{j} = \frac{1}{1 + \sqrt{ε}} − u_{j}, we have, with f(t) = (1 − (1 − εt^{2}))/2,

2(γ_{j+1} − γ_{j}) = 2f(γ_{j}) − 2γ_{j} = 1 + (1 − ε)γ_{j}^{2} − 2γ_{j}
= 1 + (1 − ε) (\frac{1}{1 + \sqrt{ε}} − u_{j})^{2} − \frac{2}{1 + \sqrt{ε}} + 2u_{j}
= 2\sqrt{ε}u_{j} + (1 − ε)u_{j}^{2} > 2\sqrt{ε}u_{j} = 2\sqrt{ε}(L_{ε} − γ_{j}).

Lemma 42. There is no pair (i, j) such that (γ_{i}, γ_{i+1}] ⊂ (α_{j}, β_{j}]. Therefore each interval I_{j} meets at most two intervals J_{i}.

Proof. Let us suppose (γ_{i}, γ_{i+1}] ⊂ (α_{j}, β_{j}]. Then

α_{j} ⩽ γ_{i} < γ_{i+1} ⩽ β_{j} = γ_{j}^{2}

and

L_{ε} − γ_{i} > L_{ε} − γ_{j}^{2} > L_{ε} − L_{ε}^{2} = L_{ε}(1 − L_{ε}) = \sqrt{ε}L_{ε}^{2}.  (86)

By Lemma 41, we also have

\sqrt{ε}(L_{ε} − γ_{i}) < γ_{i+1} − γ_{i} ⩽ β_{j} − α_{j} = εβ_{j} = εγ_{j}^{2} < εL_{ε}^{2}

which implies L_{ε} − γ_{i} < \sqrt{ε}L_{ε}^{2}, contradicting (86).

6 Estimates of P^{+}(h(n))

In this section, we study the behavior of P^{+}(h(n)) in terms of n. The results are similar to those obtained in [4] for P^{+}(g(n)), except for the numerical value of the constants.

6.1 Maximum of P^{+}(h(n))/\sqrt{n log n} for n ⩾ 4.

Theorem 43. For n ⩾ 4 we have

\frac{P^{+}(h(n))}{\sqrt{n log n}} ⩽ \frac{P^{+}(h(170))}{\sqrt{170 log(170)}} = 1.38757162 ⋯,  (87)

the maximum being attained only for n = 170 with h(170) = 2 × 3 × 5 × 7 × 11 × 13 × 17 × 19 × 23 × 29 × 41 = N_{10} × 41 and P^{+}(h(170)) = 41.

Proof. We use Proposition 37 with n_{0} = 150 000, a = 1.386 and y = 1853.18. Using Algorithm 1 we compute the first 10 terms of the optimal y–admissible G-sequence. We get intervals

\begin{matrix}j & α_{j} & β_{j} & γ_{j+1} & \{i\} & D_{j} \\ 1 & 0.2390 ⋯ & 0.2500 ⋯ & 0.619515 ⋯ & 0 & 0.582374 ⋯ \\ 2 & 0.3722 ⋯ & 0.3837 ⋯ & 0.686121 ⋯ & 0 & 0.641498 ⋯ \\ 3 & 0.4569 ⋯ & 0.4707 ⋯ & 0.728463 ⋯ & 0 & 0.677646 ⋯ \\ 4 & 0.5150 ⋯ & 0.5306 ⋯ & 0.757531 ⋯ & 1 & 0.701222 ⋯ \\ 5 & 0.5569 ⋯ & 0.5738 ⋯ & 0.778493 ⋯ & 1 & 0.724454 ⋯ \\ 6 & 0.5882 ⋯ & 0.6060 ⋯ & 0.794120 ⋯ & 1 & 0.737558 ⋯ \\ 7 & 0.6094 ⋯ & 0.6306 ⋯ & 0.804703 ⋯ & 1, 2 & 0.745702 ⋯ \\ 8 & 0.6285 ⋯ & 0.6475 ⋯ & 0.814257 ⋯ & 2 & 0.750926 ⋯ \\ 9 & 0.6435 ⋯ & 0.6630 ⋯ & 0.821764 ⋯ & 2 & 0.754179 ⋯ \\ 10 & 0.6554 ⋯ & 0.6752 ⋯ & 0.827725 ⋯ & 2 & 0.755943 ⋯ \end{matrix}

Column {i} contains the values i for which I_{j} meets J_{i}, so that m_{j} is the number of integers appearing in the j^{th} line of the column {i}.

This gives D_{10} = 0.755943 ⋯ and, with (77), b = 1.386614 ⋯ > a which proves that P^{+}(h(n)) < 1.3867\sqrt{n log n} for n ⩾ 150 000. The computation of h(n) for 4 ⩽ n ⩽ 150 000 shows that the maximum is obtained only once, for n = 170.

Lemma 44. Let q be a prime factor of h(n) and η ⩽ η_{3}(q/4) ; let Γ = (γ_{j})_{0⩽j⩽ℓ+1} be the uniform G-sequence of parameter η. This sequence is q–admissible, and

θ(qγ_{ℓ+1}) − ℓ log q ⩽ log h(n).  (88)

Proof. By Lemma 42, each interval I_{j} meets at most 2 intervals J_{j}. Thus, the integer m_{j} introduced in Definition 32 satisfies m_{j} ⩽ 2 for every j. Equality (84), the inequality

β_{1} = \frac{1}{4} ⩽ β_{j} and the fact that η_{3} is nondecreasing give

α_{j} = ηβ_{j} ⩽ β_{j}η_{3}(q/4) ⩽ β_{j}η_{3}(qβ_{j}).

Thus Inequality (74) holds with m = 3 and y = q, and Lemma 35 shows that the sequence Γ is q-admissible. Therefore, from Proposition 36, Eq. (88) holds.

Lemma 45. Let n be an integer and q the largest prime factor of h(n). When n tends to infinity, we have

q = P^{+}(h(n)) ⩽ log h(n)(1 + O(ε)),  (89)

with ε = ε_{1} + \sqrt{ε}_{2} → 0 and

ε_{1} = max_{x⩾ \frac{q}{2}} |\frac{θ(x)}{x} − 1| ,  ε_{2} = max (1 − η_{3}(\frac{q}{4}), (\frac{log q}{\sqrt{q}} )^{2}) < 1.  (90)

Proof. Let us write

η = 1 − ε_{2} and ℓ = ⌊\frac{log q}{\sqrt{ε}_{2}} ⌋ .  (91)

When n → +∞, by (10), q = P^{+}(h(n)) tends to infinity, ε_{1} tends to 0, η_{3}(q/4) tends to 1 (by Proposition 14), ε_{2} and ε tend to 0 and ℓ tends to infinity.

Let Γ = (γ_{j})_{0⩽j⩽ℓ+1} be the uniform G-sequence of parameter η and length ℓ. Since Γ is

increasing, we have qγ_{ℓ+1} ⩾ qγ_{1} = q/2. By the definition of ε_{1}, it comes \frac{θ(qγ_{ℓ+1})}{qγ_{ℓ+1}} ⩾ 1 − ε_{1},

therefore, with the notation of Lemma 40,

\frac{θ(γ_{ℓ+1}q)}{q} ⩾ γ_{ℓ+1} − γ_{ℓ+1}ε_{1}
⩾ γ_{ℓ+1} − ε_{1} = 1 − ε_{1} − (1 − L_{ε_{2}}) − (L_{ε_{2}} − γ_{ℓ+1}).  (92)

One use of Lemma 40 gives

1 − L_{ε_{2}} = 1 − \frac{1}{1 + \sqrt{ε}_{2}} ⩽ \sqrt{ε}_{2}.  (93)

By (91), ℓ + 1 > \frac{log q}{\sqrt{ε}_{2}} ; then a second use of Lemma 40 gives

L_{ε_{2}} − γ_{ℓ+1} ⩽ (1 − \sqrt{ε}_{2})^{ℓ+1} ⩽ (1 − \sqrt{ε}_{2})^{\frac{log q}{\sqrt{ε}_{2}}} ⩽ (\frac{1}{e})^{log q} = \frac{1}{q}.

With (92), (93) and the definition of ε we get

\frac{θ(qγ_{ℓ+1})}{q} ⩾ 1 − ε_{1} − \sqrt{ε}_{2} − \frac{1}{q} = 1 − ε − \frac{1}{q}.  (94)

Definition (91) of ℓ gives ℓ\frac{log q}{q} ⩽ \frac{(log q)^{2}}{q\sqrt{ε}_{2}} . With (94), this gives

\frac{θ(qγ_{ℓ+1})}{q} − ℓ\frac{log q}{q} ⩾ 1 − ε − \frac{1}{q} − \frac{log^{2} q}{q\sqrt{ε}_{2}} .

By the definition of ε_{2}, for q ⩾ 3, we have \frac{1}{q} ⩽ \frac{log^{2} q}{q} ⩽ ε_{2} ⩽ \sqrt{ε_{2}}, and therefore

\frac{θ(qγ_{ℓ+1})}{q} − ℓ\frac{log q}{q} ⩾ 1 − ε − \frac{1}{q} − \sqrt{ε_{2}} ⩾ 1 − ε − 2\sqrt{ε}_{2} ⩾ 1 − 3ε.  (95)

By the definition of ε_{2} and η (cf. (90)) and (91)), we have η ⩽ η_{3} (\frac{q}{4}), so that Lemma 44 applies to the G-sequence Γ. Inequality (95) shows that θ(qγ_{ℓ+1}) − ℓ log q is positive for n large enough, so that, by using (88) and (95), we may write

q ⩽ \frac{log h(n)}{\frac{θ(qγ_{ℓ+1})}{q} − ℓ\frac{log q}{q}} ⩽ \frac{log h(n)}{1 − 3ε} = log h(n)(1 + O(ε)).

Proposition 46. When n tends to infinity, P^{+}(h(n)) ∼ \sqrt{n log n}. Proof. Let us write q = P^{+}(h(n)). By (10), q tends to infinity with n. Using successively the prime number theorem and Inequality (11), we get

q ∼ θ(q) ⩾ log h(n).

With (89), this gives q ∼ log h(n), and ends the proof with Theorem 18.

6.2 Asymptotic upper bound for P^{+}(h(n))

Theorem 47. Let P^{+}(h(n)) be the largest prime factor of h(n). When n tends to infinity, P^{+}(h(n)) is bounded as follows:

(i) Without any hypothesis, there exists a > 0 such that

P^{+}(h(n)) ⩽ \sqrt{Li^{−1}(n)} + O(\sqrt{n}e^{−a\sqrt{log n}}) .  (96)

(ii) Under the Riemann Hypothesis:

P^{+}(h(n)) ⩽ \sqrt{Li^{−1}(n)} + O(n^{3/8}(log n)^{7/8}) .  (97)

(iii) Under the Riemann Hypothesis and the Cramér conjecture (Equation (30)):

P^{+}(h(n)) ⩽ \sqrt{Li^{−1}(n)} + O(n^{1/4}(log n)^{9/4}) .  (98)

Proof. Let us write q = P^{+}(h(n)). By Proposition 46 we have

q ∼ \sqrt{n log n} and log q ∼ \frac{1}{2} log n.  (99)

We shall also use the relation

Li^{−1}(n) ∼ n log n.  (100)

We will apply Lemma 45, evaluating in the three cases the quantities ε_{1}, ε_{2} and ε = ε_{1} +\sqrt{ε_{2}}.

(i) By the prime number theorem (20), there is some a_{1} > 0 such that

ε_{1} = O(e^{−a_{1}\sqrt{log n}}) .

By Proposition 14, (i), we have

1 − η_{3} (\frac{q}{4}) = O(q^{−0.475}) .

Thus, by (99),

\sqrt{ε}_{2} = O(q^{−0.2375}) = O(n^{−0.11875})

and ε = ε_{1} + \sqrt{ε_{2}} = O(exp(−a_{1}\sqrt{log n}). Lemma 45 gives the inequality

q ⩽ (log h(n))(1 + O(exp(−a_{1}\sqrt{log n})) ).  (101)

By (65) there is a_{2} > 0 such that

log h(n) = \sqrt{Li^{−1}(n)} + O(\sqrt{n}e^{−a_{2}\sqrt{log n}})

which, with (101) and (100), proves (96) for a < min(a_{1}, a_{2}). (ii) Under the Riemann hypothesis, we have, by (21),

ε_{1} = O(\frac{log^{2} q}{\sqrt{q}} )  (102)

and Inequality (33) of Proposition 14 gives

1 − η_{3} (\frac{q}{4}) = O(\frac{log q}{\sqrt{q}} ) .

We thus get ε_{2} = O(\frac{log q}{\sqrt{q}} ) and, by (99)

ε = ε_{1} + \sqrt{ε_{2}} = O(\frac{\sqrt{log q}}{q^{1/4}} ) = O(\frac{(log n)^{3/8}}{n^{1/8}} ) ,

so that, by Lemma 45,

q ⩽ log h(n) (1 + O(\frac{(log n)^{3/8}}{n^{1/8}} )) ,

which, with (67) and (100), yields (97). (iii) Estimate (102) is still true, while the definition (90) of ε_{2} and Equation (34) for k = 3

give ε_{2} = O(\frac{log^{2} q}{q} ) and then

ε = O(\frac{log^{2} q}{\sqrt{q}} ) = O(\frac{(log n)^{7/4}}{n^{1/4}} ) ,

which, by Lemma 45, (67) and (100), proves (98). Let us remark that (98) is still true if we replace Cramér’s conjecture (30) by the weaker relation p_{i+1} − p_{i} = O(log^{4} p_{i}) .

6.3 Effective upper bound for P^{+}(h(n))

Theorem 48. P^{+}(h(n)) satisfies the following inequalities

P^{+}(h(n)) ⩽ log h(n)(1 + \frac{1.012}{log n}) (n ⩾ 138 940).  (103)

P^{+}(h(n)) ⩽ \sqrt{n log n} (1 + \frac{log_{2} n + 1.145}{2 log n}) (n ⩾ 233 089).  (104)

Proof. The computation of P^{+}(h(n)) and log(h(n)) for 2 ⩽ n ⩽ 10^{10}, shows that Inequalities (103) and (104) are satisfied for these values of n.

Let us suppose n > 10^{10}, and that q = P^{+}(h(n)) satisfies

q > log h(n) (1 + \frac{1}{log n}) .  (105)

Since n ⩾ 10^{10} > 7387, it results from (39) that

q > \sqrt{n log n} (1 + \frac{1}{log n}) = \sqrt{n} (\sqrt{log n} + \frac{1}{\sqrt{log n}}) .

Since t ↦ t + 1/t for t ⩾ 1 is increasing this gives

q > \sqrt{n} (\sqrt{log 10^{10}} + \frac{1}{\sqrt{log 10^{10}}} ) ⩾ 5.006923\sqrt{n} > 500 692.

Therefore,

q ⩾ 500 693,  0.25 q ⩾ 125 173  (106)

and

log(0.25 q) > log(0.25 × 5.00693\sqrt{n}) > log(\sqrt{n}) = 0.5 log n.  (107)

Here we define η and ε by

ε = \frac{0.4822}{log^{2} n} and η = 1 − ε.  (108)

From (108) we deduce

\frac{0.6944}{log n} ⩽ \sqrt{ε} ⩽ \frac{0.6945}{log n}  (109)

and, also, with n ⩾ 10^{10},

ε < 0.00091 and η = 1 − ε > 0.99909.  (110)

From the table [3, Tabulation de delta3], we get δ_{3}(85 991) = 0.120544 ⋯, which, with the fact that δ_{3} is nonincreasing (cf. §3.6) and (106), implies 0.12055 ⩾ δ_{3}(85 991) ⩾ δ_{3}(125 173) ⩾ δ_{3}(0.25q). Therefore, Definition (108) of ε and the lower bound (107) give

ε = \frac{0.4822}{log^{2} n} ⩾ \frac{0.12055}{(log(0.25 q))^{2}} ⩾ \frac{δ_{3}(0.25 q)}{(log(0.25 q))^{2}} .  (111)

From (111), with (37), (where we take x = y = 0.25 q), we get

η = 1 − ε ⩽ 1 − \frac{δ_{3}(0.25 q)}{(log(0.25 q))^{2}} ⩽ η_{3} (0.25 q) .

The uniform G-sequence of parameter η satisfies the hypothesis of Lemma 44. We apply this lemma, choosing

ℓ = ⌊2.5 log n log_{2} n⌋ ⩾ ⌊2.5 log 10^{10} log_{2} 10^{10}⌋ = 180.  (112)

We have seen (cf. Remark 39) that γ_{j} = γ_{j}(η) is an increasing function of η and j. Since, by (110), η > 0.99909 and ℓ ⩾ 180 we have γ_{ℓ+1} ⩾ γ_{180}(0.99909) > 0.9705. By using (106) and (107), we get

qγ_{ℓ+1} ⩾ 0.9705 · 500 693 ⩾ 485 922 and log qγ_{ℓ+1} ⩾ log 0.25 q ⩾ 0.5 log n.

The table of θ_{d}-champion numbers given in [3, Tabulation de thetad] yields θ_{d}(485 922) ⩽ 0.3644, so that, from (36), we get

\frac{θ(qγ_{ℓ+1})}{qγ_{ℓ+1}} ⩾ 1 − \frac{θ_{d}(485 922)}{(log qγ_{ℓ+1})^{2}} ⩾ 1 − \frac{0.3644}{(log qγ_{ℓ+1})^{2}} ⩾ 1 − \frac{1.4576}{(log n)^{2}} .  (113)

Using n ⩾ 10^{10}, this gives

\frac{θ(qγ_{ℓ+1})}{q} ⩾ (1 − \frac{1.4576}{log^{2} n}) γ_{ℓ+1} ⩾ (1 − \frac{0.0634}{log n}) γ_{ℓ+1}.  (114)

Now we have to get a lower bound for γ_{ℓ+1}. From (85), using (109) and (112), we deduce

γ_{ℓ+1} ⩾ \frac{1}{1 + \sqrt{ε}} − (1 − \sqrt{ε})^{ℓ+1} ⩾ 1 − \sqrt{ε} − (1 − \frac{0.6944}{log n})^{ℓ+1}
⩾ 1 − \sqrt{ε} − (1 − \frac{0.6944}{log n})^{2.5 log_{2} n log n}

⩾ 1 − \sqrt{ε} − [(1 − \frac{0.6944}{log n})^{\frac{log n}{0.6944}} ]^{2.5 ×0.6944 log_{2}(n)}
⩾ 1 − \frac{0.6945}{log n} − \frac{1}{(log n)^{2.5×0.6944}} ⩾ 1 − \frac{0.794}{log n}.

With (114), this gives

\frac{θ(qγ_{ℓ+1})}{q} ⩾ (1 − \frac{0.0634}{log n}) (1 − \frac{0.794}{log n}) ⩾ 1 − \frac{0.8574}{log n} + \frac{0.05034}{log^{2} n}.  (115)

Since \frac{log t}{t} is a decreasing function of t for t ⩾ e, and q ⩾ \sqrt{n log n}, we have

\frac{log q}{q} ⩽ \frac{1}{2} \frac{log(n log n)}{\sqrt{n log n}}.

Using(112) and the fact that t ↦ (log t)^{3/2} log_{2} t log(t log t)/\sqrt{t} is decreasing for t ⩾ 10^{10}, this gives

ℓ\frac{log q}{q} ⩽ 1.25 log n log_{2} n\frac{log(n log n)}{\sqrt{n log n}} ⩽ \frac{0.114}{log n}.  (116)

Since the inequality log n > 0.9714 holds, Formula (88) of Lemma 44, with (115) and (116) give

q ⩽ \frac{log h(n)}{1 − \frac{0.9714}{log n} + \frac{0.05034}{log^{2} n}} .

On the interval 0 ⩽ X ⩽ 1/ log 10^{10}, the fraction \frac{0.9714 − 0.05034X}{1 − 0.9714X + 0.05034X^{2}} is increasing

and less than 1.012. This implies, for n ⩾ 10^{10},

\frac{1}{1 − \frac{0.9714}{log n} + \frac{0.05034}{log^{2} n}} = 1 + \frac{\frac{0.9714}{log n} − \frac{0.05034}{log^{2} n}}{1 − \frac{0.9714}{log n} + \frac{0.05034}{log^{2} n}} ⩽ 1 + \frac{1.012}{log n}

which, with (105), proves (103). Applying (40), we deduce from that

q ⩽ \sqrt{n log n} (1 + \frac{log_{2} n − 0.975}{2 log n}) (1 + \frac{1.012}{log n})
⩽ \sqrt{n log n} (1 + \frac{log_{2} n + 1.049}{2 log n} + \frac{1.012}{log n} \frac{log_{2} n − 0.975}{2 log n})
⩽ \sqrt{n log n} (1 + \frac{log_{2} n + 1.049}{2 log n} + \frac{1}{2 log n} \frac{1.012(log_{2} 10^{10} − 0.975)}{log 10^{10}})

which completes the proof of (104).

6.4 Lower bound for P^{+}(h(n))

Lemma 49. For all n ⩾ 7387, we have

P^{+}(h(n)) ⩾ \frac{\sqrt{n log n}}{1.000028}.  (117)

Proof. From (11) we have log h(n) ⩽ θ(P^{+}(h(n))). Inequalities (39) and (24) end the proof.

Theorem 50. For n ⩾ 7 992 we have

P^{+}(h(n)) ⩾ \sqrt{n log n} (1 + \frac{log_{2} n − 1.18}{2 log n}) ,  (118)

and, for n ⩾ 21

P^{+}(h(n)) ⩾ \sqrt{n log n}.  (119)

Proof. First, we compute h(n) and P^{+}(h(n)) for n ⩽ 10^{8} and we verify that (118) is true for 7 992 ⩽ n ⩽ 10^{8} and false for n = 7 991, and that (119) is true for 21 ⩽ n ⩽ 10^{8} and false for n = 20.

Let us note that for n > 10^{8} Eq. (119) is implied by Eq. (118), since log_{2} n > log_{2} 10^{8} = 2.913 ⋯ > 1.17.

Thus it remains to prove that Eq. (118) is true for n > 10^{8}. Let us write q = P^{+}(h(n)). From Eq. (11), we have log h(n) ⩽ θ(q). With Eq. (38) this gives

\sqrt{n log n} (1 + \frac{log_{2} n − 1.16}{2 log n}) ⩽ log h(n) ⩽ θ(q).  (120)

(i) If n_{0} = 10^{8} < n ⩽ n_{1} = 6.6 × 10^{21}, by Eq. (87), we get

q ⩽ 1.388\sqrt{n log n} ⩽ 8 × 10^{11}.  (121)

Thus, by Eq. (24) we have θ(q) < q, which, with Eq. (120), implies inequality (118).

(ii) If n > n_{1} = 6.6 × 10^{21}. By Eq. (117), q = P^{+}(h(n)) satisfies

q > 5.7 × 10^{11},

and, by Eq. (25),

θ(q) − q ⩽ 0.05\frac{q}{log^{2} q} < \frac{0.05}{log(5.7 × 10^{11})} \frac{q}{log q} < 0.002\frac{q}{log q} .

With Eq. (120) this gives

\sqrt{n log n} (1 + \frac{log_{2} n − 1.16}{2 log n}) < q + 0.002\frac{q}{log q} .  (122)

Using Eq. (117) we have q > \sqrt{n} and log q > (log n)/2. With Eq. (87), we get

\frac{q}{log q} < \frac{1.388\sqrt{n log n}}{log q} < \frac{1.388\sqrt{n log n}}{\frac{1}{2} log n} = 5.552\frac{\sqrt{n log n}}{2 log n}.

By noticing that 0.002×5.552 < 0.02, we deduce from Eq. (122) that, for n ⩾ 6.6×10^{21}, we have

q = P^{+}(h(n)) > \sqrt{n log n} (1 + \frac{log_{2} n − 1.18}{2 log n}) ,

which ends the proof of Theorem 50.

Theorem 51. (i) There exists two positive constants C and a such that, for n ⩾ 2,

P^{+}(h(n)) ⩾ \sqrt{Li^{−1}(n)} − C\sqrt{n} exp(−a\sqrt{log n}).  (123)

(ii) Under the Riemann hypothesis, there exists a positive constant C′ such that

P^{+}(h(n)) ⩾ \sqrt{Li^{−1}(n)} − C′n^{1/4}(log n)^{9/4}.  (124)

Proof. This is similar to the proof of [4, Theorem 9.2] and follows by using Eqs. (20), (22), and (11), and the lower bounds of log h(n) given in Eqs. (65) and (67).

6.5 Comparison of P^{+}(h(n)) and log h(n)

Lemma 52. There exist infinitely many prime numbers p such that θ(p) < p and infinitely many prime numbers p such that θ(p) > p.

Proof. This is [4, Lemma 10.1], based on Littlewood’s oscillation theorem.

Theorem 53. There exist infinitely many values of n such that P^{+}(h(n)) > log(h(n)) and infinitely many values of n such that P^{+}(h(n)) < log(h(n)).

Proof. Let us consider the values n belonging to the sequence (σ_{k}). For such an n, n = p_{1} + p_{2} + ⋯ + p_{k}, we have (cf. Eq. (8))

h(n) = N_{k}, log h(n) = θ(p_{k}), P^{+}(n) = p_{k},

so that P^{+}(h(n))−log h(n) = p_{k} −θ(p_{k}). By Lemma 52, there are infinitely many values of k for which this quantity is positive, and infinitely many values of k for which it is negative.

Proposition 54. Let p_{k_{0}} be the smallest prime such that θ(p_{k_{0}}) > p_{k_{0}} holds, and n_{0} the smallest integer such that P^{+}(h(n_{0})) < log h(n_{0}). Then we have

σ_{k_{0}−2} + p_{k_{0}} ⩽ n_{0} < σ_{k_{0}}.  (125)

Proof. From Eqs. (6) and (8), we get

log h(σ_{k_{0}}) = θ(p_{k_{0}}) > p_{k_{0}} = P^{+}(N_{k_{0}}) = P^{+}(h(σ_{k_{0}}),

which proves the upper bound n_{0} ⩽ σ_{k_{0}}.

Now, let n satisfy n < σ_{k_{0}−1} so that k = k(n) satisfies k < k_{0} − 1, σ_{k} ⩽ n < σ_{k+1}, θ(p_{k}) < p_{k} (as θ(p_{k}) is transcendental, it cannot be equal to p_{k}) and θ(p_{k+1}) < p_{k+1}.

If σ_{k} ⩽ n < σ_{k+1} − p_{k}, by Proposition 7 (i), we get

log h(n) = log N_{k} = θ(p_{k}) < p_{k} = P^{+}(N_{k}) = P^{+}(h(n)).

If σ_{k+1} − p_{k} ⩽ n < σ_{k+1}, by Eq. (9) and Proposition 7 (ii), we have

log h(n) ⩽ log N_{k+1} = θ(p_{k+1}) < p_{k+1} ⩽ P^{+}(h(n))

which shows n_{0} ⩾ σ_{k_{0}−1}.

It remains to study the case σ_{k_{0}−1} ⩽ n < σ_{k_{0}−2} + p_{k_{0}}. By Proposition 7 (i), we get log h(n) = θ(p_{k_{0}−1}) < p_{k_{0}−1} = P^{+}(N_{k_{0}−1}) = P^{+}(h(n)).

Corollary 55. For n ⩽ 11 896 693 289 932 185 243 249, we have log h(n) < P^{+}(h(n)).

Proof. The value of p_{k_{0}} is still unknown. From Eq. (23), we know that p_{k_{0}} ⩾ p_{k_{1}} = 800000000047, the smallest prime exceeding 8·10^{11}. Therefore, we have p_{k_{1}−2} = 799999999889, σ_{p_{k_{1}−2}} = 11896693289132185243203 and

n_{0} ⩾ σ_{k_{1}−2} + p_{k_{1}} = 11 896 693 289 932 185 243 250.

Remark 56. There are 3 272 numbers ⩽ 10^{6} such that P^{+}(g(n)) > log g(n) (cf. [4, §10]).

References

[1] R. C. Baker, G. Harman, and J. Pintz, The difference between consecutive primes. II, Proc. London Math. Soc. 83 (2001), 532–562.

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

 [3] M. Deléglise, web pages, http://math.univ-lyon1.fr/~deleglis/Htables.html.

[4] M. Deléglise and J.-L. Nicolas, Le plus grand facteur premier de la fonction de Landau, Ramanujan J. 27 (2012), 109–145.

[5] Marc Deléglise and Jean-Louis Nicolas, Maximal product of primes whose sum is bounded, Proc. Steklov Inst. Math. 282 (Issue 1, Supplement) (2013), 73–102.

[6] Marc Deléglise, Jean-Louis Nicolas, and Paul Zimmermann, Landau’s function for one million billions, J. Théor. Nombres Bordeaux 20 (2008), 625–671.

[7] P. Dusart, Estimates of some functions over primes without R. H., preprint, 2010,

http://arxiv.org/abs/1002.0442v1.

[8] William John Ellison, Les Nombres Premiers, Hermann, Paris, 1975. En collaboration avec Michel Mendès France, Publications de l’Institut de Mathématique de l’Université de Nancago, No. IX, Actualités Scientifiques et Industrielles, No. 1366.

[9] Jon Grantham, The largest prime dividing the maximal order of an element of S_{n}, Math. Comp. 64 (1995), 407–410.

[10] A. E. Ingham, The Distribution of Prime Numbers, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1990.

[11] E. Landau, Über die Maximalordnung der Permutationen gegebenen Grades, Archiv. der Math. und Phys. 5 (1903), 92–103. Handbuch der Lehre von der Verteilung der Primzahlen, I, 2nd ed., Chelsea, 1953, pp. 222–229.

[12] J.-P. Massias, J.-L. Nicolas, and G. Robin, Évaluation asymptotique de l’ordre maximum d’un élément du groupe symétrique, Acta Arith. 50 (1988), 221–242.

[13] Jean-Pierre Massias, Majoration explicite de l’ordre maximum d’un élément du groupe symétrique, Ann. Fac. Sci. Toulouse Math. 6 (1984), 269–281.

[14] Jean-Pierre Massias, Jean-Louis Nicolas, and Guy Robin, Effective bounds for the maximal order of an element in the symmetric group, Math. Comp. 53 (188) (1989), 665–678.

[15] Thomas R. Nicely, New maximal prime gaps and first occurrences, Math. Comp. 68 (227) (1999), 1311–1315.

[16] J.-L. Nicolas, Ordre maximum d’un élément du groupe de permutations et highly composite numbers, Bull. Soc. Math. France 97 (1969), 129–191.

[17] J.-L. Nicolas, Ordre maximal d’un élément d’un groupe de permutations, C.R. Acad. Sci. Paris 270 (1970), 1473–1476.

[18] J.-L. Nicolas, On Landau’s function g(n). In Ronald L. Graham and Jaroslav Nešetřil, eds., The Mathematics of Paul Erdős I, Vol. 13 of Algorithms and Combinatorics, Springer-Verlag, 1997, pp. 207–220.

[19] Olivier Ramaré and Yannick Saouter, Short effective intervals containing primes, J. Number Theory 98 (2003), 10–33.

[20] J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64–94.

[21] Lowell Schoenfeld, Corrigendum: “Sharper bounds for the Chebyshev functions θ(x) and ψ(x). II”, Math. Comp. 30 (136) (1976), 900.

2010 Mathematics Subject Classification: Primary 11A25; Secondary 11N37, 11N05, 11-04. Keywords: distribution of primes, champion number, highly compostite number, Landau function.

(Concerned with sequences \underline{A000793} and \underline{A159685}.)

Received September 22 2014; revised version received January 15 2015. Published in Journal of Integer Sequences, January 25 2015.

Return to Journal of Integer Sequences home page.