Bounds for the Eventual Positivity of Difference Functions of Partitions

into Prime Powers

Roger Woodford Department of Mathematics University of British Columbia Vancouver, BC V6T 1Z2 Canada

                  rogerw@math.ubc.ca

Abstract

In this paper we specialize work done by Bateman and Erdős concerning difference functions of partition functions. In particular we are concerned with partitions into fixed powers of the primes. We show that any difference function of these partition functions is eventually increasing, and derive explicit bounds for when it will attain strictly positive values. From these bounds an asymptotic result is derived.

1 Introduction

Given an underlying set A ⊆ ℕ, we denote the number of partitions of n with parts taken from A by p_{A}(n). The k-th difference function p_{A}^{(k)}(n) is defined inductively as follows: for k = 0, p_{A}^{(k)}(n) = p_{A}(n). If k > 0, then

p_{A}^{(k)}(n) = p_{A}^{(k−1)}(n) − p_{A}^{(k−1)}(n − 1).

Let f_{A}^{(k)}(x) be the generating function for p_{A}^{(k)}(n). We have [5] the following power series identity:

f_{A}^{(k)}(x) = ∑_{n=0}^{∞} p_{A}^{(k)}(n)x^{n}  (1)

= (1 − x)^{k} ∑_{n=0}^{∞} p_{A}(n)x^{n}  (2)
= (1 − x)^{k} ∏_{a∈A} \frac{1}{1 − x^{a}} .  (3)

This may be used to define p_{A}^{(k)}(n) for all k ∈ ℤ, including k < 0.

Bateman and Erdős [5] characterize the sets A for which p_{A}^{(k)}(n) is ultimately nonnegative. Note that if k < 0, then the power series representation of (1−x)^{k} has nonnegative coefficients so that p_{A}^{(k)}(n) ≥ 0. For k ≥ 0, they prove the following: if A satisfies the property that whenever k elements are removed from it, the remaining elements have greatest common divisor 1, then

lim_{n→∞} p_{A}^{(k)}(n) = ∞.

A simple consequence of this is the fact that p_{A}(n) is eventually monotonic if k > 0.

No explicit bounds for when p_{A}^{(k)}(n) becomes positive are included with the result of Bateman and Erdős [5]. By following their approach but specializing to the case when

A = {p^{ℓ} : p is prime},  (4)

for some fixed ℓ ∈ ℕ, we shall find bounds for n depending on k and ℓ which guarantee that p_{A}^{(k)}(n) > 0. For the remainder, A shall be as in (4), with ℓ ∈ ℕ fixed.

In a subsequent paper, Bateman and Erdős [6] prove that in the special case when ℓ = 1, p_{A}^{(1)}(n) ≥ 0 for all n ≥ 2. That is, the sequence A000607 of partitions of n into primes is increasing for n ≥ 1. Our result pertains to more general underlying sets; partitions into squares of primes (A090677), cubes of primes, etc.

In a series of papers (cf. [10]- [13]), L. B. Richmond studies the asymptotic behaviour for partition functions and their differences for sets satisfying certain stronger conditions. The results none-the-less apply to the cases of interest to us, that is, where A is defined as above. Richmond proves [12] an asymptotic formula for p_{A}^{(k)}(n). Unfortunately, his formula is not useful towards finding bounds for when p_{A}^{(k)}(n) must be positive, since, as is customary, he does not include explicit constants in the error term.

Furthermore, his asymptotic formula includes functions such as α = α(n) defined by

n = ∑_{a∈A} \frac{a}{e^{αa} − 1} − \frac{k}{e^{α} − 1}.

As we are seeking explicit constants, a direct approach will be cleaner than than attempting to adapt the aforementioned formula.

Another result worthy of comment from Richmond [12] pertains to a conjecture of Bateman and Erdős [5]. His result applies to A as defined in (4), and states that

\frac{p_{A}^{(k+1)}(n)}{p_{A}^{(k)}(n)} = O(n^{−1/2}), as n → ∞.

We omit the subscript and write p^{(k)}(n) in case the underlying set is A, and omit the superscript if k = 0. The letter B will always be used to denote a finite subset of A. We shall also write ζ_{n} for the primitive n-th root of unity e^{2πi/n}. The letters ζ and η shall always denote roots of unity. We shall denote the m-th prime by p_{m}.

Our main results are Theorems 1.1 and 1.2. The former is established in Sections 2 and 3.

Theorem 1.1. Let k be a nonnegative integer, let b_{0} = 2π\sqrt{1 − \frac{π^{2}}{12}} and let

t = ⌊6 (\frac{2}{b_{0}} )^{3(k+1)} (k + 2)^{8ℓk+10ℓ+3}⌋ .

Then there are positive absolute constants a_{1}, …, a_{7} such that if

N = N(k, ℓ) = a_{1}t (\frac{a_{2}a_{3}^{ℓ log^{2} t}}{a_{4}^{(k+3)^{ℓ}}} )^{t−1} + a_{5}t^{3} (a_{6}(a_{7}t)^{6ℓ})^{t−1} ,

then n ≥ N implies that p^{(k)}(n) > 0.

Remark 1. The values of the constants are approximately

a_{1} ≈ 1.000148266,
a_{2} ≈ 2757234.845,
a_{3} ≈ 1424.848799,
a_{4} ≈ 2.166322546,
a_{5} ≈ 1.082709333,
a_{6} ≈ .0193095561,
a_{7} ≈ 2.078207555.

For the remainder of the paper, b_{0} shall be as defined in Theorem 1.1. Note that b_{0} ≈ 2.6474. Furthermore, Define

F (k, ℓ) = min {N ∈ ℕ : n ≥ N implies that p^{(k)}(n) > 0}.

We show in Section 4 that Theorem 1.1 yields the following asymptotic result:

Theorem 1.2. Fix ℓ ∈ ℕ. Then as k → ∞,

log F (k, ℓ) = o ((k + 2)^{8ℓk}) .

Following Bateman and Erdős [5], we first tackle the finite case.

2 Finite subsets of A

Lemma 2.1. Let B be a finite subset of A of size r, and suppose k < r. The function p_{B}^{(k)}(n) can be decomposed as follows:

p_{B}^{(k)}(n) = g_{B}^{(k)}(n) + ψ_{B}^{(k)}(n),

where g_{B}^{(k)}(n) is a polynomial in n of degree r−k−1 with leading coefficient ((r − k − 1)! ∏_{q∈B} q)^{−1},

and ψ_{B}^{(k)}(n) is periodic in n with period ∏_{q∈B} q.

Proof. We use partial fractions to decompose the generating function f_{B}^{(k)}(x) as follows:

f_{B}^{(k)}(x) = \frac{1}{(1 − x)^{r−k}} ∏_{q∈B} ∏_{j=1}^{q−1} \frac{1}{1 − ζ_{q}^{j}x}  (5)

= \frac{α_{1}}{1 − x} + \frac{α_{2}}{(1 − x)^{2}} + … + \frac{α_{r−k}}{(1 − x)^{r−k}} + ∑_{q∈B} ∑_{j=1}^{q−1} \frac{β(ζ_{q}^{j})}{1 − ζ_{q}^{j}x},  (6)

where the α_{i}, and β(ζ_{q}^{j}) are complex numbers that can be determined. Note that

α_{r−k} = (∏_{q∈B} q)^{−1} .

The power series expansion for (1 − x)^{−h} is given by

\frac{1}{(1 − x)^{h}} = ∑_{n=0}^{∞} \binom{n + h − 1}{h − 1}x^{n}.

Hence, if

g_{B}^{(k)}(n) = ∑_{h=1}^{r−k} α_{h}\binom{n + h − 1}{h − 1},

and

ψ_{B}^{(k)}(n) = ∑_{q∈B} ∑_{j=1}^{q−1} β(ζ_{q}^{j})ζ_{q}^{jn},

then the lemma is proved.

For the remainder of this paper, g_{B}^{(k)}(n) and ψ_{B}^{(k)}(n) shall be as in Lemma 2.1, for a given finite set B ⊆ A which shall be clear from the context.

Remark 2. Let B be as in Lemma 2.1. We wish to know the precise value of β(ζ_{q}^{j}). To simplify notation a little, we will frequently write β_{ζ} instead, when ζ is clear from the context.

In particular, suppose η = ζ_{q}^{j}, where q ∈ B, and 0 < j < q. Then

(1 − ηx)f_{B}^{(k)}(x) = (1 − x)^{k} \frac{1}{1 + ηx + ⋯ + (ηx)^{q−1}} ∏_{\begin{matrix}p∈B \\ p≠q \end{matrix}} \frac{1}{1 − x^{p}}

= β_{η} + (1 − ηx) (\frac{α_{1}}{1 − x} + ⋯ + \frac{α_{r−k}}{(1 − x)^{r−k}} + ∑_{ζ≠η} \frac{β_{ζ}}{1 − ζx}) ,

hence,

β_{η} = \frac{(1 − η̄)^{k}}{q} ∏_{\begin{matrix}p∈B \\ p≠q \end{matrix}} \frac{1}{1 − η̄^{p}} .

We shall frequently make use of the inequality

1 − \frac{θ^{2}}{2} ≤ cos θ ≤ 1 − \frac{θ^{2}}{2} + \frac{θ^{4}}{24},

which holds for all values of θ. Note that

|e^{iθ} − 1| = \sqrt{2(1 − cos θ)},

so for −2\sqrt{3} ≤ θ ≤ 2\sqrt{3},

|θ|\sqrt{1 − \frac{θ^{2}}{12}} ≤ |e^{iθ} − 1| ≤ |θ|.

In particular, for 0 ≤ θ ≤ π,

θ\sqrt{1 − \frac{θ^{2}}{12}} ≤ |e^{iθ} − 1| ≤ θ.  (7)

Lemma 2.2. Suppose that ζ ≠ 1 is a q-th root of unity, q ≥ 2. Then

\frac{b_{0}}{q} ≤ |1 − ζ| ≤ 2.

Proof. Clearly |1 − ζ| ≤ 2. On the other hand, by equation (7),

|1 − ζ| ≥ |1 − e^{2πi/q}|

≥ \frac{2π}{q} \sqrt{1 − \frac{4π^{2}}{12q^{2}}}

≥ \frac{b_{0}}{q} .

Lemma 2.3. Suppose that k < r, and B ⊆ A, satisfies |B| = r. Suppose further that η = ζ_{q}^{j}, for some q ∈ B, j ∈ {1, …, q − 1}. Then for k ≥ 0,

|β_{η}| ≤ \begin{cases}\frac{2^{k}q^{r−2}}{b_{0}^{r−1}} , & if k ≥ 0; \\ \frac{q^{r−k−2}}{b_{0}^{r−k−1}} , & if k < 0. \end{cases}

Proof. Making use of Remark 2 and Lemma 2.2 we have that for k ≥ 0:

|β_{η}| = \frac{|1 − ζ_{q}^{−j}|^{k}}{q} ∏_{\begin{matrix}p∈B \\ p≠q \end{matrix}} \frac{1}{|1 − ζ_{q}^{−jp}|}

≤ \frac{2^{k}}{q} ∏_{\begin{matrix}p∈B \\ p≠q \end{matrix}} \frac{1}{|1 − ζ_{q}|}

≤ \frac{2^{k}}{q} (\frac{q}{b_{0}} )^{r−1}

= \frac{2^{k}q^{r−2}}{b_{0}^{r−1}} .

A similar arguments works for the case when k < 0.

Theorem 2.1. Suppose that k < r, and B ⊆ A, satisfies |B| = r. Then

|ψ_{B}^{(k)}(n)| ≤ \begin{cases}\frac{2^{k}}{b_{0}^{r−1}} ∑_{q∈B} q^{r−1}, & if k ≥ 0; \\ \frac{1}{b_{0}^{r−k−1}} ∑_{q∈B} q^{r−k−1}, & if k < 0. \end{cases}

Proof. First assume that k ≥ 0. By Lemmas 2.3 and 2.1,

|ψ_{B}^{(k)}(n)| = |∑_{q∈B} ∑_{j=1}^{q−1} β(ζ_{q}^{j})ζ_{q}^{jn}|

≤ ∑_{q∈B} ∑_{j=1}^{q−1} |β(ζ_{q}^{j})|

≤ ∑_{q∈B} ∑_{j=1}^{q−1} \frac{2^{k}q^{r−2}}{b_{0}^{r−1}}

= \frac{2^{k}}{b_{0}^{r−1}} ∑_{q∈B}(q − 1)q^{r−2}

≤ \frac{2^{k}}{b_{0}^{r−1}} ∑_{q∈B} q^{r−1}.

A similar argument works for k < 0.

To obtain bounds for the coefficients α_{h}, we will use Laurent series.

Lemma 2.4. Suppose that k < r, and B ⊆ A, satisfies |B| = r. Denote the largest element of B by Q, and suppose further that 0 < r_{0} < |1 − ζ_{Q}|. Let

d_{B}(r_{0}) = ∏_{q∈B} ∏_{j=1}^{q−1}(|ζ_{q}^{j} − 1| − r_{0}).

Then

|α_{h}| ≤ \frac{1}{r_{0}^{r−k−h}d_{B}(r_{0})}.

Proof. Let γ be the circle |z−1| = r_{0}. From equations (5) and (6), and the Laurent expansion theorem, we have that

|α_{h}| = |\frac{1}{2πi} ∫_{γ} f_{B}^{(k)}(z)(z − 1)^{h−1} dz|

≤ \frac{1}{2π} ∫_{γ} \frac{1}{|z − 1|^{r−k−h+1}} ∏_{q∈B} ∏_{j=1}^{q−1} \frac{1}{|1 − ζ_{q}^{j}z|} dz

≤ \frac{1}{r_{0}^{r−k−h}d_{B}(r_{0})}.

For the following proposition, we define several new constants:

c_{1} = ∏_{k=3}^{∞} (1 − \frac{π^{2}}{3 · 4^{k}} ) ,

c_{2} = ∏_{k=3}^{∞} (1 − \frac{π^{2}}{3 · 4^{k}} )^{\frac{1}{2^{k}}} ,
c_{3} = 4π^{−6}c_{1},
c_{4} = \frac{2 log π}{log 2} − 1,
c_{5} = (\frac{π}{2} )^{1/2} c_{2},
c_{6} = (\frac{π}{2} )^{1/2} (1 − \frac{π^{2}}{48})^{1/4} ,
c_{7} = \frac{sin 4π/5}{4π/5},
b_{1} = c_{5}c_{6} = 1.471843248 …,
b_{2} = \frac{c_{3}}{c_{6}} = .003278645140 …,
b_{3} = c_{4} = 2.302992260 …,
b_{4} = c_{7}π/2 = .3673657828 ….

Proposition 2.1. Let B ⊆ A satisfy |B| = r, and suppose that all the elements of B are odd. Let Q = max{B}, and T = ⌈log_{2} Q⌉. If

r_{0} = min \{|ζ⌈\frac{q}{2^{j}} ⌉_{q} − 1| − |ζ_{2^{j}} − 1| : q ∈ B, j = 2, …, T \},

then

0 < \frac{b_{4}}{Q^{2}} ≤ r_{0} < |1 − ζ_{Q}| ≤ \frac{2π}{Q} .

Furthermore, if d_{B} = d_{B}(r_{0}), then

d_{B} ≥ b_{1}^{∑_{q∈B} q} (b_{2}Q^{b_{3}}e^{− \frac{log^{2} Q}{log 2}} )^{r} .

Proof. Observe that T satisfies

2^{T −1} < Q < 2^{T} .

Now, let

δ_{q} = ∏_{j=1}^{q−1}(|ζ_{q}^{j} − 1| − r_{0}),

so that

d_{B} = ∏_{q∈B} δ_{q}.

Note that since each element of B is odd, we have that

δ_{q} = ∏_{j=1}^{\frac{q−1}{2}}(|ζ_{q}^{j} − 1| − r_{0})^{2}.

Consequently,

δ_{q} ≥ ∏_{k=2}^{T} ∏_{⌈\frac{q}{2^{k}} ⌉≤j<⌈\frac{q}{2^{k−1}} ⌉} |ζ_{2^{k}} − 1|^{2}

≥ ∏_{k=2}^{T} (\frac{π^{2}}{4^{k−1}} (1 − \frac{π^{2}}{3 · 4^{k}} ))^{⌈^{\frac{q}{2^{k−1}}} ⌉−⌈\frac{q}{2^{k}} ⌉}

= (\frac{π^{2}}{4} (1 − \frac{π^{2}}{48}))^{⌈^{\frac{q}{2}}⌉−⌈\frac{q}{4}⌉} × ∏_{k=3}^{T} (\frac{π^{2}}{4^{k−1}} (1 − \frac{π^{2}}{3 · 4^{k}} ))^{⌈^{\frac{q}{2^{k−1}}} ⌉−⌈\frac{q}{2^{k}} ⌉}

≥ (\frac{π^{2}}{4} (1 − \frac{π^{2}}{48}))^{\frac{q−1}{4}} × ∏_{k=3}^{T} (\frac{π^{2}}{4^{k−1}} (1 − \frac{π^{2}}{3 · 4^{k}} ))^{\frac{q}{2^{k}} +1} .

Now

∏_{k=3}^{T} (\frac{π^{2}}{4^{k−1}} (1 − \frac{π^{2}}{3 · 4^{k}} ))^{\frac{q}{2^{k}} +1} ≥ \frac{π^{2(T −2)}}{4^{\binom{T}{2}−1}} (\frac{π^{2( \frac{1}{4} − \frac{1}{2^{T}} )}}{4^{\frac{3}{4} − \frac{T +1}{2^{T}}}} )^{q} c_{1}c_{2}^{q}

≥ \frac{4π^{−4}Q^{\frac{2 log π}{log 2}}}{Qe^{\frac{log^{2} Q}{log 2}}} (\frac{π^{2( \frac{1}{4} − \frac{1}{Q})}}{4^{\frac{1}{4}}} )^{q} c_{1}c_{2}^{q}

≥ 4π^{−4}c_{1}Q^{\frac{2 log π}{log 2} −1}e^{− \frac{log^{2} Q}{log 2}} (\frac{π^{1/2}c_{2}}{2^{1/2}} )^{q} π^{−2}

= c_{3}Q^{c_{4}}e^{− \frac{log^{2} Q}{log 2}} c_{5}^{q}

So we have that

d_{B} ≥ ∏_{q∈B} ((\frac{c_{3}}{c_{6}} ) (c_{5}c_{6})^{q}Q^{c_{4}}e^{− \frac{log^{2} Q}{log 2}} )

= b_{1}^{∑_{q∈B} q} (b_{2}Q^{b_{3}}e^{− \frac{log^{2} Q}{log 2}} )^{r}

Our next task is to bound r_{0} from below. For q ∈ B, j ∈ {2, …, T }, let

f(x) = \sqrt{2(1 − cos x)},
θ = θ(j) = \frac{2π}{2^{j}} , and
ε = ε(q, j) = \frac{2π}{q} ⌈\frac{q}{2^{j}} ⌉ − \frac{2π}{2^{j}} .

Then by the mean value theorem,

|ζ⌈\frac{q}{2^{j}} ⌉_{q} − 1| − |ζ_{2^{j}} − 1| = f(θ + ε) − f(θ)

= \frac{ε sin c}{\sqrt{2(1 − cos c)}},

for some c ∈ (θ, θ + ε).

It is easily seen that 2π⌈q/2^{j}⌉/q can be no greater than 4π/5. On the interval [0, 4π/5], we have sin x ≥ c_{7}x. Therefore

f(θ + ε) − f(θ) ≥ \frac{εc_{7}c}{c} = εc_{7}.  (8)

Choose a ∈ ℕ such that (a−1)2^{j} +1 ≤ q ≤ a2^{j} −1. Then clearly a ≤ 2^{T −j}. Furthermore,

ε ≥ \frac{2πa}{a2^{j} − 1} − \frac{2π}{2^{j}}

= \frac{2π}{2^{j} − 1/a} − \frac{2π}{2^{j}}

≥ \frac{2π}{2^{j} − 2^{j−T}} − \frac{2π}{2^{j}}

≥ \frac{2π}{2^{T} − 1} − \frac{2π}{2^{T}}

≥ \frac{π}{2Q^{2}} .

Hence, by (8) we conclude that

r_{0} ≥ \frac{b_{4}}{Q^{2}} .

Bounding r_{0} from above is a far simpler matter. By definition,

r_{0} < |ζ_{Q} − 1| ≤ \frac{2π}{Q} .  (9)

3 Infinite subsets of ℕ and A

Proposition 3.1. For k ≤ 0, and D_{1} ⊆ D_{2} ⊆ ℕ, we have p_{D_{2}}^{(k)}(n) ≥ p_{D_{1}}^{(k)}(n) ≥ 0.

Proof. This follows immediately from equation 2 and the fact that for k ≤ 0, the power series expansion for (1 − x)^{k} has nonnegative coefficients.

For the sake of clarity and the comprehensiveness of this exposition we include the following theorem of Bateman and Erdős [5] suitably adapted to our needs.

Theorem 3.1. Let D ⊆ ℕ be an infinite set. For any t ∈ ℕ, we have that

\frac{p_{D}(n)}{p_{D}^{(−1)}(n)} ≤ \frac{1}{t + 1} + \frac{(t − 1)^{2}}{t + 1} \frac{n^{2t−3}}{p_{D}^{(−1)}(n)}.

Proof. Denote by P_{q}(n), the number of partitions of n into parts from D such that there are exactly q distinct parts. P_{q}(n) has generating function

∑_{n=0}^{∞} P_{q}(n)x^{n} = ∑_{\{a_{1},...a_{q}\}⊆D} \frac{x^{a_{1}}}{1 − x^{a_{1}}} ⋯ \frac{x^{a_{q}}}{1 − x^{a_{q}}} .

If R_{q}(n) is defined by

∑_{n=0}^{∞} R_{q}(n)x^{n} = ∑_{\{a_{1},...a_{q}\}⊆[n]} \frac{x^{a_{1}}}{1 − x^{a_{1}}} ⋯ \frac{x^{a_{q}}}{1 − x^{a_{q}}} ,

where [n] = {1, …, n}, then P_{q}(n) ≤ R_{q}(n).

There are \binom{n}{q} subsets of [n] of size q. Also, the coefficient of x^{n} in

(x^{a_{1}} + x^{2a_{1}} + ⋯) ⋯ (x^{a_{q}} + x^{2a_{q}} + ⋯)

is less than or equal to the coefficient of x^{n} in

(x + x^{2} + ⋯)^{q} = ∑_{m=q}^{∞} \binom{m − 1}{q − 1}x^{m},

so

P_{q}(n) ≤ \binom{n}{q}\binom{n − 1}{q − 1} ≤ n^{2q−1}.

Any partition n = n_{1}a_{1} + ⋯ n_{q}a_{q}, where a_{1}, …, a_{q} ∈ A, gives rise to a partition of n − a_{i} for i = 1, …, q, namely

n − a_{1} = (n_{1} − 1)a_{1} + n_{2}a_{2} + ⋯ + n_{q}a_{q},
n − a_{2} = n_{1}a_{1} + (n_{2} − 1)a_{2} + ⋯ + n_{q}a_{q},
⋮
n − a_{q} = n_{1}a_{1} + n_{2}a_{2} + ⋯ + (n_{q} − 1)a_{q}.

Note that no two distinct partitions of n can give rise to the same partition of any m < n in this way, and so

∑_{q=1}^{n} qP_{q}(n) ≤ ∑_{m=0}^{n−1} p_{D}(m).

Now if t ∈ ℕ, then

p_{D}^{(−1)}(n) = ∑_{m=0}^{n} p_{D}(m)

≥ p_{D}(n) + ∑_{q=1}^{n} qP_{q}(n)

= (t + 1)p_{D}(n) + ∑_{q=1}^{n}(q − t)P_{q}(n)

≥ (t + 1)p_{D}(n) − (t − 1) ∑_{q=1}^{t−1} P_{q}(n)

≥ (t + 1)p_{D}(n) − (t − 1)^{2}n^{2t−3},

and the theorem is proved.

For the remainder of this section, we follow the approach of Bateman and Erdős [5] and simultaneously make the results explicit by applying them to the special case under consideration. To be consistent, we shall assume k ≥ 0, and use the following notation:

Notation 1. Let B be the least k+2 elements of A, and let C = A\B. B_{1} = {p_{k+3}^{ℓ}, p_{k+4}^{ℓ}, …, p_{k+2t}^{ℓ}} be the least 2t − 2 elements of C, where t is determined as in the statement of Theorem 1.1 from the values of k and ℓ in question. Furthermore, let

g = (\frac{2}{b_{0}} )^{k+1} (k + 2)^{2ℓ(k+1)+1}, and  (10)
h = 3(k + 2)^{2ℓ(k+2)}g = 3 (\frac{2}{b_{0}} )^{k+1} (k + 2)^{4ℓk+6ℓ+1}.

Finally, let us remark that numerous constants shall be defined in the subsequent argument. Their definitions shall remain consistent throughout.

Note that the right hand side of (10) is increasing in k and ℓ, so g ≥ 16/b_{0} = 6.04 . . ..

Lemma 3.1. For all n ≥ 0, we have

p_{B}^{(k)}(n) ≥ 1 − g.  (11)

Proof. Since |B| = k + 2, g_{B}^{(k)}(n) is linear in n, and g_{B}^{(k+1)}(n) is a constant function. By Lemma 2.1,

g_{B}^{(k)}(n) = ∑_{h=1}^{2} α_{h}\binom{n + h − 1}{h − 1}

where α_{2} = (p_{1} ⋯ p_{k+2})^{−ℓ}. Substituting x = 0 into (5) and (6) gives

α_{1} + α_{2} + ∑_{q∈B} ∑_{j=1}^{q−1} β(ζ_{q}^{j}) = 1.

Hence,

g_{B}^{(k)}(n) = (p_{1} ⋯ p_{k+2})^{−ℓ}n + 1 − ∑_{q∈B} ∑_{j=1}^{q−1} β(ζ_{q}^{j}),

so

p_{B}^{(k)}(n) = g_{B}^{(k)}(n) + ψ_{B}^{(k)}(n)

= (p_{1} ⋯ p_{k+2})^{−ℓ}n + 1 − ∑_{q∈B} ∑_{j=1}^{q−1}(1 − ζ_{q}^{jn})β(ζ_{q}^{j})

≥ (p_{1} ⋯ p_{k+2})^{−ℓ}n + 1 − ∑_{q∈B} ∑_{j=1}^{q−1} |1 − ζ_{q}^{jn}||β(ζ_{q}^{j})|

≥ (p_{1} ⋯ p_{k+2})^{−ℓ}n + 1 − 2 ∑_{q∈B} ∑_{j=1}^{q−1} |β(ζ_{q}^{j})|

≥ (p_{1} ⋯ p_{k+2})^{−ℓ}n + 1 − (\frac{2}{b_{0}} )^{k+1} ∑_{q∈B} q^{k+1}

≥ 1 − (\frac{2}{b_{0}} )^{k+1} ∑_{q∈B} q^{k+1}.

Now, it is easy to see that

∑_{q∈B} q^{k+1} ≤ Q_{0}^{k+1}(k + 2) ≤ (k + 2)^{2ℓ(k+1)+1},

where Q_{0} = max (B). From this, the Lemma follows. Lemma 3.2. For all n ≥ 0, we have

1 + |p_{B}^{(k+1)}(n)| < g − 1.  (12)

Proof. Note that

g_{B}^{(k+1)}(n) = (p_{1} ⋯ p_{k+2})^{−ℓ}.

Making use of Theorem 2.1, we see that

g − 2 − |p_{B}^{(k+1)}(n)| ≥g − 2 − (p_{1} ⋯ p_{k+2})^{−ℓ} − |ψ_{B}^{(k+1)}(n)|
≥g − 2 − (p_{1} ⋯ p_{k+2})^{−ℓ} − \frac{2^{k}}{b_{0}^{k+1}} ∑_{q∈B} q^{k+1}
≥ ∑_{i=1}^{k+2} ((\frac{2(k + 2)^{2ℓ}}{b_{0}} )^{k+1} − \frac{1}{2} (\frac{2p_{i}^{ℓ}}{b_{0}} )^{k+1})

− 2 − (p_{1} ⋯ p_{k+2})^{−1}.

Observe that for a fixed i, 1 ≤ i ≤ k + 2, the expression

(\frac{2(k + 2)^{2ℓ}}{b_{0}} )^{k+1} − \frac{1}{2} (\frac{2p_{i}^{ℓ}}{b_{0}} )^{k+1} ,

is positive and increasing in ℓ, for ℓ ≥ 1, so,

(\frac{2(k + 2)^{2ℓ}}{b_{0}} )^{k+1} − \frac{1}{2} (\frac{2p_{i}^{ℓ}}{b_{0}} )^{k+1} ≥ (\frac{2(k + 2)^{2}}{b_{0}} )^{k+1} − \frac{1}{2} (\frac{2p_{i}}{b_{0}} )^{k+1}

≥ (\frac{2(k + 2)^{2}}{b_{0}} )^{k+1} − \frac{1}{2} (\frac{2p_{k+2}}{b_{0}} )^{k+1}

≥ \frac{2(k + 2)^{2}}{b_{0}} − \frac{p_{k+2}}{b_{0}}

≥ \frac{4}{b_{0}} + \frac{(k + 2)^{2} − p_{k+2}}{b_{0}}

≥ \frac{4}{b_{0}} .

Hence,

g − 2 − |p_{B}^{(k+1)}(n)| ≥ (k + 2)\frac{4}{b_{0}} − 2 − (p_{1} ⋯ p_{k+2})^{−1}

≥ \frac{8}{b_{0}} − \frac{13}{6} = 0.855167405 … > 0,

that is,

1 + |p_{B}^{(k+1)}(n)| < g − 1.

Corollary 3.1.

\frac{p_{B}^{(k)}(n)}{1 + |p_{B}^{(k+1)}(n)|} ≥ 2 if n ≥ h.  (13)

Proof. It follows from the proof of Lemma 3.1 that

p_{B}^{(k)}(n) ≥ (p_{1} ⋯ p_{k+2})^{−ℓ}n + 1 − g
> (p_{1} ⋯ p_{k+2})^{−ℓ}n − g.

The Corollary follows from this, together with Lemma 3.2 and the fact that

p_{1} ⋯ p_{k+2} ≤ (k + 2)^{2(k+2)}.

Lemma 3.3. There is an h_{1} ∈ ℕ such that such that n ≥ h_{1} implies

\frac{(t − 1)^{2}}{t + 1} \frac{n^{2t−3}}{p_{C}^{(−1)}(n)} ≤ \frac{(t − 1)^{2}}{t + 1} \frac{n^{2t−3}}{p_{B_{1}}^{(−1)}(n)} ≤ \frac{1}{t + 1}.  (14)

Proof. The first inequality is a consequence of Proposition 3.1. Note that

t ≥ 6 (\frac{2}{b_{0}} )^{3(k+1)} (k + 2)^{8ℓk+10ℓ+3} − 1

≥ 6 (\frac{2}{b_{0}} )^{3k+3} 2^{8k+13} − 1

≥ \frac{3 · 2^{16}}{b_{0}^{3}} (\frac{2^{11}}{b_{0}^{3}} )^{k} .

Hence

log t ≥ log (\frac{3 · 2^{16}}{b_{0}^{3}} ) + k log (\frac{2^{11}}{b_{0}^{3}} ).

since log t ≤ t/e, if we let M = e log (2^{11}/b_{0}^{3}), then

k ≤ \frac{t}{M} .

Choose r_{0} and d_{B_{1}} with respect to the set B_{1} as in Proposition 2.1, and let Q = p_{k+2t}^{ℓ} = max (B_{1}). It is clear that t ≥ ⌊6(2/b_{0})^{3}2^{13}⌋ = 21192, which we denote by t_{0}. By equation (9), we have that

r_{0} ≤ \frac{2π}{Q} ≤ \frac{2π}{(2t)^{ℓ}} ≤ \frac{π}{t_{0}} .

We also have that

r_{0} ≥ \frac{b_{4}}{Q^{2}} ≥ \frac{b_{4}}{(k + 2t)^{4ℓ}} ,

and

d_{B_{1}} ≥ b_{1}^{∑_{q∈B_{1}} q} (b_{2}Q^{b_{3}}e^{− \frac{log^{2} Q}{log 2}} )^{2t−2}

≥ b_{1}^{(k+3)^{ℓ}(2t−2)} (b_{2}(k + 2t)^{b_{3}ℓ}(k + 2t)^{− \frac{2ℓ log (k+2t)}{log 2}} )^{2t−2}

= (\frac{b_{2} · b_{1}^{(k+3)^{ℓ}}(k + 2t)^{b_{3}ℓ}}{(k + 2t)^{\frac{2ℓ log (k+2t)}{log 2}}} )^{2t−2}

Let us now bound p_{B_{1}}^{(−1)}(n) from below. Assume that n ≥ 2t, and let b_{5} = 1/M + 2 = 2.078207555 …, and b_{7} = t_{0}/(t_{0} − π). Making use of Theorem 2.1, we have

p_{B_{1}}^{(−1)}(n) =g_{B_{1}}^{(−1)}(n) + ψ_{B_{1}}^{(−1)}(n)
≥α_{2t−1}\binom{n + 2t − 2}{2t − 2} − ∑_{h=1}^{2t−2} |α_{h}|\binom{n + h − 1}{h − 1}

− |ψ_{B_{1}}^{(−1)}(n)|

≥\frac{(p_{k+3} ⋯ p_{k+2t})^{−ℓ}n^{2t−2}}{(2t − 2)!} − \binom{n + 2t − 3}{2t − 3} ∑_{h=1}^{2t−2} |α_{h}|

− \frac{1}{b_{0}^{2t−2}} ∑_{m=k+3}^{k+2t} p_{m}^{ℓ(2t−2)}

≥\frac{(k + 2t)^{−ℓ(2t−2)}n^{2t−2}}{(2t − 2)!} − \frac{(n + 2t − 3)^{2t−3}}{(2t − 3)!} ∑_{h=1}^{2t−2} \frac{r_{0}^{h}}{r_{0}^{2t−1}d_{B_{1}}}

− \frac{1}{b_{0}^{2t−2}} (2t − 2)(k + 2t)^{2ℓ(2t−2)}

≥\frac{(b_{5}t)^{−ℓ(2t−2)}n^{2t−2}}{(2t − 2)!} − \frac{n^{2t−3}2^{2t−3}}{(2t − 3)!} \frac{1}{(1 − r_{0})r_{0}^{2t−2}d_{B_{1}}}

− \frac{(2t − 2)(k + 2t)^{2ℓ(2t−2)}}{b_{0}^{2t−2}}

≥\frac{(b_{5}t)^{−ℓ(2t−2)}n^{2t−2}}{(2t − 2)!} − \frac{b_{7}n^{2t−3}2^{2t−3}}{(2t − 3)!} (\frac{(k + 2t)^{(4−b_{3})ℓ+ \frac{2ℓ log (k+2t)}{log 2}}}{b_{4}b_{2}b_{1}^{(k+3)^{ℓ}}} )^{2t−2}

− \frac{2t(b_{5}t)^{2ℓ(2t−2)}}{b_{0}^{2t−2}} .

Observe that

(k + 2t)^{(4−b_{3})ℓ+ \frac{2ℓ log (k+2t)}{log 2}}

≤ (b_{5}t)^{(4−b_{3})ℓ+ \frac{2ℓ log Ct}{log 2}}

= e^{ℓ(log b_{5}+log t)((4−b_{3}+ \frac{2 log C}{log 2} )+ \frac{2 log t}{log 2})}

= e^{ℓ(\frac{2}{log 2} log^{2} t+(4−b_{3}+ \frac{4 log b_{5}}{log 2} ) log t+(4−b_{3}+ \frac{4 log b_{5}}{log 2} ) log b_{5})}

≤ e^{b_{6}ℓ log^{2} t},

where b_{6} is a constant determined as follows. Let x_{0} = log t_{0}. Then we may take

b_{6} = \frac{2}{log 2} + (4 − b_{3} + \frac{4 log b_{5}}{log 2} ) \frac{1}{x_{0}} + (4 − b_{3} + \frac{4 log b_{5}}{log 2} ) \frac{log b_{5}}{x_{0}^{2}}

= 3.523150893 ….

It suffices to select h_{1} such that for n ≥ h_{1},

p_{B_{1}}^{(−1)}(n)n^{−(2t−3)} ≥ (t − 1)^{2}.  (15)

Observe that (15) is implied by

\frac{(b_{5}t)^{−ℓ(2t−2)}n}{(2t − 2)!} − \frac{b_{7}}{2(2t − 3)!} (\frac{2e^{b_{6}ℓ log^{2} t}}{b_{4}b_{2}b_{1}^{(k+3)^{ℓ}}} )^{2t−2} − \frac{2t(b_{5}t)^{2ℓ(2t−2)}}{n^{2t−3}b_{0}^{2t−2}} ≥ (t − 1)^{2},

which is equivalent to

n ≥ (b_{5}t)^{ℓ(2t−2)}×

(b_{7}(t − 1) (\frac{2e^{b_{6}ℓ log^{2} t}}{b_{4}b_{2}b_{1}^{(k+3)^{ℓ}}} )^{2t−2} + \frac{2t(b_{5}t)^{2ℓ(2t−2)}(2t − 2)!}{n^{2t−3}b_{0}^{2t−2}} + (t − 1)^{2}(2t − 2)!) .  (16)

The inequality

e^{n}n! ≤ n^{n+1},

holds for n ≥ 7. This implies that

\frac{(2t − 2)!}{(2t)^{2t−3}} ≤ \frac{(2t)^{3}}{e^{2t}(2t − 1)}.

Thus, since n ≥ 2t by assumption, (16) is implied by

n ≥ (b_{5}t)^{ℓ(2t−2)}(A_{1} + A_{2} + A_{3}),

where

A_{1} = b_{7}t (\frac{2e^{b_{6}ℓ log^{2} t}}{b_{4}b_{2}b_{1}^{(k+3)^{ℓ}}} )^{2t−2}

A_{2} = \frac{16t^{4}(b_{5}t)^{2ℓ(2t−2)}}{(2t − 1)e^{2t}b_{0}^{2t−2}}
A_{3} = \frac{(t − 1)^{2}(2t)^{2t}}{(2t − 1)e^{2t}} .

The term A_{3} is negligible relative to A_{2}, yet A_{1} and A_{2} are not easily compared since one or the other may dominate depending on the values chosen for k, and ℓ. None the less, we may simplify matters a little by absorbing A_{3} into A_{2} in the following way:

\frac{A_{2} + A_{3}}{t^{3}(b_{5}t)^{2ℓ(2t−2)}/(e^{2t}b_{0}^{2t−2})} ≤ \frac{16t}{2t − 1} + \frac{b_{0}^{2t−2}(2t)^{2t}}{t(2t − 1)(b_{5}t)^{2(2t−2)}}

= \frac{16t}{2t − 1} + (\frac{4t}{2t − 1}) (\frac{2b_{0}}{b_{5}^{2}t} )^{2t−2}

≤ \frac{16t_{0}}{2t_{0} − 1} + (\frac{4t_{0}}{2t_{0} − 1}) (\frac{2b_{0}}{b_{5}^{2}t_{0}} )^{2t_{0}−2}

≤ 8.000188756.

So, let

A′_{2} = 8.000188756\frac{t^{3}(b_{5}t)^{2ℓ(2t−2)}}{e^{2t}b_{0}^{2t−2}} .

Then we may take

h_{1} = (b_{5}t)^{ℓ(2t−2)}(A_{1} + A′_{2}).

Remark 3. Note that

t = ⌊6 (\frac{2}{b_{0}} )^{3(k+1)} (k + 2)^{8ℓk+10ℓ+3}⌋ = ⌊2g^{2}h⌋,

and so

\frac{1}{t + 1} ≤ \frac{1}{2(g + 1)(g − 1)h}.

Lemma 3.4. There exists an N = N(k, ℓ) > 0, such that if n ≥ N, then

p^{(k)}(n) ≥ p_{C}^{(−1)}(n) > 0.

Proof. The second inequality is obvious. For the first, by Proposition 3.1, Theorem 3.1, Lemma 3.3 and Remark 3, we have that for n ≥ h_{1},

\frac{p_{C}(n)}{p_{C}^{(−1)}(n)} ≤ \frac{1}{t + 1} + \frac{(t − 1)^{2}}{t + 1} \frac{1}{p_{B_{1}}^{(−1)}(n)n^{−(2t−3)}} ≤ \frac{1}{(g + 1)(g − 1)h}.  (17)

Now, using, (11), (12), (13), (17), and the identity

p^{(k)}(n) = ∑_{m=0}^{n} p_{B}^{(k)}(n − m)p_{C}(m),

we have that for n ≥ h + h_{1} − 1,

p^{(k)}(n) ≥2 ∑_{0≤m≤n−h}(1 + |p_{B}^{(k+1)}(n − m)|)p_{C}(m)

− (g − 1) ∑_{n−h<m≤n}(1 + |p_{B}^{(k+1)}(n − m)|)p_{C}(m)

≥2 ∑_{m=0}^{n}(1 + |p_{B}^{(k+1)}(n − m)|)p_{C}(m) − (g + 1)(g − 1) ∑_{n−h<m≤n} p_{C}(m)

≥2 ∑_{m=0}^{n}(1 + |p_{B}^{(k+1)}(n − m)|)p_{C}(m)

− (g^{2} − 1) ( ∑_{n−h<m≤n}^{n} \frac{p_{C}(m)}{p_{C}^{(−1)}(m)}) p_{C}^{(−1)}(n)

≥ (2 − (g^{2} − 1) ∑_{n−h<m≤n} \frac{p_{C}(m)}{p_{C}^{(−1)}(m)}) × ∑_{m=0}^{n}(1 + |p_{B}^{(k+1)}(n − m)|)p_{C}(m)

≥ ∑_{m=0}^{n}(1 + |p_{B}^{(k+1)}(n − m)|)p_{C}(m)

≥ ∑_{m=0}^{n} p_{C}(m)
=p_{C}^{(−1)}(n).

Proof of Theorem 1.1.

By the proofs of Lemmas 3.3 and 3.4, it suffices us to choose N ≥ h+h_{1} = h+(b_{5}t)^{ℓ(2t−2)}(A_{1}+ A′_{2}). First observe that A′_{2} ≥ 2t. The quantity (b_{5}t)^{ℓ(2t−2)}A_{1} may be simplified further with an upper bound. Let

b_{9} = \frac{log b_{5}}{x_{0}^{2}} + \frac{1}{x_{0}} + b_{6} = 3.630910490 …,

and

b_{10} = \frac{2}{b_{2}b_{4}} .

Then

(b_{5}t)^{ℓ(2t−2)}A_{1} = b_{7}t (\frac{b_{10}(b_{5}t)^{ℓ}e^{b_{6}ℓ log^{2} t}}{b_{1}^{(k+3)^{ℓ}}} )^{2t−2}

= b_{7}t (\frac{b_{10}e^{ℓ(log b_{5}+log t+b_{6} log^{2} t)}}{b_{1}^{(k+3)^{ℓ}}} )^{2t−2}

≤ b_{7}t (\frac{b_{10}e^{b_{9}ℓ log^{2} t}}{b_{1}^{(k+3)^{ℓ}}} )^{2t−2}

Denote

A′_{1} = b_{7}t (\frac{b_{10}e^{b_{9}ℓ log^{2} t}}{b_{1}^{(k+3)^{ℓ}}} )^{2t−2} .

We will use the fact that h ≤ t to absorb h into (b_{5}t)^{ℓ(2t−2)}A′_{2} in the following way:

\frac{h + (b_{5}t)^{ℓ(2t−2)}A′_{2}}{t^{3}(b_{5}t)^{3ℓ(2t−2)}/(e^{2t}b_{0}^{2t−2})} ≤ \frac{e^{2t}b_{0}^{2t−2}}{t^{2}(b_{5}t)^{3(2t−2)}} + 8.000188756

= \frac{e^{2}}{t^{2}} (\frac{eb_{0}}{b_{5}^{3}t^{3}} )^{2t−2} + 8.000188756

≤ \frac{e^{2}}{t_{0}^{2}} (\frac{eb_{0}}{b_{5}^{3}t_{0}^{3}} )^{2t_{0}−2} + 8.000188756

≤ 8.000188757

Letting b_{8} = 8.0002, we may take

N = A′_{1} + \frac{b_{8}t^{3}(b_{5}t)^{3ℓ(2t−2)}}{e^{2t}b_{0}^{2t−2}}

= b_{7}t (\frac{b_{10}e^{b_{9}ℓ log^{2} t}}{b_{1}^{(k+3)^{ℓ}}} )^{2t−2} + \frac{b_{8}t^{3}(b_{5}t)^{3ℓ(2t−2)}}{e^{2t}b_{0}^{2t−2}} .

We conclude the proof by restructuring the constants as follows:

a_{1} = b_{7}
a_{2} = b_{10}^{2}
a_{3} = e^{2b_{9}}
a_{4} = b_{1}^{2}
a_{5} = e^{−2}b_{8}
a_{6} = e^{−2}b_{0}^{−2}
a_{7} = b_{5}.
□

4 Asymptotic results

Observe that as k → ∞, log t ≍ k log k, when ℓ remains fixed. This implies that if ℓ > 2, then

\frac{a_{3}^{ℓ log^{2} t}}{a_{4}^{(k+2)^{ℓ}}} → 0, as k → ∞,

and so in this situation, the second term dominates in the expression for N(k, ℓ) in Theorem 1.1.

If ℓ = 1 or 2, then

\frac{a_{3}^{ℓ log^{2} t}}{a_{4}^{(k+2)^{ℓ}}} = e^{λ_{1}(k)},

where λ_{1}(k) ≍ k^{2} log^{2} k, and

(a_{7}t)^{6ℓ} = e^{λ_{2}(k)},

where λ_{2}(k) ≍ k log k. In this case the first term dominates in the expression for N(k, ℓ). Thus we have proved the following corollary to Theorem 1.1:

Corollary 4.1. Let ℓ ∈ ℕ be fixed. Then as k → ∞,

F (k, ℓ) = O (t (\frac{a_{2}a_{3}^{ℓ log^{2} t}}{a_{4}^{(k+3)^{ℓ}}} )^{t−1}) , if ℓ = 1, 2;

F (k, ℓ) = O (t^{3} (a_{6}(a_{7}t)^{6ℓ})^{t−1}) , if ℓ > 2.

Theorem 1.2 follows from Corollary 4.1 simply by taking logarithms.

5 Acknowledgements

The author is supported by an NSERC CGS D research grant and wishes to acknowledge the Natural Sciences and Engineering Research Council for their generous funding, as well as the support of his supervisor Dr. Izabella Laba.

References

[1] G. H. Hardy, and S. Ramanujan, Asymptotic formulae for the distribution of integers of various types, Proc. London Math. Soc., Ser. 2, 16 (1916), 112–132.

[2] P. Erdős, On an elementary proof of some asymptotic formulas in the theory of partitions, Ann. Math., 43 (1942), 437–450.

[3] C. G. Haselgrove, and H. N. V. Temperley, Asymptotic formulae in the theory of partitions, Proc. Cambridge Philos. Soc., 50 Part 2 (1954), 225–241.

[4] O. P. Gupta, and S. Luthra, Partitions into primes, Proc. Nat. Inst. Sci. India, A21 (1955), 181–184.

[5] P. T. Bateman, and P. Erdős, Monotonicity of partition functions, Mathematika, 3 (1956), 1–14.

[6] P. T. Bateman, and P. Erdős, Partitions into primes, Publ. Math. Debrecen, 4 (1956), 198–200.

[7] Takayoshi Mitsui, On the partitions of a number into the powers of prime numbers, J. Math. Soc. Japan, 9 (1957), 428–447.

[8] E. Grosswald, Partitions into prime powers, Michigan Math. J., 7 (1960), 97–122.

[9] S. M. Kerawala, On the asymptotic values of ln p_{A}(n) and ln p_{A}^{(}d)(n) with A as the set of primes, J. Natur. Sci. and Math., 9 (1969), 209–216.

[10] L. B. Richmond, Asymptotic relations for partitions, J. Number Theory, 7 (1975), 389– 405.

[11] L. B. Richmond, Asymptotic results for partitions (I) and the distribution of certain integers, J. Number Theory, 8 (1976), 372–389.

[12] L. B. Richmond, Asymptotic results for partitions (II) and a conjecture of Bateman and Erdős, J. Number Theory, 8 (1976), 390–396.

[13] L. B. Richmond, Asymptotic relations for partitions, Trans. Amer. Math. Soc., 219 (1976), 379–385.

2000 Mathematics Subject Classification: Primary 05A17; Secondary 11P81. Keywords: partition function, difference function.

(Concerned with sequences \underline{A000607} and \underline{A090677}.)

Received April 10 2006; revised version received November 18 2006. Published in Journal of Integer Sequences, December 29 2006.

Return to Journal of Integer Sequences home page.