Asymptotique des récurrences mahlériennes : le cas cyclotomique

Dumas, Philippe; Flajolet, Philippe

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 ${\prod }_{k=0}^{+\infty }{(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 ${\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.

[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

[2] Jean-Paul Allouche et Jeffrey Shallit, The ring of k-regular sequences, Theoretical Computer Science 98 (1992), 163-197. | MR | Zbl

[3] George E. Andrews, The theory of partitions, Encyclopedia of Mathematics and its Applications, vol. 2, Addison-Wesley, 1976. | MR | Zbl

[4] Thomas H. Cormen, Charles E. Leiserson, et Ronald L. Rivest, Introduction to Algorithms, MIT Press, New York, 1990. | MR | Zbl

[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

[6] ____, Asymptotic methods in analysis, Dover, 1981, A reprint of the third North Holland edition, 1970 (first edition, 1958). | MR

[7] Hubert Delange, Sur la fonction sommatoire de la fonction somme des chiffres, L'enseignement Mathématique XXI (1975), no. 1, 31-47. | MR | Zbl

[8] G. Doetsch, Theorie und Andwendung der Laplace-Transformation, Die Grundlehren der mathematischen Wissenschaften in Einzeldarstellungen, vol. XLVII, Verlag von Julius Springer, 1937. | Zbl

[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

[11], Mellin transforms and asymptotics: The mergesort recurrence, Acta Informatica 31 (1994), 673-696. | MR | Zbl

[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 | Zbl

[13] Leo J. Guibas et Andrew M. Odlyzko, Periods in strings, Journal of Combinatorial Theory, Series A 30 (1981), 19-42. | MR | Zbl

[14] Kurt Mahler, Arithmetische Eigenschaften der Lösungen einer Klasse von Funktionalgleichungen, Mathematische Annalen 101 (1929), 342-366. | JFM | MR

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

[16], Arithmetic properties of lacunary power series with integral coefficients, Journal of the Australian Mathematical Society 5 (1965), 56-64. | MR | Zbl

[17], Fifty years as a mathematician, Journal of Number Theory 14 (1982), 121-155. | MR | Zbl

[18] Mireille Régnier, Enumeration of bordered words, RAIRO Theoretical Informatics and Applications 26 (1992), no. 4, 303-317. | Numdam | MR | Zbl

[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 | Zbl

[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 | Zbl

[21] E.C. Titchmarsh et D.R. Heath-Brown, The theory of the Riemann zeta-function, second ed., Oxford Science Publications, 1986. | MR | Zbl

[22] E.T. Whittaker et G.N. Watson, A course of modern analysis, fourth ed., Cambridge University Press, 1927, Reprinted 1973. | JFM | MR

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