An independence result of PA using multiplicative number theory^{∗}

Arnoud den Boer

14 december 2005

Samenvatting

We consider the maximumlength of a sequence of descending ordinal numbers which are bounded by a function indexed with an ordinal α ≤ ϵ_{0}. From Königs Lemma it follows that this length is finite. By Schutte-isomorphism between the ordinals ≤ ϵ_{0} and the natural numbers ≥ 1, we translate this to a statement in the natural numbers. Using lowerand upperbounds of the global countfunction of a certain multiplicative system, we then obtain that this maximumlength is provably total iff α < ϵ_{0}.

1 Introduction and Preliminaries

1.1 Introduction

In 1975, Paris and Harrington were the first to find a mathematical relevant statement which is true but unprovable within PA (the axioms about the natural numbers). In 1931 Gödel already had proven the existence of such statements, but the example he came with, was somewhat artificial and thus less satisfying. (It looked like the sentence ’this sentence is true but unprovable’). Since 1975, a lot more of interesting independence results have been found. In this paper we prove another independence result It is known by folklore that all strictly descending sequences of ordinals, are of finite size (descending w.r.t. the standard ordering on ordinals). This implies that the maximum length of a sequence of strictly descending ordinals (m_{i}) which are bounded by a certain function m_{i} ≤ f(i), is also finite. This fact is unprovable from PA if we take f the identity function. If f is constant, then PA does prove it. The question arises for which functions, the finiteness of this length, is provable from PA. In this paper we obtain an exact classification to this problem. It turns out that there exist a family of functions (f_{α})_{α≤ϵ_{0}} with α an ordinal, such that the phase transition exactly lies at ϵ_{0}.

∗This article an elaboration of a preprint of Andreas Weiermann entitled ’An application of multiplicative number theory to independence results for PA’, and was made as ’kleine scriptie’

The proof is based on bounds of the count function of a certain multiplicative system. Although asymptotic bounds for additive and multiplicative number systems have been studied a lot in literature, there is no result for the asymptotic behaviour of the system that is studied in this paper. Therefore we spend most of this paper to establish lower- and upperbounds. It turns out that these bounds are essential in the proofs of the proof-theoretic assertion.

1.2 Definitions

With N we denote the natural numbers, starting at 0. Let (p_{i})_{i≥1} enumerate the prime numbers in increasing order. Let P be the set of all primes. Define the following relation on N: m ≺ n :⇔ (m ≠ n&(n = 0 ∨ m = 1 ∨ [\frac{m}{gcd(m,n)} = p_{m_{1}} · . . . · p_{m_{k}}&\frac{n}{gcd(m,n)} = p_{n_{1}} · . . . ·_{n_{l}} &∀i ≤ k∃j ≤ l(m_{i} ≺ n_{j}]))

A multiplicative number system ⟨A, P, ·, 1, M⟩ is a countable free commutative monoid ⟨A, ·, 1⟩ with P the set of indecomposable elements (’primes’), and M a multiplicative norm on A (i.e. M : A → N, M(a) = 1 ⇔ a = 1, M(a · b) = M(a) · M(b) for all a, b ∈ A), such that for every n ≥ 2, {a ∈ A : M(a) = n} is finite. Let q_{1} := p_{2} and q_{k+1} := p_{q_{k}} for k ≥ 1; and q_{0}(d) := d and q_{k+1}(d) := p_{q_{k}(d)} for k ≥ 1 For K ≥ 1, let Q_{K} := {m ∈ N : m ≺ q_{K}} and Q_{K}(d) := {m ∈ N : m ≺ q_{K}} Let M(n) := n Then ⟨Q_{K}, P ∩ Q_{K}, · ↑ (Q_{K} × Q_{K}), 1, M ↑ Q_{K}⟩ is a multiplicative system. (↑ means restriction). Let C_{Q_{K}} (n) := #{a ∈ Q_{K} : M(a) ≤ n} be the global count function. In section 2 of this article, nontrivial upper- and lowerbounds on this global countfunction will be obtained.

An additive number system ⟨A, P, ·, 1, N⟩ is a countable free commutative monoid ⟨A, ·, 1⟩ with P the set of indecomposable elements, and with N an additive norm on A (i.e. N : A → N, N(a) = 0 ⇔ a = 1, N(a · b) = N(a) + N(b) for all a, b ∈ A), such that for every n ≥ 1, {a ∈ A : N(a) = n} is finite Let N(1) := 0 and N(Π_{i∈I}p_{i}^{m_{i}}) := ∑_{i∈I} m_{i} · (N(i) + 1) be an additive norm. Let c_{Q_{K}} (n) := #{a ∈ Q_{K} : N(a) = n} be the local count function. Bounds for the local count function have already been obtained in the literature on additive number theory, and even the asymptotic behaviour. For example a famous theorem of Hardy and Ramanujan says

c_{Q_{2}}(n) ∼ \frac{exp (π\sqrt{\frac{2}{3}n})}{4\sqrt{3n}}

Related results for the set Q_{K} for K ≥ 3 have been obtained by Yamashita in [8].

We write a_{1} := a, a_{k+1} := a^{a_{k}}, a_{0}(d) := d, a_{k+1}(d) := a^{a_{k}(d)} for a, d ∈ R, k ∈ N For n ≥ 1 let ln_{1}(n) := max{(1, ln(n)} and ln_{k+1}(n) := max{1, ln_{1}(ln_{k}(n))}

1.3 Auxilary lemmata

Lemma 1.1 1. p_{n} ≤ 3n for n ≤ 11

2. p_{n} ≤ 4n for 11 < n ≤ 19

3. p_{n} ≤ n(ln_{1}(n) + ln_{1} ln_{1}(n) − \frac{1}{2}) for n ≥ 20

4. p_{n} ≤ n(ln_{1}(n) + ln_{1} ln_{1}(n) + 3) for n ≥ 1

5. p_{n} ≤ 6n ln_{1}(n) for n ≥ 1

6. p_{n} ≥ n(ln_{1}(n) + ln_{1} ln_{1}(n) − 1.0072629) for n ≥ 3

7. p_{n} ≥ 1, 5 · n for n ≥ 1

Proof The assertions 1) and 2) follow by looking at a prime number table. Assertion 3) follows from Rosser Schoenfeld [6]. Assertion 4) follows from assertion 1)-3). Assertion 5) follows from 4) as follows: If ln_{1} ln_{1}(n) ≤ 1 then 3 + ln_{1} ln_{1}(n) = 4 ≤ 5 ln_{1}(n) If ln_{1} ln_{1}(n) ≥ 1 then n ≥ 16. From 3 + ln_{1} ln_{1}(16) ≤ 5 ≤ 5 ln_{1} 16 and \frac{d}{dn}(3 + ln ln(n)) ≤ \frac{d}{dn}5 ln(n) we see 3 + ln_{1} ln_{1}(n) ≤ 5 ln_{1}(n)∀n ≥ 1. The assertion follows by applying assertion 4). Assertion 6) follows from Rosser Schoenfeld [6]. Assertion 7) is checked manually for n = 1, ⋯, 4 and for n ≥ 5 it follows from assertion 6) since then ln_{1}(n)+ln_{1} ln_{1}(n)−1.0072629 ≥ ln_{1}(5)+ln_{1} ln_{1}(5)− 1.0072629 ≥ 1.5

Lemma 1.2 m ≤ 2^{2·N(m)^{2}} for all m ≥ 1

Proof Induction on m. If m = 1 then M(m) = 1 = 2^{2N(1)^{2}} Assume 2 ≤ m = p_{i_{1}} · . . . · p_{i_{k}} · 2^{n} where p_{i_{l}} ≥ 3 for all 1 ≤ l ≤ k. For 1 ≤ l ≤ k : i_{l} < p_{i_{l}} ≤ m so the induction hypothesis yields i_{l} ≤ 2^{2N(i_{l})^{2}} hence by lemma 1.1.4

p_{i_{l}} ≤ p_{2^{2N(i_{l})^{2}}} ≤ 2^{2N(i_{l})^{2}}(ln_{1}(2^{2N(i_{l})^{2}}) + ln_{1}(ln_{1}(2^{2N(i_{l})^{2}})) + 3)  (1)

Since ln_{1}(2^{2N(i_{l})^{2}}) ≤ 2N(i_{l})^{2} ln_{1}(2) and ln_{1}(ln_{1}(2^{2N(i_{l})^{2}})) ≤ ln_{1}(2N(i_{l})^{2} ln_{1}(2)) ≤ ln_{1}(2N(i_{l})^{2}) ≤ ln_{1}(2) + ln_{1}(N(i_{l})^{2}) ≤ ln_{1}(2) + 2 ln_{1}(N(i_{l})) we get by (1) that

p_{i_{l}} ≤ 2^{2N(i_{l})^{2}}(2N(i_{l})^{2} ln_{1}(2) + ln_{1}(2) + 2 ln_{1}(N(i_{l})) + 3)

≤ 2^{2N(i_{l})^{2}}(2N(i_{l})^{2} + 2 ln_{1}(N(i_{l})) + 4)

≤ 2^{2N(i_{l})^{2}}(2N(i_{l})^{2} + 2N(i_{l}) + 4) ≤ 2^{2N(i_{l})^{2}}(2N(i_{l})^{2} + 4N(i_{l}) + 2)

(since N(i_{l}) ≥ 1)

= 2^{2N(i_{l})^{2}}2(N(i_{l}) + 1)^{2} = 2^{2N(i_{l})^{2}+1+2log_{2}(N(i_{l})+1)}
≤ 2^{2N(i_{l})^{2}+2+2(N(i_{l})+1)} ≤ 2^{2N(i_{l})^{2}+4N(i_{l})+2} = 2^{2(N(i_{l})+1)^{2}}

Hence

m ≤ 2^{2(N(i_{1})+1)^{2}} · . . . · 2^{2(N(i_{k})+1)^{2}} · 2^{n}

Now if k = 1 then

2(N(i_{1}) + 1)^{2} + n = 2N(i_{1})^{2} + 4N(i_{1}) + 2 + n

≤ 2N(i_{1})^{2} + 4N(i_{1})k + 2k^{2} + 2n^{2} + 4N(i_{1})n + 4kn = 2(N(i_{1}) + k + n)^{2}

And if k > 1 then

2(N(i_{1}) + 1)^{2} + … + 2(N(i_{k}) + 1)^{2} + n

= 2N(i_{1})^{2} + … + 2N(i_{k})^{2} + 4N(i_{1}) + … + 4N(i_{k}) + 2 + … + 2 + n

≤ 2N(i_{1})^{2} + … + 2N(i_{k})^{2} + 4N(i_{1})k + … + 4N(i_{k})k
+2(N(i_{1})N(i_{2})) + … + 2N(i_{k−1})N(i_{k}) + 2N(i_{k})N(i_{1}) + 2n^{2}
≤ 2(N(i_{1}) + … + N(i_{k}) + k + n)^{2}

Hence

m ≤ 2^{2(N(i_{1})+...+N(i_{k})+k+n)^{2}} = 2^{2(N(i_{1})+1+...+N(i_{k})+1+N(2^{n}))^{2}} = 2^{2(N(m))^{2}}

Lemma 1.3 a) If a_{n} and b_{n} are nonnegative, and a_{n} ∼ b_{n} and b_{n} → ∞ for n → ∞, then ln(a_{n}) ∼ ln(b_{n})

b) In particular we have ln_{K−2}(ln_{2}(n)^{2}) ∼ ln_{K}(n) for K ≥ 4

Proof a) Let ϵ > 0 Choose M_{1} s.t. ∀n ≥ M_{1} b_{n}^{ϵ} ≥ b_{M_{1}}^{ϵ} > 1 Choose M_{2} s.t. ∀n ≥ M_{2} \frac{a_{n}}{b_{n}} ≤ b_{M_{2}}^{ϵ} Let M := max(M_{1}, M_{2}) Then ∀n ≥ M : \frac{a_{n}}{b_{n}} ≤ b_{n}^{ϵ} hence

| ln(a_{n}) − ln(b_{n})| ≤ ϵ| ln(b_{n})|

⇒ |\frac{ln(a_{n})}{ln(b_{n})} − 1| = |\frac{ln(a_{n}) − ln(b_{n})}{ln(b_{n})}| ≤ \frac{ϵ| ln(b_{n})|}{| ln(b_{n})|} = ϵ

⇒ ln(a_{n}) ∼ ln(b_{n})

b) We consider n > e_{K}, then ln_{k}(n)(1 ≤ k ≤ K) is just the k-times iterated logarithm

ln_{K−2}(ln_{2}(n)^{2}) = ln_{K−3}(ln(ln_{2}(n)^{2})) = ln_{K−3}(2 ln_{3}(n)) = ln_{K−4}(ln(2 ln_{3}(n)))

= ln_{K−4}(ln(2) + ln_{4}(n))

We show the statement by induction on K If K = 4 then

lim_{n→∞} \frac{ln_{K−2}(ln_{2}(n)^{2})}{ln_{K}(n)} = lim_{n→∞} \frac{ln_{K−4}(ln(2) + ln_{4}(n))}{ln_{K}(n)} = lim_{n→∞} \frac{ln(2) + ln_{4}(n)}{ln_{4}(n)} = 1

For K > 4 Suppose

lim_{n→∞} \frac{ln_{K−2}(ln_{2}(n)^{2})}{ln_{K}(n)} = 1

We can apply a), since ln_{K}(n) → ∞ as n → ∞, and both ln_{K−2}(ln_{2}(n)^{2}) and ln_{K}(n) are nonnegative numbers for all n That gives us

1 = lim_{n→∞} \frac{ln(ln_{K−2}(ln_{2}(n)^{2}))}{ln(ln_{K}(n))} = lim_{n→∞} \frac{ln_{K+1−2}(ln_{2}(n)^{2})}{ln_{K+1}(n)}

Lemma 1.4 (Stirlings Formula) S(n) := (\frac{n}{e})^{n} \sqrt{2πn}. Then S(n) ∼ n! as n → ∞

Lemma 1.5 ln(p_{2^{0}}) · . . . · ln(p_{2^{k}}) ≤ (k + 1)!

Proof It suffices to show ln(p_{2^{i−1}}) ≤ i for all i. For i = 1, 2, 3 it is checked manually. For i ≥ 4 it follows using Lemma 1.1.4:

ln(p_{2^{4−1}}) ≤ ln(2^{4−1} · (ln_{1}(2^{4−1}) + ln_{1}(ln_{1}(2^{4−1})) + 3)) ≤ 4

Now

ln(2^{i−1}(ln_{1}(2^{i−1}) + ln_{1}(ln_{1}(2^{i−1})) + 3)) =

(i − 1) ln(2) + ln((i − 1) ln(2) + ln(i − 1) + ln(ln(2)) + 3)

⇒ \frac{d}{di} ln(2^{i−1}(ln_{1}(2^{i−1}) + ln_{1}(ln_{1}(2^{i−1})) + 3)) =

\frac{d}{di}(i − 1) ln(2) + ln((i − 1) ln(2) + ln(i − 1) + ln(ln(2)) + 3)

= ln(2) + \frac{ln(2) + \frac{1}{i−1}}{(i − 1) ln(2) + ln(i − 1) + ln(ln(2)) + 3}

≤ ln(2) + \frac{ln(2) + \frac{1}{4−1}}{(4 − 1) ln(2) + ln(4 − 1) + ln(ln(2)) + 3} < 1

And thus ln(p_{2^{i−1}}) ≤ ln(2^{i−1}(ln_{1}(2^{i−1}) + ln_{1}(ln_{1}(2^{i−1})) + 3)) ≤ i for all i ≥ 4 Lemma 1.6 \frac{2^{−mx}}{1−2^{−mx}} ≤ \frac{1}{m} \frac{2^{−x}}{1−2^{−x}} for all x ∈]0, ∞[, m ∈ N

Proof By induction. For m = 1 it is obvious. Assume for all x ∈]0, ∞[ we have

\frac{2^{−mx}}{1 − 2^{−mx}} ≤ \frac{1}{m} \frac{2^{−x}}{1 − 2^{−x}}

We rewrite it

(\frac{2^{−x}}{1 − 2^{−x}} ) \frac{(2^{−x})^{m−1}}{1 + 2^{−x} + ⋯ + (2^{−x})^{m−1}} ≤ \frac{1}{m} \frac{2^{−x}}{1 − 2^{−x}}

The term \frac{2^{−x}}{1−2^{−x}} is strictly positive, hence

\frac{(2^{−x})^{m−1}}{1 + 2^{−x} + ⋯ + (2^{−x})^{m−1}} ≤ \frac{1}{m} ⇒

m(2^{−x})^{m−1} ≤ 1 + (2^{−x}) + ⋯ + (2^{−x})^{m−1}

Now by the induction hypothesis,

(m+1)(2^{−x})^{m} = 2^{−x}m(2^{−x})^{m−1}+(2^{−x})^{m} ≤ 2^{−x} (1 + (2^{−x}) + ⋯ + (2^{−x})^{m−1})+(2^{−x})^{m}

= (2^{−x})^{m} + 2^{−x} + ⋯ + (2^{−x})^{m} ≤ 1 + 2^{−x} + ⋯ + (2^{−x})^{m}

since (2^{−x})^{m} ≤ 1 for all x > 0, m ≥ 0. Hence

\frac{(2^{−x})^{m}}{1 + 2^{−x} + ⋯ + (2^{−x})^{m}} ≤ \frac{1}{m + 1} ⇒

\frac{2^{−x}}{1 − 2^{−x}} \frac{(2^{−x})^{m}}{1 + 2^{−x} + ⋯ + (2^{−x})^{m}} ≤ \frac{1}{m + 1} \frac{2^{−x}}{1 − 2^{−x}} ⇒

\frac{2^{−(m+1)x}}{1 − 2^{−(m+1)x}} ≤ \frac{1}{m} \frac{2^{−x}}{1 − 2^{−x}}

for all x ∈]0, ∞[, m ∈ N

Lemma 1.7 (cf. Norris 1.12) With S(n) the Stirling estimate as defined in Lemma 1.4, we have \frac{n!}{S(n)} ≤ \frac{M!}{S(M)} for all n ≥ M

Proof Define

a_{n} := ln \frac{n!}{S(n)} = ln \frac{n!}{(\frac{n}{e})^{n} \sqrt{2πn}}

a_{n} − a_{n+1} = ln(\frac{n!}{S(n)}) − ln (\frac{(n + 1)!}{S(n + 1)}) = ln (\frac{n!}{(n + 1)!} \frac{(n + 1)^{n+1+ \frac{1}{2}} e^{−(n+1)}}{n^{n+ \frac{1}{2}} e^{−n}} )

= ln (\frac{1}{e}(\frac{n + 1}{n})^{n+ \frac{1}{2}} ) = −1+(n+\frac{1}{2}) log(\frac{n + 1}{n}) = \frac{1}{2}(2n+1) ln(\frac{1 + (2n + 1)^{−1}}{1 − (2n + 1)^{−1}} )−1

For all |t| < 1 we have the power series expansion

ln(1 + t) = t − \frac{1}{2}t^{2} + \frac{1}{3}t^{3} − ⋯

ln(1 − t) = −t − \frac{1}{2}t^{2} − \frac{1}{3}t^{3} − ⋯

And thus

\frac{1}{2} ln (\frac{1 + t}{1 − t}) = t + \frac{1}{3}t^{3} + \frac{1}{5}t^{5} + ⋯

Using this, we get

a_{n} − a_{n+1} = (2n + 1) (\frac{1}{2n + 1} + \frac{1}{3} \frac{1}{(2n + 1)^{3}} + \frac{1}{5} \frac{1}{(2n + 1)^{5}} + ⋯) − 1

= \frac{1}{3} \frac{1}{(2n + 1)^{2}} + \frac{1}{5} \frac{1}{(2n + 1)^{4}} + ⋯ ≥ 0

Hence, (∀M)(∀n ≥ M) we have

\frac{M!}{S(M)} = exp(a_{M}) ≥ exp(a_{M+1}) ≥ ⋯ ≥ exp(a_{n}) = \frac{n!}{S(n)}

Corollary 1.8 \frac{1}{n!} ≥ 0.9 · (\frac{e}{n})^{n} \frac{1}{\sqrt{2πn}} for all n ∈ N

Proof Take M=1 in Lemma 1.7 and use \frac{S(1)}{1!} > 0.9

Lemma 1.9 y ≥ 2 ⇒ 0.9 · exp(y) ≥ exp(0.9 · y)

Proof 0.9 exp(2) > exp(0.9 · 2) and \frac{d}{dy} 0.9 · exp(y) = 0.9 · exp(y) > 0.9 · exp(0.9 · y) = \frac{d}{dy} exp(0.9 · y)

Lemma 1.10 ln(\frac{1}{1−x})) = ∑_{m=1}^{∞} \frac{x^{m}}{m} for 0 < x < 1

Proof By powerseries expansion, like in the proof of lemma 1.7, ln(\frac{1}{1−x})) = − ln(1 − x) = ∑_{m=1}^{∞} \frac{x^{m}}{m} for 0 < x < 1

Lemma 1.11

ln(\frac{1}{1 − 1.5^{−x}}) ≤ \frac{2^{−x}}{1 − 2^{−x}} + 0.5 (x > 0)

Proof Case 1: x > \frac{1}{2} Define F (x) = ln(\frac{1}{1−1.5^{−x}}) and G(x) = \frac{2^{−x}}{1−2^{−x}} + 0.5 Both these functions are strictly decreasing in x. F is a bijection from (0, ∞) to (0, ∞), G is a bijection from (0, ∞) to (0.5, ∞) Let x_{1} = F^{−1}(0.5). For all x > x_{1}, F (x) < F (x_{1}) = 0.5 < G(x) Let x_{2} = F^{−1}(G(x_{1})). For all x_{2} < x < x_{1}, F (x) < F (x_{2}) = G(x_{1}) < G(x) Let x_{3} = F^{−1}(G(x_{2})). For all x_{3} < x < x_{2}, F (x) < F (x_{3}) = G(x_{2}) < G(x) Let x_{4} = F^{−1}(G(x_{3})). For all x_{4} < x < x_{3}, F (x) < F (x_{4}) = G(x_{3}) < G(x) Let x_{5} = F^{−1}(G(x_{4})). For all x_{5} < x < x_{4}, F (x) < F (x_{5}) = G(x_{4}) < G(x) Calculations show that x_{5} < 0.5, this proofs the assertion for all x > 0.5

Case 2: 0 < x < \frac{1}{2} Observe

x < 1 ⇒ \frac{2^{−x}}{1 − 2^{−x}} > 1 ⇒ e · \frac{2^{−x}}{1 − 2^{−x}} ≤ exp (\frac{2^{−x}}{1 − 2^{−x}} )

Write

\frac{1}{1 − 1.5^{−x}} = \frac{1 − 2^{−x}}{x} \frac{x}{1 − 1.5^{−x}} 2^{x} \frac{2^{−x}}{1 − 2^{−x}}

We claim that for 0 < x < \frac{1}{2}

\frac{1 − 2^{−x}}{x} \frac{x}{1 − 1.5^{−x}} 2^{x} < e

(Observe that this proves the assertion for all 0 < x < \frac{1}{2}) Proof of the claim: (∀x > 0)2^{x} ln(2) > ln(2), hence (∀x > 0)\frac{d}{dx}2^{x} − 1 > \frac{d}{dx}x ln(2) Together with 2^{0} − 1 = 0 ln(2) this implies

(∀x > 0)2^{x} − 1 > x ln(2)
⇒ (∀x > 0)1 − 2^{−x} > 2^{−x}x ln(2)
⇒ (∀x > 0)x2^{−x} ln(2) − (1 − 2^{−x}) < 0

⇒ (∀x > 0)\frac{d}{dx} \frac{1 − 2^{−x}}{x} = \frac{x2^{−x} ln(2) − (1 − 2^{−x})}{x^{2}} < 0

Furthermore, lim_{x↓0} \frac{1−2^{−x}}{x} = ln(2) We can conclude (∀x > 0)\frac{1−2^{−x}}{x} < ln(2) With a similar argument, but with 2 replaced by 1.5, we can show that

(∀x > 0)\frac{d}{dx} \frac{x}{1 − 1.5^{−x}} > 0

and thus

0 < x < \frac{1}{2} ⇒ \frac{x}{1 − 1.5^{−x}} < \frac{\frac{1}{2}}{1 − 1.5^{\frac{1}{2}}}

And thus, for all 0 < x < \frac{1}{2},

\frac{1 − 2^{−x}}{x} \frac{x}{1 − 1.5^{−x}} 2^{x} < ln(2)\frac{\frac{1}{2}}{1 − 1.5^{\frac{1}{2}}} · 2^{\frac{1}{2}} < e

2 Bounds for C_{Q_{K}}

2.1 Lower bounds for C_{Q_{K}}

Lemma 2.1 C_{Q2}(n) ≥ exp(1, 9 · \sqrt{ln(n)}) for n ≥ 1 + exp(83^{2})

Proof We use an argument from the book of Burris [2] Choose any n ≥ 1 + exp(83^{2}) C_{Q_{2}}(n) = #{m ∈ N : m ⪯ q_{2} = 5, m ≤ n} C_{Q_{1}(2^{⌊\sqrt{ln(n)}⌋})}(n) = #\{m ∈ N : m ⪯ p_{2^{⌊\sqrt{ln(n)}⌋}}, m ≤ n\}

If m ⪯ p_{2^{⌊\sqrt{ln(n)}⌋}} then m ⪯ p_{3}, since 2^{⌊\sqrt{ln(n)}⌋} ⪯ 3. Hence C_{Q_{2}}(n) ≥ C_{Q_{1}(2^{⌊\sqrt{ln(n)}⌋})}(n)

Q_{1}(2^{⌊\sqrt{ln(n)}⌋}) = \{p_{2^{0}}^{m_{0}} · . . . · p_{2^{k}}^{m_{k}} : k = ⌊\sqrt{ln(n)}⌋ − 1, m_{0}, …, m_{k} ∈ N \}

has ⌊\sqrt{ln(n)}⌋ indecomposable elements, namely p_{2^{0}}, …, p_{2^{⌊\sqrt{ln(n)}⌋−1}}

Hence, C_{Q_{1}(2^{⌊\sqrt{ln(n)}⌋})}(n) is the number of (m_{0}, …, m_{k}) ∈ N^{⌊\sqrt{ln(n)}⌋} s.t.

p_{2^{0}}^{m_{0}} · . . . · p_{2^{k}}^{m_{k}} ≤ n

Take ln on both sides:

m_{0} ln(p_{2^{0}}) + … + m_{k} ln(p_{2^{k}}) ≤ ln(n)

Write

A := {(m_{0}, ⋯, m_{k}) ∈ N_{≥0}^{k+1} : m_{0} ln(p_{2^{0}}) + … + m_{k} ln(p_{2^{k}}) ≤ ln(n)}

B := {(m_{0}, ⋯, m_{k}) ∈ R_{≥0}^{k+1} : m_{0} ln(p_{2^{0}}) + … + m_{k} ln(p_{2^{k}}) ≤ ln(n)}

Let vol(B) be the volume of B in R^{k+1}. We claim #A ≥vol(B) : For all \overrightarrow{m} = (m_{0}, ⋯, m_{k}) ∈ A we define

I\overrightarrow{m} := \{(x_{0}, ⋯, x_{k}) ∈ R^{k+1} : m_{i} ≤ x_{i} ≤ m_{i} + 1, i = 0, ⋯, k\}

vol(I\overrightarrow{m}) = 1, hence

#A = ∑_{\overrightarrow{m}∈A} 1 = ∑_{\overrightarrow{m}∈A} vol(I\overrightarrow{m}) = vol ( ⋃_{\overrightarrow{m}∈A} I\overrightarrow{m})

Take any (m_{0}, …, m_{k}) ∈ B. Then (⌊m_{0}⌋, …, ⌊m_{k}⌋) ∈ A and (m_{0}, …, m_{k}) ∈ I_{(⌊m_{0}⌋,...,⌊m_{k}⌋)}. Hence B ⊂ ⋃_{\overrightarrow{m}∈A} I\overrightarrow{m} ⇒ vol(B) ≤ vol(⋃_{\overrightarrow{m}∈A} I\overrightarrow{m}) = #A. Hence,

C_{Q_{1}(2^{⌊\sqrt{ln(n)}⌋})}(n) = #A

≥ vol(B) = \frac{1}{⌊\sqrt{ln(n)}⌋! ln(p_{2^{0}}) · . . . · ln(p_{2^{k}})}(ln(n))^{⌊\sqrt{ln(n)}⌋}

≥ \frac{1}{⌊\sqrt{ln(n)}⌋!^{2}} (ln(n))^{⌊\sqrt{ln(n)}⌋}

by lemma 1.5

Note that (\frac{S(2)}{2!})^{2} > 0.9, and n ≥ 1 + exp(83^{2}) > e^{4} ⇒ ⌊\sqrt{ln(n)}⌋ ≥ 2 so we can apply lemma 1.7 to get

\frac{1}{⌊\sqrt{ln(n)}⌋!^{2}} (ln(n))^{⌊\sqrt{ln(n)}⌋} ≥ 0.9·( \frac{1}{^{\frac{⌊\sqrt{ln(n)}⌋}{e}})^{⌊\sqrt{ln(n)}⌋}\sqrt{2π⌊\sqrt{ln(n)}⌋}})^{2} (ln(n))^{⌊\sqrt{ln(n)}⌋}

= 0.9 · e^{2⌊\sqrt{ln(n)}⌋} \frac{1}{⌊\sqrt{ln(n)}⌋^{2⌊\sqrt{ln(n)}⌋}} \frac{1}{2π⌊\sqrt{ln(n)}⌋}(ln(n))^{⌊\sqrt{ln(n)}⌋}

≥ 0.9 · e^{2⌊\sqrt{ln(n)}⌋} \frac{1}{2π⌊\sqrt{ln(n)}⌋} \frac{⌊\sqrt{ln(n)}⌋^{2⌊\sqrt{ln(n)}⌋}}{⌊\sqrt{ln(n)}⌋^{2⌊\sqrt{ln(n)}⌋}}

= 0.9 · e^{2⌊\sqrt{ln(n)}⌋} \frac{1}{2π⌊\sqrt{ln(n)}⌋}

= 0.9 · exp(2⌊\sqrt{ln(n)}⌋) exp (ln (\frac{1}{2π⌊\sqrt{ln(n)}⌋}))

= 0.9 · exp(2⌊\sqrt{ln(n)}⌋ − ln(2π⌊\sqrt{ln(n)}⌋))

We write N_{≥2} = ⋃_{p≥0} [⌊1 + exp(p^{2})⌋, ⌊exp((p + 1)^{2})⌋] For each n ∈ N_{≥2} there exist a unique p st n ∈ [⌊1 + exp(p^{2})⌋, ⌊exp((p + 1)^{2})⌋] Now

(i)\sqrt{ln(n)} ≥ \sqrt{ln(⌊1 + exp(p^{2})⌋)} ≥ \sqrt{ln(exp(p^{2}))} = p
(ii)⌊\sqrt{ln(n)}⌋ ≥ ⌊\sqrt{ln(⌊1 + exp(p^{2})⌋)⌋} ≥ ⌊\sqrt{ln(exp(p^{2}))}⌋ = ⌊p⌋ = p

(iii)⌊\sqrt{ln(n)}⌋ ≤ ⌊\sqrt{ln(⌊exp((p + 1)^{2})⌋)}⌋ ≤ ⌊\sqrt{ln(exp((p + 1)^{2}))}⌋ = ⌊p+1⌋ = p+1

Hence,

0.9 exp(2⌊\sqrt{ln(n)}⌋ − ln(2π⌊\sqrt{ln(n)}⌋))
≥ 0.9 exp(2p − ln(2π(p + 1))

We know

0.1p − 1.9 + ln(0.9) ≥ ln(2π) + ln(p + 1)

for p ≥ 83. (Calculation show that the estimate does not hold for p = 82 but does hold for p = 83; and for p ≥ 83 the derivative w.r.t. p of the lefthandside is strictly larger than that of the righthandside, implying that it holds for all p ≥ 83). This implies

ln 0.9 + 2p − ln(2π(p + 1)) ≥ 1.9(p + 1)
⇒ 0.9 exp(2p − ln(2π(p + 1))) ≥ exp(1.9(p + 1))

for p ≥ 83. Therefore, for n ≥ 1 + exp(83^{2}), we have the estimation

C_{Q2}(n) ≥ exp(1, 9 · \sqrt{ln(n)})

Remark We can slightly improve this estimate and get the coefficient 1.9 as close to 2 as we want. Because

\frac{1}{⌊\sqrt{ln(n)}⌋!^{2}} (ln(n))^{⌊\sqrt{ln(n)}⌋} ≥ (\frac{S(M)}{M!})^{2} \frac{1}{S(⌊\sqrt{ln(n)}⌋)^{2}} (ln(n))^{⌊\sqrt{ln(n)}⌋}

for any M, n ≥ M, and (\frac{S(M)}{M!})^{2} → 1 when M → ∞.

Write C = (\frac{S(M)}{M!})^{2} There exists a p′ such that for all p ≥ p′ we have

(1 − C)p − (1 + C) + ln(C) ≥ ln(2π) + ln(p + 1)
⇒ C_{Q2}(n) ≥ C exp(2p − ln(2π(p + 1))) ≥ exp((1 + C)(p + 1))

n ≥ M, n ≥ 1 + exp(p^{′2})

Lemma 2.2 C_{Q_{3}}(n) ≥ exp(\frac{0.5 ln(n)}{ln_{2}(n)}) for n ≥ e_{4}^{e_{3}}

Proof Choose n ≥ e_{4}^{e_{3}} Put

k := k(n) := \frac{ln_{1}(n)}{ln_{2}(n)^{2} + 2 ln_{3}(n) + ln(6)}

and

l := l(n) := exp(ln_{2}(n)^{2})

Then n ≥ e_{4}^{e_{3}} ≥ e^{e} hence

k ln_{1}(6l ln_{1}(l)) = k(ln(6) + ln(l) + ln(ln(l))) =

k(ln(6) + ln_{2}(n)^{2} + ln(ln_{2}(n)^{2})) = k(ln(6) + ln_{2}(n)^{2} + 2 ln(ln_{2}(n))) = ln(n)

By Lemma 1.1.5 k ln_{1}(p_{l}) ≤ k ln_{1}(6l ln_{1}(l)) = ln(n). Hence, (p_{l})^{k} ≤ n.

Define S_{3}(k, l) = {p_{m_{1}} · . . . · p_{m_{k}} : (∀1 ≤ i ≤ k)m_{i} ≤ l&m_{i} ≺ q_{2}} If m ∈ S_{3}(k, l) then m = p_{m_{1}} · · · · · p_{m_{k}} with (∀1 ≤ i ≤ k)m_{i} ≤ l&m_{i} ≺ q_{2}

⇒ m ≤ p_{l} · . . . · p_{l} = (p_{l})^{k} ≤ n

And

m_{i} ≺ q_{2} ⇒ p_{m_{i}} ≺ p_{q_{2}} = q_{3} ⇒ m ≺ q_{3}

Hence C_{Q_{3}}(n) ≥ #S_{3}(k, l)

First we note that for n ≥ e_{4}^{e_{3}}, k is strictly increasing in n:

\frac{dk(n)}{dn} = \frac{\frac{1}{n}(ln_{2}(n)^{2} + 2 ln_{3}(n) + ln(6)) − ln(n) (2 ln_{2}(n) · \frac{1}{n ln(n)} + \frac{2}{n·ln(n)·ln_{2}(n)})}{(ln_{2}(n)^{2} + 2 ln_{3}(n) + ln(6))^{2}}

The denominator is clearly positive, and so is the enumerator:

\frac{1}{n}(ln_{2}(n)^{2} + 2 ln_{3}(n) + ln(6)) − ln(n) (2 ln_{2}(n) · \frac{1}{n ln(n)} + \frac{2}{n · ln(n) · ln_{2}(n)})

= \frac{ln_{2}(n)^{2} + 2 ln_{3}(n) + ln(6) − 2 ln_{2}(n) − \frac{2}{ln_{2}(n)}}{n}

= \frac{1}{n} · (ln_{2}(n)(ln_{2}(n) − 2) + 2 ln_{3}(n) + \frac{(ln 6) ln_{2}(n) − 2}{ln_{2}(n)}) > 0

when ln_{2}(n) > 2 and ln_{2}(n) > \frac{2}{ln(6)}. This is clearly the case since we have n ≥ e_{4}^{e_{3}}. Also \frac{ln_{2}(n)^{2}}{ln_{2}(n)^{2}+2 ln_{3}(n)+ln(6)} is increasing in n, since the inverse is decreasing in n:

n > e_{4}^{e_{3}} > e_{3} (\frac{1}{2}) ⇒ 1 − 2 ln_{3}(n) < 0

⇒ \frac{d}{dn} (1 + \frac{2 ln_{3}(n) + ln(6)}{ln_{2}(n)^{2}}) = \frac{−2 ln(6)}{n ln(n)(ln_{2}(n))^{3}} + \frac{d}{dn} \frac{2 ln_{3}(n)}{ln_{2}(n)^{2}}

< \frac{d}{dn} \frac{2 ln_{3}(n)}{ln_{2}(n)^{2}} = \frac{2 ln_{2}(n)}{n ln(n)} · (1 − 2 ln_{3}(n)) · (ln_{2}(n))^{−4} < 0

Using this last result we obtain for n > e_{4}^{e_{3}}

\sqrt{ln(l)}·k = ln_{2}(n)·\frac{ln_{1}(n)}{ln_{2}(n)^{2} + 2 ln_{3}(n) + ln(6)} = \frac{ln(n)}{ln_{2}(n)}·\frac{ln_{2}(n)^{2}}{ln_{2}(n)^{2} + 2 ln_{3}(n) + ln(6)}

≥ \frac{ln(n)}{ln_{2}(n)} · \frac{ln_{2}(e_{4}^{e_{3}})^{2}}{ln_{2}(e_{4}^{e_{3}})^{2} + 2 ln_{3}(e_{4}^{e_{3}}) + ln(6)} ≥ 0.99 · \frac{ln(n)}{ln_{2}(n)}

Since n ≥ e_{4}^{e_{3}} > 1 + exp(83^{2}) we have by lemma 2.1

#S_{3}(k, l) ≥ \frac{C_{Q_{2}}(l)^{k}}{k!}

≥ \frac{exp(1.9\sqrt{ln(l)})^{k}}{k!}

≥ exp(1.9\sqrt{ln(l)})^{k} \frac{1}{S(k)} · 0.9

(by corrolary 1.8)

= 0.9 · exp(1.9\sqrt{ln(l)} · k) exp(k − k ln(k) − ln(\sqrt{2π · k}))

Claim: k − k ln(k) − ln(\sqrt{2πk}) ≥ −1.1\sqrt{ln(l)} · k for n > e_{4}^{e_{3}} Proof claim: First note that ln(k) = ln(ln_{1}(n))−ln(ln_{2}(n)^{2} +2 ln_{3}(n)+ln(6)) ≤ ln(ln(n)) = \sqrt{ln(l)}. ( n > e_{4}^{e_{3}} so the ln’s are all> 1) Hence

\frac{k − k ln(k) − ln(\sqrt{2πk})}{\sqrt{ln(l)} · k} ≥ \frac{k − k\sqrt{ln(l)} − ln(\sqrt{2π}) − \frac{1}{2} \sqrt{ln(l)}}{\sqrt{ln(l)} · k}

= \frac{k − ln(\sqrt{2π})}{\sqrt{ln(l)} · k} − 1 − \frac{1}{2k} > −1 − \frac{1}{2k} > −1.1

since \frac{k−ln(\sqrt{2π})}{\sqrt{ln(l)}·k} > \frac{k(e_{4}^{e_{3}} )−ln(\sqrt{2π})}{\sqrt{ln(l)}·k} > 0, (where we’ve used that k is increasing in

n), and k > k(e_{4}^{e_{3}}) > 5 Having proved the claim, we continue

C_{Q_{3}}(n) ≥ 0.9 · exp(1.9\sqrt{ln(l)} · k) exp(k − k ln(k) − ln(\sqrt{2π · k})

≥ 0.9 · exp(0.8\sqrt{ln(l)} · k) ≥ exp(0.9 · 0.8 · 0.99 · \frac{ln(n)}{ln_{2}(n)}) ≥ exp (0.5\frac{ln(n)}{ln_{2}(n)})

by lemma 1.9 (n ≥ e_{4}^{e_{3}} ⇒ 0.8 · 0.99 · \frac{ln(n)}{ln_{2}(n)} > 2)

Lemma 2.3 C_{Q_{K}} (n) ≥ exp (2^{2−K}(\frac{ln(n)}{ln_{K−1}(n))}) for K ≥ 3 and n ≥ T (K) := max{e_{4}^{e_{3}}, e_{K}}

Proof Induction on K. For K = 3 the assertion is given by Lemma 2.2 with T (3) = e_{4}^{e_{3}}. Assume now that the assertion holds for some K ≥ 3. Choose an n ≥ T (K + 1) and define

k := k(n) := \frac{ln_{1}(n)}{ln_{2}(n)^{2} + 2 ln_{3}(n) + ln(6)}

l := l(n) := exp(ln_{2}(n)^{2})
S_{K+1}(k, l) = {p_{m_{1}} · . . . · p_{m_{k}} : (∀1 ≤ i ≤ k)m_{i} ≤ l&m_{i} ≺ q_{K}}

Likewise as in Lemma 2.2 we obtain p_{l}^{k} ≤ n and hence: if m ∈ S_{K+1}(k, l) then m = p_{m_{1}} · . . . · p_{m_{k}} ≤ (p_{l})^{k} ≤ n. Also m_{i} ≺ q_{K} ⇒ p_{m_{i}} ≺ p_{q_{K}} = q_{K+1} ⇒ m ≺ q_{K+1}. Hence, C_{Q_{K+1}}(n) ≥ #S_{K+1}(k, l).

If T (K) = e_{K} then e_{2}(\sqrt{ln(T (K))}) = e_{2}(\sqrt{e_{K−1}}) < e_{2}(e_{K−1}) ≤ e_{K+1} ≤ T (K +

1) ≤ n and if T (K) = e_{4}^{e_{3}} then e_{2}(\sqrt{ln(T (K))}) = e_{2}(e_{3}) ≤ e_{4}^{e_{3}} ≤ T (K + 1). So in both cases n ≥ e_{2}(\sqrt{ln(T (K)}) ⇒ l = exp(ln_{2}(n)^{2}) ≥ T (K) and thus we can apply the induction hypothesis to obtain

#S_{K+1}(k, l) ≥ \frac{C_{Q_{K}} (l)^{k}}{k!} ≥ \frac{exp(2^{2−K} \frac{ln(l)}{ln_{K−1}(l)})^{k}}{k!}

≥ exp(2^{2−K} \frac{ln(l)}{ln_{K−1}(l)} · k) · 0.9 · \frac{e^{k}}{k^{k}} \frac{1}{\sqrt{2πk}}

(by corollary 1.8)

= exp(0.9 · 2^{2−K} \frac{ln(l)}{ln_{K−1}(l)} · k − k ln(k) − ln(\sqrt{2πk})

We claim that \frac{ln_{2}(n)}{ln_{K−2}(ln_{2}(n)^{2})} is a increasing function wich tends to infinity as n → ∞: First that it is increasing in n:

\frac{d}{dn} \frac{ln_{2}(n)}{ln_{K−2}(ln_{2}(n)^{2})} =

(\frac{ln_{K−2}(ln_{2}(n)^{2})}{n ln(n)} − ln_{2}(n) · \frac{1}{ln_{2}(n)^{2} · ln(ln_{2}(n)^{2}) · . . . · ln_{K−3}(ln_{2}(n)^{2})} · \frac{2 ln_{2}(n)}{n ln(n)})·(ln_{K−2}(ln_{2}(n)^{2}))^{−2}

= (\frac{ln_{K−2}(ln_{2}(n)^{2})}{n ln(n)} − \frac{1}{n ln(n)} \frac{2}{ln(ln_{2}(n)^{2}) · . . . · ln_{K−3}(ln_{2}(n)^{2})})·(ln_{K−2}(ln_{2}(n)^{2}))^{−2}

≥ \frac{1}{n ln(n)}(ln_{K−2}(ln_{2}(n)^{2}) − 2) · (ln_{K−2}(ln_{2}(n)^{2}))^{−2} > 0

(since ln(ln_{2}(n)^{2})·. . .·ln_{K−3}(ln_{2}(n)^{2}) ≥ (ln_{K−3}(ln_{2}(n)^{2}))^{K−3} ≥ (ln_{K−3}(ln_{2}(e_{K})^{2}))^{K−3} = (ln_{K−3}(e_{K−2}^{2})^{K−3} ≥ (ln_{K−3}(e_{K−3}))^{K−3} = 1, and in the last step, n ≥ e_{K+1} ⇒ ln_{K−2}(ln_{2}(n)^{2}))^{−2} ≥ ln_{K−2}(ln_{2}(e_{K+1})^{2}))^{−2} = ln_{K−2}(e_{K−1}^{2}) > ln_{K−2}(e_{K−1}) = e > 2

The fact that it goes to infinity follows from n = e_{2}(\sqrt{e_{w−2}}) ⇒ \frac{ln_{2}(n)}{ln_{K−2}(ln_{2}(n)^{2})} = \sqrt{e_{w−2}}

Another fact we will use to proof the lemma is the following: ln_{K−2}(ln_{2}(n)^{2}) ≤ 1.1 · ln_{K}(n). We proof it by induction on K: K = 4 : ln_{2}(ln_{2}(n)^{2}) = ln(2) + ln_{4}(n) ≤ 1, 1 · ln_{K}(n) since n ≥ e_{4}^{e_{3}} > e_{4}(10 ln(2)) implies ln(2) ≤ 0.1 ln_{4}(n). K > 4 : Note that n ≥ T (K + 1) implies ln_{(K+1)−2}(ln_{2}(n)^{2}) > ln_{K−1}(ln_{2}(n)) = ln_{K+1}(n) > 1. So we obtain

ln_{(K+1)−2}(ln_{2}(n)^{2}) = ln(ln_{K−2}(ln_{2}(n)^{2})) ≤ ln(1.1 · ln_{K}(n))

= ln(1.1) + ln_{K+1}(n) ≤ 1.1 · ln_{K+1}(n)

since n ≥ e_{K+1} ≥ e_{K+1}(10 ln(1, 1)) implies ln(1.1) ≤ 0.1 ln_{K+1}(n). Next we show that −k ln(k) − ln(\sqrt{2πk}) ≥ −0.2 · 2^{2−K} \frac{ln(l)}{ln_{K−1}(l)} · k Observe that since n ≥ e_{K+1}

0.1 · 2^{2−K} · \frac{ln_{2}(n)}{ln_{K−2}(ln_{2}(n)^{2})} ≥ 0.1 · 2^{2−K} · \frac{ln_{2}(e_{K+1})}{ln_{K−2}(ln_{2}(e_{K+1})^{2})}

≥ 0.1 · 2^{2−K} · \frac{ln_{2}(e_{K+1})}{1.1 ln_{K}(e_{K+1})} = \frac{2^{2−K}}{11e} · e_{K−1} > 1

⇒ ln_{2}(n) < 0.1 · 2^{2−K} · \frac{ln_{2}(n)^{2}}{ln_{K−2}(ln_{2}(n)^{2})} = \frac{ln(l)}{ln_{K−1}(l)}

⇒ ln(k) = ln_{2}(n) − ln(ln_{2}(n)^{2} + 2 ln_{3}(n) + ln(6)) < 0.1 · 2^{2−K} · \frac{ln(l)}{ln_{K−1}(l)} (since ln(ln_{2}(n)^{2} + 2 ln_{3}(n) + ln(6)) > ln(ln_{2}(e_{4}^{e_{3}})^{2} + 2 ln_{3}(e_{4}^{e_{3}}) + ln(6)) > 0

⇒ −k ln(k) > −0.1 · 2^{2−K} · \frac{ln(l)}{ln_{K−1}(l)} · k

And

− ln(\sqrt{2πk}) = − ln(\sqrt{2π}) − \frac{1}{2} ln(k) > − ln(k)

(n ≥ e_{4}^{e_{3}} ⇒ k > 2π ⇒ ln(\sqrt{2π}) < \frac{1}{2} ln(k))

> −0.1 · 2^{2−K} · \frac{ln(l)}{ln_{K−1}(l)} > −0.1 · 2^{2−K} · \frac{ln(l)}{ln_{K−1}(l)} · k

Hence we have −k ln(k) − ln(\sqrt{2πk}) ≥ −0.2 · 2^{2−K} \frac{ln(l)}{ln_{K−1}(l)} · k Therefore

0.9 · exp(2^{2−K} \frac{ln(l)}{ln_{K−1}(l)} · k − k ln(k) − ln(\sqrt{2πk}))

≥ 0.9 · exp(0.8 · 2^{2−K} \frac{ln(l)}{ln_{K−1}(l)} · k)

Note that since \frac{ln_{2}(n)^{2}}{ln_{2}(n)^{2}+2 ln_{3}(n)+ln(6)} is increasing in n (shown in the proof of Lemma 2.2), we have

\frac{ln(l)}{ln_{K−1}(l)} · k = \frac{ln_{2}(n)^{2}}{ln_{K−2}(ln_{2}(n)^{2})} · k = \frac{ln(n)}{ln_{K−2}(ln_{2}(n)^{2})} · \frac{ln_{2}(n)^{2}}{ln_{2}(n)^{2} + 2 ln_{3}(n) + ln(6)}

≥ \frac{ln(n)}{ln_{K−2}(ln_{2}(n)^{2})} · \frac{ln_{2}(e_{4}^{e_{3}})^{2}}{ln_{2}(e_{4}^{e_{3}})^{2} + 2 ln_{3}(e_{4}^{e_{3}}) + ln(6)} ≥ \frac{ln(n)}{ln_{K−2}(ln_{2}(n)^{2})} · 0.99

≥ \frac{ln(n)}{ln_{K}(n)} · 0.99 · \frac{1}{1.1}

Concluding:

C_{Q_{K+1}}(n) ≥ 0.9 · exp(0.8 · 2^{2−K} \frac{ln(l)}{ln_{K−1}(l)} · k)

> 0.9 · exp(0.8 · 0.99 · \frac{1}{1.1} · 2^{2−K} \frac{ln(n)}{ln_{K}(n)})

> exp(0.9 · 0.8 · 0.99 · \frac{1}{1.1} · 2^{2−K} \frac{ln(n)}{ln_{K}(n)})

> exp(2^{2−(K+1)} \frac{ln(n)}{ln_{(K+1)−1}(n)})

(At the end we’ve used Lemma 1.9. We need to check the condition that

0.8 · 0.99 · \frac{1}{1.1} · 2^{2−K} \frac{ln(n)}{ln_{K}(n)} > 2

This is clearly true since n ≥ e_{K+1}

2.2 Upper bounds for C_{Q_{K}}

In this paragraph we proof the following upperbounds for C_{Q_{K}}: For all ϵ > 0 there exists an N such that for all n > N we have C_{Q_{2}}(n) ≤

exp ((π\sqrt{\frac{2}{3 ln(2)}} + ϵ) \sqrt{ln(n)})

And for K ≥ 3 we prove that for large enough n, C_{Q_{K}} (n) ≤ exp(48(\frac{ln(n)}{ln_{K−1}(n)}))

We make use of the fundamental identity of multiplicative number systems. First we introduce the following definitions:

γ_{K}(n) := #{m ≺ q_{K} : m = n}

Γ_{K}(z) := ∑_{l=1}^{∞} γ_{K}(l)l^{−z}

π_{K}(n) := #{p ≺ q_{K} : p = n&p ∈ P }

Π_{K}(z) := ∑_{l=2}^{∞} π_{K}(l)l^{−z}

Then C_{Q_{K}} (n) = ∑_{i=1}^{n} γ_{K}(i)

Lemma 2.4 Γ_{2}(x) ≤ \frac{1}{1−2^{−x}} exp(\frac{π^{2}}{6} \frac{2^{−x}}{1−2^{−x}}) for x ∈]0, ∞[ Proof By the fundamental identity of multiplicative number systems

Γ_{2}(x) = ∑_{l=1}^{∞} γ_{2}(l)l^{−x} = ∏_{k=2}^{∞} \frac{1}{(1 − k^{−x})^{π_{2}(k)}}

We have π_{2}(k) = 1 ⇔ #{p ⪯ q_{2} : p = k, p ∈ P} = 1 ⇔ k ⪯ q_{2}&k ∈ P ⇔ k = p_{2^{l}} for some l ≥ 0 where the last equivalence is easily seen following definition of the relation ⪯ : k ∈ P ⇔ k = p_{j} for some j. And p_{j} ⪯ q_{2} = p_{3} ⇒ j ⪯ 3 = p_{2} ⇒ j = 2^{l} for some l.

So k = p_{2^{l}} ⇒ π_{2}(k) = 1 and k ≠ p_{2^{l}} ⇒ π_{2}(k) = 0 Thus

Γ_{2}(x) = ∏_{l=0}^{∞} \frac{1}{1 − (p_{2^{l}})^{−x}} = \frac{1}{1 − 2^{−x}} ∏_{l=1}^{∞} \frac{1}{1 − (p_{2^{l}})^{−x}}

We have

∀k : p_{k} > k ⇒ ∀l : p_{2^{l}} > 2^{l} ⇒ ∀l : (p_{2^{l}})^{−x} < 2^{−lx} ⇒

∀l : 1 − (p_{2^{l}})^{−x} > 1 − 2^{−lx} ⇒ ∀l : \frac{1}{1 − (p_{2^{l}})^{−x}} < \frac{1}{1 − 2^{−lx}} ⇒

Γ_{2}(x) ≤ \frac{1}{1 − 2^{−x}} ∏_{l=1}^{∞} \frac{1}{1 − 2^{−lx}}

Let Γ′_{2}(x) := ∏_{l=1}^{∞} \frac{1}{1−2^{−lx}} = exp(ln(∏_{l=1}^{∞} \frac{1}{1−2^{−lx}})) = exp(∑_{l=1}^{∞} ln(\frac{1}{1−2^{−lx}})) (this is well defined since l, x > 0 ⇒ 1 − 2^{−lx} > 0

By Lemma 1.10

ln (\frac{1}{1 − 2^{−lx}} ) = ∑_{m=1}^{∞} \frac{2^{−lxm}}{m}

And thus

Γ′_{2}(x) = exp (∑_{l=1}^{∞} ln(\frac{1}{1 − 2^{−lx}})) = exp (∑_{l=1}^{∞} ∑_{m=1}^{∞} \frac{2^{−lxm}}{m} ) = exp ( ∑_{m=1}^{∞} ∑_{l=1}^{∞} \frac{2^{−lxm}}{m} )

(since all terms are ≥ 0).

= exp ( ∑_{m=1}^{∞} \frac{1}{m} ∑_{l=1}^{∞}(2^{−mx})^{l}) = exp ( ∑_{m=1}^{∞} \frac{1}{m} \frac{2^{−mx}}{1 − 2^{−mx}} )

by the geometric series formula ∑_{l=1}^{∞} a^{l} = \frac{a}{1−a}. (Note that 2^{−mx} < 1∀m ≥ 1, x ≥ 0)

≤ exp ( ∑_{m=1}^{∞} \frac{1}{m} \frac{1}{m} \frac{2^{−x}}{1 − 2^{−x}} )

(by lemma 1.6)

≤ exp (\frac{π^{2}}{6} \frac{2^{−x}}{1 − 2^{−x}} )

(since ∑_{m=1}^{∞} \frac{1}{m^{2}} = \frac{π^{2}}{6} ) Hence,

Γ_{2}(x) ≤ \frac{1}{1 − 2^{−x}} Γ′_{2}(x) ≤ \frac{1}{1 − 2^{−x}} exp (\frac{π^{2}}{6} \frac{2^{−x}}{1 − 2^{−x}} )

Lemma 2.5 Let ϵ := 0.6, U(K) := 2 + (ϵ)^{0} + … + (ϵ)^{K−2} = \frac{3−2ϵ−ϵ^{K−1}}{1−ϵ}. Then for all K ≥ 2, Γ_{K}(x) ≤ e_{K−1}(U(K)\frac{2^{−x}}{1−2^{−x}})

Proof By induction on K. K=2: Since ln(\frac{1}{1−2^{−x}}) = ∑_{m=1}^{∞} \frac{(2^{−x})^{m}}{m} < ∑_{m=1}^{∞}(2^{−x})^{m} = \frac{2^{−x}}{1−2^{−x}}, we have for all x ∈]0, ∞[, using Lemma 2.4:

Γ_{2}(x) ≤ \frac{1}{1 − 2^{−x}} exp(\frac{π^{2}}{6} \frac{2^{−x}}{1 − 2^{−x}}) = exp(ln(\frac{1}{1 − 2^{−x}})) exp(\frac{π^{2}}{6} \frac{2^{−x}}{1 − 2^{−x}})

< exp(\frac{2^{−x}}{1 − 2^{−x}}) exp(\frac{π^{2}}{6} \frac{2^{−x}}{1 − 2^{−x}}) = exp((1 + \frac{π^{2}}{6} )\frac{2^{−x}}{1 − 2^{−x}}) < exp(3\frac{2^{−x}}{1 − 2^{−x}})

So we can take U(2) = 3 = 2 + ϵ^{0}

Now assume Γ_{K}(x) ≤ e_{K−1}(U(K)\frac{2^{−x}}{1−2^{−x}}) for all x ∈]0, ∞[. By the fundamental identity:

Γ_{K+1}(x) = ∑_{l=1}^{∞} γ_{K+1}(l)l^{−x} = ∏_{k=2}^{∞} \frac{1}{(1 − k^{−x})^{π_{K+1}(k)}} =

exp (ln (∏_{k=2}^{∞} \frac{1}{(1 − k^{−x})^{π_{K+1}(k)}} )) = exp (∑_{k=2}^{∞} ln (\frac{1}{(1 − k^{−x})^{π_{K+1}(k)}} )) =

exp (∑_{k=2}^{∞} π_{K+1}(k) ln (\frac{1}{(1 − k^{−x})})) = exp (∑_{k=2}^{∞} π_{K+1}(k) ∑_{m=1}^{∞} \frac{k^{−mx}}{m} )

(by lemma 1.10)

= exp ( ∑_{m=1}^{∞} \frac{1}{m} ∑_{k=2}^{∞} π_{K+1}(k)k^{−mx}) = exp ( ∑_{m=1}^{∞} \frac{1}{m}Π_{k+1}(mx))

by definition of Π

Claim: Π_{K+1}(x) ≤ 1.5^{−x}Γ_{K}(x) for all x ∈ (0, ∞) Proof of claim: π_{K+1}(l) = 1 ⇔ (∃m)l = p_{m} with p_{m} ≺ q_{K+1} = p_{q_{K}} ⇔ (∃m)l = p_{m} with m ≺ q_{K}. With Lemma 1.1.7: Π_{K+1}(x) = ∑_{m≺q_{K}} p_{m}^{−x} ≤ ∑_{m≺q_{K}} (1.5m)^{−x} = 1.5^{−x} ∑_{m≺q_{K}} m^{−x} = 1.5^{−x}Γ_{K}(x)

So we have using induction hypothesis

Γ_{K+1}(x) ≤ exp ( ∑_{m=1}^{∞} \frac{1}{m}Π_{k+1}(mx))

≤ exp ( ∑_{m=1}^{∞} \frac{1}{m}1.5^{−mx}Γ_{k}(mx)) ≤ exp ( ∑_{m=1}^{∞} \frac{1}{m}1.5^{−mx}e_{K−1} (U(K)\frac{2^{−mx}}{1 − 2^{−mx}} ))

≤ exp ( ∑_{m=1}^{∞} \frac{1}{m}(1.5^{−x})^{m}e_{K−1} (U(K)\frac{1}{m} \frac{2^{−x}}{1 − 2^{−x}} ))

(by lemma 1.10)

≤ exp (ln (\frac{1}{1 − 1.5^{−x}} ) e_{K−1} (U(K)\frac{2^{−x}}{1 − 2^{−x}} ))

In order to get our assertion, we need

exp (ln (\frac{1}{1 − 1.5^{−x}} ) e_{K−1} (U(K)\frac{2^{−x}}{1 − 2^{−x}} )) ≤ exp (e_{K−1} (U(K + 1)\frac{2^{−x}}{1 − 2^{−x}} ))

so it suffices to show

ln (\frac{1}{1 − 1.5^{−x}} ) e_{K−1} (U(K)\frac{2^{−x}}{1 − 2^{−x}} ) ≤ e_{K−1} (U(K + 1)\frac{2^{−x}}{1 − 2^{−x}} )

Write h(x) := \frac{2^{−x}}{1−2^{−x}}. With δ := 0.5 we have ln(\frac{1}{1−1.5^{−x}}) ≤ h(x) + δ for all x ∈ (0, ∞) (lemma 1.11)

Since h is a bijection (0, ∞) → (0, ∞), writing y = h(x), it suffices to show that for all y > 0 and K ≥ 1:

(y + δ)e_{K} (\frac{3 − 2ϵ − ϵ^{K}}{1 − ϵ} y) ≤ e_{K} (\frac{3 − 2ϵ − ϵ^{K+1}}{1 − ϵ} y)

We prove this with induction on K Let K = 1 ϵ = 0.6 and δ = 0.5 ⇒ ϵ > max_{y>0} \frac{ln(y+δ)}{y}

⇒ (y+δ) exp(\frac{3 − 2ϵ − ϵ^{1}}{1 − ϵ} y) = (y+δ) exp(3y) ≤ exp((3+ϵ)y) = exp(\frac{3 − 2ϵ − ϵ^{2}}{1 − ϵ} y)

Now suppose K > 1 and suppose that for all y > 0,

(y + δ)e_{K} (\frac{3 − 2ϵ − ϵ^{K}}{1 − ϵ} y) ≤ e_{K} (\frac{3 − 2ϵ − ϵ^{K+1}}{1 − ϵ} y)

For 0 < y < 1 − δ we then have immediately

(y+δ)e_{K+1} (\frac{3 − 2ϵ − ϵ^{K+1}}{1 − ϵ} y) ≤ e_{K+1} (\frac{3 − 2ϵ − ϵ^{K+1}}{1 − ϵ} y) ≤ e_{K+1} (\frac{3 − 2ϵ − ϵ^{K+2}}{1 − ϵ} y)

Suppose 1 − δ < y Put

y′ := \frac{1 − ϵ}{3 − 2ϵ − ϵ^{K+1}} exp(\frac{3 − 2ϵ − ϵ^{K+2}}{1 − ϵ} y)

Then

y′ ≥ \frac{1 − ϵ}{3 − 2ϵ − ϵ^{K+1}} exp(\frac{3 − 2ϵ − ϵ^{K+1}}{1 − ϵ} y) ≥ y

(Since exp(αy) ≥ αy for y > 0, α > 0 For ϵ = 0.6 and δ = 0.5 we have that

y > 1 − δ > \frac{1}{−ϵ^{K+1}} ln(\frac{3 − 2ϵ − ϵ^{K}}{3 − 2ϵ − ϵ^{K+1}} )

Hence

−ϵ^{K+1}y = (\frac{3 − 2ϵ − ϵ^{K+1}}{1 − ϵ} − \frac{3 − 2ϵ − ϵ^{K+2}}{1 − ϵ} y) y < ln(\frac{3 − 2ϵ − ϵ^{K}}{3 − 2ϵ − ϵ^{K+1}} )

⇒ exp (\frac{3 − 2ϵ − ϵ^{K+1}}{1 − ϵ} y) < \frac{3 − 2ϵ − ϵ^{K}}{3 − 2ϵ − ϵ^{K+1}} exp (\frac{3 − 2ϵ − ϵ^{K+2}}{1 − ϵ} y)

⇒ e_{K+1} (\frac{3 − 2ϵ − ϵ^{K+1}}{1 − ϵ} y) < e_{K}(\frac{3 − 2ϵ − ϵ^{K}}{3 − 2ϵ − ϵ^{K+1}} exp (\frac{3 − 2ϵ − ϵ^{K+2}}{1 − ϵ} y))

= e_{K}(\frac{3 − 2ϵ − ϵ^{K}}{1 − ϵ} y′)

And thus

(y + δ)e_{K+1} (\frac{3 − 2ϵ − ϵ^{K+1}}{1 − ϵ} y) ≤ (y′ + δ)e_{K}(\frac{3 − 2ϵ − ϵ^{K}}{1 − ϵ} y′)

≤ e_{K}(\frac{3 − 2ϵ − ϵ^{K+1}}{1 − ϵ} y′)

(by induction hypothesis)

≤ e_{K+1}(\frac{3 − 2ϵ − ϵ^{K+2}}{1 − ϵ} y)

(by definition of y′)

Remark We have chosen ϵ = 0.6 and δ = 0.5. With these values we get an upperbound: for all K, U(K) ≤ U := 4.5 This value δ can in fact be chosen lower, ∼ 0.26, and this ϵ we can vary, as long as the following conditions are fullfilled:

⇒ ϵ > max_{y>0} \frac{ln(y + δ)}{y}

and

1 − δ > \frac{1}{−ϵ^{K+1}} ln(\frac{3 − 2ϵ − ϵ^{K}}{3 − 2ϵ − ϵ^{K+1}} )

In this way we could obtain a lower U The upperbound on U(K) will be useful in the proof on upperbounds of C_{Q_{K}}

Asymptotic upperbound for Γ_{K} For the behaviour of the upperbound of Γ_{K}(x) for x → 0, we have the following:

∀ϵ_{2}, …, ϵ_{K} > 0∃δ > 0 : 0 < x < δ ⇒ Γ_{K}(x) ≤ e_{K−1}((ϵ_{2} + … + ϵ_{K})\frac{2^{−x}}{1 − 2^{−x}})

Proof Again by induction on K. For K = 2 we first claim

∀ϵ > 0∃δ > 0 : 0 < x < δ ⇒ ln(\frac{1}{1 − 2^{−x}}) < ϵ · \frac{2^{−x}}{1 − 2^{−x}}

Proof of this claim: It is clear that ∀ϵ > 0∃δ_{ϵ} > 0 s.t. α > δ_{ϵ} ⇒ \frac{α}{exp(α)−1} ≤ ϵ i.e., α ≤ ϵ(exp(α)−1) =

ϵ · \frac{1−exp(−α)}{exp(−α)}. Let ϵ > 0, write α = ln(\frac{1}{1−2^{−x}}). Then for all 0 < x < δ := (ln(2))^{−1} · ln(\frac{1}{1−exp(−δ_{ϵ})})

x < (ln(2))^{−1} · ln(\frac{1}{1 − exp(−δ_{ϵ})}) ⇒ 2^{x} < \frac{1}{1 − exp(−δ_{ϵ})}

⇒ 2^{−x} > 1 − exp(−δ_{ϵ}) ⇒ 1 − exp(−α) > 1 − exp(−δ_{ϵ}) ⇒ α > δ_{ϵ}

and thus

α ≤ ϵ · \frac{1 − exp(−α)}{exp(−α)} ⇒ ln(\frac{1}{1 − 2^{−x}}) < ϵ · \frac{2^{−x}}{1 − 2^{−x}}

Using the claim just proved, we get

Γ_{2}(x) ≤ \frac{1}{1 − 2^{−x}} exp(\frac{π^{2}}{6} \frac{2^{−x}}{1 − 2^{−x}}) = exp(ln(\frac{1}{1 − 2^{−x}})) exp(\frac{π^{2}}{6} \frac{2^{−x}}{1 − 2^{−x}})

< exp((\frac{π^{2}}{6} + ϵ)\frac{2^{−x}}{1 − 2^{−x}})

for 0 < x < δ Now let K > 2. With the same reasoning as in the preceding lemma, we obtain that (∀ϵ_{2}, …, ϵ_{K} > 0)∃δ > 0 : 0 < x < δ ⇒

Γ_{K+1}(x) ≤ exp (ln (\frac{1}{1 − 1.5^{−x}} ) e_{K−1} (U(K)\frac{2^{−x}}{1 − 2^{−x}} ))

with U(K) = \frac{π^{2}}{6} + ϵ_{2} + … + ϵ_{K}. There is a δ_{ϵ} > 0 s.t. 0 < x < δ_{ϵ} implies

ln (\frac{1}{1 − 1.5^{−x}} ) < ϵ_{K+1} \frac{2^{−x}}{1 − 2^{−x}}

Thus

Γ_{K+1} ≤ exp (ln (\frac{1}{1 − 1.5^{−x}} ) e_{K−1} (U(K)\frac{2^{−x}}{1 − 2^{−x}} )) ≤

e_{K} ((U(K) + ϵ_{K+1})\frac{2^{−x}}{1 − 2^{−x}} )

Lemma 2.6 For all ϵ > 0 there exists an N such that for all n > N we have C_{Q_{2}}(n) ≤ exp ((π\sqrt{\frac{2}{3 ln(2)}} + ϵ) \sqrt{ln(n)})

Proof For all x ∈ (0, ∞) we have

C_{Q_{2}}(n) = #{m ∈ N : m ≺ q_{2}, m ≤ n} = ∑_{l=1}^{n} #{m ∈ N : m ≺ q_{2}, m = l}

= ∑_{l=1}^{n} γ_{2}(l) ≤ ∑_{l=1}^{n} γ_{2}(l) (\frac{n}{l})^{x} ≤ n^{x} ∑_{l=1}^{n} γ_{2}(l)l^{−x} = n^{x}Γ_{2}(x)

Thus

ln(C_{Q_{2}}(n)) ≤ ln(n^{x}Γ_{2}(x)) = x ln(n) + ln(Γ_{2}(x))

If n = 1 then C_{Q_{2}}(1) = 1 ≤ exp(V · \sqrt{ln(n)}) for all V Assume n ≥ 2. Put

α := α(n) := \sqrt{ln(n)}
β := (1 + π^{2}/6) ln(2)
y := ^{\frac{2α^{2}+β−\sqrt{4(β−ln(2))α^{2}+β^{2}}}{2α^{2}+2 ln(2)}}
x := x(n) := \frac{− ln(y)}{ln(2)}

Note that 2^{−x} = y. Using this x we get with lemma 2.4

ln(C_{Q_{2}}(n)) ≤ x ln(n) + ln(Γ_{2}(x)) ≤ x ln(n) − ln(1 − 2^{−x}) + \frac{π^{2}}{6} \frac{2^{−x}}{1 − 2^{−x}}

= \frac{− ln(y)}{ln(2)}α^{2} − ln(1 − y) + \frac{π^{2}}{6} \frac{y}{1 − y}

Now

lim_{α→∞} y = lim_{α→∞} \frac{2α^{2} + β − \sqrt{4(β − ln(2))α^{2} + β^{2}}}{2α^{2} + 2 ln(2)}

= lim_{α→∞} \frac{2α^{2} − \sqrt{4(β − ln(2))}α}{2α^{2}} = lim_{α→∞} 1 − \frac{\sqrt{β − ln(2)}}{α}

For convenience, write c := \sqrt{β − ln(2)}

lim_{α→∞} \frac{− ln(y)}{ln(2)}α^{2} − ln(1 − y) + \frac{π^{2}}{6} \frac{y}{1 − y} =

lim_{α→∞} [\frac{− ln(1 − \frac{c}{α})}{ln(2)}α − \frac{ln(\frac{c}{α})}{α} + \frac{π^{2}}{6} \frac{1 − \frac{c}{α}}{\frac{c}{α}} \frac{1}{α}] α  (2)

lim_{α→∞} \frac{− ln(1 − \frac{c}{α})}{ln(2)}α = \frac{c}{ln(2)}

lim_{α→∞} −\frac{ln(\frac{c}{α})}{α} = lim_{α→∞} −\frac{ln(c)}{α} − \frac{ln(α)}{α} = 0

lim_{α→∞} \frac{π^{2}}{6} \frac{1 − \frac{c}{α}}{\frac{c}{α}} \frac{1}{α} = lim_{α→∞} \frac{π^{2}}{6} \frac{α − c}{c} \frac{a}{α} = \frac{1}{c} \frac{π^{2}}{6}

And thus if α → ∞ then

(2) → [\frac{c}{ln(2)} + \frac{π^{2}}{6} \frac{1}{c}]α = π\sqrt{\frac{2}{3 ln(2)}}α

Thus, if ∀ϵ > 0∃N∀n > N

ln(C_{Q_{2}}(n)) ≤ (π\sqrt{\frac{2}{3 ln(2)}} + ϵ) \sqrt{ln(n)}

Lemma 2.7 If n < e_{K−1}(1 + 10 ln(2)) then C_{Q_{K}} (n) ≤ exp(24\frac{ln(n)}{ln_{K−1}(n)} + C̃) where C̃ is a positive constant, and K ≥ 3. If n ≥ e_{K−1}(1 + 10 ln(2)) then C_{Q_{K}} (n) ≤ exp(48(\frac{ln(n)}{ln_{K−1}(n)})) for K ≥ 3

Proof For n = 1, 2 the assertion is true. Now assume n ≥ 3

C_{Q_{K}} (n) = ∑_{l=1}^{n} γ_{K}(l) ≤ ∑_{l=1}^{n} γ_{K}(l)(\frac{n}{l})^{x} ≤ n^{x} ∑_{l=1}^{n} γ_{K}(l)l^{−x} = n^{x}Γ_{K}(x)

Thus

ln(C_{Q_{K}} (n)) ≤ ln(n^{x}Γ_{K}(x)) = x ln(n) + ln(Γ_{K}(x))

≤ x ln(n) + e_{K−2}(U(K)\frac{1}{1 − 2^{−x}})

(by lemma 2.5). This holds for all K ≥ 3 and x ∈ (0, ∞).

For chosen K, define c := (1 + 2U(K)) ln(2) D := \frac{U(K)}{c} C := ⌈\frac{c+1}{ln(2)} · ln(c + 1)⌉ C̃ := e_{K−2}(\frac{U(K)}{1−2^{− \frac{C}{c+1}}} ) and choose x := x(n) := \frac{C}{ln_{K−1}(n)} Case 1 3 ≤ n ≤ e_{K−1}(c + 1) Note that

n ≤ e_{K−1}(c+1) ⇒ x = \frac{C}{ln_{K−1}(n)} ≥ \frac{C}{ln_{K−1}(e_{K−1}(c + 1))} = \frac{C}{c + 1} ⇒ \frac{1}{1 − 2^{−x}} ≤ \frac{1}{1 − 2^{− \frac{C}{c+1}}}

hence

ln(C_{Q_{K}} (n)) ≤ x ln(n) + e_{K−2} (U(K)\frac{1}{1 − 2^{−x}} )

≤ \frac{C ln(n)}{ln_{K−1}(n)} + e_{K−2} (U(K)\frac{1}{1 − 2^{− \frac{C}{c+1}}} ) ≤ C \frac{ln(n)}{ln_{K−1}(n)} + C̃

Since U(K) ≤ U = 4.5, C ≤ 24, and hence

C_{Q_{K}} (n)) ≤ exp(24\frac{ln(n)}{ln_{K−1}(n)} + C̃)

Case 2 n ≥ e_{K−1}(c + 1) Claim 1: If n ≥ e_{K−1}(c + 1) then \frac{U(K)}{1−2^{−x}} ≤ D ln_{K−1}(n) Proof claim 1

C ≥ \frac{c + 1}{ln(2)} · ln(c + 1) ⇒ \frac{C}{c + 1} ln(2) ≥ ln(c + 1) ⇒ \frac{−C}{c + 1} ln(2) ≤ − ln(c + 1)

⇒ 2^{\frac{−C}{c+1}} ≤ \frac{1}{c + 1} ⇒ 1 − 2^{\frac{−C}{c+1}} ≥ 1 − \frac{1}{c + 1} = \frac{c}{c + 1} ⇒ (c + 1)(1 − 2^{\frac{−C}{c+1}} ) ≥ c

We have n ≥ e_{K−1}(c + 1) ⇒ ln_{K−1}(n) ≥ c + 1 and thus ln_{K−1}(n) · (1 − 2^{\frac{−C}{ln_{K−1}(n)}} ) ≥ (c + 1)(1 − 2^{\frac{−C}{c+1}} ) ≥ c

⇒ \frac{1}{ln_{K−1}(n)}·\frac{1}{1 − 2^{\frac{−C}{ln_{K−1}(n)}}} ≤ \frac{1}{c} ⇒ \frac{U(K)}{C} \frac{\frac{C}{ln_{K−1}(n)}}{1 − 2^{− \frac{C}{ln_{K−1}(n)}}} ln_{K−1}(n) ≤ \frac{U(K)}{c} ln_{K−1}(n)

⇒ \frac{U(K)}{1 − 2^{−x}} ≤ D ln_{K−1}(n)

Claim 2: e_{K−2}(D ln_{K−1}(n)) ≤ ln(n)^{D} Proof claim 2 Since U(K) ≥ 1.5, 1 > D = \frac{U(K)}{c} = \frac{U(K)}{1+2U(K)} \frac{1}{ln(2)} ≥ \frac{3}{7 ln(2)} > \frac{1}{2}. n ≥ e_{K−1}(c + 1) > e_{K−1}(\frac{1}{D}) First we show that the assertion is true for n = e_{K−1}(\frac{1}{D}). And then we show by taking derivative w.r.t. n on both sides of the equation, that it holds for all n ≥ e_{K−1}(\frac{1}{D}). So let n = e_{K−1}(\frac{1}{D}). Then

e_{K−2}(D ln_{K−1}(n)) = e_{K−2} = (eK−2^{\frac{1}{D}})^{D} ≤ (e_{K−2} (\frac{1}{D} ))^{D} = ln(n)^{D}

Now we look at the derivatives w.r.t. n. Using D < 1 we get with induction:

\frac{d}{dn}e_{K−2}(D ln_{K−1}(n)) ≤ \frac{D}{n}

For K = 3:

\frac{d}{dn}e_{K−2}(D ln_{K−1}(n)) = exp(D ln_{2}(n)) · \frac{d}{dn}D ln_{2}(n)

= exp(D ln_{2}(n)) · D · \frac{1}{n ln(n)} < ln(n) · D · \frac{1}{n ln(n)} = \frac{D}{n}

For K > 3:

\frac{d}{dn}e_{K−2}(D ln_{K−1}(n)) = e_{K−2}(D ln_{K−1}(n)) · \frac{d}{dn}e_{K−3}(D ln_{K−1}(n))

= e_{K−2}(D ln_{K−1}(n)) · e_{K−3}(D ln_{K−1}(n)) · \frac{d}{dn}e_{K−4}(D ln_{K−1}(n)) =

e_{K−2}(D ln_{K−1}(n)) · e_{K−3}(D ln_{K−1}(n)) … e(D ln_{K−1}(n)) · \frac{d}{dn}D ln_{K−1}(n))

≤ ln_{1}(n) · ln_{2}(n) · . . . · ln_{K−2}(n) · D · \frac{1}{n · ln_{1}(n) · ln_{2}(n) . . . · ln_{K−2}(n)}

= \frac{D}{n}

Hence

\frac{d}{dn}e_{K−2}(D ln_{K−1}(n)) ≤ \frac{D}{n} ≤ \frac{D(ln(n))^{D−1}}{n} = \frac{d}{dn}(ln(n))^{D}

And thus the assertion holds for all n ≥ e_{K−1}(\frac{1}{D}), in particular for all n ≥ e_{K−1}(c + 1).

Claim 3: ln(n)^{D} < \frac{C ln(n)}{ln_{K−1}(n)} Proof claim 3

n > 2 ⇒ ln(n) > (\frac{1}{1.62})^{\frac{1}{0.27}} ⇒ 1.62(ln(n))^{0.27} > 1

⇒ 1.62\frac{(ln(n))^{0.27}}{n ln(n)} > \frac{1}{n ln(n)} ⇒ 1.62\frac{(ln(n))^{−0.73}}{n} > \frac{1}{n ln(n)}

⇒ \frac{d}{dn}6(ln(n))^{0.27} > \frac{d}{dn} ln(ln(n))

This, together with 6(ln(2))^{0.27} > ln(ln(2)) gives

(∀n ≥ 2) 6(ln(n))^{0.27} > ln(ln(n))

Furthermore

c = (1 + 2U(K)) ln(2) > 2U(K) ln(2)

⇒ C = ⌈\frac{c + 1}{ln(2)} · ln(c + 1)⌉ > \frac{2U(K) ln(2) + 1}{ln(2)} ln((2U(K) ln(2)) + 1) > (2U(K)+\frac{1}{ln(2)}) ln(2U(K) ln(2)) > 2U(K) ln(2U(K) ln(2)) > 2U(K) ln(U(K)) Hence

U(K) ≥ 3 ⇒ C ≥ 2 · 3 · ln(3) > 6 ⇒ C(ln(n))^{0.27} > 6(ln(n))^{0.27} Notice

D = \frac{U(K)}{c} < \frac{U(K)}{2U(K) ln(2)} = \frac{1}{2 ln(2)}

⇒ 1 − D > 1 − \frac{1}{2 ln(2)} > 0.27

⇒ C(ln(n))^{1−D} > C(ln(n))^{0.27} > 6(ln(n))^{0.27} > ln(ln(n))

Hence

\frac{C(ln(n))^{1−D}}{ln(ln(n))} > 1 ⇒ \frac{C ln(n)}{ln(ln(n))} > (ln(n))^{D}

Now for all K ≥ 3 : ln_{K−1}(n) ≤ ln_{2}(n), hence

\frac{C ln(n)}{ln_{K−1}(n)} ≥ \frac{C ln(n)}{ln(ln(n))} > (ln(n))^{D}

Combining claim 1, 2, 3 we get, for n ≥ e_{K−1}(c + 1)

ln(C_{Q_{K}} (n)) ≤ x ln(n) + e_{K−2}(U(K)\frac{1}{1 − 2^{−x}})

≤ \frac{C ln(n)}{ln_{K−1}(n)} + e_{K−2}(D ln_{K−1}(n))

≤ \frac{C ln(n)}{ln_{K−1}(n)} + (ln(n))^{D} ≤ \frac{C ln(n)}{ln_{K−1}(n)} + \frac{C ln(n)}{ln_{K−1}(n)}

≤ 48\frac{ln(n)}{ln_{K−1}(n)}

since U(K) ≤ U = 4.5 implying 2C ≤ 48

Asymptotic upperbound for C_{Q_{K}}, K ≥ 3 For the behaviour of the upperbound of C_{Q_{K}} (n), K ≥ 3 for n → ∞, we have the following:

∀δ > 0∃N∀n ≥ N C_{Q_{K}} (n) ≤ exp( \frac{\frac{π^{2}}{6} + ϵ_{K} + δ}{ln(2)} \frac{ln(n)}{ln_{K−1}(n)})

where U_{K} = \frac{π^{2}}{6} + ϵ_{K} for an ϵ_{K} > 0. Proof: C := \frac{U(K)+δ}{ln(2)} c := C ln(2) − \frac{δ}{2} D := \frac{U(K)}{c} x := x(n) := \frac{C}{ln_{K−1}(n)}

Claim 1: If n large enough, then \frac{U(K)}{1−2^{−x}} ≤ D ln_{K−1}(n) Proof claim 1

lim_{y→∞} y · (1 − (2^{−C})^{\frac{1}{y}}) = lim_{y→0} \frac{(1 − (2^{−C})^{y})}{y} = − ln(2^{−C}) = C ln(2)

and y · (1 − (2^{−C})^{\frac{1}{y}}) increases in y. Hence, for y large enough,

c = C ln(2) − \frac{δ}{2} ≤ y · (1 − (2^{−C})^{\frac{1}{y}})

⇒ c ≤ (1 − (2^{− \frac{C}{ln_{K−1}(n)}} ) ln_{K−1}(n)

for n large enough.

\frac{U(K)}{1 − 2^{−x}} = \frac{U(K)}{1 − (2^{− \frac{C}{ln_{K−1}(n)}}} ≤ \frac{U(K)}{c} ln_{K−1}(n) = D ln_{K−1}(n)

for n large enough.

Claim 2: e_{K−2}(D ln_{K−1}(n)) ≤ (ln(n))^{D} for n large enough. Proof claim 2 Observe that \frac{1}{2} < D < 1 and thus the proof of claim 2 in the preceding lemma still holds.

Claim 3: ∀ϵ_{0} > 0∃N∀n ≥ N(ln(n))^{D} ≤ ϵ_{0} \frac{C ln(n)}{ln_{K−1}(n)} Proof claim 3 D < 1 ⇒ 1−D > 0 ⇒ 1−exp(1−D) < 0, and thus z^{1−exp(1−D)} → 0 (z → ∞)

\frac{ln(y)}{y^{1−D}} = \frac{ln(y)}{exp((1 − D) ln(y))} = \frac{ln(y)}{(e^{1−D})^{ln(y)}} = ln(y)^{1−exp(1−D)} → 0 (ln y → ∞)

\frac{ln_{K−2} y}{y^{1−D}} ≤ \frac{ln(y)}{y^{1−D}}, so also \frac{ln_{K−2} y}{y^{1−D}} → 0 (ln(y) → ∞, i.e. y → ∞) Hence

\frac{ln_{K−2} ln(n)}{(ln(n))^{1−D}} → 0 (n → ∞)

i.e.

∀ϵ_{0} > 0∃N∀n ≥ N \frac{ln_{K−1}(n)}{(ln(n))^{1−D}} → ϵ_{0}C

hence

∀ϵ_{0} > 0∃N∀n ≥ N(ln(n))^{D} ≤ ϵ_{0} \frac{C ln(n)}{ln_{K−1}(n)}

We conclude that for n large enough

C_{Q_{K}} (n) ≤ x ln(n) + e_{K−2}(U(K)\frac{1}{1 − 2^{−x}}) ≤ C \frac{ln(n)}{ln_{K−1}(n)} + ϵ_{0}C \frac{ln(n)}{ln_{K−1}(n)}

3 The proof- and recursion-theoretic part

3.1 Preliminaries

Definitions

With |x| we denote the binary length of x. Thus |0| := 1 and |x| := ⌈log_{2}(x+1)⌉ for x > 0.

We call a function h : N → N unbounded if h is weakly increasing and lim_{x→∞} h(x) = ∞. If h is unbounded, we let h^{−1}(x) := min{n ∈ N : x < h(n)}. We call an unbounded function h log-like if (∀x > 0)[h(x−1) < h(x) ⇒ (∃y)[x = 2^{y}]] We call an unbounded function h exp-like if (∀x)[F (x) ∈ {0} ∪ {2^{y} : y ∈ N }].

For any limit ordinal λ < ϵ_{0}, let (λ[n])_{n∈N} be the fundamental sequence of λ. Thus if λ = ω^{α_{1}} + … + ω^{α_{k}} > α_{1} ≥ … ≥ α_{k} = β + 1, then λ[n] = ω^{α_{1}} + … + ω^{α_{k−1}} + ω^{β} · n and if λ = ω^{α_{1}} + … + ω^{α_{k}} > α_{1} ≥ … ≥ α_{k} ∈ Lim, then λ[n] = ω^{α_{1}} + … + ω^{α_{k−1}} + ω^{α_{k}[n]}. For all ordinals α ≤ ϵ_{0} we define the explike function F_{α} : N → N as follows F_{0}(x) := 2^{x}, F_{α+1}(x) := F_{α}^{x+1}(x), where the upper index denotes the number of iterations, and F_{λ}(x) := F_{λ[x]}(x) if λ is a limit.

A basic result is that P A proves the totality of F_{α} iff α < ϵ_{0}. Thus P A does not prove the assertion (∀x)(∃y)[F_{ϵ_{0}}(x) = y]. See [3] for a proof. For all α ≤ ϵ_{0} we put f_{a}(K, i) := K + i^{|i|_{F{−1 \atop α}(i)}} Summary of the result

In this section we establish the following result. Theorem

1. PA ⊬ (∀K)(∃M) ((∀m_{0}, ⋯, m_{M−1})[0 ≻ m_{0}&∀i < M : m_{i} ≤ f_{ϵ_{0}}(K, i)]) ⇒ ∃i < M − 1 : m_{i} ⪯ m_{i+1}

2. If α < ϵ_{0} then PA ⊢ (∀K)(∃M) ((∀m_{0}, ⋯, m_{M−1})[0 ≻ m_{0}&∀i < M : m_{i} ≤ f_{α}(K, i)]) ⇒ ∃i < M − 1 : m_{i} ⪯ m_{i+1}

Consider the following function:

D(K, h) := max{M : (∃m_{0} ≻ ⋯ ≻ m_{M−1})[0 ≻ m_{0}&(∀i < M)m_{i} ≤ K+i^{|i|_{h(i)}}]}

Then our theorem is equivalent to

1. PA ⊬ (∀K)(∃M)M > D(K, F_{ϵ_{0}}^{−1})

2. If α < ϵ_{0} then PA ⊢ (∀K)(∃M)M > D(K, F_{α}^{−1})

This theorem is the multiplicative analogue of the following result of Arai and Weiermann ([1],[7]):

1. PA ⊬ (∀K)(∃M) ((∀m_{0}, ⋯, m_{M−1})[0 ≻ m_{0}&∀i < M : N(m_{i}) ≤ K + |i| · |i|_{F_{e_{0}}^{−1}(i)}) ⇒ ∃i < M − 1 : m_{i} ⪯ m_{i+1}

2. If α < ϵ_{0} then PA ⊢ (∀K)(∃M) ((∀m_{0}, ⋯, m_{M−1})[0 ≻ m_{0}&∀i < M : N(m_{i}) ≤ K + |i| · |i|_{F_{a}^{−1}(i)}) ⇒ ∃i < M − 1 : m_{i} ⪯ m_{i+1}

Or, with

L(K, h) := max{M : (∃m_{0} ≻ ⋯ ≻ m_{M−1})[0 ≻ m_{0}&(∀i < M)N(m_{i}) ≤ K+|i|·|i|_{h(i)}]}

1. PA ⊬ (∀K)(∃M)M > L(K, F_{ϵ_{0}}^{−1})

2. If α < ϵ_{0} then PA ⊢ (∀K)(∃M)M > L(K, F_{α}^{−1})

So by replacing the additive norm N with the multiplicative norm M, and replacing the function K + |i| · |i|_{F_{a}^{−1}(i)} with K + i^{|i|_{F{−1 \atop α}}}, we get again an independence result. The first is obtained by using bounds on the local countfunction c_{Q_{K}}, the latter by using bounds on the global count function C_{Q_{K}}. This suggests the existence of a relation between local additive and global multiplicative. In fact, this parallelism is stated as an open problem in the book of Burris [12.21 in 2]

In [1] it is shown that, with l(i) = |i|^{2}, F_{ϵ_{0}} is bounded by K ↦ L(2K + 16, l). Therefore the latter function is not provably total in PA. In section 3.3 of this paper we show that F_{ϵ_{0}} is also bounded by a function which involves D. This yields the unprovability assertion. For the provability result, section 3.2, we show that for α < ϵ_{0}, D is bounded from above by a function which is primitive recursive in F_{α}. This implies that D is provable recursive in PA.

Some auxiliary lemmas needed in the proofs

Lemma 3.1 1. x ≥ 4 ⇒ x^{2} ≤ 2^{x}

2. x ≥ 3 ⇒ 3_{n}(x) ≤ 2_{n}(2x)

3. |2_{K}(y)|_{K} ≥ y

4. 2_{K−1}(|N + 1|_{K}) ≤ N + 1 for all K ≥ 4, N + 1 ≥ 2_{K−1}(K − 2)

5. K ≥ 4&1 ≤ m_{0} ≤ K + 1 ⇒ m_{0} ⪯ q_{K−1}.

6. h loglike ⇒ h^{−1} explike

7. F explike ⇒ F^{−1} loglike

Proof

1. See Proposition 14 in [1]

2. See Proposition 14 in [1] 3. Induction on K. If K=1 then |2_{1}(y)| = ⌈log_{2}(2^{y} + 1)⌉ ≥ ⌈log_{2}(2^{y})⌉ = y And |2_{K+1}(y)|_{K+1} = | |2_{1}(2_{K}(y))| |_{K} ≥ |2_{K}(y)|_{K} ≥ y 4. First we show it is true for N + 1 = 2_{K−1}(K − 2) K = 4 2_{4−1}(|2_{4−1}(4 − 2)|_{4}) = 2_{4} = N + 1 K > 4 2_{K}(|N + 1|_{K+1}) = 2_{1}(2_{K−1}(||N + 1||_{K}) ≤ 2_{1}(|N + 1|) Take N + 1 = 2_{K−1}(K − 2) : 2_{K}(|2_{K−1}(K − 2)|_{K+1}) ≤ 2_{1}(|2_{K−1}(K − 2)|) = 2_{1}(2_{K−2}(K − 2)) = 2_{K−1}(K − 2) Since 2_{K−1}(|N + 1|_{K}) grows slower in N than 1, the assertion follows for all N + 1 ≥ 2_{K_{1}}(K − 2) 5. For K = 4 it is checked by hand. For K ≥ 5 we prove the assertion by induction on m_{0} Suppose that m_{0} ≻ q_{K−1} If q_{K−1}|m_{0} then, since m_{0} ≠ q_{K−1}, K +1 ≥ m_{0} > q_{K−1} > K +1 Contradiction. Thus q_{K−1} is not a divisor of m_{0}. Since q_{K−1} is prime, this implies that gcd(m_{0}, q_{K−1}) = 1. Them by definition of ≺: there is a prime p_{j}|m_{0} s.t. q_{K−1} ≺ p_{j}, i.e. p_{q_{K−2}} ≺ p_{j}, i.e. q_{K−2} ≺ j. (Here we use the fact that ∀a, b ≠ 0, 1 a ≺ b ⇔ p_{a} ≺ p_{b}, which follows easy from the definition of ≺) But j < m_{0} ≤ K + 1, and thus j ≤ K, K − 1 ≥ 4 ⇒ j ⪯ q_{K−2} by induction hypothesis. Contradiction. 6. Let h be loglike. h^{−1}(x) = min{n ∈ N : h(n) > x}. Suppose h^{−1}(x) = m ≠ 0. Then h(m) > x and h(m − 1) ≤ x, hence h(m) > h(m − 1) ⇒ (∃y)m = 2^{y} Thus (∀x)h^{−1}(x) ∈ {0} ⋃{2^{y} : y ∈ N}, hence, h^{−1} is explike. 7. Let F be explike. F^{−1}(x) = min{n ∈ N : F (n) > x}. Let x > 0 be arbitrary Suppose m = F^{−1}(x) > F^{−1}(x − 1) = m′. If F (m′) > x then m = F^{−1}(x) ≤ m′ = F^{−1}(x − 1) but we assumed m > m′ Neither is possible F (m′) < x because then x − 1 < F (m′) < x which is not possible Hence, F (m′) = x, hence, x = 2^{y} ∃y

Of course, we also need to show that the assertion about which the independence result is retrieved, is true indeed. This is a simple consequence of Königs lemma (every finitely-branched infinite tree has a path), and the fact that an descending chain of ordinals cannot be infinite. Remember that ⟨N^{+}, ≺⟩ ≃ ⟨E ≤ ϵ_{0}, <⟩

Lemma 3.2 Let || || be any norm, let f be any function N → N (∀K)(∃M)∀α_{0}, …, α_{M} ≺ 0(∀i ≤ M : ||α_{i}|| ≤ K + f(i) ⇒ ∃i : α_{i} ⪯ α_{i+1})

Proof Let

b := {< α_{0}, …, α_{M} >: ∀i ≤ M : ||α_{i}|| ≤ K + f(i), 0 ≻ α_{0} ≻ … ≻ α_{M}}

Suppose the lemma is false Then (∃K)(∀M)∃ < α_{0}, …, α_{M} >∈ b Then b is an infinite tree. b is also finitely branched, since: suppose < α_{0}, …, α_{M} >∈ b. If < α_{0}, …, α_{M+1} >∈ b then ||α_{M+1}|| ≤ K + f(m + 1), so there are only finite possible succesors. By Königs lemma, there is a path f : N → N, (∀i) < f(0), f(1), …, f(i) >∈ b. But then f(0), f(1), … are isomorph with an infinite descending chain of ordinals, which is impossible

3.2 The provability result

Lemma 3.3 Let h be loglike, F := h^{−1} Let V := max(C̃ + 24, 48) Then ∀K ≥ max{4, h(0)} we have D(K, h) ≤ max{2F (K), 2_{K}(K−2), 2_{K+1}(5V)}

Proof Fix K ≥ max{4, h(0)}. Let N_{1} := max{2F (K), 2_{K}(K − 2), 2_{K+1}(5V)}.

Choose an arbitrary sequence m_{0}, …, m_{n−1} s.t. 0 ≻ m_{0} ≻ ⋯ ≻ m_{n−1} and m_{i} ≤ K + i^{(|i|_{h(i)})} for all i = 0, ⋯, n − 1. We need to show n ≤ N_{1}. We proof this by contradiction. Assume n > N_{1}.

h is loglike, so F = h^{−1} is explike. From this fact together with K ≥ 4, it follows that ∃N ≥ 4 s.t. N_{1} = 2^{N+1}. We have K ≥ 4 and m_{0} ≤ K + 0^{|0|_{h(0)}} ≤ K + 1, so by lemma 3.1.5 m_{0} ⪯ q_{K−1}. By transitivity of ⪯, m_{i} ≺ q_{K−1} for all i = 0, ⋯, n − 1. Since n > N_{1} = 2^{N+1} we thus have m_{2^{N}} , ⋯, m_{2^{N+1}−1} ∈ Q_{K−1}.

h is loglike so h(i) = h(2^{N}) for all i ∈ [2^{N}, 2^{N+1} − 1]. Let k := K + (2^{N+1} − 1)^{|2^{N+1}−1|_{h(2^{N})}}. Then we have ∀i ∈ [2^{N}, 2^{N+1} − 1] : m_{i} ≤ K + (i)^{|i|_{h(i)}} ≤ k And hence C_{Q_{K−1}}(k) ≥ card([2^{N}, 2^{N+1} − 1]) = 2^{N} Lemma 2.7 tells us that C_{Q_{K−1}}(k) ≤ exp(V \frac{ln_{1}(k)}{ln_{K−2}(k)})

To reach a contradiction we’ll show that exp(V \frac{ln_{1}(k)}{ln_{K−2}(k)}) < 2^{N}, which is equivalent to

V \frac{ln_{1}(k)}{N} < ln_{K−2}(k) ln(2)  (3)

Step one \frac{ln_{1}(k)}{N} ≤ ln(2) · (1 + 2|N + 1|_{K}) Proof step one: By definition N_{1} ≥ 2F (K), therefore 2^{N} ≥ F (K) = h^{−1}(K) h^{−1}(K) = min{n : K < h(n)}, so K < h(h^{−1}(K)) 2^{N} ≥ h^{−1}(K) ⇒ h(2^{N}) ≥ h(h^{−1}(K)) > K (h is weakly increasing) and hence K ≤ h(2^{N}) − 1 Thus

|N + 1|_{h(2^{N})−1} ≤ |N + 1|_{K}  (4)

An easy induction on K shows 2_{K}(K − 2) ≥ 2^{K+1}, hence 2^{N+1} = N_{1} ≥ 2_{K}(K − 2) ≥ 2^{K+1}, and thus N ≥ K. For k we have using (4)

k = K + (2^{N+1} − 1)^{|2^{N+1}−1|_{h(2^{N})}} ≤ K + (2^{N+1})^{|N+1|_{h(2^{N})−1}}
= K + 2^{(N+1)|N+1|_{h(2^{N})−1}} < N + 2^{(N+1)|N+1|_{K}}
≤ 2^{N+1} · 2^{(N+1)|N+1|_{K}}

(since ∀y ≥ 1 : N + y ≤ y · 2^{N+1}) Hence

ln_{1}(k) ≤ ln(2^{N+1} · 2^{(N+1)|N+1|_{K}}) = (N + 1)(|N + 1|_{K} + 1) ln(2)

And thus

\frac{ln_{1}(k)}{N} ≤ \frac{(N + 1)}{N}(|N + 1|_{K} + 1) ln(2) ≤ (\frac{5}{4}|N + 1|_{K} + \frac{5}{4}) ln(2)

(since N ≥ 4)

≤ (\frac{5}{4}|N + 1|_{K} + 1 + \frac{1}{4} · |N + 1|_{K}) ln(2)

(since |N + 1|_{K} ≥ 1)

≤ (2|N + 1|_{K} + 1) ln(2)

Step two V · (1 + 2|N + 1|_{K}) ≤ ln_{K−2}(k) (This together with step one proves (3) and hence the contradiction) Proof step two: Let x := V (1 + 2|N + 1|_{K}). We’ll show e_{K−2}(x) ≤ k N_{1} ≥ 2_{K+1}(5V) ⇒ N + 1 ≥ 2_{K}(5V) ⇒ |N + 1|_{K} ≥ |2_{K}(5V)|_{K} ≥ 5V (Lemma 3.1.3) ≥ 5 > 4

This gives 2x = 2V (1 + 2|N + 1|_{K}) < 4V + 4V |N + 1|_{K} < |N + 1|_{K}V + 4V |N + 1|_{K} = 5V |N + 1|_{K} < (|N + 1|_{K})^{2}.

Hence we get

e_{K−2}(x) ≤ 3_{K−2}(x) ≤ 2_{K−2}(2x)

(Lemma 3.1.2)

≤ 2_{K−2}((|N + 1|_{K})^{2}) ≤ 2_{K−1}(|N + 1|_{K})

by applying Lemma 3.1.1: |N+1|_{K} ≥ 4 ⇒ (|N+1|_{K})^{2} ≤ 2^{|N+1|_{K}} ⇒ 2_{K−2}((|N+ 1|_{K})^{2}) ≤ 2_{K−2}(2^{|N+1|_{K}}) = 2_{K−1}(|N + 1|_{K})

Using lemma 3.1.4:

e_{K−2}(x) ≤ 2_{K−1}(|N + 1|_{K}) ≤ N + 1 < k

and we have reached a contradiction (The last estimation N + 1 < k is true because k = K + (N_{1} − 1)^{|N_{1}−1|_{h(2^{N})}} > (N_{1} − 1)^{|N_{1}−1|_{h(2^{N})}} ≥ (N_{1} − 1)^{1} = 2^{N+1} − 1 > N + 1)

Theorem If α < ϵ_{0} then P A ⊢ (∀K)(∃M)M > D(K, h)

Proof Let h(i) := F_{α}^{−1}(i) h is loglike, h^{−1} = F_{α}, hence by Lemma 3.3

(∀K ≥ max{4, h(0)}) D(K, h) ≤ max{2F_{α}(K), 2_{K}(K − 2), 2_{K+1}(5V)}

This last function is primitive recursive in F_{α}, hence provable recursive in PA. Therefore also D(K, h) is provable recursive in PA, and thus the Theorem holds.

Remark In Lemma 3.3, the contradiction followed from exp(V \frac{ln_{1}(k)}{ln_{K−2}(k)}) < 2^{N} with k, V, N primitive recursive in K. Since very rough estimates were used to proof this, the question arises for which less tight upperbounds of C_{K}(k), say C_{K}(k) ≤ b(k), we still have b(k) < 2^{N}. The most trivial, b(k) = k, does not work. But maybe we can find a bound b for which it does hold, and which is easier to derive than the one in Lemma 2.7.

3.3 Proof of the unprovability assertion

Define g_{1}, g, r as follows: r(n) := 2n + 16 g_{1}(n) := max{2_{n+2}(n + 1), 2_{1}(2_{1}(21) − 1), 2^{T (n+3)}} (Recall that T (K) = max{e_{4}^{e_{3}}, e_{K}} from Lemma 2.3 ) g(n) := 6^{2_{1}(3n+20)−1} · 2^{2_{1}(3n+20)} · 2^{g_{1}(n)} l(i) := |i|^{2}

Lemma 3.4 1. 2^{(|i|−1)} ≤ i ≤ 2^{|i|} − 1

2. i > g_{1}(n) ⇒ l(|i|) ≥ n + 3 + r(n)

3. i > g_{1}(n) ⇒ (|i| − 1) ≥ 8l(|i|)^{2}

4. q_{m+r(n)} · 2^{g_{1}(n)} ≤ g(n)

Proof 1. |i| = α ⇒ 2^{α} ≤ i ≤ 2^{α+1} − 1 ⇒ 2^{|i|−1} ≤ i ≤ 2^{|i|} − 1 2.

i > g_{1}(n) ≥ 2_{n+2}(n + 1) ⇒ l(|i|) = ||i||^{2} > ||2_{n+2}(n + 1)||^{2} = |2_{n+1}(n + 1) + 1|^{2}

≥ |2_{n+1}(n + 1)|^{2} = (2_{n}(n + 1) + 1)^{2}

For n = 1 : (2_{1}(1 + 1) + 1)^{2} = 25 > 22 = 3n + 19 For n > 1 observe that (2_{n}(n + 1) + 1)^{2} grows faster in n then 3n + 19. 3. If γ ≥ 21 then 2^{γ} > 8(γ + 1)^{4}. Hence,

β ≥ 8 · 22^{4} ⇒ (\frac{1}{8}β)^{\frac{1}{4}} − 1 ≥ 21

⇒ 2^{( \frac{1}{8} β)^{\frac{1}{4}} −1} > 8((\frac{1}{8}β)^{\frac{1}{4}} − 1 + 1)^{4} = β

Applying assertion 1 to |i| gives 2^{(||i||−1)} ≤ |i| ≤ 2^{||i||} −1, and applying assertion 1 again to these bounds gives 2^{2^{(||i||−1)}−1} ≤ i ≤ 2^{2^{||i||}−1} − 1 Now

i ≥ 2_{1}(2_{1}(21) − 1) ⇒ ||i|| ≥ 22 ⇒ 8l(|i|)^{2} = 8||i||^{4} ≥ 8 · 22^{4}
⇒ 2^{( \frac{1}{8} 8||i||^{4})^{\frac{1}{4}} −1} > 8||i||^{4}
⇒ 2^{||i||−1} > 8l(|i|)^{2} ⇒ |i| − 1 ≥ 2^{||i||−1} − 1 ≥ 8||i||^{4}

4. Put m := n + 3 and z(n) := 6n ln_{1}(n). p_{n} ≤ z(n) (lemma 1.1.5). Note that z is increasing in n By repeated application we get q_{k} ≤ z^{(k)}(2). And thus q_{m+r(n)} · 2^{g_{1}(n)} ≤ z^{(m+r(n))}(2) · 2^{g_{1}(n)} ≤ z^{(3n+20)}(2) · 2^{g_{1}(n)} We claim z^{(k)}(n) ≤ 6^{2_{1}(k)−1} · n^{2_{1}(k)}. This follows with induction: z^{(1)}(n) ≤ 6n^{2} and

z^{(k+1)}(n) = z(z^{(k)}(n)) ≤ z(6^{2_{1}(k)−1}·n^{2_{1}(k)}) ≤ 6(6^{2_{1}(k)−1}·n^{2_{1}(k)})^{2} = 6^{2_{1}(k+1)−1}·n^{2_{1}(k+1)}

And thus

q_{m+r(n)} · 2^{g_{1}(n)} ≤ z^{(3n+20)}(2) · 2^{g_{1}(n)} ≤ 6^{2_{1}(3n+20)−1} · 2^{2_{1}(3n+20)} · 2^{g_{1}(n)} ≤ g(n)

Lemma 3.5 Let l(i) := |i|^{2} A(n) := L(n, l) h fixed log-like function F (n) := h^{−1}(n) ≤ L(r(n), l) Then F (n) ≤ D(g(n), h) for all n

Proof Let m := n + 3

L(r(n)), l) = max{M : (∃0 ≻ m_{0} ≻ … ≻ m_{M−1})(∀i)N(m_{i}) ≤ r(n) + |i| · |i|_{l(i)}}

Choose a sequence 0 ≻ l_{0} ≻ … ≻ l_{M_{0}} with ∀i N(l_{i}) ≤ r(n) + |i| · |i|_{l(i)} and M_{0} maximal (i.e. M_{0} = L(r(n), l) − 1) Since |i|^{2} ≥ 1 ⇒ |i|_{|i|^{2}} ≤ |i| ⇒ |i| · |i|_{l(i)} = |i| · |i|_{|i|^{2}} ≤ |i| · |i| = l(i) And thus ∀i N(l_{i}) ≤ r(n) + l(i).

From this sequence, we’ll construct a sequence 0 ≻ m_{0} ≻ … ≻ m_{F (n)} with ∀i m_{i} ≤ g(n) + i^{|i|_{h(i)}}. This proves the assertion.

First we observe that l_{0} = q_{r(n)}. Since suppose not. Then either l_{0} ≺ q_{r(n)} or l_{0} ≻ q_{r(n)}. In the first case we have 0 ≻ q_{r(n)} ≻ l_{0} ≻ … ≻ l_{M_{0}}. Since ∀x N(q_{x}) = x + 1: N(q_{r(n)}) = r(n) + 1 = r(n) + |0| · |0|_{l(0)} N(l_{i}) ≤ r(n) + |i| · |i|_{l(i)} ≤ r(n) + |i + 1| · |i + 1|_{l(i+1)} And hence M_{0} is not maximal. Contradiction. In the case that l_{0} ≻ q_{r(n)}, we either have that ∃α > 1 l_{0} = q_{r(n)} · α and then N(l_{0}) = N(q_{r(n)}) + N(α) > N(q_{r(n)}) = r(n) + 1 = r(n) + |0| · |0|_{l(0)}. Contradiction. Or we have that ∃β > r(n)&∃γ l_{0} = q_{β} · γ and then N(l_{0}) > N(q_{β}) = β + 1 > r(n) + 1 = r(n) + |0| · |0|_{l(0)}. Contradiction.

For 0 ≤ i ≤ g_{1}(n) we put m_{i} := q_{m+r(n)} · 2^{g_{1}(n)−i}. Then obviously 0 ≻ m_{0} ≻ … ≻ m_{g_{1}(n)}. And m_{i} ≤ g(n) by lemma 3.4.4

For g_{1}(n) < i ≤ F (n) we define k(i) := 2^{(|i|−1)(|i|_{h(i)}−1)} Q^{m}(≤ k(i)) := {l ≺ q_{m} : l ≤ k(i)} And enum_{Q^{m}(≤k(i))} is the enumeration function of enum_{Q^{m}(≤k(i))} with respect to ≺. (So enum_{Q^{m}(≤k(i))}(2^{|i|}−i) is the (2^{|i|}−i)-th element of the set {l ≺ q_{m} : l ≤ k(i)} ordered by ≺. Below we show that such an element indeed exists) We put m_{i} := q_{m}(l_{|i|}) · enum_{Q^{m}(≤k(i))}(2^{|i|} − i). For all i > g_{1}(n)

m_{g_{1}(n)} = q_{m+r(n)} = q_{m}(q_{r(n)}) = q_{m}(l_{0}) ≻ q_{m}(l_{|i|})

since l_{0} ≻ l_{|i|}. And thus m_{i} ≺ m_{g_{1}(n)} for all i > g_{1}(n).

If |i| = |i + 1| then k(i) = k(i + 1), q_{m}(l_{|i|}) = q_{m}(l_{|i+1|}) and

enum_{Q^{m}(≤k(i))}(2^{|i|} − i) ≻ enum_{Q^{m}(≤k(i+1))}(2^{|i+1|} − (i + 1))

And thus m_{i} ≻ m_{i+1}

If |i| < |i + 1| then l_{|i|} ≻ l_{|i+1|} ⇒ q_{m}(l_{|i|}) ≻ q_{m}(l_{|i+1|}) Also enum_{Q^{m}(≤k(i))}(2^{|i|} − i) ≺ q_{m}(l_{|i|}) and enum_{Q^{m}(≤k(i+1))}(2^{|i+1|} − (i + 1)) ≺ q_{m}(l_{|i|}) And thus m_{i} ≻ m_{i+1}

So we have shown m_{g_{1}(n)} ≻ m_{i} ≻ m_{i+1} ≻ … ≻ m_{F (n)} for all g_{1}(n) ≤ F (n). Now we have to show that for those i, m_{i} ≤ g(n) + i^{|i|_{h(i)}}

With Lemma 1.2 follows

m_{i} ≤ q_{m}(l_{|i|}) · k(i) ≤ 2^{2(N(q_{m}(l_{|i|})))^{2}} · k(i)
= 2^{2(m+N(l_{|i|}))^{2}} · k(i) ≤ 2^{2(m+r(n)+l(|i|))^{2}} · k(i)

Using Lemma 3.4.1, 3.4.2, 3.4.3 we get

m_{i} ≤ 2^{2(2l(|i|))^{2}} · k(i) = 2^{8l(|i|)^{2}+(|i|−1)(|i|_{h(i)}−1)}
≤ 2^{(|i|−1)+(|i|−1)(|i|_{h(i)}−1)} = (2^{(|i|−1)})^{|i|_{h(i)}} ≤ i^{|i|_{h(i)}} ≤ i^{|i|_{h(i)}} + g(n)

We still had to show that the (2^{|i|} − i)-th element of Q^{m}(≤ k(i)) exists. We’ll show that #Q^{m}(≤ k(i)) ≥ 2^{|i|} − 1. Note F (n) ≥ i ⇒ h(i) = F^{−1}(i) ≤ n. And from i > g_{1}(n) ≥ 2^{T (m)} follows k(i) = 2_{1}((|i| − 1)(|i|_{h(i)} − 1)) ≥ 2_{1}((|i| − 1)(|i|_{n} − 1)) ≥ 2_{1}(|i| − 1) ≥ T (m) So by lemma 2.3, C_{Q_{m}}(k(i)) ≥ exp(2^{2−m} \frac{ln(k(i))}{ln_{m−1}(k(i))}) i > g_{1}(n) ≥ 2_{n+2}(n + 1) implies 2^{2−m}(|i|_{n} − 1) ≥ ln_{m−1}(2_{1}((|i| − 1)^{2})), since the lefthandside grows faster in i than the righthandside, and for i = 2_{n+2}(n + 1) the lefthandside is greater than the righthandside Hence

2^{2−m}(|i|_{n} − 1) ≥ ln_{m−1}(2_{1}((|i| − 1)^{2})) ⇒

2^{2−m}(|i|_{h(i)} −1) ≥ 2^{2−m}(|i|_{n} −1) ≥ ln_{m−1}(2_{1}((|i|−1)(|i|_{h(i)} −1)) = ln_{m−1}(k(i))

⇒ 2^{2−m} ln(k(i)) = 2^{2−m}(|i|_{h(i)} − 1)(|i| − 1) ln(2)
≥ (|i| − 1) ln(2) ln_{m−1}(k(i)) = ln(2^{|i|−1}) ln_{m−1}(k(i))

⇒ 2^{2−m} \frac{ln(k(i))}{ln_{m−1}(k(i))} ≥ ln(2^{|i|−1})

⇒ C_{Q_{m}}(k(i)) ≥ exp(2^{2−m} \frac{ln(k(i))}{ln_{m−1}(k(i))}) ≥ 2^{|i|−1}

Theorem PA ⊬ (∀K)(∃M)M > D(K, F_{ϵ_{0}}^{−1})

Proof F_{ϵ_{0}} is bounded by the function K ↦ L(2K+16, l). Therefore F_{ϵ_{0}} is also bounded by n ↦ A(r(n)) = L(2n + 16, l). By applying Lemma 3.5 with h := F_{ϵ_{0}}^{−1}, we get that F_{ϵ_{0}} is bounded by the function D(g(n), F_{ϵ_{0}}^{−1}). Hence, D(g(n), F_{ϵ_{0}}^{−1}) is not provably total, and thus the theorem holds.

References

[1] Toshiyasu Arai: On the slowly well-orderedness of ϵ_{0}. Mathematical Logic Quarterly 48 (2002) 125-139.

[2] S.N. Burris: Number Theoretic Density and Logical Limit Laws. Mathematical Surveys and Monographs 86. American Mathematical Society 2001.

[3] Harvey Friedman and Michael Sheard: Elementary descent recursion and proof theory. Annals of Pure and Applied Logic 71 (1995), 1-45.

[4] J.R. Norris, Markov Chains, Cambridge University Press, Cambridge, 1997 [5] Rosser, J. Barkley, Schoenfeld, Lowell. Approximative formulas for some functions of prime numbers. Illinois J. Math. 6, 64-94, 1962.

[6] K. Schütte: Proof Theory. Springer, Berlin 1977.

[7] Andreas Weiermann. An application of graphical enumeration to PA. To appear in the Journal of Symbolic Logic.

[8] M. Yamashita: Asymptotic estimation of the number of trees, Trans. IECE Japan, 62-A (1979), 128-135 (in Japanese).