Karim Belabas on Mon, 12 May 2014 13:11:33 +0200


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

Re: More thue() troubles in master/2.5.5 after the roots patch


* Georgi Guninski [2014-05-12 10:19]:
> On Sun, May 11, 2014 at 02:25:41PM +0200, Karim Belabas wrote:
> > * Georgi Guninski [2014-05-11 13:00]:
> > > This appears an ``issue'' to me on today master
> > > and 2.5.5
> > > 
> > > ? F=(2*x^3+2*y^3)^3*(3*x+3*y)^3;th=thueinit(subst(F,y,1),1);so=thue(th,subst(subst(F,x,2),y,1))
> > > %23 = [[2, 1], [1, 2]]
> > > ? subst(subst(F,x,-2),y,-1)
> > > %24 = 4251528
> > > ? subst(subst(F,x,2),y,1)
> > > %25 = 4251528
> > > ? %25==%24
> > > %26 = 1
> > > 
> > > [-2,-1] and the like are missing IMHO.
> > 
> > They are. :-(
> > 
> > In fact thue(f^e*g,...), (f,g)=1, e even, where f irreducible and
> >   deg f <= min{deg P : P | g}
> > missed solutions such that f < 0.
> > 
> > Fixed in master.
> >
> 
> Are you sure my bug is fixed in master?

It was, but then I broke it again yesterday in this commit:

commit 80632773a52cb95030feab8434f79a86cd3e827f
Author: Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr>
Date:   Sun May 11 17:21:20 2014 +0200

    thue(reducible cases): don't reduce to monic case
    
    Wasteful since can introduce many more divisor pairs to check. E.g.
      thue(pol = (10946*x-6765)*(x^2+x-1), 1)
    Rewriting as POL(x) = C*pol(x/L), with POL monic the RHS becomes 119814916
    with 27 divisors; and then we have to remove solutions with L \nmid x.
    
    Sticking  with pol, we have only 1 divisor, and all solutions are good.

The implementation failed in the non-primitive case because of a typo
(C should have been 1/C). Now fixed again. :-)

> Built it today and got worse:
> 
> ? F=(2*x^3+2*y^3)^3*(3*x+3*y)^3;th=thueinit(subst(F,y,1),1);so=thue(th,subst(subst(F,x,2),y,1))
> %1 = []

The original code treated only the rock-bottom hard case: F monic, irreducible
of degree > 2; this one has been well-tested and should now be stable.

All the current problems come from "trivial" cases, for which the
test-suite is obviously not sufficient, even though it exercises each
line of code (though not yet all code branches). I am adding every bug report
you submit to the 'thue' test-suite, so keep them coming !

N.B: I had added your original example but in a simplified form which
was enough to trigger the original bug. Unfortunately, it wasn't enough
to catch the *new* one I introduced yesterday.

N.B2: I'm currently working on one final improvement: allow quadratic
imaginary equations (currently we fail for F^e, if degree F <= 2), so that we
can treat uniformly all cases where we have finitely many solutions.

I may add code to handle your original example P(x^e, y^e) = RHS
(x^4+y^4 = RHS in your case) as well. It's all "trivial" and better done
on the user's side (simplify mathematically your equation first), but it's
nicer to users to handle "trivial" improvements... (There's another can of
worms we can get into: try to find local obstructions to the existence of
solutions.)

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux1.fr/~kbelabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux1.fr/  [PARI/GP]
`