Karim Belabas on Sat, 10 May 2014 19:09:29 +0200

 Re: Reducible thue() might be missing solutions

```* 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);
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]
`

```