Sufficient conditions for zero-one laws

Bell, Jason

doi:10.1090/S0002-9947-01-02884-7

Sufficient conditions for zero-one laws
HTML articles powered by AMS MathViewer

by Jason P. Bell PDF

Trans. Amer. Math. Soc. 354 (2002), 613-630 Request permission

Abstract:

We generalize a result of Bateman and Erdős concerning partitions, thereby answering a question of Compton. From this result it follows that if $\mathcal {K}$ is a class of finite relational structures that is closed under the formation of disjoint unions and the extraction of components, and if it has the property that the number of indecomposables of size $n$ is bounded above by a polynomial in $n$, then $\mathcal {K}$ has a monadic second order $0$-$1$ law. Moreover, we show that if a class of finite structures with the unique factorization property is closed under the formation of direct products and the extraction of indecomposable factors, and if it has the property that the number of indecomposables of size at most $n$ is bounded above by a polynomial in $\log n$, then this class has a first order $0$-$1$ law. These results cover all known natural examples of classes of structures that have been proved to have a logical $0$-$1$ law by Compton’s method of analyzing generating functions.

References

Tom M. Apostol, Introduction to analytic number theory, Undergraduate Texts in Mathematics, Springer-Verlag, New York-Heidelberg, 1976. MR 0434929
Stanley N. Burris, Number Theoretic Density and Logical Limit Laws. Mathematical Surveys and Monographs, 86. American Mathematical Society, Providence, RI, 2001.
Stanley Burris and András Sárközy, Fine spectra and limit laws. I. First-order laws, Canad. J. Math. 49 (1997), no. 3, 468–498. MR 1451257, DOI 10.4153/CJM-1997-022-4
Stanley Burris and András Sárközy, Fine spectra and limit laws. I. First-order laws, Canad. J. Math. 49 (1997), no. 3, 468–498. MR 1451257, DOI 10.4153/CJM-1997-022-4
Kevin J. Compton, A logical approach to asymptotic combinatorics. I. First order properties, Adv. in Math. 65 (1987), no. 1, 65–96. MR 893471, DOI 10.1016/0001-8708(87)90019-3
Kevin J. Compton, A logical approach to asymptotic combinatorics. II. Monadic second-order properties, J. Combin. Theory Ser. A 50 (1989), no. 1, 110–131. MR 978070, DOI 10.1016/0097-3165(89)90009-5
G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, 5th ed., The Clarendon Press, Oxford University Press, New York, 1979. MR 568909
John Lawrence, personal communication.
Albert Eagle, Series for all the roots of a trinomial equation, Amer. Math. Monthly 46 (1939), 422–425. MR 5, DOI 10.2307/2303036
Herbert S. Wilf, generatingfunctionology, Academic Press, Inc., Boston, MA, 1990. MR 1034250