Opened 7 months ago

Closed 5 months ago

#29629 closed enhancement (fixed)

Ore polynomials

Reported by: caruso Owned by:
Priority: major Milestone: sage-9.2
Component: algebra Keywords:
Cc: tscrim, jsrn, gh-Adurand8 Merged in:
Authors: Xavier Caruso Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 1c7a67c (Commits) Commit: 1c7a67c8638b3984256281b5da382daf69ec36ae
Dependencies: #21264 Stopgaps:

Description

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

Change History (44)

comment:1 Changed 7 months ago by caruso

  • Branch set to u/caruso/ore_polynomials

comment:2 Changed 7 months ago by caruso

  • Commit set to 8984aa7ce206511c05b2ee4df544e4d8b1fcd243

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


New commits:

e3f2b25rebase on top of ticket #21262
96dab84add missing doctest in skew_polynomial_element
e8e9139add a reference to my paper with Le Borgne
5897dfcaddress Travis' comments
05c6bdfmake left_quo_rem and right_quo_rem cdef functions
99b4ee7Merge branch 'u/caruso/skew_polynomial_finite_field_rebased' of git://trac.sagemath.org/sage into skew_polynomial_finite_field_rc1
eac641bMaking imports more local in matrices.
c5f5bd7Merge branch 'u/tscrim/specific_imports_matrices-29561' of git://trac.sagemath.org/sage into skew_polynomial_finite_field_rc1
2ed055dmove imports
8984aa7Working implementation of Ore polynomials

comment:3 Changed 7 months ago by caruso

  • Authors set to Xavier Caruso
  • Branch changed from u/caruso/ore_polynomials to u/caruso/ore_polynomials_rebased
  • Commit changed from 8984aa7ce206511c05b2ee4df544e4d8b1fcd243 to d4565513e8f19e8d1e8ea85ca83d088632578b6d
  • Status changed from new to needs_review

Ticket is now ready for review.

comment:4 Changed 7 months ago by caruso

  • Dependencies set to #21264

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

comment:5 Changed 7 months ago by git

  • Commit changed from d4565513e8f19e8d1e8ea85ca83d088632578b6d to f225cbc1a8533f908eb9827b0d2564eab1df2bbc

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

f225cbcfix pyflakes

comment:6 Changed 7 months ago by caruso

  • Cc jsrn gh-Adurand8 added

New commits:

f225cbcfix pyflakes

comment:7 Changed 7 months ago by chapoton

  • Status changed from needs_review to needs_work

patchbots report one failing doctest

comment:8 Changed 7 months ago by git

  • Commit changed from f225cbc1a8533f908eb9827b0d2564eab1df2bbc to b35e1d0ab287298943e3b4f67ec906351cfa10c7

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

b35e1d0fix one doctest

comment:9 Changed 7 months ago by caruso

  • Status changed from needs_work to needs_review

comment:10 Changed 6 months ago by chapoton

  • Status changed from needs_review to needs_work

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

comment:11 Changed 5 months ago by git

  • Commit changed from b35e1d0ab287298943e3b4f67ec906351cfa10c7 to 131d78e35942a01e6a2679a3dcb61ffa47bd8401

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

131d78eMerge branch 'develop' into t/29629/ore_polynomials_rebased

comment:12 Changed 5 months ago by caruso

  • Status changed from needs_work to needs_review

comment:13 follow-up: Changed 5 months ago by tscrim

  • Reviewers set to Travis Scrimshaw

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

comment:14 Changed 5 months ago by git

  • Commit changed from 131d78e35942a01e6a2679a3dcb61ffa47bd8401 to ea3f0b11545d13198007e3f1effdc95f1d523f15

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

ea3f0b1address Travis' comments

comment:15 in reply to: ↑ 13 ; follow-up: Changed 5 months ago by 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

comment:16 Changed 5 months ago by git

  • Commit changed from ea3f0b11545d13198007e3f1effdc95f1d523f15 to fdbded75f7b0cbacabfa218162cb96386d4de3de

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

445913aabstract method degree raises NotImplementedError
fdbded7add full-stop after math formulas

comment:17 in reply to: ↑ 15 ; follow-up: Changed 5 months ago by 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.

comment:18 Changed 5 months ago by git

  • Commit changed from fdbded75f7b0cbacabfa218162cb96386d4de3de to c77835679d5a6ce00b33a9f303a815b2245d3078

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

c778356remove import sage

comment:19 in reply to: ↑ 17 ; follow-up: Changed 5 months ago by 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).

comment:20 in reply to: ↑ 19 Changed 5 months ago by 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 ticket is mostly moving code that was already there, we can delay it for another ticket.

Last edited 5 months ago by tscrim (previous) (diff)

comment:21 Changed 5 months ago by caruso

OK, I created ticket #30054.

comment:22 Changed 5 months ago by 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).

comment:23 follow-up: Changed 5 months ago by 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?

comment:24 Changed 5 months ago by git

  • Commit changed from c77835679d5a6ce00b33a9f303a815b2245d3078 to 94a1a5c0439ef5f5cef470e0b563fa81cfe88cf5

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

bf17a36Merge branch 'develop' of https://github.com/sagemath/sage into t/29629/ore_polynomials_rebased
94a1a5clazy import

comment:25 Changed 5 months ago by git

  • Commit changed from 94a1a5c0439ef5f5cef470e0b563fa81cfe88cf5 to 15f6dfad8a18ed26fbab018718e0df60769163aa

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

15f6dfafix indentation

comment:26 in reply to: ↑ 23 Changed 5 months ago by 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.

comment:27 Changed 5 months ago by tscrim

Also, green bot => positive review.

comment:28 Changed 5 months ago by tscrim

  • Status changed from needs_review to positive_review

comment:29 Changed 5 months ago by tscrim

  • Status changed from positive_review to needs_review

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!

comment:30 Changed 5 months ago by git

  • Commit changed from 15f6dfad8a18ed26fbab018718e0df60769163aa to a9bae6909bcc44b89e7e5cc9c44ba8a753a60a05

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

a9bae69update documentation

comment:31 Changed 5 months ago by caruso

Done. Thanks.

comment:32 Changed 5 months ago by tscrim

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

comment:33 Changed 5 months ago by 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

comment:34 Changed 5 months ago by tscrim

I am working on fixing this.

comment:35 Changed 5 months ago by tscrim

  • Branch changed from u/caruso/ore_polynomials_rebased to u/tscrim/ore_polynomials-29629
  • Commit changed from a9bae6909bcc44b89e7e5cc9c44ba8a753a60a05 to 5d822f323238c9dd73224a41d12efd2b79b52ec4

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:

f111d30Merge branch 'u/caruso/ore_polynomials_rebased' of git://trac.sagemath.org/sage into u/caruso/ore_polynomials_rebased
5d822f3Fixing the doc and != for polynomial injection maps.

comment:36 Changed 5 months ago by caruso

  • Status changed from needs_review to positive_review

Thanks!

comment:37 Changed 5 months ago by vbraun

  • Status changed from positive_review to needs_work

Merge conflict

comment:38 Changed 5 months ago by caruso

  • Branch changed from u/tscrim/ore_polynomials-29629 to u/caruso/ore_polynomials-29629

comment:39 Changed 5 months ago by caruso

  • Commit changed from 5d822f323238c9dd73224a41d12efd2b79b52ec4 to 200d7bd99aaea8377e5148d8e744b9cb5d56cf3a
  • Status changed from needs_work to needs_review

New commits:

1cc0ed8Merge branch 'develop' into t/29629/ore_polynomials_rebased
200d7bdupdate doctests

comment:40 Changed 5 months ago by tscrim

  • Status changed from needs_review to positive_review

Tests pass for me with the updated branch.

comment:41 Changed 5 months ago by tscrim

  • Status changed from positive_review to needs_work

Docbuild is failing.

comment:42 Changed 5 months ago by tscrim

  • Branch changed from u/caruso/ore_polynomials-29629 to u/tscrim/ore_polynomials-29629
  • Commit changed from 200d7bd99aaea8377e5148d8e744b9cb5d56cf3a to 1c7a67c8638b3984256281b5da382daf69ec36ae
  • Status changed from needs_work to positive_review

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:

f111d30Merge branch 'u/caruso/ore_polynomials_rebased' of git://trac.sagemath.org/sage into u/caruso/ore_polynomials_rebased
5d822f3Fixing the doc and != for polynomial injection maps.
1c7a67cMerge branch 'u/tscrim/ore_polynomials-29629' of git://trac.sagemath.org/sage into u/caruso/ore_polynomials-29629

comment:43 Changed 5 months ago by caruso

Thanks. And sorry for forgetting to pull your changes!

comment:44 Changed 5 months ago by vbraun

  • Branch changed from u/tscrim/ore_polynomials-29629 to 1c7a67c8638b3984256281b5da382daf69ec36ae
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.