Opened 7 years ago

Closed 6 years ago

# PARI and Singular can't handle all polynomial resultants

Reported by: Owned by: robharron major sage-6.3 algebra pari, resultant, sylvester matrix Robert Harron, Peter Bruin Martin von Gagern N/A 51523b1 (Commits) 51523b10dd11ba8e7b0689b351130e7596decc23

### Description

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.

### comment:1 Changed 7 years ago by robharron

• Status changed from new to needs_review

### comment:2 Changed 7 years ago by robharron

• Status changed from needs_review to needs_work

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

### comment:4 follow-up: ↓ 7 Changed 7 years ago by pbruin

• Status changed from needs_work to needs_info

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.

### comment:5 Changed 7 years ago by vbraun_spam

• Milestone changed from sage-6.1 to sage-6.2

### comment:6 Changed 7 years ago by gagern

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

### comment:7 in reply to: ↑ 4 ; follow-up: ↓ 8 Changed 7 years ago by gagern

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.

### comment:8 in reply to: ↑ 7 ; follow-up: ↓ 9 Changed 7 years ago by pbruin

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.

### comment:9 in reply to: ↑ 8 ; follow-up: ↓ 10 Changed 6 years ago by gagern

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.

### comment:10 in reply to: ↑ 9 ; follow-up: ↓ 11 Changed 6 years ago by pbruin

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.

### comment:11 in reply to: ↑ 10 Changed 6 years ago by gagern

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…

Last edited 6 years ago by gagern (previous) (diff)

### comment:12 Changed 6 years ago by pbruin

• Authors set to Robert Harron, Peter Bruin
• Branch set to u/pbruin/15061-resultant
• Cc pbruin removed
• Commit set to d1a25de7d398d83dd7aee240b84665648483e279
• Status changed from needs_info to needs_review
• Summary changed from Pari can't handle all polynomial resultants to PARI and Singular can't handle all polynomial resultants

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.

### comment:13 Changed 6 years ago by git

• Commit changed from d1a25de7d398d83dd7aee240b84665648483e279 to 51523b10dd11ba8e7b0689b351130e7596decc23

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

 ​51523b1 `Trac 15061: delete an irrelevant doctest`

### comment:14 follow-ups: ↓ 15 ↓ 16 Changed 6 years ago by gagern

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.

### comment:15 in reply to: ↑ 14 Changed 6 years ago by pbruin

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!

### comment:16 in reply to: ↑ 14 ; follow-up: ↓ 17 Changed 6 years ago by gagern

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?

### comment:17 in reply to: ↑ 16 ; follow-up: ↓ 18 Changed 6 years ago by pbruin

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

### comment:18 in reply to: ↑ 17 ; follow-up: ↓ 19 Changed 6 years ago by gagern

• Reviewers set to Martin von Gagern
• Status changed from needs_review to positive_review

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?

### comment:19 in reply to: ↑ 18 Changed 6 years ago by pbruin

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.

### comment:20 Changed 6 years ago by vbraun_spam

• Milestone changed from sage-6.2 to sage-6.3

### comment:21 Changed 6 years ago by vbraun

• Branch changed from u/pbruin/15061-resultant to 51523b10dd11ba8e7b0689b351130e7596decc23
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.