Asymptotics of Mahler recurrences: The cyclotomic case. (Asymptotique des récurrences mahlériennes: Le cas cyclotomique.) (French) Zbl 0869.11080

Mahler studied the transcendence properties of functions such as \(\sum z^{B^n}\) and \(\prod (1-z^{B^n})^{-1}\) and, more generally, solutions of functional equations of the shape \(c_0(z) f(z)+c_1(z) f(z^B)+ \cdots +c_N(z) f(z^{B^N})=0\). He developed new methods to resolve questions about the transcendence and algebraic independence of functions of this type and their values at algebraic points. The Mahler functions appear in many applications, including the theory of partitions and the theory of automata and as generating functions for various combinatorial problems.
De Bruijn gave very precise asymptotic estimates for binary partitions and partitions whose parts are powers of \(B\) by analysing the particular Mahler function \(\prod (1-z^{B^n})^{-1}\). The analytic technique is based on Mellin transforms and the circle method. In this paper, the method is developed to obtain the asymptotic expansion \[ \prod^\infty_{k=0} {1\over\Phi_a(z^{B^k})} \sim\exp \left[{\log^2 \rho \over 2\log B} +(1+ \kappa) \log\rho +n\rho+ {1\over 2} \log n\rho \right] \times \sum^\infty_{k=0} {1\over (n \rho)^{k/2}} \omega_k \left({\log\rho \over\varphi (a)\log B} \right), \] where \(\Phi_a\) is the cyclotomic polynomial of order \(a\), \(\rho\) is defined by \(\log\rho \sim- \log n+ \log\log n-\log \log 2+ o(1)\) and the functions \(\omega_k\) are analytic and have period 1.
The waves which appear in the expansion are typical and arise in various problems about restricted partitions [see K. F. Roth and G. Szekeres, Q. J. Math., Oxf. II. Ser. 5, 241-259 (1954; Zbl 0057.03902)] which gives the asymptotic behaviour of the number of partitions of \(n\) into \(m\) parts and also in the spectral study of automata [see E. Bombieri and J. E. Taylor, J. Phys. 47, Colloq. C3, Suppl. au No. 7, 19-28 (1986; Zbl 0693.52002)] which discusses the same phenomenon in the context of the properties of 1-dimensional quasicrystals.


11P82 Analytic theory of partitions
11B85 Automata sequences
11B37 Recurrences
Full Text: DOI Numdam EuDML EMIS


[1] Abramowitz, Milton et Stegun, Irene A., Handbook of mathematical functions, Dover, 1973, A reprint of the tenth National Bureau of Standards edition, 1964. · Zbl 0643.33001
[2] Allouche, Jean-Paul et Shallit, Jeffrey, The ring of k-regular sequences, Theoretical Computer Science98 (1992), 163-197. · Zbl 0774.68072
[3] Andrews, George E., The theory of partitions, Encyclopedia of Mathematics and its Applications, vol. 2, Addison-Wesley, 1976. · Zbl 0655.10001
[4] Cormen, Thomas H., Leiserson, Charles E., et Rivest, Ronald L., Introduction to Algorithms, MIT Press, New York, 1990. · Zbl 1047.68161
[5] de Bruijn, N.G., 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). · Zbl 0082.04202
[7] Delange, Hubert, Sur la fonction sommatoire de la fonction somme des chiffres, L’enseignement MathématiqueXXI (1975), no. 1, 31-47. · Zbl 0306.10005
[8] Doetsch, G., Theorie und Andwendung der Laplace-Transformation, Die Grundlehren der mathematischen Wissenschaften in Einzeldarstellungen, vol. XLVII, Verlag von Julius Springer, 1937. · Zbl 0018.12903
[9] Dumas, Philippe, Récurrences mahlériennes, suites automatiques et études asymptotiques, Doctorat de mathématiques, Université de Bordeaux I, 1993.
[10] Flajolet, Philippe et Golin, Mordecai, Exact asymptotics of divide-and-conquer recurrences, Proceedings of ICALP’93, Lund., July 1993. · Zbl 1418.68252
[11] , Mellin transforms and asymptotics: The mergesort recurrence, Acta Informatica31 (1994), 673-696. · Zbl 0818.68064
[12] Flajolet, Philippe, Grabner, Peter, Kirschenhofer, Peter, Prodinger, Helmut, et Tichy, Robert, Mellin transforms and asymptotics: Digital sums, Theoretical Computer Science123 (1994), 291-314. · Zbl 0788.44004
[13] Guibas, Leo J. et Odlyzko, Andrew M., Periods in strings, Journal of Combinatorial Theory, Series A 30 (1981), 19-42. · Zbl 0464.68070
[14] Kurt, Mahler, Arithmetische Eigenschaften der Lösungen einer Klasse von Funktionalgleichungen, Mathematische Annalen101 (1929), 342-366. · JFM 55.0115.01
[15] , On a special functional equation, Journal of the London Mathematical Society15 (1940), 115-123. · JFM 66.0563.02
[16] , Arithmetic properties of lacunary power series with integral coefficients, Journal of the Australian Mathematical Society5 (1965), 56-64. · Zbl 0148.27703
[17] , Fifty years as a mathematician, Journal of Number Theory14 (1982), 121-155. · Zbl 0482.10002
[18] Régnier, Mireille, Enumeration of bordered words, RAIRO Theoretical Informatics and Applications26 (1992), no. 4, 303-317. · Zbl 0754.68089
[19] Stolarsky, Kenneth B., Power and exponential sums of digital sums related to binomial coefficients, SIAM Journal on Applied Mathematics32 (1977), no. 4, 717-730. · Zbl 0355.10012
[20] Supowit, K.J. et Reingold, E.M., Divide and conquer heuristics for minimum weighted Euclidean matching, SIAM Journal on Computing12 (1983), no. 1, 118-143. · Zbl 0501.68032
[21] Titchmarsh, E.C. et Heath-Brown, D.R., The theory of the Riemann zeta-function, second ed., Oxford Science Publications, 1986. · Zbl 0601.10026
[22] Whittaker, E.T. et Watson, G.N., A course of modern analysis, fourth ed., Cambridge University Press, 1927, Reprinted 1973. · JFM 53.0180.04
[23] Roderick, Wong, Asymptotic approximations of integrals, Academic Press, 1989. · Zbl 0679.41001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.