Ore polynomials

[xcaruso]

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

Depends on #21264

CC: @tscrim @johanrosenkilde @Adurand8

Component: algebra

Author: Xavier Caruso

Branch/Commit: 1c7a67c

Reviewer: Travis Scrimshaw

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

[xcaruso]

Branch: u/caruso/ore_polynomials

[xcaruso]

Commit: 8984aa7

[xcaruso]

comment:2

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

[xcaruso]

comment:3

Ticket is now ready for review.

[xcaruso]

Author: Xavier Caruso

[xcaruso]

Changed branch from u/caruso/ore_polynomials to u/caruso/ore_polynomials_rebased

[xcaruso]

Changed commit from 8984aa7 to d456551

[xcaruso]

Dependencies: #21264

[xcaruso]

comment:4

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

f225cbc

fix pyflakes

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from d456551 to f225cbc

[xcaruso]

New commits:

f225cbc

fix pyflakes

[fchapoton]

comment:7

patchbots report one failing doctest

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from f225cbc to b35e1d0

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

b35e1d0

fix one doctest

[fchapoton]

comment:10

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

131d78e

Merge branch 'develop' into t/29629/ore_polynomials_rebased

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from b35e1d0 to 131d78e

[tscrim]

comment:13

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

[tscrim]

Reviewer: Travis Scrimshaw

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 131d78e to ea3f0b1

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

ea3f0b1

address Travis' comments

[xcaruso]

comment:15

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from ea3f0b1 to fdbded7

[tscrim]

comment:17

Replying to @xcaruso:

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.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from fdbded7 to c778356

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

c778356

remove import sage

[xcaruso]

comment:19

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]

comment:20

Replying to @xcaruso:

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 ticket is mostly moving code that was already there, we can delay it for another ticket.

[xcaruso]

comment:21

OK, I created ticket #30054.

[tscrim]

comment:22

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

[xcaruso]

comment:23

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?

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from c778356 to 94a1a5c

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 94a1a5c to 15f6dfa

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

15f6dfa

fix indentation

[tscrim]

comment:26

Replying to @xcaruso:

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]

comment:27

Also, green bot => positive review.

[tscrim]

comment:29

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!

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

a9bae69

update documentation

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 15f6dfa to a9bae69

[xcaruso]

comment:31

Done. Thanks.

[tscrim]

comment:32

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

[fchapoton]

comment:33

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]

comment:34

I am working on fixing this.

[tscrim]

Changed commit from a9bae69 to 5d822f3

[tscrim]

Changed branch from u/caruso/ore_polynomials_rebased to u/tscrim/ore_polynomials-29629

[tscrim]

comment:35

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.

[xcaruso]

comment:36

Thanks!