Karim Belabas on Thu, 14 Nov 2013 17:35:23 +0100


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

Re: factorpadic() for non-squarefree polynomials


* Bill Allombert [2013-11-14 14:33]:
> On Thu, Nov 14, 2013 at 01:30:08PM +0100, Jeroen Demeyer wrote:
> > Hello pari-users,
> > 
> > The documentation for ??factorpadic states that the discriminant of
> > the polynomial much have p-adic valuation less than r. While I
> > understand where the condition comes from, does that mean that the
> > following is undefined behaviour:
> 
> I think the documentation is inaccurate. This function should return
> the Q_p factorization reduced to the precision p^r

Which it does. Except that "reduced to the precision p^r" is not precise
enough.

What the routine does is reduce to an absolute precision p^r
(basically add O(p^r) to all coefficients); I believe this is silly
and we should reduce to *relative* precision p^r  (multiply all
coefficients by 1 + O(p^r)). Trivial to do because that's what we do
internally using only ordinary integers, only the final output is
mangled to use t_PADICs.

> What matter is the precision of the polynomial itself.
> If the polynomial has inexact entries and its discriminant is 0 to the
> precision, then the Q_p factorization is not well determined (it depend
> on a lifting).

What we do exactly indeed depends on an initial "truncation/lifting"
from the input polynomial in Qp[X] (coeffs having varying accuracies) to Z[X].

This is *defined* as taking the p-adic primitive part (reducing to
content 1), then applying truncate() to individual coefficients.
We factor the resulting exact polynomial over Qp.

> On the other hand, if the polynomial has exact entries, there is no issue. 

As well, I'd advise to only input polynomials with rational coefficients.

[...]
> I do not know why it returns + O(3^0).

Because we define "reduction to precision p^r" in a silly way here
(absolute instead of relative). The function quickly determines that the
input is irreducible over Qp then insists on coercing the output to
t_PADICs with absolute accuracy 3^5, thereby losing information.

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