TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY Volume 00, Number 0, Pages 000–000 S 0002-9947(XX)0000-0

ASYMPTOTICS FOR LOGICAL LIMIT LAWS: WHEN THE GROWTH OF THE COMPONENTS IS IN AN RT CLASS

JASON P. BELL AND STANLEY N. BURRIS

Abstract. Compton’s method of proving monadic second order limit laws is based on analyzing the generating function of a class of finite structures. For applications of his deeper results we previously relied on asymptotics obtained using Cauchy’s integral formula. In this paper we develop elementary techniques, based on a Tauberian theorem of Schur (as well as a modification of his theorem), that significantly extend the classes of structures for which we know that Compton’s theory can be applied.

1. Introduction

We are primarily interested in being able to show that an answer exists to the following question, given a class K of finite relational structures and a property Φ:

What is the probability that a finite structure, randomly selected from K, has the property Φ?

While pursing this goal we are able to prove (in Corollary 4.3) the conjecture ([10] p. 462) of Durrett, Granovsky and Gueron arising in the study of coagulation-fragmentation processes which says that if S(x) = ∑ s(n)x^{n} is a power series with positive coefficients such that s(n − 1)/s(n) → ρ then the coefficients of the power series expansion of exp (S(x)) have the same property.

The notion of probability that we use is to take the proportion q_{n} of finite structures of size n in K (we only count up to isomorphism) that have the property Φ, and then to take the limit q of the sequence q_{n} as n goes to infinity. This limit, when it exists, is also called the asymptotic density of the members of K that satisfy Φ.

It has been known since the mid 1970s that a few well known classes, like graphs or directed graphs, are such that if Φ is a property defined by

\begin{matrix}c \\ ◯ \end{matrix}1997 American Mathematical Society

Received by the editors February 4, 2003.

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

Key words and phrases. ratio test, Schur’s Tauberian theorem, asymptotic density, monadic second order logic, zero-one law, limit law.

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

a first-order sentence then the probability must exist, and be 0 or 1. If K is a class such that every sentence in a given (logic) language L defines a property for which a probability exists then we say K has an L-limit law.

In the 1980s Kevin Compton gave a new method for proving that a class K of relational structures has a monadic second-order limit law, a method that only depends on analyzing the growth rate of a(n), the number of structures of size n in K. This applies to classes that are closed under disjoint union and components. For such classes the count function p(n), the number of components of size n in K, is often more readily available than a(n), and we would like to know conditions on p(n) that guarantee a logical limit law. The best results of this type previously known were

• if p(n) = O(n^{c}), that is, p(n) is polynomially bounded, then K has a monadic second order 0–1 law (Bell [1]), and

• if p(n) = Cβ^{n} + O(γ^{n}), where 0 < γ < β and C > 0, then K has a monadic second order limit law (see [4], Chapters 5 and 6).

We will make use of a Tauberian theorem of Schur, and a variant of his theorem, to extend these results to cover a large number of new classes of structures. For example, we will show that

p(n) ∼ an^{b}e^{cn^{d}},

with d < 1 and a, c > 0, yields a monadic second-order 0–1 law; and Corollary 9.4. For μ < 1 < β and C > 0, or μ = 1 < β and C > 1, the condition

p(n) ∼ Cβ^{n}/n^{μ}

guarantees that K has a monadic second order limit law.

In addition to the standard ‘big O’ and ‘little o’ notation from asymptotics we use the following:

notation  means
f(n) ≺ g(n) f(n) is eventually less than g(n)
f(n) ≼ g(n) f(n) is eventually less than or equal to g(n)
f(n) ≻ g(n) f(n) is eventually greater than g(n)
f(n) ≽ g(n) f(n) is eventually greater than or equal to g(n)

As mathematics symbols we will be using upper case boldface roman letters exclusively to denote power series, and the corresponding lower case ordinary italic letters name the coefficients. Thus we will use A(x) = ∑_{n} a(n)x^{n},…, T(x) = ∑_{n} t(n)x^{n}.

2. The class RT_{ρ}

The sequences in RT_{ρ} play a central role in the study of Compton’s development of logical limit laws. We find conditions to guarantee membership in this class and then apply them to prove logical limit laws.

Definition 2.1. RT_{ρ} is the collection of sequences s(n) of real numbers that satisfy (a) s(n) ≻ 0, and

(b) lim_{n→∞} \frac{s(n − 1)}{s(n)} = ρ.

We also say that a power series S(x) is in RT_{ρ} if its sequence of coefficients s(n) is in RT_{ρ}. And if f(x) is a function that admits a power series expansion ∑ s(n)x^{n} about 0 then we say f(x) is in RT_{ρ} if s(n) is in RT_{ρ}.

The following lemma and corollary give the most basic information about the growth rate of members of RT_{ρ}.

Lemma 2.2. If s(n) ∈ RT_{ρ} with 0 < ρ < ∞ then, for 0 < ε < ρ^{−1}, there is an N such that, for n ≥ N,

(ρ^{−1} − ε)^{n} < s(n) < (ρ^{−1} + ε)^{n}.

From this we see that a smaller ρ leads to much faster growing sequences.

Corollary 2.3. If s(n) ∈ RT_{σ} and t(n) ∈ RT_{τ} with 0 < σ < τ < ∞ then t(n) = o(s(n)).

The class RT_{ρ} has some remarkable similarities to the class RV_{α}, the class of functions of regular variation at infinity with index α, but this connection does not seem to have been thoroughly researched. For 0 < ρ < ∞ the sequence ρ^{−n} is perhaps the simplest member of the class RT_{ρ}. And this sequence, along with RT_{1}, completely determines RT_{ρ}, as one can easily check that

s(n) ∈ RT_{ρ} ⟺ s(n)ρ^{n} ∈ RT_{1}.

In terms of power series this would be written as

(2.1)  S(x) ∈ RT_{ρ} ⟺ S(ρx) ∈ RT_{1}.

Here are three of the simplest examples from RT_{1}:

s(n) = c  for c > 0
s(n) = n^{c}  for c any real number
s(n) = d^{n^{c}}  for c < 1 < d.

We can use these examples, with Proposition 2.4, to make a substantial collection of sequences in RT_{ρ}. Multiplication of the sequences s(n) and t(n) gives s(n)·t(n), and division gives s(n)/t(n), where we define s(n)/t(n) to be 0 whenever t(n) = 0.

Proposition 2.4. RT_{1} is closed under multiplication, division, and asymptotically equal. And, for 0 < σ, τ < ∞, if s(n) ∈ RT_{σ} and t(n) ∈ RT_{τ} then 1/s(n) ∈ RT_{1/σ}, and s(n) · t(n) ∈ RT_{στ}. Furthermore S(x) ∈ RT_{ρ} iff S′(x) ∈ RT_{ρ} iff xS(x) ∈ RT_{ρ}.

Proof. (Straightforward.) □

With this we can easily see, for example, that for a, c, ρ > 0 and b any real number, if s(n) ∼ an^{b}e^{c\sqrt{n}}/ρ^{n} then s(n) ∈ RT_{ρ}. Just such an example played an important role in finding the first applications of Compton’s 1989 theoretical development of logical limit laws. A key fact about this particular sequence is that an^{b}e^{c\sqrt{n}} ∈ RT_{1}, and it is eventually nondecreasing.

3. The Cauchy product

The Cauchy product R(x) = S(x) · T(x) is defined by

r(n) = ∑_{k=0}^{n} s(k) · t(n − k).

The following two lemmas and corollary help us extract information about RT_{ρ} classes from the Cauchy product. We start with the classic Tauberian theorem of Schur.^{1}

Lemma 3.1 (Schur). With 0 ≤ ρ < ∞, suppose that (a) A(x) ∈ RT_{ρ},

(b) B(x) has radius of convergence greater than ρ, and

(c) B(ρ) > 0. Let C(x) = A(x) · B(x). Then

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

Proof. (See Bender [3] or Burris [4].) □

Thus from the hypotheses of Schur’s Lemma we deduce C(x) ∈ RT_{ρ}.

Corollary 3.2. With 0 < ρ < ∞, suppose A(x) ∈ RT_{ρ} and the radius of convergence of B(x) is greater than ρ. If B(ρ) > 0 then

A(x) · B(x) ∈ RT_{ρ}.

Proof. Let C(x) = A(x) · B(x). From Schur’s Lemma we have

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

so, by Proposition 2.4, C(x) ∈ RT_{ρ}. □

The next lemma offers a variation on this theme.

Lemma 3.3. Suppose C(x) = A(x) · B(x), where A(x) and B(x) have nonnegative coefficients and B(x) is not the zero power series. If

(a) A(x) ∈ RT_{ρ}, where 0 < ρ < ∞,

(b) b(n) = o(c(n)), and

(c) \frac{c(n − 1)}{c(n)} ≼ ρ,

then C(x) ∈ RT_{ρ}.

1It is a Tauberian theorem as it gives an extra condition, namely the radius of convergence of B(x) > ρ, to allow us to go from a generalized limit, lim_{x→ρ} C(x)/A(x), to an ordinary limit, lim_{n→∞} c(n)/a(n).

Proof. From the following equivalent statements

A(x) = B(x) · C(x) iff A(ρx) = B(ρx) · C(ρx)
A(x) ∈ RT_{ρ}  iff A(ρx) ∈ RT_{1}
b(n) = o(c(n))  iff b(n)ρ^{n} = o(c(n)ρ^{n})
\frac{c(n − 1)}{c(n)} ≼ ρ  iff \frac{c(n − 1)ρ^{n−1}}{c(n)ρ^{n}} ≼ 1,
C(x) ∈ RT_{ρ}  iff C(ρx) ∈ RT_{1}

it suffices to prove the lemma in the case that ρ = 1. With ρ = 1 the goal is:

from (a′) A(x) ∈ RT_{1}, (b′) b(n) = o(c(n)), and (c′) c(n−1) ≼
c(n), prove that C(x) ∈ RT_{1}.

Let ε > 0. By (a′) there exists an integer M such that, for n > M,

(3.1)  |a(n) − a(n − 1)| < εa(n).

Since A(x) ∈ RT_{1} implies a(n) ≻ 0, and B(x) is not the zero power series, we have c(n) ≻ 0. So, in view of (c′) we can also assume that M is sufficiently large to guarantee

(3.2)  n ≥ M ⟹ \{ \begin{matrix}c(n) > 0, and \\ \frac{c(n − 1)}{c(n)} ≤ 1. \end{matrix}

By assumption (b′) we can find an integer N > M such that

(3.3)  b(n) ≤ \frac{ε}{(M + 1) max (1, a(0), …, a(M))} · c(n)

for n ≥ N − M.

Now suppose n ≥ M + N. Then, by (3.2),

(3.4)  0 < c(n − M) ≤ ⋯ ≤ c(n − 1) ≤ c(n).

For n ≥ M + N,

c(n) − c(n − 1) = ∑_{i=0}^{n} a(n − i) · b(i) − ∑_{i=0}^{n−1} a(n − 1 − i) · b(i)
= ∑_{i<n−M} (a(n − i) − a(n − 1 − i)) · b(i)

+ ∑_{i=n−M}^{n} a(n − i) · b(i) − ∑_{i=n−M}^{n−1} a(n − 1 − i) · b(i)

≤ ε ∑_{i=0}^{n} a(n − i) · b(i) + ∑_{i=n−M}^{n} εc(i)/(M + 1) by (3.1), (3.3)

≤ εc(n) + ∑_{i=n−M}^{n} εc(n)/(M + 1) by (3.4)
= 2εc(n).

Therefore 1 − 2ε ≤ \frac{c(n − 1)}{c(n)} ≤ 1. As this holds for any n > M + N, we

have lim_{n→∞} \frac{c(n − 1)}{c(n)} = 1, so C(x) ∈ RT_{1}. □

4. Exponentiation

We will be particularly interested in knowing that exponentiation of a power series preserves membership in RT_{ρ}. First we prove a special case of this result.

Lemma 4.1. Let T(x) = exp (S(x)), where

(a) S(x) ∈ RT_{1},

(b) the s(n) are nonnegative, and

(c) lim inf_{n→∞} \frac{t(n)}{t(n − 1)} = C > 0.

Then T(x) ∈ RT_{1}.

Proof. Note that C ≤ 1 as the radius of convergence of T(x) is 1. From S(x) ∈ RT_{1} we know xS′(x) ∈ RT_{1}, so, given ε > 0, we can choose M such that

|ms(m) − (m − 1)s(m − 1)| < εms(m)

for m ≥ M. Also we can choose N such that \frac{t(n)}{t(n − 1)} > \frac{C}{2} for n > N.

From this we see that

(4.1)  n − r > N ⟹ \frac{t(n)}{t(n − r)} > \frac{C^{r}}{2^{r}} .

Differentiating T(x) = exp (S(x)) we have

T′(x) = S′(x)T(x),

and equating the coefficients of x^{n−1} on both sides of this equation gives

(4.2)  nt(n) = ∑_{m≤n} t(m) · (n − m)s(n − m).

From this it follows that if n > N + M (we adopt the convention that s(m) = 0 for m < 0),

|nt(n) − (n − 1)t(n − 1)|
=  | ∑_{m≤n} t(m) · ((n − m)s(n − m) − (n − 1 − m)s(n − 1 − m))|
≤  ∑_{0≤m≤n−M} t(m) · ε(n − m)s(n − m)

+ ∑_{n−M<m≤n} t(m) · |(n − m)s(n − m) − (n − 1 − m)s(n − 1 − m)|

≤ εnt(n) + 2 · ( max_{0≤m≤M} ms(m)) · ∑_{n−M<m≤n} t(m) by (4.2)
≤ εnt(n) + 2M · ( max_{0≤m≤M} s(m)) · M2^{M} · C^{−M} · t(n) by (4.1)
= (ε + o(1))nt(n).

Thus nt(n) ∈ RT_{1}, so t(n) ∈ RT_{1}. □

Lemma 4.2. S(x) ∈ RT_{1} ⟹ exp (S(x)) ∈ RT_{1}.

Proof. Let T(x) = exp (S(x)). Since s(n) ∈ RT_{1} and 2^{−n} ∈ RT_{2}, by Corollary 2.3 there exists N such that s(n) > 2^{−n} for n > N. Define ŝ(n) to be 1 for 0 ≤ n ≤ N and to be s(n) for n > N. Let Ŝ(x) = ∑_{n} ŝ(n)x^{n}, and let T̂(x) = ∑_{n} t̂(n)x^{n} be such that T̂(x) = exp (Ŝ(x)). Since

ŝ(n) ≥ 2^{−n}/n, for n ≥ 1,

Ŝ(x) + log(1 − x/2) is a power series with nonnegative coefficients. Thus, for n ≥ 0,

t̂(n) − t̂(n − 1)/2 = [x^{n}](1 − x/2)T̂(x)
= [x^{n}] exp ( log(1 − x/2) + Ŝ(x))
≥ 0,

so

lim inf_{n→∞} \frac{t̂(n)}{t̂(n − 1)} ≥ 1/2 > 0.

Now T̂(x) ∈ RT_{1} by Lemma 4.1 as Ŝ(x) ∈ RT_{1}. To finish the proof, observe that

S(x) − Ŝ(x) = p(x),

where p(x) is a polynomial, so

T(x) = exp (p(x)) · T̂(x).

By Corollary 3.2, T(x) ∈ RT_{1}. □

Next we see that RT_{ρ} classes are closed under exponentiation of power series, proving the conjecture ([10] p. 462) of Durrett, Granovsky and Gueron.

Corollary 4.3. For 0 < ρ < ∞,

S(x) ∈ RT_{ρ} ⟹ exp (S(x)) ∈ RT_{ρ}.

Proof. This follows from (2.1) and Lemma 4.2. □

If we exponentiate a power series in RT_{ρ} that diverges at ρ then we obtain a power series whose coefficients grow much faster than those of the original series.

Lemma 4.4. Let T(x) = exp (S(x)) where (a) S(x) ∈ RT_{ρ} with 0 < ρ < ∞, and

(b) S(ρ) = ∞. Then s(n) = o(t(n)).

Proof. First we prove this lemma for the case that the coefficients of S(x) are nonnegative. Choose N ≥ 1 and observe that, for n ≥ N,

t(n) = ∑_{j≥0} \frac{1}{j!}[x^{n}]S(x)^{j} ≥ \frac{1}{2}[x^{n}]S(x)^{2} ≥ \frac{1}{2} ∑_{k=0}^{N} s(k)s(n − k)

and thus

\frac{t(n)}{s(n)} ≥ \frac{1}{2} ∑_{k=0}^{N} s(k)\frac{s(n − k)}{s(n)}.

Taking the lim inf_{n→∞} of both sides, using the fact that S(x) ∈ RT_{ρ}, gives

lim inf_{n→∞} \frac{t(n)}{s(n)} ≥ \frac{1}{2} ∑_{k=0}^{N} s(k)ρ^{k}.

Now use the fact that S(ρ) = ∞.

For the general case, where some of the coefficients of S(x) can be negative, let p(x) be a polynomial such that Ŝ(x) = S(x)+p(x) has nonnegative coefficients. Clearly Ŝ(x) ∈ RT_{ρ} and Ŝ(ρ) = ∞. Then T̂(x) = exp (Ŝ(x)) is such that

(4.3)  ŝ(n) = o(t̂(n)),

by the first part of the proof. And by Corollary 4.3, T̂(x) ∈ RT_{ρ}. As

T(x) = exp ( − p(x)) · T̂(x),

by Schur’s Lemma we have

t(n) ∼ exp ( − p(ρ)) · t̂(n),

so from (4.3) we have s(n) = o(t(n)) since s(n) eventually equals ŝ(n). □

A modest growth condition on the coefficients of S(x) guarantees that the coefficients of exp (S(x)) satisfy a growth condition used to prove logical limit laws. But first we prove a technical lemma on membership in RT_{1}.

Lemma 4.5. Suppose S(x) ∈ RT_{1}. Then

lim inf_{n→∞} s(n) > 1 ⟹ s(n) − 1 ∈ RT_{1}.

Proof. Choose C, N > 1 such that s(n) ≥ C, for n ≥ N. Then, for n ≥ N,

(4.4)  1 − \frac{1}{s(n)} ≥ \frac{C − 1}{s(n)} ≥ C − 1 > 0.

Now

\frac{s(n − 1) − 1}{s(n) − 1} − 1 = \frac{\frac{s(n−1)}{s(n)} − 1}{1 − \frac{1}{s(n)}},

and the right side tends to 0 as n tends to infinity since s(n) ∈ RT_{1} says the numerator tends to 0, and (4.4) says the denominator is bounded away from 0. Thus

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

□

Now we proceed with the analysis of the growth rate of the coefficients after exponentiation.

Lemma 4.6. Let T(x) = exp (S(x)) where (a) S(x) ∈ RT_{ρ} with 0 < ρ < ∞, and

(b) lim inf_{n→∞} ns(n)ρ^{n} > 1.

Then T(x) ∈ RT_{ρ} and \frac{t(n − 1)}{t(n)} ≺ ρ.

Proof. Corollary 4.3 gives T(x) ∈ RT_{ρ}. To verify t(n − 1) ≺ t(n)ρ note that

t(n)ρ^{n} − t(n − 1)ρ^{n−1} = [x^{n}]((1 − x) · T(ρx))
= [x^{n}]((1 − x) · exp (S(ρx)))
= [x^{n}] exp (s(0) + ∑_{n≥1} (s(n)ρ^{n} − 1/n)x^{n}).

As S(x) ∈ RT_{ρ},

ns(n)ρ^{n} ∈ RT_{1},

and then Lemma 4.5 gives ns(n)ρ^{n} − 1 ∈ RT_{1}. Using Proposition 2.4 we have

(4.5)  s(n)ρ^{n} − 1/n ∈ RT_{1}.

Choose N ≥ 1 such that, for n ≥ N,

(4.6)  ns(n)ρ^{n} > 1,

and let

p(x) = s(0) + ∑_{n=1}^{N−1} (s(n)ρ^{n} − 1/n)x^{n} − ∑_{n=1}^{N−1} x^{n}

R(x) = ∑_{n=1}^{N−1} x^{n} + ∑_{n=N}^{∞} (s(n)ρ^{n} − 1/n)x^{n}.

By (4.5) we know that R(x) ∈ RT_{1}, so Lemma 4.2 gives

(4.7)  exp (R(x)) ∈ RT_{1}.

Noting that p(x) is a polynomial we have

t(n)ρ^{n} − t(n − 1)ρ^{n−1} = [x^{n}] exp (s(0) + ∑_{n≥1} (s(n)ρ^{n} − 1/n)
= [x^{n}]( exp (p(x)) · exp (R(x)))
∼ exp (p(1)) · [x^{n}] exp (R(x))

by (4.7) and Schur’s Lemma, and thus, as the coefficients of R(x) are positive,

t(n)ρ^{n} − t(n − 1)ρ^{n−1} ≻ 0.

This says \frac{t(n − 1)}{t(n)} ≺ ρ. □

5. The star transformation

Now we introduce a transformation on a power series S(x) that plays an important role in combinatorics.

Definition 5.1. Let S^{⋆}(x) = ∑ s^{⋆}(n)x^{n} be the power series defined by

s^{⋆}(0) = 0
s^{⋆}(n) = ∑_{jk=n} s(j)/k for n ≥ 1.

Lemma 5.2. For 0 < ρ < 1, if S(x) ∈ RT_{ρ} has nonnegative coefficients then

(a) s^{⋆}(n) ∼ s(n), and

(b) S^{⋆}(x) ∈ RT_{ρ}.

Proof. Since s(n) ∈ RT_{ρ} we know from Corollary 2.3 that 0 < β < ρ^{−1} < α implies

n^{2}β^{n} = o(s(n)) and s(n) = o(α^{n})

as n^{2}β^{n} ∈ RT_{1/β} and α^{n} ∈ RT_{1/α}. Choose α satisfying ρ^{−1} < α < ρ^{−2} and choose C such that |s(n)| < Cα^{n} for all n. Choose N such that s(n) ≥ 0 for n ≥ N. Then

ns^{⋆}(n) = ∑_{d|n} ds(d)

≤ ns(n) + ∑_{d≤n/2} ds(d)

≤ ns(n) + ∑_{d≤n/2} dCα^{n/2}
= ns(n) + O(n^{2}α^{n/2})
= ns(n) + o(s(n))  (since \sqrt{α} < ρ^{−1}).

Hence ns^{⋆}(n) ∼ ns(n) as 0 ≤ s(n) ≤ s^{⋆}(n), and thus s^{⋆}(n) ∼ s(n), giving (a). Then from Proposition 2.4 we have S^{⋆}(x) ∈ RT_{ρ}. □

This result is best possible as one can easily find examples with ρ = 1 such that S(x) ∈ RT_{1} but S^{⋆}(x) ∉ RT_{1}. For example, S(x) = ∑_{n} x^{n} ∈ RT_{1}, but S^{⋆}(x) = ∑_{n} σ(n)x^{n}/n ∉ RT_{1}. However the power series expansion of \frac{x}{1 − x} · S^{⋆}′(x) is much better behaved in this situation.

Lemma 5.3. Suppose s(n) ∈ RT_{1} is a sequence of nonnegative terms. Then

s^{⋆}(1) + ⋯ + ns^{⋆}(n) ∈ RT_{1}.

Proof. Let S^{⋆}(n) = s^{⋆}(1) + ⋯ + ns^{⋆}(n). Then

(5.1)  S^{⋆}(n) = ∑_{j=1}^{n} ⌊\frac{n}{j}⌋js(j)

as

S^{⋆}(n) = ∑_{m=1}^{n} ms^{⋆}(m) = ∑_{jk=1}^{n} jk · s(j)/k = ∑_{jk=1}^{n} js(j) = ∑_{j=1}^{n} ⌊\frac{n}{j}⌋js(j).

Also

(5.2)  S^{⋆}(n) − S^{⋆}(n − 1) = ns^{⋆}(n) = ∑_{d|n} ds(d).

We shall show that S^{⋆}(n) − S^{⋆}(n − 1) is o(S^{⋆}(n)).

Fix ε ∈ (0, 1) and choose

(5.3)  M > \frac{1}{ε(1 − ε)}.

For any fixed integer r, \frac{(n − r)s(n − r)}{ns(n)} → 1 as n tends to infinity. Hence

we can choose N > M^{3} such that

|ns(n) − (n − r)s(n − r)| < εns(n)

for 0 ≤ r ≤ M and n ≥ N/M, and thus

(5.4)  (n − r)s(n − r) > (1 − ε)ns(n)

for 0 ≤ r ≤ M and n ≥ N/M.

For integers d_{1}, d_{2} with 1 ≤ d_{1} < d_{2} ≤ M, and for n ≥ N, we have

\frac{n}{d_{1}} − \frac{n}{d_{2}} = \frac{n(d_{2} − d_{1})}{d_{1}d_{2}} ≥ \frac{n}{M^{2}} > \frac{M^{3}}{M^{2}} = M,

and thus \frac{n}{d_{2}} < \frac{n}{d_{1}} − M.

Consequently, for n ≥ N, if d_{1} < ⋯ < d_{k} are the divisors of n from the interval [1, M] we see that

(5.5) \frac{n}{M} < \frac{n}{d_{k}} − M < \frac{n}{d_{k}} < \frac{n}{d_{k−1}} − M < ⋯ < \frac{n}{d_{1}} − M < \frac{n}{d_{1}} .

Returning to the expression for S^{⋆}(n) in (5.1), now assuming that n ≥ N, we have

S^{⋆}(n) = ∑_{j=1}^{n} ⌊\frac{n}{j}⌋js(j)

= ∑_{1≤j≤n/M} ⌊\frac{n}{j}⌋js(j) + ∑_{n/M<j≤n} ⌊\frac{n}{j}⌋js(j)

≥ ∑_{1≤j≤n/M} Mjs(j) + ∑_{n/M<j≤n} js(j)

≥ \frac{1}{ε} ∑_{1≤j≤n/M} js(j) + ∑_{{d|n \atop d<M}} ( ∑_{{n/d−M ≤ j \atop j ≤ n/d}} js(j)) by (5.3), (5.5)

≥ \frac{1}{ε} ∑_{{d|n \atop d≤n/M}} ds(d) + ∑_{{d|n \atop d<M}} M(1 − ε)\frac{n}{d} · s(\frac{n}{d}) by (5.4)

≥ \frac{1}{ε} ∑_{{d|n \atop d≤n/M}} ds(d) + \frac{1}{ε} ∑_{{d|n \atop d>n/M}} ds(d) by (5.3)

= \frac{1}{ε} ∑_{d|n} ds(d)

= \frac{1}{ε}(S^{⋆}(n) − S^{⋆}(n − 1)) by (5.2)

Thus 0 ≤ S^{⋆}(n) − S^{⋆}(n − 1) ≤ εS^{⋆}(n), so S^{⋆}(n) ∈ RT_{1}. □

6. Combining star with exponentiation

Theorem 6.1. Let T(x) = exp (S^{⋆}(x)), where (a) S(x) ∈ RT_{ρ} with 0 < ρ < 1,

(b) the s(n) are nonnegative, and

(c) lim inf_{n→∞} ns(n)ρ^{n} > 1.

Then T(x) ∈ RT_{ρ} and \frac{t(n − 1)}{t(n)} ≺ ρ.

Furthermore, if S(ρ) = ∞ then s(n) = o(t(n)).

Proof. S^{⋆}(x) ∈ RT_{ρ} by Lemma 5.2, so T(x) ∈ RT_{ρ} by Corollary 4.3. From 0 ≤ s(n) ≤ s^{⋆}(n) we have lim inf_{n→∞} ns^{⋆}(n)ρ^{n} > 1. Thus t(n − 1) ≺ t(n)ρ by Lemma 4.6.

For the final assertion assume S(ρ) = ∞. Then S^{⋆}(ρ) = ∞, so from Lemma 4.4 we have s^{⋆}(n) = o(t(n)), and thus s(n) = o(t(n)). □

When ρ = 1 we can no longer assume S^{⋆}(x) ∈ RT_{1} just because S(x) ∈ RT_{1}. Instead we turn to xS^{⋆}′(x)/(1 − x) to find a well behaved sequence of coefficients.

Theorem 6.2. Let T(x) = exp (S^{⋆}(x)) where (a) S(x) ∈ RT_{1},

(b) the s(n) are nonnegative, and

(c) s(n) ≽ 1/n. Then exp (S^{⋆}(x)) ∈ RT_{1}. Furthermore, s(n) = o(t(n)).

Proof. From

(6.1)  s^{⋆}(n) ≥ s(n) ≽ 1/n

it follows that there exists a polynomial p(x) such that

(6.2)  S^{⋆}(x) + p(x) + log(1 − x)

has nonnegative coefficients. Then

(6.3)  R(x) = exp (S^{⋆}(x) + p(x))

has nonnegative coefficients. Since (6.2) has nonnegative coefficients it also follows that the exponential of (6.2) has nonnegative coefficients, that is,

(6.4)  [x^{n}]((1 − x) · R(x)) ≥ 0.

Differentiating (6.3), and multiplying through by x, gives

xR′(x) = x(S^{⋆}′(x) + p′(x)) · R(x)
= (x(1 − x)^{−1}(S^{⋆}′(x) + p′(x))) · (1 − x)R(x).

We will use Lemma 3.3 with

A(x) = x(1 − x)^{−1}(S^{⋆}′(x) + p′(x))
B(x) = (1 − x)R(x)
C(x) = xR′(x).

For n larger than the degree of p(x), we have

a(n) = [x^{n}](x(1 − x)^{−1}S^{⋆}′(x) + x(1 − x)^{−1}p′(x))
(6.5)  = s^{⋆}(1) + ⋯ + ns^{⋆}(n) + p′(1).

From (6.1) we have S^{⋆}′(1) = ∞, and thus

(6.6)  p′(1) = o( ∑_{m<n} ms^{⋆}(m)).

From (6.5) and (6.6) it follows that

(6.7)  a(n) ∼ s^{⋆}(1) + ⋯ + ns^{⋆}(n),

so by Lemma 5.3 and Proposition 2.4, A(x) ∈ RT_{1}. This is condition (a) of Lemma 3.3.

B(x) has nonnegative coefficients by (6.4), and since R(x) also has nonnegative coefficients,

0 ≤ b(n) = [x^{n}](1 − x)R(x) ≤ r(n) = [x^{n}]xR′(x)/n = c(n)/n,

so b(n) = o(c(n)). This gives condition (b) of Lemma 3.3.

From (6.4) we also have

c(n) − c(n − 1) = nr(n) − (n − 1)r(n − 1) ≥ 0.

Hence condition (c) of Lemma 3.3 holds.

So, by Lemma 3.3, C(x) ∈ RT_{1}, that is, xR′(x) ∈ RT_{1}. Then R(x) ∈ RT_{1} by Proposition 2.4, so from Corollary 3.2 we have

T(x) = exp ( − p(x)) · R(x) ∈ RT_{1}.

Finally, condition (c) implies S(1) = ∞, so

s(n) = o([x^{n}] exp (S(x)))

by Lemma 4.4. Now 0 ≤ s(n) ≤ s^{⋆}(n) leads to

[x^{n}] exp (S(x)) ≤ [x^{n}] exp (S^{⋆}(x)) = [x^{n}]T(x)

and thus s(n) = o(t(n)). □

7. Compton’s approach to logical limit laws

A class K of finite relational structures is said to be adequate if it is closed under disjoint union and components, and, up to isomorphism, it has only finitely many structures of each size. Let p(n) count (up to isomorphism) the number of component structures in K of size n, and let a(n) count the total number of structures in K of size n. The combinatorial identity connecting the two counting functions a(n) and p(n) is

(7.1)  A(x) = exp (P^{⋆}(x)),

where

\begin{matrix}A(x) = ∑ a(n)x^{n} & P^{⋆}(x) = ∑ p^{⋆}(n)x^{n} \\ p^{⋆}(0) = 0 & p^{⋆}(n) = ∑_{jk=n} p(j)/k for n ≥ 1. \end{matrix}

The connection between adequate classes and (7.1) is very tight, for if p(n) is any nonnegative integer valued function with p(0) = 0 then there is an adequate class K with p(n) the count function for the components of K, and the function a(n) satisfying (7.1) is the total count function for K.

Compton proved two main theorems for the purpose of finding classes K with logical limit laws. We assume that K is an adequate class of relational structures with the counting functions a(n) and p(n) as described above. Furthermore we assume a(n) ≻ 0.^{2} The striking feature of Compton’s theorems is that he is able to prove logical limit laws just from knowing information about the counting function a(n). Note that if a(n) ∈ RT_{ρ} then 0 ≤ ρ ≤ 1 as the a(n) are integers. We only consider 0 < ρ ≤ 1 as Compton’s method does not work for the case ρ = 0. (The case ρ = 0 requires more knowledge about K than just the count functions to determine if there is a logical limit law.)

Theorem 7.1 (Compton, 1987/1989). If a(n) ∈ RT_{1} then K has a monadic second order 0–1 law.

Theorem 7.2 (Compton, 1989). If a(n) ∈ RT_{ρ}, where 0 < ρ < 1, and if there exist K and C such that

(7.2)  \frac{a(n − k)}{a(n)} ≤ Cρ^{k} for K ≤ k ≤ n

then K has a monadic second order limit law.

8. A useful corollary

For applications of Theorem 7.2 we use the following.

Corollary 8.1. Suppose a(n) ∈ RT_{ρ} and \frac{a(n − 1)}{a(n)} ≼ ρ. Then K has a

monadic second order limit law.

Proof. Choose K ≥ 1 such that

n ≥ K ⟹ \{ \begin{matrix}a(n) > 0, and \\ \frac{a(n − 1)}{a(n)} ≤ ρ. \end{matrix}

Now suppose K ≤ k ≤ n.

Case 1: If n − k ≥ K then

\frac{a(n − k)}{a(n)} = \frac{a(n − k)}{a(n − k + 1)} ⋯ \frac{a(n − 1)}{a(n)} ≤ ρ^{k}.

2This is the same as requiring that the gcd of the sizes of the components be 1.

Case 2: If n − k < K then

\frac{a(n − k)}{a(n)} = \frac{a(n − k)}{a(K)} \frac{a(K)}{a(n)}
≤ \frac{a(n − k)}{a(K)}ρ^{n−K}  by Case 1
= (\frac{a(n − k)}{a(K)}ρ^{n−K−k})ρ^{k}
≤ (\frac{1}{a(K)} · max (a(0), ⋯, a(K − 1)) · ρ^{−K})ρ^{k}.

Thus Theorem 7.2 applies. □

9. Applications to logical limit laws

Now we use our results to improve the scope of the conditions on p(n) that lead to classes of structures covered by Compton’s theorems.

Theorem 9.1. If p(n) ∈ RT_{1} then K has a monadic second order 0–1 law.

Proof. This follows from Theorems 6.2 and 7.1 after noting that p(n) is always a nonnegative integer. □

This theorem yields many classes of structures that, before, were not known to have a 0–1 law. For example if

p(n) ∼ an^{b}e^{cn^{d}},

with d < 1 and a, c > 0, then one has a monadic second-order 0–1 law. Previously the known comprehensive general collection of count functions p(n) which implied such a law was the family of polynomially bounded p(n), that is, p(n) = O(n^{c}) for some c (see Bell [1]). Now we have entire families of superpolynomial count functions p(n) which guarantee such laws.

Example 9.2. Let K be the class of finite directed graphs G = (G, R) satisfying the first-order conditions

∀x(∃y(yRx) ↔ xRx)
∀x∀y((xRx)&(xRy) → (yRx))
∀x∀y∀z((xRx)&(xRy)&(yRz) → (xRz))
∀x(¬(xRx) → ∃!y(xRy))

Such a digraph consists of an equivalence relation plus a possibly empty collection of vertices that each have but one edge attached to them, and that edge is outgoing to an element in the equivalence relation. The vertices comprising the equivalence relation are precisely those in the range of the binary relation R. The indecomposable members of K are those with a single equivalence class. It is easy to see that p(n) is the number of partitions of the integer n, which we know from the famous results of Hardy and Ramanujan to satisfy

p(n) ∼ \frac{1}{4\sqrt{3}}n^{−1}e^{\sqrt{2/3}πn^{1/2}}.

By Theorem 9.1 we see that K has a monadic second-order 0–1 law.

Theorem 9.3. Suppose 0 < ρ < 1. If (a) p(n) ∈ RT_{ρ} and

(b) lim inf_{n→∞} np(n)ρ^{n} > 1

then K has a monadic second order limit law.

Proof. From Theorem 6.1 we know a(n) ∈ RT_{ρ} as well as \frac{a(n − 1)}{a(n)} ≺ ρ, so

Corollary 8.1 applies. □

Prior to Theorem 9.3 all applications of Compton’s Theorem 7.2 were based on the asymptotics of Knopfmacher, Knopfmacher, and Warlimont [11] that say if

(9.1)  p(n) = C_{1}β^{n} + O(γ^{n}),  0 < γ < β, C_{1} > 0

then

a(n) ∼ C_{2}β^{n}e^{2\sqrt{an}}/n^{3/4},  for some C_{2} > 0.

These results were proved by the well known use of Cauchy’s integral theorem for asymptotics, in this case

a(n) = \frac{1}{2πi} ∫_{C} exp (P^{⋆}(z)) · \frac{dz}{z^{n+1}} .

From the hypothesis (9.1) we immediately have ρ = 1/β and p(n) ∈ RT_{ρ} as well as lim inf_{n→∞} np(n)ρ^{n} > 1. Thus Theorem 9.3 covers condition (9.1). But we can say much more. In the following corollary we focus on generalizing the Cβ^{n} asymptotics, and drop any reference to an error term.

Corollary 9.4. For μ < 1 < β and C > 0, or μ = 1 < β and C > 1, the condition

p(n) ∼ Cβ^{n}/n^{μ}

guarantees that K has a monadic second order limit law.

Proof. From Proposition 2.4 we see that p(n) ∈ RT_{ρ}, where ρ = 1/β, and the condition lim inf_{n→∞} np(n)ρ^{n} > 1 is readily verified. Thus Theorem 9.3 applies. □

Example 9.5. For a fixed positive integer k let K be the class of finite kcolored linear forests. (The components of linear forests are chains. If k = 4 then one can think of a member of K as a collection of DNA fragments.) Then

p(n) ∼ k^{n}

so by Corollary 9.4 we know that K has a monadic second-order limit law.

Example 9.6. For h a fixed positive integer let K be the class of finite forests of planted plane trees of height at most h, that is, the class of finite graphs whose components are planted plane trees of height at most h.

The basic study of the generating function P(x) := ∑ p(n)x^{n} for finite planted plane trees can be found in the 1972 paper [9] of de Bruijn, Knuth and Rice. From their work we know that

P(x) = \frac{f(x)}{g(x)}

where f(x) and g(x) are the polynomials given by

f(x) = 2x · \frac{(1 + \sqrt{1 − 4x})^{h} − (1 − \sqrt{1 − 4x})^{h}}{\sqrt{1 − 4x}}

g(x) = \frac{(1 + \sqrt{1 − 4x})^{h+1} − (1 − \sqrt{1 − 4x})^{h+1}}{\sqrt{1 − 4x}} .

They also note that the degree of g(x) is d = ⌊h/2⌋, and that g(x) has d distinct positive roots r_{j} given by

r_{j} = \frac{1}{4} sec^{2} (\frac{jπ}{h + 1}) for 1 ≤ j ≤ d.

Of course we need h ≥ 2 in order for g(x) to have any roots. Clearly 0 < r_{1} < … < r_{d}, and for h ≥ 3 the smallest root r_{1} lies in the interval (1/4, 1/2].

Given that h ≥ 3, for some c ≠ 0 we have

g(x) = c(x − r_{1}) ⋯ (x − r_{d}),

so by the method of partial fractions,

\frac{1}{g(x)} = ∑_{j=1}^{d} \frac{c_{j}}{x − r_{j}} where c_{j} = c^{−1} ∏_{i≠j}(r_{j} − r_{i})^{−1}.

From this we easily have

p(n) = [x^{n}]\frac{f(x)}{g(x)}

= − ∑_{j=1}^{d} c_{j}f(r_{j})/r_{j}^{n+1}  for n ≥ ⌊\frac{h − 1}{2}⌋ (= deg(f))

∼ −c_{1} \frac{f(r_{1})}{r_{1}}(\frac{1}{r_{1}} )^{n},

and thus for h ≥ 3 the class K has a monadic second-order limit law by Corollary 9.4. In the cases h = 1, 2 the values p(n) are uniformly bounded, and thus one has a monadic second-order 0-1 law.

Remark 9.7. If we change the condition μ < 1 in Corollary 9.4 to μ > 1 then we can find examples of classes K with such a count function p(n) which fail to have a first-order limit law.

Remark 9.8. We can construct, for any given ρ with 0 < ρ ≤ 1, an infinite sequence K_{m} of classes of finite relational structures with monadic second order limit laws such that the count functions p_{m}(n) and a_{m}(n) for K_{m} are in RT_{ρ} and growing infinitely faster at each successive step, that is, we have

p_{m}(n) = o(a_{m}(n)) and a_{m}(n) = o(p_{m+1}(n)).

To construct the sequence we start with

p_{0}(n) = ⌊1/ρ^{n}⌋, for n ≥ 1.

Then

a_{0}(n) = [x^{n}] exp (P_{0}^{⋆}(x))

gives p_{0}(n) = o(a_{0}(n)) by Theorem 6.1 or 6.2. Now observe that by modifying a_{0}(n), by simply setting a_{0}(0) to 0, we have a sequence that can be used as a p(n), satisfying the premises of Theorem 6.1 or 6.2. Inductively define p_{k+1} and a_{k+1} by: p_{k+1}(0) = 0 and

p_{k+1}(n) = [x^{n}] exp (A_{k}^{⋆}(x)),  for n ≥ 1
a_{k+1}(n) = [x^{n}] exp (P_{k+1}^{⋆}(x)), for n ≥ 0,

where P_{k}(x) = ∑_{n} p_{k}(n)x^{n} and A_{k}(x) = ∑_{n} a_{k}(n)x^{n}. Now take classes K_{m} with counting functions a_{m}(n), p_{m}(n).

In the case that ρ = 1 these classes have, for m ≥ 1, both count functions with superpolynomial growth, growing far faster than the classes with polynomially bounded p(n) that were, with minor exceptions, the only ones that were previously known to have a monadic second order 0–1 law. And likewise, with 0 < ρ < 1, the classes K_{m}, for m ≥ 1, grow far faster than any examples that we knew before with a monadic second order limit law.

References

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

[2] Jason P. Bell, Edward A. Bender, Peter J. Cameron, L. Bruce Richmond, Asymptotics for the probability of connectedness and the distribution of number of components. Electron. J. Combin. 7 (2000), R33.

[3] Edward A. Bender, Asymptotic methods in enumeration. SIAM Rev. 16 (1974), 485– 515.

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

[5] Stanley Burris, Spectrally determined first-order limit laws. Logic and Random Structures (New Brunswick, NJ, 1995), 33–52, ed. by Ravi Boppana and James Lynch. DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 33, Amer. Math. Soc., Providence, RI, 1997.

[6] Stanley Burris and András Sárközy, Fine spectra and limit laws I. First-order laws. Canad. J. Math. 49 (1997), 468–498.

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

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

[9] N.G. de Bruijn, D.E. Knuth and S.O. Rice, The average height of planted plane trees. Graph Theory and Computing, Academic Press, New York, 1972, pp. 15–22.

[10] R. Durrett, B. Granovsky, and S. Gueron, The equilibrium behavior of reversible coagulation-fragmentation processes. J. Theoret. Probab. 12 (1999), 447–474.

[11] Arnold Knopfmacher, John Knopfmacher and Richard Warlimont, “Factorisatio numerorum” in arithmetical semigroups. Acta Arith. 61 (1992), 327–336.

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