Opened 9 years ago
Closed 8 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 )
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 9 years ago by
- Description modified (diff)
comment:2 Changed 9 years ago by
- Dependencies set to #9640
comment:3 Changed 8 years ago by
- Cc zimmerma added
comment:4 follow-up: ↓ 5 Changed 8 years ago by
- Cc mmezzarobba added
comment:5 in reply to: ↑ 4 ; follow-up: ↓ 11 Changed 8 years ago by
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 8 years ago by
- Status changed from new to needs_review
comment:7 Changed 8 years ago by
- Cc roed added
comment:8 Changed 8 years ago by
- Cc robharron added
comment:9 Changed 8 years ago by
- Description modified (diff)
comment:10 Changed 8 years ago by
- Description modified (diff)
comment:11 in reply to: ↑ 5 ; follow-up: ↓ 12 Changed 8 years ago by
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 8 years ago by
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 8 years ago by
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 8 years ago by
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 8 years ago by
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 8 years ago by
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 8 years ago by
- 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 aNotImplementedError
. 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 8 years ago by
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 8 years ago by
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 8 years ago by
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 interpretingt^2*(1 + O(3^20))
as thep
-adic coercion oft^2
and nott^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 8 years ago by
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 8 years ago by
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 8 years ago by
- Dependencies changed from #9640 to #9640, #11868
comment:24 in reply to: ↑ 17 Changed 8 years ago by
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 8 years ago by
- 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 8 years ago by
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 8 years ago by
comment:27 in reply to: ↑ 21 Changed 8 years ago by
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 inZp[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 8 years ago by
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 8 years ago by
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 8 years ago by
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 8 years ago by
- 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 8 years ago by
- 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