Skew polynomials

[caruso]

If R is a ring equipped with an endomorphism sigma, the ring of skew polynomials over (R,sigma) is the ring of usual polynomials over R with the modified multiplication given by the rule X*a = sigma(a)*X.

Skew polynomials play an important role in several domains like coding theory or Galois representations theory in positive characteristic.

This ticket provides:

1. a basic implementation of skew polynomials over any commutative ring (including addition, multiplication, euclidean division, gcd...)
2. construction of skew polynomial rings

[caruso]

File trac_13215_skew_polynomials.2.patch replaces trac_13215_skew_polynomials.patch

[tfeulner]

With your changes it is now possible to test some element in an Univariate Quotient Polynomial Ring to be a unit and to compute its inverse. Unfortunately, this computation gives wrong results:

sage: Z16x.<x> = Integers(16)[]
sage: GR.<y> =  Z16x.quotient(x**2 + x+1 )
sage: (2*y).is_unit()
True
sage: (2*y)^(-1)
15*y + 15
sage: (2*y)*(2*y)^(-1)
2

Thomas

[caruso]

Thanks for catching this!

I've updated my patch. (I've simply decided to raise a NotImplementedError? when the base ring is not a field and, by the way, I've added some doctests.)

PS: apply patch trac_13215_skew_polynomials.patch and forget trac_13215_skew_polynomials.2.patch (is it possible to remove it?)

[tfeulner]

Maybe you should produce a seperate trac ticket for the fix of

sage: (2*y)^(-1)
...
NotImplementedError: The base ring (=Ring of integers modulo 16) is not a field

By the way, I know that this is a problem which also occurs for usual polynomials (because of the default definition of the reduce function). Do you have any idea how to fix this:

sage: Z16x.<x> = SkewPolynomialRing(Integers(16)) 
sage: # Z16x.<x> = Integers(16)[] # has the same behaviour
sage: GR.<y> =  Z16x.quotient(x**2 + x+1 )
sage: I = GR.ideal(4)
sage: I.reduce(6)
6

[caruso]

Ok, I split my patch in two parts and I open a new ticket (cf #13303).

I'm afraid I don't understand quite well the problem with reduce. Could you explain it a bit more please?

[jdemeyer]

Please fill in your real name as Author.

[tfeulner]

Hi Xavier,

you are right this is a more general problem. I started a discussion on ​https://groups.google.com/d/topic/sage-devel/s5y604ZPiQ8/discussion. The function reduce() does what it says returning an element of the ring. But in the definition of a QuotientRing? there is the following assumption

I.reduce(x)==I.reduce(y) \iff x-y \in I, and x-I.reduce(x) \in I, for all x \in R.

With this default behaviour, the quotient ring is just a copy of the original ring R.

Best, Thomas

[burcin]

It would be great to have all this in Sage. Thanks a lot for your work.

I haven't had a chance to look at the patches yet. I will try to make some time available for this in the coming weeks. For now, I have two questions,

• Did you consider using Singular's noncommutative component, Plural, as a basic data structure for skew polynomials? I expect the arithmetic to be much faster with Plural than a new implementation in Cython.
• Can the patches be broken down into smaller components for easier review?

[caruso]

I haven't heard about Plural before that... so, I haven't considered using it for skew polynomials yet. I will compare how fast is the arithmetic with Plural and with my own implementation in Cython and let you know.

Ok, I will split my patch in several components. (Is two enough or are you expecting more than that?).

[burcin]

Thanks for the prompt response! I am attending a workshop this week and I haven't had a chance to read through your patch properly yet. So please excuse me if I am completely off the mark in my response below. :)

Replying to caruso:

I haven't heard about Plural before that... so, I haven't considered using it for skew polynomials yet. I will compare how fast is the arithmetic with Plural and with my own implementation in Cython and let you know.

Your patch provides more functionality than Plural, for example gcd's and factoring. The coefficient domains supported by Plural are also limited. I suppose your implementation supports more general coefficient domains, basically anything Sage already knows about.

It would be good to have a clear comparison between Plural and your implementation first. But I imagine having two skew polynomial classes in Sage, a generic implementation from your patch and one based on Plural. We could probably share the high level functionality not provided by Plural using the category framework.

I am not opposed to just including your patch and think about the Plural part later as an optimization if you say that your implementation is more capable.

Ok, I will split my patch in several components. (Is two enough or are you expecting more than that?).

I don't know yet. It depends on how many functionally independent parts there are. For instance, the short representations for morphisms can be an independent piece that is trivial to review. The hash functions for morphisms would also be a separate bug fix. Actually, I attempted to fix that a long time ago at #9016.

[caruso]

I had a quick look at the documentation of Plural but I didn't find how to create a skew polynomial ring (i.e. I don't know how to represent a skew polynomial ring as a G-algebra). Could you please learn me this?

[burcin]

Replying to caruso:

I had a quick look at the documentation of Plural but I didn't find how to create a skew polynomial ring (i.e. I don't know how to represent a skew polynomial ring as a G-algebra). Could you please learn me this?

For example, QQ[n, S:n->n+1] :

sage: A.<n, S> = FreeAlgebra(QQ, 2)
sage: R.<n, S> = A.g_algebra({S*n: n*S + 1})
sage: R
Noncommutative Multivariate Polynomial Ring in n, S over Rational Field, nc-relations: {S*n: n*S + 1}
sage: S*n
n*S + 1
sage: S^2*n
n*S^2 + 2*S

After applying the patches on this ticket and its dependencies, I get the following error:

sage: R.<t> = ZZ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]; S
Skew Polynomial Ring in x over Univariate Polynomial Ring in t over Integer Ring twisted by t |--> t + 1
sage: x*t
---------------------------------------------------------------------------
NotImplementedError                       Traceback (most recent call last)
...
sage: %debug
> /home/burcin/sage/sage-5.2/skewpolynomial_element.pyx(347)sage.rings.polynomial.skewpolynomial_element.SkewPolynomial._list_c (sage/rings/polynomial/skewpolynomial_element.c:4716)()

[burcin]

Replying to burcin:

Replying to caruso:

Ok, I will split my patch in several components. (Is two enough or are you expecting more than that?).

I don't know yet. It depends on how many functionally independent parts there are. For instance, the short representations for morphisms can be an independent piece that is trivial to review. The hash functions for morphisms would also be a separate bug fix. Actually, I attempted to fix that a long time ago at #9016.

From a cursory reading of attachment:trac_13215_skew_polynomials.patch​, I see these separate parts that should have a ticket of its own:

• short representations for morphisms
• hash functions for morphisms (#9016)
• q_jordan
• modular exponentiation of polynomial_element

A few comments (not a full review):

• the operator / always constructs the quotient domain in Sage, even if exact division is possible. Since in this case we need a generic Ore localization for /, I suggest you only implement exact division with // and raise an error on /.

  +    sage: d = a * b
  +    sage: d/b == a   # Right division
  +    True
  +
  +    sage: c/b
  +    Traceback (most recent call last):
  +    ...
  +    ValueError: the division is not exact
  

• For the constructor, why don't you check if the argument of the __getitem__ method is a Morphism instead of this:

        from sage.categories.morphism import Morphism
         if isinstance(x,tuple) and len(x) == 2 and isinstance(x[1],Morphism):
  

  This should remove the limitation of having to specify the variable name on the right hand side as documented here:

  +One can also use a shorter syntax::
  +
  +    sage: S.<x> = R['x',sigma]; S
  +    Skew Polynomial Ring in x over Univariate Polynomial Ring in t over Integer Ring twisted by t |--> t + 1
  +
  +Be careful, with the latter syntax, one cannot omit the name of the 
  +variable neither in LHS nor in RHS. If we omit it in LHS, the variable 
  +is not created::
  +
  +    sage: Sy = R['y',sigma]; Sy
  +    Skew Polynomial Ring in y over Univariate Polynomial Ring in t over Integer Ring twisted by t |--> t + 1
  +    sage: y.parent()
  +    Traceback (most recent call last):
  +    ...
  +    NameError: name 'y' is not defined    
  +
  +If we omit it in RHS, sage tries to create a polynomial ring and fails::
  +
  +    sage: Sz.<z> = R[sigma]
  +    Traceback (most recent call last):
  +    ...
  +    ValueError: variable names must be alphanumeric, but one is 'Ring endomorphism of Univariate Polynomial Ring in t over Integer Ring
  +      Defn: t |--> t + 1' which is not.
  

• There is a class SkewPolynomialRing_finite_field defined in sage/rings/polynomial/skewpolynomial_ring.py. There is also a file sage/rings/polynomial/skewpolynomial_finite_field.pyx. It seems that the class defined in the latter does not use the latter:

  cdef class SkewPolynomial_finite_field_dense (SkewPolynomial_generic_dense):
  

• I suggest using skew_polynomial in the file names instead of skewpolynomial.

• Are the Left and Right objects defined in sage/structure/side.py really necessary? If Right is the default, can't you just have a keyword argument left=<bool>?

• There are many functions missing a docstring or tests. Here is partial coverage output:

  $ ./sage -coverage devel/sage/sage/rings/polynomial/skew*
  ----------------------------------------------------------------------
  devel/sage/sage/rings/polynomial/skewpolynomial_element.pyx
  ERROR: Please add a `TestSuite(s).run()` doctest.
  SCORE devel/sage/sage/rings/polynomial/skewpolynomial_element.pyx: 78% (58 of 74)
  
  Missing documentation:
  	 * __hash__(self):
  	 * __richcmp__(left, right, int op):
  	 * __nonzero__(self):
  	 * _is_atomic(self):
  	 * __lshift__(self, k):
  	 * __rshift__(self, k):
  	 * is_gen(self):
  	 * make_generic_skewpolynomial(parent, coeffs):
  	 * Element _call_(self, x):
  	 * __init__(self, domain, codomain):
  	 * Element _call_(self, x):
  	 * Element _call_with_args(self, x, args=(), kwds={}):
  	 * section(self):
  
  
  Missing doctests:
  	 * SkewPolynomial _new_constant_poly(self,RingElement a,Parent P,char check=0):
  	 * is_unit(self):
  	 * __copy__(self):
  
  
  Possibly wrong (function name doesn't occur in doctests):
  	 * ModuleElement _add_(self, ModuleElement right):
  	 * ModuleElement _sub_(self, ModuleElement right):
  	 * ModuleElement _neg_(self):
  	 * ModuleElement _lmul_(self, RingElement right):
  	 * ModuleElement _rmul_(self, RingElement left):
  	 * RingElement _mul_(self, RingElement right):
  	 * RingElement _div_(self, RingElement right):
  
  ----------------------------------------------------------------------
  
  ----------------------------------------------------------------------
  devel/sage/sage/rings/polynomial/skewpolynomial_finite_field.pyx
  ERROR: Please add a `TestSuite(s).run()` doctest.
  SCORE devel/sage/sage/rings/polynomial/skewpolynomial_finite_field.pyx: 82% (29 of 35)
  
  Missing documentation:
  	 * __init__(self, parent, x=None, int check=1, is_gen=False, int construct=0, **kwds):
  	 * reduced_norm_factor(self):
  	 * _factorizations_rec(self):
  
  
  Missing doctests:
  	 * _irreducible_divisors(self,side):
  	 * __init__(self,parent,cutoff=0):
  	 * __repr__(self):
  
  
  Possibly wrong (function name doesn't occur in doctests):
  	 * RingElement _mul_(self, RingElement right):
  
  ----------------------------------------------------------------------
  
  ----------------------------------------------------------------------
  devel/sage/sage/rings/polynomial/skewpolynomial_ring_constructor.py
  SCORE devel/sage/sage/rings/polynomial/skewpolynomial_ring_constructor.py: 100% (1 of 1)
  ----------------------------------------------------------------------
  
  ----------------------------------------------------------------------
  devel/sage/sage/rings/polynomial/skewpolynomial_ring.py
  SCORE devel/sage/sage/rings/polynomial/skewpolynomial_ring.py: 42% (17 of 40)
  
  Missing documentation:
  	 * _call_ (self, x):
  	 * __init__(self,domain,codomain,embed,order):
  	 * _repr_(self):
  	 * _call_(self,x):
  	 * section(self):
  	 * __init__ (self, skew_ring, names=None, sparse=False, element_class=None):
  	 * __classcall__(cls, base_ring, map, name=None, sparse=False, element_class=None):
  	 * __init__(self, base_ring, map, name, sparse, element_class):
  	 * __reduce__(self):
  	 * _element_constructor_(self, x=None, check=True, is_gen = False, construct=False, **kwds):
  	 * _coerce_map_from_(self, P):
  	 * __cmp__(left, right):
  	 * _repr_(self):
  	 * _latex_(self):
  	 * gens_dict(self):
  	 * __classcall__(cls, base_ring, map, name=None, sparse=False, element_class=None):
  	 * __init__(self, base_ring, map, name, sparse, element_class):
  
  
  Missing doctests:
  	 * _repr_ (self):
  	 * _latex_ (self):
  	 * parameter(self):
  	 * is_sparse(self):
  	 * _new_retraction_map(self,alea=None):
  	 * _retraction(self,x,newmap=False,alea=None):
  
  ----------------------------------------------------------------------
  
  

[burcin]

Here is some more information from Viktor Levandovskyy about Plural and skew polynomials rings over finite fields with the frobenius map.

> Plural can be used in the following situations:
> Let |F|=p^k, where p is a prime.
> *) always possible: k = 1,2 and k = p-1,p.
> *) For k=3,...,p-2 there's no general statement, sometimes
> works, sometimes not. Depends on p and k
> *) k>p: impossible (with Plural)

[caruso]

Thanks a lot for all your comments!

Replying to burcin:

• short representations for morphisms
• hash functions for morphisms (#9016)
• q_jordan
• modular exponentiation of polynomial_element

Ok, I've done it (see tickets #13640, #13641 #13642 and old ticket #13214 for "hash functions for morphisms").

After applying the patches on this ticket and its dependencies, I get the following error:

sage: R.<t> = ZZ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]; S
Skew Polynomial Ring in x over Univariate Polynomial Ring in t over Integer Ring twisted by t |--> t + 1
sage: x*t
---------------------------------------------------------------------------
NotImplementedError                       Traceback (most recent call last)
...
sage: %debug
> /home/burcin/sage/sage-5.2/skewpolynomial_element.pyx(347)sage.rings.polynomial.skewpolynomial_element.SkewPolynomial._list_c (sage/rings/polynomial/skewpolynomial_element.c:4716)()

It's now fixed. (I haven't really understood what was the problem. It worked well on sage 5.1.0. I just removed some inline somewhere.)

• the operator / always constructs the quotient domain in Sage, even if exact division is possible. Since in this case we need a generic Ore localization for /, I suggest you only implement exact division with // and raise an error on /.

Done.

• For the constructor, why don't you check if the argument of the __getitem__ method is a Morphism instead of this:

        from sage.categories.morphism import Morphism
         if isinstance(x,tuple) and len(x) == 2 and isinstance(x[1],Morphism):
  

  This should remove the limitation of having to specify the variable name on the right hand side as documented here:

It's not possible to remove this limitation this way because of the preparser (you see in the following example that the variable 'x' doesn't appear in the first instruction on the last line).

sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: preparse(S.<x> = k[Frob])
sage: preparse("S.<x> = k[Frob]")
'S = k[Frob]; (x,) = S._first_ngens(1)'

• I suggest using skew_polynomial in the file names instead of skewpolynomial.

Done.

• Are the Left and Right objects defined in sage/structure/side.py really necessary? If Right is the default, can't you just have a keyword argument left=<bool>?

Sometimes, Left is the default (for lcm). I agree that we can just have a boolean argument but, when I wrote this code, I thought that it was more elegant to do this way. Anymay, I can change if you insist :-).

• There are many functions missing a docstring or tests.

I've added some documentation and doctests (but I'm still far from a 100% coverage).

[caruso]

I've posted an updated version of this patch which should apply at the top of sage 5-10 (hopefully).

[darij]

Needs to be rebased on sage-5.12beta5. The patch fails to apply to sage/structure/all.py.

I'd do it myself but when I try to open the file in gedit, I get: "The file you opened has some invalid characters. If you continue editing this file you could corrupt this document. You can also choose another character encoding and try again." Might be some accents or umlauts on names.

[git]

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

​f6305ce

Revert "adding examples involving min_symbolic and max_symbolic"(did changes in the wrong ticket)

[arpitdm]

New commits:

​d915c13	merging the skew_polynomial ticket 13215 in local repository
​447ddb3	Extensions for skew_polynomial_element and skew_polynomial_finite field added.
​05cc01b	The methods PY_NEW_SAME_TYPE and PY_TYPE_CHECK_EXACT are not supported by Sage anymore and are replaced by the method type. The Cython comparison function is updated to _cmp_ supported in other rings in Sage.
​241b98d	The methods PY_NEW_SAME_TYPE and PY_TYPE_CHECK_EXACT are not supported by Sage anymore and are replaced by the method type.
​98277cd	Rewrote the construction of skew polynomial ring according to the new conventions. Original code had placed it in the /sage/rings/rings.pyx file but the current location has moved to the getitem method of /sage/category/ring.py
​de61ca4	Importing ring_element, integral_domain and principal_ideal_domain were throwing deprecation warnings. Updated the import statements according to Tickets 19167 and 20011.

[git]

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

​9d21b54

module that implements class 'Side' with Left and Right as the two instances.

[git]

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

​9c526ad

Fixed doctests caused by deprecation warnings, inability to access private variables, AttributeError in accessing of parent, and .

[dlucas]

I fixed one of the remaining bugs related to coercion of integers to a skew polynomial ring element. Some bugs still remain.

---

New commits:

​9de7bc1	Merge branch 'u/arpitdm/skew_polynomials' of git://trac.sagemath.org/sage into skew_polynomials
​a06c2bf	Merge branch 'u/arpitdm/skew_polynomials' of git://trac.sagemath.org/sage into skew_polynomials
​18c7982	Fixed bug with integer coercion

[jsrn]

A little thing I noted: is_SkewPolynomial should be removed, I think. Sage moved away from that kind of functions. The category framework should be used instead, but I don't think we need to find a replacement for it just now.

[tscrim]

A better idiom is to just use isinstance(S, SkewPolynomialRing_general) as it is explicit (and there is no category for skew polynomial rings).

[jsrn]

One of the bugs in the doctest has to do with failing in the proper manner when the twist map is not invertible (this is the TypeError: bad operand type for unary ~ bug). This is because self._map ** n is being called with negative n, which will then try to invert self._map using the unary ~ operator which is not supported by self._map of type Homomorphism_im_gens.

But the code was always supposed to fail! The doc-test just expected the error NotImplementedError?, while the error nowadays is this unhelpful unary-~-stuff.

One solution is therefore simply to catch the strange error and rethrow a NotImplementedException?. The following patch should be put in skew_polynomial_ring.py (the line numbers are not completely correct):

@@ -534,9 +534,18 @@ class SkewPolynomialRing_general(sage.algebras.algebra.Algebra,UniqueRepresentat
         try:
             return self._maps[n]
         except KeyError:
-            map = self._map**n
-            self._maps[n] = map
-            return map
+            if n >= 0:
+                map = self._map**n
+                self._maps[n] = map
+                return map
+            else:
+                try:
+                    map = self._map**n
+                except TypeError:
+                    raise NotImplementedError("Inversion of the twist map %s" % self._map)
+                self._maps[n] = map
+                return map
+                    

Best, Johan

---

New commits:

​c6183bc	Merge branch 'develop' into temp3
​dd5c575	Editing declarations of cython functions so as to make them compatible.

[jsrn]

Note that I didn't modify any code: the two commits just appear under my message because arpitdm didn't leave a comment after his last push.

[git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

​81a291f	Added more sig_on/sig_off
​dce652e	Fix some imports
​a7b8815	commented out suspicious __copy__ method
​dd821ec	A few more sig_on/off and cleaning up some commented out code
​d5fad11	sig_on/off almost everywhere in finite field pyx (omitted factoring/irreducible stuff)
​df59050	Fixed bug with crashing add for finite fields by declaring SkewPolynomial.__normalize
​a92d241	Fixed segfault with _pow_ by declaring some _inplace_* already in SkewPolynomial class
​bb36f9a	Suspicious reuse of list of coefficients made into a safe copy
​544ca8d	Fix x._pow_(2) by calling ._new_c instead of _parent (I don't know why this worked!)
​378b2cf	fixed indentation error

[arpitdm]

Cherry-picked commits based on fixes by Johan. The segfault from before is now fixed. Various doctest errors still remain. Now breaking up this ticket into smaller pieces so that it will be easier to manage.

[git]

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

​f3a9209	removed skew_polynomial_finite_field files
​09dc81d	removed the irreducibility, center and finite field stuff from this file
​ff60603	removed finite_fields stuff from file
​97c7770	removed extension from module_list.py
​60dc332	removed empty class CenterSkewPolynomial_generic_dense

[arpitdm]

The current ticket now contains only the basic framework for skew polynomials. All features related to finite fields, irreducibility, center and karatsuba multiplication will be put into a separate ticket. The aim is to fix the failed doctests in the skew_polynomial_element.pyx file and then refactor the code, improve/add documentation and tests, phase out "side".

[git]

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

​5b886b3

Fixed NotImplementedError and other standalone errors.

[jsrn]

Fixed some nasty errors, and some not so nasty ones.

---

New commits:

​fa9f2a3	Remove __cmp__
​1061067	missing return statement
​21be4d8	Fixed some doctests

[git]

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

​c0250fe	Edits to documentation, clean up code
​3c758fe	minor edit to a documentation
​f0bd901	merging changes
​0189fc2	implemented special case for def is_unit when base ring is an integral domain
​17ce5ec	Merge branch 'partially_refactored_skew_polynomials' into skew_polynomials
​c65088d	fixed doctest that was mistakenly edited before

[git]

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

​71e77de	renamed lmonic as left_monic, rmonic as right_monic and removed def monic.
​99664e6	renamed lquo_rem and rquo_rem as left_quo_rem and right_quo_rem. removed def quo_rem. split def is_divisible_by into def is_left_divisible_by and is_right_divisible_by. Same for def divides. replaced all instances in this file accordingly.
​783f8df	renamed lxgcd and rxgcd as left_xgcd and right_xgcd. removed def xgcd.
​2a4f087	renamed lgcd and rgcd as left_gcd and right_gcd. removed def gcd.
​cd44a5a	fixed doctest errors from left_gcd. renamed llcm and rlcm as left_lcm and right_lcm. removed def lcm.
​bc2a863	removed sig_on/sig_off from everywhere.
​d7f51f9	small cleanup

[git]

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

​f0f31b9	removed def coeffs since it has been deprecated in polynomial_element.pyx. modified def coefficients to support return of only non-zero entries as well as all.
​883146f	added methods def reverse, def number_of_terms and def is_one.
​cebe0b4	added __copy__, evaluation of polynomial and is_constant methods.
​98d357d	removed from pow method in Class SkewPolynomial_generic_dense. Added documentation and tests to all the remaining functions and classes.

[git]

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

​49f2626	added a couple of tests. fixed typos in documentation.
​56982a2	added documentation and tests. fixed doctests.
​1808bb3	small documentation for normalize function.
​e189fec	removed side.py

[arpitdm]

We planned on breaking up this skew polynomials ticket into five pieces namely:

1. Ticket A - The main framework. Skew polynomials, basic operations, coercions, skew polynomial rings, etc.
2. Ticket B - Class SkewPolynomial_finite_field_dense, class SkewPolynomialRing_finite_field and related methods
3. Ticket C - cdef class SkewPolynomial_finite_field_karatsuba and related methods
4. Ticket D - class SectionSkewPolynomialCenterInjection?, class SkewPolynomialCenterInjection?, class CenterSkewPolynomialRing? and related methods
5. Ticket E - Irreducibility and Factoring related methods.

The current ticket #13215 has been modified to cover Ticket A. I will post an update here with the links to the remaining tickets once they have been created. For now, based on discussions, the main framework has been refactored, appended to, edited, documented and tested. I'm now opening this ticket for review.

[dlucas]

Hello,

I started reviewing your work. For now, I mostly read documentation and checked formatting, without focusing on the code itself. Here are my comments:

Generic comments:

• For now, there's nothing related to skew polynomials in the index file, so it won't be possible for the user to access the documentation through the online reference manual. Can you please add a dedicated section in the related index file? See src/doc/en/reference/polynomial_rings/index.rst.

• I would also use the experimental decorator here: the code in itself seems stable, but it will allow us to make later name changes (for instance) without putting deprecation warnings all over the place. In particular, I have in mind later implementations of sparse rings and multivariate rings, which might trigger some renaming in the classes implemented here.

skew_polynomial_ring_constructor.py

• I might be wrong, but it does not seem to have any reason to get both input name and names. The argument in the NOTE block sounds weird to me, especially when reading the code: it seems to be some kind of argument for later enhancements (multivariate skew polynomial rings), as for now it does not work if the list contains more than one element. Furthermore, the input names is only used to set name if the latter is None, and dropped just after. And in any case, I think it's better to use only one input and use type checks. I propose to remove names, rename name into variable_names, and use sanity checks: if it's a string, or a list with a single string, use it, otherwise return an appropriate error. I also suggest to add a line in the note block to say that multivariate rings are not supported (it's only detailed in tests for now).
• Can you please explicit what LHS/RHS means?
• There's an option sparse=False which, if set to True, returns a NotImplementedError. I suggest to remove it for now in order to not confuse the user, and reinstate it later when it will be fully implemented. In this case, also remove all references to this feature in the documentation.
• INPUT block could be enhanced: I would rather explain what's name (or variable_names if you agree with my comment above) instead of just saying "a string". I would also rename sigma to something more indicative. What about base_ring_endomorphism?
• As I suggest to remove some not implemented but planned features, it might be a good idea to add a TODO block as a reminder of these features (sparse rings, multivariate rings).
• Module title says "constructorS for skew polynomial rings", while there's only one method in this module. </quibbling>
• Module documentation itself is not great. I think it might be a good idea to add a few links to skew_polynomial_ring.py, and even to give a small definition of a skew polynomial ring in this module.

skew_polynomial_ring.py

• The short description of this module: "Sage implements dense skew univariate polynomials over commutative rings.", seems unhelpful. I'd rather replace it by something explaining the purpose of this module.
• I think the definition can be enhanced a bit: for instance, you find references to "twisting" all over the examples, but it's not defined everywhere. Reading what's in the DEFINITION block should be enough to understand the terminology used in the module, even if you're not familiar with skew polynomials at all.
• Same remark as above regarding LHS/RHS.
• Some imports are not necessary anymore, e.g. import sage.misc.latex as latex.
• Some methods here do not follow the mandatory documentation template. For instance, __init__ does not have a short description, nor an INPUT block...
• There are a few methods in this file which are commented. If these are no longer useful, I suggest to remove them instead of commeting them.
• In some methods, documentation is not really helpful: see twist_map for instance. If says "Return the twist map [...]" which is not very informative...
• While I'm talking about it, would it be possible to explain why this method might fail if you pass a negative number as input? The sentence "Sometimes it succeeds" seems to imply it's more or less random, but if you could investigate this a bit it would lead to a more satisfying documentation.

skew_polynomial_element.py

• Same remark as above regarding the definition of a skew polynomial ring.
• Same remark as above regarding imported packages.
• Same remark as above regarding informativeness of docstrings for some methods.
• Same remark as above regarding documentation itself: a few methods (e.g. conjugate) do not have a short description, while make_generic_skew_polynomial does not have documentation at all!

Best,

David

[tscrim]

Replying to dlucas:

• I would also use the experimental decorator here: the code in itself seems stable, but it will allow us to make later name changes (for instance) without putting deprecation warnings all over the place. In particular, I have in mind later implementations of sparse rings and multivariate rings, which might trigger some renaming in the classes implemented here.

It is okay to change class names as long as the public API doesn't change (although this can entail unpickling issues in either case). I would instead future-proof this by

• Can you please explicit what LHS/RHS means?

I think these are such common abbreviations for Left(Right)-Hand Side that being explicit about them will add some clutter.

• There's an option sparse=False which, if set to True, returns a NotImplementedError. I suggest to remove it for now in order to not confuse the user, and reinstate it later when it will be fully implemented. In this case, also remove all references to this feature in the documentation.
• As I suggest to remove some not implemented but planned features, it might be a good idea to add a TODO block as a reminder of these features (sparse rings, multivariate rings).

I disagree with these comments. This is documenting an upcoming feature, it helps keeps the API consistent with future plans and other parts of Sage, and tells someone reading the code what is currently not implemented.

• Some methods here do not follow the mandatory documentation template. For instance, __init__ does not have a short description, nor an INPUT block...

I treat this more as a strong guideline than a hard rule, but with that being said, anything more non-trivial should at least document its inputs (e.g., the __init__ would be useful).

I agree with the rest of David's comments.

Also, from a cursory glance, there seems to be a lot of duplication with the current implementations of polynomials (i.e., the elements). I feel there could be a lot of simplification of the code by either subclassing or creating a mix-in (cython) class that overrides the _mul_ of polynomials. Is there a reason why you didn't do this? This might entail doing some refactoring/abstracting of the polynomial code though, but it should make the implementation of skew polynomials a lot easier (and bug proof).

[tscrim]

One last thing, make sure all functions have doctests.

[arpitdm]

Replying to dlucas:

• For now, there's nothing related to skew polynomials in the index file, so it won't be possible for the user to access the documentation through the online reference manual. Can you please add a dedicated section in the related index file? See src/doc/en/reference/polynomial_rings/index.rst.

I read up a little on Sphinx documentation and from what I understand, I need to add the following in the file you mentioned, right?

@sage.misc.superseded.experimental(trac_number=13215)
Skew Polynomials
----------------

.. toctree::
   :maxdepth: 2

   sage/rings/polynomial/skew_polynomial_element
   sage/rings/polynomial/skew_polynomial_ring_constructor
   sage/rings/polynomial/skew_polynomial_ring

• I would also use the experimental decorator here: the code in itself seems stable, but it will allow us to make later name changes (for instance) without putting deprecation warnings all over the place. In particular, I have in mind later implementations of sparse rings and multivariate rings, which might trigger some renaming in the classes implemented here.

Placing the experimental warning (like I did above) is not the right way to do it because it does not throw an error. Do I instead place this line at the start of every class in all the three files instead?

skew_polynomial_ring_constructor.py

• I might be wrong, but it does not seem to have any reason to get both input name and names. The argument in the NOTE block sounds weird to me, especially when reading the code: it seems to be some kind of argument for later enhancements (multivariate skew polynomial rings), as for now it does not work if the list contains more than one element. Furthermore, the input names is only used to set name if the latter is None, and dropped just after. And in any case, I think it's better to use only one input and use type checks. I propose to remove names, rename name into variable_names, and use sanity checks: if it's a string, or a list with a single string, use it, otherwise return an appropriate error. I also suggest to add a line in the note block to say that multivariate rings are not supported (it's only detailed in tests for now).

I agree. names and name are both not required and variable_names along with tests to check type of the input is cleaner. I've made this change.

• Can you please explicit what LHS/RHS means?

Like @tscrim mentions, I think LHS/RHS are extremely common terms that are used almost everywhere and perhaps don't need explicit description.

• There's an option sparse=False which, if set to True, returns a NotImplementedError. I suggest to remove it for now in order to not confuse the user, and reinstate it later when it will be fully implemented. In this case, also remove all references to this feature in the documentation.

There are a lot of places where a NotImplementedError? is raised and not just in this ticket but in other polynomial files as well. I think it makes more sense to have them if they are already there. However, there is then the inconsistency in that derivations in skew polynomials are not implemented and are marked as todo as is the multivariate case in some places. Still, I argue for keeping sparse as it is since it is integrated in the framework already unlike the other two. And with the experimental warning showing up, changing this will not create too much trouble.

• INPUT block could be enhanced: I would rather explain what's name (or variable_names if you agree with my comment above) instead of just saying "a string". I would also rename sigma to something more indicative. What about base_ring_endomorphism?

An endomorphism that admits an inverse is an automorphism and skew polynomial rings AFAIK are based on automorphisms. Please correct me if I'm mistaken in this. If so, the places where it says that the twist map is not invertible, maybe should say that twist map should be invertible. And accordingly, the name can be changed to base_ring_automorphism.

• Module documentation itself is not great. I think it might be a good idea to add a few links to skew_polynomial_ring.py, and even to give a small definition of a skew polynomial ring in this module.

Understood. I've made changes and expanded on the definitions and examples from other files. Same goes for all other notes (below) about improving explanations.

• Some imports are not necessary anymore, e.g. import sage.misc.latex as latex.

I tried to do that with the ones I thought were not needed/deprecated. I've obviously missed a few. I'll go over this once again.

• Some methods here do not follow the mandatory documentation template. For instance, __init__ does not have a short description, nor an INPUT block...

Is there a reference doc or something where I can go through the mandatory documentation template? Or is it that Description, Input, Output, Examples, Tests - should these be present for every method? A lot of places, it doesn't make sense to have all of this.

• In some methods, documentation is not really helpful: see twist_map for instance. not have a short description, while make_generic_skew_polynomial does not have documentation at all!

Oh right! I mentioned this in the email thread with Johan except that I somehow messed up the name. I wasn't sure of what this method was doing.

[dlucas]

Replying to arpitdm:

Replying to dlucas:

• For now, there's nothing related to skew polynomials in the index file, so it won't be possible for the user to access the documentation through the online reference manual. Can you please add a dedicated section in the related index file? See src/doc/en/reference/polynomial_rings/index.rst.

I read up a little on Sphinx documentation and from what I understand, I need to add the following in the file you mentioned, right?

@sage.misc.superseded.experimental(trac_number=13215)
Skew Polynomials
----------------

.. toctree::
   :maxdepth: 2

   sage/rings/polynomial/skew_polynomial_element
   sage/rings/polynomial/skew_polynomial_ring_constructor
   sage/rings/polynomial/skew_polynomial_ring

Yup! I you're not sure of what you're doing, here's a way to test it: run sage --docbuild src/doc/en/reference/polynomial_rings html, it will compile the doc and give you an address. Copy-paste this address in your browser, and click on "index" in the page which opens. If what you added in index.rst works, you should see it here (and you'll be able to check its formatting as well).

• I would also use the experimental decorator here: the code in itself seems stable, but it will allow us to make later name changes (for instance) without putting deprecation warnings all over the place. In particular, I have in mind later implementations of sparse rings and multivariate rings, which might trigger some renaming in the classes implemented here.

Placing the experimental warning (like I did above) is not the right way to do it because it does not throw an error. Do I instead place this line at the start of every class in all the three files instead?

Mmh, I reconsidered my position on this thanks to Travis' comment: as we'll not change the public API (which is the method in skew_polynomial_ring_constructor.py), I don't think it's necessary to put experimental warnings everywhere, as long as we're future proof as Travis suggests.

• Can you please explicit what LHS/RHS means?

Like @tscrim mentions, I think LHS/RHS are extremely common terms that are used almost everywhere and perhaps don't need explicit description.

Yes, you're both right, let's drop that and keep LHS/RHS.

• There's an option sparse=False which, if set to True, returns a NotImplementedError. I suggest to remove it for now in order to not confuse the user, and reinstate it later when it will be fully implemented. In this case, also remove all references to this feature in the documentation.

There are a lot of places where a NotImplementedError? is raised and not just in this ticket but in other polynomial files as well. I think it makes more sense to have them if they are already there. However, there is then the inconsistency in that derivations in skew polynomials are not implemented and are marked as todo as is the multivariate case in some places. Still, I argue for keeping sparse as it is since it is integrated in the framework already unlike the other two. And with the experimental warning showing up, changing this will not create too much trouble.

Yes, thinking again about it, I think you're both right. It's better to be future proof, and if it's used elsewhere in polynomials, there's definitely no trouble in doing so.

• INPUT block could be enhanced: I would rather explain what's name (or variable_names if you agree with my comment above) instead of just saying "a string". I would also rename sigma to something more indicative. What about base_ring_endomorphism?

An endomorphism that admits an inverse is an automorphism and skew polynomial rings AFAIK are based on automorphisms. Please correct me if I'm mistaken in this. If so, the places where it says that the twist map is not invertible, maybe should say that twist map should be invertible. And accordingly, the name can be changed to base_ring_automorphism.

Err, yes my bad. base_ring_automorphism sounds good :)

• Some imports are not necessary anymore, e.g. import sage.misc.latex as latex.

I tried to do that with the ones I thought were not needed/deprecated. I've obviously missed a few. I'll go over this once again.

Don't worry, it's quite tricky.

• Some methods here do not follow the mandatory documentation template. For instance, __init__ does not have a short description, nor an INPUT block...

Is there a reference doc or something where I can go through the mandatory documentation template? Or is it that Description, Input, Output, Examples, Tests - should these be present for every method? A lot of places, it doesn't make sense to have all of this.

You can read this ​tutorial for Sage developers. But I agree this is not strong rules: while I do follow the "short description, jump line, optional long description" for my methods, I only write an OUTPUT block when the output is not obvious from reading the short description. I always write an INPUT block when there's input arguments, as I think that even if the names of the input arguments seems obvious, it's always nice to have an explicit definition. EXAMPLES are of course mandatory. TESTS are not, I think you should only use them when you want to run a few more tests which do not really make sense for the user. For instance, I use TESTS to doctest sanity checks. It's nice to add a doctest to ensure everything is sanitized, but it's of little interest for the user.

• In some methods, documentation is not really helpful: see twist_map for instance. not have a short description, while make_generic_skew_polynomial does not have documentation at all!

Oh right! I mentioned this in the email thread with Johan except that I somehow messed up the name. I wasn't sure of what this method was doing.

Oh ok! I'll read it and try to understand what it does.

Best,

David

[arpitdm]

Replying to dlucas:

Replying to arpitdm:

Replying to dlucas:

• For now, there's nothing related to skew polynomials in the index file, so it won't be possible for the user to access the documentation through the online reference manual. Can you please add a dedicated section in the related index file? See src/doc/en/reference/polynomial_rings/index.rst.

I read up a little on Sphinx documentation and from what I understand, I need to add the following in the file you mentioned, right?

@sage.misc.superseded.experimental(trac_number=13215)
Skew Polynomials
----------------

.. toctree::
   :maxdepth: 2

   sage/rings/polynomial/skew_polynomial_element
   sage/rings/polynomial/skew_polynomial_ring_constructor
   sage/rings/polynomial/skew_polynomial_ring

Yup! I you're not sure of what you're doing, here's a way to test it: run sage --docbuild src/doc/en/reference/polynomial_rings html, it will compile the doc and give you an address. Copy-paste this address in your browser, and click on "index" in the page which opens. If what you added in index.rst works, you should see it here (and you'll be able to check its formatting as well).

That command you mentioned didn't work. I get the following error message.

'src/doc/en/reference/polynomial_rings' is not a recognized document. Type 'sage --docbuild -D' for a list
of documents, or 'sage --docbuild --help' for more help.

I've made the other changes according to the discussions above.

[jsrn]

Replying to tscrim:

It is okay to change class names as long as the public API doesn't change (although this can entail unpickling issues in either case). I would instead future-proof this by

Was there supposed to be some ending of this sentence?

• There's an option sparse=False which, if set to True, returns a NotImplementedError. I suggest to remove it for now in order to not confuse the user, and reinstate it later when it will be fully implemented. In this case, also remove all references to this feature in the documentation.
• As I suggest to remove some not implemented but planned features, it might be a good idea to add a TODO block as a reminder of these features (sparse rings, multivariate rings).

I disagree with these comments. This is documenting an upcoming feature, it helps keeps the API consistent with future plans and other parts of Sage, and tells someone reading the code what is currently not implemented.

This is debatable: sparse skew polynomials are not very useful whenever there is a derivation (since sparsity is not retained well across operations), and it's not very clear what a multivariate skew ring is. The most natural generalisation of this structure is Ore polynomials, but that would likely be a separate class. I don't think it makes sense to leave implementation artifacts that will, most likely, never lead to real implementations. In the odd case that they *would* lead to implementations, we could reinstate them with no penalty.

Also, from a cursory glance, there seems to be a lot of duplication with the current implementations of polynomials (i.e., the elements). I feel there could be a lot of simplification of the code by either subclassing or creating a mix-in (cython) class that overrides the _mul_ of polynomials. Is there a reason why you didn't do this? This might entail doing some refactoring/abstracting of the polynomial code though, but it should make the implementation of skew polynomials a lot easier (and bug proof).

That's arguably true. To be fair: Xavier Caruso made the code, and Arpit just tried to get it into shape with less than full-rewrite-workload. That said, I would be concerned about subclassing commutative classes that commutative-only code creeps into the skew polynomials: for instance if someone later on adds a method to the parent class and forgets to explicitly overwrite or remove this method in the skew polynomial class. It's really only all the basics that are shared btw commutative/non-commutative: all the substantial and complex properties are not shared at all.

[jsrn]

Replying to jsrn:

This is debatable: sparse skew polynomials are not very useful whenever there is a derivation (since sparsity is not retained well across operations),

Oh, I just remembered that this patch doesn't provide skew polynomials with derivations :-D So then this comment might be somewhat moot ;-)

The most natural generalisation of this structure is Ore polynomials,

One would perhaps add skew polynomials with derivations before full-fledged Ore rings, though :-)

Best, Johan

[tscrim]

Replying to jsrn:

Replying to tscrim:

It is okay to change class names as long as the public API doesn't change (although this can entail unpickling issues in either case). I would instead future-proof this by

Was there supposed to be some ending of this sentence?

That must of gotten lost when I had connectivity issues. This was suppose to be "by using a consistent API".

Also, from a cursory glance, there seems to be a lot of duplication with the current implementations of polynomials (i.e., the elements). I feel there could be a lot of simplification of the code by either subclassing or creating a mix-in (cython) class that overrides the _mul_ of polynomials. Is there a reason why you didn't do this? This might entail doing some refactoring/abstracting of the polynomial code though, but it should make the implementation of skew polynomials a lot easier (and bug proof).

That's arguably true. To be fair: Xavier Caruso made the code, and Arpit just tried to get it into shape with less than full-rewrite-workload.

I thank them both for working on this and pushing it forward.

That said, I would be concerned about subclassing commutative classes that commutative-only code creeps into the skew polynomials: for instance if someone later on adds a method to the parent class and forgets to explicitly overwrite or remove this method in the skew polynomial class. It's really only all the basics that are shared btw commutative/non-commutative: all the substantial and complex properties are not shared at all.

I don't want to diminish their work, but sometimes after having the code there and looking ahead, major refactoring can be needed. However, there would likely need to be refactoring of the usual commutative polynomials to address the issue you brought up. There could also be ways to factor out common code from other algebras across Sage. So in short, what I'm suggesting is to have a common abstract base class for both for the basic/core functionality. If there is only a little overlap (I really haven't looked), then we can just continue in our current fashion.

[jsrn]

Replying to tscrim:

That must of gotten lost when I had connectivity issues. This was suppose to be "by using a consistent API".

Ah ok. You're right: aim for a good API. I think that the experimental decorator is still a good idea for such a big, brand-new feature, though. That what it was introduced for.

I don't want to diminish their work, but sometimes after having the code there and looking ahead, major refactoring can be needed. However, there would likely need to be refactoring of the usual commutative polynomials to address the issue you brought up. There could also be ways to factor out common code from other algebras across Sage. So in short, what I'm suggesting is to have a common abstract base class for both for the basic/core functionality. If there is only a little overlap (I really haven't looked), then we can just continue in our current fashion.

I agree that this would be nice and should be looked at. However, can I suggest that this is for another ticket (cf. Reviewer's Checklist The perfect is the enemy of the good?​http://doc.sagemath.org/html/en/developer/reviewer_checklist.html).

That way, improvements could progress on both ends (improving code sharing between the polynomial types, while improving skew poly functionality, and the coding theory constructions that we will build using skew polynomials).

[tscrim]

Replying to jsrn:

Replying to tscrim:

That must of gotten lost when I had connectivity issues. This was suppose to be "by using a consistent API".

Ah ok. You're right: aim for a good API. I think that the experimental decorator is still a good idea for such a big, brand-new feature, though. That what it was introduced for.

In this case we have very similar features that we have had for a long time, in addition to a certain amount of stability with the code. By that, I think we shouldn't scare users with such a warning.

I don't want to diminish their work, but sometimes after having the code there and looking ahead, major refactoring can be needed. However, there would likely need to be refactoring of the usual commutative polynomials to address the issue you brought up. There could also be ways to factor out common code from other algebras across Sage. So in short, what I'm suggesting is to have a common abstract base class for both for the basic/core functionality. If there is only a little overlap (I really haven't looked), then we can just continue in our current fashion.

I agree that this would be nice and should be looked at. However, can I suggest that this is for another ticket (cf. Reviewer's Checklist The perfect is the enemy of the good?​http://doc.sagemath.org/html/en/developer/reviewer_checklist.html).

I'm not asking for perfection. If we do decide to subclass, then it just makes it somewhat harder to refactor once this is included. Just to be clear, I am just raising the question, not making the refactoring a requirement.

That way, improvements could progress on both ends (improving code sharing between the polynomial types, while improving skew poly functionality, and the coding theory constructions that we will build using skew polynomials).

If only I had time... :P

[dlucas]

Replying to arpitdm:

That command you mentioned didn't work. I get the following error message.

'src/doc/en/reference/polynomial_rings' is not a recognized document. Type 'sage --docbuild -D' for a list
of documents, or 'sage --docbuild --help' for more help.

I've made the other changes according to the discussions above.

Oh, my mistake, sage --docbuild reference/polynomial_rings html is enough... By the way, don't forget to rebuild before compiling documentation. If you don't, changes you made to the docstrings/tests since your last rebuild will not be considered.

Best,

David

[arpitdm]

Hi David,

The name and names that we had agreed upon changing to variable_names is giving a problem I did not notice until I was testing stuff today. I think the reason they exist is not just to facilitate multi-variate rings but also to support the diamond bracket notation. S.<x> = SkewPolynomialRing(R, sigma) and without it gives TypeError? (unexpected keyword argument). Also, this is a syntax present in other ring constructors in Sage. And while we don't support multivariate rings for Skew Polynomials, perhaps this feature might be added later on and we do need the diamond notation. Is there an alternate way in Sage to capture the diamond bracket or should we revert back to the original?

[dlucas]

Hello,

Oh, ok I was not aware of that. I tested it on my side, and indeed whenever you use diamond bracket, it expects an argument called names. Xavier's comments on the NOTE block makes sense now.

In that case, what about removing the argument name and keep only names? Then, through input sanitization, allow only string, list containing one string, fail with a specific error if one passes a list with several strings in it explaining multivariate ring is not yet supported, and fail with a generic error message, e.g. "You can only pass a string, or a list of string for input names" otherwise. I think it does the trick.

David

[jsrn]

Replying to tscrim:

In this case we have very similar features that we have had for a long time, in addition to a certain amount of stability with the code. By that, I think we shouldn't scare users with such a warning.

You have a point. The names and conventions are unlikely to change within the limited scope of this ticket. For the follow-up tickets containing the rest of Caruso's code the experimental decorator could be considered.

I'm not asking for perfection. If we do decide to subclass, then it just makes it somewhat harder to refactor once this is included. Just to be clear, I am just raising the question, not making the refactoring a requirement.

I don't think it makes it harder to refactor later on than now: it's exactly the same work, since the full implementation of skew polynomials has already been written, doctested etc. That's one reason I would suggest leaving it for a future ticket.

[tscrim]

Replying to jsrn:

Replying to tscrim:

I'm not asking for perfection. If we do decide to subclass, then it just makes it somewhat harder to refactor once this is included. Just to be clear, I am just raising the question, not making the refactoring a requirement.

I don't think it makes it harder to refactor later on than now: it's exactly the same work, since the full implementation of skew polynomials has already been written, doctested etc. That's one reason I would suggest leaving it for a future ticket.

It just means we have to deal with getting old pickles to work, which might be non-trivial (granted, Sage is not always successful with this).

[tscrim]

You do want to use names:

sage: preparse('R.<x> = PolynomialRing(ZZ)')
"R = PolynomialRing(ZZ, names=('x',)); (x,) = R._first_ngens(1)"

Some notes on the code from a skim through:

• You seem to be using the exact same format of polynomials, which contains a lot of old code. For example, don't implement a _repr_() that just calls (a Python function) _repr(). This is useless (even in the usual polynomial ring code it seems); instead just implement _repr_(). Similarly, there are a number of methods you could simply cpdef.
• Kill with fire and holy water is_* methods. They just trivially call isinstance.
• You can use

  self._no_generic_basering_coercion = True
  

  to avoid constructing the coercion from the base ring when initializing the skew polynomial ring.
• _cmp_ is planned to be removed. Use _richcmp_ instead.
• You should lazy import the ring constructor.
• You are double importing things in the element class; only keep the cimport's.

[jsrn]

Hi Travis,

You seem to understand these things quite well, and we had quite some problems with getting this code to work, so could you please elaborate on the following things:

Replying to tscrim:

• You seem to be using the exact same format of polynomials, which contains a lot of old code. For example, don't implement a _repr_() that just calls (a Python function) _repr(). This is useless (even in the usual polynomial ring code it seems); instead just implement _repr_(). Similarly, there are a number of methods you could simply cpdef.

That would be great. Can you give us the full list of the methods for which we can do this, or point us to how we can figure it out?

• You can use

  self._no_generic_basering_coercion = True
  

  to avoid constructing the coercion from the base ring when initializing the skew polynomial ring.

To be precise, do you mean that can insert the above line in SkewPolynomialRing_general.__init__ just before the call to Algebra.__init__, and then remove the call to self._unset_coercions_used()? Or is there more to it?

• _cmp_ is planned to be removed. Use _richcmp_ instead.

Are you talking about SkewPolynomial._cmp_? We spent many hours debugging the comparison code because it threw strange errors and segfaults. To avoid me spending many more hours, could I ask you to tell us exactly how to write the correct comparison code then?

Simon King's tutorial on implementing algebraic structures should be updated to be more informative on this, I think.

• You should lazy import the ring constructor.

Do you mean sage.rings.ring in skew_polynomial_ring.py? Why is exactly that one important to lazily import?

Thanks for the help!

Best, Johan

[arpitdm]

Replying to tscrim: To add to what Johan is asking,

• Kill with fire and holy water is_* methods. They just trivially call isinstance.

Which "is_" methods are you referring to? I couldn't really find any that call isinstance directly apart from the is_SkewPolynomialRing. For example, is_finite returns true if the base ring is finite and has order 1 and false otherwise. And so on. Each have minor conditions that the user could of course check themselves if need be, but its not always a one line call and its not always obvious what methods are available to the user so that they may verify. Should such methods then still be removed?

• You are double importing things in the element class; only keep the cimport's.

Could you elaborate with a tiny example or something what you mean by this?

Again, thank you for your help!

Best, Arpit.

[tscrim]

Replying to arpitdm:

Replying to tscrim: To add to what Johan is asking,

• Kill with fire and holy water is_* methods. They just trivially call isinstance.

Which "is_" methods are you referring to? I couldn't really find any that call isinstance directly apart from the is_SkewPolynomialRing. For example, is_finite returns true if the base ring is finite and has order 1 and false otherwise. And so on. Each have minor conditions that the user could of course check themselves if need be, but its not always a one line call and its not always obvious what methods are available to the user so that they may verify. Should such methods then still be removed?

Sorry, I misspoke slightly. It is the is_* functions, which as you say are things like is_SkewPolynomialRing.

• You are double importing things in the element class; only keep the cimport's.

Could you elaborate with a tiny example or something what you mean by this?

You should make this change:

-from sage.structure.element import Element, AlgebraElement
 from sage.structure.element cimport Element, AlgebraElement, ModuleElement
 from sage.structure.parent cimport Parent
-from polynomial_compiled import CompiledPolynomialFunction
 from polynomial_compiled cimport CompiledPolynomialFunction

[tscrim]

Replying to jsrn:

Replying to tscrim:

• You seem to be using the exact same format of polynomials, which contains a lot of old code. For example, don't implement a _repr_() that just calls (a Python function) _repr(). This is useless (even in the usual polynomial ring code it seems); instead just implement _repr_(). Similarly, there are a number of methods you could simply cpdef.

That would be great. Can you give us the full list of the methods for which we can do this, or point us to how we can figure it out?

Anything python method (a def) which only calls a cdef method. Another example is list calling _list_c. IIRC, you can't do this for __hash__ because this is a Python special method. I think _list_c is the only other one (and you can replace this by just calling the attribute __coeffs).

• You can use

  self._no_generic_basering_coercion = True
  

  to avoid constructing the coercion from the base ring when initializing the skew polynomial ring.

To be precise, do you mean that can insert the above line in SkewPolynomialRing_general.__init__ just before the call to Algebra.__init__, and then remove the call to self._unset_coercions_used()? Or is there more to it?

Yes, exactly.

• _cmp_ is planned to be removed. Use _richcmp_ instead.

Are you talking about SkewPolynomial._cmp_? We spent many hours debugging the comparison code because it threw strange errors and segfaults. To avoid me spending many more hours, could I ask you to tell us exactly how to write the correct comparison code then?

You can look at src/sage/rings/real_arb.pyx or src/sage/rings/real_double.pyx for example. We can include the _cmp_ as it is now, but it means some more hardship when we finally start converting.

Simon King's tutorial on implementing algebraic structures should be updated to be more informative on this, I think.

Yes, it should be. It was written before we really had to worry about going to Python3.

• You should lazy import the ring constructor.

Do you mean sage.rings.ring in skew_polynomial_ring.py? Why is exactly that one important to lazily import?

It is the thing which imports the rest of the code (once the is_* functions are gone). So all of the other files are not imported on startup, which helps keep that down because this is not a "common" object that the average user will use (IMO).

Thanks for the help!

Thank you for the good discussions and work.

[git]

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

​1f62ef4	added a section related to skew polynomils in the index file.
​abbd05e	removed double imports and unused classes and methods
​8b337c5	improved description of module, definition of skew polynomial, removed unnecessary imports, improved informativeness of docstrings, input sanitization and documentation of a couple of methods.
​e0f3f42	changes to incorporate merging and into
​0c8f6ec	removed unnecessary imports
​0641ecf	improved description of module, definition of skew polynomial ring, removed unnecessary imports, improved informativeness of docstrings, input sanitization and documentation of some methods. cleaned up code.
​22eab5d	same as previous commit

[arpitdm]

Stuff fixed in the commits above based on latest set of discussions:

1. Improved descriptions for element, ring and ring constructor files
2. Improved definitions.
3. Input sanitization and INPUT block for init methods
4. name and names merged into a single names argument.
5. Improved documentation and tests for twist_map, make_generic_skew_polynomial` and other such methods.
6. Removed all functions that trivially called isinstance. Merged _repr_ and _repr into _repr_.
7. Improved call to coercion, removed double imports, removed unnecessary imports. Added lazy import where possible.
8. Solving any doctests that came up in the course of the aforementioned changes.

Please let me know if I have missed something and of course any other changes that ought to be made. I'm now opening this for review.

[jsrn]

Sounds great!

Did you look at the _cmp_ thing that Travis brought up? Best, Johan

[dlucas]

Hello,

Good work on docstrings and module documentation, it's much better now. However, I have some comments:

• documentation does not compile: it seems you have some formatting errors in bullet lists.
• you used single backquote notation at some places in the documentation where it should be double backquotes, e.g. in SkewPolynomial class, you wrote self between single backquotes (which triggers LaTeX formatting) instead of double.
• a few lines below, default: False, False should be between double backquotes.
• you kept the import import sage.misc.latex as latex. I'm quite sure you can remove it, but in that case, you'll have to change latex.latex(self.base_ring()) to self.base_ring()._latex_() (l. 359, skew_polynomial_ring.py). There's probably some more to change.

Apart from that, it looks good to me. Patchbot says some doctests fails, but according to which doctests are failing, I'm quite sure it's not because of this ticket.

Best,

David

[git]

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

​1c717db	resolved single and double back tick formatting inconsistencies.
​6f4d80a	resolved back tick inconsistencies from other files
​dc5fb56	replaced method _cmp_ with _richcmp_. removed latex import.

[arpitdm]

I think I managed to replace the _cmp_ method with _richcmp_. Please let me know if I did it incorrectly or something. Back tick inconsistencies are resolved. The latex import in skew_polynomial_element.pyx was removable, but the skew_polynomial_ring did not allow it. It threw up errors and I think its because the latex method of the self._map does not support it.

Also, I don't understand what is going wrong when I try to build the documentation. I can't find any indentation errors.

[polynomia] loading pickled environment... not yet created
[polynomia] WARNING: intersphinx inventory '/home/arpit/Documents/GSOC_16/sage/local/share/doc/sage/inventory/en/reference/objects.inv' not fetchable due to <type 'exceptions.IOError'>: [Errno 2] No such file or directory: '/home/arpit/Documents/GSOC_16/sage/local/share/doc/sage/inventory/en/reference/objects.inv'
[polynomia] docstring of sage.rings.polynomial.skew_polynomial_element:16: WARNING: Literal block expected; none found.
[polynomia] docstring of sage.rings.polynomial.skew_polynomial_element:20: WARNING: Definition list ends without a blank line; unexpected unindent.
[polynomia] docstring of sage.rings.polynomial.skew_polynomial_element:30: WARNING: Literal block expected; none found.
[polynomia] docstring of sage.rings.polynomial.skew_polynomial_element.SkewPolynomial.left_gcd:11: WARNING: Bullet list ends without a blank line; unexpected unindent.
[polynomia] docstring of sage.rings.polynomial.skew_polynomial_element.SkewPolynomial.left_lcm:11: WARNING: Bullet list ends without a blank line; unexpected unindent.
[polynomia] docstring of sage.rings.polynomial.skew_polynomial_element.SkewPolynomial.left_xgcd:11: WARNING: Bullet list ends without a blank line; unexpected unindent.
[polynomia] docstring of sage.rings.polynomial.skew_polynomial_element.SkewPolynomial.right_gcd:11: WARNING: Bullet list ends without a blank line; unexpected unindent.
[polynomia] docstring of sage.rings.polynomial.skew_polynomial_element.SkewPolynomial.right_lcm:11: WARNING: Bullet list ends without a blank line; unexpected unindent.
[polynomia] docstring of sage.rings.polynomial.skew_polynomial_element.SkewPolynomial.right_xgcd:11: WARNING: Bullet list ends without a blank line; unexpected unindent.
[polynomia] docstring of sage.rings.polynomial.skew_polynomial_element.make_generic_skew_polynomial:12: WARNING: Literal block expected; none found.
[polynomia] /home/arpit/Documents/GSOC_16/sage/local/lib/python2.7/site-packages/sage/rings/polynomial/skew_polynomial_ring_constructor.py:docstring of sage.rings.polynomial.skew_polynomial_ring_constructor.SkewPolynomialRing:70: WARNING: Literal block expected; none found.
[polynomia] /home/arpit/Documents/GSOC_16/sage/local/lib/python2.7/site-packages/sage/rings/polynomial/skew_polynomial_ring_constructor.py:docstring of sage.rings.polynomial.skew_polynomial_ring_constructor.SkewPolynomialRing:105: WARNING: Literal block expected; none found.
[polynomia] /home/arpit/Documents/GSOC_16/sage/local/lib/python2.7/site-packages/sage/rings/polynomial/multi_polynomial_sequence.py:docstring of sage.rings.polynomial.multi_polynomial_sequence:3: WARNING: citation not found: CMR05
[polynomia] Exception occurred:
[polynomia] File "/home/arpit/Documents/GSOC_16/sage/src/sage_setup/docbuild/ext/multidocs.py", line 286, in link_static_files
[polynomia] os.symlink(master_static_dir, static_dir)
[polynomia] OSError: [Errno 17] File exists
[polynomia] The full traceback has been saved in /tmp/sphinx-err-IsQg2Y.log, if you want to report the issue to the developers.
[polynomia] Please also report this if it was a user error, so that a better error message can be provided next time.
[polynomia] A bug report can be filed in the tracker at <https://github.com/sphinx-doc/sphinx/issues>. Thanks!
Error building the documentation.
Traceback (most recent call last):
  File "/home/arpit/Documents/GSOC_16/sage/local/lib/python/runpy.py", line 162, in _run_module_as_main
    "__main__", fname, loader, pkg_name)
  File "/home/arpit/Documents/GSOC_16/sage/local/lib/python/runpy.py", line 72, in _run_code
    exec code in run_globals
  File "/home/arpit/Documents/GSOC_16/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__main__.py", line 2, in <module>
    main()
  File "/home/arpit/Documents/GSOC_16/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 1629, in main
    builder()
  File "/home/arpit/Documents/GSOC_16/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 710, in _wrapper
    getattr(DocBuilder, build_type)(self, *args, **kwds)
  File "/home/arpit/Documents/GSOC_16/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 103, in f
    runsphinx()
  File "/home/arpit/Documents/GSOC_16/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/sphinxbuild.py", line 215, in runsphinx
    raise exception
OSError: [polynomia] WARNING: intersphinx inventory '/home/arpit/Documents/GSOC_16/sage/local/share/doc/sage/inventory/en/reference/objects.inv' not fetchable due to <type 'exceptions.IOError'>: [Errno 2] No such file or directory: '/home/arpit/Documents/GSOC_16/sage/local/share/doc/sage/inventory/en/reference/objects.inv'


Note: incremental documentation builds sometimes cause spurious
error messages. To be certain that these are real errors, run
"make doc-clean" first and try again.

[dlucas]

Well, I don't know what happens... Here's what I have on my local machine:

[polynomia] docstring of sage.rings.polynomial.skew_polynomial_element:16: WARNING: Literal block expected; none found.
[polynomia] docstring of sage.rings.polynomial.skew_polynomial_element:20: WARNING: Definition list ends without a blank line; unexpected unindent.
[polynomia] docstring of sage.rings.polynomial.skew_polynomial_element:30: WARNING: Literal block expected; none found.
[polynomia] docstring of sage.rings.polynomial.skew_polynomial_element.SkewPolynomial.left_gcd:11: WARNING: Bullet list ends without a blank line; unexpected unindent.
[polynomia] docstring of sage.rings.polynomial.skew_polynomial_element.SkewPolynomial.left_lcm:11: WARNING: Bullet list ends without a blank line; unexpected unindent.
[polynomia] docstring of sage.rings.polynomial.skew_polynomial_element.SkewPolynomial.left_xgcd:11: WARNING: Bullet list ends without a blank line; unexpected unindent.
[polynomia] docstring of sage.rings.polynomial.skew_polynomial_element.SkewPolynomial.right_gcd:11: WARNING: Bullet list ends without a blank line; unexpected unindent.
[polynomia] docstring of sage.rings.polynomial.skew_polynomial_element.SkewPolynomial.right_lcm:11: WARNING: Bullet list ends without a blank line; unexpected unindent.
[polynomia] docstring of sage.rings.polynomial.skew_polynomial_element.SkewPolynomial.right_xgcd:11: WARNING: Bullet list ends without a blank line; unexpected unindent.
[polynomia] docstring of sage.rings.polynomial.skew_polynomial_element.make_generic_skew_polynomial:12: WARNING: Literal block expected; none found.
[polynomia] /home/david/Desktop/sage/local/lib/python2.7/site-packages/sage/rings/polynomial/skew_polynomial_ring_constructor.py:docstring of sage.rings.polynomial.skew_polynomial_ring_constructor.SkewPolynomialRing:73: WARNING: Literal block expected; none found.
[polynomia] /home/david/Desktop/sage/local/lib/python2.7/site-packages/sage/rings/polynomial/skew_polynomial_ring_constructor.py:docstring of sage.rings.polynomial.skew_polynomial_ring_constructor.SkewPolynomialRing:108: WARNING: Literal block expected; none found.
Error building the documentation.
Traceback (most recent call last):
  File "/home/david/Desktop/sage/local/lib/python/runpy.py", line 162, in _run_module_as_main
    "__main__", fname, loader, pkg_name)
  File "/home/david/Desktop/sage/local/lib/python/runpy.py", line 72, in _run_code
    exec code in run_globals
  File "/home/david/Desktop/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__main__.py", line 2, in <module>
    main()
  File "/home/david/Desktop/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 1630, in main
    builder()
  File "/home/david/Desktop/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 710, in _wrapper
    getattr(DocBuilder, build_type)(self, *args, **kwds)
  File "/home/david/Desktop/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 103, in f
    runsphinx()
  File "/home/david/Desktop/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/sphinxbuild.py", line 215, in runsphinx
    raise exception
OSError: [polynomia] docstring of sage.rings.polynomial.skew_polynomial_element:16: WARNING: Literal block expected; none found.

This is the kind of error sphinx returns when there's no blank line after a bullet list. Usually, it's because you did not indented properly if you put several lines in a single bullet. It should be like this:

- my first line
  and my second line

so it's not 4 whitespaces, it has to be aligned with the first character of the line above.

Anyway, for your issues, I'd say run make doc-clean and make.

David

[git]

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

​54099ac	fixed errors that came up while building documentation
​0de3552	reference for CMR05 was missing from the docs in multi_polynomial_sequence.py file. Added that.

[arpitdm]

Hi David,

I finally managed to make sense of the error messages that were showing up in the documentation. For instance, [polynomia] docstring of sage.rings.polynomial.skew_polynomial_element:16: WARNING: Literal block expected; none found.

Represents some error in the 16th line of the documentation of the file and so on..

And like you suggested, one set of errors was because it indented incorrectly. Anyway, I think I've solved all the issues (docs build successfully on my system) and I do get a path to all the html files. Can you please confirm this?

[dlucas]

Hello,

I finally managed to make sense of the error messages that were showing up in the documentation. For instance, [polynomia] docstring of sage.rings.polynomial.skew_polynomial_element:16: WARNING: Literal block expected; none found.

Oh, sorry, I thought you knew how to read these! Otherwise, I would have told you... It's not the most intuitive error message for sure, and I had some troubles with Sphinx compiler messages when I started working on Sage :).

I just pulled your branch and I'm recompiling the reference manual. If everything goes smoothly, I don't have other remarks, so if Johan and Travis agree, we can set this to positive_review.

[dlucas]

And it worked just fine. So, documentation compiles, tests passes, you fixed what we asked you to, I'm fine with it. If no one objects, I'll set this to positive_review.

David

[tscrim]

The important thing is the first comment. The rest is more polish, but I think a fair amount more is needed.

• All methods and functions must have doctests (e.g., the one added to map.pyx and hidden methods). Also, I think you should remove the commented out code.
• You should remove this line from module_list.py:

  # depends = numpy_depends),
  

• I would swap these lines in rings.py:

              
  -            from sage.categories.morphism import Morphism
               if isinstance(arg, tuple):
  +                from sage.categories.morphism import Morphism
                   if len(arg) == 2 and isinstance(arg[1], Morphism):
                      from sage.rings.polynomial.skew_polynomial_ring_constructor import SkewPolynomialRing
                      return SkewPolynomialRing(self, arg[1], names=arg[0])
                   
  

• Remove all trailing whitespace (well, at least do not add any).
• In skew_polynomial_element.pyx, there are a number of things that need to be in latex mode (and an equation using the .. MATH:: block).
• I would move most-to-all of the module-level doc to the user entry point and then have a .. SEEALSO:: block referencing said doc, so it is visible from the ? on the command line. This also applies to the parent class(es?) (i.e. module-level to class-level).
• You should make list into a cpdef with an output type of list and remove _list_c.
• For __iter__, just iterate over self.__coeffs. Actually, a similar statement applies to many other places you call _list_c where you don't expose it to the user or modify the list (e.g., __getitem__ and _richcmp_. The multivariate and sparse versions should be overriding these methods anyways.
• You should use the cached version of 0 instead of going through coercion and getting a new object in memory:

           try:
               l = (<SkewPolynomial>self)._list_c()[n]
               return l
           except IndexError:
  -            c = self.base_ring()(0)
  -            return c
  +            return self.base_ring().zero()
  

• Use Python3 syntax for errors: raise IndexError("skew polynomials are immutable").
• Similar to above: self.parent()(0) -> self.parent().zero().
• is_nilpotent should have a short description of what the method should do (as well as the intended operation).
• Returns -> Return in a few first-line of docstrings.
• .. Note:: -> .. NOTE:: (this is a consistency thing).
• You have a blank .. SEEALSO:: in __floordiv__.
• is_left_divisible_by doesn't have a short description. Similar for other such methods.
• Error messages should start with a lowercase letter (this was something we've agreed upon in somewhat more recent history).
• There is a preference to have ``True`` in code formatting since it is a Python object/concept.
• Actually, a number of functions that use _list_c should be moved to the concrete class (and maybe an @abstract_method placeholder done in the ABC.

I might have some more comments later too. However this is looking very good and it will be a great addition to Sage.

Also, the _richcmp_ looks correct (although I don't have time right now to run any serious tests).

[jsrn]

The implemented operator evaluation __call__ is incorrect. For instance, 1(a) = a and x(a) = sigma(a) in a correct implementation, but that is not the case here. The following implementation works:

    if eval_pt not in self._parent:
        raise TypeError("Evaluation point must be a ring element")
    sigma = self._parent.twist_map()
    coefficients = self.coefficients(sparse=False)
    sum = self._parent.zero()
    a = eval_pt
    for c in coefficients:
        sum += c * a
        a = sigma(a)
    return sum

I think we should make an effort to cythonize this method. Could you try that Arpit?

Best, Johan

[git]

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

​35364a9	removed commented code. added documentation and test for :meth: inverse.
​cede096	removed commented line of code.
​17450fa	import of Morphism moved to inside of statement so that it acts like a lazy import.
​5a36953	removed all trailing whitespaces. removed commented code from skew_polynomial_element.pxd.
​bd45351	converted to Python3 syntax for errors. edited error messages to start with lower case letters.
​c203856	code formatting for True, False and None Python objects. added latex typsetting in docs. added descriptions for some methods that didn't have them.
​b52fc95	using cached versions of 0 and 1 wherever applicable.
​6fb186a	changed Returns to Return and Note to NOTE for consistency. Removed trailing whitespaces. codeformatting for True, False and None objects.

[arpitdm]

Replying to tscrim:

• All methods and functions must have doctests (e.g., the one added to map.pyx and hidden methods). Also, I think you should remove the commented out code.

I am still going over the methods to check whether there are any remaining. And I still have some commented code to remove.

• I would move most-to-all of the module-level doc to the user entry point and then have a .. SEEALSO:: block referencing said doc, so it is visible from the ? on the command line. This also applies to the parent class(es?) (i.e. module-level to class-level).

Could you please explain with an example maybe, what this means? Or maybe refer me to some method in some file from where I can read and understand.

• You should make list into a cpdef with an output type of list and remove _list_c.

class SkewPolynomial_general inherits from class SkewPolynomial. The _list_c method is implemented in the former while in the latter it is not. Are you suggesting that I remove _list_c from both classes and only have a cpdef list list(self) in the latter class?

• For __iter__, just iterate over self.__coeffs. Actually, a similar statement applies to many other places you call _list_c where you don't expose it to the user or modify the list (e.g., __getitem__ and _richcmp_. The multivariate and sparse versions should be overriding these methods anyways.

There is no __coeffs attribute in class SkewPolynomial and it is actually defined in class SkewPolynomial_general. Is it Python convention to access from one class, an attribute with double leading underscores of another class? If so, what is the correct way of doing that?

• Actually, a number of functions that use _list_c should be moved to the concrete class (and maybe an @abstract_method placeholder done in the ABC.

Could you please elaborate a little what you mean by this? I'm not sure I follow.

[arpitdm]

Replying to jsrn:

The implemented operator evaluation __call__ is incorrect. For instance, 1(a) = a and x(a) = sigma(a) in a correct implementation, but that is not the case here. The following implementation works:

Oh! I now recall having this discussion before. Thank you for pointing it out again.

I think we should make an effort to cythonize this method. Could you try that Arpit?

Yup. On it. :)

Best, Arpit

[tscrim]

Replying to arpitdm:

Replying to tscrim:

• I would move most-to-all of the module-level doc to the user entry point and then have a .. SEEALSO:: block referencing said doc, so it is visible from the ? on the command line. This also applies to the parent class(es?) (i.e. module-level to class-level).

Could you please explain with an example maybe, what this means? Or maybe refer me to some method in some file from where I can read and understand.

I would make a change like this:

 """
 Top/Module-level
 
-Description
 """
 class Foo:
     """
     Class-level.
+
+    Description
     """

That way when you do Foo?, you get Description. You also want some cross-linking so that someone using the online doc has links to follow to get to Description.

• You should make list into a cpdef with an output type of list and remove _list_c.

class SkewPolynomial_general inherits from class SkewPolynomial. The _list_c method is implemented in the former while in the latter it is not. Are you suggesting that I remove _list_c from both classes and only have a cpdef list list(self) in the latter class?

• For __iter__, just iterate over self.__coeffs. Actually, a similar statement applies to many other places you call _list_c where you don't expose it to the user or modify the list (e.g., __getitem__ and _richcmp_. The multivariate and sparse versions should be overriding these methods anyways.

There is no __coeffs attribute in class SkewPolynomial and it is actually defined in class SkewPolynomial_general. Is it Python convention to access from one class, an attribute with double leading underscores of another class? If so, what is the correct way of doing that?

Don't make it double underscore (you can also do the explicit name-mangling). In general, I avoid double underscores so you can use the hidden attributes in subclasses (unless you really wanted it to be completely hidden from all subclasses, which is very rare).

• Actually, a number of functions that use _list_c should be moved to the concrete class (and maybe an @abstract_method placeholder done in the ABC.

Could you please elaborate a little what you mean by this? I'm not sure I follow.

ABC = Abstract Base Class, so the methods you have that just raise a NotImplementedError (e.g., _inplace_add), you should have them be blank (modulo a docstring and a doctest of a concrete implementation) with a @abstract_method. These then get picked up by a failure of the TestSuite.

[git]

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

​1204f2d	the current implementation of the :meth: __call__ was incorrect. added the correct and cythonized version.
​7e076fa	moved module level docs to user entry point at the class level so that they are accessible at command line. added a SEEALSO block.
​69fecc4	converted :meth: into a cpdef method with output type list. removed and directly use the attribute.
​271bfac	removed some commented code and trailing whitespaces.

[arpitdm]

Replying to tscrim:

• Actually, a number of functions that use _list_c should be moved to the concrete class (and maybe an @abstract_method placeholder done in the ABC.

Could you please elaborate a little what you mean by this? I'm not sure I follow.

ABC = Abstract Base Class, so the methods you have that just raise a NotImplementedError (e.g., _inplace_add), you should have them be blank (modulo a docstring and a doctest of a concrete implementation) with a @abstract_method. These then get picked up by a failure of the TestSuite.

I tried adding the @abstract_method to the cdef void _inplace_add method and I got an error message saying "Cdef functions/classes cannot take arbitrary decorators." According to ​their docs, I don't think decorators are implemented yet.

[tscrim]

Oh, I missed that they were cdef methods. I don't think you need to declare anything for them for ABCs, but I am not completely sure if Cython allows this.

[dlucas]

Hello,

Some doctests are still missing. If you're not sure you documented everything, use the following command: sage -coverage <path_to_files>. On my side, it returns:

david@david:~/Desktop/sage/src/sage/rings/polynomial$ sage -coverage skew_polynomial_*
------------------------------------------------------------------------
SCORE skew_polynomial_element.pyx: 97.4% (76 of 78)

Missing doctests:
     * line 327: cpdef SkewPolynomial _new_constant_poly(self, RingElement a, Parent P, char check=0)
     * line 892: def is_nilpotent(self)

Possibly wrong (function name doesn't occur in doctests):
     * line 2434: def mod(self, other)
     * line 3129: cpdef Element _call_with_args(self, x, args=(), kwds={})
------------------------------------------------------------------------
SCORE skew_polynomial_ring_constructor.py: 100.0% (1 of 1)
------------------------------------------------------------------------
SCORE skew_polynomial_ring.py: 78.9% (15 of 19)

Missing documentation:
     * line 129: def __classcall__(cls, base_ring, map, name=None, sparse=False, element_class=None)

Missing doctests:
     * line 191: def __reduce__(self)
     * line 514: def parameter(self)
     * line 567: def is_sparse(self)

Also, documentation does not compile:

sage.rings.polynomial.skew_polynomial_ring.SkewPolynomialRing_general:53: 
WARNING: Block quote ends without a blank line; unexpected unindent.

• line 872 in skew_polynomial_element.pyx, I think it would be better to return an error message with the exception ValueError.

• There are some undocumented methods/classes in skew_polynomial_element.pyx (starting at line 2776 with _left_pow).

• There's still one old style raise statement (l. 494 in skew_polynomial_ring.py).

David

[jsrn]

I fixed a minor issue with src/module_list.py.

---

New commits:

​362fff7	Merge branch 'u/arpitdm/skew_polynomials' of git://trac.sagemath.org/sage into 13215_skew_polynomials
​4a33c5f	mv skew_polynomial_element in module_list

[jsrn]

• Is there any sense to the function make_generic_skew_polynomial? Shouldn't it just be removed? (incidentally, I don't see the sense of sage.rings.polynomial.polynomial_element.make_generic_polynomial either, which presumably was the inspiration to make_generic_skew_polynomial.)

• You created _leftpow_ and _rightpow_ from __pow__ to avoid the optional argument side. But they are not standard magic functions, so there's no sense in them being underscore-methods. Rather, they should be called something different. E.g power_left_mod and power_right_mod, where modulus is now a mandatory argument.

• I'm worried about the _inplace_* methods: they are not doc-tested but are also not indirectly used anywhere (except _inplace_pow which is used in _leftpow and _inplace_rmul which is used in _inplace_pow). I only tried to read _inplace_add yet, but already found one bug (duplicate line `x += y[len(x):]`). I would prefer that these methods be removed, possibly reinstated at a later time when they will be used (and hence at least slightly doctested). I believe they were more arduously used in the Karatsuba or factorisation implementations?

Best, Johan

[arpitdm]

Replying to dlucas:

• line 892: def is_nilpotent(self)

The is_nilpotent method is not implemented since order of the automorphism is not supported in Sage yet. How about if I remove this method completely and place the note instead in def is_unit? Or should I leave it as it is?

Possibly wrong (function name doesn't occur in doctests):

• line 3129: cpdef Element _call_with_args(self, x, args=(), kwds={})

There is a cpdef Element _call_(self, x) method that does exactly the same thing as the above method. Do we need to keep both or can we keep the more general _call_with_args and remove _call_?

[arpitdm]

• Is there any sense to the function make_generic_skew_polynomial? Shouldn't it just be removed? (incidentally, I don't see the sense of sage.rings.polynomial.polynomial_element.make_generic_polynomial either, which presumably was the inspiration to make_generic_skew_polynomial.)

Yup. I believe that was the inspiration. And I agree. If one wants to make a generic skew polynomial using coefficients, it can be directly done without using this method.

• I'm worried about the _inplace_* methods: they are not doc-tested but are also not indirectly used anywhere (except _inplace_pow which is used in _leftpow and _inplace_rmul which is used in _inplace_pow). I only tried to read _inplace_add yet, but already found one bug (duplicate line `x += y[len(x):]`). I would prefer that these methods be removed, possibly reinstated at a later time when they will be used (and hence at least slightly doctested). I believe they were more arduously used in the Karatsuba or factorisation implementations?

Yes. They are used in factorizations and center related methods. Which is why it was not possible to add indirect tests for them either. Alright, removing _inplace_add, _inplace_sub and _inplace_rmul.

[git]

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

​a921040	Changed unfortunate parameter name
​f43767a	Some minor doc and error message modifications
​7c5c511	Modelled SkewPolynomialBaseringInjection more closely on PolynomialBaseringInjection
​d6fd904	Fix Cython warning
​7134b7e	Removed _call_with_args

[jsrn]

I fixed some other stuff that I came across. Most importantly, I changed the parent type of SkewPolynomialBaseringInjection so that it mimics PolynomialBaseringInjection: I'm not fully understanding the extend of what this means, but if PolynomialBaseringInjection should be a Morphism and not a RingHomomorphism, then I don't see why it should be different for SkewPolynomialBaseringInjection.

I also removed _call_with_args: as the name says, it's there for supporting calling an object that takes more than one argument. This makes sense in the very general PolynomialBaseringInjection as the example in the source shows. But it doesn't (yet) make any sense for skew polynomial rings, so I've removed it for now. If it should ever be useful, someone can add it at that time. For now, it will simply throw a (somewhat meaningful) error when one tries to apply more than one argument to a call to a SkewPolynomialBaseringInjection.

[caruso]

Many many thanks (to all of you) for all your hard work on this ticket! I really appreciate it and apologize for being silent for such a long time.

I'm looking forward to seeing you soon in SageDays? 75.

[arpitdm]

New commits:

​d48fea6	fixed documentation errors
​fae0483	fixed documentation
​dfb6b1d	removed unused methods. modified leftpow and rightpow methods.

[jsrn]

There's a bug in right_lcm. I don't yet know what it is but here is an example which makes it blow up:

k.<a> = GF(3^2,'a')
sigma = k.frobenius_endomorphism()
S.<x> = k['x', sigma]
(x^2 + 1*x + a).right_lcm(x - a)
<BOOM>
NotImplementedError: the leading coefficient is not a unit

Since we're over a field, it must be the ZeroDivisionError causing this, which should never happen.

I also don't see why we should catch the ZeroDivisionError: it is never expected behaviour that V3 is 0?

As an aside, the naming in this and related methods is terrible: R means two very different things in 10 lines, and the skew polynomial variables should not be capitalised.

Best, Johan

[caruso]

The problem comes from the multiplication by the skew polynomial 0 which does not work as expected (it returns a polynomial of positive degree):

sage: k.<a> = GF(5^2)
sage: S.<x> = SkewPolynomialRing(k, k.frobenius_endomorphism())
sage: zero = S(0)*x
sage: zero.degree()
1
sage: zero + 1
 + 1

[jsrn]

Thanks Xavier: it turned out that the problem was even with S(0), which got represented as [0] instead of []. I fixed it now and added a test for posterity.

---

New commits:

​291c28c	Fixed construct-0 bug
​ca15975	Fix doctest

[git]

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

​ba6a753

Fix mathematically incorrect doc-string

[jsrn]

Small doc-string fix in the lcm-functions.

[jdemeyer]

Just skimming the code, not a full review...

1. All this

           if op == 0:
               return x < y
           elif op == 1:
               return x <= y
           elif op == 2:
               return x == y
           elif op == 3:
               return x != y
           elif op == 4:
               return x > y
           else:
               return x >= y
   

can be replaced by return PyObject_RichCompare(x, y, op), see src/sage/structure/coerce.pyx for an example.

2. Lots of private methods are unused:

       cdef void _inplace_add(self, SkewPolynomial_generic_dense right)
       cdef void _inplace_sub(self, SkewPolynomial_generic_dense right)
       cdef void _inplace_lmul(self, SkewPolynomial_generic_dense right)
       cpdef _leftpow_(self,right,modulus=*)
   

Since these are private, I see no point in implementing them.

3. The .pxd file contains too much stuff. In particular, the following all seems unused:

   include "cysignals/signals.pxi"
   include "../../ext/cdefs.pxi"
   include '../../ext/stdsage.pxi'
   
   from sage.rings.integer cimport Integer
   from polynomial_compiled cimport CompiledPolynomialFunction
   

Some of this might be needed in .pyx files, but then it should be in the .pyx file. The include statements for cdefs.pxi and stdsage.pxi should be replaced instead by the relevant cimport statements.

4. Use the standard copyright template from ​http://doc.sagemath.org/html/en/developer/coding_basics.html#headings-of-sage-library-code-files

5. __getslice__ is deprecated.

6. __mod__ should use the coercion model (#269).

7. __floordiv__ should use the coercion model (#2034).

8. Replace trac #13215 by :trac:`13215`

9. In several places, you use exact type checks of the form type(x) is foo. Why not isinstance(x, foo)?

[jdemeyer]

10. according to the patchbot, the documentation does not build.

[dlucas]

Hello Jeroen,

10. according to the patchbot, the documentation does not build.

The patchbot might have used an older version of this ticket, because documentation builds just fine on my side.

David

[arpitdm]

Hi Jeroen,

I've made changes to the ticket based on your comments. Please do let me know if I've made a mistake and if there are any other changes I should be making.

Also, as David mentioned, the documentation builds on my system as well. I don't know the patchbot is suggesting otherwise.

Best, Arpit.

---

New commits:

​d48fea6	fixed documentation errors
​fae0483	fixed documentation
​dfb6b1d	removed unused methods. modified leftpow and rightpow methods.
​2ea89c1	merged new updates from remote
​5c9f2f3	modified richcmp method. removed some inplace methods.
​c034df8	removed unused private methods and imports
​ac109c8	converted to standard copyright template
​5137ef9	removed deprecated method getslice
​b1e42c3	Merge commit 'aca3398a81b3688e1f2e69c5910b8214d13be925' of git://trac.sagemath.org/sage into skew_polynomials
​f563aba	mod and floordiv modified to use coercion model. replaced type with isinstance.

[jdemeyer]

Just a remark (feel free to change this or not): there is no point in writing cdef list here since you're not using the fact that it's a list:

        cdef list x = (<SkewPolynomial>left)._coeffs
        cdef list y = (<SkewPolynomial>right)._coeffs
        return PyObject_RichCompare(x, y, op)

In general one should avoid such pointless type declarations.

In this case, it doesn't hurt since Cython knows anyway that it's a list (_coeffs is declared to be a list).

[jdemeyer]

Replying to arpitdm:

I've made changes to the ticket based on your comments. Please do let me know if I've made a mistake and if there are any other changes I should be making.

You forgot to change the copyright statements. Apart from that, it looks ok.

[arpitdm]

Replying to jdemeyer:

Replying to arpitdm:

I've made changes to the ticket based on your comments. Please do let me know if I've made a mistake and if there are any other changes I should be making.

You forgot to change the copyright statements. Apart from that, it looks ok.

By copyright, do you mean add names inside the block too? I added myself and Johan as authors (commit ac109c8)

As for the cdef list, I went with the rest of the code on the ticket which declares things similarly at the time. But I can change that.

[dlucas]

By copyright, do you mean add names inside the block too? I added myself and Johan as authors (commit ac109c8)

Actually, there's a template for copyrights in Sage (Jeroen sent you the link yesterday).

The copyright statements in this ticket are like this:

#############################################################################
#    Copyright (C) 2012 Xavier Caruso <xavier.caruso@normalesup.org>
#
#  Distributed under the terms of the GNU General Public License (GPL)
#
#                  http://www.gnu.org/licenses/
#****************************************************************************

while they should be like this

#*****************************************************************************
#       Copyright (C) 2013 YOUR NAME <your email>
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 2 of the License, or
# (at your option) any later version.
#                  http://www.gnu.org/licenses/
#*****************************************************************************

David

[jsrn]

Replying to arpitdm:

By copyright, do you mean add names inside the block too? I added myself and Johan as authors (commit ac109c8)

You misspelled my last name. But I've actually recently changed my name to "Johan Rosenkilde".

Replying to dlucas:

while they should be like this

#*****************************************************************************
#       Copyright (C) 2013 YOUR NAME <your email>

OK, stupid copyright stuff leading to an uncomfortable discussion: I think the copyright name should be retained as Xavier Caruso. Arpit should add his name in the list of AUTHORS as he has done (but he should of course fix the rest of the banner).

Best, Johan

[dlucas]

OK, stupid copyright stuff leading to an uncomfortable discussion: I think the copyright name should be retained as Xavier Caruso. Arpit should add his name in the list of AUTHORS as he has done (but he should of course fix the rest of the banner).

Yes, I agree.

[git]

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

​26e4689

modified copyright banner

[arpitdm]

Hello,

I've updated the copyright banner.

@Johan: Sorry for misspelling your name.

I've kept the inplace_pow and inplace_rmul methods because they are being used by power_right_mod and power_left_mod. I'm now opening it for review.

Best, Arpit.

[dlucas]

Hello,

There's still some small issues here:

• ValueError line 836 in skew_polynomial_element.pyx does not have any error message to explain to the user why this exception was raised.

• There's one old raise statement l.528 in skew_polynomial_ring.py (raise IndexError, "generator n not defined")

• Some methods in skew_polynomial_element,pyx are still undocumented. Even if I'm kind of ok with _call_ not having a short description, I'm definitely not fine with a constructor (l. 2945) without any description of its input parameters...

Back to needs_work.

David

[git]

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

​88196bf

some more fixes to the documentation.

[arpitdm]

• ValueError line 836 in skew_polynomial_element.pyx does not have any error message to explain to the user why this exception was raised.

• There's one old raise statement l.528 in skew_polynomial_ring.py (raise IndexError, "generator n not defined")

• Some methods in skew_polynomial_element,pyx are still undocumented. Even if I'm kind of ok with _call_ not having a short description, I'm definitely not fine with a constructor (l. 2945) without any description of its input parameters...

My apologies for missing out on these. I've made the changes now. Back to needs_review. :)

[dlucas]

Hello,

It seems good to me. I just have two remarks:

• You wrote error messages for every exception, including ZeroDivisionError and NotImplementedError. IMHO, it's not necessary to write (for instance) ZeroDivisionError("division by zero is not valid"). To be honest, I would have been fine with it... But you wrote ZeroDivisionError: division by zero is not valid which I think is not compatible with Python 3 (not sure though).

• There's a broken doctest:

  File "../rings/polynomial/rings.py", line 744, in sage.rings.polynomial.rings.Rings.ParentMethods.__getitem__
  Failed example:
      k['x',Frob]
  Expected:
      Skew Polynomial Ring in x over Finite Field in t of size 5^3 twisted by Frobenius Endomorphism x |-> x^5 on Finite Field in t of size 5^3
  Got:
      Skew Polynomial Ring in x over Finite Field in t of size 5^3 twisted by t |--> t^5
  
  

Apart from that, I'm fine with your changes, tests pass and a lot of work have been done here. Issues found by reviewers have been fixed, and if no one objects, I'll set this to positive_review on the next iteration.

Best,

David

[arpitdm]

• You wrote error messages for every exception, including ZeroDivisionError and NotImplementedError. IMHO, it's not necessary to write (for instance) ZeroDivisionError("division by zero is not valid"). To be honest, I would have been fine with it... But you wrote ZeroDivisionError: division by zero is not valid which I think is not compatible with Python 3 (not sure though).

I looked up online if it was required to write an error message along with ZeroDivisionError since it seems pretty obvious what the error is. It seems, that depending on the situation, this error can mean different things and people write "infinity", "not valid" or simply "division by zero" as an error message after raising the error (python 3 ​docs). And my thinking behind adding an error message for NotImplementedError is to allow the user to understand the reason behind this not being implemented. Should I remove them?

[dlucas]

Replying to arpitdm:

• You wrote error messages for every exception, including ZeroDivisionError and NotImplementedError. IMHO, it's not necessary to write (for instance) ZeroDivisionError("division by zero is not valid"). To be honest, I would have been fine with it... But you wrote ZeroDivisionError: division by zero is not valid which I think is not compatible with Python 3 (not sure though).

I looked up online if it was required to write an error message along with ZeroDivisionError since it seems pretty obvious what the error is. It seems, that depending on the situation, this error can mean different things and people write "infinity", "not valid" or simply "division by zero" as an error message after raising the error (python 3 ​docs). And my thinking behind adding an error message for NotImplementedError is to allow the user to understand the reason behind this not being implemented. Should I remove them?

Oh, ok I understand. If it is advised in Python documentation, please do not revert what you did :).

David

[arpitdm]

• There's a broken doctest:

  File "../rings/polynomial/rings.py", line 744, in sage.rings.polynomial.rings.Rings.ParentMethods.__getitem__
  Failed example:
      k['x',Frob]
  Expected:
      Skew Polynomial Ring in x over Finite Field in t of size 5^3 twisted by Frobenius Endomorphism x |-> x^5 on Finite Field in t of size 5^3
  Got:
      Skew Polynomial Ring in x over Finite Field in t of size 5^3 twisted by t |--> t^5
  
  

There isn't a rings.py file in sage/rings/polynomial. That was moved to sage/categories and the doctest passes there. Maybe you have some portion of an older version of this ticket?

[dlucas]

Mmh maybe... But it's weird though because I recompiled 7.3 a few days ago, then made a branch and pulled your branch from #13215. I have the latest version of this ticket on my local branch (commit 88196bf) and there's a file rings.py in rings/polynomial. Even with my clean version of 7.3 as it's available from download (I always keep a clean version of the develop branch), I can find such a file...

Anyway, as git log rings/polynomial/rings.py returns nothing while git log categories/rings.py returns your commits, I probably messed up somewhere.

So, I guess we're good to go now. If no one objects, I'll set this ticket to positive review.

David

[dlucas]

As no one objected, I set this ticket to positive review.

Best,

David

[jsrn]

Sorry to object, but I would like to re-insist on adding the experimental decorator on construction of skew polynomials. The reason is that I'm right now talking to a researcher in skew polynomials (Felice Manganiello), and he is making me aware of considerations that might mean some restructuring down the road. In particular, his natural notion of evaluation is *not* operator evaluation, but rather right (resp. left) modulo of x-a.

Therefore, it is not clear that the syntax f(a) should mean operator evaluation. Perhaps it should be e.g. f(a, 'operator') etc. or something different. In any case, it demonstrates that this module is maybe not as mature as we had initially assumed.

Best, Johan

[arpitdm]

Hi,

Sorry to object, but I would like to re-insist on adding the experimental decorator on construction of skew polynomials. The reason is that I'm right now talking to a researcher in skew polynomials (Felice Manganiello), and he is making me aware of considerations that might mean some restructuring down the road. In particular, his natural notion of evaluation is *not* operator evaluation, but rather right (resp. left) modulo of x-a.

This reminds me of the three approaches to evaluating a skew polynomial we discussed once before. One of them was, given a skew polynomial p and a point a, p(a) = p.right_quo_rem(x-a) (resp. left). Which I believe is what you are referring to? I think we now have the features to support this generalization of the remainder evaluation method in the non-commutative case. Or perhaps, we add an option to the call method. It takes as argument the algorithm "remainder" (or "operator") and default is set to one of them. That way the third approach of using normal basis can also be easily added if need be in the future.

Best, Arpit.

[tscrim]

Replying to jsrn:

Sorry to object, but I would like to re-insist on adding the experimental decorator on construction of skew polynomials. The reason is that I'm right now talking to a researcher in skew polynomials (Felice Manganiello), and he is making me aware of considerations that might mean some restructuring down the road. In particular, his natural notion of evaluation is *not* operator evaluation, but rather right (resp. left) modulo of x-a.

Therefore, it is not clear that the syntax f(a) should mean operator evaluation. Perhaps it should be e.g. f(a, 'operator') etc. or something different. In any case, it demonstrates that this module is maybe not as mature as we had initially assumed.

The only thing I would agree with being marked experimental in this case would be the evaluation (i.e., __call__), which would be the only thing that would really see this (behavioral) change. I also think we should take the time to get this consistent with the conventions of skew polynomial research. Could you give Felice access to the code to experiment with (in particular, to get feedback on what additional features he would want and bottlenecks)?

[tscrim]

Did anyone look at the compiled documentation? I highly doubt the pdf documentation would build because \base_ring_endomorphism is not valid latex.

Looking more closely, there are also some incorrect statements about the code and many overly verbose statements (e.g., the definition of an automorphism). I'm going over the doc and code now trying to clean things up. However, you currently have an issue in that the skew polynomials themselves do not pickle (which was caught by a TestSuite(S).run() test I'm adding). Feel free to push changes and I can merge them into my branch once this is fixed.

[vbraun]

PDF docs don't build

[dlucas]

My mistake, I did not try to compile the pdf documentation, only the html one... I'll check this as well from now on.

David

[git]

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

​eb78e69

small fixes to docstrings

[tscrim]

I often forget to also check that the pdf docs build, but you can usually see bad latex formatting on the html docs IIRC.

Let me also clarify my last comment about pushing, I would prefer pushed changes that fix the pickling. I'm taking care of the docstrings and appreciate not having to deal with trivial merge conflicts.

[arpitdm]

Replying to tscrim:

Did anyone look at the compiled documentation? I highly doubt the pdf documentation would build because \base_ring_endomorphism is not valid latex.

My mistake too. I did not check for pdf docs. They build now.

Looking more closely, there are also some incorrect statements about the code and many overly verbose statements (e.g., the definition of an automorphism). I'm going over the doc and code now trying to clean things up. However, you currently have an issue in that the skew polynomials themselves do not pickle (which was caught by a TestSuite(S).run() test I'm adding). Feel free to push changes and I can merge them into my branch once this is fixed.

Can you explain a little more about pickling? Or maybe direct me to a link that does?

[tscrim]

Pickling is how Python allows you to save data. In particular, you want

sage: loads(dumps(x)) == x
True

for (essentially) any object x.

[arpitdm]

Hi,

Pickling is how Python allows you to save data. In particular, you want

sage: loads(dumps(x)) == x
True

for (essentially) any object x.

So I ran some examples and here's what I have so far. When the base ring is a finite field of the form GF(q^m), pickling succeeds, but unpickling does not. Specifically, it fails to recognize or coerce the exponent m as an integer, I think. I tried pickling various other skew polynomials over Integer Ring, Rational Field, etc. and it works just fine. I don't understand where the problem is coming from. Also,

sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x', Frob]
sage: loads(dumps(S)) == S
Traceback:
...
ValueError: (ValueError('exponent must be an integer',), <function SkewPolynomialRing at 0x7f02ca186140>, (Finite Field in t of size 5^3, Identity endomorphism of Finite Field in t of size 5^3, 'x', False))

sage: loads(dumps(k)) == k
True
sage: loads(dumps(Frob)) == Frob
False

[tscrim]

The bigger problem is that a skew polynomial itself does not pickle:

sage: R.<t> = ZZ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = SkewPolynomialRing(R, sigma)
sage: loads(dumps(x))
---------------------------------------------------------------------------
PicklingError                             Traceback (most recent call last)
...
PicklingError: Can't pickle <type 'dictproxy'>: attribute lookup __builtin__.dictproxy failed

With that being said, the above pickling issue with the Frobenius endomorphism is a separate issue that necessitates a ticket:

sage: loads(dumps(Frob))
Identity endomorphism of Finite Field in t of size 5^3

in addition to this independent issue:

sage: Frob.parent() is Hom(k, k)
True
sage: Hom(k, k)(Frob)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
...
TypeError: unable to coerce <type 'sage.rings.finite_rings.hom_finite_field_givaro.FrobeniusEndomorphism_givaro'>

[arpitdm]

Yes. I was able to recreate this error earlier myself. But I figured that the correct pickling of the ring was dependent on the correct pickling of the underlying automorphism and every other attribute for that matter.

How can I resolve these coercion errors? Any pointers would be really helpful. I have no idea where these stem from.

Best, Arpit.

[tscrim]

Well, the pickling issue doesn't stem from coercion, nor does it have to do with the pickling of the parent (which worked okay). It is likely that you need to implement a __reduce__ method.

The conversion failure of Frob above is likely coming from the generic code for Homset being too strict, but as I said, this is an independent issue.

[git]

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

​ec19611

added a reduce method to support pickling and unpickling of skew polynomials

[arpitdm]

I've added a __reduce__ method that pickles and unpickles a skew polynomial and a skew polynomial ring over a non-finite base ring correctly now. The error in the earlier example you mentioned is now resolved. However, the problem with the finite fields case persists. I haven't managed to swat that bug away yet. Any ideas on what is causing that?

[tscrim]

The (un)pickling of the Frobenius (well, perhaps its base class) is not setting the _power correctly:

sage: Frob.power()
1
sage: loads(dumps(Frob)).power()
0

The solution is probably to make the __reduce__ less generic. This will need to be a separate ticket (which we don't have to make as a dependency of this one).

[jsrn]

About the experimental warning: @arpitdm: yes, what you describe is exactly the other evaluation notions, so it is not complicated to implement them - it is only a matter of discussing interface. For progressing with our GSoC, I strongly prefer to take that discussion in a follow-up ticket (e.g. during SD75) and just mark skew polynomials with the experimental warning.

@tscrim: Marking *only* __call__ is certainly an option, and will be less disconcerting to users who wants to take skew polynomials into use soon, and I am also sort of OK with this. However, I prefer to mark the entire module as experimental: this __call__ issue might just be the first example of other similar conventions. Felice has already asked for a trac account and will look at the functionality when he has time. But in the interest of being able to continue with our other goals, I would strongly prefer to get this major ticket closed before we are sure everything has converged, and the point of the experimental decorator is exactly to be able to do that.

Best, Johan

[jsrn]

I renamed power_left_mod to left_power_mod similarly for right. I suggested the old names myself, but realised that it's much better if all such sided operations begin with left/right (and all the other sided operations already do).

Best, Johan

---

New commits:

​15ac350	Merge branch 'u/arpitdm/skew_polynomials' of git://trac.sagemath.org/sage into 13215_skew_polynomials
​f78efb1	power_left/right_mod -> left/right_power_mod

[arpitdm]

Replying to jsrn:

About the experimental warning: @arpitdm: yes, what you describe is exactly the other evaluation notions, so it is not complicated to implement them - it is only a matter of discussing interface. For progressing with our GSoC, I strongly prefer to take that discussion in a follow-up ticket (e.g. during SD75) and just mark skew polynomials with the experimental warning.

Agreed. We can keep that for SD75.

@tscrim: Marking *only* __call__ is certainly an option, and will be less disconcerting to users who wants to take skew polynomials into use soon, and I am also sort of OK with this. However, I prefer to mark the entire module as experimental: this __call__ issue might just be the first example of other similar conventions. Felice has already asked for a trac account and will look at the functionality when he has time. But in the interest of being able to continue with our other goals, I would strongly prefer to get this major ticket closed before we are sure everything has converged, and the point of the experimental decorator is exactly to be able to do that.

If we are placing the experimental decorator, which I think we should, I second placing it over the entire skew polynomial ticket. Because call is not the only one that will be changed. Derivations are missing. Anyone who is working on skew polynomial research will probably point that out immediately. And there could be a bunch of changes to accommodate that.

[tscrim]

I've gone through and made some cleanup to the documentation and code. I've made the SkewPolynomial actually behave like an ABC that can be subclassed to sparse skew polynomials (mainly, removed the _coeffs attribute).

I strongly disagree with marking the entire class with @experimental. For example, all of the changes I did would not require any deprecation, i.e., the public API and behavior was unchanged. If you know you must change the API/behavior to accommodate something, then this code has no business being in Sage and you should just go ahead and do it. If the behavior could undergo (radical) changes, then the code isn't (IMO) correct and should not be included.

(Personally, I see very little use-cases for @experimental and no real use at the top-level. People who will actually experiment with the code will be those who can just get the code from the trac server (which requires no login). By marking something at the top-level, nobody will really use the code because there are no guarantees.)

---

New commits:

​11fc028	Merge branch 'u/arpitdm/skew_polynomials' of trac.sagemath.org:sage into public/rings/skew_polynomials-13215
​c2bfcd7	Merge branch 'u/arpitdm/skew_polynomials' of trac.sagemath.org:sage into public/rings/skew_polynomials-13215
​225a66a	Initial round of docstring and code fixing.
​05587a9	Merge branch 'u/jsrn/skew_polynomials' of trac.sagemath.org:sage into public/rings/skew_polynomials-13215
​92ae069	Moving things around so the ABC actually is the ABC for univariate skew polynomials.

[jsrn]

Hi Travis,

Replying to tscrim:

I've gone through and made some cleanup to the documentation and code. I've made the SkewPolynomial actually behave like an ABC that can be subclassed to sparse skew polynomials (mainly, removed the _coeffs attribute).

Great!

I strongly disagree with marking the entire class with @experimental. For example, all of the changes I did would not require any deprecation, i.e., the public API and behavior was unchanged. If you know you must change the API/behavior to accommodate something, then this code has no business being in Sage and you should just go ahead and do it. If the behavior could undergo (radical) changes, then the code isn't (IMO) correct and should not be included.

(Personally, I see very little use-cases for @experimental and no real use at the top-level. People who will actually experiment with the code will be those who can just get the code from the trac server (which requires no login). By marking something at the top-level, nobody will really use the code because there are no guarantees.)

I see we disagree on the @experimental decorator itself. It is a "local beta", in that it says: "you can count on this functionality being in Sage soon in roughly the same shape. If you want to use it already, be prepared that the API might change mildly". It facilitates Request-for-comments from developers who believe they have well-designed some module, but acknowledge that they might not have considered everything. This goes doubly for math code, since any given math structure can be considered from so many angles, and usually the initial developer considers mostly just one. It allows building other new stuff on top of it (which we really need now: #20970), which postponing the ticket wouldn't, and that new stuff might not need an @experimental warning itself (for #20970, skew polynomials is just a tool, and its exact API has roughly no bearing on the API of the Gabidulin codes).

The decorator was originally suggested because without it, it is difficult to start introducing the "basic" modules on a new set of functionality, since one can only really judge its design once many things have been developed on top of it. This happened for us in coding theory, where we felt forced to have our own fork of Sage and develop for nine months before making the first pushes to Sage, greatly complicating the development process.

See also the discussion here: ​https://groups.google.com/forum/#!topic/sage-devel/LXWs6KOw0Lk. This ticket is exactly one of the intended use cases for this decorator.

I still insist on the module-wide experimental warning here. I expect I will be active in polishing the skew polynomial module in the coming months, and I really don't want to be burdened/limited by deprecation considerations all the time. On the other hand, we really need this ticket to go into Sage to proceed with the GSoC, and at least >95% of the current functionality and API is good.

[tscrim]

From the discussion above, there are suggestions of major behavioral and API changes, not mild. While this is not the hill I necessarily want to die on, I do have a use-case for this code. By saying the module is "subject to change without notice" means I can't build upon it because it could break all of my code, as well as yours for #20970. You say you only need this as a tool, but suppose #20970 is merged before this is stable and then you force whomever has to make changes to this code to also fix your code (which defeats the entire point) or your code gets broken if it is something not doctested.

You also seem stuck on the idea the code has to be merged in order to proceed with GSoC. You can build other code on top of this, and this doesn't need to be merged by the end of the program for the GSoC to be considered successful (granted, it took a little too long for the knot theory GSoC code to get merged).

Additionally, if 95% of the code is set, then mark the 5% with @experimental if you think it is that likely to change. If you disagree, then I am forced to disagree with your assessment of the completeness of the code. As a reminder, internal changes do not need to be deprecated (for example, none of the changes I pushed would not require one).

[tscrim]

If you feel we are at an impasse, then we can ask on sage-devel.

[jsrn]

Replying to tscrim:

From the discussion above, there are suggestions of major behavioral and API changes, not mild.

I don't consider the __call__ discussion a major change. My current idea for accommodating multiple notions of evaluation would be to throw a warning/error when __call__ is used before "setting" the default evaluation on the skew polynomial ring in question. That's a completely local change (local to __call__. But as I mentioned, I prefer to postpone that discussion to a later ticket.

While this is not the hill I necessarily want to die on, I do have a use-case for this code. By saying the module is "subject to change without notice" means I can't build upon it because it could break all of my code, as well as yours for #20970. You say you only need this as a tool, but suppose #20970 is merged before this is stable and then you force whomever has to make changes to this code to also fix your code (which defeats the entire point) or your code gets broken if it is something not doctested.

As I said, I imagine that it would be an overlapping set of developers (at least me) who would improve skew polynomials in the forseeable future, as well as use it before it was "stable", in e.g. #20970. This is, once again, what I would regard the common use-case of @experimental (whoever adds some feature usually needs it him/herself).

If you want to build upon this code yourself, I also don't understand your stance: not having @experimental means that any near-future sensible change to this module's API will be clumsy to accommodate. If you have made use of this module in the mean-time, either included in Sage or not, there's two possible outcomes: the improvement is not done, or it is done and your code will start spewing warnings. I don't see how either outcomes are better than what would happen with the @experimental warning on.

You also seem stuck on the idea the code has to be merged in order to proceed with GSoC. You can build other code on top of this, and this doesn't need to be merged by the end of the program for the GSoC to be considered successful (granted, it took a little too long for the knot theory GSoC code to get merged).

You know how it is: unmerged code just has a much larger probability of rotting on trac or ending up causing a huge workload for the mentors/other interessants of the project. We already have a queue of 4 tickets waiting for this one, and I really want to pop most of them before GSoC runs out!

Additionally, if 95% of the code is set, then mark the 5% with @experimental if you think it is that likely to change.

But I don't *know* what could change! It's my assessment that this is pretty close to stable, and Xavier, Arpit, David, Burcin, you, and me have thought things pretty well through. But it *is* a large, new structure to Sage.

If you disagree, then I am forced to disagree with your assessment of the completeness of the code. As a reminder, internal changes do not need to be deprecated (for example, none of the changes I pushed would not require one).

I am somewhat shocked at how vehemently you are against the @experimental decorator. Discussion on sage-devel it is, I guess...

[jsrn]

​https://groups.google.com/forum/#!topic/sage-devel/JlJXGtxsYr0

[jsrn]

The discussion on sage-devel seems to have tapered off, so we need to take a decision here. We got two pieces of input: leif suggested a compromise with a warning in the doc, and wstein seemed to favour something like not pre-importing the module until the module is deemed "stable".

IMHO, neither of the two shared your concerns of not being able to build upon the module, and seemed OK with the idea of accepting not-completely-stable code into Sage. Conversely, they apparently didn't really like @experimental in the current form either.

I like both of the alternative suggestions less than just including the module and defining it as stable, handling any possible deprecation warnings that might arise in the near future. However, I still claim that using @experimental on the module is the right way to go.

But in the interest of progressing, I leave it to you Travis: if you are still strongly against a module-level @experimental, let's drop it. I guess you are still OK with having @experimental on call, together with a sensible message in the doc, e.g.

    WARNING::

        Currently only "operator evaluation" of skew polynomials is implemented. There are two other common notions of evaluation of `f(x)` at some `a` from the base ring, namely the remainder after left or right modulo by `x-a`. The current calling convention might change in the future to accommodate these.

Best, Johan

[tscrim]

Replying to jsrn:

But in the interest of progressing, I leave it to you Travis: if you are still strongly against a module-level @experimental, let's drop it. I guess you are still OK with having @experimental on call, together with a sensible message in the doc, e.g.

    WARNING::

        Currently only "operator evaluation" of skew polynomials is implemented.
        There are two other common notions of evaluation of `f(x)` at some `a`
        from the base ring, namely the remainder after left or right modulo by `x-a`.
        The current calling convention might change in the future to accommodate these.

I still strongly am against a module-level @experimental, but I think this is a good compromise. Positive review on my part once this is done. Thank you for your input and work on this!

[chapoton]

from the patchbot:

+inside file:  b/src/sage/rings/polynomial/skew_polynomial_ring_constructor.py
+@@ -0,0 +1,207 @@
++            ....:     print S
+python2-only print syntax inserted on 1 non-empty lines
+Traceback (most recent call last):
+  File "/nfs4/home6/vdelecro/.local/lib/python2.7/site-packages/sage_patchbot/patchbot.py", line 1053, in test_a_ticket
+    baseline=baseline, **kwds)
+  File "/usr/labri/vdelecro/.local/lib/python2.7/site-packages/sage_patchbot/plugins.py", line 368, in oldstyle_print
+    msg="python2-only print syntax", **kwds)
+  File "/usr/labri/vdelecro/.local/lib/python2.7/site-packages/sage_patchbot/plugins.py", line 214, in exclude_new
+    raise ValueError(full_msg)
+ValueError: python2-only print syntax inserted on 1 non-empty lines

+inside file:  b/src/sage/rings/polynomial/skew_polynomial_element.pyx
+@@ -0,0 +1,3019 @@
++        INPUT::
+inside file:  b/src/sage/rings/polynomial/skew_polynomial_ring.py
+@@ -0,0 +1,732 @@
++        INPUT::
+Bad Input/Output blocks inserted on 2 non-empty lines
+Traceback (most recent call last):
+  File "/nfs4/home6/vdelecro/.local/lib/python2.7/site-packages/sage_patchbot/patchbot.py", line 1053, in test_a_ticket
+    baseline=baseline, **kwds)
+  File "/usr/labri/vdelecro/.local/lib/python2.7/site-packages/sage_patchbot/plugins.py", line 352, in input_output_block
+    msg="Bad Input/Output blocks", **kwds)
+  File "/usr/labri/vdelecro/.local/lib/python2.7/site-packages/sage_patchbot/plugins.py", line 214, in exclude_new
+    raise ValueError(full_msg)
+ValueError: Bad Input/Output blocks inserted on 2 non-empty lines

[dlucas]

Oh, you managed to get some feedback from the patchbot? I was actually slightly worried about the Python 2 only syntax, but I do not know any efficient way to test for this locally...

David

[arpitdm]

Based on the conclusions reached above, I tried adding the experimental warning to the call method. And I get an error message while building Sage that seems to that it is not possible to add the experimental decorator at all.

Error compiling Cython file:
------------------------------------------------------------
...
        else:
            n = self._new_c([],P)
        return n

    @experimental(trac_number=13215)
    def __call__(self, eval_pt):
   ^
------------------------------------------------------------

sage/rings/polynomial/skew_polynomial_element.pyx:336:4: special functions of cdef classes cannot have decorators

Is there an alternate way to add the experimental warning?

[git]

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

​4b86345

fixed INPUT/OUTPUT syntax in docs. updated print statement to python3 syntax

[arpitdm]

I think I've managed to rectify the patchbot errors. How can I check if there are further patchbot errors?

[chapoton]

Patchbots should soon come back. Then you have to wait for one of them to look at your ticket. Or run your own patchbot.

[jsrn]

Replying to arpitdm:

Based on the conclusions reached above, I tried adding the experimental warning to the call method. And I get an error message while building Sage that seems to that it is not possible to add the experimental decorator at all.

Ah ok, that's a snag. Have you tried looking up the source code for @experimental in sage/misc/superseded.py? You should be able to just print the warning manually as the first line of __call__. Perhaps add a comment mentioning this emulates @experimental such that it can be found if one greps "@experimental".

Best, Johan

[tscrim]

That's right, it's a Cython issue because double-underscore methods need to be assigned to slots at compile time (or at least be handled in a special way), so decorators don't work on them. I agree with comment:181, just issue the warning yourself.

[git]

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

​8553b93

added a manual experimental warning to the '__call__' method

[arpitdm]

Hello,

I've added the experimental warning to the __call__ method manually based on the source code for experimental as suggested by @jsrn. There are a couple of doctests that "fail" because they issue the experimental warning before returning the correct answer. Should I modify the doctests or keep them as it is?

Best, Arpit.

[tscrim]

You need to make sure all doctests pass, so you need to include the warning in the doctest output.

[dlucas]

As warnings are issued only once per session, you can fix this by triggering the experimental warning in a specific "doctest" at the top of the file. See what have been done in rings/asymptotic/asymptotic_ring.py for instance.

[git]

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

​137b58b

fixed small doctest errors

[arpitdm]

Done. Fixed! I'm opening it for review.

[jsrn]

Is there a reason you didn't add a single doctest at the top for triggering the warning, as David suggested?

[tscrim]

@jsm @dlucas Warnings for doctests are handled different than in a session. For deprecation warnings, these are done every time the deprecation message is hit, and I believe that behavior extends to all warnings.

@arpitdm If you are going to do a redirection, which is good for if evaluation does change provided you give it a more descriptive name (and include it as part of the public API), I believe you can just mark the (Python) function with the decorator without problem (as it is no longer a special method).

[dlucas]

Replying to tscrim:

@jsm @dlucas Warnings for doctests are handled different than in a session. For deprecation warnings, these are done every time the deprecation message is hit, and I believe that behavior extends to all warnings.

Is that a recent behaviour? Because triggering the experimental warning once works just fine in the file I referenced above. I also used this myself in #20284 and it also worked perfectly.

[jsrn]

Replying to tscrim:

@jsm @dlucas Warnings for doctests are handled different than in a session. For deprecation warnings, these are done every time the deprecation message is hit, and I believe that behavior extends to all warnings.

As David, I have my doubts about this too...

@arpitdm If you are going to do a redirection, which is good for if evaluation does change provided you give it a more descriptive name (and include it as part of the public API), I believe you can just mark the (Python) function with the decorator without problem (as it is no longer a special method).

Agree, since you did an indirection anyway. operator_eval is a more descriptive name. Then the two others that we might add later on could be left_mod_eval and right_mod_eval; not too long, uses very common abbreviations, and all follow the same style.

[tscrim]

It's also quite possible that classes and methods/functions are handled differently by the decorator.

[caruso]

Here is another issue:

sage: k = GF(5^3)
sage: S.<x> = SkewPolynomialRing(k, k.frobenius_endomorphism())
sage: x.right_quo_rem(Graphics())
...
zsh: segmentation fault (core dumped)  sage

As far as understand, one has to use the decorator @coerce_binop for all binary operations.

[arpitdm]

@tscrim, @jsrn - Just to clarify, there is a __call__ magic function for evaluation of the polynomial which calls an _call function. Are you suggesting that I rename the latter to operator_eval?

@Caruso - What does Graphics()`

[caruso]

Graphics() is an empty plot. It is not a skew polynomials; that's the point.

[caruso]

Do you really need the __call__ function for this ticket? Otherwise, I would suggest to forget it for now and reintroduce it only when needed.

[jsrn]

Replying to arpitdm:

@tscrim, @jsrn - Just to clarify, there is a __call__ magic function for evaluation of the polynomial which calls an _call function. Are you suggesting that I rename the latter to operator_eval?

Yes.

[jsrn]

Replying to caruso:

Do you really need the __call__ function for this ticket? Otherwise, I would suggest to forget it for now and reintroduce it only when needed.

We need it for Gabidulin codes (for which we need #21131)

[git]

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

​cf14817	Merge branch 'public/rings/skew_polynomials-13215' of git://trac.sagemath.org/sage into skew_polynomials
​2d4a140	triggered experimental warning at the top of the session

[arpitdm]

A helper function def _call has been added that acts as a helper function to accommodate for operator evaluation. The def operator_eval is available as a public method. And the experimental warning is triggered at the top of the module. The segmentation fault due to Graphics() for def right_quo_rem (resp. left) have been resolved.

[git]

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

​5dcea53

adding coerce_binop decorator to relevant methods

[arpitdm]

The coerce_binop decorator is added to the relevant methods to resolve the remaining segmentation fault methods.

[tscrim]

• You need to change the docstring of _call to reflect that its existence is only because of @experimental:

  Helper function for the ``__call__`` method to accommodate
  the ``@experimental`` decorator.
  

• I think you should make operator_eval into a cpdef method as it will likely be an important method (and should have a C version). You also need to change

  -(<RingElement> c)*a
  +c * a
  

  so the skew polynomial ring can support non-RingElement classes as a coefficients and to avoid an unneeded type check by Cython.
• You have added extra coercion checks for each step of things like left_xgcd. I feel that you would be better having a public method that does @coerce_binop and then private (cdef?) functions that assume both elements belong to the same parent. If you don't think this is so important, than don't feel compelled to change it.
• Are the *_monic methods useful to have at the public namespace (instead of (effectively hidden) cdef methods)? I feel one can just divide by the leading coefficient and that this operation will not be called frequently by a user.

[jsrn]

Replying to tscrim:

• You have added extra coercion checks for each step of things like left_xgcd. I feel that you would be better having a public method that does @coerce_binop and then private (cdef?) functions that assume both elements belong to the same parent. If you don't think this is so important, than don't feel compelled to change it.

Seems like the gain would currently be very small, since these methods now mostly do not call each other internally. If this changes later on, the private method can be added at this time.

• Are the *_monic methods useful to have at the public namespace (instead of (effectively hidden) cdef methods)? I feel one can just divide by the leading coefficient and that this operation will not be called frequently by a user.

Usual commutative polynomials have a monic method. This is the analogue for non-commutative polynomials.

Best, Johan

[tscrim]

Replying to jsrn:

Replying to tscrim:

• You have added extra coercion checks for each step of things like left_xgcd. I feel that you would be better having a public method that does @coerce_binop and then private (cdef?) functions that assume both elements belong to the same parent. If you don't think this is so important, than don't feel compelled to change it.

Seems like the gain would currently be very small, since these methods now mostly do not call each other internally. If this changes later on, the private method can be added at this time.

However this feels it could be used in tight loops, and so while individual calls are marginal, the net sum over 10000 loops can add up. I leave it up to you.

• Are the *_monic methods useful to have at the public namespace (instead of (effectively hidden) cdef methods)? I feel one can just divide by the leading coefficient and that this operation will not be called frequently by a user.

Usual commutative polynomials have a monic method. This is the analogue for non-commutative polynomials.

Only for univariate, and in that case all it does is divide by the leading coefficient. However, in that case it extends the base ring so the leading coefficient is a unit, which is different than the behavior here. Also, I don't necessarily see the point of having monic in the public API for commutative polynomials (and don't take that as a guide for what must/should be included in the API).

[git]

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

​8c283a8

made operator_eval a cpdef method. small fix to the operator_eval method.

[jsrn]

Replying to tscrim:

However this feels it could be used in tight loops, and so while individual calls are marginal, the net sum over 10000 loops can add up. I leave it up to you.

It's mostly the relative gain that's important, which is still low as long as the functions don't call each other a lot.

Only for univariate, and in that case all it does is divide by the leading coefficient. However, in that case it extends the base ring so the leading coefficient is a unit, which is different than the behavior here. Also, I don't necessarily see the point of having monic in the public API for commutative polynomials (and don't take that as a guide for what must/should be included in the API).

I think it's a handy helper function that I think people will expect. I've used monic for univariate polynomials many times. (for multivariate polynomials, it's much more ambiguous what can be meant so the helper function is less useful).

[caruso]

Replying to tscrim:

However this feels it could be used in tight loops, and so while individual calls are marginal, the net sum over 10000 loops can add up. I leave it up to you.

Maybe, we can leave as it currently is for this ticket and come back to this in ticket #21088 where inplace fast functions are designed.

[arpitdm]

I've made the operator_eval method a cpdef method. And I've edited the docstring to mention that it is a helper function to accommodate the @experimentaldecorator.

Best, Arpit.

[tscrim]

I am okay with the current state. Any other objections?

[git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

​b9d1ecd	Fixed some of the doctests I just broke
​6efcd02	more doc
​8a991b7	more doc
​69e3398	Evaluation outside the base ring is *not* possible
​472193b	improve __call__ doc
​4300204	More various doc
​36cc788	Rephrase the same phrase repeated many times
​dd8b275	More doc string fixes
​47ba6f0	There should not be a mod, but rather left_mod and right_mod
​1f44135	Doc fixes for the last methods

[jsrn]

I went through all docs a last time, polishing many docs and also modifying a few tests and even an implementation or two. Please review.

Best, Johan

[tscrim]

I disagree with the following:

• This is probably not true:

        - ``monic`` -- boolean (default: ``True``). Return whether the right gcd
          should be normalized to be monic. This parameter must be passed as a
          named argument.
  

  At least I don't see a reason why must go monic=True as an argument (for everything but left_xgcd). Actually, I don't see why left_xgcd has unlimited number of arguments but right_xgcd does not.
• This change make it seem like there is one unique skew polynomial ring (to rule them all :P).

  -    Return the globally unique skew polynomial ring with given
  -    properties and variable name or names.
  +    Return the globally unique skew polynomial ring.
  

• The part about the general case not being implemented should be in a .. NOTE:: or .. WARNING:: block:

           r"""
           Return ``True`` if this skew polynomial is a unit.
   
  -        .. NOTE::
  +        When the base ring `R` is an integral domain, then a skew polynomial `f`
  +        is a unit if and only if degree of `f` is `0` and `f` is then a unit in
  +        `R`.
   
  -            When the base ring `R` is an integral domain, then a skew
  -            polynomial `f` is a unit if and only if degree of `f` is
  -            `0` and `f` is then a unit in `R`. The general case is not
  -            yet implemented.
  +        The case when `R` is not an integral domain is not yet implemented.
   
           EXAMPLES::
  

• You should revert this change so we keep it under 80 characters/line:

               else:
                   return False
           else:
  -            raise NotImplementedError("support for determining if skew polynomial"
  -                                      " is a unit is not available when the base"
  -                                      " ring of the parent skew polynomial"
  -                                      " ring is not an integral domain")
  +            raise NotImplementedError("is_unit is not implemented for skew polynomial rings over base rings which are not integral domains.")
   
       def is_nilpotent(self):
           r"""
  

• You should not break :trac:`13215` across multiple lines (I might just be paranoid for this one though).
• AFAIK, only operator evaluation is implemented, so I don't understand this removal:

           .. NOTE::
   
  -            Currently, only "operator evaluation" of skew polynomials is implemented
  -            (see :meth:`.operator_eval`).
               There are two other common notions of evaluation of `f(x)` at some element `a`
               from the base ring, namely the remainder after left or right modulo by `x-a`.
  

• `__call__` is not latex, it should be :meth:`__call__` (or ``__call__``).

Otherwise all your changes look good to me.

[git]

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

​8ae28e0	monic can be passed as unnamed. And rm *-args from left_xgcd
​ef7fbe0	Fix reviewer's other comments

[jsrn]

Thanks for carefully going through all the modifications.

Replying to tscrim:

• This is probably not true:

        - ``monic`` -- boolean (default: ``True``). Return whether the right gcd
          should be normalized to be monic. This parameter must be passed as a
          named argument.
  

  At least I don't see a reason why must go monic=True as an argument (for everything but left_xgcd). Actually, I don't see why left_xgcd has unlimited number of arguments but right_xgcd does not.

Indeed. I've chatted with Xavier, and the original reason for the "This parameter must be passed as named argument" (and perhaps the * in left_xgcd) is the broken behaviour of coerce_binop. This has now been fixed, see #21322. Therefore I've now set the doc and the code to what it should be as soon as #21322 is merged.

• This change make it seem like there is one unique skew polynomial ring (to rule them all :P).

OK, that change was a bit fast ;-)

• The part about the general case not being implemented should be in a .. NOTE:: or .. WARNING:: block:

I found this overkill, which is why I removed it. But if you insist.

• You should revert this change so we keep it under 80 characters/line:

I disagree. It makes the source code look terrible. Also:

$ grep  '.\{80,\}' -r src/sage | grep "raise" | wc -l 
4703

So the 80 chars/line is defacto not a convention upheld in raise-statements.

• You should not break :trac:`13215` across multiple lines (I might just be paranoid for this one though).

Indeed. Emacs reflow doesn't understand Sphinx magic syntax probably doesn't allow line breaks :-)

• AFAIK, only operator evaluation is implemented, so I don't understand this removal:

           .. NOTE::
   
  -            Currently, only "operator evaluation" of skew polynomials is implemented
  -            (see :meth:`.operator_eval`).
               There are two other common notions of evaluation of `f(x)` at some element `a`
               from the base ring, namely the remainder after left or right modulo by `x-a`.
  

The entirety of the __call__ doc reads better now, IMHO: the first line clearly states that operator evaluation is considered. So the note doesn't need to repeat this.

• `__call__` is not latex, it should be :meth:`__call__` (or ``__call__``).

Indeed.

Otherwise all your changes look good to me.

Great!

[caruso]

Another remark: Should we define the methods left_quo and right_quo as well? And create aliases left_rem and right_rem for left_mod and right_mod respectively?

[tscrim]

Replying to jsrn:

Thanks for carefully going through all the modifications.

Thank you for your work on this (and dealing with my griping).

Replying to tscrim:

• This is probably not true:

        - ``monic`` -- boolean (default: ``True``). Return whether the right gcd
          should be normalized to be monic. This parameter must be passed as a
          named argument.
  

  At least I don't see a reason why must go monic=True as an argument (for everything but left_xgcd). Actually, I don't see why left_xgcd has unlimited number of arguments but right_xgcd does not.

Indeed. I've chatted with Xavier, and the original reason for the "This parameter must be passed as named argument" (and perhaps the * in left_xgcd) is the broken behaviour of coerce_binop. This has now been fixed, see #21322. Therefore I've now set the doc and the code to what it should be as soon as #21322 is merged.

Does #21322 need to be a dependency of this ticket then?

• You should revert this change so we keep it under 80 characters/line:

I disagree. It makes the source code look terrible. Also:

$ grep  '.\{80,\}' -r src/sage | grep "raise" | wc -l 
4703

So the 80 chars/line is defacto not a convention upheld in raise-statements.

It makes the source code look fine if you are using < ~160 chars wide editors. We do try to stick to ~80 character lines overall in the code, but it is not absolute. Plus, there is a big difference between 90 chars and ~160 chars. IMO, a more fair comparison would be to look at how many raise statements are 80,90,100,100+ lines. I do not see the gain for the long line unless you have an editor with a very large character line limit (literally).

• AFAIK, only operator evaluation is implemented, so I don't understand this removal:

           .. NOTE::
   
  -            Currently, only "operator evaluation" of skew polynomials is implemented
  -            (see :meth:`.operator_eval`).
               There are two other common notions of evaluation of `f(x)` at some element `a`
               from the base ring, namely the remainder after left or right modulo by `x-a`.
  

The entirety of the __call__ doc reads better now, IMHO: the first line clearly states that operator evaluation is considered. So the note doesn't need to repeat this.

The key word is "only", and the __call__ doc does not mention this (nor is it anywhere else IIRC).

[git]

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

​a649c67	fixes to the documentation
​f54e80e	removed method reverse
​1336c57	small fixes to the documentation
​81b8fb8	small fixes to the ring_constructor file

[arpitdm]

I went through the docs once and clarified them in some places where it was not clear/missing and made some small changes to standardize the docs whereever possible.

Based on discussions with @caruso and @jsrn, the def reverse method is inappropriate in that, reversing a skew polynomial actually involves creating a new skew polynomial ring over the inverse twist map. And that requires more consideration since twist map cannot always be inverted in Sage and also perhaps since "dual_ring" or something like that could also be nice to have.

Best, Arpit.

[tscrim]

Changes like:

@@ -134,7 +134,7 @@ cdef class SkewPolynomial(AlgebraElement):
     where `\sigma` is the base ring automorphism. This is called
     the *operator evaluation* method.
 
-    EXAMPLES:
+    EXAMPLES::
 
     We illustrate some functionalities implemented in this class.
 

are wrong because text follows, not (indented) code. So the last commit should be reverted. Also, I disagree with changing the .. TODO:: block because it is a TODO.

One other thing I just noticed, a better test than if not isinstance(base_ring, ring.CommutativeRing): would be if base_ring not in Rings().Commutative(): as it is a mathematical check, not an implementation check.

It is also okay to have methods that rely on others than can error out in certain cases when implementations are not done yet. Just FYI.

You also did not need to change r""" for every docstring (it doesn't hurt, but it is only necessary when you have escape \ characters).

[git]

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

​b6e77d2

fixed html documentation build errors

[arpitdm]

• EXAMPLES:

+ EXAMPLES:: }}} are wrong because text follows, not (indented) code. So the last commit should be reverted.

I just checked whether the html documentation builds and in this particular case, it did not give an error while in a couple of other places it did.

Also, I disagree with changing the .. TODO:: block because it is a TODO.

Do you mean, changing the name from TODO to NOTE or the description as well?

One other thing I just noticed, a better test than if not isinstance(base_ring, ring.CommutativeRing): would be if base_ring not in Rings().Commutative(): as it is a mathematical check, not an implementation check.

Okay. I will change that.

It is also okay to have methods that rely on others than can error out in certain cases when implementations are not done yet. Just FYI.

You also did not need to change r""" for every docstring (it doesn't hurt, but it is only necessary when you have escape \ characters).

I was just trying to follow the conventions in other files where I saw that r""" is used everywhere. So while, I was going through the code, I figured, it didn't hurt to change it.

[tscrim]

Replying to arpitdm:

Also, I disagree with changing the .. TODO:: block because it is a TODO.

Do you mean, changing the name from TODO to NOTE or the description as well?

You made a change .. TODO:: -> .. NOTE::, where the message is describing a TODO.

You also did not need to change r""" for every docstring (it doesn't hurt, but it is only necessary when you have escape \ characters).

I was just trying to follow the conventions in other files where I saw that r""" is used everywhere. So while, I was going through the code, I figured, it didn't hurt to change it.

Yes, it's perfectly fine (in some aspects, it should be the standard way we do docstrings in Sage). This was another just FYI and future reference.

[git]

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

​27c05c6	improved check on commutativity of base ring
​97ba596	reverted NOTE back to TODO

[git]

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

​92564c5	rewrap
​35fcdf2	Merge branch 'public/rings/skew_polynomials-13215' of trac.sagemath.org:sage into 13215_skew_polynomials

[jsrn]

Replying to tscrim:

Does #21322 need to be a dependency of this ticket then?

Not in our opinion: what we do here is the intended behaviour of coerce_binop, and the decorated methods works as well as all other methods in Sage decorated with coerce_binop. So #21322 is just a (already known) bug that should be fixed.

It makes the source code look fine if you are using < ~160 chars wide editors.

??? The line is 141 chars. Also, having a < 160 chars editor doesn't make the old 4-line wrapping look good.

We do try to stick to ~80 character lines overall in the code, but it is not

absolute.

Indeed my point before.

Plus, there is a big difference between 90 chars and ~160 chars. IMO, a more fair comparison would be to look at how many raise statements are 80,90,100,100+ lines. I do not see the gain for the long line unless you have an editor with a very large character line limit (literally).

    $ grep  '.\{100,\}' -r src/sage | grep "raise" | wc -l
    1628

    $ grep  '.\{120,\}' -r src/sage | grep "raise" | wc -l
    588

    $ grep  '.\{140,\}' -r src/sage | grep "raise" | wc -l
    210

Also, btw:

    $ grep  '.\{140,\}' -r src/sage | wc -l
    10459

So it's not like you're not likely to come across a long line in your editor while editing Sage codes.

• AFAIK, only operator evaluation is implemented, so I don't understand this removal:

           .. NOTE::
   
  -            Currently, only "operator evaluation" of skew polynomials is implemented
  -            (see :meth:`.operator_eval`).
               There are two other common notions of evaluation of `f(x)` at some element `a`
               from the base ring, namely the remainder after left or right modulo by `x-a`.
  

The entirety of the __call__ doc reads better now, IMHO: the first line clearly states that operator evaluation is considered. So the note doesn't need to repeat this.

The key word is "only", and the __call__ doc does not mention this (nor is it anywhere else IIRC).

It says "The current calling convention might change in the future to accommodate these. Therefore, the current method has been marked as experimental.". Try to read the doc-string in its entirety -- it really does say everything.

Best, Johan

[jsrn]

Oh yeah, forgot to add about the whole wrapping thing: I now pushed a compromise where the line is wrapped in two but takes up 92 chars.

[arpitdm]

This ticket is still open for review. Are there any further objections?

-Arpit.

[tscrim]

Replying to jsrn:

Replying to tscrim:

It makes the source code look fine if you are using < ~160 chars wide editors.

??? The line is 141 chars. Also, having a < 160 chars editor doesn't make the old 4-line wrapping look good.

It makes it more consistent and it is a standard way to split long lines of text by PEP8.

We do try to stick to ~80 character lines overall in the code, but it is not

absolute.

Indeed my point before.

I can accept the 92 char lines as a compromise.

Also, btw:

    $ grep  '.\{140,\}' -r src/sage | wc -l
    10459

So it's not like you're not likely to come across a long line in your editor while editing Sage codes.

There are a number of lines that are forced to be long because they are large numbers with no spaces. Plus, I have no idea exactly how many lines of code we have in Sage, but this smells of a fallacy.

• AFAIK, only operator evaluation is implemented, so I don't understand this removal:

           .. NOTE::
   
  -            Currently, only "operator evaluation" of skew polynomials is implemented
  -            (see :meth:`.operator_eval`).
               There are two other common notions of evaluation of `f(x)` at some element `a`
               from the base ring, namely the remainder after left or right modulo by `x-a`.
  

The entirety of the __call__ doc reads better now, IMHO: the first line clearly states that operator evaluation is considered. So the note doesn't need to repeat this.

The key word is "only", and the __call__ doc does not mention this (nor is it anywhere else IIRC).

It says "The current calling convention might change in the future to accommodate these. Therefore, the current method has been marked as experimental.". Try to read the doc-string in its entirety -- it really does say everything.

I very carefully had read it, and no, it does not say everything. It does not say that this is the only type of evaluation currently implemented. I know this is dangerously close to bikeshedding because this is only visible at the code level. Yet, I think it is important to state why we are (currently) doing things this way: there currently is no other option.

[git]

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

​e72a8cc

reinstate as per reviewer's insistence

[jsrn]

Replying to tscrim:

I very carefully had read it, and no, it does not say everything. It does not say that this is the only type of evaluation currently implemented. I know this is dangerously close to bikeshedding because this is only visible at the code level. Yet, I think it is important to state why we are (currently) doing things this way: there currently is no other option.

Bikeshedding indeed...

[jsrn]

Replying to jsrn:

Bikeshedding indeed...

Sorry for this grumbling. I shouldn't reply to comments before my morning coffee.

Anyway, it seems the issues are getting exponentially less important, so perhaps we can positive review this ticket soon. Best, Johan

[tscrim]

Sorry I have a bit of a stick up my @$* about this, but I'd like to get this right. So we don't have to deal with issues because someone came along and changed things due to a lack of documentation.

Anyways, I believe we are at a positive review.

[vbraun]

PDF docs fail

[docpdf] LaTeX Warning: Hyper reference `sage/rings/polynomial/skew_polynomial_element:s
[docpdf] age.rings.polynomial.skew_polynomial_element.SkewPolynomialBaseringInjection' o
[docpdf] n page 471 undefined on input line 39011.
[docpdf] 
[docpdf] ! Missing { inserted.
[docpdf] <to be read again> 
[docpdf]                    _
[docpdf] l.39015 The current semantics of \(__
[docpdf]                                      call__\) are experimental, so a warning...
[docpdf] 
[docpdf] ? 
[docpdf] ! Emergency stop.
[docpdf] <to be read again> 
[docpdf]                    _
[docpdf] l.39015 The current semantics of \(__
[docpdf]                                      call__\) are experimental, so a warning...
[docpdf] 
[docpdf] !  ==> Fatal error occurred, no output PDF file produced!
[docpdf] Transcript written on polynomial_rings.log.

[git]

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

​204be65

fix doc building error

[tscrim]

I'm assuming that you wanted this back to needs review.

[jsrn]

Indeed, thanks. I seem to have too many things on my stack today ;-)

[tscrim]

This is now one less. :)

[vbraun]

Fails on 32-bit

sage -t --long src/sage/rings/polynomial/skew_polynomial_element.pyx
**********************************************************************
File "src/sage/rings/polynomial/skew_polynomial_element.pyx", line 299, in sage.rings.polynomial.skew_polynomial_element.SkewPolynomial.__hash__
Failed example:
    h = hash(a); h
Expected:
    -1717348446110052408
Got:
    -368406584
**********************************************************************
1 item had failures:
   1 of   6 in sage.rings.polynomial.skew_polynomial_element.SkewPolynomial.__hash__
    [722 tests, 1 failure, 0.57 s]

[tscrim]

Ah, right 32v64 bit. @jsm @arpitdm I would just make the doctest hash(a) == hash(a) and you can set a positive review on my behalf once that is done.

[git]

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

​ddb5d7f

Merge branch 'public/rings/skew_polynomials-13215' of trac.sagemath.org:sage into 13215_skew_polynomials

[git]

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

​7cb0cce

hash doctest as per reviewer's suggestion

[jsrn]

Done. Let's try again :-)