Opened 9 years ago

Last modified 5 years ago

#13215 closed enhancement

Skew polynomials — at Version 9

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: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #13214, #13303 Stopgaps:

Status badges

Description (last modified by 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.

The attached patch provides:

  1. a basic implementation of skew polynomials over any commutative ring (including addition, multiplication, euclidean division, gcd...)
  2. 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).

Change History (11)

comment:1 Changed 9 years ago by caruso

  • Status changed from new to needs_review

comment:2 Changed 9 years ago by caruso

  • Dependencies set to #13214
  • Description modified (diff)

Changed 9 years ago by caruso

comment:3 Changed 9 years ago by caruso

File trac_13215_skew_polynomials.2.patch replaces trac_13215_skew_polynomials.patch

comment:4 Changed 9 years ago by tfeulner

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

comment:6 Changed 9 years ago by caruso

  • Status changed from needs_work to needs_review

comment:7 Changed 9 years ago by 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

comment:8 Changed 9 years ago by 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?

Last edited 9 years ago by caruso (previous) (diff)

comment:9 Changed 9 years ago by caruso

  • Dependencies changed from #13214 to #13214, #13303
  • Description modified (diff)
Note: See TracTickets for help on using tickets.