p-adic root finding broken (mathematically incorrect answer)

[rharron]

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

Component: padics

Keywords: roots

Reviewer: Jeroen Demeyer

Issue created by migration from https://trac.sagemath.org/ticket/14812

[roed314]

comment:1

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 3¹⁹, 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.

[jdemeyer]

comment:3

Duplicate of #15422 which needs review.

[jdemeyer]

Reviewer: Jeroen Demeyer