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

 Heuristic that might speed some thue equations with no solutions

• To: pari-dev@pari.math.u-bordeaux.fr
• Subject: Heuristic that might speed some thue equations with no solutions
• From: Georgi Guninski <guninski@guninski.com>
• Date: Mon, 12 May 2014 15:38:14 +0300
• Delivery-date: Mon, 12 May 2014 14:38:21 +0200
• User-agent: Mutt/1.5.20 (2009-06-14)

```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

```