#15422 closed defect (fixed)

factorization of non-squarefree polynomials over the p-adics

Reported by: jdemeyer Owned by:
Priority: major Milestone: sage-5.13
Component: padics Keywords:
Cc: zimmerma, mmezzarobba, roed, robharron Merged in: sage-5.13.rc0
Authors: Jeroen Demeyer Reviewers: Robert Bradshaw, David Roe
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #864, #9640, #10018, #11868 Stopgaps:

Description (last modified by 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 15422_factorpadic.patch

Attachments (1)

15422_factorpadic.patch (51.9 KB) - added by jdemeyer 12 months ago.

Download all attachments as: .zip

Change History (33)

comment:1 Changed 13 months ago by jdemeyer

  • Description modified (diff)

comment:2 Changed 13 months ago by jdemeyer

  • Dependencies set to #9640

comment:3 Changed 12 months ago by jdemeyer

  • Cc zimmerma added

comment:4 follow-up: Changed 12 months ago by zimmerma

  • Cc mmezzarobba added

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

Paul

comment:5 in reply to: ↑ 4 ; follow-up: Changed 12 months ago by mmezzarobba

Replying to zimmerma:

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

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

comment:6 Changed 12 months ago by jdemeyer

  • Authors set to Jeroen Demeyer
  • Status changed from new to needs_review

comment:7 Changed 12 months ago by jdemeyer

  • Cc roed added

comment:8 Changed 12 months ago by jdemeyer

  • Cc robharron added

comment:9 Changed 12 months ago by jdemeyer

  • Description modified (diff)

comment:10 Changed 12 months ago by jdemeyer

  • Description modified (diff)

comment:11 in reply to: ↑ 5 ; follow-up: Changed 12 months ago by jdemeyer

Replying to mmezzarobba:

I have made the change in the book.

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

comment:12 in reply to: ↑ 11 ; follow-ups: Changed 12 months ago by roed

Replying to jdemeyer:

Replying to mmezzarobba:

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.

comment:13 in reply to: ↑ 12 Changed 12 months ago by mmezzarobba

Replying to roed:

Replying to jdemeyer:

Replying to mmezzarobba:

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!

comment:14 in reply to: ↑ 12 ; follow-up: Changed 12 months ago by jdemeyer

Replying to roed:

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()

comment:15 Changed 12 months ago by jdemeyer

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

comment:16 in reply to: ↑ 14 Changed 12 months ago by roed

Replying to jdemeyer:

Replying to roed:

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.

comment:17 follow-ups: Changed 12 months ago by roed

  • Status changed from needs_review to needs_work

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.

comment:18 in reply to: ↑ 17 Changed 12 months ago by jdemeyer

Replying to roed:

  • 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^20))*t^2 ) is not well-defined. One simply cannot determine whether it has p-adic roots or not.

comment:19 follow-up: Changed 12 months ago by 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.

comment:20 in reply to: ↑ 19 ; follow-up: Changed 12 months ago by roed

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^20))*t^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+310)(t-310) would be another possible factorization.

Last edited 12 months ago by roed (previous) (diff)

comment:21 in reply to: ↑ 20 ; follow-up: Changed 12 months ago by jdemeyer

Replying to roed:

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?...

Last edited 12 months ago by jdemeyer (previous) (diff)

comment:22 Changed 12 months ago by jdemeyer

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.

comment:23 Changed 12 months ago by jdemeyer

  • Dependencies changed from #9640 to #9640, #11868

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.

comment:24 in reply to: ↑ 17 Changed 12 months ago by jdemeyer

Replying to roed:

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)

comment:25 Changed 12 months ago by jdemeyer

  • Dependencies changed from #9640, #11868 to #864, #9640, #10018, #11868
  • Reviewers set to Robert Bradshaw
  • Status changed from needs_work to needs_review

comment:26 Changed 12 months ago by jdemeyer

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).

Changed 12 months ago by jdemeyer

comment:27 in reply to: ↑ 21 Changed 12 months ago by roed

Replying to jdemeyer:

Replying to roed:

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.

comment:28 follow-ups: Changed 12 months ago by roed

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^2+O(3^20) as (t + O(3^10))^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.

comment:29 in reply to: ↑ 28 Changed 12 months ago by jdemeyer

Replying to roed:

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.

comment:30 in reply to: ↑ 28 ; follow-up: Changed 12 months ago by 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?

comment:31 in reply to: ↑ 30 Changed 12 months ago by roed

  • Reviewers changed from Robert Bradshaw to Robert Bradshaw, David Roe
  • Status changed from needs_review to positive_review

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.

comment:32 Changed 12 months ago by jdemeyer

  • Merged in set to sage-5.13.rc0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.