PARTITION IDENTITIES II. THE RESULTS OF BATEMAN AND ERDŐS

JASON P. BELL AND STANLEY N. BURRIS

Abstract. This paper shows that the natural setting for the Bateman and Erdős study of monotonicity of the kth difference of partition functions a(n) is the class of partition identities

A(x) := ∑_{n=0}^{∞} a(n)x^{n} = ∏_{n=1}^{∞}(1 − x^{n})^{−p(n)}

with polynomially bounded p(n). The results include a proof of a generalized version of their conjecture for polynomially bounded p(n)—their conjecture was for p(n) ∈ {0, 1}.

1. Introduction

In Part I [6] the property a(n − 1)/a(n) → 1 of partition identities^{1}

(1)  A(x) := ∑_{n=0}^{∞} a(n)x^{n} = ∏_{n=1}^{∞}(1 − x^{n})^{−p(n)}

was the topic of investigation. Unless explicitly stated otherwise, it is assumed that the p(n) , and hence the a(n) , are nonnegative integers. When a partition identity is mentioned without a specific reference then the reader can assume (1) above is meant, using the two counting functions p(n) and a(n) .

Date: June 15, 2004.

1991 Mathematics Subject Classification. Primary 03C13, 05A16, 11P99, 41A60; Secondary 11N45, 11N80, 11U99, 60J20.

Key words and phrases. RT_{1}, partition identities, Bateman and Erdős results, Bateman and Erdős conjecture.

The second author would like to thank NSERC for support of this research.

1In [7] the models A = (A, P, +, 0, ∥ ∥) of partition identities are called additive number systems, and the partition identity of an additive number system is called its fundamental identity. This paper does not assume the reader is familiar with additive number systems; however there are a couple of places in this paper where the development is completely transparent from the point of view of such systems. Such places have a footnote attached to explain this. For a basic reference on additive (and multiplicative) number systems see [7].

The notation used here follows that of Part I [6]:

a(n)  partition (count) function
p(n)  component (count) function
A(x) := ∑ a(n)x^{n} generating function for the partitions
P(x) := ∑ p(n)x^{n} generating function for the components
rank(p) := ∑ p(n) rank of the partition identity.

There are three main results proved in this paper:

(a) Theorem 3.5 gives a full generalization of the Bateman and Erdős monotonicity results for the kth difference a^{(k)}(n) of a partition function a(n) to the cases where the component function p(n) is polynomially bounded. These results show that a^{(k)}(n) is eventually monotone iff a very simple property called BE_{k}(n) holds for p(n); and further properties concerning the rate of growth of a^{(k)}(n) hold if p(n) satisfies BE_{k}(n).

(b) Theorem 3.6 gives an enormous class of partition identities for which all the conclusions from Theorem 3.5 about the behavior of the kth difference a^{(k)}(n) of the partition function a(n) hold, even though the premisses are quite different from those of Theorem 3.5.

(c) Theorem 4.2 gives a natural extension of the Bateman and Erdős Conjecture to partition identities with polynomially bounded component function p(n), an extension which is proved to be true.

The possibility of further generalizations is discussed briefly, and there are examples to show that the above theorems are essentially best possible.

2. The Property RT_{1}

The property

\frac{f(n − 1)}{f(n)} → 1 ,

where f(n) is eventually positive, was discussed in some detail in Part I [6]. It plays a significant role in the results of Bateman and Erdős and is essential to Compton’s approach to proving logical 0–1 laws. When dealing with partition functions a(n) it is convenient to use interchangeably any of the phrases:

(i) a(n) satisfies RT_{1}, (ii) A(x) satisfies RT_{1}, or (iii) the partition identity satisfies RT_{1}. There are three basic results concerning when a partition function

a(n) satisfies RT_{1} , that is, when a(n − 1)/a(n) → 1 as n → ∞. But first some definitions. A partition identity is reduced if

gcd {n : p(n) > 0} = 1 .

It is well known that a(n) is eventually positive iff the partition identity is reduced^{2}—see, for example, p. 43 of [7]. Given a partition identity let

d := gcd {n : p(n) > 0}
p^{⋆}(n) := p(nd)
a^{⋆}(n) := a(nd) .

Then

(2)  A^{⋆}(x) := ∑_{n=0}^{∞} a^{⋆}(n)x^{n} = ∏_{n=1}^{∞}(1 − x^{n})^{−p^{⋆}(n)} .

This is the reduced form of the partition identity (1). The reduced form of a partition identity is reduced; and a reduced partition identity is the same as its reduced form.

Here are the three basic theorems concerning conditions on a partition identity that guarantee a(n) satisfies RT_{1}:

• Theorem A. (Bell [4]) Given a reduced partition identity, if p(n) is polynomially bounded, that is, p(n) = O(n^{γ}) for some γ ∈ ℝ, then a(n) satisfies RT_{1} . This generalizes a result of Bateman and Erdős [2] that says if p(n) ∈ {0, 1} then RT_{1} holds.

• Theorem B. (Bell and Burris [5]) If p(n − 1)/p(n) → 1 as n → ∞ then a(n) satisfies RT_{1} .

• Theorem C. (Stewart’s Sum Theorem:^{3} (see [7], p. 85) If

∑_{n=0}^{∞} a_{j}(n)x^{n} = ∏_{n=1}^{∞}(1 − x^{n})^{−p_{j}(n)} (j = 1, 2)

and each a_{j}^{⋆}(n) satisfies RT_{1} then a^{⋆}(n) also satisfies RT_{1} , where

∑_{n=0}^{∞} a(n)x^{n} = ∏_{n=1}^{∞}(1 − x^{n})^{−p(n)}

with p(n) = p_{1}(n) + p_{2}(n) . Repeated use will be made of (iterations of) the following simple

application of Stewart’s Sum Theorem:

if A(x) is a generating function satisfying RT_{1} then, for d a positive integer, A(x)·(1−x^{d})^{−1} is again a generating function satisfying RT_{1}.

2The property BE_{0} in Section 3 says that the partition identity is reduced.

3This theorem says that the sum of two additive number systems whose reduced forms satisfy RT_{1} is again an additive number system whose reduced form satisfies RT_{1}.

A key feature of these three results is that they are proved by elementary means—one does not need the traditional methods of “hard asymptotics”, namely the Cauchy integral theorem, the saddle-point methods, etc.

We adopt the convention of [7] that upper case bold letters name power series whose coefficients are given by the corresponding lower case italic letters, for example

F(x) = ∑_{n=0}^{∞} f(n)x^{n} .

By this convention A(x) is the power series ∑ a(n)x^{n} and A_{1}(x) is the power series ∑ a_{1}(n)x^{n}, etc. It will be convenient to define coefficients f(n) of a power series F(x) to be 0 for negative values of n.

3. The Bateman and Erdős Monotonicity Results Revisited

Given a subset J of the positive integers let a(n) be the number of ways to express n as a sum of integers from J . The function a(n) and the set J are connected by the partition identity

∑_{n=0}^{∞} a(n)x^{n} = ∏_{j∈J}^{∞}(1 − x^{j})^{−1} .

The kth difference a^{(k)}(n) of a(n) is given by

∑_{n=0}^{∞} a^{(k)}(n)x^{n} = (1 − x)^{k} ∏_{j∈J}^{∞}(1 − x^{j})^{−1} .

In their 1956 paper [2] Bateman and Erdős showed that a^{(k)}(n) is eventually positive iff the following property, called P_{k}, holds:^{4}

• J has at least k + 1 elements,

• for j_{1}, …, j_{k} ∈ J ,

gcd (J \ {j_{1}, …, j_{k}}) = 1 .

A key ingredient in their proof was to show that a(n) satisfies RT_{1} . They go on to conjecture that if P_{k} holds then

4Our choice of notation to describe a partition identity is quite different from that of Bateman and Erdős. They use p(n) to count the number of ways to partition n (as a sum of elements of J), whereas our use of p(n) follows [7] where it is used to denote the number of indecomposables, or ‘primes’, in an additive number system. So, for the partition identities they consider, their p(n) is our a(n) .

(3)  \frac{a^{(k+1)}(n)}{a^{(k)}(n)} = O(\frac{1}{\sqrt{n}}) .

Two major improvements to the work of Bateman and Erdős have been published by Bell, namely the polynomial bound Theorem A mentioned earlier, and the following result from [3].

• Theorem D. The Bateman and Erdős Conjecture (3) is cor-

rect. Clearly Bateman and Erdős are studying partition identities with

the restriction that p(n) can only take the values 0 and 1. Our goal (Theorems 3.3, 4.2) is to show that the natural home of the monotonicity results of Bateman and Erdős, and their conjecture, is the collection of partition identities with polynomially bounded p(n) .

First the condition P_{k} is reformulated^{5} (and called BE_{k}) so that it makes sense for any component function p(n):

BE_{k} : \{  \begin{matrix}• rank(p) > k, \\ • for any q(n) satisfying the two conditions \\ \{ & \begin{matrix}0 ≤ q(n) ≤ p(n) , \\ ∑_{n} (p(n) − q(n)) = k \end{matrix} \\ one has \\ gcd \{n : q(n) > 0\} = 1 . \end{matrix}

Of course BE_{k} holds if k < 0 as the conditions on q(n) cannot be satisfied; and clearly BE_{k+1} implies BE_{k}. If a component function p(n) satisfies BE_{k} for all k then p(n) satisfies BE_{∞}. A simple and useful criterion for a component function to satisfy BE_{∞} is that it be eventually positive. In particular every component function p(n) that satisfies RT_{1} also satisfies BE_{∞}.

5From the point of view of additive number systems, BE_{k} is the obvious generalization of their P_{k}. The condition P_{k} says that the set of indecomposables of the system has at least k + 1 members, and if one removes any k members of this set then the gcd of the sizes of the remaining indecomposables is 1. This is precisely the definition of BE_{k}, giving a good example where the language and imagery of additive number systems (say as given in [7]) provides a valuable tool when studying partition identities. Using the language of additive number systems, our goal is to study when the kth difference a^{(k)}(n) of the counting function a(n) for an additive number system is eventually positive. The function a(n) counts the number of ways one can add indecomposables to get a ‘number’ of size n. The results of Bateman and Erdős apply to precisely the cases where one has at most one indecomposable of each size.

As a particular example of what Theorem 3.5 covers one has that if p(n) is polynomially bounded then: a(n) is eventually strictly increasing iff p(n) satisfies BE_{1} . Outside of Theorem 3.5 there is one well known result involving BE_{k} that should be mentioned, namely that any partition function a(n) is eventually positive iff its partition identity is reduced. Being reduced is the same as saying p(n) satisfies BE_{0}.

The next result is for partition identities of finite rank.

Proposition 3.1. Given a partition identity

∑_{n=0}^{∞} a(n)x^{n} = ∏_{n=1}^{∞}(1 − x^{n})^{−p(n)}

satisfying BE_{k} and such that r := rank(p) < ∞, let

D := ∏_{n≥1} n^{p(n)} .

Then

(4)  a^{(k)}(n) = \frac{1}{(r − k − 1)! · D} · n^{r−k−1} + O(n^{r−k−2}) .
(5)  \frac{a^{(k+1)}(n)}{a^{(k)}(n)} = 1 − \frac{a^{(k)}(n − 1)}{a^{(k)}(n)} = O(\frac{1}{n}) .

Proof. The proof follows exactly the same reasoning as that given by Bateman and Erdős (in Lemma 2 and Theorem 3 of [2]) for the case that p(n) ∈ {0, 1}, namely start with

a^{(k)}(n) = [x^{n}](1 − x)^{k} ∏_{n=0}^{∞}(1 − x^{n})^{−p(n)}

and apply complex partial fractions to the essentially finite product on the right. □

Lemma 3.2. Given a reduced partition identity

∑_{n=0}^{∞} a(n)x^{n} = ∏_{n=1}^{∞}(1 − x^{n})^{−p(n)}

one has:

(a) the a(n) are eventually positive;

(b) if rank(p) = ∞ then a(n) is super polynomial, that is,

lim_{n→∞} \frac{a(n)}{n^{γ}} = ∞ for any γ ∈ ℝ .

Proof. For a sufficiently large positive integer t the partition identity

∑_{n=0}^{∞} a_{t}(n)x^{n} = ∏_{n=1}^{t}(1 − x^{n})^{−p(n)}

is reduced; so a_{t}(n) is eventually positive by Proposition 3.1 (with k = 0). Then noting that a(n) ≥ a_{t}(n) gives (a).

Suppose rank(p) = ∞ and γ ∈ ℝ. Choose t a sufficiently large integer so that p(1) + ⋯ + p(t) − 1 > γ. Then n^{γ} = o(a_{t}(n)) by Proposition 3.1, so n^{γ} = o(a(n)), proving (b). □

Proposition 3.3. Given a partition identity

∑_{n=0}^{∞} a(n)x^{n} = ∏_{n=1}^{∞}(1 − x^{n})^{−p(n)} ,

let r = rank(p). One has

(a) lim_{n→∞} \frac{a(0) + ⋯ + a(n)}{n^{γ}} → ∞ for γ < r.

If p(n) = O(n^{γ}) then as n → ∞,

(b) \frac{a(n)}{a(0) + ⋯ + a(n)} = 1 − \frac{a(0) + ⋯ + a(n − 1)}{a(0) + ⋯ + a(n)} → 0 .

Proof. Let A(n) = a(0) + ⋯ + a(n) . The partition identity

(6)  ∑_{n=0}^{∞} A(n)x^{n} = (1 − x)^{−1} ∏_{n=1}^{∞}(1 − x^{n})^{−p(n)}

is clearly reduced; so Lemma 3.2 (b) gives (a). If p(n) = O(n^{γ}) then apply Bell’s Theorem A to (6) to show that A(n) satisfies RT_{1} , which is (b). □

The following gives a compactness result for BE_{k}.

Lemma 3.4. p(n) satisfies BE_{k} iff there is a p_{1}(n) such that (i) 0 ≤ p_{1}(n) ≤ p(n) ,

(ii) rank(p_{1}) < ∞, and

(iii) p_{1}(n) satisfies BE_{k}.

Proof. First note that if there is a p_{1}(n) satisfying conditions (i)–(iii) then clearly A(x) must satisfy BE_{k}. For the converse assume p(n) satisfies BE_{k}. If rank(p) < ∞ just let p_{1}(n) = p(n) .

Now suppose rank(p) = ∞. For any prime number π,

∑_{π∤n}p(n) > k .

Otherwise there is a q(n) satisfying the hypotheses of BE_{k} with q(n) = 0 whenever π ∤ n, which leads to π| gcd {n : q(n) > 0}, contradicting BE_{k}. Thus for each prime π one can choose a finite subset X_{π} of positive integers from {n : π ∤ n} such that

∑_{n∈X_{π}} p(n) > k .

Now choose a subset X of k + 1 positive integers n, each satisfying p(n) > 0 , say X = {n_{1}, …, n_{k+1}}. Then for any set Y of positive integers that contains X and any Z ⊂ Y with k elements one sees that some member of X is in Y \ Z; so if a prime π divides the gcd of Y \ Z then it must divide one of n_{1}, …, n_{k+1} . Let

Y = X ∪ ⋃_{j=1}^{k+1} ⋃_{π|n_{j}} X_{π} .

Then p_{1}(n) defined to be p(n) for n ∈ Y and 0 otherwise has the desired properties. □

The next theorem gives our generalization of the main results of Bateman and Erdős.

Theorem 3.5. Given a partition identity

∑_{n=0}^{∞} a(n)x^{n} = ∏_{n=1}^{∞}(1 − x^{n})^{−p(n)}

let r = rank(p). Then

(a) if p(n) satisfies BE_{k} then \frac{a^{(k)}(n)}{n^{γ}} → ∞ for γ < r − k − 1 .

If p(n) is polynomially bounded then

(b) the kth difference function a^{(k)}(n) is eventually positive iff p(n) satisfies BE_{k};

(c) if p(n) satisfies BE_{k} then a^{(k)}(n) satisfies RT_{1} .

Proof. First note that any reduced partition identity for which a^{(k)}(n) is eventually positive has p(n) satisfying BE_{k}. For if q(n) is as in the hypotheses of BE_{k} then, letting r(n) = p(n) − q(n) , from

∏_{n=1}^{∞}(1 − x^{n})^{r(n)} ∑_{n=1}^{∞} a^{(k)}(n)x^{n} = (1 − x)^{k} ∏_{n=1}^{∞}(1 − x^{n})^{−q(n)}

follows

∏_{r(n)>0}(1 + x + ⋯ + x^{n−1}) ∑_{n=1}^{∞} a^{(k)}(n)x^{n} = ∏_{n=1}^{∞}(1 − x^{n})^{−q(n)} .

As the coefficients of the power series obtained by multiplying out the left side are eventually positive, it follows that the gcd of the set of n for which q(n) > 0 must be 1. This is the condition BE_{k}.

To show that ‘p(n) satisfies BE_{k} implies that a^{(k)}(n) is eventually positive’ first note that (4) gives this for the case that rank(p) < ∞. Furthermore, for the case that rank(p) < ∞, (4) shows

(7)  a^{(k)}(n) → ∞ as n → ∞

holds iff k + 1 < rank(p).

So now assume that rank(p) = ∞, and decompose p(n) as p_{1}(n) + p_{2}(n) where rank(p_{1}) < ∞ and the generating function determined by p_{1}(n) has the property BE_{k}. For p_{1}(n) and p_{2}(n) introduce the partition identities

A_{j}(x) := ∑_{n=0}^{∞} a_{j}(n)x^{n} = ∏_{n=1}^{∞}(1 − x^{n})^{−p_{j}(n)} (j = 1, 2) .

By (7) one knows that there is a positive constant M such that

(8)  a_{1}^{(k)}(n) ≥ \begin{cases}−M & for all n \\ 2 & for n ≥ M. \end{cases}

Using the notation

A_{2}(n) := a_{2}(0) + ⋯ + a_{2}(n)

one has

a^{(k)}(n) = ∑_{j=1}^{n} a_{1}^{(k)}(n − j)a_{2}(j)

≥ ∑_{j=1}^{n−M} a_{1}^{(k)}(n − j)a_{2}(j) − ∑_{j=n−M+1}^{n} |a_{1}^{(k)}(n − j)|a_{2}(j)

≥ 2 ∑_{j=1}^{n−M} a_{2}(j) − M · ∑_{j=n−M+1}^{n} a_{2}(j)

= 2 ∑_{j=1}^{n} a_{2}(j) − (M + 2) · ∑_{j=n−M+1}^{n} a_{2}(j)
= 2A_{2}(n) − (M + 2) · (A_{2}(n) − A_{2}(n − M + 1))

= 2A_{2}(n) − (M + 2) · \frac{A_{2}(n) − A_{2}(n − M + 1)}{A_{2}(n)} · A_{2}(n) .

Since the fraction in the last line goes to 0 by Proposition 3.3 (b), it follows that eventually

a^{(k)}(n) > A_{2}(n) ,

showing that a^{(k)}(n) is eventually positive. This finishes the proof of (a): a^{(k)}(n) is eventually positive is equivalent to p(n) satisfies BE_{k}, given that p(n) is polynomially bounded.

To show (b), that p(n) satisfies BE_{k} implies a^{(k)}(n) grows much faster than n^{γ} for γ < rank(p) − k − 1 , first note that if rank(p) < ∞ then this follows from (4). Now assume that rank(p) = ∞. Given any γ one can choose the p_{1}(n) above to be such that rank(p_{1}) > γ + k + 2 . Then from

a_{1}^{(k)}(n) < a^{(k)}(n)
\frac{a_{1}^{(k)}(n)}{n^{γ}} → ∞ by (4)

one has the conclusion (b).

Item (c) follows from Stewart’s Sum Theorem since

A^{(k)}(x) = A_{1}^{(k)}(x) · A_{2}(x) ,

and using the facts that the reduced form of a_{2}(n) satisfies RT_{1} (by Theorem A as p_{2}(n) is polynomially bounded) and a_{1}^{(k)}(n) satisfies RT_{1} by (5). □

Looking over the proof of Theorem 3.5 (a), we actually showed every p(n) for which a^{(k)}(n) is eventually positive has the property BE_{k}. The last step of the proof that ‘p(n) satisfies BE_{k} implies a^{(k)}(n) is eventually positive’, where Bell’s Theorem A is used to show that a_{2}(n) satisfies RT_{1} , is the only obstacle to generalizing the Bateman and Erdős monotonicity proof to any generating function satisfying BE_{k}.

Examining the proof of (a) it is clear that one can take any p(n) satisfying BE_{k} and decompose it into p_{1}(n) + p_{2}(n) such that p_{1}(n) has all the properties needed in the proof. The only thing missing is that one does not know if a_{2}(n) satisfies RT_{1} . If indeed a_{2}(n) satisfies RT_{1} , then by Stewart’s Sum Theorem one sees that a(n) must also satisfy RT_{1} . This leads to the following:

Question 1. Suppose p(n) satisfies BE_{k}, where k ≥ 1, and a(n) satisfies RT_{1} . Does it follow that a^{(k)}(n) is eventually positive?

We are not able, under these hypotheses, to prove that decomposing p(n) into p_{1}(n)+p_{2}(n) as in the proof gives an a_{2}(n) that satisfies RT_{1} . Determining whether or not this must always be the case is equivalent to the following:

Question 2. Given a generating function A(x) , if

• the coefficients of (1 − x)^{−2} · A(x) satisfy RT_{1} does it follow that

• the coefficients of (1 − x)^{−1} · A(x) satisfy RT_{1}?

This does not seem overtly plausible. However, using Theorem 4.3 (the Eventual Sandwich Theorem from Part I [6] on partition identities), there is clearly an enormous range of partition identities for which all the conclusions from Theorem 3.5 concerning the behavior of a^{(k)}(n) hold, even though p(n) need not be polynomially bounded.

Theorem 3.6. Suppose the partition identity

(9)  ∑_{n=0}^{∞} ȧ(n)x^{n} = ∏_{n=1}^{∞}(1 − x^{n})^{−ṗ(n)}

is such that ṗ(n) satisfies RT_{1}. Then for any partition identity

(10)  ∑_{n=0}^{∞} a(n)x^{n} = ∏_{n=1}^{∞}(1 − x^{n})^{−p(n)}

with

ṗ(n) ≤ p(n) = O(ȧ(n)) ,

for n sufficiently large, one has:

(a) a^{(k)}(n) is eventually positive;

(b) \frac{a^{(k)}(n)}{n^{γ}} → ∞ for γ < rank(p) − k − 1 ;

(c) a^{(k)}(n) satisfies RT_{1} . In particular the hypotheses hold for functions ṗ(n) satisfying RT_{1}.

Proof. Since ṗ(n) satisfies RT_{1} one can split it into ṗ_{1}(n) + ṗ_{2}(n) such that

(i) rank(ṗ_{1}) < ∞ and satisfies BE_{k}, (ii) ṗ_{2}(n) satisfies RT_{1} .

Let

p_{1}(n) = ṗ_{1}(n) ,
p_{2}(n) = p(n) − ṗ_{1}(n) .

Then using this decomposition one can carry through the part of the proof of (a) in Theorem 3.5 for ‘p(n) satisfies BE_{k} implies a^{(k)}(n) is eventually positive’, but using Theorem 4.3 of Part I [6] (instead of Bell’s Theorem A) at the end to show ȧ_{2}(n) satisfies RT_{1} . The proofs of (b) and (c) are as in Theorem 3.5. □

Examining the proof it is clear that the property of ṗ(n) that is really needed is that it can be decomposed as ṗ_{1}(n) + ṗ_{2}(n) where

(i) rank(ṗ_{1}) < ∞ and satisfies BE_{k}, (ii) the coefficients of (1 − x)^{−1} · Ȧ_{2}(x) satisfy RT_{1} . To show how this theorem can be used several examples are given—

one can easily verify that the ṗ(n) (the lower bounds) satisfy RT_{1}. However to show that the upper bounds are O(ȧ(n)) uses substantial results from the literature (see §5 of Part I [6] for details).

Examples: If a partition identity satisfies one of the following conditions on p(n), where C_{1} > 0, ε > 0, s ≥ 1, and α ≥ 1:

(1) 1 ≤ p(n) = O(e^{π\sqrt{\frac{2}{3} n}}/n)

(2) C_{1} ≤ p(n) = O(e^{(π\sqrt{\frac{2}{3} C_{1}} − ε)\sqrt{n}}/n)

(3) C_{1}n^{α−1} ≤ p(n) = O(e^{C_{2}n^{α/(α+1)}}),

where C_{2} = (1 + \frac{1}{α})(C_{1}ζ(α + 1)Γ(α + 1))^{1/(α+1)} − ε

(4) e^{C_{1}n^{α/(α+1)}} ≤ p(n) = O(e^{(C_{2}n/(log n)^{1/α})}),

where C_{2} = α(\frac{C_{1}}{α + 1})^{1 +1 /α} − ε,

(5) e^{C_{1}n/(log^{(s)} n)^{1/α}} ≤ p(n) = O(e^{((C_{1}−ε)n/(log^{(s+1)} n)^{1/α})}),

then for any k, (a) a^{(k)}(n) is eventually positive;

(b) \frac{a^{(k)}(n)}{n^{γ}} → ∞ for γ ∈ ℝ;

(c) a^{(k)}(n) satisfies RT_{1} .

4. The Bateman and Erdős Conjecture

Since the results of Bateman and Erdős lift so completely to the case that p(n) is polynomially bounded, it is not surprising that their conjecture also has a natural extension.

First a theorem on the asymptotics of a(n) is introduced in the case that rank(p) < ∞, but in the more general context of the p(n) being nonnegative real numbers. We call these generalized partition identities. For the case that p(n) has integer values, the next proposition is well known, and is covered by Proposition 3.1 with k = 0 .)

Proposition 4.1. Given a ‘generalized’ partition identity

A(x) = ∑_{n=0}^{∞} a(n)x^{n} = ∏_{n=1}^{∞}(1 − x^{n})^{−p(n)}

such that r := rank(p) < ∞ and gcd {n : p(n) > 0} = 1 , let

D = ∏_{n≥1} n^{p(n)} .

Then

(11)  a(n) = \frac{n^{r−1}}{Γ(r) · D}(1 + o(1))) .

Proof. The method of partial fractions that works so well when the p(n) are integers does not apply in this generality. Instead we turn to Darboux’s Theorem. One can assume p(n) = 0 for n > k. Then

(12)  A(z) = ∏_{j=1}^{k}(1 − z^{j})^{−p(j)} .

A(z) has radius of convergence 1. Let

f(z) := ∏_{j=1}^{k}(1 − z^{j})
g(z) := (1 + z)^{−p(2)} ⋯ (1 + z + ⋯ + z^{k−1})^{−p(k)}
β_{λ} := − ∑{α_{j} : λ^{d_{j}} = 1} .

Note that the β_{λ} are all real numbers, and g(1) = 1/D. From

A(z) = ∏ \{(1 − \frac{z}{λ})^{β_{λ}} : f(λ) = 0\}

one sees that the only singularities of A(z) on the circle |z| = 1 are algebraic singularities.

Next note that 1 is the only common root of the polynomials x^{d_{1}} −1, …, x^{d_{k}} − 1, for if λ is a common root then λ^{d_{1}} = 1, …, λ^{d_{k}} = 1 gives λ^{d} = 1 where d = gcd {d_{1}, …, d_{k}}. But d = 1 by assumption. From this one sees that

β_{1} = −(α_{1} + ⋯ + α_{k}) = −r < β_{λ} (λ ≠ 1) .

Thus the unique minimal value among the β_{λ} occurs when λ = 1, and in this case β_{1} = −r. As

A(z) = g(z)(1 − z)^{−r}

it follows from Darboux’s Theorem (as presented in Odlyzko’s survey article [11]) that^{6}

a(n) = \frac{g(1)}{Γ(r)} · n^{r−1} + o(n^{r−1})
= \frac{1}{Γ(r) · D} · n^{r−1} + o(n^{r−1}) .
□

Now we are ready for the generalization of the error estimate in the Bateman and Erdős Conjecture, and its proof.

Theorem 4.2. Given a partition identity

(13)  A(x) := ∑_{n=0}^{∞} a(n)x^{n} = ∏_{n=1}^{∞}(1 − x^{n})^{−p(n)}

with p(n) = O(n^{γ}) and satisfying BE_{k}, where γ ≥ 0 , one has

(14)  a^{(k+1)}(n) = O(\frac{a^{(k)}(n)}{n^{1/(γ+2)}} ) .

The conjecture of Bateman and Erdős is the case p(n) ∈ {0, 1} (and therefore a special case of our result when γ = 0) . The idea of our proof is as follows:

The case that rank(p) is finite is taken care of by Proposition 3.1, which actually gives the stronger result

a^{(k+1)}(n) = O(\frac{a^{(k)}(n)}{n}) .

So assume that rank(p) is infinite. From the compactness result Lemma 3.4 for BE_{k} one can find an arbitrarily large finite set of positive integers J such that

p(n) − χ_{J}(n)

still satisfies BE_{k}. We will use the notation

[x] := x − ⌊x⌋ .

6Phillipe Flajolet informs us that using integration over Hankel contours (as developed in his paper [9] with Andrew Odlyzko) one can improve the error term to O(1/n). However this would not lead to any strengthening of the conclusion in our Theorem 4.2.

Since p(n) satisfies BE_{k}, with

r := ⌈γ⌉ + 2

one can choose positive integers

1 = d_{0} < d_{1} < d_{2} < ⋯ < d_{r}

such that, for 1 ≤ j ≤ r,

∏_{i=1}^{j} (1 − x^{d_{i}})A(x)

has a component function that still satisfies BE_{k}. Let

β_{j} := \begin{cases}[γ] + δ_{[γ]=0} & if j = r − 1 \\ 1 & otherwise \end{cases}
A_{0}(x) := A^{(k−1)}(x)
A_{j+1}(x) := (1 − x^{d_{j−1}})^{β_{j−1}}A_{j−1}(x) for 0 ≤ j ≤ r
B_{j}(x) := ∏_{i=0}^{j} (1 − x^{d_{i}})^{−β_{i}}  for 0 ≤ j ≤ r .

One can picture the A_{j}(x) as follows:

A_{r+1} \underleftarrow{(1−x^{dr})^{βr}} A_{r} \underleftarrow{(1−x^{d_{r−1}})^{β_{r−1}}} A_{r−1} ⋯ A_{1} \underleftarrow{(1−x^{d_{0}})^{β_{0}}} A_{0} .

In particular, if γ is an integer then r = γ + 2 = ⌊γ⌋ + 2 and all the β_{j} are equal to 1. If γ is not an integer then r = ⌊γ⌋ + 3 and all the β_{j} = 1 except β_{r−1} = [γ] .

We briefly employ the A_{j}^{∗}(x) defined as follows:

A_{0}^{∗}(x) := A^{(k−1)}(x)
A_{j+1}^{∗}(x) := (1 − x^{d_{j}})A_{j}^{∗}(x) for 0 ≤ j ≤ r .

From our choice of the d_{j} it follows that each (1 − x)^{−k}A_{j}^{∗}(x) has a component function that satisfies BE_{k}, and thus, as n → ∞ one has from Proposition 3.3, for 0 ≤ j ≤ r + 1 ,

\frac{a_{j}^{∗}(n)}{n^{δ}} → ∞ for any δ ∈ ℝ
\frac{a_{j}^{∗}(n − 1)}{a_{j}^{∗}(n)} → 1 ,

and for 0 ≤ j ≤ r

a_{j}^{∗}(n + d_{j}) − a_{j}^{∗}(n) = a_{j+1}^{∗}(n) .

As

A_{j}(x) := \begin{cases}A_{j}^{∗}(x) & for 0 ≤ j ≤ r − 1 \\ (1 − x^{d_{r−1}})^{β_{r−1}−1}A_{j}^{∗}(x) & for j = r, r + 1 , \end{cases}

one has, for 0 ≤ j ≤ r + 1 ,

(15)  \frac{a_{j}(n)}{n^{δ}} → ∞ for any δ ∈ ℝ
(16)  \frac{a_{j}(n − 1)}{a_{j}(n)} → 1 ,

and for 0 ≤ j ≤ r,

(17)  (a_{j}(n + d_{j}) − a_{j}(n)) − \frac{1}{2}a_{j+1}(n) → ∞ .

Property (15) says that not only is a_{j}(n) eventually positive, but it actually has super polynomial growth. Property (16) says a_{j}(n) satisfies the RT_{1} condition. Property (17) says that the difference a_{j}(n + d_{j}) − a_{j}(n) is eventually positive, and indeed exceeds the super polynomially fast growing a_{j+1}(n)/2 .

Choose a positive integer N such that for n ≥ N

a_{j}(n) > 0 for 0 ≤ j ≤ r + 1
(18) a_{j}(n) − a_{j}(n − d_{j}) ≥ \frac{1}{2}a_{j+1}(n) for 0 ≤ j ≤ r .

The proof falls into two parts: the first part shows that

(19)  a_{r}(n) = O(a_{0}(n)/n) .

The second part uses this to show

a_{1}(n) = O(\frac{a_{0}(n)}{n^{1/(γ+2)}} )

which is then lifted to

(20)  a_{1}^{(1)}(n) = O(\frac{a_{0}^{(1)}(n)}{n^{1/(γ+2)}} ) ,

giving the desired result. Throughout this proof n will only be used to designate nonnegative integers.

Proof. [First part of the proof]:

This part of the proof concentrates on A_{0}(x) , A_{r}(x) and A_{r+1}(x) using

H(x) := log A_{r}(x)
S(x) := x(1 − x^{d_{r}})^{−β_{r}}H′(x) .

PARTITION IDENTITIES II 17

One has

[x^{n}]\frac{xA′(x)}{A(x)} = ∑_{j|n} jp(j)
(21)  xA_{r}′(x) = S(x)A_{r+1}(x)
(22)  A_{0}(x) = B_{r}(x)A_{r+1}(x)
(23)  \frac{1}{C_{1}} n^{γ+2} < b_{r}(n) < C_{2}n^{γ+2} ,

for some C_{1}, C_{2} > 0 . Item (23) follows from Proposition 4.1 after observing that

β_{0} + ⋯ + β_{r} = γ + 3 .

Also

xH′(x) = − \frac{kx}{1 − x} − ∑_{j=0}^{r−1} \frac{β_{j}d_{j}x^{d_{j}}}{1 − x^{d_{j}}} + \frac{xA′(x)}{A(x)}

so by (21)

nh(n) = −k − ∑_{j=0}^{r−1} β_{j}d_{j} · δ_{d_{j}|n} + ∑_{j|n} jp(j) .

From this follows

(24)  −k − ∑_{j=0}^{r−1} β_{j}d_{j} · δ_{d_{j}|n} ≤ nh(n) ≤ ∑_{j|n} jp(j) .

Furthermore

S(x) = x(1 − x^{d_{r}})^{−1}H′(x) = ∑_{i≥0} x^{id_{r}} ∑_{j≥1} jh(j)x^{j}
= ∑_{n≥1} ( ∑_{\begin{matrix}i≥0 \\ j≥1 \\ id_{r}+j=n \end{matrix}} jh(j))x^{n}

so by (24)

s(n) = ∑_{1≤j≤n} ∑_{\begin{matrix}i≥0 \\ j≥1 \\ id_{r}+j=n \end{matrix}} jh(j) ≤ ∑_{1≤j≤n} ∑_{i|j} ip()
≤ ∑_{1≤i≤n} ∑_{j≤n/i} ip(i) = n ∑_{1≤i≤n} p(i)
= O(n^{γ+2});

18 JASON P. BELL AND STANLEY N. BURRIS

and again by (24)

−s(n) ≤ ∑_{1≤j≤n} ∑_{\begin{matrix}i≥0 \\ j≥1 \\ id_{r}+j=n \end{matrix}} (k + ∑_{j=0}^{r−1} β_{j}d_{j} · δ_{d_{j}|n})
= O(n^{2}) .

Thus there is a constant C > 0 such that

|s(n)| ≤ C · n^{γ+2} for n ≥ 1 .

From (21)

na_{r}(n) = ∑_{i=0}^{n} s(n − i)a_{r+1}(i)
= ∑_{i=N}^{n} s(n − i)a_{r+1}(i) + ∑_{i<N} s(n − i)a_{r+1}(i)
(25)  ≤ C \underbrace{∑_{i=N}^{n}(n − i)^{γ+2}a_{r+1}(i)}_{(I)} + O(n^{γ+2}) .

To estimate (I) one uses:

∑_{i=N}^{n}(n − i)^{γ+2}a_{r+1}(i)

≤ C_{1} ∑_{i=N}^{n} b_{r}(n − i)a_{r+1}(i) by (23)
= C_{1}( ∑_{i=0}^{n} b_{r}(n − i)a_{r+1}(i) − ∑_{i<N} b_{r}(n − i)a_{r+1}(i))
≤ C_{1}(a_{0}(n) + O(n^{γ+2})) by (22), (23).

This with (25) gives

n · a_{r}(n) ≤ CC_{1}(a_{0}(n) + O(n^{γ+2)})) + O(n^{γ+2});

consequently

a_{r}(n) = O(a_{0}(n)/n) .

This finishes the first part of the proof, the proof of (19). □

Proof. [Second part of the proof]:

For 1 ≤ j ≤ r let

λ_{j} := β_{0} + ⋯ + β_{j−1}

Then λ_{1} = 1 and λ_{r} = γ + 2 . For 1 ≤ j ≤ r it is claimed that

(26)  a_{j}(n) = O(a_{0}(n)/n^{λ_{j}/(γ+2)}) .

To prove this start with j = r and work down to j = 1 . For j = r the claim is true as

a_{r}(n) = O(a_{0}(n)/n)

is the conclusion of the first part of the proof of the theorem. To keep the notation simple the step from j = 2 to j = 1 is given. All previous steps, from j to j − 1 , use an identical argument^{7}. So assume (26) holds for j = 2 , that is,

(27)  a_{2}(n) = O(\frac{a_{0}(n)}{n^{λ_{2}/(γ+2)}} );

we want to prove

(28)  a_{1}(n) = O(\frac{a_{0}(n)}{n^{λ_{1}/(γ+2)}} ) .

By (27), for some C > 0 ,

(29)  a_{2}(n) ≤ C · \frac{a_{0}(n)}{n^{λ_{2}/(γ+2)}}

for n sufficiently large—without loss of generality one can assume that (29) holds for n ≥ N .

Assuming n − jd_{1} ≥ N , from (18), for 0 ≤ i ≤ j

a_{1}(n − id_{1}) − a_{1}(n − (i + 1)d_{1}) ≤ a_{2}(n − id_{1})/2 ;

summing this from i = 0 to j − 1 gives

a_{1}(n) − a_{1}(n − jd_{1}) ≤ ∑_{i=0}^{j−1} a_{2}(n − id_{1})/2 ,

or

(30)  a_{1}(n − jd_{1}) ≥ a_{1}(n) − ∑_{i=0}^{j−1} a_{2}(n − id_{1})/2 .

Then from (18), (29) and (30),

a_{1}(n − jd_{1}) ≥ a_{1}(n) − \frac{C}{2} ∑_{i=0}^{j−1} \frac{a_{0}(n − id_{1})}{(n − id_{1})^{λ_{2}/(γ+2)}}

7A couple of footnotes have been inserted at appropriate spots to indicate the indices to be used in the general j step, that is, in the argument from j to j − 1 .

(31)  ≥ a_{1}(n) − \frac{jC}{2} \frac{a_{0}(n)}{(n − jd_{1})^{λ_{2}/(γ+2)}} .

From A_{0}(x) = B_{0}(x) · A_{1}(x) follows^{8}

a_{0}(n) = ∑_{j=0}^{n} b_{0}(j)a_{1}(n − j) .

By Proposition 4.1 one can choose a constant C_{1} > 0 such that^{9}

(32)  b_{0}(n) ≥ C_{1}n^{λ_{1}−1}

when n is sufficiently large–without loss of generality one can assume (32) holds for n ≥ N .

Since a_{1}(n) satisfies RT_{1} and has super polynomial growth, and b_{0}(n) has polynomially bounded growth, it follows that

( ∑_{0≤j<N} + ∑_{n−N<j≤n} )a_{1}(n − j)b_{0}(j) = O(a_{1}(n)) (33)

( ∑_{0≤jd<N} + ∑_{(n−N)<jd≤n} )a_{1}(n − jd_{1})j^{λ_{1}−1} = O(a_{1}(n)) . (34)

Noting that a_{1}(n − j) and b_{0}(j) are both positive for N ≤ j ≤ n − N provided n ≥ 2N one has, in view of (32), (33) and (34), for n ≥ 2N

a_{0}(n) = ∑_{j=0}^{n} a_{1}(n − j)b_{0}(j)

= ∑_{j=N}^{n−N} a_{1}(n − j)b_{0}(j) + O(a_{1}(n))
≥ ∑_{N≤jd≤(n−N)} a_{1}(n − jd_{1})b_{0}(jd_{1}) + O(a_{1}(n))
≥ C_{1}d_{1}^{λ_{1}−1} ∑_{N≤jd≤n−N} a_{1}(n − jd_{1})j^{λ_{1}−1} + O(a_{1}(n))
(35)  ≥ C_{1}d_{1}^{λ_{1}−1} ∑_{0≤jd≤n} a_{1}(n − jd_{1})j^{λ_{1}−1} + O(a_{1}(n)) .

Since a_{1}(n) satisfies RT_{1} and has superpolynomial growth one sees that, as n → ∞,

(36)  \frac{1}{a_{1}(n)} ∑_{0≤jd≤n} a_{1}(n − jd_{1})j^{λ_{1}−1} → ∞ .

8For the general j step use A_{0}(x) = B_{j−2}(x) · A_{j−1}(x) at this point in the proof.

9In the general j step use b_{j−2}(n) ≥ C_{1}n^{λ_{j−1}−1} .

Thus from (35) and (36)

(37)  a_{0}(n) ≥ K ∑_{0≤jd≤n} a_{1}(n − jd_{1})j^{λ_{1}−1}

for n sufficiently large, where

K = C_{1}d_{1}^{λ_{1}−1}/2.

Choose N_{1} ≥ 2N such that (37) holds for n ≥ N_{1} .

Suppose (28) fails. Given any n we claim that there is a positive integer m such that the following two inequalities hold:

(38)  m ≥ N + d · m^{1/(γ+2)}
(39)  a_{1}(m) ≥ \frac{C}{2} n · \frac{a_{0}(m)}{m^{λ_{1}/(γ+2)}} .

Item (38) holds for m sufficiently large, and (39) holds for infinitely many m as (28) fails. Thus for each n there are infinitely many solutions m to (38) and (39). For the rest of the proof fix 𝔪 = 𝔪(n) to provide one solution for each n. Let

𝔮 = 𝔮(n) := ⌊𝔪^{1/(γ+2)}⌋.

Clearly

𝔪 → ∞ and 𝔮 → ∞

as n → ∞. Item (38) yields

𝔪 − 𝔮d ≥ N,

and this with (18) gives

(40)  a_{1}(𝔪 − 𝔮d_{1}) ≤ a_{1}(𝔪 − jd_{1}) for 0 ≤ j ≤ 𝔮.

From (31), (39), (40), for 0 ≤ j ≤ 𝔮,

a_{1}(𝔪 − jd_{1}) ≥ a_{1}(𝔪) − \frac{C}{2} \frac{ja_{0}(𝔪)}{(𝔪 − jd_{1})^{λ_{2}/(γ+2)}}
(41)  ≥ \frac{C}{2} a_{0}(𝔪)(\frac{n}{𝔪^{λ_{1}/(γ+2)}} − \frac{j}{(𝔪 − 𝔮d_{1})^{λ_{2}/(γ+2)}} ) .

Choose N_{2} > 0 such that 𝔪 ≥ N_{1} for n ≥ N_{2} . Then, from (40) and (37), for n ≥ N_{2}

(42)  a_{0}(𝔪) ≥ K ∑_{j=0}^{𝔮−1} a_{1}(𝔪 − jd_{1})j^{λ_{1}−1}.

From (41) and (42) one has, for n ≥ N_{2} ,

a_{0}(𝔪) ≥ \frac{KC}{2} a_{0}(𝔪)(n ∑_{j=0}^{𝔮−1} \frac{j^{λ_{1}−1}}{𝔪^{λ_{1}/(γ+2)}} − ∑_{j=0}^{𝔮−1} \frac{j^{λ_{1}}}{(𝔪 − 𝔮d_{1})^{λ_{2}/(γ+2)}} ) ,

so

(43) 1 ≥ \frac{KC}{2} · (n · ∑_{j=0}^{𝔮−1} \frac{j^{λ_{1}−1}}{𝔪^{λ_{1}/(γ+2)}} − ∑_{j=0}^{𝔮−1} \frac{j^{λ_{1}}}{(𝔪 − 𝔮d_{1})^{λ_{2}/(γ+2)}} ) .

For estimates of these sums, as functions of n, one has, as λ_{2} ≥ λ_{1} ≥ 1 ,

∑_{j=0}^{𝔮−1} \frac{j^{λ_{1}−1}}{𝔪^{λ_{1}/(γ+2)}} = \frac{1}{𝔪^{λ_{1}/(γ+2)}} (\frac{𝔮^{λ_{1}}}{λ_{1}} + o(𝔮^{λ_{1}}))

= \frac{1}{𝔪^{λ_{1}/(γ+2)}} (\frac{𝔪^{λ_{1}/(γ+2)}}{λ_{1}} + o(𝔪^{λ_{1}/(γ+2)}))
(44)  = \frac{1}{λ_{1}} + o(1) .

and

∑_{j=0}^{𝔮−1} \frac{j^{λ_{1}}}{(𝔪 − 𝔮d_{1})^{λ_{2}/(γ+2)}} = \frac{1}{(𝔪 − 𝔮d_{1})^{λ_{2}/(γ+2)}} (\frac{𝔮^{λ_{2}}}{λ_{2}} + o(𝔮^{λ_{2}}))

= \frac{1}{(𝔪 − 𝔮d)^{λ_{2}/(γ+2)}} (\frac{𝔪^{λ_{2}/(γ+2)}}{λ_{2}} + o(𝔪^{λ_{2}/(γ+2)}))
(45)  = \frac{1}{λ_{2}} + o(1) .

Substituting (44) and (45) into (43) gives

(46) 1 ≥ KC · (n · (\frac{1}{λ_{1}} + o(1)) − (\frac{1}{λ_{2}} + o(1))) .

Taking the limit of both sides of (46) as n → ∞ gives 1 ≥ ∞, a contradiction.

Item (26), with j = 1 , gives

a_{1}(n) = O(\frac{a_{0}(n)}{n^{1/(γ+2)}} ) ,

that is

a^{(k)}(n) = O(\frac{a^{(k−1)}(n)}{n^{1/(γ+2)}}) .

To obtain the desired result

a^{(k+1)}(n) = O(\frac{a^{(k)}(n)}{n^{1/(γ+2)}} )

simply copy the last part of Bell’s proof of the original Bateman and Erdős conjecture in [3], pp. 151–152, replacing the exponent 1/2 with 1/(γ + 2) . □

5. (Counter)Examples

In this section examples are given to show that the results are, to a great extent, the best possible.

5.1. Polynomially bounded is best possible for BE_{k}. Let f(n) be a nonnegative super polynomial function. Now it is shown that if p(n) ≤ f(n) and satisfies BE_{k} then a(n) need not be eventually strictly increasing; indeed it need not even be eventually nondecreasing.

First, select a sequence of positive integers 4 ≤ m_{1}, … as follows. Having selected m_{1}, …, m_{d}, find some m_{d+1} such that

[x^{m_{d+1}+1}](1 − x^{2})^{−k−1}(1 − x^{3})^{−k−1} ∏_{j=1}^{d}(1 − x^{m_{j}})^{−⌊f(m_{j})⌋} < ⌊f(m_{d+1})⌋.

Let p(n) = 0 if n ≥ 4 and n ∉ {m_{1}, …}. Let p(1) = 0, p(2) = p(3) = k + 1 and p(m_{i}) = ⌊f(m_{i})⌋. Observe that with this set up, a(m_{d}) ≥ ⌊f(m_{d})⌋. Notice however, that

a(m_{d} + 1) = [x^{m_{d}+1}] ∏_{j=1}^{∞}(1 − x^{j})^{−p(j)}

= [x^{m_{d}+1}](1 − x^{2})^{−k−1}(1 − x^{3})^{−k−1} ∏_{j=1}^{d}(1 − x^{m_{j}})^{−⌊f(m_{j})⌋}
= [x^{m_{d}+1}](1 − x^{2})^{−k−1}(1 − x^{3})^{−k−1}

· ∏_{j=1}^{d−1}(1 − x^{m_{j}})^{−⌊f(m_{j})⌋} + [x](1 − x^{2})^{−k−1}(1 − x^{3})^{−k−1}

· ∏_{j=1}^{d−1}(1 − x^{m_{j}})^{−⌊f(m_{j})⌋}

= [x^{m_{d}+1}](1 − x^{2})^{−k−1}(1 − x^{3})^{−k−1} ∏_{j=1}^{d−1}(1 − x^{m_{j}})^{−⌊f(m_{j})⌋}
< ⌊f(m_{d})⌋

< a(m_{d}).

5.2. Showing O(n^{−1/(γ+2)}) is best possible. Bateman and Erdős showed that their result

\frac{a^{(k+1)}a(n)}{a^{(k)}(n)} = O(n^{−1/2})

for partition identities with p(n) ∈ {0, 1} satisfying their condition P_{k} was best possible by examining the asymptotics for the classical partition function. In the same spirit it will be shown that Theorem 3.5

\frac{a^{(k+1)}(n)}{a^{(k)}(n)} = O(n^{−1/(γ+2)})

for partition identities with p(n) = O(n^{γ}) and satisfying BE_{k} is best possible.

To see this, for convenience we use real nonnegative values of p(n). Let k be a nonnegative integer and take

p(n) = (k + 1)δ_{1,n} + n^{γ}.

Then

a^{(k+1)}(n) = ∏_{j=1}^{∞}(1 − x^{j})^{−n^{γ}}.

Meinardus’ theorem (Theorem 6.2 of Andrews [1]) will be needed. Using the notation of Andrews,

D(s) = ∑_{n=1}^{∞} \frac{n^{γ}}{n^{s}} = ζ(s − γ).

Classical results (see page 91 of Andrews [1] for results about ζ(s) and Γ(s) and look at Riemann’s formula for the Zeta function for negative values of Re(s) in Conway [8]) show that D(s) satisfies the conditions of the theorem with a pole of order 1 at s = γ + 1. Thus according to his theorem,

a^{(k+1)}(n) ∼ Cn^{κ} exp(Bn^{\frac{γ+1}{γ+2}} ),

where C and B are nonzero constants and

κ = \frac{ζ(−γ) − 1 − \frac{γ+1}{2}}{γ + 2} .

Similarly, using Meinardus’ theorem again,

a^{(k)}(n) ∼ C′n^{κ′} exp(Bn^{\frac{γ+1}{γ+2}} ),

where again C′ is a nonzero constant, B is the same constant as appearing in the asymptotic expression for a^{(k+1)}(n) and

κ′ = \frac{ζ(−γ) − \frac{γ+1}{2}}{γ + 2} .

Hence

a^{(k+1)}(n)/a^{(k)}(n) ∼ C_{0}n^{κ−κ′} = C_{0}n^{−1/(γ+2)},

where C_{0} = C/C′. This shows that our result is best possible.

6. Generalized Partition Identities

The notion of generalized partition identities was briefly introduced in Proposition 4.1, that is, where the p(n) are allowed to take on nonnegative real values.^{10} Essentially everything presented goes through in this setting. Our reason for restricting our attention to the case that the p(n) have nonnegative integer values is simply that this is where the applications to combinatorics, additive number theory, and logical limit laws are to be found.

The modification of the previous proofs to apply to generalized partition identities is quite straightforward; however for the Bateman and Erdős results some clarification may be useful. For the general setting

10Allowing the p(n) to be nonnegative real numbers is a rather obvious generalization, but it does not seem to have found much favor in the literature, perhaps because there is no clear connection to combinatorial systems.

Another direction to generalize partition identities that seems to have been more resonant is to keep the p(n) as nonnegative integers but allow the exponents of x in the factors of the product to be nonnegative real numbers. One interprets this in number systems by saying that the indecomposables have been assigned real valued norms. If one does this only on the right side of a partition identity, the product side

∏_{n=1}^{∞}(1 − x^{r_{n}})^{−p(n)} ,

then one might still expect to obtain a power series on the left side. But this is not the direction pursued in abstract additive number theory (see Knopfmacher [10]). Instead one adds the assumption {m : r_{m} ≤ n} is finite for all n and expresses the product as a generalized power series

A(x) := ∑_{n=0}^{∞} a(n)x^{t_{n}} ,

where the values t_{n} come from the additive monoid generated by the r_{n}. With this approach the study of generalized additive number systems is essentially identical to the study of generalized multiplicative systems where one has generalized Dirichlet series ∑ a(n) exp ( − λ_{n}s) for the generating functions. It is not clear that one even has good and/or interesting analogues of RT_{1} and kth difference functions in this setting.

the following notion of BE_{κ} is introduced, where κ is a real number:

BE_{κ} : \{  \begin{matrix}• rank(p) > κ, \\ • for any (real-valued) q(n) satisfying the two con- \\ ditions \\ \{ & \begin{matrix}0 ≤ q(n) ≤ p(n) \\ ∑_{n} (p(n) − q(n)) = κ . \end{matrix} \\ one has \\ gcd \{n : q(n) > 0\} = 1 . \end{matrix}

Then a reduced generalized generating function A(x) will satisfy BE_{κ} iff the coefficients of the κ-fold difference function

(1 − x)^{κ} · A(x)

are eventually positive. The conclusion for the conjecture can be extended to

a^{(κ+β)}(n) = O(\frac{a^{(κ)}(n)}{n^{β/(γ+2)}} )

where 0 ≤ β ≤ 1 .

References

[1] George Andrews, The Theory of Partitions. Cambridge University Press, 1984.

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

[3] Jason P. Bell, A proof of a partition conjecture of Bateman and Erdős. Journal of Number Theory 87 (2001), 144–153.

[4] Jason P. Bell, Sufficient conditions for zero-one laws. Trans. Amer. Math. Soc. 354 (2002), no. 2, 613–630.

[5] Jason P. Bell and Stanley N. Burris, Asymptotics for logical limit laws: when the growth of the components is in an RT class. Trans. Amer. Math. Soc. 355 (2003), 3777–3794.

[6] Jason P. Bell and Stanley N. Burris, Partition identities I. Sandwich theorems and logical 0-1 laws. (Preprint, 2004)

[7] Stanley N. Burris, Number Theoretic Density and Logical Limit Laws. Mathematical Surveys and Monographs, Vol. 86, Amer. Math. Soc., 2001.

[8] John Conway, Functions of one Complex Variable. Vol. I Springer-Verlag, seventh corrected printing 1995.

[9] P. Flajolet and A.M. Odlyzko, Singularity analysis of generating functions. SIAM J. Discrete Math. 3 (1990), 216–240.

[10] J. Knopfmacher, Abstract analytic number theory. North-Holland Mathematical Library, Vol. 12. North-Holland Publishing Co., Amsterdam-Oxford; American Elsevier Publishing Co., Inc., New York, (1975).

[11] A.M. Odlyzko, Asymptotic enumeration methods. Handbook of Combinatorics Vol. II, R.L. Graham, M. Grötschel and L. Lovász, eds., 1063–1230, Elsevier, 1995.

Mathematics Department, University of Michigan, East Hall, 525 East University, Ann Arbor, MI 48109-1109, USA

E-mail address: belljp@umich.edu

Department of Pure Mathematics, University of Waterloo, Waterloo, Ontario N2L 3G1 Canada

E-mail address: snburris@thoralf.uwaterloo.ca
URL: www.thoralf.uwaterloo.ca