{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,23]],"date-time":"2026-07-23T01:05:35Z","timestamp":1784768735315,"version":"3.55.0"},"reference-count":30,"publisher":"American Mathematical Society (AMS)","issue":"358","license":[{"start":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T00:00:00Z","timestamp":1773187200000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"funder":[{"DOI":"10.13039\/501100004618","name":"Universit\u00e9 de Bourgogne","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004618","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>\n                    Consider a square free polynomial\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper P element-of double-struck upper Q left-bracket x right-bracket\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>P<\/mml:mi>\n                            <mml:mo>\n                              \u2208\n                              \n                            <\/mml:mo>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:mi mathvariant=\"double-struck\">Q<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mo stretchy=\"false\">[<\/mml:mo>\n                            <mml:mi>x<\/mml:mi>\n                            <mml:mo stretchy=\"false\">]<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">P\\in \\mathbb {Q}[x]<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    of degree\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"n\">\n                        <mml:semantics>\n                          <mml:mi>n<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">n<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    and whose coefficients have binary length at most\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"h\">\n                        <mml:semantics>\n                          <mml:mi>h<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">h<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    . We present an algorithm computing the linear relations with coefficients in\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"double-struck upper Q\">\n                        <mml:semantics>\n                          <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                            <mml:mi mathvariant=\"double-struck\">Q<\/mml:mi>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">\\mathbb {Q}<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    between the roots of\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper P\">\n                        <mml:semantics>\n                          <mml:mi>P<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">P<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    , in polynomial time in\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"n comma h\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>,<\/mml:mo>\n                            <mml:mi>h<\/mml:mi>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">n,h<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    . We also present an algorithm for computing multiplicative relations between the roots of\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper P\">\n                        <mml:semantics>\n                          <mml:mi>P<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">P<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    , also running in polynomial time in\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"n comma h\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>,<\/mml:mo>\n                            <mml:mi>h<\/mml:mi>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">n,h<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    . Previous methods were running in polynomial time in\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"n factorial\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>!<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">n!<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    . Alongside, we present how to build polynomials having many relations between their roots (additive or multiplicative). Finally, we present several applications: the elementary computation of hyperelliptic integrals, the Galois group computation of differential and difference equation with constant coefficients, and the computation of torsion number for\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper C squared\">\n                        <mml:semantics>\n                          <mml:msup>\n                            <mml:mi>C<\/mml:mi>\n                            <mml:mn>2<\/mml:mn>\n                          <\/mml:msup>\n                          <mml:annotation encoding=\"application\/x-tex\">C^2<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    finite difference equations.\n                  <\/p>","DOI":"10.1090\/mcom\/4081","type":"journal-article","created":{"date-parts":[[2025,3,11]],"date-time":"2025-03-11T11:12:44Z","timestamp":1741691564000},"page":"999-1022","source":"Crossref","is-referenced-by-count":3,"title":["Computing linear relations between polynomial roots"],"prefix":"10.1090","volume":"95","author":[{"given":"Thierry","family":"Combot","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"14","published-online":{"date-parts":[[2025,3,11]]},"reference":[{"issue":"2","key":"1","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1006\/jagm.1993.1038","article-title":"Factor refinement","volume":"15","author":"Bach, Eric","year":"1993","journal-title":"J. Algorithms","ISSN":"https:\/\/id.crossref.org\/issn\/0196-6774","issn-type":"print"},{"issue":"3","key":"2","doi-asserted-by":"publisher","first-page":"827","DOI":"10.1006\/jabr.1995.1330","article-title":"Polynomial relations between polynomial roots","volume":"177","author":"Baron, Gerd","year":"1995","journal-title":"J. Algebra","ISSN":"https:\/\/id.crossref.org\/issn\/0021-8693","issn-type":"print"},{"key":"3","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/j.jsc.2017.03.009","article-title":"A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration","volume":"86","author":"Becker, Ruben","year":"2018","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"key":"4","isbn-type":"print","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1145\/3452143.3465540","article-title":"Elementary integration of superelliptic integrals","author":"Combot, Thierry","year":"[2021] \\copyright2021","ISBN":"https:\/\/id.crossref.org\/isbn\/9781450383820"},{"issue":"3","key":"5","doi-asserted-by":"publisher","first-page":"293","DOI":"10.4064\/aa-82-3-293-302","article-title":"Polynomials with nontrivial relations between their roots","volume":"82","author":"Dixon, John D.","year":"1997","journal-title":"Acta Arith.","ISSN":"https:\/\/id.crossref.org\/issn\/0065-1036","issn-type":"print"},{"key":"6","unstructured":"T. Dokchitser, Transitive groups of degree up to 15, \\url{https:\/\/people.maths.bris.ac.uk\/ matyd\/GroupNames\/T15.html}, 2024."},{"key":"7","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1112\/S1461157000001406","article-title":"Finding integral linear dependencies of algebraic numbers and algebraic Lie algebras","volume":"10","author":"Fieker, Claus","year":"2007","journal-title":"LMS J. Comput. Math."},{"key":"8","unstructured":"G. Ge, Algorithms Related to Multiplicative Representations, University of California, Berkeley, 1993."},{"key":"9","doi-asserted-by":"crossref","unstructured":"Guoqiang Ge, Testing Equalities of Multiplicative Representations in Polynomial Time, Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science, IEEE, 1993, pp. 422\u2013426.","DOI":"10.1109\/SFCS.1993.366845"},{"issue":"1","key":"10","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/BF01312446","article-title":"Linear dependence of zeros of polynomials and construction of primitive elements","volume":"39","author":"Girstmair, Kurt","year":"1982","journal-title":"Manuscripta Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-2611","issn-type":"print"},{"issue":"1","key":"11","doi-asserted-by":"publisher","first-page":"53","DOI":"10.4064\/aa-89-1-53-96","article-title":"Linear relations between roots of polynomials","volume":"89","author":"Girstmair, Kurt","year":"1999","journal-title":"Acta Arith.","ISSN":"https:\/\/id.crossref.org\/issn\/0065-1036","issn-type":"print"},{"key":"12","series-title":"Mathematical Sciences Research Institute Publications","isbn-type":"print","volume-title":"Generic polynomials","volume":"45","author":"Jensen, Christian U.","year":"2002","ISBN":"https:\/\/id.crossref.org\/isbn\/0521819989"},{"key":"13","unstructured":"M. Kauers, Algorithms for nonlinear higher order difference equations, Thesis Ph.D.\u2013Johannes-Kepler University Linz, 2005."},{"key":"14","isbn-type":"print","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1145\/3597066.3597070","article-title":"Order bounds for \ud835\udc36\u00b2-finite sequences","author":"Kauers, Manuel","year":"[2023] \\copyright2023","ISBN":"https:\/\/id.crossref.org\/isbn\/9798400700392"},{"key":"15","isbn-type":"print","volume-title":"Difference equations","author":"Kelley, Walter G.","year":"2001","ISBN":"https:\/\/id.crossref.org\/isbn\/012403330X","edition":"2"},{"issue":"4","key":"16","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","article-title":"Factoring polynomials with rational coefficients","volume":"261","author":"Lenstra, A. K.","year":"1982","journal-title":"Math. Ann.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5831","issn-type":"print"},{"issue":"2","key":"17","doi-asserted-by":"publisher","first-page":"630","DOI":"10.1006\/jabr.1998.7481","article-title":"On the maximum order of torsion elements in \ud835\udc3a\ud835\udc3f(\ud835\udc5b,\ud835\udc4d) and \ud835\udc34\ud835\udc62\ud835\udc61(\ud835\udc39_{\ud835\udc5b})","volume":"208","author":"Levitt, Gilbert","year":"1998","journal-title":"J. Algebra","ISSN":"https:\/\/id.crossref.org\/issn\/0021-8693","issn-type":"print"},{"key":"18","isbn-type":"print","first-page":"248","article-title":"Linear relations on algebraic groups","author":"Masser, D. W.","year":"1988","ISBN":"https:\/\/id.crossref.org\/isbn\/0521335450"},{"key":"19","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1016\/j.jsc.2014.02.001","article-title":"From approximate factorization to root isolation with application to cylindrical algebraic decomposition","volume":"66","author":"Mehlhorn, Kurt","year":"2015","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"key":"20","isbn-type":"print","first-page":"259","article-title":"Some useful bounds","author":"Mignotte, M.","year":"1983","ISBN":"https:\/\/id.crossref.org\/isbn\/321181776X"},{"key":"21","isbn-type":"print","volume-title":"Factoring univariate polynomials over the rationals","author":"Novocin, Andrew","year":"2008","ISBN":"https:\/\/id.crossref.org\/isbn\/9780549730866"},{"key":"22","unstructured":"S. Orange, G. Renault, and A. Valibouze, A new tools for computing galois groups and galois ideals, [Research Report] lip6.2006.002, LIP6, 2005."},{"issue":"2","key":"23","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0022-314X(86)90094-6","article-title":"Additive and multiplicative relations connecting conjugate algebraic numbers","volume":"23","author":"Smyth, C. J.","year":"1986","journal-title":"J. Number Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0022-314X","issn-type":"print"},{"key":"24","unstructured":"B. M. Trager, Integration of algebraic functions, Thesis Ph.D.\u2013Massachusetts Institute of Technology, 1984."},{"issue":"1","key":"25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4064\/aa131-1-1","article-title":"Sur les relations entre les racines d\u2019un polyn\u00f4me","volume":"131","author":"Valibouze, Annick","year":"2008","journal-title":"Acta Arith.","ISSN":"https:\/\/id.crossref.org\/issn\/0065-1036","issn-type":"print"},{"issue":"4","key":"26","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1016\/j.jsc.2010.10.013","article-title":"Gr\u00f6bner basis of the alternating Galoisian ideal","volume":"46","author":"Valibouze, Annick","year":"2011","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"key":"27","series-title":"Lecture Notes in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0096118","volume-title":"Galois theory of difference equations","volume":"1666","author":"van der Put, Marius","year":"1997","ISBN":"https:\/\/id.crossref.org\/isbn\/3540632433"},{"key":"28","series-title":"Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-55750-7","volume-title":"Galois theory of linear differential equations","volume":"328","author":"van der Put, Marius","year":"2003","ISBN":"https:\/\/id.crossref.org\/isbn\/3540442286"},{"key":"29","isbn-type":"print","volume-title":"Fundamental problems of algorithmic algebra","author":"Yap, Chee Keng","year":"2000","ISBN":"https:\/\/id.crossref.org\/isbn\/0195125169"},{"key":"30","doi-asserted-by":"crossref","unstructured":"T. Zheng, A fast algorithm for computing multiplicative relations between the roots of a generic polynomial, Journal of Symbolic Computation, 104 (2019), 381-401.","DOI":"10.1016\/j.jsc.2020.08.001"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.ams.org\/mcom\/2026-95-358\/S0025-5718-2025-04081-X\/S0025-5718-2025-04081-X.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T06:00:23Z","timestamp":1776837623000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2026-95-358\/S0025-5718-2025-04081-X\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,11]]},"references-count":30,"journal-issue":{"issue":"358","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["S0025-5718-2025-04081-X"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/4081","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":[[2025,3,11]]}}}