Computing solutions of linear Mahler equations

Chyzak, Frédéric; Dreyfus, Thomas; Dumas, Philippe; Mezzarobba, Marc

doi:10.1090/mcom/3359

Computing solutions of linear Mahler equations
HTML articles powered by AMS MathViewer

by Frédéric Chyzak, Thomas Dreyfus, Philippe Dumas and Marc Mezzarobba PDF

Math. Comp. 87 (2018), 2977-3021 Request permission

Abstract:

Mahler equations relate evaluations of the same function $f$ at iterated $b$th powers of the variable. They arise, in particular, in the study of automatic sequences and in the complexity analysis of divide-and-conquer algorithms. Recently, the problem of solving Mahler equations in closed form has occurred in connection with number-theoretic questions. A difficulty in the manipulation of Mahler equations is the exponential blow-up of degrees when applying a Mahler operator to a polynomial. In this work, we present algorithms for solving linear Mahler equations for series, polynomials, and rational functions, and get polynomial-time complexity under a mild assumption. Incidentally, we develop an algorithm for computing the gcrd of a family of linear Mahler operators.

References

Shreeram Abhyankar, Two notes on formal power series, Proc. Amer. Math. Soc. 7 (1956), 903–905. MR 80647, DOI 10.1090/S0002-9939-1956-0080647-9
S. A. Abramov, Rational solutions of linear differential and difference equations with polynomial coefficients, Zh. Vychisl. Mat. i Mat. Fiz. 29 (1989), no. 11, 1611–1620, 1757 (Russian); English transl., U.S.S.R. Comput. Math. and Math. Phys. 29 (1989), no. 6, 7–12 (1991). MR 1025995, DOI 10.1016/S0041-5553(89)80002-3
S. A. Abramov, Rational solutions of linear difference and $q$-difference equations with polynomial coefficients, Programmirovanie 6 (1995), 3–11 (Russian, with Russian summary); English transl., Program. Comput. Software 21 (1995), no. 6, 273–278. MR 1615571
Boris Adamczewski and Colin Faverjon, Méthode de Mahler: relations linéaires, transcendance et applications aux nombres automatiques, Proc. Lond. Math. Soc. (3) 115 (2017), no. 1, 55–90 (French, with English and French summaries). MR 3669933, DOI 10.1112/plms.12038
Boris Adamczewski and Colin Faverjon, Méthode de Mahler: relations linéaires, transcendance et applications aux nombres automatiques, Proc. Lond. Math. Soc. (3) 115 (2017), no. 1, 55–90 (French, with English and French summaries). MR 3669933, DOI 10.1112/plms.12038
Jason P. Bell and Michael Coons, Transcendence tests for Mahler functions, Proc. Amer. Math. Soc. 145 (2017), no. 3, 1061–1070. MR 3589306, DOI 10.1090/proc/13297
Alin Bostan, Philippe Flajolet, Bruno Salvy, and Éric Schost, Fast computation of special resultants, J. Symbolic Comput. 41 (2006), no. 1, 1–29. MR 2194883, DOI 10.1016/j.jsc.2005.07.001
Manuel Bronstein, On solutions of linear ordinary difference equations in their coefficient field, J. Symbolic Comput. 29 (2000), no. 6, 841–877. MR 1765927, DOI 10.1006/jsco.2000.0368
Claude Chevalley, Introduction to the Theory of Algebraic Functions of One Variable, Mathematical Surveys, No. VI, American Mathematical Society, New York, N. Y., 1951. MR 0042164
Gilles Christol, Ensembles presque periodiques $k$-reconnaissables, Theoret. Comput. Sci. 9 (1979), no. 1, 141–145 (French, with English summary). MR 535129, DOI 10.1016/0304-3975(79)90011-2
G. Christol, T. Kamae, M. Mendès France, and G. Rauzy, Suites algébriques, automates et substitutions, Bull. Soc. Math. France 108 (1980), no. 4, 401–419 (French, with English summary). MR 614317
T. Dreyfus, Charlotte Hardouin, and Julien Roques, Hypertranscendance of solutions of Mahler equations, J. Eur. Math. Soc. (2015), 26 pages. To appear. http://arxiv.org/abs/1507.03361.
Philippe Dumas, Récurrences mahlériennes, suites automatiques, études asymptotiques, Institut National de Recherche en Informatique et en Automatique (INRIA), Rocquencourt, 1993 (French, with French summary). Thèse, Université de Bordeaux I, Talence, 1993. MR 1346304
D. Yu. Grigor′ev, Complexity of factoring and calculating the GCD of linear ordinary differential operators, J. Symbolic Comput. 10 (1990), no. 1, 7–37. MR 1081258, DOI 10.1016/S0747-7171(08)80034-X
Peter Henrici, Applied and computational complex analysis. Vol. 1, Wiley Classics Library, John Wiley & Sons, Inc., New York, 1988. Power series—integration—conformal mapping—location of zeros; Reprint of the 1974 original; A Wiley-Interscience Publication. MR 1008928
Oscar H. Ibarra, Shlomo Moran, and Roger Hui, A generalization of the fast LUP matrix decomposition algorithm and applications, J. Algorithms 3 (1982), no. 1, 45–56. MR 646891, DOI 10.1016/0196-6774(82)90007-4
K. Mahler, Berichtigung zu der Arbeit von K. Mahler: Arithmetische Eigenschaften der Lösungen einer Klasse von Funktionalgleichungen, Math. Ann. 103 (1930), no. 1, 532 (German). MR 1512635, DOI 10.1007/BF01455708
Kumiko Nishioka, Mahler functions and transcendence, Lecture Notes in Mathematics, vol. 1631, Springer-Verlag, Berlin, 1996. MR 1439966, DOI 10.1007/BFb0093672
F. Pellarin, An introduction to Mahler’s method for transcendence and algebraic independence, $t$-motives: Hodge structures, transcendence and other motivic aspects (G. Boeckle, D. Goss, U. Hartl, and M. Papanikolas, eds.), European Mathematical Society, 2016, 47 pages. To appear. Proceedings of BIRS, Banff, Canada, 2009. http://arxiv.org/abs/1005.1216.
J. Roques, On the local structure of Mahler modules, https://www-fourier.ujf-grenoble.fr/~jroques/OTLSOMM.pdf, 2016.
Julien Roques, On the algebraic relations between Mahler functions, Trans. Amer. Math. Soc. 370 (2018), no. 1, 321–355. MR 3717982, DOI 10.1090/tran/6945
Joris van der Hoeven, Relax, but don’t be too lazy, J. Symbolic Comput. 34 (2002), no. 6, 479–542. MR 1943041, DOI 10.1006/jsco.2002.0562
Robert J. Walker, Algebraic curves, Springer-Verlag, New York-Heidelberg, 1978. Reprint of the 1950 edition. MR 513824