How difficult is it to solve a Thue equation?

DOI10.1007/3-540-61581-4_67MaRDI QIDQ4375625zbMATH OpenFDO

Publication date 11 October 1998

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-61581-4_67

complexity analysis higher degree equation Thue equations

Higher degree equations; Fermat's equation (11D41) Number-theoretic algorithms; complexity (11Y16) Computer solution of Diophantine equations (11Y50)

Review text

Let \(F\in \mathbb{Z} [x,y]\) be an irreducible binary form of degree \(n>3\). The equation \[ F(x,y)=m, \quad m\in \mathbb{Z}, \] in integers \(x\) and \(y\) is known as a Thue equation. It has been known since the beginning of this century that Thue equations have only finitely many solutions. But we had to wait until 1989 to see a practical algorithm, due to \textit{N. Tzanakis} and \textit{B. M. M. de Weger} [J. Number Theory 31, 99-132 (1989; Zbl 0657.10014)], that could actually solve such equations in general. Although this algorithm should work in almost every individual case, it is known to break down under certain (extreme) circumstances. Reasons could be that the value of \(m\) is too large, or that the regulator and/or class number of the corresponding number field is too large (see [\textit{R. J. Stroeker} and \textit{B. M. M. de Weger}, Exp. Math. 3, 209-220 (1994; Zbl 0824.11012)]), or -- and this is shown by the present author -- that two of the roots of \(F(x,1)=0\) are very close together. In the paper under review the author attempts to give a complexity analysis that addresses the problem as to how difficult it is in practice to find all solutions. Consider \(n\) fixed. Then the complexity is measured in terms of the sum of \(\log| m|\) and \(\log L(F)\), where \(L(F)= \sum^n_{i=1} | a_i|\) and the \(a_i\) are the coefficients of the monic polynomial \(F(x,1)\). The complexity results the author obtains -- they are too technical to reproduce here -- force him to concede, and I quote: So although solving Thue equations is now considered trivial we seem to be a long way off from a ``good algorithm. For the entire collection see [Zbl 0852.00023].

Recommendations

Cited in

(3)

This page was built for publication: How difficult is it to solve a Thue equation?

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