Factoring p-adic polynomials

[Joao Alberto de Faria]

What is the difficulty in factoring polynomials with multiple roots over the p-adic ring? 

[[[ R.<x>=Qp(5)[]

f=x^2

g=gcd(f,f.derivative())

(f/g).factor() ]]]

returns the following error:

sage.rings.padics.precision_error.PrecisionError: p-adic factorization
not well-defined since the discriminant is zero up to the requestion
p-adic precision

this works fine over the rationals:

[[[ R.<x>=QQ[]
f=x^2
g=gcd(f,f.derivative())
(f/g).factor() ]]]

I'm not well versed in p-adics, is this impossible or just not implemented?

[Nils Bruin]

On Tuesday, April 28, 2015 at 10:28:06 AM UTC-7, Joao Alberto de Faria wrote:

What is the difficulty in factoring polynomials with multiple roots over the p-adic ring? 

[[[ R.<x>=Qp(5)[]

f=x^2

g=gcd(f,f.derivative())

(f/g).factor() ]]]

returns the following error:

sage.rings.padics.precision_error.PrecisionError: p-adic factorization
not well-defined since the discriminant is zero up to the requestion
p-adic precision

You didn't do what you think you did there:

sage: f/g
((1 + O(5^20))*x^2)/((1 + O(5^20))*x)

It looks like sage is being conservative here in taking out apparent common factors. Calling "factor" on that will probably attempt to factor numerator and denominator separately. You'd really want to do a long division here:

sage: f // g
(1 + O(5^20))*x
sage: (f//g).factor()
(1 + O(5^20))*x + (O(5^20))

Checking the remainder:

sage: f % g
(O(5^20))*x^2

so it's indeed indistinguishable from 0.

[Joao Alberto de Faria]

The problem is that this issue also occurs for 

 R.<x>=Qp(5)[]

f=x^2

f.factor(), I was trying to fiddle with it and accidently copied the wrong code

[Nils Bruin]

On Tuesday, April 28, 2015 at 11:25:07 AM UTC-7, Joao Alberto de Faria wrote:

The problem is that this issue also occurs for 

 R.<x>=Qp(5)[]

f=x^2

f.factor(), I was trying to fiddle with it and accidently copied the wrong code

Right. That particular polynomial looks like it can't be confused with an irreducible one, but that's a special case because its trailing coefficient is 0, and the code doesn't special case that. But you should really think of that polynomial as

sage: f+1-1
(1 + O(5^20))*x^2 + (O(5^20))

which could be an approximation to any one of

(1 + O(5^40))*x^2 + (-1*5^20+O(5^40)) #which is reducible
(1 + O(5^40))*x^2 + (2*5^20+O(5^40))  #which is irreducible
(1 + O(5^40))*x^2 + (1*5^21+O(5^40))  #which is irreducible for a different reason

so if a polynomial isn't obviously square free, deciding its factorization is numerically unstable. Sage apparently opts to not guess. If you have reason to believe that you have enough precision to tell the multiplicities of factors in its factorization then you should proceed exactly as you did: take the square-free part, factor that, and figure out the multiplicities of the factors. Sage's reluctance to do that for you is perhaps inconvienent and possibly not the best user interface choice, but it's certainly defensible.

[David Roe]

See http://trac.sagemath.org/ticket/15422.  Jeroen and I had a disagreement on what to do in this case, and ended up deciding that we should leave it as an ArithmeticError for now, pending more work on factoring.  Brian Sinclair has a patch in progress at http://trac.sagemath.org/ticket/12561 implementing p-adic factoring natively in Sage, though it needs some work.

A degree 2 polynomial over Qp(5), such as f = (1 + O(5^20))*x^2 + O(5^20)*x + O(5^20), can be thought of as a ball inside a three dimensional affine space A over Qp(5) (representing all of the possible polynomials that f approximates).  There are various loci inside A corresponding to different factorization patterns (in this case, A has a closed subvariety consisting of reducible polynomials together with its complement consisting of irreducible polynomials; in higher degree there are more options).  If you pick one of these loci, the factorization of f is well defined up to a certain precision (see http://arxiv.org/pdf/1402.7142v1.pdf, end of appendix B2).  In this case, you get either

((1 + O(5^10))*x + O(5^10))^2 for the reducible locus,
(1 + O(5^20))*x^2 + O(5^20)*x + O(5^20) for the irreducible locus.

I think the most useful answer is to return ((1 + O(5^10))*x + O(5^10)) * ((1 + O(5^10))*x + O(5^10)) (possibly requiring a certain keyword parameter to the factor method).  If your actual polynomial lies in the irreducible locus, it is possible to increase precision enough so that a ball around it lies entirely within the irreducible locus.  But if the actual polynomial is reducible, any ball will intersect the irreducible locus.  Choosing to raise an error every time you try to factor a non-irreducible polynomial will just cause frustration (as we see here).
David

--
You received this message because you are subscribed to the Google Groups "sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
To post to this group, send email to sage-...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[Jeroen Demeyer]

There is no problem with reducible polynomials, only with non-squarefree
polynomials. The correct statement is:

If your actual polynomial lies in the squarefree locus, it is possible

to increase precision enough so that a ball around it lies entirely

within the squarefree locus. But if the actual polynomial is not
squarefree, any ball will intersect the squarefree locus.

[David Roe]

You're right, thanks.

David

On Wed, Apr 29, 2015 at 6:11 AM, Jeroen Demeyer <jdem...@cage.ugent.be> wrote:

There is no problem with reducible polynomials, only with non-squarefree polynomials. The correct statement is:

If your actual polynomial lies in the squarefree locus, it is possible to increase precision enough so that a ball around it lies entirely within the squarefree locus.  But if the actual polynomial is not squarefree, any ball will intersect the squarefree locus.

[Jeroen Demeyer]

On 2015-04-28 20:59, Nils Bruin wrote:
> On Tuesday, April 28, 2015 at 11:25:07 AM UTC-7, Joao Alberto de Faria
> wrote:
>
> The problem is that this issue also occurs for
> R.<x>=Qp(5)[]
> f=x^2
> f.factor(), I was trying to fiddle with it and accidently copied the
> wrong code
>

> its trailing coefficient is 0
No, it's not, the trailing coefficient is O(5^20):

sage: R.<x> = Qp(5)[]
sage: f = x^2
sage: parent(f[0])
5-adic Field with capped relative precision 20

This polynomial could have been an approximation of (x^2 + 5^21), which
is irreducible.

Precisely to avoid these issues, polynomials over QQ have a
factor_padic() method which assumes that the input is exact:

sage: R.<x> = QQ[]
sage: f = x^2
sage: f.factor_padic(5,20)
((1 + O(5^20))*x + (O(5^20)))^2

[Nils Bruin]

On Wednesday, April 29, 2015 at 3:15:44 AM UTC-7, Jeroen Demeyer wrote:

No, it's not, the trailing coefficient is O(5^20):

sage: R.<x> = Qp(5)[]
sage: f = x^2
sage: parent(f[0])
5-adic Field with capped relative precision 20

Note the capped *relative* precision. These are "floats*. That's to say that elements are represented as p^v*u where u is a unit  represented by an element in Z/p^rZ with r<=20 ... except that 0 admits representations like that for any v as long as r=0. Apparently we ended up having an "exact" zero in Qp(5).

So it is correct *in this case* that you can actually positively conclude that f is a square, since it's a monomial of degree 2. This is such a special case, however, that it doesn't make sense to support it in factorization, so we don't. I suspect that after removing content from the polynomial, factorization first moves to a (capped?) absolute precision representation, i.e., effectively we probably work with factorization of polynomials in (Z/p^nZ)[x], where f cannot be distinguished from polynomials that come from the square-free locus.

[Jeroen Demeyer]

On 2015-04-29 17:49, Nils Bruin wrote:
> effectively we probably work with
> factorization of polynomials in (Z/p^nZ)[x], where f cannot be
> distinguished from polynomials that come from the square-free locus.

Yes, that's true.