Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-66644f4456-vjjx6 Total loading time: 0 Render date: 2025-02-13T03:19:09.561Z Has data issue: true hasContentIssue false

Analytic combinatorics of the transfinite: A unifying Tauberian perspective

Published online by Cambridge University Press:  01 March 2011

By
Andreas Weiermann
Edited by
Françoise Delon ,
Ulrich Kohlenbach ,
Penelope Maddy  and
Frank Stephan
Françoise Delon
Affiliation:
UFR de Mathématiques
Ulrich Kohlenbach
Affiliation:
Technische Universität, Darmstadt, Germany
Penelope Maddy
Affiliation:
University of California, Irvine
Frank Stephan
Affiliation:
National University of Singapore
Get access

Summary

Abstract. From a Tauberian perspective we prove and survey several results about the analytic combinatorics of (transfinite) proof-theoretic ordinals. In particular we show how certain theorems of Petrogradsky, Karamata, Kohlbecker, Parameswaran, and Wagner can be used to give a unified treatment of asymptotics for count functions for ordinals. This uniform approach indicates that (Tauberian theorems for) Laplace transforms provide a general tool to establish connections between additive and multiplicative results and may therefore be seen as a contribution to Problem 12.21 in Burris's book on number theoretic density and logical limit laws. In the last section we give applications and prove in some detail phase transitions related to Friedman style combinatorial well-orderdness principles for fragments of first order Peano arithmetic.

Introduction to the transfinite combinatorics of the transfinite. Some years ago the author had a discussion with another logician about which fields in mathematics are surely have no connection with each other. A suggestion was: The theory of transfinite ordinal numbers and complex analysis. Of course this seems a safe guess since it is difficult to imagine that Cauchy's integral formula has something to say about the ordinals below ωω or below ∈0.

It has therefore been surprising that those connections exist and give rise to interesting cross-disciplinary applications. Perhaps even more interestingly we apply in this paper results from a paper in Lie-algebra theory to questions in logic.

Type
Chapter
Information
Logic Colloquium 2007 , pp. 238 - 267
Publisher: Cambridge University Press
Print publication year: 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] W., Ackermann, Zur Widerspruchsfreiheit der Zahlentheorie, Mathematische Annalen, vol. 117 (1940), pp. 162–194.Google Scholar
[2] G. E., Andrews, The Theory of Partitions, Encyclopedia of Mathematics and Its Applications, vol. 2, Addison-Wesley, Reading, Mass.-London-Amsterdam, 1976.Google Scholar
[3] T. M., Apostol, Introduction to Analytic Number Theory, Undergraduate Texts in Mathematics, Springer-Verlag, New York, 1976.Google Scholar
[4] T., Arai, On the slowly well orderedness of ε0, Mathematical Logic Quarterly, vol. 48 (2002), no. 1, pp. 125–130.Google Scholar
[5] P., Bell and S., Burris, Partition identities. I. Sandwich theorems and logical 0-1 laws, Electronic Journal of Combinatorics, vol. 11 (2004), no. 1, pp. Research Paper 49, 25 pp. (electronic).Google Scholar
[6] N. H., Bingham, C. M., Goldie, and J. L., Teugels, Regular Variation, Encyclopedia of Mathematics and Its Applications, vol. 27, Cambridge University Press, Cambridge, 1989.Google Scholar
[7] W., Buchholz, A., Cichon, and A., Weiermann, A uniform approach to fundamental sequences and hierarchies, Mathematical Logic Quarterly, vol. 40 (1994), no. 2, pp. 273–286.Google Scholar
[8] S. N., Burris, Number Theoretic Density and Logical Limit Laws, Mathematical Surveys and Monographs, vol. 86, American Mathematical Society, Providence, RI, 2001.Google Scholar
[9] N. G., de Bruijn, On Mahler's partition problem, Nederl. Akad. Wetensch., Proc., vol. 51 (1948), pp. 659–669 = Indagationes Math. 10, 210–220 (1948).Google Scholar
[10] R., de la Bretèche and G., Tenenbaum, Sur certaines équations fonctionnelles arithmétiques, Université de Grenoble. Annales de l'Institut Fourier, vol. 50 (2000), no. 5, pp. 1445–1505.Google Scholar
[11] A., den Boer, An independence result for PA using multiplicative number theory, http://cage.rug.ac.be/∼weierman/.
[12] P., Dumas and P., Flajolet, Asymptotique des récurrences mahlériennes: le cas cyclotomique, Journal de Théorie des Nombres de Bordeaux, vol. 8 (1996), no. 1, pp. 1–30.Google Scholar
[13] P., Erdös, On an elementary proof of some asymptotic formulas in the theory of partitions, Annals of Mathematics. Second Series, vol. 43 (1942), pp. 437–450.Google Scholar
[14] P., Flajolet and R., Sedgewick, Analytic Combinatorics, Cambridge University Press, Cambridge, 2009.Google Scholar
[15] J. L., Geluk, L., de Haan, and U., Stadtmüller, A Tauberian theorem of exponential type, Canadian Journal of Mathematics. Journal Canadien de Mathématiques, vol. 38 (1986), no. 3, pp. 697–718.Google Scholar
[16] B., Gittenberger, On the contour of random trees, SIAM Journal on Discrete Mathematics, vol. 12 (1999), no. 4, pp. 434–458 (electronic).Google Scholar
[17] I., Gutman and A., Ivić, On Matula numbers, Discrete Mathematics, vol. 150 (1996), no. 1–3, pp. 131–142, Selected papers in honour of Paul Erdős on the occasion of his 80th birthday (Keszthely, 1993).Google Scholar
[18] G. H., Hardy and S., Ramanujan, Asymptotic formulœ for the distribution of integers of various types [Proc. London Math. Soc. (2) 16 (1917), 112–132], Collected Papers of Srinivasa Ramanujan, AMS Chelsea, Providence, RI, 2000, pp. 245–261.Google Scholar
[19] A. E., Ingham, A Tauberian theorem for partitions, Annals of Mathematics. Second Series, vol. 42 (1941), pp. 1075–1090.Google Scholar
[20] D. E., Knuth, The Art of Computer Programming. Volume 1: Fundamental Algorithms, Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing, Reading, Mass.-London-Don Mills, Ont., 1973.Google Scholar
[21] E. E., Kohlbecker, Weak asymptotic properties of partitions, Transactions of the American Mathematical Society, vol. 88 (1958), pp. 346–365.Google Scholar
[22] J., Korevaar, Tauberian Theory: A Century of Developments, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 329, Springer-Verlag, Berlin, 2004.Google Scholar
[23] L., Mutafchiev, Asymptotic Enumeration of Plane Partitions of Large Integers and Hayman's Theorem for Admissible Generating Functions, unpublished preprint.
[24] A. M., Odlyzko, Asymptotic enumeration methods, Handbook of Combinatorics, vol. 1, 2 (R. L., Graham, M., Groetschel, and L., Lovasz, editors), Elsevier, Amsterdam, 1995, pp. 1063–1229.Google Scholar
[25] A. M., Odlyzko and L. B., Richmond, Asymptotic expansions for the coefficients of analytic generating functions, Aequationes Mathematicae, vol. 28 (1985), no. 1-2, pp. 50–63.Google Scholar
[26] H.-H., Ostmann, Additive Zahlentheorie. Erster Teil: Allgemeine Untersuchungen. Zweiter Teil: Spezielle Zahlenmengen, Ergebnisse der Mathematik und ihrer Grenzgebiete (N.F.), Hefte 7, vol. 11, Springer-Verlag, Berlin, 1956.Google Scholar
[27] S., Parameswaran, Partition functions whose logarithms are slowly oscillating, Transactions of the American Mathematical Society, vol. 100 (1961), pp. 217–240.Google Scholar
[28] W. B., Pennington, On Mahler's partition problem, Annals of Mathematics. Second Series, vol. 57 (1953), pp. 531–546.Google Scholar
[29] V. M., Petrogradsky, Growth of finitely generated polynilpotent Lie algebras and groups, generalized partitions, and functions analytic in the unit circle, International Journal of Algebra and Computation, vol. 9 (1999), no. 2, pp. 179–212.Google Scholar
[30] G., Pólya and G., Szegö, Aufgaben und Lehrsätze der Analysis (Problems and Theorems in Analysis), Springer Grundlehren, Berlin, 1928.Google Scholar
[31] H. E., Rose, Subrecursion: Functions and Hierarchies, Oxford Logic Guides, vol. 9, The Clarendon Press Oxford University Press, New York, 1984.Google Scholar
[32] W., Schwarz, Schwache asymptotische Eigenschaften von Partitionen, Journal für die Reine und Angewandte Mathematik, vol. 232 (1968), pp. 1–16.Google Scholar
[33] R., Smith, The consistency strengths of some finite forms of the Higman and Kruskal theorems, Harvey Friedman's Research on the Foundations of Mathematics, Studies in Logic and the Foundations of Mathematics, vol. 117, North-Holland, Amsterdam, 1985, pp. 119–136.Google Scholar
[34] E., Wagner, Ein reeller Tauberscher Satz für die Laplace-Transformation, Mathematische Nachrichten, vol. 36 (1968), pp. 323–331.Google Scholar
[35] A., Weiermann, An application of graphical enumeration to PA, The Journal of Symbolic Logic, vol. 68 (2003), no. 1, pp. 5–16.Google Scholar
[36] A., Weiermann, An application of results by Hardy, Ramanujan and Karamata to Ackermannian functions, Discrete Mathematics & Theoretical Computer Science. DMTCS., vol. 6 (2003), no. 1, pp. 133–141 (electronic).Google Scholar
[37] A., Weiermann, Phase transitions for Gödel incompleteness, Annals of Pure and Applied Logic, vol. 157 (2009), pp. 281–296.Google Scholar
[38] M., Yamashita, Asymptotic estimation of the number of trees, The Transactions of the Institute of Electronics and Communication Engineers of Japan, vol. 62-A (1979), pp. 128–135 (in Japanese).Google Scholar

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

Available formats
×