Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Computing solutions of linear Mahler equations

Authors: Frédéric Chyzak, Thomas Dreyfus, Philippe Dumas and Marc Mezzarobba
Journal: Math. Comp. 87 (2018), 2977-3021
MSC (2010): Primary 39A06; Secondary 33F10, 68W30
Published electronically: July 2, 2018
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 39A06, 33F10, 68W30

Retrieve articles in all journals with MSC (2010): 39A06, 33F10, 68W30

Additional Information

Frédéric Chyzak
Affiliation: INRIA, Université Paris-Saclay, Palaiseau, France

Thomas Dreyfus
Affiliation: CNRS, Institut de Recherche Mathématique Avancée, UMR 7501, Université de Strasbourg, 7 rue René Descartes 67084 Strasbourg, France

Philippe Dumas
Affiliation: INRIA, Université Paris-Saclay, Palaiseau, France

Marc Mezzarobba
Affiliation: Sorbonne Université, CNRS, Laboratoire d’Informatique de Paris 6, LIP6, F-75005 Paris, France

Received by editor(s): January 26, 2017
Published electronically: July 2, 2018
Additional Notes: This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme under the Grant Agreement No 648132.
The fourth author was supported in part by ANR grant ANR-14-CE25-0018-01 (FastRelax)
Article copyright: © Copyright 2018 American Mathematical Society

American Mathematical Society