Computing solutions of linear Mahler equations

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.
Document type :
Journal articles
Liste complète des métadonnées

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/hal-01418653
Contributor : Frédéric Chyzak <>
Submitted on : Tuesday, April 10, 2018 - 3:02:59 PM
Last modification on : Wednesday, March 27, 2019 - 1:34:23 AM

File

mahlersols.pdf
Files produced by the author(s)

Identifiers

Citation

Frédéric Chyzak, Thomas Dreyfus, Philippe Dumas, Marc Mezzarobba. Computing solutions of linear Mahler equations. Mathematics of Computation, American Mathematical Society, 2018, 87, pp.2977-3021. ⟨https://www.ams.org/journals/mcom/2018-87-314/S0025-5718-2018-03359-2/⟩. ⟨10.1090/mcom/3359⟩. ⟨hal-01418653v2⟩

Share

Metrics

Record views

224

Files downloads

147