Re: Reducible thue() might be missing solutions

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

* Georgi Guninski [2014-05-10 17:56]:
> On Sat, May 10, 2014 at 05:09:21PM +0200, Karim Belabas wrote:
> > * Karim Belabas [2014-05-10 16:20]:
> > 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...

In fact it required a leading coefficient exactly equal to -1.

> One man's bad luck is another man's good luck,
> especially for bugs ;)
> 
> What about 2.5.5, is it still supported?

No. You should upgrade to either 2.7.* (new stable branch) or to master.
master is preferred if you intend to go bug-hunting of course
(that would be nice :-)

1) Here's a minimal fix for 2.7.*

diff --git a/src/basemath/QX_factor.c b/src/basemath/QX_factor.c
index 87190dc..2efb912 100644
--- a/src/basemath/QX_factor.c
+++ b/src/basemath/QX_factor.c
@@ -807,9 +807,9 @@ DDF_roots(GEN A)
   { lc = NULL; lcpol = A; }
   else
   { lc = absi(lc); lcpol = ZX_Z_mul(A, lc); }
-  Ap = ZX_to_Flx(A, pp);
+  Ap = Flx_normalize(ZX_to_Flx(A, pp), pp);
   bound = root_bound(A);
-  if (lc) { Ap = Flx_normalize(Ap, pp); bound = mulii(lc, bound); }
+  if (lc) bound = mulii(lc, bound);
   e = logint(addiu(shifti(bound, 1), 1), p, &pe);
   pes2 = shifti(pe, -1);
   if (DEBUGLEVEL>2) timer_printf(&T, "Root bound");

> (it caught some of the roots unlike master).

2) 2.5.5 is *not* affected by the bug in nfrootsQ() we're talking about,
but it contains a few genuine bugs in thue() itself.

Here's a minimal fix *for the problem you originally reported* for 2.5.5
(there were a few other problems in 2.5.5:thue() : it doesn't support
non-monic polynomials, the final checks are much slower, and it leaked
"user variables")

diff --git a/src/modules/thue.c b/src/modules/thue.c
index 46176c9..a9ede7b 100644
--- a/src/modules/thue.c
+++ b/src/modules/thue.c
@@ -1103,7 +1103,7 @@ thue(GEN tnf, GEN rhs, GEN ne)
       ry = nfrootsQ(Rab);
       for (k = 1; k < lg(ry); k++)
         if (typ(gel(ry,k)) == t_INT) check_y(&S, P, POL, gel(ry,k), rhs);
-      if (!odd(e)) {
+      if (odd(e)) {
         Rab = gsubst(gsubst(R, va, negi(df)), vb, negi(dg));
         ry = nfrootsQ(Rab);
         for (k = 1; k < lg(ry); k++)


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