Opened 9 years ago
Last modified 5 years ago
#13215 closed enhancement
Skew polynomials — at Version 23
Reported by: | caruso | Owned by: | tbd |
---|---|---|---|
Priority: | major | Milestone: | sage-7.4 |
Component: | algebra | Keywords: | skew polynomials, sd75 |
Cc: | tfeulner, caruso, burcin, jsrn, dlucas, tscrim | Merged in: | |
Authors: | Xavier Caruso | Reviewers: | Burcin Erocal |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #13214, #13303, #13640, #13641, #13642 | Stopgaps: |
Description (last modified by )
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.
The attached patch provides:
- a basic implementation of skew polynomials over any commutative ring (including addition, multiplication, euclidean division, gcd...)
- a more complete implementation of skew polynomials over finite fields (including factoring)
NB: This ticket depends on
- ticket #13214: Frobenius endomorphisms over finite fields
- ticket #13642: Fast modular exponentiation (only for speed)
Change History (30)
comment:1 Changed 9 years ago by
- Status changed from new to needs_review
comment:2 Changed 9 years ago by
- Dependencies set to #13214
- Description modified (diff)
Changed 9 years ago by
comment:3 Changed 9 years ago by
comment:4 Changed 9 years ago by
- Cc tfeulner added
- Status changed from needs_review to needs_work
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
comment:5 Changed 9 years ago by
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?)
comment:6 Changed 9 years ago by
- Status changed from needs_work to needs_review
comment:7 Changed 9 years ago by
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
Changed 9 years ago by
comment:8 Changed 9 years ago by
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?
comment:9 Changed 9 years ago by
- Dependencies changed from #13214 to #13214, #13303
- Description modified (diff)
comment:10 Changed 9 years ago by
- Cc caruso added
comment:11 Changed 9 years ago by
Please fill in your real name as Author.
comment:12 Changed 9 years ago by
comment:13 Changed 9 years ago by
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
, andx-I.reduce(x) \in I
, for allx \in R
.
With this default behaviour, the quotient ring is just a copy of the original ring R.
Best, Thomas
comment:14 Changed 9 years ago by
- Cc burcin added
- Component changed from experimental package to algebra
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?
comment:15 follow-up: ↓ 16 Changed 9 years ago by
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?).
comment:16 in reply to: ↑ 15 ; follow-up: ↓ 19 Changed 9 years ago by
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.
comment:17 follow-up: ↓ 18 Changed 9 years ago by
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?
comment:18 in reply to: ↑ 17 Changed 9 years ago by
- Description modified (diff)
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)()
comment:19 in reply to: ↑ 16 ; follow-up: ↓ 21 Changed 9 years ago by
- Reviewers set to Burcin Erocal
- Status changed from needs_review to needs_work
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 aMorphism
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 insage/rings/polynomial/skewpolynomial_ring.py
. There is also a filesage/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 ofskewpolynomial
.
- Are the
Left
andRight
objects defined insage/structure/side.py
really necessary? IfRight
is the default, can't you just have a keyword argumentleft=<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): ----------------------------------------------------------------------
comment:20 Changed 9 years ago by
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)
comment:21 in reply to: ↑ 19 Changed 9 years ago by
- Dependencies changed from #13214, #13303 to #13214, #13303, #13640, #13641, #13642
- Description modified (diff)
- Status changed from needs_work to needs_review
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 aMorphism
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 ofskewpolynomial
.
Done.
- Are the
Left
andRight
objects defined insage/structure/side.py
really necessary? IfRight
is the default, can't you just have a keyword argumentleft=<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).
Changed 9 years ago by
Changed 9 years ago by
comment:22 Changed 8 years ago by
- Cc darij added
Changed 8 years ago by
Changed 8 years ago by
comment:23 Changed 8 years ago by
- Description modified (diff)
I've posted an updated version of this patch which should apply at the top of sage 5-10 (hopefully).
File trac_13215_skew_polynomials.2.patch replaces trac_13215_skew_polynomials.patch