{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T20:44:32Z","timestamp":1776804272538,"version":"3.51.2"},"reference-count":23,"publisher":"American Mathematical Society (AMS)","issue":"314","license":[{"start":{"date-parts":[[2019,7,2]],"date-time":"2019-07-02T00:00:00Z","timestamp":1562025600000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-14-CE25-0018-01"],"award-info":[{"award-number":["ANR-14-CE25-0018-01"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>\n                    Mahler equations relate evaluations of the same function\u00a0\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"f\">\n                        <mml:semantics>\n                          <mml:mi>f<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">f<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    at iterated\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"b\">\n                        <mml:semantics>\n                          <mml:mi>b<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">b<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    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.\n                  <\/p>","DOI":"10.1090\/mcom\/3359","type":"journal-article","created":{"date-parts":[[2018,2,21]],"date-time":"2018-02-21T09:48:56Z","timestamp":1519206536000},"page":"2977-3021","source":"Crossref","is-referenced-by-count":12,"title":["Computing solutions of linear Mahler equations"],"prefix":"10.1090","volume":"87","author":[{"given":"Fr\u00e9d\u00e9ric","family":"Chyzak","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Dreyfus","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Philippe","family":"Dumas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marc","family":"Mezzarobba","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2018,7,2]]},"reference":[{"key":"1","doi-asserted-by":"publisher","first-page":"903","DOI":"10.2307\/2033558","article-title":"Two notes on formal power series","volume":"7","author":"Abhyankar, Shreeram","year":"1956","journal-title":"Proc. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9939","issn-type":"print"},{"issue":"11","key":"2","doi-asserted-by":"publisher","first-page":"1611","DOI":"10.1016\/S0041-5553(89)80002-3","article-title":"Rational solutions of linear differential and difference equations with polynomial coefficients","volume":"29","author":"Abramov, S. A.","year":"1989","journal-title":"Zh. Vychisl. Mat. i Mat. Fiz.","ISSN":"https:\/\/id.crossref.org\/issn\/0044-4669","issn-type":"print"},{"issue":"6","key":"3","first-page":"3","article-title":"Rational solutions of linear difference and \ud835\udc5e-difference equations with polynomial coefficients","author":"Abramov, S. A.","year":"1995","journal-title":"Programmirovanie","ISSN":"https:\/\/id.crossref.org\/issn\/0132-3474","issn-type":"print"},{"issue":"1","key":"4","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1112\/plms.12038","article-title":"M\u00e9thode de Mahler: relations lin\u00e9aires, transcendance et applications aux nombres automatiques","volume":"115","author":"Adamczewski, Boris","year":"2017","journal-title":"Proc. Lond. Math. Soc. (3)","ISSN":"https:\/\/id.crossref.org\/issn\/0024-6115","issn-type":"print"},{"issue":"1","key":"5","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1112\/plms.12038","article-title":"M\u00e9thode de Mahler: relations lin\u00e9aires, transcendance et applications aux nombres automatiques","volume":"115","author":"Adamczewski, Boris","year":"2017","journal-title":"Proc. Lond. Math. Soc. (3)","ISSN":"https:\/\/id.crossref.org\/issn\/0024-6115","issn-type":"print"},{"issue":"3","key":"6","doi-asserted-by":"publisher","first-page":"1061","DOI":"10.1090\/proc\/13297","article-title":"Transcendence tests for Mahler functions","volume":"145","author":"Bell, Jason P.","year":"2017","journal-title":"Proc. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9939","issn-type":"print"},{"issue":"1","key":"7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jsc.2005.07.001","article-title":"Fast computation of special resultants","volume":"41","author":"Bostan, Alin","year":"2006","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"issue":"6","key":"8","doi-asserted-by":"publisher","first-page":"841","DOI":"10.1006\/jsco.2000.0368","article-title":"On solutions of linear ordinary difference equations in their coefficient field","volume":"29","author":"Bronstein, Manuel","year":"2000","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"key":"9","series-title":"Mathematical Surveys, No. VI","doi-asserted-by":"crossref","DOI":"10.1090\/surv\/006","volume-title":"Introduction to the Theory of Algebraic Functions of One Variable","author":"Chevalley, Claude","year":"1951"},{"issue":"1","key":"10","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0304-3975(79)90011-2","article-title":"Ensembles presque periodiques \ud835\udc58-reconnaissables","volume":"9","author":"Christol, Gilles","year":"1979","journal-title":"Theoret. Comput. Sci.","ISSN":"https:\/\/id.crossref.org\/issn\/0304-3975","issn-type":"print"},{"issue":"4","key":"11","doi-asserted-by":"crossref","first-page":"401","DOI":"10.24033\/bsmf.1926","article-title":"Suites alg\u00e9briques, automates et substitutions","volume":"108","author":"Christol, G.","year":"1980","journal-title":"Bull. Soc. Math. France","ISSN":"https:\/\/id.crossref.org\/issn\/0037-9484","issn-type":"print"},{"key":"12","unstructured":"T. Dreyfus, Charlotte Hardouin, and Julien Roques, Hypertranscendance of solutions of Mahler equations, J. Eur. Math. Soc. (2015), 26 pages. To appear. \\url{http:\/\/arxiv.org\/abs\/1507.03361}."},{"key":"13","isbn-type":"print","volume-title":"R\\'{e}currences mahl\\'{e}riennes, suites automatiques, \\'{e}tudes asymptotiques","author":"Dumas, Philippe","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/2726108172"},{"issue":"1","key":"14","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1016\/S0747-7171(08)80034-X","article-title":"Complexity of factoring and calculating the GCD of linear ordinary differential operators","volume":"10","author":"Grigor\u2032ev, D. Yu.","year":"1990","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"key":"15","series-title":"Wiley Classics Library","isbn-type":"print","volume-title":"Applied and computational complex analysis. Vol. 1","author":"Henrici, Peter","year":"1988","ISBN":"https:\/\/id.crossref.org\/isbn\/0471608416"},{"issue":"1","key":"16","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/0196-6774(82)90007-4","article-title":"A generalization of the fast LUP matrix decomposition algorithm and applications","volume":"3","author":"Ibarra, Oscar H.","year":"1982","journal-title":"J. Algorithms","ISSN":"https:\/\/id.crossref.org\/issn\/0196-6774","issn-type":"print"},{"issue":"1","key":"17","doi-asserted-by":"publisher","first-page":"532","DOI":"10.1007\/BF01455708","article-title":"Berichtigung zu der Arbeit von K. Mahler: Arithmetische Eigenschaften der L\u00f6sungen einer Klasse von Funktionalgleichungen","volume":"103","author":"Mahler, K.","year":"1930","journal-title":"Math. Ann.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5831","issn-type":"print"},{"key":"18","series-title":"Lecture Notes in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0093672","volume-title":"Mahler functions and transcendence","volume":"1631","author":"Nishioka, Kumiko","year":"1996","ISBN":"https:\/\/id.crossref.org\/isbn\/3540614729"},{"key":"19","unstructured":"F. Pellarin, An introduction to Mahler\u2019s method for transcendence and algebraic independence, \ud835\udc61-motives: Hodge structures, transcendence and other motivic aspects (G. Boeckle, D. Goss, U. Hartl, and M. Papanikolas, eds.), European Mathematical Society, 2016, 47 pages. To appear. Proceedings of BIRS, Banff, Canada, 2009. \\url{http:\/\/arxiv.org\/abs\/1005.1216}."},{"key":"20","unstructured":"J. Roques, On the local structure of Mahler modules, \\url{https:\/\/www-fourier.ujf-grenoble.fr\/ jroques\/OTLSOMM.pdf}, 2016."},{"issue":"1","key":"21","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1090\/tran\/6945","article-title":"On the algebraic relations between Mahler functions","volume":"370","author":"Roques, Julien","year":"2018","journal-title":"Trans. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9947","issn-type":"print"},{"issue":"6","key":"22","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1006\/jsco.2002.0562","article-title":"Relax, but don\u2019t be too lazy","volume":"34","author":"van der Hoeven, Joris","year":"2002","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"key":"23","isbn-type":"print","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-6323-4","volume-title":"Algebraic curves","author":"Walker, Robert J.","year":"1978","ISBN":"https:\/\/id.crossref.org\/isbn\/0387903615"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.ams.org\/mcom\/2018-87-314\/S0025-5718-2018-03359-2\/mcom3359_AM.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"http:\/\/www.ams.org\/mcom\/2018-87-314\/S0025-5718-2018-03359-2\/S0025-5718-2018-03359-2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2018-87-314\/S0025-5718-2018-03359-2\/S0025-5718-2018-03359-2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T19:49:41Z","timestamp":1776800981000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2018-87-314\/S0025-5718-2018-03359-2\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,2]]},"references-count":23,"journal-issue":{"issue":"314","published-print":{"date-parts":[[2018,11]]}},"alternative-id":["S0025-5718-2018-03359-2"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/3359","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2018,7,2]]}}}