Computing solutions of linear Mahler equations

DOI10.1090/MCOM/3359zbMATH Open1393.39002arXiv1612.05518OpenAlexW2583658760MaRDI QIDQ3177728FDOQ3177728

Frédéric Chyzak, Thomas Dreyfus, Philippe Dumas, Marc Mezzarobba

Publication date: 1 August 2018

Published in: Mathematics of Computation (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1612.05518

zbMATH Keywords

exponential blow-upMahler equationnumber-theoretic problem

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Linear difference equations (39A06) Symbolic computation of special functions (Gosper and Zeilberger algorithms, etc.) (33F10)

Cites Work

• Ensembles presque périodiques \(k\)-reconnaissables. (Almost periodic \(k\)-recognizable sets)
• Relax, but don't be too lazy
• Suites algébriques, automates et substitutions
• Title not available (Why is that?)
• Complexity of factoring and calculating the GCD of linear ordinary differential operators
• Mahler functions and transcendence
• Title not available (Why is that?)
• Title not available (Why is that?)
• Fast computation of special resultants
• On solutions of linear ordinary difference equations in their coefficient field
• A generalization of the fast LUP matrix decomposition algorithm and applications
• Rational solutions of linear differential and difference equations with polynomial coefficients
• Two Notes on Formal Power Series
• Transcendence tests for Mahler functions
• Rational solutions of linear difference and \(q\)-differential equations with polynomial coefficients
• On the algebraic relations between Mahler functions
• Méthode de Mahler : relations linéaires, transcendance et applications aux nombres automatiques

Cited In (7)

• An algorithm to recognize regular singular Mahler systems
• Hahn series and Mahler equations: algorithmic aspects
• Frobenius method for Mahler equations
• Radial behavior of Mahler functions
• Mahler's method
• On the existence and convergence of formal power series solutions of nonlinear Mahler equations
• Title not available (Why is that?)

   Recommendations

• Computing hypergeometric solutions of linear recurrence equations 👍 👎
• SOLVING LINEAR EQUATIONS IN L-FUNCTIONS 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Computing rational solutions of linear matrix inequalities 👍 👎
• Title not available (Why is that?) 👍 👎
• On the numerical solving of complex linear systems 👍 👎
• Title not available (Why is that?) 👍 👎
• Computational Methods for Linear Matrix Equations 👍 👎
• Title not available (Why is that?) 👍 👎

This page was built for publication: Computing solutions of linear Mahler equations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3177728)