Opened 3 years ago

Closed 2 years ago

# factorization of non-squarefree polynomials over the p-adics

Reported by: Owned by: jdemeyer major sage-5.13 padics zimmerma, mmezzarobba, roed, robharron sage-5.13.rc0 Jeroen Demeyer Robert Bradshaw, David Roe N/A #864, #9640, #10018, #11868

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)
(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.

### comment:1 Changed 3 years ago by jdemeyer

• Description modified (diff)

### comment:2 Changed 3 years ago by jdemeyer

• Dependencies set to #9640

### comment:4 follow-up: ↓ 5 Changed 3 years ago by zimmerma

Marc, do you agree with the change in the "polynomes" chapter?

Paul

### comment:5 in reply to: ↑ 4 ; follow-up: ↓ 11 Changed 3 years ago by mmezzarobba

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 3 years ago by jdemeyer

• Authors set to Jeroen Demeyer
• Status changed from new to needs_review

### comment:9 Changed 3 years ago by jdemeyer

• Description modified (diff)

### comment:10 Changed 3 years ago by jdemeyer

• Description modified (diff)

### comment:11 in reply to: ↑ 5 ; follow-up: ↓ 12 Changed 3 years ago by jdemeyer

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 3 years ago by roed

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 3 years ago by 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 3 years ago by jdemeyer

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 2 years ago by jdemeyer

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 2 years ago by 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 2 years ago by roed

• Status changed from needs_review to needs_work

• 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 a NotImplementedError. 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 2 years ago by jdemeyer

• 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 2 years ago by 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 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 2 years ago by roed

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.

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+310)(t-310) would be another possible factorization.

Last edited 2 years ago by roed (previous) (diff)

### comment:21 in reply to: ↑ 20 ; follow-up: ↓ 27 Changed 2 years ago by jdemeyer

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?...

Last edited 2 years ago by jdemeyer (previous) (diff)

### comment:22 Changed 2 years ago by jdemeyer

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 2 years ago by jdemeyer

• Dependencies changed from #9640 to #9640, #11868

The change to sage/libs/pari/gen.pyx would conflict with #11868, so I moved that part of the patch to #11868.

I made the changes you requested, except for changing the ArithmeticError.

### comment:24 in reply to: ↑ 17 Changed 2 years ago by jdemeyer

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 2 years ago by jdemeyer

• 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 2 years ago by jdemeyer

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()

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

### comment:27 in reply to: ↑ 21 Changed 2 years ago by 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?...

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 2 years ago by roed

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 2 years ago by jdemeyer

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 2 years ago by 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?

### comment:31 in reply to: ↑ 30 Changed 2 years ago by roed

• Status changed from needs_review to positive_review