ON THE NUMBER OF DIVISORS OF n!

Paul Erdős, S. W. Graham, Aleksandar Ivić and Carl Pomerance

For Heini Halberstam on his retirement

Abstract. Several results involving d(n!) are obtained, where d(m) denotes the number of positive divisors of m. These include estimates for d(n!)/d((n − 1)!), d(n!) − d((n − 1)!), as well as the least number K with d((n + K)!)/d(n!) ≥ 2.

§1 Introduction Let as usual d(m) denote the number of positive divisors of m. We are interested here in problems involving d(n!). There seem to exist only a few results in the literature on this subject, one of which is the result of G. Tenenbaum [13] that

∑_{1≤j≤d(n!)} (\frac{d_{j+1}}{d_{j}} − 1)^{α} ≪_{α} 1

for any fixed α > 1, where 1 = d_{1} < d_{2} < ⋯ < d_{m} = n! are the divisors of n! (and so m = d(n!)).

We note that the divisor function can at least occasionally be large, since by a classical result of Wigert, one has

(1)  log d(m) ≤ \frac{log 2 log m}{log log m} + O (\frac{log m}{(log log m)^{2}} ) ,

with equality holding if m = p_{1}p_{2} ⋯ p_{r}, where r → ∞, and p_{r} is the r-th prime number. Our first goal is to obtain an asymptotic formula for log d(n!), showing that it is ∼ c_{0} log(n!)/(log log(n!))^{2}, where c_{0} is an explicit constant approximately equal to 1.25775.

We next are concerned with the function d(n!)/d((n − 1)!). We show that this is well approximated by 1 + P (n)/n, where P (n) is the largest prime factor of n. From this we are able to find the limit points of the sequence d(n!)/d((n − 1)!).

Let K = K(n) denote the least number with d((n + K)!)/d(n!) ≥ 2. We are able to show that infinitely often K(n) is abnormally large, namely that K(n)/ log n is unbounded. The method of proof involves the Erdős-Rankin method for showing that there are sometimes abnormally large gaps between the primes. On the other hand we show that K(n) cannot be too large: it is < n^{4/9} for all sufficiently large

Typeset by AMS-TEX

Research of the second author was partially supported by the National Security Agency; research of the third author financed by the Mathematical Insititute of Belgrade; research of the fourth author partially supported by the National Science Foundation.

2 PAUL ERDŐS, S. W. GRAHAM, ALEKSANDAR IVIĆ AND CARL POMERANCE

numbers n. The proof comes from the circle of ideas, begun by Ramachandra, for showing that short intervals contain integers with large prime factors.

Finally we consider the function D(n) = d(n!) − d((n − 1)!). In particular we consider “champs” for this sequence, namely numbers n with D(n) > D(m) for all numbers m smaller than n. We show that primes and the doubles of primes are such champs, we show on the prime k-tuples conjecture that there are infinitely many other champs, and we show on the Riemann Hypothesis that the set of champs has asymptotic density zero.

§2 An approximate formula for d(n!) Our first aim is to express d(n!) in terms of elementary functions. If [x] denotes the integer part of x, then

n! = ∏_{p≤n} p^{w_{p}(n)}, where w_{p}(n) := [\frac{n}{p}] + [\frac{n}{p^{2}} ] + [\frac{n}{p^{3}} ] + ⋯,

hence

log d(n!) = ∑_{p≤n} log(w_{p}(n) + 1)

= ∑_{p≤n^{3/4}} log(w_{p}(n) + 1) + ∑_{n^{3/4}<p≤n} log(w_{p}(n) + 1) = ∑_{1} + ∑_{2}, (2)

say. Since w_{p}(n) < n ∑_{j} p^{−j} = n/(p − 1), we have

∑_{1} < ∑_{p≤n^{3/4}} log (1 + \frac{n}{p − 1}) ≪ log n ∑_{p≤n^{3/4}} 1 ≪ n^{3/4}.

Now note that in Σ_{2} we have w_{p}(n) = [n/p], since [n/p^{k}] = 0 for k ≥ 2. Therefore by the prime number theorem we have

∑_{2} = ∫_{n^{3/4}}^{n} log ([\frac{n}{x}] + 1) dπ(x)

= ∫_{n^{3/4}}^{n} \frac{log ([\frac{n}{x}] + 1)}{log x}dx + ∫_{n^{3/4}}^{n} \frac{log ([\frac{n}{x}] + 1)}{log x}dR(x) = I_{1} + I_{2},

say, where (see e.g. [2] or [7]) R(x) = O(xe^{−\sqrt{log x}}). Since log ([\frac{n}{x}] + 1) is a nonincreasing function of x in [1, n] we obtain, on integrating by parts,

I_{2} ≪ ne^{(−1/2)\sqrt{log n}}.

The main contribution to log d(n!) comes from

I_{1} = ∫_{n^{3/4}}^{n} \frac{log ([\frac{n}{x}] + 1)}{log x}dx = n ∫_{1}^{n^{1/4}} \frac{log([t] + 1)}{t^{2} log (\frac{n}{t})}dt

= \frac{n}{log n} ∑_{k=0}^{K} \frac{1}{log^{k} n} ∫_{1}^{n^{1/4}} \frac{log([t] + 1)}{t^{2}} log^{k} t dt + O (\frac{n}{log^{K+2} n})

= \frac{n}{log n} ∑_{k=0}^{K} \frac{c_{k}}{log^{k} n} + O (\frac{n}{log^{K+2} n})

for any fixed integer K ≥ 0, where

(3)  c_{k} = ∫_{1}^{∞} \frac{log([t] + 1)}{t^{2}} log^{k} t dt.

In particular,

c_{0} = ∫_{1}^{∞} log([t] + 1)\frac{dt}{t^{2}} = ∑_{k=2}^{∞} ∫_{k−1}^{k} log k \frac{dt}{t^{2}} = ∑_{k=2}^{∞} \frac{log k}{k(k − 1)} ≈ 1.25775.

Thus we have proved

Theorem 1. For any fixed integer K ≥ 0 and c_{k} given by (3) we have

d(n!) = exp \{\frac{n}{log n} ∑_{k=0}^{K} \frac{c_{k}}{log^{k} n} + O (\frac{n}{log^{K+2} n})\} .

Let m = n!. Then by Stirling’s formula one has log m = n log n − n + O(log n), which gives

log n = log log m + O(log log log m), n = \frac{log m}{log log m} (1 + O (\frac{log log log m}{log log m})) .

Therefore we obtain from Theorem 1 that

log d(m) = \frac{c_{0} log m}{(log log m)^{2}} (1 + O (\frac{log log log m}{log log m})) ,

which may be compared with (1).

§3 The function d(n!)/d((n − 1)!) We now note another consequence of Theorem 1. It implies that d(n!)/d((n−1)!) → 1 as n → ∞ on a set of asymptotic density 1. We can show more. We begin with the following lemma.

Lemma 1. Let S(n) denote the sum of the prime factors of n where they are summed with multiplicity. Then for every integer n ≥ 1,

1 + \frac{S(n)}{2n} ≤ \frac{d(n!)}{d((n − 1)!)} ≤ 1 + \frac{2S(n)}{n}.

Proof. For the upper bound, we have

\frac{d(n!)}{d((n − 1)!)} = ∏_{p^{a}||n} \frac{w_{p}(n − 1) + 1 + a}{w_{p}(n − 1) + 1}

= ∏_{p^{a}||n} (1 + \frac{a}{w_{p}(n − 1) + 1}) ≤ exp ( ∑_{p^{a}||n} \frac{a}{w_{p}(n − 1) + 1}) . (4)

We have for any prime p dividing n that [(n−1)/p] = n/p−1. Thus, w_{p}(n−1)+1 ≥ [(n − 1)/p] + 1 = n/p, and so

(5)  \frac{d(n!)}{d((n − 1)!)} ≤ exp ( ∑_{p^{a}||n} \frac{a}{n/p}) = exp(S(n)/n).

But clearly S(n) ≤ n for every natural number n, so that exp(S(n)/n) ≤ 1 + 2S(n)/n, which completes our proof of the upper bound in the lemma.

For the lower bound, we have

\frac{d(n!)}{d((n − 1)!)} = ∏_{p^{a}||n} (1 + \frac{a}{w_{p}(n − 1) + 1}) ≥ 1 + ∑_{p^{a}||n} \frac{a}{w_{p}(n − 1) + 1}.

But w_{p}(n − 1) + 1 < 1 + (n − 1) ∑_{j} p^{−j} = 1 + (n − 1)/(p − 1) ≤ 2n/p (the last inequality easily proved for all integers p, n with 2 ≤ p ≤ n). Thus we have the lower bound in the lemma.

We are now ready to prove the following theorem.

Theorem 2. Let P (n) denote the largest prime factor of n. Then

\frac{d(n!)}{d((n − 1)!)} = 1 + \frac{P (n)}{n} + O (\frac{1}{n^{1/2}} ) .

Proof. Let Ω(n) denote the number of prime factors of n, counted with multiplicity. Then S(n) ≤ P (n)Ω(n) ≤ P (n) log_{2} n. First suppose that p = P (n) ≤ n^{1/2} and q = P (n/p) ≤ n^{1/3}. Then S(n) = p + S(n/p) ≤ p + q log_{2} n ≪ n^{1/2}. Next suppose that p ≤ n^{1/2} and n^{1/3} < q ≤ p. Then S(n) = p + q + S(n/pq) ≤ p + q + n/pq ≤ 3p ≪ n^{1/2}. Thus, if P (n) ≤ n^{1/2}, then S(n) ≪ n^{1/2}, and so the theorem follows from the lemma in this case.

Now suppose that p = P (n) > n^{1/2}. Writing n = mp, we have w_{p}(n) = [n/p] = m, w_{p}(n − 1) = m − 1, so that from (4),

\frac{d(n!)}{d((n − 1)!)} = \frac{m + 1}{m} ∏_{q^{b}||m} (1 + \frac{b}{w_{q}(n − 1) + 1}) .

By the calculations in the proof of the lemma we have

1 ≤ ∏_{q^{b}||m} (1 + \frac{b}{w_{q}(n − 1) + 1}) ≤ ∏_{q^{b}||m} (1 + \frac{b}{n/q} ) ≤ exp ( ∑_{q^{b}||m} \frac{bq}{n} )

= exp (\frac{S(m)}{n}) ≤ exp (\frac{m}{n}) ≤ 1 + \frac{2m}{n} ≤ 1 + \frac{2}{n^{1/2}} .

This completes the proof of the theorem.

Corollary 1. The set of limit points of the sequence d(n!)/d((n − 1)!) consists of the number 1 and the numbers 1 + 1/m, where m is a natural number.

From Theorem 2 it is straightforward to get asymptotic estimates, or even asymptotic expansions, for the average order of d(n!)/d((n−1)!), or any fixed positive or negative power of this fraction. For example, such results follow from the circle of papers that includes [3].

For a positive integer k, let F_{k}(n) = d((n + k)!)/d(n!). Then

F_{k}(n) = F_{1}(n + 1)F_{1}(n + 2) ⋯ F_{1}(n + k).

It follows from Theorem 2 that for fixed k, the average order of F_{k}(n) is 1. Indeed, from Theorem 2,

(6)  1 ≤ F_{k}(n) ≤ exp (\frac{1}{n} ∑_{i=1}^{k} P (n + i) + O (\frac{k}{n^{1/2}} )) .

Let u(m) denote the number of positive integers n < m with n ≤ x and n + k ≥ m. Then u(m) ≤ k. It follows that

∑_{n≤x} ∑_{i=1}^{k} P (n + i) = ∑_{m} u(m)P (m)

≤ k ∑_{m≤x+k} P (m) ≪ kx^{2}/ log x = o(x^{2}).

Thus, on average, ∑_{i=1}^{k} P (n + i) = o(n), and for all n, we have this sum ≪ kn. Hence our assertion follows from (6). This argument can be used to show that if k = k(n) varies with n in such a way that k(n) = o(log^{2} n), then the normal order of F_{k}(n) is 1. That is, F_{k}(n) ∼ 1 as n tends to ∞ through a set of integers of asymptotic density 1. It is also possible to show via (6) that if c > 0 is fixed and k = k(n) ∼ c log n, then the normal order of F_{k}(n) is g(c), where g(c) > 1 is a number that depends on c. These results may well be true too for the average order, but the proof is likely to be harder.

§4 The least K with d((n + K)!)/d(n!) ≥ 2 Let K = K(n) denote the least positive integer with F_{K}(n) ≥ 2. That is, d((n + K)!) ≥ 2d(n!). If n + 1 is prime, then K(n) = 1. From Theorem 1 it seems that one should compare K(n) with log n. In fact, this theorem immendiately implies that the average order of K(n) is ≍ log n. One might ask about the maximal order of K(n). The following two results show that K(n) < n^{4/9} for all large numbers n and that K(n)/ log n is unbounded.

Theorem 3. Recall that S(n) denotes the sum of the prime factors of n, with multiplicity. Let f(n) denote the least number such that

∑_{i=1}^{f(n)} S(n + i) > n.

For each number ε > 0 there are infinitely many integers n for which

f(n) ≥ (1/4 − ε) log n log log n log log log log n/(log log log n)^{3}.

We first show the connection of Theorem 3 to the maximal order of K(n).

Corollary 2. For infinitely many natural numbers n we have

K(n) > log n\frac{log log n log log log log n}{9(log log log n)^{3}}.

In particular, K(n)/ log n is unbounded.

Proof of the Corollary. From the theorem, there are infinitely many pairs n, K with K > (1/9) log n log log n log log log log n/(log log log n)^{3} and with ∑_{i=1}^{K} S(n + i) ≤ \frac{1}{2}n. It follows from (5) that

\frac{d((n + K)!)}{d(n!)} < exp (∑_{i=1}^{K} \frac{S(n + i)}{n + i}) < exp (\frac{1}{n} ∑_{i=1}^{K} S(n + i)) ≤ exp (\frac{1}{2}) < 2.

Thus, K(n) > K and the corollary is proved.

Proof of Theorem 3. Let u denote a large number and let M = M(u) denote the product of the primes in the interval [log^{2} u, u]. Let ε > 0 be arbitrary and fixed. By the Erdős–Rankin argument, for all sufficiently large numbers u, depending on the choice of ε, there is a residue class A mod M, such that (A + i, M) > 1 for each integer i with

1 ≤ i ≤ L := (1/2 − ε/4)u log u log log log u/(log log u)^{3}.

Indeed, it suffices to show that for each prime p|M there is a residue class a_{p} mod p, such that for each integer i with 1 ≤ i ≤ L, there is a prime p|M with i ≡ a_{p} mod p. The numbers a_{p} can be chosen as follows: for y := u^{(1−ε/4) log log log u/ log log u} < p ≤ u/ log log u, we choose a_{p} = 0. The number of integers i in [1, L] that are not congruent to 0 modulo any of these primes p is ∼ L log log u/ log u (using de Bruijn [1]). Next, for the primes p with log^{2} u ≤ p ≤ y, we choose a_{p} sequentially in such a way that for each p we have as many as possible remaining integers in [1, L] congruent to a_{p} mod p. The number of remaining integers i in [1, L] that are still not covered by any of the residue classes a_{p} mod p for log^{2} u ≤ p ≤ u/ log log u is, by Mertens’ theorem, less than or asymptotically equal to

\frac{2 log log u}{log y} · \frac{L log log u}{log u} = \frac{2}{1 − ε/4} · \frac{L(log log u)^{3}}{(log u)^{2} log log log u} = \frac{1 − ε/2}{1 − ε/4} · \frac{u}{log u}.

It follows from the prime number theorem that for u sufficiently large, there are fewer residual values of i left unsieved in [1, L] than there are primes p in the remaining interval u/ log log u < p ≤ u, so even if we use these primes to remove just one value of i each, we will succeed in covering the entire interval [1, L] as claimed.

For any integer l ≤ u^{3}, let N(l) denote the number of pairs i, j of integers with 1 ≤ i ≤ L, M/2 ≤ j ≤ M, and (jM + A + i)/l is prime.

Lemma 2. We have uniformly for l ≤ u^{3},

N(l) ≪ \frac{LM log u}{φ(l)u log log u} + \frac{(l, M)M log u}{φ(l)u log log u}.

Proof. Let k = l/(l, M). First consider the case (l, M) ≤ L. For l to divide jM + A + i, we must have i ≡ −A mod (l, M). There are ≪ L/(l, M) values of i ∈ [1, L] for which this holds. Fixing one of these, for l to divide jM + A + i, we must have j in a fixed residue class mod k. So the number of such j values in [M/2, M] for which jM + A + i is a prime, is, by the sieve,

≪ \frac{M/k}{log(M/k)} · \frac{Mk}{φ(Mk)} ≪ \frac{M}{φ(k) log M} · \frac{M}{φ(M)} ≪ \frac{M}{φ(k)u} · \frac{M}{φ(M)},

where we have used log(M/k) ∼ log M ∼ u and φ(Mk) ≥ φ(M)φ(k). Now M/φ(M) ≍ log u/ log log u, and multiplying by the number of possible i values, we get

N(l) ≪ \frac{L}{(l, M)} · \frac{M log u}{φ(k)u log log u} ≤ \frac{LM log u}{φ(l)u log log u}.

Now consider the case (l, M) > L. Then there is at most one value of i ∈ [1, L] for which l can divide jM + A + i. Thus again using the sieve, we have

N(l) ≪ \frac{M/k}{log(M/k)} · \frac{Mk}{φ(Mk)} ≪ \frac{M log u}{φ(k)u log log u} ≤ \frac{(l, M)M log u}{φ(l)u log log u}.

This completes the proof of the lemma.

We now return to the proof of the theorem. We are going to show that

(7)  ∑_{M/2≤j≤M} ∑_{1≤i≤L} S(jM + A + i) = o(M^{3})

as u → ∞. Note that for j ∈ [M/2, M] and i ∈ [1, L], we have jM + A + i ≍ M^{2}. If we show (7) it will follow that for u large there is some number j ∈ [M/2, M] with ∑_{1≤i≤L} S(jM + A + i) < jM + A, so that f(jM + A) > L, and the theorem follows.

Let S(n) = S_{1}(n) + S_{2}(n), where S_{1}(n) is the sum of the prime factors of n that are bigger than n/u^{3}, while S_{2}(n) is the sum of the smaller prime factors of n. Note that S_{2}(n) ≪ (n/u^{3}) log n. Thus

∑_{M/2≤j≤M} ∑_{1≤i≤L} S_{2}(jM + A + i) ≪ ∑_{M/2≤j≤M} ∑_{1≤i≤L} \frac{M^{2}}{u^{3}} log(M^{2}) ≪ \frac{LM^{3}}{u^{2}} = o(M^{3}),

as u → ∞. Thus it suffices to show

(8)  ∑_{M/2≤j≤M} ∑_{1≤i≤L} S_{1}(jM + A + i) = o(M^{3})

as u → ∞. If S_{1}(jM + A + i) > 0, then jM + A + i = P l, where P is prime and l < u^{3}. By the choice of A, we have (l, M) > 1, so that l ≥ log^{2} u. Thus, by the lemma, we have

∑_{M/2≤j≤M} ∑_{1≤i≤L} S_{1}(jM + A + i)

= ∑_{log^{2} u≤l<u^{3}} ∑_{M/2<j<M} ∑_{{1≤i≤L \atop (jM+A+i)/l is prime}} \frac{jM + A + i}{l}

≪ ∑_{log^{2} u≤l<u^{3}} ∑_{M/2<j<M} ∑_{{1≤i≤L \atop (jM+A+i)/l is prime}} M^{2}/l = ∑_{log^{2} u≤l<u^{3}} N(l)M^{2}/l

≪ ∑_{log^{2} u≤l} (\frac{LM^{3} log u}{lφ(l)u log log u} + \frac{(l, M)M^{3} log u}{lφ(l)u log log u})

≪ \frac{LM^{3} log u}{u log^{2} u log log u} + ∑_{d|M} ∑_{v=1}^{∞} \frac{dM^{3} log u}{dvφ(dv)u log log u}

≪ \frac{LM^{3}}{u log u log log u} + ∑_{d|M} \frac{M^{3} log u}{φ(d)u log log u}

≪ \frac{LM^{3}}{u log u log log u} + \frac{M^{3} log^{2} u}{u(log log u)^{2}} = o(M^{3}),

as u → ∞. This proves (8) and the theorem.

Theorem 3 shows that sometimes f(n), and hence K(n), can be abnormally large. We now show that they cannot be too large.

Theorem 4. Let f(n) be as in Theorem 3. If n is sufficiently large, then f(n) < n^{4/9}.

The theorem is an immediate consequence of the following lemma.

Lemma 3. Let x be a sufficiently large positive real number, let c = 4/9, and δ = 1/10000. Then the number of primes p such that p divides some m in the interval (x, x + x^{c}] and p > x^{1−c+δ} is ≫ x^{c}.

To see how the Theorem follows from the Lemma, note that if we take g(n) = n^{4/9}, then

∑_{i=1}^{g(n)} S(n + i) ≥ n^{5/9+δ}R,

where R is the number of primes p > x^{5/9+δ} that divide some integer in the interval (n, n + f(n)]. By the Lemma, R ≫ n^{4/9}, so

∑_{i=1}^{g(n)} S(n + i) > n

for n sufficiently large. Therefore, f(n) ≤ g(n).

Lemma 3 also has consequences for our function K(n) defined before Theorem 3. We have the following result.

Corollary 3. For all sufficiently large numbers n, we have K(n) < n^{4/9}.

Indeed, from Lemma 1 we have

\frac{d((n + [n^{4/9}])!)}{d(n!)} > ∏_{1≤i≤n^{4/9}} (1 + \frac{S(n + i)}{2(n + i)}) > 1 + \frac{1}{2} ∑_{1≤i≤n^{4/9}} \frac{S(n + i)}{n + i}

> 1 + \frac{1}{3n} ∑_{1≤i≤n^{4/9}} S(n + i) ≥ 1 + \frac{1}{3n}n^{5/9+δ}[n^{4/9}] > 2,

for all sufficiently large numbers n. Thus, we have the corollary.

Proof of Lemma 3. For most of the argument, we shall assume only that c is a real number with c < 1/2; only at the last step will we specialize to c = 4/9. Our proof is an adaptation of K. Ramachandra’s proof [10] that the greatest prime factor of the product of the integers in the interval (x, x + x^{1/2}] exceeds x^{15/26}, for x sufficiently large. Ramachandra’s exponent has been improved by a series of authors; see the references in [9]. The current best exponent is 0.723, and it is due independently to Hong-Quan Liu [9] and Jia Chaohua [8]. It is very likely that our exponent of 4/9 can be improved by using ideas from these papers, but, for reasons of brevity, we do not consider these possible improvements here.

In the initial stage, we follow an argument due to Chebyshev (cf. [6], Chapter 2). We begin by observing that

x^{c} log x + O(x^{c}) = ∑_{x<m≤x+x^{c}} log m

= ∑_{x<m≤x+x^{c}} ∑_{d|m} Λ(d) = ∑_{d} Λ(d)N(d) (9)

where

(10)  N(d) = ∑_{{d|m \atop x<m≤x+x^{c}}} 1,

and Λ is von Mangoldt’s function; i.e., Λ(d) = log p if d = p^{a} for some prime p and 0 otherwise. We decompose the last sum in (9) as

∑_{d} Λ(d)N(d) = ∑_{d≤x^{c}} Λ(d)N(d) + ∑_{p≤x^{c}<p^{a}} N(p^{a}) log p + ∑_{p>x^{c}} ∑_{a≥1} N(p^{a}) log p

= Σ_{1} + Σ_{2} + Σ_{3}, (11)

say. From the trivial estimate N(d) = x^{c}/d + O(1), we get

Σ_{1} = x^{c} ∑_{d≤x^{c}} Λ(d)/d + O(x^{c}) = cx^{c} log x + O(x^{c}).

If p^{a} > x^{c}, then N(p^{a}) ≤ 1, and N(p^{a}) = 0 if p^{a} > 2x > x + x^{c}. Therefore

Σ_{2} ≤ ∑_{p≤x^{c}} ∑_{a≤log(2x)/ log p} 1 ≪ ∑_{p≤x^{c}} \frac{log x}{log p} ≪ x^{c}.

Combining (9) and (11) together with the above estimates for Σ_{1} and Σ_{2} gives

(12)  Σ_{3} = (1 − c)x^{c} log x + O(x^{c}).

Since we wish to get prime factors p with p > x^{1−c+δ}, we write

(13) Σ_{3} = ∑_{x^{c}<p≤x^{1−c+δ}} ∑_{a≥1} N(p^{a}) log p + ∑_{x^{1−c+δ}<p} N(p) log p = Σ_{4} + Σ_{5},

say. Here, δ is a small positive constant that will be chosen later. In our notation for Σ_{5}, we have used the fact that if c < 1/2 then (1 − c) > 1/2; consequently, if p > x^{1−c} and N(p^{a}) ≠ 0, then we must have a = 1.

Our objective is to show that Σ_{5} ≫ x^{c} log x for some value of c. We do this by using Selberg’s upper bound sieve to give an upper bound for Σ_{4}. We will split the range of summation in this sum into subintervals of the form v < p^{a} ≤ ev; accordingly, it is convenient to define

T (v) = ∑_{{x^{c}<p \atop v<p^{a}≤ev}} N(p^{a}).

Now we let z = z(v, x) be a parameter to be chosen later; for now, we assume only that z ≤ x^{c}. Suppose that we have real numbers λ_{d} with λ_{1} = 1 and λ_{d} = 0 if d > z or if d is not squarefree. Then

T (v) ≤ ∑_{v<m≤ev} N(m) (∑_{d|m} λ_{d})^{2} .

Upon expanding the square, we obtain

(14)  T (v) ≤ ∑_{k,l} λ_{k}λ_{l} ∑_{v<m[k,l]≤ev} N(m[k, l]).

We expect that the inner sum is about x^{c}/[k, l]. Accordingly, we wish to choose the λ_{k}’s to minimize the bilinear form ∑_{k,l} λ_{k}λ_{l}[k, l]^{−1} subject to the restraints λ_{1} = 1 and λ_{k} = 0 if k > z. ¿From the theory of the Selberg sieve (cf. [6], pp. 8ff.), it is known that this conditional minimum is ≤ (log z)^{−1}. Using this choice of λ_{k} and writing ρ_{d} = ∑_{[k,l]=d} λ_{k}λ_{l}, we see that (14) may be re-written as

(15)  T (v) ≤ ∑_{d<z^{2}} ρ_{d} ∑_{v/d<m≤ev/d} N(md).

For future reference, we note also that the minimizing choice of λ_{k} satisfies |λ_{k}| ≤ μ^{2}(k) ([6], equation 18); therefore

(16)  ρ_{d} ≤ μ^{2}(d)τ_{3}(d),

where τ_{3}(d) denotes the number of ways of writing d as a product of three ordered factors.

Now let ψ(w) = w − [w] − 1/2. The inner sum in (15) may be written as

∑_{v/d<m≤ev/d} N(md) = ∑_{v/d<m≤ev/d} (\frac{x^{c}}{md} − ψ (\frac{x + x^{c}}{md} ) + ψ (\frac{x}{md}))

= \frac{x^{c}}{d} + O (\frac{x^{c}}{v} ) + ∑_{v/d<m≤ev/d} (ψ (\frac{x}{md}) − ψ (\frac{x + x^{c}}{md} )) .

This together with the bound ∑_{k,l} λ_{k}λ_{l}[k, l]^{−1} ≤ (log z)^{−1} and (16) gives

(17)  T (v) ≤ \frac{x^{c}}{log z} + O (x^{c}v^{−1}z^{2} log^{2} z) + R_{1} − R_{2},

where

R_{1} = ∑_{d<z^{2}} ρ_{d} ∑_{v/d<m≤ev/d} ψ (\frac{x}{md}) ,

and R_{2} is the corresponding sum with x replaced by x + x^{c}.

We use the theory of exponent pairs to estimate R_{1} and R_{2}. Assume that (k, l) is an exponent pair with k ≠ 0 and l ≠ 1. (In our application, we will use only the exponent pairs B(0, 1) = (1/2, 1/2), AB(0, 1) = (1/6, 2/3) and A^{2}B(0, 1) = (1/14, 11/14).) ¿From Lemma 4.3 of [5], we see that

R_{i} ≪ ∑_{d<z^{2}} τ_{3}(d) (x^{k/(k+1)}d^{−l/(k+1)}v^{(l−k)/(k+1)} + v^{2}x^{−1}d^{−1})
≪ x^{k/(k+1)}v^{(l−k)/(k+1)}z^{2(1+k−l)/(k+1)} log^{2} z + v^{2}x^{−1} log^{3} z

for i = 1 and 2. Now we choose z to make the first term in the above estimate < x^{c}/(log x)^{2}; in other words, we choose z to satisfy

z^{2+2k−2l} = v^{k−l}x^{c(k+1)−k}(log x)^{−4(k+1)}.

With this choice of z, the above estimates give

T (v) ≤\frac{θ(u, k, l)x^{c}}{log x} + O (\frac{x^{c} log log x}{log^{2} x}) + O (\frac{v^{2} log^{3} x}{x})

+ O (\frac{x^{(2c+2ck−cl−k)/(1+k−l)}}{v^{1/(1+k−l)}(log x)^{(2+2k+3l)/(1+k−l)}} ) , (18)

where u = log v/ log x and

θ(u, k, l) = \frac{2(1 + k − l)}{c + ck − k + ku − lu}.

Now if v ≤ x^{(1+c)/2}(log x)^{−5/2}, then the second error term in (18) is ≪ x^{c}/ log^{2} x. We also note that if v ≥ x^{c}, then the third error term is

≪ x^{c}x^{(c−1)k/(1+k−l)}(log x)^{−(2+2k+3l)/(1+k−l)} ≪ x^{c}(log x)^{−2}.

Therefore, if

x^{c} ≤ v ≤ x^{(1+c)/2}(log x)^{−5/2},

then our bound for T (v) may be simplified to

(19)  T (v) ≤ \frac{θ(u, k, l)x^{c}}{log x} · (1 + O(ϵ(x))) ,

where, for brevity, we have written ϵ(x) for (log log x)/ log x.

Now we are ready to bound Σ_{4}. Let

V = {e^{j}x^{c} : 0 ≤ j and e^{j}x^{c} ≤ x^{1−c+δ}},

so that

Σ_{4} ≤ ∑_{v∈V} log(ev)T (v).

We now set

α = \frac{1 + 17c}{18} and β = \frac{1 + 5c}{6}.

For x^{c} ≤ v ≤ x^{α}, we will use the exponent pair (1/14, 11/14). For x^{α} < v ≤ x^{β}, we use (1/6, 2/3), and for x^{β} < v ≤ x^{1−c+δ}, we use (1/2, 1/2). We assume that 1 − c + δ < (1 + c)/2, so that for x sufficiently large, x^{1−c+δ} ≤ x^{(1+c)/2}(log x)^{−5/2} and (19) holds. We find that

Σ_{4} ≤ I(c)x^{c}(log x)(1 + O(ϵ(x))),

where

I(c) = ∫_{c}^{α} uθ(u, 1/14, 11/14)du+∫_{α}^{β} uθ(u, 1/6, 2/3)du+∫_{β}^{1−c+δ} uθ(u, 1/2, 1/2)du.

Henceforth, we specialize to the choice of c = 4/9 and δ = .0001. Now a lengthy but straightforward computation shows that 4/9+I(4/9) < 0.9998 . . .. We conclude from (12) and (13) that if x is sufficiently large, then

∑_{x^{5/9+δ}<p} N(p) log p > 0.0002x^{4/9} log x.

This completes the proof of Lemma 3.

§5 The differences d(n!) − d((n − 1)!) We now turn our attention to the function

D(n) := d(n!) − d((n − 1)!).

Thus, D(n) is the number of divisors of n! that are not divisors of (n − 1)!. It is easy to assess the average order of D(n), since the sum of D(n) for n ≤ x is exactly d([x]!). We may also find the average order of log D(n). Indeed, from Theorem 2, we have

D(n) = d((n − 1)!) (\frac{d(n!)}{d((n − 1)!)} − 1) = d((n − 1)!) (\frac{P (n)}{n} + O (\frac{1}{n^{1/2}} )) .

Thus, log D(n) = log d((n − 1)!) + O(log n), and so the average order of log D(n) is essentially the same as the average order of log d(n!). In fact, we have immediately from Theorem 1 that there are numbers d_{0}, d_{1}, … such that

∑_{2≤n≤x} log D(n) = \frac{x^{2}}{log x} ∑_{k=0}^{K} \frac{d_{k}}{log^{k} x} + O (\frac{x^{2}}{log^{K+2} x})

for any fixed positive integer K. Note that the coefficient of the main term, d_{0}, is c_{0}/2 ≈ 0.6289.

We shall call a natural number n a champ if D(n) > D(m) for all natural numbers m < n. Thus a champ is entirely analogous to the concept, introduced by Ramanujan [11], of a highly composite number. This is an integer n with d(n) > d(m) for all natural numbers m smaller than n.

We have the following elementary result.

Theorem 5. For each prime p, both p and 2p are champs.

Proof. We have

D(p) = d(p!) − d((p − 1)!) = d((p − 1)!) ≥ d(m!) > D(m)

for every m < p. Thus, p is a champ.

Note that for every positive integer m we have D(m) ≤ d(m!)/2. Indeed, we note that there are two kinds of divisors of m!: those that divide (m−1)! and those that don’t. There are at least as many divisors of the first kind as of the second kind, since if d is a divisor of the second kind, then d/m is a divisor of the first kind. Thus, D(m), the number of divisors of the second kind, is at most d(m!)/2. Now say p is an odd prime. We have

D(2p) = d((2p)!)−d((2p−1)!) > \frac{3}{2}d((2p−1)!)−d((2p−1)!) = \frac{1}{2}d((2p−1)!) ≥ D(m),

for every positive integer m < 2p. Thus, 2p is a champ. To conclude the proof of the theorem, it remains to note that 4 is a champ.

Theorem 5 suggest two natural questions. The first is if there are any, or infinitely many, champs n which are not of the form p or 2p. The second is if, in some sense, most of the champs are of the form p or 2p, or at least to decide if the set of champs has asymptotic density 0.

On the first question, we first note that yes indeed, there are champs other than the prescribed forms of Theorem 5. The least such champ is 8. Marc Deleglise computed all of the champs up to 500 and found that there are 30 of them that are not of the form p or 2p. These exceptional champs are all of the form mp where p is a prime ≥ P (m) and m is 3, 4, 5, 6 or 7. In particular with m = 3 we have the champs 3p for p = 3, 5, 7, 11, 13, 17, 19, 29, 31, 41, 53, 73, 79, 83, 97, 101, 109, 139 and 149. For m = 4 we have the champs 4p for p = 2, 7, 13, 31, 47 and 107. For m = 5 we have the champs 5p for p = 5 and 13. For m = 6 we have the champs 6p for p = 11 and 13. Finally we have the champ 7p for p = 11. It is not trivial to compute these numbers, since the values of D(n) get large quickly. For example, when n is the largest champ below 500, namely the prime 499, the value D(499) has 61 decimal digits. We warmly thank Dr. Deleglise for permitting us to include this summary of his interesting calculations.

It is reasonable to conjecture that there are infinitely many champs not of the form p, 2p. In fact, this conjecture follows from the prime k-tuples conjecture. For example, it is relatively easy to show that if q, r are primes with 2q + 1 = 3r, then 3r is a champ. And of course, the prime k-tuples conjecture implies that there are infinitely many such pairs of primes q, r. (In fact, whenever q and r are primes with 2q < 3r and such that there are no primes in the interval [2q, 3r], then 3r is a champ. It may be not hopeless to show unconditionally that such pairs of primes q, r occur infinitely often.) Similar arguments can show that for each fixed positive integer m, there are infinitely many champs that are m times a prime. In fact it may be that for each m there is a positive density of primes p with mp a champ.

We also conjecture that the set of champs has asymptotic density zero. It is very annoying that we cannot seem to prove this. We can at least show the following conditional result.

Theorem 6. Assuming the Riemann Hypothesis, the set of champs has asymptotic density zero.

Proof. We first show the following unconditional result: If P (n) ≤ n/ log^{3} n and there is a prime in the interval (n − \frac{1}{3} log^{3} n, n], then n is not a champ. Indeed, suppose n is a champ and P (n) ≤ n/ log^{3} n. Let m = [n − \frac{1}{3} log^{3} n]. Since n is a champ,

d((n − 1)!) = d(m!) + D(m + 1) + D(m + 2) + ⋯ + D(n − 1)

< d(m!) + (n − 1 − m)D(n) ≤ d(m!) + \frac{1}{3}D(n) log^{3} n.

By Theorem 2, d(n!) ≤ (1 + log^{−3} n + O(n^{−1/2}))d((n − 1)!), so that D(n) ≤ (log^{−3} n + O(n^{−1/2}))d((n − 1)!). It follows that if n is sufficiently large, D(n) ≤ \frac{3}{2}(log^{−3} n)d((n − 1)!), and so

d((n − 1)!) < d(m!) + \frac{1}{3} · \frac{3}{2}d((n − 1)!),

that is, d((n − 1)!) < 2d(m!). Since d(p!) = 2d((p − 1)!) for a prime p, it follows that there are no primes in the interval (m, n]. This proves our assertion.

Thus, the set of non-champs contains the intersection of the set of (sufficiently large) n with P (n) ≤ n/ log^{3} n and the set of n for which there is a prime in the interval (n − \frac{1}{3} log^{3} n, n]. The number of n up to x not in the first set is O(x log log x/ log x), unconditionally, so that the first set has asymptotic density 1.

It follows from a theorem of Selberg [12] that if the Riemann Hypothesis holds, then the second set also has asymptotic density 1. This concludes the proof of the theorem.

From a conjecture of H. Cramér we have that for n sufficiently large, the interval (n − \frac{1}{3} log^{3} n, n] always contains a prime. If this holds, then the above argument gives that the number of champs up to x is ≪ x log log x/ log x. On the other hand, clearly the number of champs up to x is ≫ x/ log x. We are unsure what function to suggest for the true order of magnitude for the counting function of the champs.

We close finally with the following conjecture. Show that the asymptotic density of the set of integers n with D(n + 1) > D(n) is equal to 1/2. We can show that this conjecture is equivalent to the conjecture that the asymptotic density of the set of integers n with P (n + 1) > P (n) is 1/2. It follows by the method of [4] that the set of integers n with D(n) > D(n + 1) has positive lower density and an upper density that is less than 1. In particular, the upper density of the set of champs is < 1.

References

1. N. G. de Bruijn, On the number of positive integers ≤ x and free of prime factors > y, Nederl. Akad. Wet. 54 (1951), 50-60.

2. H. Davenport, Multiplicative Number Theory (2nd ed.), Springer-Verlag, Berlin-Heidelberg-New York, 1980.

3. P. Erdős, A. Ivić and C. Pomerance, On sums involving reciprocals of the largest prime factor of an integer, Glasnik Mat. 21 (1986), 283-300.

4. P. Erdős and C. Pomerance, On the largest prime factors of n and n + 1, Aequationes Math. 17 (1978), 311-321.

5. S. W. Graham and G. Kolesnik, Van der Corput’s method of exponential sums, Cambridge University Press, Cambridge, 1991.

6. C. Hooley, Applications of sieve methods to the theory of numbers, Cambridge University Press, Cambridge, 1976.

7. A. Ivić, The Riemann-zeta-function, John Wiley & Sons, New York, 1985.

8. Jia Chaohua, The greatest prime factor of the integers in a short interval (III), Acta Mathematica Scinica (New Series) 9 (1993), 321-336.

9. Hong-Quan Liu, The greatest prime factor of the integers in an interval, Acta Arith. 65 (1993), 301-328.

10. K. Ramachandra, A note on numbers with a large prime factor, J. London Math. Soc. (2) 1 (1969), 303-306.

11. S. Ramanujan, Collected Works, Chelsea, New York, 1962.

12. A. Selberg, On the normal density of primes in small intervals, and the difference between consecutive primes, Arch. Math. Naturvid. 47 (1943), 87-105.

13. G. Tenenbaum, Sur un problème extrémal en arithmétique, Ann. Inst. Fourier 27 (1987), 1-18.

P. Erdős, Matematikai Kutáto Intézete, Reáltanoda utca 13-15, H-1364 Budapest V, Hungary

S. W. Graham, Mathematical Sciences Department, Michigan Technological University, Houghton, MI 49931, USA

E-mail address: swgraham@mtu.edu

A. Ivić, Katedra Matematike RGF-a, Universiteta u Beogradu, Djušina 7, 11000 Beograd, Serbia (Yugoslavia)

E-mail address: aleks@ivic.matf.bg.ac.yu

C. Pomerance, Department of Mathematics, University of Georgia, Athens, GA 30602, USA

E-mail address: carl@ada.math.uga.edu