Skip to Main content Skip to Navigation
New interface
Journal articles

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
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/hal-01418653
Contributor : Frédéric Chyzak Connect in order to contact the contributor
Submitted on : Tuesday, April 10, 2018 - 3:02:59 PM
Last modification on : Friday, August 5, 2022 - 9:26:02 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, 2018, 87, pp.2977-3021. ⟨10.1090/mcom/3359⟩. ⟨hal-01418653v2⟩

Share

Metrics

Record views

414

Files downloads

529