Georgi Guninski on Mon, 12 May 2014 14:38:21 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Heuristic that might speed some thue equations with no solutions


I am not good at theory, but this appears plausible to me.

Suppose you want to solve 
thue(f(x),A) [1]
where $f(x)$ is irreducible.

Let $K$ be the number field with defining polynomial
$f(x)$. Every solution to [1] $u,v$ satisfies 
norm(v x- u)=A.

If $A$ is not an integer norm in $K$, [1] has no solution.
bnfisintnorm() appears significantly faster than thue().

Is it sound first to check bnfisintnorm() and
if it fails to not bother with thue(), assuming
f(x) is (monic) irreducible?

Example:

? a=20^30+3;K=bnfinit(x^4+1);a%4
%30 = 3
? bnfisintnorm(K,a)
%31 = [] \\ fast
? th=thueinit(K.pol);
? \g 3
   debug = 3
? thue(th,a)
* Checking for small solutions <= 8095430811