# 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.
Type de document :
Article dans une revue
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〉
Domaine :

Littérature citée [20 références]

https://hal.inria.fr/hal-01418653
Contributeur : Frédéric Chyzak <>
Soumis le : mardi 10 avril 2018 - 15:02:59
Dernière modification le : samedi 20 octobre 2018 - 01:16:03

### Fichier

mahlersols.pdf
Fichiers produits par l'(les) auteur(s)

### 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〉

### Métriques

Consultations de la notice

## 182

Téléchargements de fichiers