Fine Spectra and Limit Laws I. First-Order Laws

Burris, Stanley ; Sárközy, András

Canadian journal of mathematics, Tome 49 (1997) no. 3, pp. 468-498

Résumé

Using Feferman-Vaught techniques we show a certain property of the fine spectrumof an admissible class of structures leads to a first-order 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 law. We present three conditions for verifying that the above property actually holds.The first condition is that the count function of an admissible class has regular variation with a certain uniformity of convergence. This applies to a wide range of admissible classes, including those satisfying Knopfmacher's Axiom A, and those satisfying Bateman and Diamond's condition.The second condition is similar to the first condition, but designed to handle the discrete case, i.e., when the sizes of the structures in an admissible class K are all powers of a single integer. It applies when either the class of indecomposables or the whole class satisfies Knopfmacher's Axiom A#.The third condition is also for the discrete case, when there is a uniform bound on the number of K-indecomposables of any given size.

Détail

DOI : 10.4153/CJM-1997-022-4

Mots-clés : O3C13, 11N45, 11N80, 05A15, 05A16, 11M41, 11P81, First order limit laws, generalized number theory

Bibliographie

[1] 1. Bateman, P.T. and Diamond, H.G., Asymptotic distribution of Beurling's generalized prime numbers, . In: Studies in Number Theory, (ed. LeVeque, W.), MAA Stud. Math. 6, Prentice-Hall, 1969. Google Scholar

[2] 2. Beurling, A., Analyse de la loi asymptotique de la distribution des nombres premiers généralisés, I, Acta Math. 68(1937), 255–291. Google Scholar

[3] 3. Bigelow, D. and Burris, S., Boolean algebras of factor congruences, Acta Sci. Math. (Szeged) 54(1990), 11–20. Google Scholar

[4] 4. Burris, S. and Idziak, P., A directly representable variety has a discrete first-order law, International J. Algebra Comput. 6(1996), 269–276. Google Scholar

[5] 5. Compton, K., A logical approach to asymptotic combinatorics. I. First order properties, Adv. in Math. 65(1987), 65–96. Google Scholar

[6] 6. Compton, K.J., Henson, C.W. and Shelah, S., Nonconvergence, undecidability, and intractability in asymptotic problems, Ann. Pure Appl. Logic 36(1987), 207–224. Google Scholar

[7] 7. Compton, K., Odlyzko, A. and Richmond, B., Fine spectra and limit laws II. First-order0–1 laws. Google Scholar

[8] 8. Feferman, S. and Vaught, R.L., The first-order properties of algebraic systems, Fund. Math. 47(1959), 57–103. Google Scholar

[9] 9. Geluk, J.L. and de Haan, L., Regular variation, extensions and Tauberian theorems, CWI Tract 40, Centre for Mathematics and Computer Science, 1987. Google Scholar

[10] 10. Higman, G., Enumerating p-groups. I: Inequalities, Proc. London Math. Soc. 10(1960), 24–30. Google Scholar

[11] 11. Knopfmacher, J., Arithmetical properties of finite rings and algebras, and analytic number theory. I, J. Reine Angew. Math. 252(1972), 16–43. Google Scholar

[12] 12. Knopfmacher, J., Arithmetical properties of finite rings and algebras, and analytic number theory. III. Finite modules and algebras over Dedekind domains, J. Reine Angew. Math. 259(1973), 157–170. Google Scholar

[13] 13. Knopfmacher, J., Abstract Analytic Number Theory, North Holland, 1975. Google Scholar

[14] 14. Knopfmacher, J., Analytic Arithmetic of Algebraic Function Fields, Marcel Dekker, Inc., 1979. Google Scholar

[15] 15. Knopfmacher, A., Knopfmacher, J. and Warlimont, R., “Factorisatio numerorum” in arithmetical semigroups, Acta Arith. 61(1992), 328–336. Google Scholar

[16] 16. Landau, E., Neuer Beweis des Primzahlsatzes und Beweis des Primidealsatzes, Math. Ann. 56(1903), 645–670. Google Scholar

[17] 17. McKenzie, R., McNulty, G., and Taylor, W., Algebras, Varieties, Lattices. Vol. I, Wadsworth and Cole/Brooks, 1987. Google Scholar

[18] 18. Oppenheim, A., On an arithmetic function, J. London Math. Soc. 1(1926), 105–211. Google Scholar

[19] 19. Oppenheim, A., On an arithmetic function (II), J. London Math. Soc. 2(1927), 123–130. Google Scholar

[20] 20. Skolem, Th., Untersuchungen über die Axiome des Klassenkalküls und über Produktations- und Summationsprobleme, welche gewisse Klassen von Aussagen betreffen, Videnskabsakademiet i Kristiania, Skrifter I, 3, 1919. 37. Google Scholar

[21] 21. Szekeres, G. and Turán, P., Über das zweite Hauptproblem der “Factorisatio Numerorum”, Acta Litt. Szeged 6(1933), 143–154. Google Scholar

[22] 22. Taylor, W., The fine spectrum of a variety, Algebra Universalis 5(1975), 263–303. Google Scholar

[23] 23. Titchmarsh, E.C., The theory of functions, 2nd ed., Oxford Univ. Press, 1939. Google Scholar

[24] 24. Wilf, H., Generating functionology, 2nd ed., Academic Press, 1994. Google Scholar

[25] 25. Willard, R., Varieties having Boolean factor congruences, J. Algebra 130(1990), 130–153. Google Scholar