PARI and Singular can't handle all polynomial resultants

[rharron]

Consider the following:

sage: R.<T> = PowerSeriesRing(QQ)                                                                                                                          
sage: F = R([1,1],2)                                                                                                                                       
sage: F                                                                                                                                                    
1 + T + O(T^2)                                                                                                                                             
sage: RP.<x> = PolynomialRing(R)                                                                                                                           
sage: P = x^2 - F                                                                                                                                                                                                                                                     
sage: P.resultant(P.derivative())
ValueError: series precision must be finite for conversion to pari object.

In particular, sage is incapable of computing the discriminant of this quadratic polynomial! I'll shortly post a patch that catches this error and uses the sylvester matrix instead.

Component: algebra

Keywords: pari, resultant, sylvester matrix

Author: Robert Harron, Peter Bruin

Branch/Commit: 51523b1

Reviewer: Martin von Gagern

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

[rharron]

comment:2

There's something wrong with the patch because of some whitespace issues. I'll fix this soon.

[rharron]

Attachment: trac_15061_use_sylvester_matrix_for_resultant_when_pari_fails.patch.gz

[pjbruin]

comment:4

I noticed that this problem is also solved by #15601, which implements conversion to PARI for power series with infinite precision by converting them to polynomials.

There are probably other base rings that cannot be converted to PARI, so using sylvester_matrix() as a last resort is probably still useful. It would be good to have another example that still fails after applying #15601.

[gagern]

comment:6

My changes from #16014 comment:2 make P.discriminant() work.

[gagern]

comment:7

Replying to @pjbruin:

It would be good to have another example that still fails after applying #15601.

sage: R.<x> = AA[]
sage: (2*x^2 + 3*x + 5).discriminant()
TypeError: no conversion of this ring to a Singular ring defined

Does this help, even though it's singular here and not pari? RIF does the same. I haven't worked out yet which resultants get computed by pari and which by singular.

[pjbruin]

comment:8

Replying to @gagern:

Replying to @pjbruin:

It would be good to have another example that still fails after applying #15601.

sage: R.<x> = AA[]
sage: (2*x^2 + 3*x + 5).discriminant()
TypeError: no conversion of this ring to a Singular ring defined

Does this help, even though it's singular here and not pari? RIF does the same. I haven't worked out yet which resultants get computed by pari and which by singular.

This example still fails with the patch applied. There seems to be a different problem here, namely that the class of that polynomial inherits from Polynomial_singular_repr, even though the base field does not have a conversion to Singular. The same error occurs when you replace PowerSeriesRing by LaurentSeriesRing in the original example.

[gagern]

comment:9

Replying to @pjbruin:

There seems to be a different problem here, namely that the class of that polynomial inherits from Polynomial_singular_repr, even though the base field does not have a conversion to Singular.

polynomial_element_generic.Polynomial_generic_field inherits from polynomial_singular_interface.Polynomial_singular_repr. That inheritance was introduced in 35bb3ea from 2007. Unfortunately I can't see what kind of bug this was supposed to fix. It seems like a bad move to me, though, since that class clearly assumes that you can convert to singular without further checks.

[pjbruin]

comment:10

Replying to @gagern:

Replying to @pjbruin:

There seems to be a different problem here, namely that the class of that polynomial inherits from Polynomial_singular_repr, even though the base field does not have a conversion to Singular.

polynomial_element_generic.Polynomial_generic_field inherits from polynomial_singular_interface.Polynomial_singular_repr. That inheritance was introduced in 35bb3ea from 2007.

That commit only changed the order of the superclasses; the inheritance was there before.

Unfortunately I can't see what kind of bug this was supposed to fix. It seems like a bad move to me, though, since that class clearly assumes that you can convert to singular without further checks.

I agree that it is strange for polynomials over arbitrary fields to inherit from that class. An alternative would be to "manually" prescribe this inheritance for polynomials over fields that support conversion to Singular, but that doesn't sound very attractive. Another alternative would be to move resultant() to a more generic polynomial class that first tries to use Singular and uses a generic Python implementation in case that fails.

[gagern]

comment:11

Replying to @pjbruin:

That commit only changed the order of the superclasses; the inheritance was there before.

Thanks, I missed that fact.

I agree that it is strange for polynomials over arbitrary fields to inherit from that class. An alternative would be to "manually" prescribe this inheritance for polynomials over fields that support conversion to Singular, but that doesn't sound very attractive.

I see how the constructor of PolynomialRing_field checks for singular support and sets the _has_singular property accordingly. We could use that place to change element_class in a suitable way. But if we wanted to handle this using different classes, we'd add one more point to the already dense network of generic vs. special, domain vs. field, sparse vs. dense. Not sure I like that either.

Another alternative would be to move resultant() to a more generic polynomial class that first tries to use Singular and uses a generic Python implementation in case that fails.

Sounds good. As a first step, we could change Polynomial_singular_repr to check self.parent()._has_singular and call super if that isn't set. We could then make sure that Polynomial.resultant falls back to sylvester_matrix if PARI doesn't work. Although I don't know yet for which rings PARI will work. Messy business…

[pjbruin]

comment:12

I think I have found a solution that will solve most of these problems. In this branch:

• Rob Harron's patch, with minor modifications.
• Remove lcm() and resultant() from Polynomial_singular_repr. For lcm(), delete the code and move the doctests to the existing MPolynomial_libsingular.lcm(); for resultant(), move the code and doctests to the new MPolynomial_polydict.resultant().
• In MPolynomial_polydict.resultant(), fall back on Sylvester matrices if the ring has no Singular implementation.
• Various cosmetic fixes.

[pjbruin]

Author: Robert Harron, Peter Bruin

[pjbruin]

Commit: d1a25de

[pjbruin]

Branch: u/pbruin/15061-resultant

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

51523b1

Trac 15061: delete an irrelevant doctest

[sagetrac-git]

Changed commit from d1a25de to 51523b1

[gagern]

comment:14

Judging from the timestamps, your system clock is wrong. Apart from that, I like the code, from what I can tell at first glance. Thanks! Will pull and run tests soon.

[pjbruin]

comment:15

Replying to @gagern:

Judging from the timestamps, your system clock is wrong.

I know, but it is a system that I am not the administrator of.

Apart from that, I like the code, from what I can tell at first glance. Thanks! Will pull and run tests soon.

OK, thanks!

[gagern]

comment:16

Will pull and run tests soon.

All tests in src/sage/rings passed here. And the code still looks sane at second glance. Am I qualified to give this a positive review?

[pjbruin]

comment:17

Replying to @gagern:

All tests in src/sage/rings passed here. And the code still looks sane at second glance. Am I qualified to give this a positive review?

You can probably judge yourself if you have done the things suggested in "Reviewing Patches" in the developer guide. (Note in particular that you are supposed to run all doctests; things can really break in unexpected places.)

[gagern]

comment:18

Replying to @pjbruin:

You can probably judge yourself if you have done the things suggested in "Reviewing Patches" in the developer guide.

• ./sage -t --all --long: done, no new errors
• make including documentation: done
• ./sage -docbuild reference pdf: done
• ./sage -coverage src/sage/rings/polynomial/*.py{,x}: Diff shows that this now has 6 things less to complain about, and no new ones

I wonder whether the docs for resultant regarding “Implemented using PARI’s polresultant function.” should get adjusted. On the other hand, I doubt that detailing the possible choices of algorithm is worth the effort.

(Note in particular that you are supposed to run all doctests; things can really break in unexpected places.)

Did so, and found #16285 in the process. But that's reproducible without your change, so not your fault.

Shouldn't running the testsuite be handled by patchbot? Or hasn't that been migrated to the git workflow yet?

[gagern]

Reviewer: Martin von Gagern

[pjbruin]

comment:19

Replying to @gagern:

Shouldn't running the testsuite be handled by patchbot? Or hasn't that been migrated to the git workflow yet?

It has, but not enough people are running patchbots, and I think there are also some glitches that sometimes prevent it from doing its job.

[vbraun]

Changed branch from u/pbruin/15061-resultant to 51523b1