\documentstyle[12pt]{article} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand{\FF}{{\mbox{\sf F}}} \newcommand{\FH}{{\mbox{\sf H}}} \newcommand{\FK}{{\mbox{\sf K}}} \newcommand{\FR}{{\mbox{\sf R}}} \newcommand{\FV}{{\mbox{\sf V}}} \newcommand{\fspecK}{\sigma_{\,\FK}} \newcommand{\fspecF}{\sigma_{\,\FF}} \newcommand{\Prob}{{\rm Prob}} %%%%%%%%%%%%%%%%%% Environments %%%%%%%%%%%%% \newtheorem{daf}{\sc Definition}[section] \newenvironment{df}{\begin{daf}\hspace{-1.2ex}. \it}{\end{daf}} \newtheorem{thr}[daf]{\sc Theorem} \newenvironment{th}{\begin{thr} \hspace{-1.2ex}. \it}{\end{thr}} \newtheorem{lam}[daf]{\sc Lemma} \newenvironment{lm}{\begin{lam}\hspace{-1.2ex}. \it}{\end{lam}} \newtheorem{cllr}[daf]{\sc Corollary} \newenvironment{cor}{\begin{cllr}\hspace{-1.2ex}. \it}{\end{cllr}} \newtheorem{prb}{\sc Problem}%%%% \newenvironment{prob}{\begin{prb}\hspace{-1.2ex}. \it}{\end{prb}} \newtheorem{rme}[daf]{\sc Remark} \newenvironment{rem}{\begin{rme}\hspace{-1.2ex}. \it}{\end{rme}} \newtheorem{prp}[daf]{\sc Proposition} \newenvironment{prop}{\begin{prp} \hspace{-1.2ex}. \it}{\end{prp}} \newtheorem{exmp}[daf]{\sc Example} \newenvironment{examp}{\begin{exmp}\hspace{-1.2ex}. \rm}{\end{exmp}} \newcounter{thlistctr} \newenvironment{thlist}{\ \begin{list}% {\alph{thlistctr}}% {\setlength{\labelwidth}{2ex}% \setlength{\labelsep}{1ex}% \setlength{\leftmargin}{6ex}% \renewcommand{\makelabel}[1]{\makebox[\labelwidth][r]{\rm (##1)}}% \usecounter{thlistctr}}}% {\end{list}} %%%%%%%%%%%%%% Abbreviations %%%%%%%%%%%%%%%%% \newcommand {\schluss}{\rule{2mm}{2mm}} \newcommand {\miff}{\makebox[1in]{iff}} \newcommand {\gap}{\hspace*{.4in}} \newcommand {\leftbr}{[\hspace{-.4ex}[} \newcommand {\rightbr}{]\hspace{-.4ex}]} \newcommand {\bA}{{\bf A}} \newcommand {\bB}{{\bf B}} \newcommand {\bC}{{\bf C}} \newcommand {\bD}{{\bf D}} \newcommand {\bG}{{\bf G}} \newcommand {\bM}{{\bf M}} \newcommand {\bP}{{\bf P}} \newcommand {\bQ}{{\bf Q}} \newcommand {\bS}{{\bf S}} \newcommand {\bT}{{\bf T}} \newcommand {\bZ}{{\bf Z}} \newcommand {\cA}{{\cal A}} \newcommand {\cC}{{\cal C}} \newcommand {\cG}{{\cal G}} \newcommand {\cL}{{\cal L}} \newcommand {\cN}{{\cal N}} \newcommand {\cP}{{\cal P}} \newcommand {\cR}{{\cal R}} \newcommand {\rC}{{\rm C}} \newcommand {\rH}{{\rm H}} \newcommand {\rN}{{\rm N}} \newcommand {\rS}{{\rm S}} \newcommand{\prf}{{\sc Proof.\ }} %%%%%%%%%%%%% Page Layout %%%%%%%%%%%%%%%%%%%%%%%%% \hoffset=-.5in \voffset=-.75in \setlength{\textwidth}{6in} \setlength{\textheight}{8.2in} \renewcommand{\baselinestretch}{1.1} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{\Large \bf Fine Spectra and Limit Laws II.\\First-Order 0--1 Laws} \author{Kevin Compton, Andrew Odlyzko, and Bruce Richmond} \date{\today\\\bigskip\fbox{\sc Preliminary Version}} \begin{document} \large \pagestyle{myheadings} \maketitle %%%%%%% Abstract %%%%%%%%%%% \begin{minipage}[c]{27pc} \hrule \medskip \footnotesize Using Feferman-Vaught techniques a condition on the fine spectrum of an admissible class of structures is found which leads to a first-order 0--1 law. The condition presented is best possible in the sense that if it is violated then one can find an admissible class with the same fine spectrum which does not have a first-order 0--1 law. If the condition is satisfied (and hence we have a first-order 0--1 law) we give a natural model of the limit law theory; and show that that the limit law theory is decidable if the theory of the directly indecomposables is decidable. Using asymptotic methods from the partition calculus a useful test is derived to show several admissible classes have a first-order 0--1 law. \medskip \hrule \end{minipage} %%%%%%%%% End of Abstract %%%%%%%%%%% \vspace{.4in} \section{Front-loaded classes} We will continue using the notation of Part I, the first paper \cite{part1} of this sequel. First we study, in an abstract setting, the key property of fine spectra which suffices to prove 0--1 laws exist. In this section a subscripted lower case letter is used for members of a sequence, e.g. $(a_n)$, and the corresponding upper case letter for the partial sum function, e.g. $A(x) = \sum_{n\leq x}a_n$. \begin{lm} \label{tfae} For $(a_n)$ a sequence of non-negative integers the following are equivalent: \begin{thlist} \item $\displaystyle \lim_{t\rightarrow \infty}\ \frac{A(t x)}{A(t)} = 1 \mbox{ for all [some] } x > 1. $ \item $\displaystyle \lim_{n\rightarrow \infty}\ \frac{A(n x)}{A(n)} = 1 \mbox{ for all [some] } x > 1. $ \item $\displaystyle \lim_{n\rightarrow \infty}\ \frac{A(x ^{n+1})}{A(x ^n)} = 1 \mbox{ for all [some] } x > 1. $ \end{thlist} We also obtain further equivalent statements by replacing $tx$ by $t/x$ in {\rm (a)}, and $nx$ by $n/x$ in {\rm (b)}. \end{lm} \noindent \prf Regarding the `{\em for all $x$}' versions one has (a) $\Longrightarrow$ (b), (c). Likewise for the `{\em for some $x$}' versions. Also, in each case the `{\em for all $x$}' version implies the `{\em for some $x$}' version. Thus for the equivalences (a)--(c) it suffices to show that the `{\em for some $x$}' versions of (b), (c) each imply the `{\em for all $x$}' version of (a). First suppose the `{\em for some}' version of (b) holds. Choose $u>1$ such that \[ \lim_{n\rightarrow \infty}\ \frac{A(nu)}{A(n)} = 1. \] For $n$ sufficiently large we have $u n>n+1$, and consequently \[ 1\leq \frac{A(n+1)}{A(n)} \leq \frac{A(nu)}{A(n)}. \] Thus \[ \lim_{n\rightarrow \infty}\ \frac{A(n+1)}{A(n)} = 1. \] Then \[ 1\leq \frac{A(tu)}{A(t)} \leq \frac{A((\lfloor t\rfloor +1)u)}{A(\lfloor t \rfloor)} = \frac{A((\lfloor t\rfloor +1)u)}{A(\lfloor t \rfloor + 1)}\cdot \frac{A(\lfloor t\rfloor +1)}{A(\lfloor t \rfloor)}. \] So \[ \lim_{t\rightarrow \infty}\ \frac{A(t u)}{A(t)} = 1. \] Then for any positive integer $s$ we have \[ \lim_{t\rightarrow \infty}\ \frac{A(tu^s)}{A(t)} = 1. \] Given any $x > 1$ choose a positive integer $s$ such that $11$ such that \[ \lim_{n\rightarrow \infty}\ \frac{A(u^{n+1})}{A(u^n)} = 1. \] Then, for $u^n\leq t \leq u^{n+1}$, we have $u^{n+1}\leq tu \leq u^{n+2}$, and then \[ \frac{A(u^{n+2})}{A(u^n)} \geq \frac{A(tu)}{A(t)} \geq 1, \] so \[ \lim_{t\rightarrow \infty}\ \frac{A(tu)}{A(t)} = 1. \] Now, as in the previous case, we have, for any $x > 1$, \[ \lim_{t\rightarrow \infty}\ \frac{A(tx)}{A(t)} = 1. \] To see that one can replace $nx$ by $n/x$ in (b) it suffices to note the following: \[ \frac{A(2\lfloor nx \rfloor)}{A(\frac{1}{2x}(2\lfloor nx\rfloor))} \geq \frac{A(nx)}{A(n)} \geq 1, \] and for $n>x$ \[ \frac{A(\lfloor n/x \rfloor)}{A(2x\lfloor n/x \rfloor)} \leq \frac{A(n/x)}{A(n)} \leq 1. \] The same argument shows that one can replace $tx$ by $t/x$ in (a). \gap\schluss\\ \begin{df} A sequence of non-negative integers $(a_n)$ is said to be \underline{\em front-loaded} if $A(x)$ is slowly varying, i.e., for all $x > 0$, \[ \lim_{t\rightarrow\infty} \frac{A(t x)}{A(t)} = 1. \] A class $\FK$ of finite structures is \underline{\em front-loaded} if its fine spectrum is front-loaded. \end{df} \begin{th}\label{oz:th} The Dirichlet convolution product of finitely many front-loaded sequences is front-loaded. \end{th} \prf It suffices to consider two front-loaded sequences, say $(a_n)$ and $(b_n)$. We want to show that the sequence $(c_n)$ defined by $c_n = \sum_{m|n} a_mb_{n/m}$ is front-loaded. Now \[ C(x) = \sum_{k\leq x} a_k \cdot B(x/k). \] We have to prove, for $x > 1$ and $\delta > 0$, that there is a $t_0(x,\delta)$ such that \[ C(t x) \leq (1+\delta) \cdot C(t) \mbox{ for } t > t_0(x,\delta). \] Since the $b$-sequence is front-loaded, \[ B(t x) \leq (1+\delta/2) \cdot B(t) \mbox{ for } t > t_1(x,\delta), \] and we assume $t_1 > x$. Then \begin{eqnarray*} C(t x)&=&\sum_{k\leq t x} a_k \cdot B(t x/k)\\ &\leq& (\sum_{k\leq t x/t_1} a_k \cdot B(t x/k)) + B(t_1) \cdot ( A(t x) - A(t x/t_1) )\\ &\leq& (1+\delta/2) \cdot (\sum_{k\leq t}( a_k \cdot B(t/k) ) + B(t_1) \cdot ( A(t x) - A(t x/t_1) )\\ &=& (1+\delta/2) \cdot C(t) + o( A(t) ) \end{eqnarray*} since the $a$-sequence is front-loaded, which completes the proof.\gap\schluss\\ The next item is essentially Lemma ZZZ of Part I. \begin{lm} \label{fl:eq} Let $\FK$ be an admissible class. Then the following are equivalent: \begin{thlist} \item $\FK$ is front-loaded. \item ${\rm Prob}_{\,\FK}(\mbox{\,\sf is divisible by $\bA$\,}) = 1$ for all $\bA \in \FK$. \item ${\rm Prob}_{\,\FK}(\mbox{\,\sf is divisible by $\bA$\,}) = 1$ for some nontrivial $\bA \in \FK$. \end{thlist} \end{lm} \prf Observe that \begin{eqnarray*} {\rm Prob}_{\,\FK}(\mbox{\,\sf is divisible by $\bA$\,}) &=& \lim_{n\rightarrow \infty}\,\frac{\tau_{\,\FK}(n \,|\, \mbox{\,\sf is divisible by $\bA$\,})}{\tau_{\,\FK}(n)}\\ &=& \lim_{n\rightarrow \infty}\,\frac{\tau_{\,\FK}(n/d)}{\tau_{\,\FK}(n)}, \end{eqnarray*} where $d$ is the size of $\bA$. Then apply Lemma \ref{tfae}. \gap\schluss\\ \begin{lm} An admissible front-loaded class $\FK$ is loaded. \end{lm} \prf Let $\FF_1,\ldots,\FF_k$ be a partition of $\FF$, and let $r_1,\ldots,r_k$ be a sequence of nonnegative integers. Choose any algebra $\bA$ with at least $r_i$ factors from each $\FF_i$. Then \[ \frac{\tau_{\,\FK}(\,n\,|\,\mbox{\sf is divisible by } \bA\,)}{\tau_{\,\FK}(n)} \leq \frac{\tau_{\,\FK}(\,n\,|\,\mbox{\sf is in } \FF_1^{\,\geq r_1}\cdots \FF_k^{\,\geq r_k})}{\tau_{\,\FK}(n)} \leq 1. \] Thus, by Lemma \ref{fl:eq}, $ \Prob_{\,\FK} (\,\mbox{\sf is in } \FF_1^{\,\geq r_1}\cdots \FF_k^{\,\geq r_k}) = 1, $ so $\FK$ is loaded. \gap\schluss %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Logical Aspects} \begin{th} \label{sb:th2} Suppose that $\FK$ is admissible. If $\FK$ is front-loaded then we have the following: \begin{thlist} \item $\FK$ has a first-order 0--1 law. \item Let $\FR$ be a selection of representatives from the isomorphism equivalence classes of $\FF$, and let $\bT = (\Pi \FR)^\omega$. Then, for $\phi$ a first-order sentence, ${\rm Prob}_{\,\FK}(\phi) = 1$ iff $\bT \models \phi$. \item If the first-order theory of $\FF$ is decidable then so is the limit law theory of $\FK$, i.e, the set of first-order $\phi$ with ${\rm Prob}_{\,\FK}(\phi) = 1$. \end{thlist} If, on the other hand, $\FK$ is not front-loaded, then there is an admissible $\FK'$ with the same fine spectrum as $\FK$, and $\FK'$ does not have a first-order 0--1 law. \end{th} \prf %%%%%%%%%%%%%% \begin{thlist} \item Examining the proof of part (a) of Theorem XXX in Part I we see in the front-loaded case that $p_{j_0,\ldots,j_{\ell-1}} = 0$ if any $j_i < c$. Thus at most one nonzero term survives in the formula for the cumulative probability of $\phi$, namely $p_{c,\ldots,c}$, and this term has the value 1. \item Given a first-order sentence $\phi$ let Feferman-Vaught sequences be determined as in the proof of part (a) of Prop YYY in Part I, and also the $\FF_i$. By regrouping the factors of $\bT$ by `members of the same $\FF_i$', we have \[ \bT \cong \bT_0\times \cdots\times \bT_{\ell-1}, \] where $\bT_i = (\Pi (\FR\cap\FF_i))^\omega$. $\bT$ will satisfy $\phi$ iff the structures from $\FK$ with at least $c$ factors from each $\FF_i$ satisfy $\phi$ (by Lemma ZZZ in Part I), and the latter holds iff $\phi$ is in the limit law theory. \item Suppose Th(\FF), the first order theory of $\FF$, is decidable. Given a first-order sentence $\phi$ we now show how to effectively determine if $\bT \models \phi$, i.e., how to determine if $\phi$ is in the limit law theory. First we use \cite{f:v} to effectively find the Feferman-Vaught sequences $\langle \Phi,\phi_1,\cdots,\phi_k \rangle$, $\langle \Phi_i,\phi_{i,1},\cdots,\phi_{i,k_i} \rangle$ ($1\leq i\leq k$) in the proof of part (a). Now we define a {\em constituent} of $\phi$ to be any conjunction $\gamma$ of the $\phi_{i,j}$'s and their negations such that for each $(i,j)$ precisely one of $\phi_{i,j}$ and $\neg\,\phi_{i,j}$ appears in the conjunction. Suppose $\gamma$ is such a constituent. Then either $\gamma$ has no model in $\FF$ or $\gamma$ defines one of the classes $\FF_i$, i.e., $\FF_i = \{\bD\in \FF : \bD \models \gamma\}$. Note that, up to ordering of the conjuncts, each $\FF_i$ is determined by a unique constituent, say by $\gamma_i$. Thus we can determine the $\ell$ in the proof of part (a) by determining the constitituents which have models in $\FF$. And we can do this by using the decidability of Th(\FF), namely a constituent $\gamma$ has a model in $\FF$ iff $\neg\, \gamma \notin {\rm Th}(\FF)$. Now that we have $\ell$, we want to determine the $\leftbr \phi_i\rightbr$ in ${\bf 2}^\ell$. This is because $\bT \models \phi$ iff ${\bf 2}^\ell\models\Phi(\leftbr\phi_1\rightbr,\ldots,\leftbr\phi_k\rightbr)$. To determine $\leftbr \phi_i\rightbr$ we will find the set $S_i$ of $j$ such that $\bT_j \models \phi_i$. $\leftbr \phi_i\rightbr$ is just the characteristic function of $S_i$ (in the set $\ell = \{0,\ldots,\ell-1\}$). So we look at the Feferman-Vaught sequence for $\phi_i$, namely\\ $\langle \Phi_i,\phi_{i,1},\cdots,\phi_{i,k_i} \rangle$. As $\bT_j$ is a countably infinite product of members of $\FF_i$, say $\bT_j = \Pi_{n<\omega}\bD_n$, we have \[ \Pi_{n<\omega}\bD_n \models \phi_i \miff {\bf 2}^\omega\models\Phi(\leftbr\phi_{i,1}\rightbr,\ldots,\leftbr\phi_{i,k_i}\rightbr). \] As the $\bD_n \models \gamma_j$, and each $\phi_{i,r}$ or its negation appears as a conjunct of $\gamma_j$, we know that \begin{eqnarray*} \leftbr \phi_{i,r}\rightbr&=& 1\gap\mbox{if $\phi_{i,r}$ appears in $\gamma_j$}\\ \leftbr \phi_{i,r}\rightbr&=& 0\gap\mbox{if $\neg\,\phi_{i,r}$ appears in $\gamma_j$}. \end{eqnarray*} Thus we can effectively find the $\leftbr \phi_{i,r}\rightbr$'s. Having determined $\Phi_i(\leftbr\phi_{i,1}\rightbr,\ldots,\leftbr\phi_{i,k_i}\rightbr)$, a sentence in the language of Boolean algebras, we use Skolem's result that Th(${\bf 2}^\omega$) is decidable to determine if $\Phi_i(\leftbr\phi_{i,1}\rightbr,\ldots,\leftbr\phi_{i,k_i}\rightbr)\in {\rm Th}({\bf 2}^\omega)$, and thus if $\bT_j\models \phi_i$. Now we have all the information needed to determine the $S_i$'s, and hence the $\leftbr \phi_i \rightbr$'s, so we can effectively find $\Phi(\leftbr\phi_1\rightbr,\ldots,\leftbr\phi_k\rightbr)$. Finally we determine if ${\bf 2}^\ell\models\Phi(\leftbr\phi_1\rightbr,\ldots,\leftbr\phi_k\rightbr)$; this is clearly decidable as ${\bf 2}^\ell$ is a finite algebra. This finishes the proof of (c). \end{thlist} Now let us suppose that $\FK$ is not front-loaded. Let $\FF$ be the class of $\FK$-indecomposables. Let $\FF'$ be an expansion of $\FF^{\, t}$ by two constants $a,\,b$, i.e., for each member $\bD$ of $\FF^{\, t}$ we create one structure $\bD'$ by interpreting the constant symbols $a,\,b$.\\ \noindent \underline{Case 1:} ${\rm Prob}_{\,\FK'}(\,\phi_{\rm ind}\,)$ does not exist. \smallskip In this case $\FK'$ does not have a first-order law.\\ \noindent \underline{Case 2:} ${\rm Prob}_{\,\FK'}(\,\phi_{\rm ind}\,)= t >0$. \smallskip In this case we have an infinite number of indecomposables. Choose positive integers $n_1\frac{2}{3}t \] and \[ \frac{\tau_{\,\FK'}(n_{2k+1}\,|\,a= b\wedge \phi_{\rm ind})}{ \tau_{\,\FK'}(n_{2k+1})} <\frac{1}{3}t. \] Thus $ {\rm Prob}_{\,\FK'}(\,a= b\wedge \phi_{\rm ind}\,) $ does not exist, so $\FK'$ does not have a first-order law.\\ \noindent \underline{Case 3:} ${\rm Prob}_{\,\FK'}(\,\phi_{\rm ind}\,)= 0$. \smallskip Without loss of generality regarding the fine spectrum being considered we can assume that \begin{description} \item [($\star$)] for every relation symbol $r$ of the language there is a corresponding function symbol $f_r$ such that for each nontrivial $\bA\in \FK'$ we have $r(a_1,\ldots,a_n)$ holds iff $f_r(a_1,\ldots,a_n) = a_1$ holds, where $a_i \in A$. \end{description} Given a member $\bA$ of $\FK'$ one can use the ternary discriminator to find a first-order sentence $\phi_\bA$ which, for members of $\FK'$, says ``$\bA$ is a factor''. If for some $\bA\in\FK'$ the cumulative probability $ {\rm Prob}_{\,\FK'}(\,\phi_\bA\,) $ is not defined then $\FK'$ does not have a first-order law, and we are finished. So we assume that $ {\rm Prob}_{\,\FK'}(\,\phi_\bA\,) $ exists for all $\bA \in \FK'$.\\ \noindent \underline{Case 3a:} ${\rm Prob}_{\,\FK'}(\,\phi_{\bA}\,)= 0$ for every nontrivial $\bA\in \FK'$. \smallskip The number of structures, up to isomorphism, in $\FF'$ must be infinite; for otherwise we could use Theorem \ref{oz:th} to show $\FK$ is front-loaded. For $k$ a positive integer let $\phi_{From our assumptions follows ${\rm Prob}_{\,\FK}(\phi_{\frac{2}{3} \] and \[ \frac{\tau_{\,\FK'}(n_{2k+1}\,|\,\phi_{a,b})}{ \tau_{\,\FK'}(n_{2k+1})} <\frac{1}{3}. \] Thus $ {\rm Prob}_{\,\FK'}(\phi_{a,b}) $ does not exist, and again $\FK'$ does not have a first-order law.\\ \noindent \underline{Case 3b:} ${\rm Prob}_{\,\FK'}(\,\phi_{\bA}\,)> 0$ for some nontrivial $\bA\in \FK'$. \smallskip Now ${\rm Prob}_{\,\FK'}(\,\phi_{\bA}\,)< 1$ for every nontrivial $\bA\in\FK'$ by Lemma \ref{fl:eq} as $\FK'$ is not front-loaded. But then $\FK'$ does not have a 0--1 law. \gap\schluss\\ Thus we see that, among the admissible classes $\FK$, those for which knowledge of the fine spectrum alone is sufficient to conclude a first-order 0--1 law are precisely those which are front-loaded. An example of an admissible $\FK$ where more information is needed is the class of finite sets. We already mentioned that it is loaded, and thus has a first-order law; however it is well-known that it has a first-order 0--1 law. This $\FK$ is clearly not front-loaded, so more information than that given by the fine spectrum is required to deduce the 0--1 law. %%%%%%%%% \begin{prop}\label{prod:prop} Suppose $\FK_i$ is admissible and front-loaded, for $1\leq i\leq m$. Let $\FF_i$ be the $\FK_i$-indecomposables. Suppose the $\FF_i$ are pairwise disjoint. Let $\FK = \FK_1\cdots\FK_m$. If $\FK$ has unique factorization then $\FK$ has a first-order 0--1 law. \end{prop} \prf The hypotheses ensure that $\FK$ is admissible, and that the Dirichlet convolution product of the fine spectra $\sigma_{\,\FK_1},\ldots, \sigma_{\,\FK_m}$ is the fine spectrum $\fspecK$. Now apply Theorems \ref{oz:th} and \ref{sb:th2}. \gap \schluss %%%%%%%%% \begin{rem}\label{prod:rem} We can apply the above to show \[ \FK^\star = \bigcup_{S\subseteq \{1,\ldots,m\}}\prod_{i\in S}\FK_i \] has a 0--1 law if it has unique factorization by observing that \begin{itemize} \item adding/deleting one-element structures that act as multiplicative units with respect to direct products from a class $\FK$ does not affect either the admissibility of $\FK$ or the fact that $\FK$ is front-loaded. \end{itemize} \end{rem} \begin{cor}\label{prod:cor} Suppose $\FK$ is admissible, and that the set $\FF$ of $\FK$-indecomposables is the disjoint union of $\FF_1,\ldots,\FF_m$, where each $\FF_i$ is closed under isomorphism. Let $\FK_i = IP_{fin}(\FF_i)$. If each $\FK_i$ is front-loaded then $\FK$ has a first-order 0--1 law. \end{cor} \prf Each $\FK_i$ is admissible, and $\FK = \FK^\star$ where $\FK^\star$ is as in Remark \ref{prod:rem}. Thus by Proposition \ref{prod:prop} and Remark \ref{prod:rem} we arrive at the desired conclusion. \gap\schluss \section{Asymptotics} Let $\FK$ be admissible, and let $\FF$ be the class of $\FK$-indecomposables. To estimate $\tau(n\,|\,P)$ and $\tau(n)$ we shall consider Dirichlet generating functions. Chapter XVII of \cite{h:w} contains an excellent introduction for our purposes to Dirichlet generating functions. Perhaps noting that $\FK$ and $\FF$ correspond to the integers and primes respectively and that \[ \sum_{n=1}^{\infty}n^{-s} = \prod_p(1-p^{-s})^{-1},\ p \mbox{ a prime}, \] will motivate what follows. If $m$ runs through the integers which are not divisible by the prime $q$ then \[ \sum_{m=1}^{\infty}m^{-s} = \prod_{p\neq q}(1-p^{-s})^{-1},\ p \mbox{ a prime}. \] Now suppose we are given a fixed positive integer $M$. Let $b_n = \sigma_{\FK}(n)$. Let $\bD_1,\bD_2,\ldots$ be a listing, up to isomorphism, of the members of $\FF$, and let $\beta_n$ be the size of $\bD_n$. Let $a_n$ denote the number of structures of size $n$ in $\FK$ which have no copies of $\bD_M$ in their $\FF$-factorization. Then it is not difficult to see that \[ \sum b_nn^{-s} = \prod_{m=1}^{\infty}(1-\beta_m^{-s})^{-1}, \] and \[ \sum a_nn^{-s} = \prod_{\begin{tabular}{c}$m=1$\\$m\neq M$\end{tabular}}^{\infty}(1-\beta_m^{-s})^{-1}. \] Furthermore \[ {\rm Prob}_{\,\FK}(\,\mbox{\sf is not divisible by}\ \bD_M\,) = \lim_{n\rightarrow \infty}\ \frac{a_1+a_2+\cdots+a_n}{b_1+b_2+\cdots+b_n}, \] provided this limit exists. \begin{th}\label{br:th} Let $(\beta_m)$, $0<\beta_1<\beta_2<\cdots$, be a sequence of real numbers and \[ \sum b_nn^{-s} = \prod_{m=1}^{\infty}(1-\beta_m^{-s})^{-1} \] \[ \sum a_nn^{-s} =\beta_M^{-s} \prod_{\begin{tabular}{c}$m=1$\\$m\neq M$\end{tabular}}^{\infty}(1-\beta_m^{-s})^{-1}. \] where $M$ is a positive integer. If \[ \log \beta_m\sim cm,\gap c>0\ \mbox{ a constant}, \] then \[ \frac{a_1+a_2+\cdots+a_n}{b_1+b_2+\cdots+b_n} = O((\log n)^{-\frac{1}{2}}). \] \end{th} \prf We will use Theorem 2.2 of \cite{ri} to derive our result. We begin with some notation and definitions used in \cite{ri}. Let $\Lambda = (\lambda_m)$, $0<\lambda_1<\lambda_2<\cdots$, be an infinite sequence of real numbers without a finite limit point. Let $N(u)$ be defined by \[ N(u) =\sum_{\lambda_m\leq u} 1 \] and suppose that for each $\epsilon > 0$ there exists a constant $C = C(\epsilon)$ such that \[ N(u) \leq C(\epsilon)\exp(\epsilon u). \] Then the infinite product \[ g(s) = \prod_{m=1}^\infty (1-\exp(-\lambda_m s))^{-1} \] converges for all complex $s$ with Re $s>0$. Let $\ell_m$ run through the monotone increasing sequence of linear combinations of the $\lambda_m$ with non-negative integral coefficients; then \[ g(s) = \sum_m p(\ell_m)e^{-\ell_ms}, \] where $p(\ell_m)$ is the number of partitions of $\ell_m$ into summands from $\{\lambda_m\}$. Let \[ P(u) = \sum_{\ell0 \rightarrow c(x) = 1$. Thus the sizes of the finite directly indecomposables of $\FV$ form the sequence $(2^n)$. By Theorem \ref{summary}, $\FK$ has a first-order 0--1 law. From Skolem's work we know that the theory of finite Boolean algebras is decidable; and using this one can give a straightforward proof that the theory of the finite directly indecomposables of $\FV$ is decidable. Thus, by Theorem \ref{sb:th2}(c), the limit law theory of $\FK$ is decidable. \end{examp} \begin{examp} Let $\FV$ be the variety of Heyting algebras generated by the three element chain. Again we have a congruence distributive variety, and thus unique factorization. Let $\FK$ be the finite members of $\FV$. The directly indecomposables of $\FV$ are precisely Boolean algebras with a new 0 adjoined. Thus the sizes of the finite directly indecomposables of $\FV$ form the sequence $(2^n+1)$. By Theorem \ref{summary}, $\FK$ has a first-order 0--1 law. Again Skolem's work leads to a straightforward proof that the theory of the finite directly indecomposables of $\FV$ is decidable. By Theorem \ref{sb:th2}(c) the limit law theory of $\FK$ is decidable. \end{examp} \begin{examp} Let $p_1,\ldots,p_\ell$ be a set of prime numbers. Let $\FK$ be the set of finite abelian groups whose exponent divides some power of $p_1\cdots p_\ell$. Then the directly indecomposables fall into $\ell$ classes with the growth of the $i^{\rm th}$ class being the exponential sequence $(p_i^n)$. Consequently $\FK$ has a first-order 0--1 law by Theorem \ref{summary}. By Theorem \ref{sb:th2}(b) one has ${\rm Prob}_{\,\FK}(\phi) = 1$ iff $\phi$ is true of the abelian group \[ \bG = \prod_{i=1}^\ell\prod_{n=1}^\infty (\bZ_{p_i^n})^\omega. \] Referring to the work of Szmielew \cite{sz} we see that (i) the exponent of $\bG$ is $\infty$, (ii) all elementary invariants of $\bG$ which involve $p_1,\ldots,p_\ell$ are $\infty$, and (iii) all elementary invariants of $\bG$ which involve other primes are 0. Thus the set of basic sentences which are true of $\bG$ is recursive, and consequently the first-order theory of $\bG$ is decidable. Consequently the limit law theory of $\FK$ is decidable. \end{examp} \begin{thebibliography}{99} \bibitem{part1} {\em Fine spectra and limit laws I. First-Order Laws.} \bibitem{f:v} S. Feferman and R.L. Vaught, {\em The first-order properties of algebraic systems.} Fund. Math. {\bf 47} (1959), 57--103. \bibitem{h:w} G.H. Hardy and E.M. Wright, {\em An Introduction to the Theory of Numbers}, Oxford Press, $4^{\rm th}$ ed. \bibitem{ri} L.B. Richmond, {\em Asymptotic results for partitions (I) and the distribution of certain integers}, J. Number Th. {\bf 8} (1976), 372--289. \bibitem{r:s} K.F. Roth and G. Szekeres, {\em Some asymptotic formulas in the theory of partitions}, Quart. J. Math. Oxford Ser. 2 {\bf 5} (1954), 244--259. \bibitem{sz} W. Szmielew, {\em Elementary properties of Abelian groups}, Fund. Math. {\bf 41} (1955), 203--271. \end{thebibliography} \small \sf \begin{tabular}{l c r} \begin{tabular}[t]{l} Department of EECS\\ University of Michigan\\ Ann Arbor, MI 48109-2122\\ U.S.A. \end{tabular}& \begin{tabular}[t]{l} AT\&T Labs - Research\\ Murray Hill, NJ 07974\\ U.S.A. \end{tabular}& \begin{tabular}[t]{l} Dept. of Comb. \& Opt.\\ University of Waterloo\\ Waterloo, Ontario\\ Canada N2L 3G1 \end{tabular} \end{tabular} \end{document}