Computing solutions of linear Mahler equations

DOI10.1090/MCOM/3359MaRDI QIDQ3177728zbMATH OpenOpenAlexFDO

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

Publication date 1 August 2018

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

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 of special functions (Gosper and Zeilberger algorithms, etc.) (33F10) Linear difference equations (39A06) Symbolic computation and algebraic computation (68W30)

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.

Recommendations

• Computing hypergeometric solutions of linear recurrence equations
• SOLVING LINEAR EQUATIONS IN L-FUNCTIONS
• scientific article; zbMATH DE number 3994892
• scientific article; zbMATH DE number 167889
• Computing rational solutions of linear matrix inequalities
• scientific article; zbMATH DE number 1354983
• On the numerical solving of complex linear systems
• scientific article; zbMATH DE number 4127318
• Computational Methods for Linear Matrix Equations
• scientific article; zbMATH DE number 7746914

Cites work

• A generalization of the fast LUP matrix decomposition algorithm and applications
• Complexity of factoring and calculating the GCD of linear ordinary differential operators
• Ensembles presque périodiques \(k\)-reconnaissables. (Almost periodic \(k\)-recognizable sets)
• Fast computation of special resultants
• scientific article; zbMATH DE number 193017 (Why is no real title available?)
• scientific article; zbMATH DE number 3620034 (Why is no real title available?)
• scientific article; zbMATH DE number 3070524 (Why is no real title available?)
• Mahler functions and transcendence
• Mahler method: linear relations, transcendence and applications to automatic numbers
• On solutions of linear ordinary difference equations in their coefficient field
• On the algebraic relations between Mahler functions
• Rational solutions of linear difference and \(q\)-differential equations with polynomial coefficients
• Rational solutions of linear differential and difference equations with polynomial coefficients
• Relax, but don't be too lazy
• Suites algébriques, automates et substitutions
• Transcendence tests for Mahler functions
• Two Notes on Formal Power Series

Cited in

(12)

• Mahler's method
• scientific article; zbMATH DE number 1740043 (Why is no real title available?)
• An algorithm to recognize regular singular Mahler systems
• Frobenius method for Mahler equations
• Hahn series and Mahler equations: algorithmic aspects
• Radial behavior of Mahler functions
• On the existence and convergence of formal power series solutions of nonlinear Mahler equations
• A purity theorem for Mahler equations
• On the computation of the difference Galois groups of order 3 equations
• First-order factors of linear Mahler operators
• Twisted Mahler discrete residues
• Regular singular Mahler equations and Newton polygons

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)