bug in factoring polynomial

[William Stein]

I hit this today when factoring a 3-division polynomial. NOTE that
there is no 2 in any denominator, but the poly is not monic:

sage: R.<x> = QQ[]; f = 3*x^4 + x^3 + 3*x^2 + 3*x; f.factor_padic(2)
---------------------------------------------------------------------------
PariError Traceback (most recent call
last)
<ipython-input-7-b9d5451b8917> in <module>()
----> 1 R = QQ['x']; (x,) = R._first_ngens(1); f =
Integer(3)*x**Integer(4) + x**Integer(3) + Integer(3)*x**Integer(2)
+ Integer(3)*x; f.factor_padic(Integer(2))

/usr/local/sage/sage-5.8/local/lib/python2.7/site-packages/sage/rings/polynomial/polynomial_rational_flint.so
in sage.
rings.polynomial.polynomial_rational_flint.Polynomial_rational_flint.factor_padic
(sage/rings/polynomial/polynomial_ra
tional_flint.cpp:13674)()

/usr/local/sage/sage-5.8/local/lib/python2.7/site-packages/sage/rings/polynomial/padics/polynomial_padic_capped_relati
ve_dense.pyc in factor(self)
1081 R = ZpCA(base.prime(), prec = m)
1082 S = PolynomialRing(R, self.parent().variable_name())
-> 1083 F = S(self).factor()
1084 return Factorization([(self.parent()(a), b) for (a, b)
in F], base(F.unit()))
1085

/usr/local/sage/sage-5.8/local/lib/python2.7/site-packages/sage/rings/polynomial/padics/polynomial_padic_flat.pyc
in f
actor(self, absprec)
135 if absprec <= 0:
136 raise ValueError, "absprec must be positive"
--> 137 G =
self._pari_().factorpadic(self.base_ring().prime(), absprec)
138 pols = G[0]
139 exps = G[1]

/usr/local/sage/sage-5.8/local/lib/python2.7/site-packages/sage/libs/pari/gen.so
in sage.libs.pari.gen._pari_trap (sag
e/libs/pari/gen.c:55289)()

PariError: division by zero (27)
sage:

--
William Stein
Professor of Mathematics
University of Washington
http://wstein.org

[Rob Harron]

Note the following interesting behaviour in gp (or rather sage's gp console):

? f = (3 + O(2^20))*x^4 +(1+ O(2^20))*x^3 + (3 + O(2^20))*x^2 + (3 + O(2^20))*x

%6 = (1 + 2 + O(2^20))*x^4 + (1 + O(2^20))*x^3 + (1 + 2 + O(2^20))*x^2 + (1 + 2 + O(2^20))*x

? factor(f)

  ***   at top-level: factor(f)

  ***                 ^---------

  *** factor: division by zero

Now, divide by 3:

? factor(f/3)

%7 = 

[(1 + O(2^20))*x 1]

[(1 + O(2^20))*x^3 + (1 + 2 + 2^3 + 2^5 + 2^7 + 2^9 + 2^11 + 2^13 + 2^15 + 2^17 + 2^19 + O(2^20))*x^2 + (1 + O(2^20))*x + (1 + O(2^20)) 1]

Or instead, remove the factor of x:

? factor(f/x)

%8 = 

[(1 + 2 + O(2^20))*x^3 + (1 + O(2^20))*x^2 + (1 + 2 + O(2^20))*x + (1 + 2 + O(2^20)) 1]

But if we make the leading coefficient a 2:

? g = (2  + O(2^20))*x^4 +(1+ O(2^20))*x^3 + (3 + O(2^20))*x^2 + (3 + O(2^20))*x

%9 = (2 + O(2^20))*x^4 + (1 + O(2^20))*x^3 + (1 + 2 + O(2^20))*x^2 + (1 + 2 + O(2^20))*x

? factor(g)

  ***   at top-level: factor(g)

  ***                 ^---------

  *** factor: division by zero

? factor(g/2)

  ***   at top-level: factor(g/2)

  ***                 ^-----------

  *** factor: division by zero

But:

? factor(g/2/x)

%10 = 

[(2 + O(2^19))*x + (1 + 2 + 2^3 + 2^4 + 2^5 + 2^9 + 2^10 + 2^11 + 2^12 + 2^14 + 2^15 + 2^17 + O(2^19)) 1]

[(1 + O(2^19))*x^2 + (1 + 2 + 2^5 + 2^6 + 2^7 + 2^12 + 2^15 + 2^17 + O(2^19))*x + (1 + 2^3 + 2^4 + 2^6 + 2^7 + 2^13 + 2^14 + 2^15 + 2^17 + O(2^19)) 1]

and:

? factor(g/x)

%11 = 

[(2 + O(2^20))*x + (1 + 2 + 2^3 + 2^4 + 2^5 + 2^9 + 2^10 + 2^11 + 2^12 + 2^14 + 2^15 + 2^17 + 2^19 + O(2^20)) 1]

[(1 + O(2^20))*x^2 + (1 + 2 + 2^5 + 2^6 + 2^7 + 2^12 + 2^15 + 2^17 + O(2^20))*x + (1 + 2^3 + 2^4 + 2^6 + 2^7 + 2^13 + 2^14 + 2^15 + 2^17 + O(2^20)) 1]

So, there's some strange behaviour. It's not entirely about the "non-monicness".

Rob

[John Cremona]

THis should be reported to the pari list?

John

> --
> You received this message because you are subscribed to the Google Groups
> "sage-padics" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sage-padics...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>