Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-6842 (online) ISSN 0025-5718 (print)

The 2020 MCQ for Mathematics of Computation is 1.98.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Computing solutions of linear Mahler equations
HTML articles powered by AMS MathViewer

by Frédéric Chyzak, Thomas Dreyfus, Philippe Dumas and Marc Mezzarobba PDF
Math. Comp. 87 (2018), 2977-3021 Request permission

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.
References
Similar Articles
  • Retrieve articles in Mathematics of Computation with MSC (2010): 39A06, 33F10, 68W30
  • Retrieve articles in all journals with MSC (2010): 39A06, 33F10, 68W30
Additional Information
  • Frédéric Chyzak
  • Affiliation: INRIA, Université Paris-Saclay, Palaiseau, France
  • Email: frederic.chyzak@inria.fr
  • Thomas Dreyfus
  • Affiliation: CNRS, Institut de Recherche Mathématique Avancée, UMR 7501, Université de Strasbourg, 7 rue René Descartes 67084 Strasbourg, France
  • MR Author ID: 1051219
  • ORCID: 0000-0003-1459-8456
  • Email: dreyfus@math.unistra.fr
  • Philippe Dumas
  • Affiliation: INRIA, Université Paris-Saclay, Palaiseau, France
  • MR Author ID: 342673
  • Email: philippe.dumas@inria.fr
  • Marc Mezzarobba
  • Affiliation: Sorbonne Université, CNRS, Laboratoire d’Informatique de Paris 6, LIP6, F-75005 Paris, France
  • MR Author ID: 904789
  • Email: marc@mezzarobba.net
  • Received by editor(s): January 26, 2017
  • Published electronically: July 2, 2018
  • Additional Notes: This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme under the Grant Agreement No 648132.
    The fourth author was supported in part by ANR grant ANR-14-CE25-0018-01 (FastRelax)
  • © Copyright 2018 American Mathematical Society
  • Journal: Math. Comp. 87 (2018), 2977-3021
  • MSC (2010): Primary 39A06; Secondary 33F10, 68W30
  • DOI: https://doi.org/10.1090/mcom/3359
  • MathSciNet review: 3834695