|
Sufficient conditions for zero-one laws
Author(s):
Jason
P.
Bell
Journal:
Trans. Amer. Math. Soc.
354
(2002),
613-630.
MSC (1991):
Primary 60F20;
Secondary 05A16
Posted:
September 28, 2001
Retrieve article in:
PDF DVI PostScript
This article is available free of charge
Abstract |
References |
Similar articles |
Additional information
Abstract:
We generalize a result of Bateman and Erdos concerning partitions, thereby answering a question of Compton. From this result it follows that if 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 is bounded above by a polynomial in , then has a monadic second order - 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 is bounded above by a polynomial in , then this class has a first order - law. These results cover all known natural examples of classes of structures that have been proved to have a logical - law by Compton's method of analyzing generating functions.
References:
- 1.
- Tom M. Apostol, Introduction to Analytic Number Theory. Springer Verlag, 1976. MR 55:7892
- 2.
- Stanley N. Burris, Number Theoretic Density and Logical Limit Laws. Mathematical Surveys and Monographs, 86. American Mathematical Society, Providence, RI, 2001. CMP 2001:05
- 3.
- S. Burris, K. Compton, A. Odlyzko, and L.B. Richmond, Fine spectra and limit laws, II. First-order
- laws. Can. J. Math. 49 (1997), 641-652. MR 98k:03076b - 4.
- S. Burris and A. Sárközy, Fine spectra and limit laws I. First-order laws. Can. J. Math. 49 (1997), 468-498. MR 98k:03076a
- 5.
- K. Compton, A logical approach to asymptotic combinatorics. I. First order properties. Advances in Math. 65 (1987), 65-96. MR 88k:03065
- 6.
- K. Compton, A logical approach to asymptotic combinatorics. II. Monadic second-order properties. Journal of Combinatorial Theory, Series A 50 (1989), 110-131. MR 90c:03024
- 7.
- G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Oxford Press, 5th ed., 1979. MR 81i:10002
- 8.
- John Lawrence, personal communication.
- 9.
- H. Rademacher, On the expansion of the partition function in a series. Ann. of Math. (2) 44 (1943), 416-422. MR 5:35a
- 10.
- H. Wilf, Generatingfunctionology, Academic Press, 1990. MR 91g:05008
Similar Articles:
Retrieve articles in Transactions of the American Mathematical Society
with MSC
(1991):
60F20,
05A16
Retrieve articles in all Journals with MSC
(1991):
60F20,
05A16
Additional Information:
Jason
P.
Bell
Affiliation:
Department of Mathematics, University of California San Diego, La Jolla, California 92093-0112
Email:
jbell@math.ucsd.edu
DOI:
10.1090/S0002-9947-01-02884-7
PII:
S 0002-9947(01)02884-7
Received by editor(s):
April 10, 2000
Received by editor(s) in revised form:
May 18, 2001
Posted:
September 28, 2001
Additional Notes:
I am indebted to Stan Burris for pointing out that results obtained in the additive case lift to the multiplicative case, to John Lawrence for helping with an application, and to the referee for valuable comments regarding the presentation.
Copyright of article:
Copyright
2001,
American Mathematical Society
|