PARTITION IDENTITIES I SANDWICH THEOREMS AND LOGICAL 0–1 LAWS

JASON P. BELL AND STANLEY N. BURRIS

Abstract. The Sandwich Theorems proved in this paper give a new method to show that the partition function a(n) of a partition identity

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

satisfies the condition RT_{1}

lim_{n→∞} \frac{a(n − 1)}{a(n)} = 1 .

This leads to numerous examples of naturally occuring classes of relational structures whose finite members enjoy a logical 0–1 law.

1. Introduction

Partition identities

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

have been a staple in combinatorics and additive number theorysince the pioneering work of Hardy and Ramanujan into the number of partitions of a positive integer n, that is, the number of ways to write n as a sum of positive integers. 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) .

The nomenclature for the anatomy of a partition identity used here is:

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.

Date: June 15, 2004.

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

Key words and phrases. ratio test, partition identity, Schur’s Tauberian theorem, zeroone law.

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

Actually any expression for a function that has A(x) for its power series expansion is also called the generating function for the partitions; likewise for P(x). When a generating function of a partition identity is mentioned without specifying if it is A(x) or P(x), the convention will be that it is A(x).

In the study of the multiplicative theory of the natural numbers, or of the integers of an algebraic number field, the total count function is readily accessible whereas the prime count function is quite difficult to pin down. Just the opposite tends to be the case in additive number theory, combinatorics and algebra. For example in the partition problems considered by Bateman and Erdős one starts with a set M of natural numbers and asks how many ways one can partition a natural number n into summands from M. In this case p(n) = χ_{M}(n), the characteristic function of M; the investigative effort goes into understanding properties of a(n). In graph theory the natural approach to enumeration problems for a class of finite graphs is to start with an enumeration of the components. In algebra, to enumerate the finite Abelian groups one starts with the fact that the indecomposables are the cyclic p-groups, one of size p^{k} for each prime number p and each positive integer k. The reader should therefore not be surprised that we also like to start with hypotheses on p(n) and deduce information about a(n).

2. The Property RT_{1}

The property

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

where f(n) is eventually positive, is called RT_{1} because it is the condition used in the well known limit form of the ratio test for convergence of the power series ∑ f(n)x^{n}; if RT_{1} holds then the radius of convergence of ∑ f(n)x^{n} is 1 .

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}.

Clearly f(n) satisfies RT_{1} guarantees that 1 is the radius of convergence of ∑ f(n)x^{n}; but this does not explain the true value of the RT_{1} property. It has much more to do with the fact that the values of f(n) vary slowly as n increases, as expressed by

(1 − ε) · f(n − 1) < f(n) < (1 + ε) · f(n − 1)

for n sufficiently large.^{1} The property RT_{1} 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.

There are three main 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—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 principal theorems concerning conditions on a partition identity that guarantee a(n) satisfies RT_{1}:

• Theorem A. (Bell [3]) 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:^{2} (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) .

1The property RT_{ρ}, meaning a(n − 1)/a(n) → ρ, is called smoothly growing by Compton; RT_{ρ} is the additive number theory analog of the property RV_{α}, regular variation of index α, in multiplicative number theory. RT_{1} is the analog of RV_{0} , slowly varying at infinity.

2This 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}.

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}.

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.

The goals of this paper are:

• To considerably extend the collection of partition identities for which it is known that a(n) satisfies RT_{1} ; and to show that this extension is, in a natural sense, best possible.

• To give a new proof of Bell’s Theorem A: if p(n) is polynomially bounded then a(n) satisfies RT_{1} .

• To show that the new techniques for proving a(n) satisfies RT_{1} lead to new examples of natural classes of finite structures which have a logical 0–1 law.

3. Background requirements

In addition to the results on RT_{1} already mentioned we will need the following two well known results:

• D The polynomial growth of a(n) when rank(p) < ∞.

• E The superpolynomail growth of a(n) when rank(p) = ∞.

Also the following Tauberian theorem is needed:

Theorem 3.1 (Schur). With 0 ≤ ρ < ∞, suppose that

(i) a(n) satisfies RT_{ρ},

(ii) B(x) has radius of convergence greater than ρ, and (iii) B(ρ) > 0 .

Let C(x) = A(x) · B(x) . Then

c(n) ∼ B(ρ) · a(n) .

Proof. (See [7], p. 62.) □

The notation f(n) ⪯ g(n) means that f(n) is eventually less or equal to g(n) .

4. The Sandwich Theorem

There has long been interest in studying the partial sums ∑_{j≤n} a(j) of the coefficients of a power series, but here the fixed length tails of these partial sums are of particular interest. For L a nonnegative integer let

a^{L}(n) := a(n) + ⋯ + a(n − L) .

For a generating function A(x) whose coefficients are eventually positive, the least nonnegative integer L such that a(n) > 0 for n ≥ L is called the conductor^{3} of A(x); designate it by L_{A}. As the following lemma shows, the coefficients of such a generating function enjoy a weak form of monotonicity that leads to monotonicity for a^{L}(n) for L ≥ L_{A}. Furthermore, the study of a^{L}(x) leads to powerful methods for showing that a(n) satisfies RT_{1}.

Lemma 4.1. Let A(x) be a generating function whose coefficients are eventually positive. Then for any L ≥ L_{A},

(a) a(n) ≥ a(m) if n − m ≥ L;

(b) a^{L}(n) is nondecreasing for all n;

(c) a^{L}(n) is positive for n ≥ L_{A} ;

(d) a^{mL}(n) ≤ m · a^{L}(n) for m = 1, 2, ⋯; n ≥ 0 .

Proof. If a(j) > 0 then for any m, a(m) ≤ a(m + j) (this does not require that the coefficients be eventually positive).^{4} For n − m ≥ L_{A} one has a(n − m) > 0; so a(m) ≤ a(m + (n − m)) = a(n). This proves (a). For (b) note that

a^{L}(n + 1) − a^{L}(n) = a(n + 1) − a(n − L) ≥ 0

by part (a). For n ≥ L_{A} clearly a^{L}(n) ≥ a(n) > 0; this is (c). Finally for (d) one has

a^{mL}(n) ≤ ∑_{j=0}^{m−1} ∑_{i=0}^{L} a(n − jL − i) = ∑_{j=0}^{m−1} a^{L}(n − jL)

≤ ∑_{j=0}^{m−1} a^{L}(n) = m · a^{L}(mL) .
□

Lemma 4.2. Let A(x) be a generating function with a(n) eventually positive, and suppose L ≥ L_{A} is an integer such that

|a(n) − a(n − 1)| = o(a^{L}(n)) .

3Wilf [12], p. 97, uses this name in the case that p(n) ∈ {0, 1}. He mentions that given such a p(n) that is eventually 0, computing L_{A} seems to be a difficult problem.

4The proof using additive number systems is trivial. Let A be a model of the partition identity and choose an element a ∈ A with ∥a∥ = j. Then the cancellation property shows that the mapping b ↦ a + b is an injective mapping from the elements of norm m into the elements of norm m + j.

Then

\frac{a(n − 1)}{a(n)} → 1 as n → ∞ .

Proof. Let ε > 0 be given and choose a positive integer M such that for n ≥ M

|a(n) − a(n − 1)| ≤ \frac{ε}{L(L + 1)}a^{L}(n).

For n ≥ M + L choose ñ and n̂ from {n − L, …, n} such that

a(ñ) ≤ a(j) ≤ a(n̂) for n − L ≤ j ≤ n .

Then for n ≥ M + L

0 ≤ a(n̂) − a(ñ) ≤ ∑_{j=n−L+1}^{n} |a(j) − a(j − 1)|

≤ \frac{ε}{L(L + 1)} ∑_{j=n−L+1}^{n} a^{L}(j)
≤ \frac{ε}{L + 1}a^{L}(n)
≤ εa(n̂) ,

and thus, as 0 < a(ñ) ≤ a(n) ≤ a(n̂) for n ≥ M + L,

1 − ε ≤ \frac{a(ñ)}{a(n̂)} ≤ \frac{a(n − 1)}{a(n)} ≤ \frac{a(n̂)}{a(ñ)} ≤ (1 − ε)^{−1} .

From this it follows that a(n − 1)/a(n) → 1 as n → ∞. □

Lemma 4.3. Suppose A_{1}(x) and A_{2}(x) are two generating functions and L ≥ L_{A} a positive integer such that, with A(x) = A_{1}(x) · A_{2}(x),

(i) \frac{a_{1}(n − 1)}{a_{1}(n)} → 1 ;

(ii) a_{2}^{L}(n) = o(a^{L}(n)) . Then as n → ∞,

\frac{a(n − 1)}{a(n)} → 1 .

Proof. Given ε > 0 choose a positive integer M that is a multiple of L and such that for n ≥ M,

|a_{1}(n) − a_{1}(n − 1)| ≤ \frac{ε}{2}a_{1}(n) .

Then there are positive constants C_{1}, C_{2} such that for n ≥ M,

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

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

+ ∑_{j<M} |a_{1}(j) − a_{1}(j − 1)| · a_{2}(n − j)

≤ \frac{ε}{2} ∑_{j=M}^{n} a_{1}(j)a_{2}(n − j) + C_{1} ∑_{j<M} a_{2}(n − j)

≤ \frac{ε}{2} ∑_{j=0}^{n} a_{1}(j)a_{2}(n − j) + C_{2} ∑_{j≤M} a_{2}(n − j)
= \frac{ε}{2}a(n) + C_{2}a_{2}^{M}(n)
≤ \frac{ε}{2}a(n) + C_{2} \frac{M}{L} a_{2}^{L}(n) .

Now choose N ≥ M such that for n ≥ N

C_{2} \frac{M}{L} a_{2}^{L}(n) ≤ \frac{ε}{2}a^{L}(n) .

Then for n ≥ N,

|a(n) − a(n − 1)| ≤ εa^{L}(n) .

Thus |a(n) − a(n − 1)| = o(a^{L}(n)), so by Lemma 4.2 it follows that a(n) satisfies RT_{1}. □

Theorem 4.4 (Sandwich Theorem). Suppose

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

is a reduced partition identity with

\frac{ȧ(n − 1)}{ȧ(n)} → 1 as n → ∞ .

Then any partition identity

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

satisfying

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

will be such that

\frac{a(n − 1)}{a(n)} → 1 as n → ∞ .

Proof. Clearly

A(x) = Ȧ(x) · Ä(x)

where

p̈(n) := p(n) − ṗ(n)

Ä(x) = ∏_{n=1}^{∞}(1 − x^{n})^{−p̈(n)} .

If p̈(n) is eventually 0, then Stewart’s Sum Theorem gives the conclusion, for in this case the reduced form of Ä(x) satisfies RT_{1} by item D.

So assume p̈(n) is not eventually 0. Choose positive integers d_{1} > d_{2} > 1 such that p̈(d_{1}) and p̈(d_{2}) are positive. Let

(5)  A_{1}(x) := (1 − x^{d_{1}})^{−1}(1 − x^{d_{2}})^{−1}Ȧ(x)
A_{2}(x) := (1 − x^{d_{1}})(1 − x^{d_{2}})Ä(x)
P_{2}(x) := −x^{d_{1}} − x^{d_{2}} + ∑_{n=1}^{∞} p̈(n)x^{n}
H_{2}(x) := P_{2}(x) + P_{2}(x^{2})/2 + ⋯
(6)  B_{j}(x) := (1 − x)^{−j}Ȧ(x)  for j = 1, 2 .

Then

(7)  A(x) = A_{1}(x)A_{2}(x)
(8)  A_{2}(x) = exp (H_{2}(x)) .

Our goal is to show that A_{1}(x) and A_{2}(x) satisfy the conditions of Lemma 4.3. Applying Stewart’s Sum Theorem to (5) one has

\frac{a_{1}(n − 1)}{a_{1}(n)} → 1 ;

so Schur’s Tauberian Theorem applied to (5) gives

(9)  d_{1}d_{2} · a_{1}(n) ∼ [x^{n}](1 − x)^{−2}Ȧ(x) = b_{2}(n) .

From (6) one readily sees that

b_{2}(n) = b_{1}(0) + ⋯ + b_{1}(n)
\frac{b_{1}(n − 1)}{b_{1}(n)} → 1  as n → ∞;

so

\frac{b_{1}(n)}{b_{2}(n)} → 0 as n → ∞ .

This, with (9), shows b_{1}(n) = o(a_{1}(n)), that is

(10)  ∑_{j=0}^{n} ȧ(j) = o(a_{1}(n)) .

Differentiating both sides of (8) with respect to x and equating coefficients gives

(11)  na_{2}(n) = ∑_{j=1}^{n} jh_{2}(j) · a_{2}(n − j) .

PARTITION IDENTITIES I 9

By (4), since p_{2}(n) ≤ p(n) one has

p_{2}(n) = O(ȧ(n)) .

From this and the fact that ȧ(0) = 1 it follows that there is a C > 0 such that for n ≥ 1 ,

(12)  ∑_{j=1}^{n} p_{2}(j) ≤ C ∑_{j=0}^{n} ȧ(j) .

The definition of h_{2}(n) and items (10), (12) yield

nh_{2}(n) = ∑_{j|n} jp_{2}(j) ≤ n ∑_{j=1}^{n} p_{2}(j)
≤ Cn ∑_{j=0}^{n} ȧ(j) = o(na_{1}(n)) .

Let L = L_{A}. Given ε > 0 choose M to be a multiple of L such that

(13) nh_{2}(n) < \frac{ε}{2} · na_{1}(n) for n ≥ M .

By (7) one has, for all n,

(14)  a_{2}(n) ≤ a(n) .

There is a positive constant K such that, for n ≥ M ,

na_{2}(n) = ∑_{j=M}^{n} jh_{2}(j)a_{2}(n − j) + ∑_{j<M} jh_{2}(j)a_{2}(n − j)  by (11)
≤ ∑_{j=M}^{n} \frac{ε}{2}na_{1}(j)a_{2}(n − j) + ∑_{j<M} a_{2}(n − j)jh_{2}(j)  by (13)
≤ n\frac{ε}{2}a(n) + Ka_{2}^{M}(n)  by (7)
≤ n\frac{ε}{2}a(n) + Ka^{M}(n)  by (14) ;

so

a_{2}(n) ≤ \frac{ε}{2}a(n) + \frac{KM}{L} \frac{a^{L}(n)}{n} .

Thus for n ≥ M, using Lemma 4.1 (b), (d),

a_{2}^{L}(n) ≤ \frac{ε}{2}a^{L}(n) + \frac{KM}{L} ∑_{j=0}^{L} \frac{a^{L}(n − j)}{n − j}
≤ \frac{ε}{2}a^{L}(n) + \frac{KM}{L(n − L)} ∑_{j=0}^{L} a^{L}(n)
= \frac{ε}{2}a^{L}(n) + \frac{KM(L + 1)}{L(n − L)}a^{L}(n) ;

so by choosing N ≥ M such that for n ≥ N,

\frac{KM(L + 1)}{L(n − L)} ≤ \frac{ε}{2} ,

one has, for n ≥ N,

a_{2}^{L}(n) ≤ εa^{L}(n) .

Thus a_{2}^{L}(n) = o(a^{L}(n)) , so a(n − 1)/a(n) → 1 as n → ∞, by Lemma 4.3. □

4.1. A New Proof of Bell’s Polynomial Bound Theorem. The following theorem is one of our favorites for proving the RT_{1} property, and is at the very heart of our considerable generalization of the Bateman and Erdős results in Partition Identities II.

Theorem 4.5 (Bell [3]). For a reduced partition identity

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

with p(n) = O(n^{γ}) one has

\frac{a(n − 1)}{a(n)} → 1 as n → ∞ .

Proof. For the case that rank(p) < ∞ simply appeal to Item D. So now suppose that rank(p) = ∞.

Choose ṗ(n) with 0 ≤ ṗ(n) ≤ p(n) satisfying the three conditions:

(i) ṗ(n) is eventually 0, (ii) ṗ(n) is equal to p(n) on at least γ +2 values of n for which p(n) does

not vanish, and (iii) the gcd of the n for which ṗ(n) does not vanish is 1.

(One can find such a p(n) .) Condition (iii) says that the partition identity determined by ṗ(n) , namely

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

is reduced.

Clearly ṗ(n) ≤ p(n) , and by Item D one has p(n) = O(ȧ(n)). Again from Item D it is known that ȧ(n) satisfies RT_{1} . Thus by Theorem 4.4 the conclusion follows. □

4.2. Showing p(n) = O(ȧ(n)) is best possible. An example is given to show that the upper bound condition on the Sandwich Theorem does not allow for any obvious improvement such as p(n) = O(n^{k} · ȧ(n)).

Let f(n) ≥ 1 be a positive nondecreasing unbounded function. An example is constructed of a generating function Ȧ(x) satisfying RT_{1} for which one can find a p(n) satisfying

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

but a(n) fails to satisfy RT_{1}. This shows that Theorem 4.4 is, in an important sense, the best possible. f(n) can be replaced by a function which is unbounded (but not necessarily nondecreasing) and the result will still be true, but it requires a little more detail.

The construction of Ȧ(x) proceeds by recursion, essentially by defining ṗ(n) on longer and longer initial segments of the natural numbers. Let

m_{1} := 1
α_{j} := 1 + \frac{1}{1 + j}  for j ≥ 0
ṗ_{0}(n) := 1  for n ≥ 1
ṗ_{1}(n) := 2^{n−1}  for n ≥ 1 .

Given a ṗ_{k}(n), of define ȧ_{k}(n) by

Ȧ_{k}(x) := ∑_{n≥0} ȧ_{k}(n)x^{n} = ∏_{n≥1} (1 − x^{n})^{−ṗ_{k}(n)}.

Let Φ(k) be the conjunction of the following three assertions:

(a) ṗ_{k−1}(m_{k}) > m_{k}

(b) [x^{n}](1 − x)^{−k} · Ȧ_{k−1}(x) < α_{k−1} · f(n) for n > m_{k}

(c) ṗ_{k}(n) = \begin{cases}ṗ_{k−1}(n) & if 1 ≤ n ≤ m_{k} \\ ⌊α_{k−1}^{n−m_{k}} · ṗ_{k−1}(m_{k})⌋ & if n > m_{k} . \end{cases}

It is easy to check that Φ(1) holds. We claim:

Given m_{j}, ṗ_{j}(n), and ȧ_{j}(n) for 1 ≤ j ≤ k, such that each of the conditions

Φ(1), ⋯, Φ(k)

holds, one can find m_{k+1}, ṗ_{k+1}(n), and ȧ_{k+1}(n) such that Φ(k + 1) holds.

To do this one only needs to find an m_{k+1} that satisfies (a) and (b) as one can use (c) to define ṗ_{k+1}(n). One can find such an m_{k+1} because Theorem B leads to

\frac{ȧ_{k}(n − 1)}{ȧ_{k}(n)} → \frac{1}{α_{k}} ,

and this in turn allows us to invoke Schur’s Tauberian Theorem to obtain

\frac{[x^{n}](1 − x)^{−k}Ȧ_{k}(x)}{ȧ_{k}(n)} → (\frac{α_{k}}{α_{k} − 1})^{k} < ∞.

Note that for k any positive integer one has ṗ_{k−1}(n) agreeing with ṗ_{k}(n) on the interval 1 ≤ n ≤ m_{k}. One arrives at ṗ(n) by letting

ṗ(n) := ṗ_{k}(n)  for any k such that n ≤ m_{k+1} .

Then ṗ(n) satisfies RT_{1} since for n ≥ m_{k} one has

ṗ(n) ≤ α_{k} · (1 + ṗ(n − 1))
ṗ(n) → ∞
α_{k} → 1.

Thus by Theorem B, ȧ(n) satisfies RT_{1}.

Now define a p(n) that lies between ṗ(n) and 3f(n)ȧ(n) for which a(n) does not satisfy RT_{1}. Put n_{1} = 1 and let Ψ(k) be the conjunction of the following two assertions:

(a) p_{k}(n) = \begin{cases}2⌊f(n_{k})ȧ(n_{k})⌋ + 1 & if n = n_{k} \\ ṗ(n) & otherwise , \end{cases}

(b) a_{k}(n_{k}) < f_{k}(n_{k})ȧ(n_{k}) . As before, given a p_{k}(n) define the corresponding a_{k}(n) by

A_{k}(x) := ∑_{n≥0} a_{k}(n)x^{n} = ∏_{n≥1} (1 − x^{n})^{−p_{k}(n)}

Clearly Ψ(1) holds, and we claim:

Given m_{j}, p_{j}(n), and a_{j}(n) for 1 ≤ j ≤ k, such that each of the conditions

Ψ(1), ⋯, Ψ(k)

holds, one can find m_{k+1}, p_{k+1}(n) and a_{k+1}(n) such that Ψ(k + 1) holds.

One only needs to find an n_{k+1} that satisfies (b), and this is possible since

a(n) ≤ [x^{n}](1 − x)^{−ṗ(n_{1})−···−ṗ(n_{k})} · Ȧ(x)

holds, by construction, for infinitely many n.

Note that for k any positive integer one has p_{k−1}(n) agreeing with p_{k}(n) on the interval 1 ≤ n < n_{k}. One arrives at p(n) by letting

p(n) := p_{k}(n)  for any k such that n ≤ n_{k} .

Now we want to show that a(n) does not satisfy RT_{1}. Notice that a(n) is nondecreasing (as p(1) > 0) and

a(n_{k}) ≥ p(n_{k}) = 2⌊f(n_{k})ȧ(n_{k})⌋ + 1 .

Let n ∈ [n_{k}, n_{k+1}]. Then

a_{k−1}(n) < f(n)ȧ(n) ,

so

a(n_{k} − 1) < f(n_{k})ȧ(n_{k})

and thus

\frac{a(n_{k})}{a(n_{k} − 1)} ≥ 2 .

One has

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

and an infinite sequence n_{k} with

a(n_{k})/a(n_{k} − 1) ≥ 2 ,

so a(n) certainly does not satisfy RT_{1} .

5. The Eventual Sandwich Theorem

Partition functions a(n), defined by partition identities

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

can be notoriously sensitive to changes in p(n) . However if p(n) satisfies RT_{1} then the situation is much more stable. The following says that if one removes any finite number of factors from the product expression in a partition identity and put back the same number of factors, but possibly with different powers of x involved, then the resulting partition function is asymptotic to a positive constant times the original partition function.

Lemma 5.1 (The Exchange Lemma). Let p_{1}(n) satisfy RT_{1}. If p_{1}(d_{1}) > 0 and d_{2} is a positive integer let

p_{2}(n) := p_{1}(n) + δ_{n=d_{2}} − δ_{n=d_{1}} .

Then

\frac{a_{1}(n)}{a_{2}(n)} ∼ \frac{d_{2}}{d_{1}} .

Proof. The connection between the two partition functions is described by

(15)  A_{2}(x) = (1 − x^{d_{2}})^{−1} · (1 − x^{d_{1}}) · A_{1}(x) .

Now, using the fact that both p_{1}(n) and p_{2}(n) satisfy RT_{1}, for j = 1, 2 one has

[x^{n}](1 − x^{d_{j}}) · A_{j}(x) = [x^{n}](1 + x + ⋯ + x^{d_{j}−1}) · A_{j}^{(1)}(x)
= a_{j}^{(1)}(n) + ⋯ + a_{j}^{(1)}(n − d_{j} + 1)
∼ d_{j} · a_{j}^{(1)}(n) .

From (15)

[x^{n}](1 − x^{d_{j}}) · A_{j}(x) = [x^{n}](1 − x^{d_{j}}) · A_{j}(x) .

Thus

\frac{a_{1}^{(1)}(n)}{a_{2}^{(1)}(n)} ∼ \frac{d_{2}}{d_{1}} .

Given ε > 0 choose N such that

|\frac{a_{1}^{(1)}(n)}{a_{2}^{(1)}(n)} − \frac{d_{2}}{d_{1}} | ≤ ε .

Then for n ≥ N,

(\frac{d_{2}}{d_{1}} − ε) · a_{2}^{(1)}(n) ≤ a_{1}^{(1)}(n) ≤ (\frac{d_{2}}{d_{1}} + ε) · a_{2}^{(1)}(n) .

Summing this gives

(\frac{d_{2}}{d_{1}} − ε) · (a_{2}(n) − a_{2}(M)) ≤ a_{1}(n) − a_{1}(M)
≤ (\frac{d_{2}}{d_{1}} + ε) · (a_{2}(n) − a_{2}(M)) ,

and this yields the result since a_{2}(n) → ∞ as n → ∞. □

Lemma 5.2 (Shuffle Lemma). Let p_{1}(n) satisfy RT_{1} and suppose p_{2}(n) differs from p_{1}(n) for only finitely many n. If

∑_{n} (p_{1}(n) − p_{2}(n)) = 0

we say p_{2}(n) is a shuffle of p_{1}(n). If p_{2}(n) is a shuffle of p_{1}(n) then, for some constant c > 0,

a_{2}(n) ∼ c · a_{1}(n) .

Proof. One can transform p_{1}(n) into p_{2}(n) by a finite sequence of exchanges as in Lemma 5.1. □

One of the difficulties with working with the Sandwich Theorem is that one needs to have ṗ(n) ≤ p(n) for all n ≥ 1, and often one only has the ‘eventually’ less than result ṗ(n) ⪯ p(n). The next theorem shows that if ṗ(n) satisfies RT_{1} then one has some much appreciated leeway.

Theorem 5.3 (The Eventual Sandwich Theorem). Suppose (i) ṗ(n) satisfies RT_{1} (ii) ṗ(n) ⪯ p(n) = O(ȧ(n))

(iii) ∑_{n} (p(n) − ṗ(n)) ≥ 0 .

Then

\frac{a(n − 1)}{a(n)} → 1 as n → ∞ .

Proof. Condition (iii) says precisely that one can find a finite shuffle p̂(n) of ṗ(n) such that for all n ≥ 1,

p̂(n) ≤ p(n) .

Then

p̂(n) ≤ p(n) = O(â(n))

since Lemma 5.2 gives

a(n) = O(â(n)) .

Consequently the Sandwich Theorem applies. □

6. The Classical Partition Function Heirarchy

Thanks to Theorem B that shows RT_{1} is preserved in the passage from p(n) to a(n), one can start with a favorite function satisfying RT_{1} and, by iterating this procedure, create an infinite heirarchy of “intervals” [p(n), O(a(n))] to use to prove that partition functions satisfy RT_{1}; and thus to prove logical 0–1 laws.

Our favorite heirarchy we call the Classical Partition Function heirarchy, and it is defined recursively as follows:

part_{0}(n) := 1  for n ≥ 1
∑_{n=0}^{∞} part_{k+1}(n)x^{n} = ∏_{n=1}^{∞} (1 − x^{n})^{−part_{k}(n)} .

Clearly the original partition function part(n) is part_{1}(n) in this heirarchy. Fortunately the asymptotics of this heirarchy have been well-studied using the tools of analytic number theory. One could use these results to see that each of the functions part_{k}(n) indeed satisfies RT_{1}; but invoking Theorem B seems much simpler. However these asymptotics allow us to draw other conclusions that strengthen our use of Sandwich Theorems. Thus they are given here in detail, following Petrogradsky’s presentation.

Theorem 6.1 (See Petrogradsky [11], Theorem 2.1). In the following the ‘input’ p(n) to a partition identity is in the left column, the ‘output’ a(n) is in the right column, where α ≥ 1 and k ≥ 1, and the constants θ and κ are defined after the table:

p(n)  a(n)
(σ + o(1)) · n^{α−1}  exp ((θ + o(1)) · n^{α/(α+1)})
exp ((σ + o(1)) · n^{α/(α+1)})  exp ((κ + o(1)) · \frac{n}{(log n)^{1/α}} )
exp ((σ + o(1)) · \frac{n}{(log^{(k)} n)^{1/α}} )  exp ((σ + o(1)) · \frac{n}{(log^{(k+1)} n)^{1/α}} )

where

θ = (1 + 1/α) · (σζ(α + 1) · Γ(α + 1))^{1/(α+1)}
κ = α · (\frac{σ}{α + 1})^{1+(1/α)} .

It is easy to verify that the p(n) discussed in Theorem 6.1 do indeed satisfy RT_{1} . The usual Hardy-Ramanujan asymptotics for part(n) do indeed fit into the above table:

part(n) ∼ \frac{exp (π\sqrt{2n/3})}{4\sqrt{3}n}
= exp ((π\sqrt{2n/3}) − ( log (4\sqrt{3}n))
= exp ((π\sqrt{2/3} − \frac{log (4\sqrt{3}n)}{\sqrt{n}}) · \sqrt{n})
= exp ((π\sqrt{2/3} + o(1)) · \sqrt{n})
= exp ((σ + o(1)) · \sqrt{n}) ,

where

σ = π\sqrt{2/3} .

Starting with this one can apply Theorem 6.1 to find the asymptotics for the classical partition heirarchy.

Corollary 6.2. Defining log^{(0)}(n) = 1 one has

part_{k}(n) = exp ((C_{k} + o(1)) · \frac{n}{(log^{(k−1)} n)^{1/2}} ) ,

for k ≥ 1 and for suitable positive constants C_{k}.

Corollary 6.3. For k, r ≥ 1 and ε > 0 one has

n^{n^{1−ε}} · part_{k}(n) = o(part_{k+1}(n))
part_{k}(n)^{r} = o(part_{k+1}(n)) .

Proof. By Corollary 6.2. □

Corollary 6.4. Given ε > 0 and k, r ≥ 1, suppose p(n) is a component function that satisfies one of the conditions: p(n) such that one of the following holds

part_{k}(n) ⪯ p(n) = O(part_{k}(n)^{r})
\frac{part_{m}(n)}{n^{n^{1−ε}}} ⪯ p(n) = O(part_{m}(n)) .

Then a(n) satisfies RT_{1}.

Proof. Apply the Eventual Sandwich Theorem to Corollary 6.3. □

Theorem 6.1 offers further concrete examples of function intervals which we can use to prove a(n) satisfies RT_{1}. These will be featured in the examples in Partition Identities II.

Corollary 6.5. If a partition identity satisfies one of the following conditions on p(n), where C_{1} > 0, ε > 0, k ≥ 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^{(k)} n)^{1/α}} ⪯ p(n) = O(e^{(C_{1}−ε)·n/( log^{(k+1)} n)^{1/α})}),

then

\frac{a(n − 1)}{a(n)} → 1 as n → ∞ .

Proof. Apply the Eventual Sandwich Theorem to Theorem 6.1. □

7. Logical 0–1 Laws

A class K of finite relational structures is adequate if it is closed under disjoint union and extracting components. A perfectly general way to construct an adequate class is to take a collection P of finite connected structures and let K be the class of finite structures with components from P. K has a MSO 0–1 law means that for every monadic second order sentence φ the probability that φ holds in a randomly chosen member of K is either 0 or 1. Define the count functions a_{K}(n) and p_{K}(n) as follows (counting up to isomorphism):

• a_{K}(n) is the number of members of K that have exactly n elements in their universe.

• p_{K}(n) is the number of members of P that have exactly n elements

in their universe. Compton ([8], [9]) showed that if K is an adequate class and a_{K}(n) satisfies RT_{1} then K has a monadic second-order 0–1 law.

Given any partition function a(n) satisfying RT_{1} there is a simple way to create an adequate class K with a_{K}(n) = a(n) . Start with the class of graphs G. The number p_{G}(n) of connected graphs of size n grows exponentially, certainly faster than p(n) as the radius of convergence of ∑ p_{G}(n)x^{n} is 0. Of course p(n) may exceed p_{G}(n) for a finite number of values, so add enough coloring predicates Red(x), Blue(x) etc., to the language of graphs so that the number of connected colored graphs of size n exceeds p(n) for all n ≥ 1. Now let P be a subclass of this class G_{c} of connected colored graphs with exactly p(n) members of size n. Let K be the class of all finite colored graphs whose components come from P.

Theorem 4.4 shows us how to find a vast array of partition identities satisfying RT_{1}, and thus one has a correspondingly vast array of classes of relational structures with a monadic second-order 0–1 law. Such examples are of course custom made. It is more satisfying to prove MSO 0–1 laws for naturally occurring classes of structures. We will conclude this section with the examples

• Forests of bounded height

• Varieties of MonoUnary Algebras

• Acyclic Graphs of bounded diameter

to illustrate the power of our new results. Before discussing these examples let it be mentioned that the previous techniques for proving a logical 0–1 law for adequate classes K (based solely on knowledge of a_{K}(n)) relied on the following results:

(A1) Finding explicit asymptotics for a_{K}(n). This is highly desirable, but rarely

possible. (A2) Applying Bell’s polynomially bounded result [3] : if p_{K}(n) = O(n^{k}) then

a_{K}(n) satisfies RT_{1}. (A3) Applying the ‘p is RT_{1}’ result from Bell and Burris [5] : if p_{K}(n) satisfies RT_{1}

then a_{K}(n) satisfies RT_{1}. (A4) Applying Stewart’s Sum Theorem to combine adequate classes K_{i} whose

count functions a_{K_{i}}(n) satisfy RT_{1} (see [7] Chap. IV).

7.1. Forests of Bounded Height. In this example one can view a forest as either a poset or as graph with rooted trees. In the poset case, the height of a forest is one less than the maximum number of vertices in a chain in the forest. Each of the classes is defined by a finitely many universally quantified sentences. For example in the poset case (where the tree roots are at the top) one can use

(∀x) (x ≤ x)
(∀x∀y) (x ≤ y & y ≤ z → x ≤ z)
(∀x∀y) ((x ≤ y & x ≤ z) → (y ≤ z) ∨ (z ≤ y)) .

Let F_{m} be the collection of forests of height at most m, and let p_{m}(n) and a_{m}(n) be its counting functions. For m = 0 one has p_{0}(1) = 1, and otherwise p_{0}(n) = 0; and a_{0}(n) = 1 for all n. For m = 1 clearly p_{1}(n) = 1 for all n ≥ 1, so a_{1}(n) = part(n). For m ≥ 1 it is easy to see that removing the root from a tree in F_{m} gives a forest in F_{m−1}, and indeed this operation is a bijection between the trees of F_{m} and all of F_{m−1}. Thus for m ≥ 1

p_{m}(n) = a_{m−1}(n − 1),

and this leads to the formula

p_{m}(n) = part_{m}(n − m) .

Thus F_{m} has a monadic second-order 0–1 law.

7.2. Varieties of MonoUnary Algebras. A monounary algebra S = (S, f) is a set with a unary operation. It has long been known that every variety of monounary algebras can be defined by a single equation, either one of the form f^{m}(x) = f^{m}(y) or f^{m+k}(x) = f^{m}(x). Only the trivial variety defined by x = y has unique factorization. However one can view any class of algebras as relational structures by simply converting n-ary operations into n + 1-ary relations. (Historically this is how logic developed, with function symbols being added later.) Although this is not the usual practice in algebra, for the purpose of logical properties it can be considered an equivalent formulation. If one treats the operation f of a monounary algebra as a binary relation then one obtains a digraph (directed graph) with the defining characteristics of a function, namely each vertex has a unique outdirected edge (possibly to itself). This formulation does not help with varieties defined by an equation of the form f^{m}(x) = f^{m}(y) as such a variety is not closed under disjoint union. However for the variety of monounary algebras M_{m,k} defined by the equation f^{m+k}(x) = f^{m}(x), the relational formulation gives an adequate class of relational structures, so one can view its finite members as an additive number system.

The connected digraphs of the models of the identity f^{m+k}(x) = f^{m}(x) look like a directed cycle (whose number of vertices divides k) with trees attached to some (perhaps all, perhaps none) of its vertices. Let the count functions for M_{m,k} be p_{m,k}(n) and a_{m,k}(n). Case k = 1: The connected digraphs of the models of an identity f^{m+1}(x) = f^{m}(x) look just like (rooted) trees of height at most m, so by our analysis of trees of bounded height one sees that each variety M_{m,1} has a monadic second-order 0–1 law. Case k > 1: Let a_{m,1,d}(n) count the number of arrangements of forests in M_{m,1} with at most d components in a directed cycle of d vertices. Then it is quite straightforward to see that

p_{m,1}(n) ≤ p_{m,k}(n)
= ∑_{d|k} a_{m,1,d}(n − d)

≤ ∑_{d|k} d! · a_{m,1}(n − d)
≤ k · k! · a_{m,1}(n) .

By our main theorem, and the previous case k = 1, it follows that a_{m,k}(n) satisfies RT_{1}, and the class M_{m,k} of monounary algebras has a monadic second-order 0–1 law.

7.3. Acyclic Graphs of Bounded Diameter. Let G_{d} be the class of acyclic graphs of diameter at most d, meaning here that the length of the longest path in the graph is at most d, where the length of a path with j vertices is j − 1.

Given a connected member of this class there is a vertex v such that the distance from v to any other vertex is at most ⌈d/2⌉ + 1. (Such a vertex is in the center of the graph.) Let

c(d) = ⌈d/2⌉
f(d) = ⌊d/2⌋ .

Now we claim that for all n ≥ 1

(16)  \frac{p_{F_{f(d)}}(n)}{n} ≤ p_{G_{d}}(n) ≤ p_{F_{f(d)}}(n) + n · p_{F_{f(d)−1}}(n − 1) .

For the lower bound note that any member of F_{f(d)} becomes a member of G_{d} by ignoring the root; and this map is at most n to 1. This gives the first inequality in (16).

For the upper bound note that any member of G_{d}(n) turns into a member of F(n) by simply designating a vertex to be the root. By choosing the root vertex in the center one obtains a member of F_{c(d)}(n). By snipping at most one leaf (and only if one has to) from the tree one has a member of F_{f(d)−1}(n) ∪ F_{f(d)}(n). This mapping is an injection for the part that maps into F_{f(d)}(n), and at most n to one for the part mapping into F_{f(d)−1}(n−1). Then using Corollary 6.3 this gives

\frac{p_{F_{f(d)}}(n)}{n} ≤ p_{G_{d}}(n)
≤ p_{F_{f(d)}}(n) + n · p_{F_{f(d)−1}}(n − 1)
= O(p_{F_{f(d)}}(n)) .

The component function for F_{k} is part_{k}(n − d), so by Corollary 6.4 every a_{F_{k}}(n) satisfies RT_{1}. Thus the class of acyclic graphs of diameter at most d enjoys RT_{1} growth and has a monadic second-order 0–1 law.

8. Generalized Partition Identities

Generalized partition identities allow p(n) to take on nonnegative real values. Essentially everything that has been presented goes through in this setting. The reason for restricting 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 results to apply to generalized partition identities is quite straightforward.

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, Sufficient conditions for zero-one laws. Trans. Amer. Math. Soc. 354 (2002), no. 2, 613–630.

[4] Jason P. Bell, Proofs of Dirichlet series conjectures of Burris. (Preprint)

[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 II. The Results of Bateman and Erdős. (Preprint, 2004).

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

[8] Kevin J. Compton, A logical approach to asymptotic combinatorics. I. First order properties. Adv. in Math. 65 (1987), 65–96.

[9] Kevin J. Compton, A logical approach to asymptotic combinatorics. II. Monadic second-order properties. J. Combin. Theory, Ser. A 50 (1989), 110–131.

[10] Phillipe Flajolet and Robert Sedgewick, The Average Case Analysis of Algorithms. (Online Draft.)

[11] Viktor M. Petrogradsky, On the growth of Lie algebras, generalized partitions, and analytic functions. Discrete Math. 217 (2000), 337-351.

[12] Herbert S. Wilf, Generatingfunctionology. 2nd ed., Academic Press, Inc., 1994.

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