p-adic factoring does not detect multiple roots

[roed314]

sage: R.<x> = Qp(2)[]
sage: f = (x - 2)^4 * (x^2 + x + 8)
sage: f.factor()
((1 + O(2^20))*x + (1 + 2^3 + 2^4 + 2^5 + 2^7 + 2^8 + 2^9 + 2^11 + 2^13 + 2^15 + O(2^20))) * ((1 + O(2^20))*x + (2^3 + 2^6 + 2^10 + 2^12 + 2^14 + 2^16 + 2^17 + 2^18 + 2^19 + O(2^20))) * ((1 + O(2^20))*x^4 + (2^3 + 2^4 + 2^5 + 2^6 + 2^7 + 2^8 + 2^9 + 2^10 + 2^11 + 2^12 + 2^13 + 2^14 + 2^15 + 2^16 + 2^17 + 2^18 + 2^19 + O(2^20))*x^3 + (2^3 + 2^4 + O(2^20))*x^2 + (2^5 + 2^6 + 2^7 + 2^8 + 2^9 + 2^10 + 2^11 + 2^12 + 2^13 + 2^14 + 2^15 + 2^16 + 2^17 + 2^18 + 2^19 + O(2^20))*x + (2^4 + O(2^20)))
sage: list(f.factor())

[((1 + O(2^20))*x + (1 + 2^3 + 2^4 + 2^5 + 2^7 + 2^8 + 2^9 + 2^11 + 2^13 + 2^15 + O(2^20)),
  1),
 ((1 + O(2^20))*x + (2^3 + 2^6 + 2^10 + 2^12 + 2^14 + 2^16 + 2^17 + 2^18 + 2^19 + O(2^20)),
  1),
 ((1 + O(2^20))*x^4 + (2^3 + 2^4 + 2^5 + 2^6 + 2^7 + 2^8 + 2^9 + 2^10 + 2^11 + 2^12 + 2^13 + 2^14 + 2^15 + 2^16 + 2^17 + 2^18 + 2^19 + O(2^20))*x^3 + (2^3 + 2^4 + O(2^20))*x^2 + (2^5 + 2^6 + 2^7 + 2^8 + 2^9 + 2^10 + 2^11 + 2^12 + 2^13 + 2^14 + 2^15 + 2^16 + 2^17 + 2^18 + 2^19 + O(2^20))*x + (2^4 + O(2^20)),
  1)]

One could argue that this is simply bad user input, since the problem of factoring a p-adic polynomial is not well-defined if the discriminant is 0.

This is a follow-up to #15422.

Component: padics

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

[roed314]

comment:1

So, I can replicate this in GP, but I think the problem is that pari doesn't try to handle the precision issues that arise in factoring. This polynomial is not squarefree, so small perturbations of the coefficients will yield polynomials with different factorization patterns. Note the following excerpt from the documentation for pari's factorpadic:

If pol has inexact t_PADIC coefficients, this is not always well-defined;
in this case, the polynomial is first made integral by dividing out the
p-adic content, then lifted to ℤ using truncate coefficientwise. Hence
we actually factor exactly a polynomial which is only p-adically close
to the input. To avoid pitfalls, we advise to only factor polynomials
with exact rational coefficients.

https://pari.math.u-bordeaux.fr/dochtml/html/Polynomials_and_power_series.html

I think the solution is to implement the reduction to squarefree factorization in Sage.

[jdemeyer]

comment:2

I think I remember having this discussion before with you, David.

There is no bug. It's an ill-posed question because there is no uniquely defined answer. To give a simpler example:

sage: R.<x> = QQ []
sage: ((x+1)^2 - 0*3^12).factor_padic(3)
((1 + O(3^10))*x + (1 + O(3^10)))^2
sage: ((x+1)^2 - 1*3^12).factor_padic(3)
((1 + O(3^10))*x + (1 + 3^6 + O(3^10))) * ((1 + O(3^10))*x + (1 + 2*3^6 + 2*3^7 + 2*3^8 + 2*3^9 + O(3^10)))
sage: ((x+1)^2 - 3*3^12).factor_padic(3)
(1 + O(3^10))*x^2 + (2 + O(3^10))*x + (1 + O(3^10))

These are 3 different factorization patterns for polynomials which are all the same up to O(3^10). So if all you have is the 3-adic approximation, there is no way to guess.

[roed314]

comment:3

Replying to @jdemeyer:

I think I remember having this discussion before with you, David.

Yeah, we've talked about it before though I don't remember the ticket/thread. I agree that this is not a bug in Pari. But I think we should adopt a principle in Sage along the lines of "assume you are in the smallest dimensional subvariety that is consistent with the given information." Otherwise asking for the kernel of a p-adic matrix never makes sense. Though I guess this is inconsistent with the valuation of O(p^n) being n and not infinity.

Anyway, I'm probably not going to work on this ticket immediately. When I'm ready to propose concrete changes like this, I'll raise it on the sage-padics list (and try to track down the discussions that we've had previously).

[jdemeyer]

comment:4

Reduced the bug somewhat.

[jdemeyer]

comment:5

Replying to @roed314:

I think we should adopt a principle in Sage along the lines of "assume you are in the smallest dimensional subvariety that is consistent with the given information." Otherwise asking for the kernel of a p-adic matrix never makes sense.

Right. Knowing a p-adic matrix up to any finite absolute precision is never sufficient to know that it has a kernel.

Similarly, knowing any non-squrefree p-adic polynomial to any finite absolute precision is never sufficient to know that it is non-squarefree.

That is mathematics, which is easy :-) The hard question is how to deal with this. Personally, I would argue that it's simply an error to ask something if the answer is not well-defined. That is what I tried in #15422 for factoring, but apparently it didn't quite work.

That being said, I'm not against "fixing" this "bug". It would make sense to do that as part of #12561 (but that seems to be stalled).