Opened 2 years ago
Closed 22 months ago
#29629 closed enhancement (fixed)
Ore polynomials
Reported by:  caruso  Owned by:  

Priority:  major  Milestone:  sage9.2 
Component:  algebra  Keywords:  
Cc:  tscrim, jsrn, ghAdurand8  Merged in:  
Authors:  Xavier Caruso  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  1c7a67c (Commits, GitHub, GitLab)  Commit:  1c7a67c8638b3984256281b5da382daf69ec36ae 
Dependencies:  #21264  Stopgaps: 
Description
We implement general univariate Ore polynomials (allowing for derivations and twisted derivations)
Change History (44)
comment:1 Changed 2 years ago by
 Branch set to u/caruso/ore_polynomials
comment:2 Changed 2 years ago by
 Commit set to 8984aa7ce206511c05b2ee4df544e4d8b1fcd243
comment:3 Changed 2 years ago by
 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 2 years ago by
 Dependencies set to #21264
I add ticket #21264 in the dependencies because I built this one on top of it.
comment:5 Changed 2 years ago by
 Commit changed from d4565513e8f19e8d1e8ea85ca83d088632578b6d to f225cbc1a8533f908eb9827b0d2564eab1df2bbc
Branch pushed to git repo; I updated commit sha1. New commits:
f225cbc  fix pyflakes

comment:7 Changed 2 years ago by
 Status changed from needs_review to needs_work
patchbots report one failing doctest
comment:8 Changed 2 years ago by
 Commit changed from f225cbc1a8533f908eb9827b0d2564eab1df2bbc to b35e1d0ab287298943e3b4f67ec906351cfa10c7
Branch pushed to git repo; I updated commit sha1. New commits:
b35e1d0  fix one doctest

comment:9 Changed 2 years ago by
 Status changed from needs_work to needs_review
comment:10 Changed 2 years ago by
 Status changed from needs_review to needs_work
La branche est passée au rouge => needs work
comment:11 Changed 2 years ago by
 Commit changed from b35e1d0ab287298943e3b4f67ec906351cfa10c7 to 131d78e35942a01e6a2679a3dcb61ffa47bd8401
Branch pushed to git repo; I updated commit sha1. New commits:
131d78e  Merge branch 'develop' into t/29629/ore_polynomials_rebased

comment:12 Changed 2 years ago by
 Status changed from needs_work to needs_review
comment:13 followup: ↓ 15 Changed 23 months ago by
 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/fullstops (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/fullstop 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 23 months ago by
 Commit changed from 131d78e35942a01e6a2679a3dcb61ffa47bd8401 to ea3f0b11545d13198007e3f1effdc95f1d523f15
Branch pushed to git repo; I updated commit sha1. New commits:
ea3f0b1  address Travis' comments

comment:15 in reply to: ↑ 13 ; followup: ↓ 17 Changed 23 months ago by
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 fromsage.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 = OrePolynomialRingis 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() 0instead 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 be0
. This would match the Sage integers:sage: lcm(0, 5) 0However, 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 sagein
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 23 months ago by
 Commit changed from ea3f0b11545d13198007e3f1effdc95f1d523f15 to fdbded75f7b0cbacabfa218162cb96386d4de3de
comment:17 in reply to: ↑ 15 ; followup: ↓ 19 Changed 23 months ago by
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 fromsage.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 wantisinstance(P, Polynomial)
to return true whenP
is a Ore polynomial as I expect many functions to implicitely interpret an instance ofPolynomial
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 = OrePolynomialRingis 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() 0instead 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 be0
. This would match the Sage integers:sage: lcm(0, 5) 0However, 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 sagein
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_denseand 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 23 months ago by
 Commit changed from fdbded75f7b0cbacabfa218162cb96386d4de3de to c77835679d5a6ce00b33a9f303a815b2245d3078
Branch pushed to git repo; I updated commit sha1. New commits:
c778356  remove import sage

comment:19 in reply to: ↑ 17 ; followup: ↓ 20 Changed 23 months ago by
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 sagedevel).
comment:20 in reply to: ↑ 19 Changed 23 months ago by
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 sagedevel).
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.
comment:21 Changed 23 months ago by
OK, I created ticket #30054.
comment:22 Changed 23 months ago by
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 followup: ↓ 26 Changed 23 months ago by
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 23 months ago by
 Commit changed from c77835679d5a6ce00b33a9f303a815b2245d3078 to 94a1a5c0439ef5f5cef470e0b563fa81cfe88cf5
comment:25 Changed 23 months ago by
 Commit changed from 94a1a5c0439ef5f5cef470e0b563fa81cfe88cf5 to 15f6dfad8a18ed26fbab018718e0df60769163aa
Branch pushed to git repo; I updated commit sha1. New commits:
15f6dfa  fix indentation

comment:26 in reply to: ↑ 23 Changed 23 months ago by
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 23 months ago by
Also, green bot => positive review.
comment:28 Changed 23 months ago by
 Status changed from needs_review to positive_review
comment:29 Changed 23 months ago by
 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 23 months ago by
 Commit changed from 15f6dfad8a18ed26fbab018718e0df60769163aa to a9bae6909bcc44b89e7e5cc9c44ba8a753a60a05
Branch pushed to git repo; I updated commit sha1. New commits:
a9bae69  update documentation

comment:31 Changed 23 months ago by
Done. Thanks.
comment:32 Changed 23 months ago by
Thanks. Once the patchbot comes back green, then positive review.
comment:33 Changed 23 months ago by
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 startstring without endstring. +Makefile:1864: recipe for target 'dochtml' failed
comment:34 Changed 23 months ago by
I am working on fixing this.
comment:35 Changed 23 months ago by
 Branch changed from u/caruso/ore_polynomials_rebased to u/tscrim/ore_polynomials29629
 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:
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.

comment:37 Changed 23 months ago by
 Status changed from positive_review to needs_work
Merge conflict
comment:38 Changed 23 months ago by
 Branch changed from u/tscrim/ore_polynomials29629 to u/caruso/ore_polynomials29629
comment:39 Changed 23 months ago by
 Commit changed from 5d822f323238c9dd73224a41d12efd2b79b52ec4 to 200d7bd99aaea8377e5148d8e744b9cb5d56cf3a
 Status changed from needs_work to needs_review
comment:40 Changed 23 months ago by
 Status changed from needs_review to positive_review
Tests pass for me with the updated branch.
comment:41 Changed 23 months ago by
 Status changed from positive_review to needs_work
Docbuild is failing.
comment:42 Changed 23 months ago by
 Branch changed from u/caruso/ore_polynomials29629 to u/tscrim/ore_polynomials29629
 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:
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_polynomials29629' of git://trac.sagemath.org/sage into u/caruso/ore_polynomials29629

comment:43 Changed 23 months ago by
Thanks. And sorry for forgetting to pull your changes!
comment:44 Changed 22 months ago by
 Branch changed from u/tscrim/ore_polynomials29629 to 1c7a67c8638b3984256281b5da382daf69ec36ae
 Resolution set to fixed
 Status changed from positive_review to closed
This ticket is not ready for review yet: doctests need to be updated/completed.
New commits:
rebase on top of ticket #21262
add missing doctest in skew_polynomial_element
add a reference to my paper with Le Borgne
address Travis' comments
make left_quo_rem and right_quo_rem cdef functions
Merge branch 'u/caruso/skew_polynomial_finite_field_rebased' of git://trac.sagemath.org/sage into skew_polynomial_finite_field_rc1
Making imports more local in matrices.
Merge branch 'u/tscrim/specific_imports_matrices29561' of git://trac.sagemath.org/sage into skew_polynomial_finite_field_rc1
move imports
Working implementation of Ore polynomials