factorization of non-squarefree polynomials over the p-adics

[jdemeyer]

1. The following should be an ArithmeticError since whether or not the polynomial factors depends on the O(3^20) error term (t^2 - 3^20 factors while t^2 - 3^21 does not):

sage: R.<t> = PolynomialRing(Qp(3))
sage: (t^2).factor()
((1 + O(3^20))*t + (O(3^20)))^2

2. The following should directly call PARI's factorpadic without coercing the coefficients to Qp first:

sage: R.<t> = PolynomialRing(QQ)
sage: ((t-1)^2).factor_padic(3,5)
(1 + O(3^5))*t^2 + (1 + 2*3 + 2*3^2 + 2*3^3 + 2*3^4 + O(3^5))*t + (1 + O(3^5))

The attached patch also does some clean-up of the various p-adic polynomial classes, now _repr() and factor() are implemented in exactly one place. One consequence of this is that _repr() for polynomials over Zp has changed: non-exact zeros are now printed.

Apply attachment: 15422_factorpadic.patch

Depends on #864
Depends on #9640
Depends on #10018
Depends on #11868

CC: @zimmermann6 @mezzarobba @roed314 @rharron

Component: padics

Author: Jeroen Demeyer

Reviewer: Robert Bradshaw, David Roe

Merged: sage-5.13.rc0

Issue created by migration from https://trac.sagemath.org/ticket/15422

[jdemeyer]

Dependencies: #9640

[zimmermann6]

comment:4

Marc, do you agree with the change in the "polynomes" chapter?

Paul

[mezzarobba]

comment:5

Replying to @zimmermann6:

Marc, do you agree with the change in the "polynomes" chapter?

I certainly do! I have made the change in the book.

[jdemeyer]

Author: Jeroen Demeyer

[jdemeyer]

comment:11

Replying to @mezzarobba:

I have made the change in the book.

Maybe that's a bit too quick, this is still only "needs_review".

[roed314]

comment:12

Replying to @jdemeyer:

Replying to @mezzarobba:

I have made the change in the book.

Maybe that's a bit too quick, this is still only "needs_review".

Yes. In particular, I disagree with the change to 1. I'm looking at the code now and writing some more comments.

[mezzarobba]

comment:13

Replying to @roed314:

Replying to @jdemeyer:

Replying to @mezzarobba:

I have made the change in the book.

Maybe that's a bit too quick, this is still only "needs_review".

Yes. In particular, I disagree with the change to 1. I'm looking at the code now and writing some more comments.

No problem: I only changed the version in our private repository. I'll keep updating it in case the output changes again, and of course test everything before we release a new version. But thanks for mentioning it!

[jdemeyer]

comment:14

Replying to @roed314:

Yes. In particular, I disagree with the change to 1.

If you do, please explain what you think Sage should answer to

sage: R.<t> = PolynomialRing(Qp(3))
sage: (t^2).factor()

and

sage: R.<t> = PolynomialRing(Qp(3))
sage: (t^2).roots()

[jdemeyer]

comment:15

David: do you agree with part 2 of the patch? Would you review it if I separated it into a different ticket?

[roed314]

comment:16

Replying to @jdemeyer:

Replying to @roed314:

Yes. In particular, I disagree with the change to 1.

If you do, please explain what you think Sage should answer to

sage: R.<t> = PolynomialRing(Qp(3))
sage: (t^2).factor()
((1 + O(3^20))*t + (O(3^10)))^2

and

sage: R.<t> = PolynomialRing(Qp(3))
sage: (t^2).roots()
[(O(3^10), 2)]

Sorry that I didn't manage to review this ticket yet. I'll work on it now and make some suggestions.

[roed314]

comment:17

polynomial_padic.py

• uniformizer_pow rather than prime_pow on line 155
• rather than raising an ArithmeticError on line 159, we should use gcds to return the square, with half the precision. Xavier Caruso and I are working on precision in p-adic factoring. In the mean time, I would prefer to switch this to a NotImplementedError. This will change some doctests (line 114 for example).
  polynomial_element.pyx
• Need to update the doctest on line 5327.
  polynomial_integer_dense_flint.pyx
• The output of factor_padic on line 1277 should be "factorization of self over the completion at p"
  polynomial_integer_dense_ntl.pyx
• The output of factor_padic on line 1002 should be "factorization of self over the completion at p"
  polynomial_rational_flint.pyx
• Need to update the doctest on line 1585.

This patch changes the behavior of content for p-adic polynomials, from returning an element to returning an ideal. I have no problem with that change, but I thought that it should be remarked.

Other than these comments, I'm happy with the changes.

[jdemeyer]

comment:18

Replying to @roed314:

• rather than raising an ArithmeticError on line 159, we should use gcds to return the square, with half the precision.

Why should we do that? My point of view is that we should warn people that they do something which is not mathematically well-defined. And as explained in the ticket description, factor( (1+O(3<sup>20))*t</sup>2 ) is not well-defined. One simply cannot determine whether it has p-adic roots or not.

[jdemeyer]

comment:19

In other words: I think it is wrong to claim that (t^2 - 3^21)*(1 + O(3^20)) has a 3-adic root of multiplicity 2. When you're interpreting t^2*(1 + O(3^20)) as the p-adic coercion of t^2 and not t^2 - 3^21, you're simply guessing.

[roed314]

comment:20

Replying to @jdemeyer:

In other words: I think it is wrong to claim that (t^2 - 3^21)*(1 + O(3^20)) has a 3-adic root of multiplicity 2. When you're interpreting t^2*(1 + O(3^20)) as the p-adic coercion of t^2 and not t^2 - 3^21, you're simply guessing.

You can never say that a p-adic polynomial has a root. The subvariety of irreducible polynomials is open (in either the Zariski or the p-adic topology), and any ball will intersect it. So for a given p-adic polynomial with finite precision, it is either definitely irreducible, or has unknown status. Rather than always raising an ArithmeticError instead of factoring, we should make the convention that we will return a factorization to the greatest extent possible among the polynomials within that ball. There is a nice algorithm to determine the precision of the resulting factors.

In particular, the only thing special about polynomials whose discriminant is indistinguishable from zero is that they have the maximum precision loss among reducible polynomials. Among the reducible polynomials in the ball (1 + O(3<sup>20))*t</sup>2 + (O(3^20))*t + (O(3^20)), all of them have monic factorizations of the form ((1 + O(3^20))*t + (O(3^10)))*((1 + O(3^20))*t + (O(3^10))). For example, (t+3¹⁰)(t-3¹⁰) would be another possible factorization.

[jdemeyer]

comment:21

Replying to @roed314:

You can never say that a p-adic polynomial has a root.

That can't be true (or I am misunderstanding you). Using Hensel's Lemma, you can be certain that polynomials factor in a certain way. For example, any polynomial over Zp which is congruent to (t-1)(t-2) modulo p, will have a single p-adic root close to 1 and a single p-adic root close to 2. In particular, (t-1)(t-2) + p*f will never be irreducible (for f in Zp[t]). What am I missing?...

[jdemeyer]

comment:22

Hensel's Lemma is exactly the reason why p-adic factoring (and root finding) makes sense: because it can give if and only if statements between factoring over Qp and factoring modulo p^n.

[jdemeyer]

comment:23

The change to sage/libs/pari/gen.pyx would conflict with #11868, so I moved that part of the patch to #11868.

I made the changes you requested, except for changing the ArithmeticError.

[jdemeyer]

Changed dependencies from #9640 to #9640, #11868

[jdemeyer]

comment:24

Replying to @roed314:

This patch changes the behavior of content for p-adic polynomials, from returning an element to returning an ideal.

Really? Can you give an example of a result which changed? The following happens both before and after my patch:

sage: parent(polygen(Zp(3, 20, 'capped-abs')).content())
Monoid of ideals of 3-adic Ring with capped absolute precision 20
sage: parent(polygen(Zp(3, 20)).content())
3-adic Ring with capped relative precision 20

(one could argue that this should be changed, but that's unrelated to this ticket)

[jdemeyer]

Reviewer: Robert Bradshaw

[jdemeyer]

Changed dependencies from #9640, #11868 to #864, #9640, #10018, #11868

[jdemeyer]

comment:26

There is a precedent:

sage: (1 + O(2^2)).is_square()
---------------------------------------------------------------------------
PrecisionError                            Traceback (most recent call last)
<ipython-input-2-a8b4da3a4425> in <module>()
----> 1 (Integer(1) + O(Integer(2)**Integer(2))).is_square()

/usr/local/src/sage-5.13.beta1/local/lib/python2.7/site-packages/sage/rings/padics/padic_generic_element.so in sage.rings.padics.padic_generic_element.pAdicGenericElement.is_square (sage/rings/padics/padic_generic_element.c:6916)()

/usr/local/src/sage-5.13.beta1/local/lib/python2.7/site-packages/sage/rings/padics/padic_capped_relative_element.so in sage.rings.padics.padic_capped_relative_element.pAdicCappedRelativeElement.residue (sage/rings/padics/padic_capped_relative_element.c:17528)()

PrecisionError: Not enough precision known in order to compute residue.

This is exactly the same as factoring t^2 - (1 + O(2^2)), so the latter should be an error also.

(I didn't know about PrecisionError, so I'm changing the patch to return a PrecisionError instead of ArithmeticError).

[roed314]

comment:27

Attachment: 15422_factorpadic.patch.gz

Replying to @jdemeyer:

Replying to @roed314:

You can never say that a p-adic polynomial has a root.

That can't be true (or I am misunderstanding you). Using Hensel's Lemma, you can be certain that polynomials factor in a certain way. For example, any polynomial over Zp which is congruent to (t-1)(t-2) modulo p, will have a single p-adic root close to 1 and a single p-adic root close to 2. In particular, (t-1)(t-2) + p*f will never be irreducible (for f in Zp[t]). What am I missing?...

You're right. I need to go to sleep now, but I'll think about this more and get back to you tomorrow. Perhaps we can add an option to pass to factor that allows for factoring non-squarefree polynomials.

As for the content comment, it was based on reading through the patch and noting that you'd deleted that function in Polynomial_element_generic.pyx. But I see now that it's defined again in the other classes, so there's no issue.

[roed314]

comment:28

Sorry for the delay again.

You are right that original claim is invalidated by Hensel lifting. But I still believe that we should factor t<sup>2+O(3</sup>20) as (t + O(3<sup>10))</sup>2 by analogy with linear algebra. Here's what I mean.

Consider the problem of finding the kernel of a matrix A over the p-adics. Sometimes, we will be able to tell that this kernel is trivial (when

A = [1 + O(3^20)     O(3^20)]
    [    O(3^20) 1 + O(3^20)]

for example). But other times we don't know if the dimension is 0 or 1:

A = [1 + O(3^20)     O(3^20)]
    [    O(3^20)     O(3^20)],

or even if the dimension is 0, 1 or 2:

A = [    O(3^20)     O(3^20)]
    [    O(3^20)     O(3^20)].

We often design algorithms so that they produce a matrix with non-trivial kernel, and rely on being able to find it. I don't want Sage to raise a PrecisionError whenever there is a nontrivial kernel.

Of course, if the matrix does have a kernel then we can find it, and we can determine the precision to which we know that kernel. I would argue that that is the more useful answer. In the same way, if a user actually has a polynomial that is not squarefree, it's more useful to tell them that the polynomial factors in a certain way, assuming that it's reducible in the first place.

I think it's a question of how we warn the user that the result is uncertain in this way: include a warning in the documentation of factor or raise a PrecisionError unless the user passes in a certain keyword argument. If we disagree on which option is more appropriate in this case, I would suggest bringing the issue up on sage-nt and sage-padic.

[jdemeyer]

comment:29

Replying to @roed314:

In the same way, if a user actually has a polynomial that is not squarefree, it's more useful to tell them that the polynomial factors in a certain way

I would say it is more useful to tell them that their question is not well-defined. Because, in this case, it is possible to make the question well-defined by either increasing the precision of the given polynomial or by starting with a polynomial over QQ.

raise a PrecisionError unless the user passes in a certain keyword argument.

I could live with this, if the default is to raise the exception.

[jdemeyer]

comment:30

Given that implementing that additional keyword for "best-effort factoring" (factor f assuming everything which could be a power actually is a power) is going to take some work, would you agree with merging this ticket as-is and leaving your suggestion for later?

[roed314]

comment:31

Replying to @jdemeyer:

Given that implementing that additional keyword for "best-effort factoring" (factor f assuming everything which could be a power actually is a power) is going to take some work, would you agree with merging this ticket as-is and leaving your suggestion for later?

I definitely think that implementing best-effort factoring should be saved for another ticket. I'm giving this a positive review, since I think that a keyword argument is a good compromise. I would like to e-mail sage-nt and sage-padic to get some more opinions, but any consensus from that discussion can be postponed to a follow up ticket.

[roed314]

Changed reviewer from Robert Bradshaw to Robert Bradshaw, David Roe

[jdemeyer]

Merged: sage-5.13.rc0