Asymptotics of Highly Composite Numbers

Achim Flammenkamp

Fakultät für Mathematik, Universität Bielefeld, Germany

                       achim@uni-bielefeld.de

For any number n ∈ ℕ let

n = ∏_{i=1}^{∞} p_{i}^{e_{i}} = ∏_{i=1}^{m} p_{i}^{e_{i}} with ∀ i ∈ ℕ : e_{i} ∈ ℕ_{0}, p_{i} ∈ ℙ and ∀ j < i : p_{j} < p_{i}

and m = max {i ∈ ℕ : e_{i} > 0} with 0 = max{}

be its canonical prime factorization. Then the number of its divisors is

d(n) = ∏_{i=1}^{m}(1 + e_{i}) .

Notation:

p_{0} := 1 and ∀ x ∈ ℝ^{+} : ln x := loge x , lb x := log_{2} x

Definition 1 A number n ∈ ℕ is called highly composite iff ∀ n′ < n : d(n′) < d(n).

Thus the sequence of the Highly composite numbers is the sequence of the recordholder of the d-function. It follows immediatly for any n ∈ HCN, the set of all Highly composite numbers, holds

∀ i, j ∈ ℕ : i ≥ j ⇒ e_{i} ≤ e_{j} .

S. Ramanujan ([1]) proved, that iff n ∈ HCN then ∀ i ∈ ℕ holds

⌊\frac{ln p_{m}}{ln p_{i}} ⌋ ≤ e_{i} ≤ 2⌊\frac{ln p_{m+1}}{ln p_{i}} ⌋ .

The upper bound can simply be improved to

e_{i} + 2 ≤ (e_{j} + 2)⌈\frac{ln p_{j}}{ln p_{i}} ⌉ ∀ j ∈ ℕ .

Minimizing the right hand side gives the asymptotically correct result e_{i} ∼ \frac{1}{ln 2} \frac{ln p_{m}}{ln p_{i}} , which Ramanujan also proved. Generally ∀ n ∈ HCN ∀ i ∈ ℕ holds

\frac{ln p_{i}}{ln(1 + \frac{1}{e_{i}+0.5})} ∼ \frac{ln p_{m}}{ln 2} respectively e_{i} ∼ \frac{1}{2^{\frac{ln p_{i}}{ln pm}} − 1} − \frac{1}{2} .

Definition 2

∀ n ∈ HCN : x_{min}(n) := max\{\frac{ln p_{i}}{ln(1 + \frac{1}{e_{i}})} : 1 ≤ i ≤ m\}

∀ n ∈ HCN : x_{max}(n) := min\{\frac{ln p_{i}}{ln(1 + \frac{1}{e_{i}+1})} : 1 ≤ i ≤ m+1\}

Theorem 1 If n ∈ HCN and x_{min}(n) < x_{max}(n) then ∀ x ∈ [x_{min}, x_{max}[ holds

e_{i} = ⌊ \frac{1}{^{x} \sqrt{p_{i}} − 1}⌋ ∀ i ∈ ℕ  (1)

Definition 3 A member of HCN is called a superior highly composite number, if ∃ x ∈ ℝ^{+} satisfying (1). Let us denote by SHCN the set of these numbers.

Theorem 2 ∀ x ∈ ℝ^{+} ∃ n ∈ ℕ whose exponents e_{i} are defined by condition (1) with n ∈ SHCN. Escpecially holds for these n: p_{m} ≤ 2^{x} < p_{m+1} .

Definition 4

∀ x ∈ ℕ : π(x) := |{p ≤ x : p ∈ ℙ}|

∀ x ∈ ℝ^{+} : Li(x) := ∫_{2}^{x} \frac{dt}{ln t}

∀ x ∈ ℂ : ζ(x) := ∑_{k=1}^{∞} \frac{1}{k^{x}} = \frac{1}{2^{1−x} − 1} ∑_{k=1}^{∞} \frac{(−1)^{k}}{k^{x}} = 2 sin\frac{xπ}{2} \frac{Γ(1−x)}{(2π)^{1−x}}ζ(1−x)

Now let us remember a few known conjectures respectively theorems:

Conjecture 1

π(x) ∼ Li(x) + O(\sqrt{x} ln x) ,,Riemann Hypothesis”
π(x) ∼ Li(x) + O(\sqrt{\frac{x ln ln x}{ln x}}) ,,Cramèr’s Estimation”

H. von Mangoldt [5] proved the following theorems, namely Theorem 3

∑_{{p∈ℙ \atop p^{k}≤x}} ln p = x − ln 2π − ln \sqrt{1− \frac{1}{x^{2}}} + ∑_{{0≤ℜρ≤1 \atop ζ(ρ)=0}} \frac{x^{ρ}}{ρ}

and Theorem 4

T ∈ ℝ^{+} : |\{t ∈ ℝ^{+} : ζ(σ+2πit) = 0 , 0 < σ < 1, t ≤ T \}| ∼ T ln \frac{T}{e} +O(ln T)

whereas Riemann made his famous conjecture regarding the zeroes of the ζ-function, namely Conjecture 2

∀ σ, t ∈ ℝ with 0 ≤ σ ≤ 1 and ζ(σ + it) = 0 ⇒ σ = \frac{1}{2}

The above two theorems together with this conjecture imply Conjecture 3

∑_{{p∈ℙ \atop p≤x}} ln p = ∑_{h∈ℕ}μ(h) ∑_{{p∈ℙ \atop p^{k}≤x \frac{1}{h}}} ln p ∼ x + O(\sqrt{x} ln^{2} x)

Using the Riemann Hypothesis one can show that Conjecture 4

p_{i+1} − p_{i} ∼ O(\sqrt{p_{i}} ln p_{i})  (2)

Since 1994 it is known [3] that ∀ ε ∈ ℝ^{+} : p_{i+1} − p_{i} ∼ O(p_{i}^{0.535+ε}) and the true order of the “maximal” gap size is conjectured to be ∼ ln^{2} p_{i}, preciser:

p_{i+1} − p_{i} = n ⇒ ln p_{i} ∼ \sqrt{n} + ln \sqrt{n} + O(1)

Definition 5 ∀ n ∈ HCN ∀ k ∈ ℕ : m_{k} := max{i ∈ ℕ : e_{i} ≥ k} Theorem 5

∀ k ∈ ℕ : \frac{ln p_{m_{k}}}{ln p_{m_{1}}} ∼ lb(1 + \frac{1}{k}) + \frac{1}{O(\sqrt{p_{m_{k}}})}

Proof: Let n ∈ HCN with n = ∏_{j=1} ∏_{i=m_{j+1}+1}^{m_{j}} p_{i}^{j} . Next we choose

n′(h, ℓ) = n\frac{∏_{i=m_{1}+1}^{m_{1}+ℓ} p_{i}}{∏_{i=m_{k}+1−h}^{m_{k}} p_{i}} and n^{∗}(h, ℓ) = n\frac{∏_{i=m_{k}+1}^{m_{k}+ℓ} p_{i}}{∏_{i=m_{1}+1−h}^{m_{1}} p_{i}}

with h, ℓ ∈ ℕ to our disposal. Because n ∈ HCN we have

d(n′) > d(n) ⇒ n′ > n and d(n^{∗}) > d(n) ⇒ n^{∗} > n meaning

2^{ℓ}k^{h} > (k + 1)^{h} ⇒ ∏_{i=1}^{ℓ} p_{m_{1}+i} > ∏_{i=1}^{h} p_{m_{k}−i+1}

and

(k + 1)^{ℓ} > k^{ℓ}2^{h} ⇒ ∏_{i=1}^{ℓ} p_{m_{k}+i} > ∏_{i=1}^{h} p_{m_{1}−i+1}

resulting in

ℓ + h lb k > h lb(k + 1) ⇒ ∑_{i=1}^{ℓ} ln p_{m_{1}+i} > ∑_{i=1}^{h} ln p_{m_{k}−i+1}

and

ℓ lb(k + 1) > h + ℓ lb k ⇒ ∑_{i=1}^{ℓ} ln p_{m_{k}+i} > ∑_{i=1}^{h} ln p_{m_{1}−i+1}

Estimating these sums by their maximal and minimal summand, we get

\frac{ℓ}{h} > lb \frac{k + 1}{k} ⇒ ℓ ln p_{m_{1}+ℓ} > h ln p_{m_{k}−h+1}

and

lb \frac{k + 1}{k} > \frac{h}{ℓ} ⇒ ℓ ln p_{m_{k}+ℓ} > h ln p_{m_{1}−h+1}

Transforming the right sides further, we get

ℓ ln p_{m_{1}} + ℓ ln(1 + \frac{p_{m_{1}+ℓ} − p_{m_{1}}}{p_{m_{1}}} ) > h ln p_{m_{k}} + h ln(1 − \frac{p_{m_{k}} − p_{m_{k}−h+1}}{p_{m_{k}}})

and for the second conclusion

ℓ ln p_{m_{k}} + ℓ ln(1 + \frac{p_{m_{k}+ℓ} − p_{m_{k}}}{p_{m_{k}}}) > h ln p_{m_{1}} + h ln(1 − \frac{p_{m_{1}} − p_{m_{1}−h+1}}{p_{m_{1}}} )

Using now the prime-gap conjecture (2), we get next for the first conclusion

ℓ ln p_{m_{1}} + ℓ\frac{O(\sqrt{p_{m_{1}}} ln p_{m_{1}})}{p_{m_{1}}} > h ln p_{m_{k}} − h\frac{O(\sqrt{p_{m_{k}}} ln p_{m_{k}})}{p_{m_{k}}}

and for the other

ℓ ln p_{m_{k}} + ℓ\frac{O(\sqrt{p_{m_{k}}} ln p_{m_{k}})}{p_{m_{k}}} > h ln p_{m_{1}} − h\frac{O(\sqrt{p_{m_{1}}} ln p_{m_{1}})}{p_{m_{1}}}

Simplifying both relation further, we get

\frac{ℓ}{h} + \frac{ℓ}{h}O(\frac{1}{\sqrt{p_{m_{1}}}} ) > \frac{ln p_{m_{k}}}{ln p_{m_{1}}} − \frac{ln p_{m_{k}}}{ln p_{m_{1}}} O(\frac{1}{\sqrt{p_{m_{k}}}})

and

\frac{ln p_{m_{k}}}{ln p_{m_{1}}} + \frac{ln p_{m_{k}}}{ln p_{m_{1}}} O(\frac{1}{\sqrt{p_{m_{k}}}}) > \frac{h}{ℓ} − \frac{h}{ℓ}O(\frac{1}{\sqrt{p_{m_{1}}}} )

Now, chose in the first case \frac{ℓ}{h} = lb\frac{k+1}{k} +ε and in the second case \frac{h}{ℓ} = lb\frac{k+1}{k} −ε such that both pre-conditions with ε ∈ ℝ^{+} become true, we get

(lb\frac{k + 1}{k} + ε)(1 + \frac{1}{O(\sqrt{p_{m_{1}}})}) > \frac{ln p_{m_{k}}}{ln p_{m_{1}}} (1 − \frac{1}{O(\sqrt{p_{m_{k}}})})

and

\frac{ln p_{m_{k}}}{ln p_{m_{1}}} (1 + \frac{1}{O(\sqrt{p_{m_{k}}})}) > (lb\frac{k + 1}{k} − ε)(1 − \frac{1}{O(\sqrt{p_{m_{1}}})})

Let now n, n′, n^{∗} grow larger and larger, such that also m_{1}−m_{2} and m_{k}−m_{k+1} become larger and larger, we can chose larger and larger values h and ℓ resulting in ε tends to 0. With the notice that surely \frac{ln p_{m_{k}}}{ln p_{m_{1}}} ∼ O(1), we finally arrive at

lb\frac{k + 1}{k} + \frac{1}{O(\sqrt{p_{m_{1}}})} > \frac{ln p_{m_{k}}}{ln p_{m_{1}}} + \frac{1}{O(\sqrt{p_{m_{k}}})} > lb\frac{k + 1}{k} − \frac{1}{O(\sqrt{p_{m_{1}}})}

which is equivalent to

\frac{ln p_{m_{k}}}{ln p_{m_{1}}} ∼ lb\frac{k + 1}{k} + \frac{1}{O(\sqrt{p_{m_{k}}})}

.□

Corollary 1

∀ k ∈ ℕ : p_{m_{k}} ∼ (1 + O(\frac{ln p_{m}}{\sqrt{p_{m_{k}}}})) p_{m}^{lb(1+ \frac{1}{k})} ∼ p_{m}^{lb(1+ \frac{1}{k})} + p_{m}^{\frac{1}{2} lb(1+ \frac{1}{k})} O(ln p_{m})

Theorem 6

n ∈ HCN : ln n ∼ p_{m} + pm^{lb \frac{3}{2}} + O(\sqrt{p_{m}} ln^{2} p_{m})

Proof:

ln n = ∑_{i=1}^{m} e_{i} ln p_{i} = ∑_{i=1}^{m_{1}} ln p_{i} + ∑_{i=1}^{m_{2}} ln p_{i} + ∑_{i=1}^{m_{3}}(e_{i} − 2) ln p_{i}

≥ ∑_{{p∈ℙ \atop p≤pm_{1}}} ln p + ∑_{{p∈ℙ \atop p≤pm_{2}}} ln p ∼ p_{m_{1}} + O(\sqrt{p_{m_{1}}} ln^{2} p_{m_{1}}) + p_{m_{2}} + O(\sqrt{p_{m_{2}}} ln^{2} p_{m_{2}})

Using p_{m} = p_{m_{1}} and ln p_{m_{2}} ∼ lb\frac{3}{2} ln p_{m} we get

ln n ≥ p_{m} + p_{m}^{lb \frac{3}{2}} + O(\sqrt{p_{m}} ln^{2} p_{m})

Because the sequence of the n ∈ HCN is strictly monoton increasing the subsequence of the n′ ∈ SHCN must have the same asymtotic in its order of growth as far as we doesn’t get finer than the spacing of successive SHCN, which is bounded from p_{m} by above. Thus we have ln n ∼ ln n′ + O(ln p_{m}) .

(e_{i} − 2) ln p_{i} ≤ ( \frac{1}{^{x} \sqrt{p_{i}} − 1} − 2) ln p_{i} = (\frac{1}{e^{\frac{ln p_{i}}{x}} − 1} − 2) ln p_{i} ≤ (\frac{x}{ln p_{i}} − 2) ln p_{i}

∑_{i=1}^{m_{3}}(e_{i} −2) ln p_{i} ≤ ∑_{i=1}^{m_{3}} x−2 ln p_{i} = m_{3}x−2 ∑_{i=1}^{m_{3}} ln p_{i} ≤ m_{3} lb p_{m+1} −2 ∑_{{p∈ℙ \atop p≤pm_{3}}} ln p

\frac{p_{m_{3}}}{ln p_{m_{3}} − 1} \frac{ln p_{m+1}}{ln 2} −2p_{m_{3}}+O(\sqrt{p_{m_{3}}} ln^{2} p_{m_{3}}) ∼ p_{m_{3}}O(\frac{ln p_{m}}{ln 2 ln p_{m_{3}}} −2) ∼ p_{m_{3}}O(1)

Putting everthing together we finally get

ln n ∼ ln n′ + O(ln p_{m}) ≤ p_{m} + p_{m}^{lb \frac{3}{2}} + O(\sqrt{p_{m}} ln^{2} p_{m}) + p_{m_{3}}O(1) + O(ln p_{m})

and because p_{m_{3}} ∼ p_{m}^{lb \frac{4}{3}} < pm^{\frac{1}{2}} we get the necessary upper bound. □

Corollary 2

∀ n ∈ HCN : p_{m} ∼ ln n − ln^{lb \frac{3}{2}} n + O(ln^{\frac{1}{2}} n ln^{2} ln n)
⇒ m = π(p_{m}) ∼ π(ln n − ln^{lb \frac{3}{2}} n) ∼ Li(ln n) − \frac{ln^{lb \frac{3}{2}} n}{ln ln n}

n ∈ HCN : lb d(n) ∼ ∑_{i=1}^{k−1} lb(1+ \frac{1}{i}) π(p_{m}^{lb 1+\frac{1}{i}})

Proof: Firstly the trival direction with fixed k ∈ ℕ:

lb d(n) = lb ∏_{j=1}^{m}(1 + e_{j}) = ∑_{i=1}^{k−1}(m_{i} − m_{i+1}) lb(1 + i) + ∑_{j=1}^{m_{k}} lb(1 + e_{j})

= ∑_{i=1}^{k−1} m_{i} lb(1+ \frac{1}{i}) + ∑_{j=1}^{m_{k}} lb \frac{1 + e_{j}}{k} ≥ ∑_{i=1}^{k−1} m_{i} lb(1+ \frac{1}{i}) = ∑_{i=1}^{k−1} π(p_{m_{i}}) lb(1+ \frac{1}{i})

To get a sufficient upper bound we estimate the neglected term with n′ ∈ SHCN using (1):

∑_{j=1}^{m_{k}} lb(1 + e_{j}) = \frac{1}{ln 2} ∑_{j=1}^{m_{k}} ln(1 + ⌊ \frac{1}{^{x} \sqrt{p_{j}} − 1}⌋) ≤ \frac{1}{ln 2} ∑_{j=1}^{m_{k}} ln(1 + \frac{1}{^{x} \sqrt{p_{j}} − 1})

Next we use the estimation ln(1 + x) < ^{2.6} \sqrt{x} < x^{0.4} which holds ∀ x ∈ ℝ^{+} .

\frac{1}{ln 2} ∑_{j=1}^{m_{k}} ln(1 + \frac{1}{^{x} \sqrt{p_{j}} − 1}) < \frac{1}{ln 2} ∑_{j=1}^{m_{k}} ( \frac{1}{^{x} \sqrt{p_{j}} − 1})^{0.4} = \frac{1}{ln 2} ∑_{j=1}^{m_{k}} \frac{1}{(e^{\frac{ln p_{j}}{x}} − 1)^{0.4}}

< \frac{1}{ln 2} ∑_{j=1}^{m_{k}} (\frac{x}{ln p_{j}} )^{0.4} < \frac{m_{k}}{ln 2}(\frac{x}{ln 2})^{0.4} < \frac{m_{k}}{ln 2}(\frac{lb p_{m+1}}{ln 2} )^{0.4} < \frac{m_{k}}{ln^{2} 2}(ln p_{m+1})^{0.4}

So, putting everything together, we get

lb d(n′) < ∑_{i=1}^{k−1} π(p_{m_{i}}) lb(1+ \frac{1}{i}) + π(p_{m_{k}})(\frac{\sqrt{ln p_{m}}}{ln^{2} 2} − lb k)

and finally together with the lower bound and p_{m_{i}} ∼ p_{m}^{lb 1+\frac{1}{i}} +O(1) p_{m}^{\frac{1}{2} lb 1+\frac{1}{i}} lnp_{m} we arrive at

lb d(n) ∼ ∑_{i=1}^{k−1} lb(1+ \frac{1}{i})π(p_{m}^{lb 1+\frac{1}{i}}) + O(\sqrt{ln p_{m}} π(p_{m}^{lb 1+\frac{1}{k}})) + O(π(p_{m}^{\frac{1}{2} lb \frac{3}{2}} lnp_{m}))

Because for k > \sqrt{6} + 2 yields lb(1 + \frac{1}{k}) < \frac{1}{2} lb\frac{3}{2}, we lastly have

lb d(n) ∼ ∑_{i=1}^{4} lb(1+ \frac{1}{i})π(p_{m}^{lb 1+\frac{1}{i}}) + O(p_{m}^{\frac{1}{2} lb \frac{3}{2}} )

□

Corollary 3

n ∈ HCN : lb d(n) ∼ Li(ln n) + \frac{1}{lb\frac{3}{2}} \frac{ln^{lb^{\frac{3}{2}}} n}{ln^{2} ln n} + O(\sqrt{n} ln n)

Next, two conjectures follow about the order of appearance of the first respectively last Highly composite number for fixed largest prime p_{m}.

Conjecture 5

∀ k ∈ ℕ ∀ n ∈ HCN ∃ n′ ∈ HCN : n′ > n , m_{k}(n′) = m_{k}(n)+1

∀ k ∈ ℕ ∀ n ∈ HCN, m_{k}(n)>0 ∃ n′ ∈ HCN : n′ < n , m_{k}(n′) = m_{k}(n)−1

Worded differently: if there is a HCN containing p_{i}^{k} then there will be a larger HCN with p_{i+1}^{k} and, supposed i>0, there is a smaller HCN containing p_{i−1}^{k} .

Conjecture 6 Let n′, n^{∗} ∈ HCN and d(n^{∗}) > 2d(n′) . Then holds with n ∈ HCN

∀ n ∈]n′, n^{∗}] : m(n) > m(n′) ⇒ ∀ n > n′ : m(n) > m(n′) .

References

[1] Srinivasa Ramanujan, Collected Papers of Srinivasa Ramanujan, Editors: G. H. Hardy, S. Aiyar, P. Venkatesvara, and B. M. Wilson, Chap. 15, Highly Composite Numbers, Cambridge Univ. Press (1927), 78–128.

[2] Srinivasa Ramanujan, Highly composite numbers, Proc. London Math. Soc., Ser. 2 14 (1915), 347–409.

[3] R. C. Baker and G. Harman, The difference between consecutive primes, Proc. London Math. Soc. III, Ser. 72 2 (1996) 261–280.

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

[5] H. von Mangoldt, Zu Riemann’s Abhandlung ,,Über die Anzahl …”, Crelles J., 114, (1895), 255–305.

[6] Marek Wolf, Some conjectures on the gaps between consecutive primes,

   http://www.ift.uni.wroc.pl/~mwolf/conjectures.ps.gz

last significantly changed: 2002–12–07 14:45 UT+2