#14812 closed defect (duplicate)
p-adic root finding broken (mathematically incorrect answer)
Reported by: | robharron | Owned by: | roed |
---|---|---|---|
Priority: | critical | Milestone: | sage-duplicate/invalid/wontfix |
Component: | padics | Keywords: | padics, roots |
Cc: | Merged in: | ||
Authors: | Reviewers: | Jeroen Demeyer | |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
This is a huge problem:
sage: x = polygen(QQ) sage: f = x^5 + x^4 - 4*x^2 - x + 3 sage: sage: f.roots() [(-1, 1), (1, 2)] sage: f.roots(Qp(3)) [(2 + 2*3 + 2*3^2 + 2*3^3 + 2*3^4 + 2*3^5 + 2*3^6 + 2*3^7 + 2*3^8 + 2*3^9 + 2*3^10 + 2*3^11 + 2*3^12 + 2*3^13 + 2*3^14 + 2*3^15 + 2*3^16 + 2*3^17 + 2*3^18 + 2*3^19 + O(3^20), 1), (1 + 3 + 2*3^3 + 2*3^4 + 2*3^6 + 3^7 + 2*3^8 + 2*3^9 + 2*3^10 + 3^12 + 2*3^14 + 3^15 + 2*3^16 + 3^17 + 3^19 + O(3^20), 1), (3 + 2*3^2 + 2*3^5 + 3^7 + 2*3^11 + 3^12 + 2*3^13 + 3^15 + 3^17 + 3^18 + O(3^20), 1)] sage: f.base_extend(Qp(3)).factor() ((1 + O(3^20))*x + (1 + O(3^20))) * ((1 + O(3^20))*x + (2 + 3 + 2*3^2 + 2*3^5 + 3^7 + 2*3^11 + 3^12 + 2*3^13 + 3^15 + 3^17 + 2*3^18 + 3^19 + O(3^20))) * ((1 + O(3^20))*x + (2*3 + 2*3^3 + 2*3^4 + 2*3^6 + 3^7 + 2*3^8 + 2*3^9 + 2*3^10 + 3^12 + 2*3^14 + 3^15 + 2*3^16 + 3^17 + 3^18 + 2*3^19 + O(3^20))) * ((1 + O(3^20))*x^2 + (1 + 2*3 + 2*3^2 + 2*3^3 + 2*3^4 + 2*3^5 + 2*3^6 + 2*3^7 + 2*3^8 + 2*3^9 + 2*3^10 + 2*3^11 + 2*3^12 + 2*3^13 + 2*3^14 + 2*3^15 + 2*3^16 + 2*3^17 + 3^18 + 3^19 + O(3^20))*x + (1 + 3^18 + O(3^20)))
The p-adic roots are quit wrong! It's such a crazy answer, I keep feeling like I'm the problem, but I tried this on two copies of sage 5.9 on my computer as well as on sage 5.10 on the cloud. Note for instance that the polynomial x^{2} + 2x + 3 has discriminant -8, which is a square mod 3 and so there should be five roots in Qp(3) (and of course 1 should be a root with multiplicity 2).
Change History (4)
comment:1 Changed 8 years ago by
comment:2 Changed 8 years ago by
- Priority changed from blocker to critical
comment:3 Changed 7 years ago by
- Milestone changed from sage-5.13 to sage-duplicate/invalid/wontfix
- Resolution set to duplicate
- Status changed from new to closed
Duplicate of #15422 which needs review.
comment:4 Changed 7 years ago by
- Reviewers set to Jeroen Demeyer
Note: See
TracTickets for help on using
tickets.
Yikes. This is a precision problem:
If you cut off the precision at some point then there are multiple valid factorizations, and this one has the unfortunate feature that it doesn't find all the roots.
h[3]
is very close to(x-1)^2
, but its discriminant is 3^{19}, which is not a square.Note the sensitivity to the precision of the input:
The precision on the two roots near
-1
is a bit disturbing. I'm curious how things go with #12561 applied, but don't have time to check at the moment.