#13215: Skew polynomials
----------------------------------------------------------+-----------------
Reporter: caruso | Owner: tbd
Type: enhancement | Status:
needs_review
Priority: major | Milestone:
sage-5.4
Component: algebra | Resolution:
Keywords: skew polynomials | Work issues:
Report Upstream: N/A | Reviewers:
Burcin Erocal
Authors: Xavier Caruso | Merged in:
Dependencies: #13214, #13303, #13640, #13641, #13642 | Stopgaps:
----------------------------------------------------------+-----------------
Changes (by caruso):
* status: needs_work => needs_review
* dependencies: #13214, #13303 => #13214, #13303, #13640, #13641, #13642
Old description:
> 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:
>
> 1. a basic implementation of skew polynomials over any commutative ring
> (including addition, multiplication, euclidean division, gcd...)
> 1. a more complete implementation of skew polynomials over finite fields
> (including factoring)
>
> NB: This ticket depends on tickets #13214 (which implements Frobenius
> endomorphisms over finite fields) and #13303 (which fixes a bug in
> quotient_polynomial_ring_element.pyx). For convenience, I reattach the
> corresponding patches here (you need to apply these two patches first).
>
> Apply: attachment:trac_13215_skew_polynomials.patch
New description:
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:
1. a basic implementation of skew polynomials over any commutative ring
(including addition, multiplication, euclidean division, gcd...)
1. a more complete implementation of skew polynomials over finite fields
(including factoring)
NB: This ticket depends on tickets #13214 (Frobenius endomorphisms over
finite fields), #13303 (which fixes a bug in
quotient_polynomial_ring_element.pyx), #13640 (some q-numbers), #13641
(short representation for morphisms), #13642 (fast modular exponentiation,
only for speed). You need to apply the corresponding patches first.
Apply: attachment:trac_13215_skew_polynomials.patch
--
Comment:
Thanks a lot for all your comments!
Replying to [comment:19 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).
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13215#comment:21>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
