Re: Reducible thue() might be missing solutions

[Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>]

* Karim Belabas [2014-05-10 16:20]:
> * Bill Allombert [2014-05-10 14:50]:
> > On Sat, May 10, 2014 at 01:31:14PM +0300, Georgi Guninski wrote:
> > > 2.5.5 on linux.
> > > 
> > > Reducible thue appears to miss solution,
> > > as shown:
> > > 
> > > ? A=10946;B=6765;F=(A*x-B*y)*(x^2+x*y-y^2);th=thueinit(subst(F,y,1),1);so=thue(th,1)
> > > %7 = [[4181, 6765], [10946, 17711]]
> > > ? so2=[2584, 4181];subst(subst(F,x,so2[1]),y,so2[2])
> > > %8 = 1
> > 
> > Over the years, a number of various bugs in thue has been reported.
> > Unfortunately, neither Karim nor I use it much, so it would be quite useful
> > if users of the function provided various families of test-cases.
> 
> As I reported, the bug has nothing to do with thue: it lies in nfrootsQ,
> which calls ZpX_liftfact with non-monic modular factors, contrary to the
> (documented) specifications of the latter.
> 
> My first fix was to replace obsolete code in nfrootsQ by a call to the
> new ZpX_roots, but ZpX_roots has the same bug. :-(
> 
> Am busy fixing the problem in a proper way...

The problem is now fixed in 'master':

(17:00) gp >  R = -y^2 - 24476*y + 119814917;
(17:00) gp > nfroots(,R)
%2 = [-28657, 4181]
(17:00) gp > thue((10946*x-6765)*(x^2+x-1), 1)
%3 = [[4181, 6765], [10946, 17711], [-17711, -28657], [2584, 4181]]

Am now investigating 2.7.* to backport a minimal fix (not using ZpX_roots).

Interesting enough, nfrootsQ *was* heavily tested: my initial replacement of
the (slightly broken) inlined root lifting code by (more broken) ZpX_roots
instantly created tens of regressions in the test-all suite.

It required a combination of non-monic polynomials (this we had in abundance,
e.g. from elltors testing), lots of rational roots compared to the degree
(this we had also, but not in combination with the first point) and a little
bad luck to exercise the bug...

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