staple
With cedram.org

Search the site

Table of contents for this issue | Next article
Philippe Dumas; Philippe Flajolet
Asymptotique des récurrences mahlériennes : le cas cyclotomique
Journal de théorie des nombres de Bordeaux, 8 no. 1 (1996), p. 1-30, doi: 10.5802/jtnb.154
Article PDF | Reviews MR 1399944 | Zbl 0869.11080

Résumé - Abstract

We study the asymptotic behaviour of a class of Mahlerian sequences whose generating functions are expressible as infinite products. A typical case is the estimation of the Taylor coefficients of $\prod _{k=0}^\infty (1+z^{2^k}+z^{2^{k+1}})^{-1}$, a problem that is related to the asymptotic counting of binary partitions obtained earlier by De Bruijn. The main result of this paper fits into a natural classification of Mahlerian sequences. The techniques used involve Mellin transforms and saddle point analysis. They lead to a composite periodic behaviour for the coefficients considered.

Bibliography

[1] Milton Abramowitz et Irene A. Stegun, Handbook of mathematical functions, Dover, 1973, A reprint of the tenth National Bureau of Standards edition, 1964.  Zbl 0643.33001
[2] Jean-Paul Allouche et Jeffrey Shallit, The ring of k-regular sequences, Theoretical Computer Science 98 (1992), 163-197.  MR 1166363 |  Zbl 0774.68072
[3] George E. Andrews, The theory of partitions, Encyclopedia of Mathematics and its Applications, vol. 2, Addison-Wesley, 1976.  MR 557013 |  Zbl 0655.10001
[4] Thomas H. Cormen, Charles E. Leiserson, et Ronald L. Rivest, Introduction to Algorithms, MIT Press, New York, 1990.  MR 1066870 |  Zbl 1047.68161
[5] N.G. de Bruijn, On Mahler's partition problem, Indagationes Math.10 (1948), 210-220, Reprinted from Koninkl. Nederl. Akademie Wetenschappen, Ser. A.  Zbl 0030.34502
[6] ____, Asymptotic methods in analysis, Dover, 1981, A reprint of the third North Holland edition, 1970 (first edition, 1958).  MR 671583
[7] Hubert Delange, Sur la fonction sommatoire de la fonction somme des chiffres, L'enseignement Mathématique XXI (1975), no. 1, 31-47.  MR 379414 |  Zbl 0306.10005
[8] G. Doetsch, Theorie und Andwendung der Laplace-Transformation, Die Grundlehren der mathematischen Wissenschaften in Einzeldarstellungen, vol. XLVII, Verlag von Julius Springer, 1937.  Zbl 0018.12903
[9] Philippe Dumas, Récurrences mahlériennes, suites automatiques et études asymptotiques, Doctorat de mathématiques, Université de Bordeaux I, 1993.
[10] Philippe Flajolet et Mordecai Golin, Exact asymptotics of divide-and-conquer recurrences, Proceedings of ICALP'93, Lund., July 1993.  MR 1252408
[11], Mellin transforms and asymptotics: The mergesort recurrence, Acta Informatica 31 (1994), 673-696.  MR 1300060 |  Zbl 0818.68064
[12] Philippe Flajolet, Peter Grabner, Peter Kirschenhofer, Helmut Prodinger, et Robert Tichy, Mellin transforms and asymptotics: Digital sums, Theoretical Computer Science 123 (1994), 291-314.  MR 1256203 |  Zbl 0788.44004
[13] Leo J. Guibas et Andrew M. Odlyzko, Periods in strings, Journal of Combinatorial Theory, Series A 30 (1981), 19-42.  MR 607037 |  Zbl 0464.68070
[14] Kurt Mahler, Arithmetische Eigenschaften der Lösungen einer Klasse von Funktionalgleichungen, Mathematische Annalen 101 (1929), 342-366.  MR 1512537 |  JFM 55.0115.01
[15], On a special functional equation, Journal of the London Mathematical Society 15 (1940), 115-123.  MR 2921 |  JFM 66.0563.02
[16], Arithmetic properties of lacunary power series with integral coefficients, Journal of the Australian Mathematical Society 5 (1965), 56-64.  MR 190094 |  Zbl 0148.27703
[17], Fifty years as a mathematician, Journal of Number Theory 14 (1982), 121-155.  MR 655723 |  Zbl 0482.10002
[18] Mireille Régnier, Enumeration of bordered words, RAIRO Theoretical Informatics and Applications 26 (1992), no. 4, 303-317.  MR 1173172 |  Zbl 0754.68089
[19] Kenneth B. Stolarsky, Power and exponential sums of digital sums related to binomial coefficients, SIAM Journal on Applied Mathematics 32 (1977), no. 4, 717-730.  MR 439735 |  Zbl 0355.10012
[20] K.J. Supowit et E.M. Reingold, Divide and conquer heuristics for minimum weighted Euclidean matching, SIAM Journal on Computing 12 (1983), no. 1, 118-143.  MR 687806 |  Zbl 0501.68032
[21] E.C. Titchmarsh et D.R. Heath-Brown, The theory of the Riemann zeta-function, second ed., Oxford Science Publications, 1986.  MR 882550 |  Zbl 0601.10026
[22] E.T. Whittaker et G.N. Watson, A course of modern analysis, fourth ed., Cambridge University Press, 1927, Reprinted 1973.  MR 1424469 |  JFM 53.0180.04
[23] Roderick Wong, Asymptotic approximations of integrals, Academic Press, 1989.  MR 1016818 |  Zbl 0679.41001