4
$\begingroup$

A Thue equation is a 2-variable homogeneous integer polynomial of degree at least 3. It's well-known that such equations have only finitely many solutions over the integers.

I'm trying to solve some simple Thue equations with Reduce but Mathematica is having trouble (no error, it just runs 'forever', or at least hours). Here's an example I pulled from a test suite:

toSym[P_] := Simplify[y^Exponent[P, x]*P /. x -> (x/y)]
thue[P_, a_Integer] := Simplify[Reduce[toSym[P] == a, {x, y}, Integers]]
thue[x^4 - 13*x^3 - 172*x^2 - 13*x + 1, 9]

I can broaden the scope, asking for rational solutions, in which case it gives

(((x > Root[-20736 - 78978339 #1^4 - 16932890540 #1^8 + 2346433600 #1^12 &, 2] || x < Root[-20736 - 78978339 #1^4 - 16932890540 #1^8 + 2346433600 #1^12 &, 1] || Root[-20736 - 78978339 #1^4 - 16932890540 #1^8 + 2346433600 #1^12 &, 1] < x < Root[-20736 - 78978339 #1^4 - 16932890540 #1^8 + 2346433600 #1^12 &, 2]) && (y == Root[-9 + x^4 - 13 x^3 #1 - 172 x^2 #1^2 - 13 x #1^3 + #1^4 &, 1] || y == Root[-9 + x^4 - 13 x^3 #1 - 172 x^2 #1^2 - 13 x #1^3 + #1^4 &, 2])) || ((x > Root[-20736 - 78978339 #1^4 - 16932890540 #1^8 + 2346433600 #1^12 &, 2] || x < Root[-20736 - 78978339 #1^4 - 16932890540 #1^8 + 2346433600 #1^12 &, 1]) && (y == Root[-9 + x^4 - 13 x^3 #1 - 172 x^2 #1^2 - 13 x #1^3 + #1^4 &, 3] || y == Root[-9 + x^4 - 13 x^3 #1 - 172 x^2 #1^2 - 13 x #1^3 + #1^4 &, 4]))) && (x | y) [Element] Rationals

but this isn't a solution -- it doesn't find whether the polynomials have the indicated rational roots or not. In any case I'm actually interested only in the integral solutions. Any ideas?

Edit: I see in Some Notes on Internal Implementation that Mathematica implements the Tzanakis-de Weger algorithm for Thue equations. Can we trace the behavior of the functions to see if this is being called internally with some sort of Unprotect scheme?

Edit 2: I don't think this should take so long to solve -- other systems can solve it in under a second. But I'd like to do this in Mathematica if possible. I suspect that the problem is that Mathematica is stuck on some aspect of the problem not being given to it in the desired format rather than a lack of ability on its part.

$\endgroup$
  • $\begingroup$ Reduce[x^4 - 172 x^2 y^2 + y^4 == 1, Integers] also drags, while replacing "172" with "5" runs quickly. $\endgroup$ – Kevin O'Bryant Jan 6 '18 at 4:57
  • $\begingroup$ Educated guess: The system is having difficulty computing a system of fundamental units: NumberFieldFundamentalUnits[ 1/4 (13 - Sqrt[865] - Sqrt[2 (509 - 13 Sqrt[865])])] is the problem spot. $\endgroup$ – Kevin O'Bryant Jan 6 '18 at 5:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.