Asymptotique des récurrences mahlériennes : le cas cyclotomique
Journal de Théorie des Nombres de Bordeaux, Tome 8 (1996) no. 1, pp. 1-30.

Nous étudions le comportement asymptotique d’une classe de suites mahlériennes dont les séries génératrices sont des produits infinis. Un exemple caractéristique est celui de l’estimation des coefficients de Taylor de k=0 + (1+z 2 k +z 2 k+1 ) -1 , voisin des partitions binaires étudiées par De Bruijn. Le résultat obtenu illustre un cas typique d’une classification naturelle des suites mahlériennes. Les techniques utilisées, transformation de Mellin ou méthode du col, ressortissent à la théorie analytique des nombres et à l’analyse asymptotique. Elles mettent en valeur un comportement doublement périodique : l’un, prévisible, suivant l’échelle ordinaire et l’autre, plus subtil, en échelle logarithmique.

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 k=0 (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.

@article{JTNB_1996__8_1_1_0,
     author = {Dumas, Philippe and Flajolet, Philippe},
     title = {Asymptotique des r\'ecurrences mahl\'eriennes : le cas cyclotomique},
     journal = {Journal de Th\'eorie des Nombres de Bordeaux},
     pages = {1--30},
     publisher = {Universit\'e Bordeaux I},
     volume = {8},
     number = {1},
     year = {1996},
     doi = {10.5802/jtnb.154},
     zbl = {0869.11080},
     mrnumber = {1399944},
     language = {fr},
     url = {jtnb.centre-mersenne.org/item/JTNB_1996__8_1_1_0/}
}
Philippe Dumas; Philippe Flajolet. Asymptotique des récurrences mahlériennes : le cas cyclotomique. Journal de Théorie des Nombres de Bordeaux, Tome 8 (1996) no. 1, pp. 1-30. doi : 10.5802/jtnb.154. https://jtnb.centre-mersenne.org/item/JTNB_1996__8_1_1_0/

[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. | JFM 55.0115.01 | MR 1512537

[15], On a special functional equation, Journal of the London Mathematical Society 15 (1940), 115-123. | JFM 66.0563.02 | MR 2921

[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. | Numdam | 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. | JFM 53.0180.04 | MR 1424469

[23] Roderick Wong, Asymptotic approximations of integrals, Academic Press, 1989. | MR 1016818 | Zbl 0679.41001