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

Philippe Dumas; Philippe Flajolet

Journal de théorie des nombres de Bordeaux (1996)

  • Volume: 8, Issue: 1, page 1-30
  • ISSN: 1246-7405

Abstract

top
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.

How to cite

top

Dumas, Philippe, and Flajolet, Philippe. "Asymptotique des récurrences mahlériennes : le cas cyclotomique." Journal de théorie des nombres de Bordeaux 8.1 (1996): 1-30. <http://eudml.org/doc/247821>.

@article{Dumas1996,
abstract = {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.},
author = {Dumas, Philippe, Flajolet, Philippe},
journal = {Journal de théorie des nombres de Bordeaux},
keywords = {Mahler functions; partitions; automata; generating functions; Mellin transforms; circle method; asymptotic expansion; cyclotomic polynomial},
language = {fre},
number = {1},
pages = {1-30},
publisher = {Université Bordeaux I},
title = {Asymptotique des récurrences mahlériennes : le cas cyclotomique},
url = {http://eudml.org/doc/247821},
volume = {8},
year = {1996},
}

TY - JOUR
AU - Dumas, Philippe
AU - Flajolet, Philippe
TI - Asymptotique des récurrences mahlériennes : le cas cyclotomique
JO - Journal de théorie des nombres de Bordeaux
PY - 1996
PB - Université Bordeaux I
VL - 8
IS - 1
SP - 1
EP - 30
AB - 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.
LA - fre
KW - Mahler functions; partitions; automata; generating functions; Mellin transforms; circle method; asymptotic expansion; cyclotomic polynomial
UR - http://eudml.org/doc/247821
ER -

References

top
  1. [1] Milton Abramowitz et Irene A. Stegun, Handbook of mathematical functions, Dover, 1973, A reprint of the tenth National Bureau of Standards edition, 1964. Zbl0643.33001
  2. [2] Jean-Paul Allouche et Jeffrey Shallit, The ring of k-regular sequences, Theoretical Computer Science98 (1992), 163-197. Zbl0774.68072MR1166363
  3. [3] George E. Andrews, The theory of partitions, Encyclopedia of Mathematics and its Applications, vol. 2, Addison-Wesley, 1976. Zbl0655.10001MR557013
  4. [4] Thomas H. Cormen, Charles E. Leiserson, et Ronald L. Rivest, Introduction to Algorithms, MIT Press, New York, 1990. Zbl1047.68161MR1066870
  5. [5] N.G. de Bruijn, On Mahler's partition problem, Indagationes Math.10 (1948), 210-220, Reprinted from Koninkl. Nederl. Akademie Wetenschappen, Ser. A. Zbl0030.34502
  6. [6] ____, Asymptotic methods in analysis, Dover, 1981, A reprint of the third North Holland edition, 1970 (first edition, 1958). MR671583
  7. [7] Hubert Delange, Sur la fonction sommatoire de la fonction somme des chiffres, L'enseignement MathématiqueXXI (1975), no. 1, 31-47. Zbl0306.10005MR379414
  8. [8] G. Doetsch, Theorie und Andwendung der Laplace-Transformation, Die Grundlehren der mathematischen Wissenschaften in Einzeldarstellungen, vol. XLVII, Verlag von Julius Springer, 1937. Zbl0018.12903
  9. [9] Philippe Dumas, Récurrences mahlériennes, suites automatiques et études asymptotiques, Doctorat de mathématiques, Université de Bordeaux I, 1993. 
  10. [10] Philippe Flajolet et Mordecai Golin, Exact asymptotics of divide-and-conquer recurrences, Proceedings of ICALP'93, Lund., July 1993. MR1252408
  11. [11], Mellin transforms and asymptotics: The mergesort recurrence, Acta Informatica31 (1994), 673-696. Zbl0818.68064MR1300060
  12. [12] Philippe Flajolet, Peter Grabner, Peter Kirschenhofer, Helmut Prodinger, et Robert Tichy, Mellin transforms and asymptotics: Digital sums, Theoretical Computer Science123 (1994), 291-314. Zbl0788.44004MR1256203
  13. [13] Leo J. Guibas et Andrew M. Odlyzko, Periods in strings, Journal of Combinatorial Theory, Series A30 (1981), 19-42. Zbl0464.68070MR607037
  14. [14] Kurt Mahler, Arithmetische Eigenschaften der Lösungen einer Klasse von Funktionalgleichungen, Mathematische Annalen101 (1929), 342-366. Zbl55.0115.01MR1512537JFM55.0115.01
  15. [15], On a special functional equation, Journal of the London Mathematical Society15 (1940), 115-123. Zbl0027.15704MR2921JFM66.0563.02
  16. [16], Arithmetic properties of lacunary power series with integral coefficients, Journal of the Australian Mathematical Society5 (1965), 56-64. Zbl0148.27703MR190094
  17. [17], Fifty years as a mathematician, Journal of Number Theory14 (1982), 121-155. Zbl0482.10002MR655723
  18. [18] Mireille Régnier, Enumeration of bordered words, RAIRO Theoretical Informatics and Applications26 (1992), no. 4, 303-317. Zbl0754.68089MR1173172
  19. [19] Kenneth B. Stolarsky, Power and exponential sums of digital sums related to binomial coefficients, SIAM Journal on Applied Mathematics32 (1977), no. 4, 717-730. Zbl0355.10012MR439735
  20. [20] K.J. Supowit et E.M. Reingold, Divide and conquer heuristics for minimum weighted Euclidean matching, SIAM Journal on Computing12 (1983), no. 1, 118-143. Zbl0501.68032MR687806
  21. [21] E.C. Titchmarsh et D.R. Heath-Brown, The theory of the Riemann zeta-function, second ed., Oxford Science Publications, 1986. Zbl0601.10026MR882550
  22. [22] E.T. Whittaker et G.N. Watson, A course of modern analysis, fourth ed., Cambridge University Press, 1927, Reprinted 1973. Zbl45.0433.02MR1424469JFM53.0180.04
  23. [23] Roderick Wong, Asymptotic approximations of integrals, Academic Press, 1989. Zbl0679.41001MR1016818

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.