Skew polynomials

[xcaruso]

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

CC: @sagetrac-tfeulner @xcaruso @burcin @johanrosenkilde @sagetrac-dlucas @tscrim

Component: algebra

Keywords: skew polynomials, sd75

Author: Xavier Caruso, Arpit Merchant, Johan Rosenkilde

Branch/Commit: 7cb0cce

Reviewer: Burcin Erocal, David Lucas, Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/13215

[xcaruso]

Dependencies: #13214

[xcaruso]

Attachment: trac_13215_skew_polynomials.2.patch.gz

[xcaruso]

comment:3

File trac_13215_skew_polynomials.2.patch replaces trac_13215_skew_polynomials.patch

[sagetrac-tfeulner]

comment:4

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

[xcaruso]

comment:5

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?)

[sagetrac-tfeulner]

comment:7

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

[xcaruso]

Attachment: trac_13303_invert_polynomial_quotient_rings.patch.gz

[xcaruso]

comment:8

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?

[xcaruso]

Changed dependencies from #13214 to #13214, #13303

[jdemeyer]

comment:11

Please fill in your real name as Author.

[xcaruso]

Author: Xavier Caruso

[sagetrac-tfeulner]

comment:13

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]

comment:14

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?

[xcaruso]

comment:15

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]

comment:16

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 @xcaruso:

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.

[xcaruso]

comment:17

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]

comment:18

Replying to @xcaruso:

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)()

[sagetrac-git]

Changed commit from e72a8cc to 204be65

[sagetrac-git]

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

204be65

fix doc building error

[tscrim]

comment:242

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

[johanrosenkilde]

comment:243

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

[tscrim]

comment:244

This is now one less. :)

[vbraun]

comment:245

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]

comment:246

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.

[sagetrac-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

[sagetrac-git]

Changed commit from 204be65 to ddb5d7f

[sagetrac-git]

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

7cb0cce

hash doctest as per reviewer's suggestion

[sagetrac-git]

Changed commit from ddb5d7f to 7cb0cce

[johanrosenkilde]

comment:249

Done. Let's try again :-)

[vbraun]

Changed branch from public/rings/skew_polynomials-13215 to 7cb0cce