Ore polynomials

[caruso]

We implement general univariate Ore polynomials (allowing for derivations and twisted derivations)

[caruso]

This ticket is not ready for review yet: doctests need to be updated/completed.

---

New commits:

​e3f2b25	rebase on top of ticket #21262
​96dab84	add missing doctest in skew_polynomial_element
​e8e9139	add a reference to my paper with Le Borgne
​5897dfc	address Travis' comments
​05c6bdf	make left_quo_rem and right_quo_rem cdef functions
​99b4ee7	Merge branch 'u/caruso/skew_polynomial_finite_field_rebased' of git://trac.sagemath.org/sage into skew_polynomial_finite_field_rc1
​eac641b	Making imports more local in matrices.
​c5f5bd7	Merge branch 'u/tscrim/specific_imports_matrices-29561' of git://trac.sagemath.org/sage into skew_polynomial_finite_field_rc1
​2ed055d	move imports
​8984aa7	Working implementation of Ore polynomials

[caruso]

Ticket is now ready for review.

[caruso]

I add ticket #21264 in the dependencies because I built this one on top of it.

[git]

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

​f225cbc

fix pyflakes

[caruso]

New commits:

​f225cbc

fix pyflakes

[chapoton]

patchbots report one failing doctest

[git]

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

​b35e1d0

fix one doctest

[chapoton]

La branche est passée au rouge => needs work

[git]

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

​131d78e

Merge branch 'develop' into t/29629/ore_polynomials_rebased

[tscrim]

Looks good overall.

A big question:

There seems to be a lot of code in OrePolynomial that I would think would be the in the generic univariate (dense) polynomial code from sage.rings.polynomial.polynomial_element.Polynomial. Is there a reason you are not inheriting from that? Perhaps we also discussed this previously?

Some comments:

I imagine the change

SkewPolynomialRing = OrePolynomialRing

is because skew polynomials are ore polynomials in univariate case, correct? Will these concepts diverge in the multivariate case? If so, a comment would be good.

Shouldn't the ABC degree raise an NotImplementedError?

The leading coefficient of the 0 polynomial is 0 for other polynomial rings:

sage: R.<x> = QQ[]
sage: R.zero().leading_coefficient()
0

instead of raising an error. This would also simplify the is_monic implementation.

Error messages should not end with periods/full-stops (e.g., is_unit).

Style thing, but I think this is more simple:

-        _,r = self.right_quo_rem(other)
-        return r
+        return self.right_quo_rem(other)[1]

There is a global instance of _Fields = Fields() in ring/ring.pyx, which the check for X in _Fields is faster than X in Fields (last time I checked).

In right/left_xlcm, the math equation should have a period/full-stop at the end.

I feel like the lcm with one of the polynomials being 0 should be 0. This would match the Sage integers:

sage: lcm(0, 5)
0

However, if you think the current way is the most reasonable, then feel free to ignore.

-        - ``monic`` -- boolean (default: ``True``). Return whether the left lcm
-          should be normalized to be monic.
+        - ``monic`` -- boolean (default: ``True``); return whether the left lcm
+          should be normalized to be monic

and similar.

I would instead put the code for checking if the polynomial is zero in __nonzero__ instead of is_zero as Sage code is more likely to ducktype and check if X: than if not X.is_zero():. However, this is a very weak opinion.

Why this

import sage

in ore_polynomial_ring.py?

You should put UniqueRepresentation first in the MRO for OrePolynomialRing; that way there is less lookup for equality/hash/etc. (and less of a chance of it getting accidentally overwritten).

For the OrePolynomialRing doc, something you might find useful is the .. RUBRIC:: A title. See, e.g., combinat/root_system/root_system.py for an example.

Instead of \FF_{x}, do you mean \GF{x}?

-    `sigma` and a twisting `sigma`-derivation can be created as well as
+    `\sigma` and a twisting `\sigma`-derivation can be created as well as

[git]

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

​ea3f0b1

address Travis' comments

[caruso]

Thanks for all your comments.

Replying to tscrim:

There seems to be a lot of code in OrePolynomial that I would think would be the in the generic univariate (dense) polynomial code from sage.rings.polynomial.polynomial_element.Polynomial. Is there a reason you are not inheriting from that? Perhaps we also discussed this previously?

Hum, I don't know. Actually, I just copied this code from the former class SkewPolynomialRing, which was designed a very long time ago. However, I think that there are good reasons for separating Ore polynomials and polynomials, e.g. we probably don't want isinstance(P, Polynomial) to return true when P is a Ore polynomial as I expect many functions to implicitely interpret an instance of Polynomial as a commutative polynomial.

I imagine the change

SkewPolynomialRing = OrePolynomialRing

is because skew polynomials are ore polynomials in univariate case, correct? Will these concepts diverge in the multivariate case? If so, a comment would be good.

I think that the two locutions are synonymous in all cases; but there are used by different people (and maybe "skew polynomials" is preferred when the twisting derivation is trivial, whereas "Ore polynomials" is preferred otherwise).

The leading coefficient of the 0 polynomial is 0 for other polynomial rings:

sage: R.<x> = QQ[]
sage: R.zero().leading_coefficient()
0

instead of raising an error. This would also simplify the is_monic implementation.

I agree and changed this. But this modifies the former interface of leading_coefficient. Should we add a deprecation somewhere?

I feel like the lcm with one of the polynomials being 0 should be 0. This would match the Sage integers:

sage: lcm(0, 5)
0

However, if you think the current way is the most reasonable, then feel free to ignore.

With polynomials, computing lcm with 0 raises an error:

sage: A.<x> = GF(5)[]
sage: P = A(0)
sage: P.lcm(x)
Traceback (most recent call last):
...
ZeroDivisionError: inverse of Mod(0, 5) does not exist

Why this

import sage

in ore_polynomial_ring.py?

This is used on line 384:

        if self.Element is None:
            self.Element = sage.rings.polynomial.ore_polynomial_element.OrePolynomial_generic_dense

and in several other places

[git]

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

​445913a	abstract method degree raises NotImplementedError
​fdbded7	add full-stop after math formulas

[tscrim]

Replying to caruso:

Thanks for all your comments.

Replying to tscrim:

There seems to be a lot of code in OrePolynomial that I would think would be the in the generic univariate (dense) polynomial code from sage.rings.polynomial.polynomial_element.Polynomial. Is there a reason you are not inheriting from that? Perhaps we also discussed this previously?

Hum, I don't know. Actually, I just copied this code from the former class SkewPolynomialRing, which was designed a very long time ago. However, I think that there are good reasons for separating Ore polynomials and polynomials, e.g. we probably don't want isinstance(P, Polynomial) to return true when P is a Ore polynomial as I expect many functions to implicitely interpret an instance of Polynomial as a commutative polynomial.

Then the common functionality should be separated out into a common ABC. Although a normal polynomial is just a skew polynomial under the identity map, correct? If so, the Polynomial class should inherit from the (abstract) SkewPolynomial.

I imagine the change

SkewPolynomialRing = OrePolynomialRing

is because skew polynomials are ore polynomials in univariate case, correct? Will these concepts diverge in the multivariate case? If so, a comment would be good.

I think that the two locutions are synonymous in all cases; but there are used by different people (and maybe "skew polynomials" is preferred when the twisting derivation is trivial, whereas "Ore polynomials" is preferred otherwise).

Okay, thank you for the explanation. Then it doesn't need a comment.

The leading coefficient of the 0 polynomial is 0 for other polynomial rings:

sage: R.<x> = QQ[]
sage: R.zero().leading_coefficient()
0

instead of raising an error. This would also simplify the is_monic implementation.

I agree and changed this. But this modifies the former interface of leading_coefficient. Should we add a deprecation somewhere?

I would be surprised if someone was relying on this behavior. It would also be very difficult to decrement, and I might even argue it was a bug before (so it does not need a deprecation).

I feel like the lcm with one of the polynomials being 0 should be 0. This would match the Sage integers:

sage: lcm(0, 5)
0

However, if you think the current way is the most reasonable, then feel free to ignore.

With polynomials, computing lcm with 0 raises an error:

sage: A.<x> = GF(5)[]
sage: P = A(0)
sage: P.lcm(x)
Traceback (most recent call last):
...
ZeroDivisionError: inverse of Mod(0, 5) does not exist

I see. Hmm...that is a bit of an annoying inconsistency (from my naïve viewpoint). Well, I guess we should follow what polynomials do.

Why this

import sage

in ore_polynomial_ring.py?

This is used on line 384:

        if self.Element is None:
            self.Element = sage.rings.polynomial.ore_polynomial_element.OrePolynomial_generic_dense

and in several other places

Then I think you should do a more localized import, so

from sage.rings.polynomial.ore_polynomial_element import OrePolynomial_generic_dense

at the module level (or in the corresponding methods if there happens to be some import cycle, but there shouldn't be...). This feels weird and like it could lead to some import problem (or requires some large import). I always prefer as localized as possible imports though.

[git]

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

​c778356

remove import sage

[caruso]

Replying to tscrim:

Then the common functionality should be separated out into a common ABC. Although a normal polynomial is just a skew polynomial under the identity map, correct? If so, the Polynomial class should inherit from the (abstract) SkewPolynomial.

I might be seduced by this idea... but I'm not completely sure it will be approved by all.

In any case, I think that it touches a lot in Sage and we cannot implement this in this ticket. So, I propose to delay this discussion to another ticket (and/or maybe collect opinions about this on sage-devel).

[tscrim]

Replying to caruso:

Replying to tscrim:

Then the common functionality should be separated out into a common ABC. Although a normal polynomial is just a skew polynomial under the identity map, correct? If so, the Polynomial class should inherit from the (abstract) SkewPolynomial.

I might be seduced by this idea... but I'm not completely sure it will be approved by all.

In any case, I think that it touches a lot in Sage and we cannot implement this in this ticket. So, I propose to delay this discussion to another ticket (and/or maybe collect opinions about this on sage-devel).

It should be fairly minimal as all it would do is add an additional class to the polynomial hierarchy, and just moving most (all?) of the methods up to that level. As far as anyone using the Polynomial class, they shouldn't see any difference/changes.

However, since this is mostly moving code that was already there, we can delay it for another ticket.

[caruso]

OK, I created ticket #30054.

[tscrim]

So if that addresses all of my comments, then this is at a positive review (unless you want to make the import of the OrePolynomialRing a lazy import).

[caruso]

On my computer, lazy import is much faster (13 μs vs 1.4ms) than an actual import. So, OK for switching.

Btw, why don't we use massively lazy imports at startup if it's much faster?

[git]

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

​bf17a36	Merge branch 'develop' of https://github.com/sagemath/sage into t/29629/ore_polynomials_rebased
​94a1a5c	lazy import

[git]

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

​15f6dfa

fix indentation

[tscrim]

Replying to caruso:

Btw, why don't we use massively lazy imports at startup if it's much faster?

Historical reasons. Also because some things get imported from the strangest places (things that we want to be fast and loaded at startup), which means we cannot just do it en masse. However, that is a general goal IIRC, to get most things imported lazily.

[tscrim]

Also, green bot => positive review.

[tscrim]

Ack, one more thing I just realized: the documentation. You need to add the files to

src/doc/en/reference/polynomial_rings/index.rst

Sorry!

[git]

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

​a9bae69

update documentation

[caruso]

Done. Thanks.

[tscrim]

Thanks. Once the patchbot comes back green, then positive review.

[chapoton]

doc does not build

sage/rings/polynomial/ore_polynomial_ring.py:docstring of 
sage.rings.polynomial.ore_polynomial_ring.OrePolynomialRing:29:
 WARNING: Inline substitution_reference start-string without end-string.
+Makefile:1864: recipe for target 'doc-html' failed

[tscrim]

I am working on fixing this.

[tscrim]

Okay, here are fixes for the documentation, including a number of tests that were not previously being run. I also fixed the not equals comparison for the skew polynomial injection maps. There were a number of other small trivial fixes (broken links, bad formatting, etc.) that I also fixed.

Documentation now builds and tests pass. So if my changes are good, then positive review.

---

New commits:

​f111d30	Merge branch 'u/caruso/ore_polynomials_rebased' of git://trac.sagemath.org/sage into u/caruso/ore_polynomials_rebased
​5d822f3	Fixing the doc and != for polynomial injection maps.

[caruso]

Thanks!

[vbraun]

Merge conflict

[caruso]

New commits:

​1cc0ed8	Merge branch 'develop' into t/29629/ore_polynomials_rebased
​200d7bd	update doctests

[tscrim]

Tests pass for me with the updated branch.

[tscrim]

Docbuild is failing.

[tscrim]

Merged in my branch with your rebased branch to fix the docbuild issues. Since no conflicts, the doc builds, and you reviewed my changes, I am setting this back to a positive review.

---

New commits:

​f111d30	Merge branch 'u/caruso/ore_polynomials_rebased' of git://trac.sagemath.org/sage into u/caruso/ore_polynomials_rebased
​5d822f3	Fixing the doc and != for polynomial injection maps.
​1c7a67c	Merge branch 'u/tscrim/ore_polynomials-29629' of git://trac.sagemath.org/sage into u/caruso/ore_polynomials-29629

[caruso]

Thanks. And sorry for forgetting to pull your changes!