Jason P Bell

Stanley N Burris
email: snburris@rogers.com.

Karen A Yeats
email: karen.yeats@math.sfu.ca.

Monadic Second-Order Classes of Forests with a Monadic Second-Order 0-1 Law

Keywords: Trees, forests, monadic second-order class, ordinary generating function, radius of convergence, Compton equations, 0-1 law

Let T be a monadic-second order class of finite trees, and let T(x) be its (ordinary) generating function, with radius of convergence ρ. If ρ ≥ 1 then T has an explicit specification (without using recursion) in terms of the operations of union, sum, stack, and the multiset operators n and (≥ n). Using this, one has an explicit expression for T(x) in terms of the initial functions x and x • 1 -x n -1 , the operations of addition and multiplication, and the Pólya exponentiation operators En, E (≥n) .

Let F be a monadic-second order class of finite forests, and let F(x) = n f (n)x n be its (ordinary) generating function. Suppose F is closed under extraction of component trees and sums of forests. Using the above-mentioned structure theory for the class T of trees in F, Compton's theory of 0-1 laws, and a significantly strengthened version of 2003 results of Bell and Burris on generating functions, we show that F has a monadic second-order 0-1 law iff the radius of convergence of F(x) is 1 iff the radius of convergence of T(x) is ≥ 1.

Introduction

In the late 1980s, Compton ([10], [START_REF]A logical approach to asymptotic combinatorics. II. Monadic second-order properties[END_REF]) introduced a new method to show that a class A of finite relational structures has a monadic second-order (MSO) 0-1 law, (i) a method that depended only on a property of the generating function A(x) for A, and not on the nature of the structures in the class. The precondition imposed on the class A was that it be closed under the extraction of components and sums of its members-we say such a class is adequate (or Compton-admissible). Compton analyzed both labelled and unlabelled classes-this paper concerns unlabelled classes A and their associated ordinary generating functions A(x) = a(n)x n . Theorem 1.1 (Compton) Let d be the gcd of the sizes of the members of an adequate class A of relational structures, and let ρ A be the radius of convergence of the generating function A(x) of A.

(a) If A has a first-order 0-1 law then ρ A ∈ {0, 1}.

(b) If ρ A > 0, then A has a monadic second-order 0-1 law iff it has a first-order 0-1 law iff

lim n→∞ a (n -1)d a(nd) = 1. (1.1)
This paper is about adequate classes of forests-for a class F of forests, the radius of convergence ρ F of the generating function F(x) = n f (n)x n is always positive. Thus Compton's Theorem on 0-1 laws is slightly simpler in the case of forests.

Corollary 1.2 Given an adequate class F of forests, let d be the gcd of the sizes of the forests in F. Then F has a monadic second-order 0-1 law iff it has a first-order 0-1 law iff

lim n→∞ f (n -1)d f (nd) = 1.
Common examples of adequate classes of forests are usually MSO-classes, that is, they are defined by a MSO-sentence. For example, Compton applied his theorem to two adequate classes of forests, namely to (1) forests of trees of height 1, and (2) forests of linear trees-these are clearly MSO classes. An adequate class F of forests is determined by its subclass T of trees, and F is a MSO-class iff T is a MSO-class. MSO-classes of trees include most of the basic examples of classes of trees one finds in the literature, for example, trees of bounded height, chains, trees of bounded width, binary trees, etc.

Although condition (1.1) is exceedingly simple to state, it can be challenging to verify that it actually holds for a given adequate class A. Most of the practical success in this direction has been in finding conditions on the generating function P(x) = n p(n)x n of the class P of components of A, conditions which ensure A satisfies (1.1). Notable results are: (1) Bell's theorem ( [START_REF] Bell | Sufficient conditions for zero-one laws[END_REF], 2002), which says that polynomially bounded growth of the component count function p(n) is sufficient, (ii) and (2) Bell and Burris's theorem ( [START_REF] Stanley | Asymptotics for logical limit laws: when the growth of the components is in an RT class[END_REF], 2003), which says that p (n -1)d /p(nd) → 1 is sufficient. Although these results have greatly increased the scope of application of Compton's theory, finding a comprehensive practical approach to verifying (1.1) remains a vexing problem. (For a recent survey of results that have augmented Compton's theory, see [START_REF]Compton's method for proving logical limit laws[END_REF].)

This paper provides a transparent description of when an adequate MSO-class F of forests has a MSO 0-1 law. Let T be the class of trees in F. Then F has a MSO 0-1 law iff ρ F = 1 iff ρ T ≥ 1 iff T has an explicit specification in terms of four natural operations on classes of trees.

The proof involves three key steps: First a structure theorem is established which shows that a MSOclass of trees T with ρ T ≥ 1 has an explicit (non-recursive) specification. Secondly, using this result, a description of the generating function T(x) of T is determined. Thirdly, the arguments used in the above-mentioned [START_REF] Stanley | Asymptotics for logical limit laws: when the growth of the components is in an RT class[END_REF] are thoroughly reworked to cover the generating functions described in the second step.

(ii) An analog of Bell's polynomial bound theorem was proved for labelled structures in 2008 by Burris and Yeats [START_REF] Yeats | Sufficient conditions for a labelled 0-1 law, Discrete Math[END_REF].

Preliminaries

The radius of a class of forests is the radius of convergence of its ordinary generating function. A class of forests must have its radius in [0, 1]∪{∞} since the coefficients of the generating function are nonnegative integers. The classes with radius infinity are precisely the finite classes (whose generating functions are polynomials). Compton's test for a MSO 0-1 law for a class F of forests requires the radius of the class to equal 1, and thus the radius of the class T of trees in F must be ≥ 1.

Forests of rooted trees occur in two basic incarnations, namely as acyclic graphs and posets. The choice of fundamental language, whether that of graphs (with a binary edge relation E and a unary root relation R), or that of posets (with a less than relation <), is not significant-being definable by a MSO sentence is a robust concept that is not affected by the choice of the basic relation(s). In this paper forests are posets (F, <).

Capital boldface letters will be used for power series, and the corresponding lowercase letters for the coefficients. For example,

A(x) = ∞ n=0 a(n)x n .
Given a class T of trees, T(x) := n≥1 t(n)x n is used for its generating function, where t(n) counts (up to isomorphism) the number of trees of size n in T . Likewise F(x) := n≥1 f (n)x n is the generating function for a class F of forests. It will be usual to abbreviate a forest (F, <) simply as F ; and likewise a tree (T, <) as T . The one-element tree is •; it is also the only one-element forest.

Four Class Constructions

This section describes the four natural constructions-union, sum, multiset and stack-that will be used to give a transparent description of a MSO-class of trees of radius ≥ 1. Namely such a class is a composition of these constructions applied to the initial object, which is the singleton class of the one-element tree. The first three constructions, union, sum and multiset, are well-known and can be used with any class of purely relational structures (such as graphs, posets, etc.).

We use the following definitions:

(a) Two forests F 1 and F 2 are disjoint if they have no elements in common, that is,

F 1 ∩ F 2 = Ø. We also say F 1 is disjoint from F 2 .
(b) Two classes F 1 and F 2 of forests are disjoint if no member of F 1 is isomorphic to a member of F 2 .

(c) The components of a forest are the maximal connected substructures, which are trees.

(d) Two forests F 1 and F 2 are component-disjoint if, up to isomorphism, they have no components in common. We also say

F 1 is component-disjoint from F 2 .
(e) Two classes F 1 and

F 2 of forests are component-disjoint if every forest F 1 in F 1 is component- disjoint from every forest F 2 in F 2 .

The Union Construction

Given classes F 1 , . . . , F m of forests, the union operation i F i is just as one would expect:

m i=1 F i = F : F ∈ F i for some i .
If the classes F 1 , . . . , F m are pairwise disjoint and F is the union of these classes, then the generating function for F is just the sum of the generating functions for the F i , that is,

F(x) = m i=1 F i (x).

The Sum Construction

Given forests F 1 , . . . , F m , the sum operation

m i=1 F i , or F 1 + • • • + F m ,
is defined by taking a disjoint union of the F i . This means we rename the elements of the forests (F i , < i ) so the sets F i are pairwise disjoint, and then we form the forest (F, <)

:= i F i , i < i .
Clearly the size of F is the sum of the sizes of the F i . For classes F 1 , . . . , F m of forests, the sum of the classes is given by (iii)

m i=1 F i = F 1 + • • • + F m : F i ∈ F i .
If the classes F 1 , . . . , F m are pairwise component-disjoint then we speak of a component-disjoint sum F := i F i , and in this case the generating function of F is the product of the generating functions of the F i , that is,

F(x) = m i=1 F i (x).
This follows from the fact that every forest F has a unique decomposition into components.

If the classes of forests F i are actually classes of trees T i , then we drop the prefix 'component-', and speak of two classes of trees being disjoint, and of a disjoint sum F = i T i . If the classes T 1 , . . . , T m are pairwise disjoint then we speak of a disjoint sum F := i T i .

The Multiset Constructions

Given a class T of trees, γT is the class of forests where each member F is a sum of γ many copies of trees from T (allowing repeats). The two forms for γ that we use are m and (≥ m), where m ≥ 0 :

mT := m i=1
T (iii) Note, the union operation gives the union of classes of forests, whereas the sum operation gives the class whose members are disjoint unions of forests from the classes.

(≥ m)T := n≥m nT .

The generating function [γT ](x) for γT is easily derived from the generating function for T using the following operators that act on power series: (iv)

E 0 A(x) := 1 E m A(x) := m j=1 1 j! m1+•••+mj =m mi≥1 1 m 1 • • • m j • A(x m1 ) • • • A(x mj ), m > 0 E (≥m) A(x) := ∞ j=m E j A(x) , m ≥ 0.
We often abbreviate E (≥0) to E. For γ any coefficient we have

[γT ](x) = E γ T(x) . (3.1)
An adequate class of forests F is one of the form (≥ 1)T , that is, it consists of all the forests that can be formed using the trees from T . Adequate classes of forests are precisely the classes of forests that are closed under sum and the extraction of component trees.

The Stack Construction

As already mentioned, the previous three constructions are general purpose constructions that one can use with any classes of relational structures. However the stack construction described in this section has been specially designed for the study of trees.

Given a tree T and a node ν in the tree, T [ν] is the full subtree of T rooted at ν, consisting of all the elements of T that are ≤ ν. Given another tree T 1 , T [ν/T 1 ] is the tree obtained by replacing T [ν] in T by T 1 .

A (construction) module M = (T, λ) is a tree T with a designated leaf λ. The one-element module is called 1 M . The stack construction can be applied to a pair of modules or to a module and a tree. The stack

M 1 • M 2 , where M i = (T i , λ i ), is the module (T 1 [λ 1 /T 2 ], λ 2 ). The stack M 1 • T 2 , where M 1 = (T 1 , λ 1 ), is the tree T 1 [λ 1 /T 2 ].
Let MODULES denote the class of modules. Then (MODULES, •, 1 M ) is a monoid (since the stack operation is associative). (v) A module M = (T, λ) is indecomposable in this monoid iff λ is a node immediately below the root of T . Furthermore, since there is a unique maximal chain going from the root of T to λ, it follows that the monoid of modules has the unique factorization property, and thus the cancellation property. This implies the monoid of modules is actually a free monoid, freely generated by its indecomposable members. (iv) The function Em comes from the well-known formula for the generating function for the set of objects that can be expressed as a sum of exactly m components (see Appendix B of [START_REF] Stanley | Number Theoretic Density and Logical Limit Laws[END_REF]). (v) The referee pointed out that pointed trees (that is, trees with a designated leaf), and the monoid described here, are well-known from the theory of regular tree languages-see, for example, [START_REF] Bojanczyk | Forest algebras[END_REF] or [START_REF] Gecseg | Tree automata[END_REF] .

Stacking n copies of a given module M := (T, λ) gives M n , where

M 0 = 1 M . Let M ≥0 := n≥0 M n . The size |M | of a module M := (T, λ
) is defined to be |T | -1, one less than the size of the tree in the module. Thus we have

1 M = 0 M 1 • M 2 = M 1 + M 1 M • T = M + T M n = n • M .
We can view stack as a class operation:

M 1 • M 2 = M 1 • M 2 : M i ∈ M i M • T = M • T : M ∈ M, T ∈ T , with the special cases M • M, M • T , etc.
, where one of the classes is a singleton.

Given a tree T and a chain of nodes ν 0 > ν 1 > . . . > ν k , with ν 0 the root of the tree, one has a decomposition of the tree as a stack

T = M 0 • M 1 • • • • • M k-1 • T k (3.2)
where

M i := (T i , ν i+1 ) with T i := T [ν i ] T [ν i+1 ] ν i+1 , for 0 ≤ i < k, and T k := T [ν k ]. If ν 0 > ν 1 > . . . > ν k is a maximal chain then (3.
2) is a complete stack decomposition of T .

Compton's Equations and the Dependency Digraph

Let F be a MSO-class of forests. Then the subclass T of trees in F is also a MSO-class. Using Ehrenfeucht-Fraïsse games, in 1986 Compton noted that every MSO class of trees has an equational specification. (vi) To describe this we need one more definition, namely if F is a forest let • F denote the tree obtained by adding a new element to F that is greater than all elements in F . Then, for F a class of forests, let

• F := • F : F ∈ F .
A MSO-class defined by a MSO-sentence of quantifier depth at most q is called a MSO q -class. (When determining the quantifier depth, both first-order and monadic second-order quantifiers are counted.) The next proposition gives an equational specification Σ q , which we call the Compton equations, for the minimal MSO q -classes of trees, and from these equations one derives an equational system defining the generating functions of these classes. Proposition 3.1 (Compton) Given a positive integer q, let T 0 , . . . , T n be the partition of the class of all trees into minimal MSO q -classes, where T 0 has the one-element tree as its only member. Then one has the following: (a) Any MSO q -class T is a union of some of the T i .

(b) There are finite sets Γ i whose members γ γ γ are sequences γ 0 , . . . , γ n of coefficients, each of the form m or (≥ m), such that one has the following system Σ q of Compton equations providing a (vi) This result was first published by Woods [START_REF] Woods | Coloring rules for finite trees, probabilities of monadic second order sentences[END_REF] in 1997, with credits to Compton.

specification for the classes T i :

Σ q : T 0 = {•} T i = • γ γ γ∈Γi n j=0 γ j T j for 1 ≤ i ≤ n.
For each γ γ γ ∈ Γ i , the γ j T j are pairwise component-disjoint classes of forests, and the j γ j T j are pairwise disjoint classes of forests.

(c) From (b) one has the generating functions T i (x) for the T i defined by the system of equations:

T 0 (x) = x T i (x) = x • γ γ γ∈Γi n j=0 γ j T j (x) for 1 ≤ i ≤ n.
Given a system Σ q of Compton equations, let ρ i be the radius of the class T i , 0 ≤ i ≤ n. The dependency digraph for the system is D q = ({0, 1, . . . , n}, →), where i → j means that some γ γ γ ∈ Γ i is such that γ j = 0. → + is the transitive closure of →. Note, by Proposition 3.1(c), that i → j, and hence i → + j, implies ρ i ≤ ρ j . The strong component of an element i of the dependency digraph is

[i] := j ∈ D q : i → + j → + i . Thus j ∈ [i] implies ρ i = ρ j . If [i] = Ø then T i is an infinite class of trees and ρ i ≤ 1.
We say i > j in D q if i → + j, but not conversely. Define the rank of i ∈ D q to be its height in the poset ({0, 1, . . . , n}, >).

The modules M ij

Given a system Σ q of Compton equations, for 0 ≤ i, j ≤ n let

M ij = M ∈ MODULES : M • T j ⊆ T i . Lemma 3.2 Suppose [i] = Ø and ρ i = 1.
(a) There is a unique module

M ii ∈ M ii such that M ii = (M ii ) ≥0 . (b) For each j ∈ [i] there is a unique module M ij such that M ij = M ij • M jj = M ii • M ij . (c) ([i], →) is a directed cycle.
Proof: If (a) fails then there are two modules M 1 and M 2 in M ii such that neither has a proper stack factorization by modules in

M ii . Define M := M 1 , M 2 , m := max(|M 1 |, |M 2 |)
, and let T ∈ T i . Then M m+n+1 • T is a subset of T i , and, by examining complete decompositions using chains of maximum length, one sees that T i has at least 2 n trees of size at most m(m+n+1)+|T |. This contradicts the assumption that ρ i = 1.

For item (b), first it is clear that Item (c) follows from an argument like that used for (a). Two distinct minimal paths from j to j, for any j ∈ [i], would lead to ρ j < 1, which would contradict the fact that all ρ k are equal, for k ∈ [i]. 2

M ii = 1 M . For i = j, note that M ji • M ij ⊆ M jj . Let M ∈ M ij , N ∈ M ji . Then N • M ∈ M jj ,

Explicit descriptions

Proposition 3.3 Let Σ q be a system of Compton equations, and suppose T i has radius ≥ 1. Then one has the following description of T i in terms of the T j with j of smaller rank, for 1 ≤ i ≤ n. This leads to a corresponding expression for T i (x).

(a) Suppose [i] = Ø. Then the Compton equations give a description of T i in terms of the T j with j of smaller rank; and likewise for the T i (x).

(b) Suppose [i] = Ø. Let Γ 0 i = γ γ γ ∈ Γ i : γ j = 0 for all j ∈ [i] . Then T i = k∈[i] (M ii ) ≥0 • M ik • • γ γ γ∈Γ 0 k n j=0 γ j T j T i (x) = k∈[i] x | M ik |+1 1 -x |Mii| • γ γ γ∈Γ 0 k n j=0 E γj T j (x) . Proof: If [i] = Ø the result is clear.
For [i] = Ø one has ρ i ≤ 1 since T i is infinite, so we can apply Lemma 3.2. Let T be a tree in T i , and let ν 0 > ν 1 > • • • ν k be a maximal chain in T . Define w : {0, . . . , k} → {1, . . . , n}, a map from the indices of the nodes ν i to the dependency digraph, by w(x) = y if T [ν x ] ∈ T y . As x moves from 0 to k, the image w(x) moves m times around the directed cycle ([i], →), from i to i each time, for some m ≥ 0, and then either immediately exits the cycle or makes a partial trip around the cycle to some node and then exits the cycle. Let ε(i) be the node of the cycle from which w(x) exits the cycle.

Let r be the number of elements in [i]; and let s = 0 if i = ε(i), otherwise let s be the length of the shortest directed path in the directed cycle from i to ε(i). Then w(0) = w(r) = . . . = w(mr) = i and w(mr + s) = ε(i). The stack of the first mr + s modules in the stack decomposition of T derived from

ν 0 > • • • > ν k gives the module (M ii ) m • M iε(i) .
We can assume the chain of nodes ν x was chosen so that the number of elements of [i] in the range of w is maximum. This means that T [ν mr+s ] ∈ T 0 ε(i) , where

T 0 ε(i) = • γ γ γ∈Γ 0 ε(i) n j=0 γ j T j . (T 0 ε(i)
is the class of trees in T ε(i) whose proper subtrees are not in T for any ∈ [i].) Putting these facts together, we have

T ∈ (M ii ) m • M iε(i) • T [ν mr+s ],
leading to the description of T i in (b). The translation into an expression for T(x) is straightforward. 2

Corollary 3.4 Let T be a MSO q -class of trees of radius ≥ 1. Then T has an explicit specification (without using recursion) in terms of the operations of union, sum, stack, and the multiset operators n and (≥ n). Also T(x) has an explicit description as a composition of functions corresponding to these operations.

Proof: Let T 1 , . . . , T m be the minimal MSO q -classes of radius ≥ 1. Then each of the T i has such a specification by Proposition 3.3, and T is a disjoint union of some of these T i . For the second claim we have T(x) = Ti⊆T T i (x), and the T i (x) have explicit descriptions in Proposition 3. Proof: For (a), use induction on the rank of i to prove this for each T i , in view of Proposition 3.3. Then use the fact that T is a union of some of the T i , and G is closed under addition. For (b), note that the base functions have radius of convergence ≥ 1, and applying the operations and operators preserves this property.

2

In order to understand the behavior of generating functions in G, we examine a larger class S.

The Class S of Power Series

Given two sequence r(n), s(n) of real numbers, we use the notation r(n) ≺ s(n) to mean r(n) is eventually less than s(n), and the notation r(n) s(n) to mean r(n) is eventually less than or equal to s(n).

Likewise we define r(n) s(n) and r(n) s(n).

To define the class S we need the notion of RT 1 .

The classes RT 1 , RT 1

Let A be an adequate class of relational structures, and let P be the class of components of A. The ordinary generating functions P(x) and A(x) are related by the partition identity:

1 + ∞ n=1 a(n)x n = ∞ n=1 1 -x n -p(n) . (4.1)
Let N be the set of nonnegative integers. The period of A is

d := gcd n : p(n) > 0 = gcd n : a(n) > 0 . a(n) is 0 if d n,
lim n→∞ a(n -1) a(n) = 1. (4.2)
Let

RT 1 := R(x) ∈ R[[x]] : r(n) 0 and lim n→∞ r(n -1) r(n) = 1 RT 1 [d] := R x d : R(x) ∈ RT 1 , for d ∈ N {0} RT 1 := d∈N\{0} RT 1 [d].

It will be convenient to write

A ∈ RT 1 , resp. A ∈ RT 1 , if A(x) ∈ RT 1 , respectively A(x) ∈ RT 1 . Likewise r(n) ∈ RT 1 means R(x) ∈ RT 1 . Define the classes RTN 1 , RTN 1 [d] and RTN 1 by intersecting the classes RT 1 , RT 1 [d] and RT 1 with N[[x]].
Using this notation, Compton's condition (1.1) can be stated as A(x) ∈ RT 1 . The main result in [START_REF] Stanley | Asymptotics for logical limit laws: when the growth of the components is in an RT class[END_REF] to prove MSO 0-1 laws was E RTN 1 ⊆ RT 1 . To prove our main theorem, Theorem 5.1, we need the much stronger result E S ⊆ RT 1 which is stated in Proposition 4.14 (the class S is defined in §4.3).

Basic results about RT 1 and RT 1

The Cauchy product C(x) of two power series A(x) and B(x) is defined by (c) RTN 1 is closed under multiplication by positive integers as well as Cauchy product.

c(n) := n j=0 a(j) • b(n -j).
Proof: For (a), suppose A(x), B(x) ∈ RT 1 , and r is a positive real. Clearly rA(x) ∈ RT 1 . For the other conditions, note that R(x) ∈ RT 1 iff r(n) 0 and r(n) -r(n -1) = o r(n) . Then to show RT 1 is closed under addition use

a(n) + b(n) -a(n -1) + b(n -1) = a(n) -a(n -1) + b(n) -b(n -1) = o a(n) + o b(n) = o a(n) + b(n) ,
as well as noting that a(n) + b(n) 0. To show closure under Cauchy product we have

a(n)b(n) -a(n -1)b(n -1) = a(n) b(n) -b(n -1) + a(n) -a(n -1) b(n -1) = a(n)o b(n) + o a(n) b(n) + o b(n) = o a(n)b(n) ,
along with a(n)b(n) 0. For asymptotic equality let c(n) ∼ a(n). Then c(n) 0, and

c(n -1) c(n) ∼ a(n -1) a(n) → 1 as n → ∞.
(c) C(x) ∈ RT 1 . Let A(x) := B(x) • C(x). Then a(n) ∼ B(1) • c(n). Proof: (See §3.8 of [8].) 2
Corollary 4.3 Suppose that B(x) and C(x) are power series such that the radius of convergence of B(x) is greater than 1, and

C(x) ∈ RT 1 . If B(1) > 0 then B(x) • C(x) ∈ RT 1 . Lemma 4.4 Suppose A(x) = B(x) • C(x)
, where A(x) and B(x) have nonnegative coefficients and C(x) is not the zero power series. If

(a) a(n -1) a(n) 1, (b) b(n) = o a(n) , and (
c) C(x) ∈ RT 1 , then A(x) ∈ RT 1 .
Proof: This is Lemma 3.3 of [START_REF] Stanley | Asymptotics for logical limit laws: when the growth of the components is in an RT class[END_REF].

2 Lemma 4.5 Let A(x) ∈ N[[x]
] have coefficients that are eventually positive, and suppose that for some

u ≥ 0, a(n) -a(n -1) = o a(n) + . . . + a(n -u) .
Then A(x) ∈ RT 1 .

Proof: By (the proof of) Lemma 4.2 of [START_REF]Partition Identities I. Sandwich Theorems and 0-1 Laws[END_REF]. 2

The definition of S

Let S be the set of power series

P(x) ∈ x • N[[x]
] {0} that can be expressed in the form

p 0 (x) + k i=1 p i (x) • R i x di , (4.3)
where

p i (x) ∈ N[x] for 0 ≤ i ≤ k, R i (x) ∈ RTN 1 , and
d i ∈ N \ {0}, for 1 ≤ i ≤ k. Let Q := x c R x d ∈ x • N[[x]] : c, d ∈ N, R(x) ∈ RTN 1 , 0 ≤ c < d .
Note that every member of S can be expressed as a polynomial from x • N[x] plus a sum of zero or more members of Q.

Lemma 4.6 Given a member of S, say

P(x) = p 0 (x) + k =1 x c R x d ,
let d be a positive integer divisible by all the exponents d (d can be any positive integer if P(x) = p 0 (x)).

Then one can express P(x) in the form

p 0 (x) + i∈I x ci S i x d , (4.4)
where the x ci S i (x d ) are in Q, and I is a finite subset of N.

Proof: We only need to consider the case that P(x) is not a polynomial. Suppose

x a • R x b ∈ Q with b d. Then x a • R x b = x a ∞ n=0 r(n)x nb = x a d/b -1 j=0 ∞ n=0 r j + d b n x jb+nd = d/b -1 j=0 x a+jb ∞ n=0 r j + d b n x d n = d/b -1 j=0 x a+jb • S j (x d ),
where the S j (x) are the power series in the previous line. One easily verifies that each

x a+jb • S j (x d ) which is non-zero is in Q. Apply this to each of the x c R (x d ) to obtain x c R (x d ) = d/d -1 j=0 x c +jd S j,l (x d ).
Then let

S i (x) = j, c l +jd =i S j, (x)
to obtain the desired result.

2

Lemma 4.7

(a) x • N[x] {0} ⊆ S. (b) x • RTN 1 ⊆ x • RTN 1 ⊆ S.
(c) S contains the functions x, and x/(1 -x m ) for m ≥ 1, and is closed under the operations of scalar multiplication by positive integers, addition and Cauchy product.

Proof: Properties (a) and (b) are obvious. For (c), note that the function x is a polynomial, and x/(1 -

x m ) ∈ RTN 1 since x/(1 -x) ∈ RTN 1 ; so x, x/(1 -x m ) ∈ S.
Clearly S is closed under scalar multiplication by positive reals, and under addition. To show that S is closed under Cauchy product, take P 1 (x), P 2 (x) ∈ S and express each one in the form (4.4), using the same d. Multiply out the two sums, and note that R(x), S(x)

∈ RT 1 implies R(x) • S(x) ∈ RT 1 , by Lemma 4.1, thus R(x d ) • S(x d ) ∈ RT 1 . 2

The Star Transformation

The star transformation on a power series plays an important role in enumeration of unlabelled structures and in additive number systems, namely given A(x) and P(x) that satisfy the partition identity (4.1), one has the well-known form 1 + A(x) = exp P (x) , that was introduced by Pólya in 1937, where

P (x) = m≥1 P(x m )/m, Writing P (x) as n p (n)x n one has p (0) := 0 p (n) := jk=n p(j) k = 1 n d|n dp(d), for n ≥ 1,
We call P (x) the star transformation of P(x). Proposition 4.12 below says that for P(x) ∈ S one has A(x) ∈ RT 1 . The proof of this reduces to showing exp Q (x) ∈ RT 1 for Q(x) ∈ Q. For this we develop properties of an auxiliary function Q(x).

Definition 4.8 Given Q(x) = q(n)x n let Q(x) := x 1 -x • d dx Q (x).
Thus we have

nq (n) = d|n dq(d) for n ≥ 1, (4.5)
and, with Q

(x) = q(n)x n , q(n) = q (1) + • • • + nq (n) for n ≥ 1. (4.6) Lemma 4.9 Suppose Q(x) ∈ Q. Then Q(x) ∈ RT 1 . Proof: We can assume Q(x) = x c R x d with R(x) ∈ RTN 1 , 0 ≤ c < d. q(n)
is a nondecreasing sequence of nonnegative integers that is eventually positive. From (4.5) and (4.6) we have

q(n) = n m=1 mq (m) = n m=1 d|m dq(d) = n m=1 n m mq(m). (4.7)
Fix ε ∈ (0, 1) and choose

M > d ε • (1 -ε) . (4.8)
For any fixed integer v,

c + (j -v)d • q c + (j -v)d (c + jd) • q(c + jd) = c + (j -v)d • r j -v) (c + jd) • r(j) → 1 as j → ∞.
Hence we can choose N > M 3 such that

(c + jd) • q(c + jd) -c + (j -v)d • q c + (j -v)d < ε(c + jd) • q(c + jd)
for 0 ≤ vd ≤ M and c + jd ≥ N/M , and thus

c + (j -v)d • q c + (j -v)d > (1 -ε) • (c + jd) • q(c + jd)
for 0 ≤ vd ≤ M and c + jd ≥ N/M where j ≥ 0. But then

(n -vd)q(n -vd) ≥ (1 -ε) • nq(n) (4.9)
for 0 ≤ vd ≤ M and n ≥ N/M , for if n is not of the form c + jd then the right side of (4.9) is 0. For integers d 1 , d 2 with 1 ≤ d 1 < d 2 ≤ M , and for n ≥ N , we have

n d 1 - n d 2 = n(d 2 -d 1 ) d 1 d 2 ≥ n M 2 > M 3 M 2 = M,
and thus n d 2 < n d 1 -M . Consequently, for n ≥ N , if d 1 < • • • < d k are the divisors of n that are less than M , we have n M < n d k -M < n d k < n d k-1 -M < • • • < n d 1 -M < n d 1 = n, (4.10)
where the first inequality follows from d k < M and n ≥ N > M 3 . Thus the intervals

I d = n d -M, n d for d < M, d n,
are pairwise disjoint subintervals of (n/M, n]. For d < M and d n we have

j∈I d jq(j) ≥ j∈I d q(j) =0 (1 -ε) n d q n d by (4.9) ≥ M d (1 -ε) n d q n d , (4.11)
the last inequality following from the fact that q(j) = 0 implies j ≡ c (mod d).

Returning to the expression for q(n) in (4.7), now assuming that n ≥ N , we have Thus 0 ≤ q(n) -q(n -1) ≤ ε q(n), so Q(x) ∈ RT 1 . 2

q(n) =

P ólya Exponentiation

For m ≥ 1 the Pólya exponentiation operators

E m , E (≥m) map x • N[[x]] into x • N[[x]
], since they convert generating functions into generating functions for multisets of the original objects. In this section we will prove that for m ≥ 1, E m and E (≥m) map S into S; and E (≥m) maps S into RT 1 . First we show that the E m map S into S.

M • E m P(x) is also in S. Since E m (P(x)) ∈ N[[x]], it follows that E m P(x) ∈ S. 2
With the help of the next lemma we will show that the E (≥m) map S into RT 1 .

Lemma 4.11 Given a power series A(x) and m a positive integer let

A m (x) = m-1 j=0 x j • A(x). Then (a) A m (x) ∈ RTN 1 implies a(n) -a(n -m) = o m-1 j=0 a(n -j) ; (b) if A mi (x) ∈ RTN 1 for i = 1, . . . , k and d = gcd m 1 , . . . , m k ) then a(n) -a(n -d) = o u j=0 a(n -j) ,
for a suitable choice of u;

(c) if d = 1 in (b) then A(x) ∈ RTN 1 . Proof: The definition of A m (x) gives a m (n) = m-1 j=0 a(n -j); so one has a(n) -a(n -m) = a m (n) -a m (n -1). Then A m (x) ∈ RTN 1 gives a(n) -a(n -m) = o a m (n) ; so a(n) -a(n -m) = o m-1 j=0 a(n -j) .
This proves (a). We give details of the proof of (b) for the case k = 2, the case we will need in the proof of Proposition 4.12; the general case is proved in a similar manner. From d = gcd(m 1 , m 2 ) we know that for some integers q 1 , q 2 we have d

= q 1 m 1 + q 2 m 2 . Let u i = |q i m i |. We can assume u 1 ≥ u 2 ; so d = u 1 -u 2 . Then for n ≥ u 1 a(n) -a(n -d) = a(n) -a(n -u 1 ) + a(n -u 1 ) -a(n -d) = a(n) -a(n -u 1 ) -a(n -d) -a(n -d -u 2 ) = o u1-1 j=0 a(n -j) + o u2-1 j=1 a(n -d -j) = o u1-1 j=0 a(n -j) .
In this case the choice of u for (b) is u = u 1 -1.

Item (c) is then an immediate application of Lemma 4.5. 2 Proposition 4.12 Suppose P(x) ∈ S. Then E P(x) ∈ RT 1 .

Proof: By Lemma 4.6, P(x) = p 0 (x)

+ Q i (x) with p 0 (x) ∈ x • N[x] and the Q i (x) ∈ Q. Since E p 0 (x) + Q i (x) = E p 0 (x) • E Q i (x) , it suffices to show that E(Q i (x) ∈ RT 1 since E p 0 (x) is either 1 (if p 0 (x) = 0), or it is in RT 1 by Theorem 2.48 of [8]. Let Q(x) := x c R x d with R(x) ∈ RTN 1 .
To show E Q(x) ∈ RT 1 it suffices to consider the case gcd(c, d) = 1. As r(j) 1, it follows that q(c + jd) ≥ 1 for j sufficiently large, say for j ≥ M .

Choose any j ≥ M . Then for n such that (c + jd) n we have

q (n) ≥ c + jd n • q(c + jd) ≥ c + jd n = -x n log 1 -x c+jd . (4.
12)

It follows that there exists a polynomial p j (x) with nonnegative coefficients such that

Q (x) + p j (x) + log 1 -x c+jd (4.13)
has nonnegative coefficients. Then

U j (x) = exp Q (x) + p j (x) (4.14)
has nonnegative coefficients. We will use Lemma 4.4 with

A j (x) := x + • • • + x c+jd • U j (x) B j (x) := (1 -x c+jd ) • U j (x) C j (x) := Q(x) + x(1 -x) -1 p j (x).
By differentiating (4.14) and adjusting polynomial factors one has A j (x) = B j (x) • C j (x). Since B j (x) is the exponential of (4.13), B j (x) has nonnegative coefficients, and clearly C j (x) has nonnegative coefficients. Thus A j (x) also has nonnegative coefficients. The definition of A j (x) says

a j (n) = nu j (n) + • • • + (n -c -jd + 1) • u j (n -c -jd + 1),
and from this follows For n larger than the degree of p j (x), we have

a j (n) -a j (n -1) = nu j (n) -(n -c -jd) • u j (n -c -jd) = n u j (n) -u j (n -c -jd) + (c + jd)u j (n -c -jd). Since B j (x) has nonnegative coefficients, u j (n) -u j (n -c -jd) = b(n) ≥ 0,
c j (n) = [x n ] Q(x) + x(1 -x) -1 • p j (x)
= q(n) + p j (1). (4.15)

From (4.7) and (4.12) we have

q(n) = n m=1
mq (m) → ∞ as n → ∞, so (4.15) leads to c j (n) ∼ q(n). (4.16) By Lemma 4.9 and Proposition 4.1, C j (x) ∈ RT 1 . This is condition (c) of Lemma 4.4. Now Lemma 4.4 gives A j (x) ∈ RT 1 , that is,

1 + x + • • • + x c+jd-1 • xU j (x) ∈ RT 1 .
Likewise, as j + 1 ≥ M ,

1 + x + • • • + x c+(j+1)d-1 • xU j+1 (x) ∈ RT 1 .
Without loss of generality we can assume that p j (x) = p j+1 (x); let us call this common polynomial p(x). Then U j (x) = U j+1 (x); let us call this power series simply U(x). It suffices to consider the case that gcd n : p(n) > 0 = 1, in which case A(x) has integer coefficients that are eventually positive. By Proposition 4.12, A(x) ∈ RT 1 ; and A(1) = ∞ since A(x) has eventually positive integer coefficients. Let m be a fixed positive integer. By Lemma 3.55, p. 69 of [START_REF] Stanley | Number Theoretic Density and Logical Limit Laws[END_REF], a m (n) = o a(n) . Since

A (≥m) (x) = A(x) - m-1 j=0 A j (x),
it follows that a (≥m) (n) ∼ a(n),

showing that A (≥m) (x) ∈ RT 1 . 2

The following proposition collects the main results concerning S. (c) For m ≥ 0 and P(x) ∈ S, one has E (≥m) P(x) ∈ RT 1 .

The Main Result

Theorem 5.1 Let F be an adequate MSO-class of forests, say F = (≥ 1)(T ). Then F has a MSO 0-1 law iff the radius of F is 1 iff the radius of T is ≥ 1.

Proof: Since the radius of the class of all trees is positive, we know that the radius of F must be positive. Then, from Corollary 1.2, F has a MSO 0-1 law iff F(x) ∈ RT 1 . F(x) ∈ RT 1 implies ρ F = 1, and this implies ρ T ≥ 1. By Corollary 3.5, ρ T ≥ 1 implies T(x) ∈ G, and then Proposition 4.14 shows that F(x) = E T(x) ⊆ RT 1 . Thus F ∈ RT 1 iff ρ F = 1 iff ρ T ≥ 1.

2

Remark 5.2 The main theorem, using essentially the same proof, holds in the more general setting of forests with finitely many unary predicates.

In the study of spectra, one finds that the periodicity results for MSO classes of trees lift to the setting of MSO classes of unary functions (viewed as functional digraphs). (vii) This leads to the natural query:

Problem. Does every adequate MSO-class U of unary functions (with finitely many unary predicates) of radius 1 have a MSO 0-1 law? (vii) For a simple proof of this result, based on Compton equations, see [START_REF] Yeats | Spectra and systems of equations[END_REF].

  so from (a) there is an integer n ≥ 1 such that N • M = (M jj ) n . By unique factorization there are unique modules M and N and integers a, b ≥ 0 such that N = (M jj ) a • N , M = M • (M jj ) b , and N • M = M jj . Holding N fixed, we see from the last equation that M must be the same for all M ∈ M ij . Thus M ij = M • M jj . Using unique factorization once again, we see that only one member of M ij can fulfill the role of M .

3 . 2 3. 8 ≥ 1 . 3 . 5 (

 328135 Definition of G Define G to be the closure of the class {x} ∪ x 1 -x m : m ≥ 1 under the operations +, ×, E m , E (≥m) for m Corollary a) Every MSO-class T of trees of radius ≥ 1 has its generating function in G. (b) Every function A(x) ∈ G has radius of convergence ≥ 1.

Lemma 4. 1 (

 1 a) RT 1 is closed under addition, multiplication by positive reals, Cauchy product, and asymptotic equality. Furthermore, S(x)∈ RT 1 iff S (x) ∈ RT 1 iff xS(x) ∈ RT 1 . (b) For d ∈ N {0}, RT 1 [d]is closed under addition, multiplication by positive reals, and Cauchy product.

2 Lemma 4 . 2 (

 242 (b) follows from (a), and (c) is Lemma 16.2 of [7]. Schur's Tauberian Theorem) Suppose that B(x) and C(x) are power series such that (a) B(x) has radius of convergence greater than 1, (b) B(1) > 0, and

  ) -q(n -1) by (4.5).

Proposition 4 .

 4 10 Suppose P(x) ∈ S. Then E m P(x) ∈ S for m ≥ 1.Proof: By the definition of E m in §3.3, there is a polynomial S(y 1 , . . . , y m ) ∈ Q[y 1 , . . . , y m ] with nonnegative coefficients such that E m (P(x)) = S P(x), . . . , P(x m ) .Let M be a positive integer such that M • S(y 1 , . . . , y m ) ∈ N[y 1 , . . . , y m ]. Since the P(x i ) are in S, and since S is closed under scalar multiplication by positive integers, addition and multiplication, it follows that

  and thusa j (n) -a j (n -1) ≥ 0.This shows condition (a) of Lemma 4.4 holds.Since B j (x) and U j (x) have nonnegative coefficients,0 ≤ b j (n) ≤ u j (n) ≤ a j (n)/n,and thus b j (n) = o a j (n) . This gives condition (b) of Lemma 4.4.

2 Proposition 4 . 13

 2413 Since gcd c+jd, c+(j +1)d = 1, by Lemma 4.11 (c) we have xU (x) ∈ RT 1 . But then U(x) ∈ RT 1 by Proposition 4.1. From Corollary 4.3,exp -p(x) • U(x) ∈ RT 1 , that is, E Q(x) = exp Q (x) ∈ RT 1 , proving the proposition. Suppose P(x) ∈ S. Then E (≥m) P(x) ∈ RT 1 for m ≥ 0. Proof: Define A m (x) := E m P(x)A (≥m) (x) := E (≥m) P(x)A(x) := E P(x) .

1 -

 1 x n ∈ S, for n ≥ 1.(b) S is closed under addition, Cauchy product, E m and E (≥m) , for m ≥ 1.

  and it is eventually positive on the set d • N of multiples of d. We say that a subclass B of A has an asymptotic density in A if b(nd)/a(nd) converges as n → ∞ (in which case the asymptotic density of B is the limiting value of the quotient).

If the period of A is 1, that is, a(n) is eventually positive, then Compton's test is simply

Research supported by NSERC. Research supported by NSERC. Research supported by NSERC. see, for example, any of [8],