Opened 8 years ago

Closed 7 years ago

Last modified 7 years ago

#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:

Status badges

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 x2 + 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 roed

Yikes. This is a precision problem:

sage: x = polygen(ZZ)
sage: f = x^5 + x^4 - 4*x^2 - x + 3
sage: R = Qp(3,print_mode='digits')
sage: fQp = f.base_extend(R)
sage: h = [a[0] for a in fQp.factor()]
sage: h
[(...1)*x + (...1),
 (...1)*x + (...12101021200010200212),
 (...1)*x + (...21121201022212022020),
 (...1)*x^2 + (...11222222222222222221)*x + (...1000000000000000001)]
sage: h[1]*h[2]
(...1)*x^2 + (...11000000000000000002)*x + (...20000000000000000010)
sage: h[3].discriminant().valuation()
19
sage: prod(h) == fQp
True

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 319, which is not a square.

Note the sensitivity to the precision of the input:

sage: R19 = Qp(3,19,print_mode='digits',print_pos=False)
sage: fQp19 = f.base_extend(R19)
sage: [a[0] for a in fQp19.factor()]
[(...1)*x + (...1),
 (...1)*x + (...121202120222222222),
 (...1)*x + (...1001020101222222222),
 (...1)*x + (...2201021200010200212),
 (...1)*x + (...1121201022212022020)]

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.

comment:2 Changed 8 years ago by jdemeyer

  • Priority changed from blocker to critical

comment:3 Changed 7 years ago by jdemeyer

  • 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 jdemeyer

  • Reviewers set to Jeroen Demeyer
Note: See TracTickets for help on using tickets.