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.

Minor changes + New section 3.6

Cited by in corpus (7)

• Desingularization in the $q$-Weyl algebra
• Hahn series and Mahler equations: Algorithmic aspects
• Mahler discrete residues and summability for rational functions
• An algorithm to recognize regular singular Mahler systems
• Frobenius method for Mahler equations
• Twisted Mahler discrete residues
• First-order factors of linear Mahler operators