Opened 3 years ago
Closed 2 years ago
#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)
Change History (33)
comment:1 Changed 3 years ago by jdemeyer
- Description modified (diff)
comment:2 Changed 3 years ago by jdemeyer
- Dependencies set to #9640
comment:3 Changed 3 years ago by jdemeyer
- Cc zimmerma added
comment:4 follow-up: ↓ 5 Changed 3 years ago by zimmerma
- Cc mmezzarobba added
comment:5 in reply to: ↑ 4 ; follow-up: ↓ 11 Changed 3 years 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 3 years ago by jdemeyer
- Status changed from new to needs_review
comment:7 Changed 3 years ago by jdemeyer
- Cc roed added
comment:8 Changed 3 years ago by jdemeyer
- Cc robharron added
comment:9 Changed 3 years ago by jdemeyer
- Description modified (diff)
comment:10 Changed 3 years ago by jdemeyer
- Description modified (diff)
comment:11 in reply to: ↑ 5 ; follow-up: ↓ 12 Changed 3 years 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: ↓ 13 ↓ 14 Changed 3 years 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 3 years 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: ↓ 16 Changed 3 years 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 2 years 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 2 years 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: ↓ 18 ↓ 24 Changed 2 years 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 2 years 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: ↓ 20 Changed 2 years 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: ↓ 21 Changed 2 years 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+3^{10})(t-3^{10}) would be another possible factorization.
comment:21 in reply to: ↑ 20 ; follow-up: ↓ 27 Changed 2 years 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?...
comment:22 Changed 2 years 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 2 years ago by jdemeyer
- Dependencies changed from #9640 to #9640, #11868
comment:24 in reply to: ↑ 17 Changed 2 years 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 2 years 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 2 years 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 2 years ago by jdemeyer
comment:27 in reply to: ↑ 21 Changed 2 years 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: ↓ 29 ↓ 30 Changed 2 years 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 2 years 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: ↓ 31 Changed 2 years 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 2 years 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 2 years ago by jdemeyer
- Merged in set to sage-5.13.rc0
- Resolution set to fixed
- Status changed from positive_review to closed
Marc, do you agree with the change in the "polynomes" chapter?
Paul