Univariate skew polynomial rings

This module provides the SkewPolynomialRing. In the class hierarchy in Sage, the locution Skew Polynomial is used for a Ore polynomial without twisting derivation.

This module also provides:

• the class SkewPolynomialRing_finite_order, which is a specialized class for skew polynomial rings over fields equipped with an automorphism of finite order. It inherits from SkewPolynomialRing but contains more methods and provides better algorithms.

• the class SkewPolynomialRing_finite_field, which is a specialized class for skew polynomial rings over finite fields.

See also

OrePolynomialRing

AUTHOR:

• Xavier Caruso (2012-06-29): initial version

• Arpit Merchant (2016-08-04): improved docstrings, fixed doctests and refactored classes and methods

• Johan Rosenkilde (2016-08-03): changes for bug fixes, docstring and doctest errors

class sage.rings.polynomial.skew_polynomial_ring.SectionSkewPolynomialCenterInjection

Bases: Section

Section of the canonical injection of the center of a skew polynomial ring into this ring.

class sage.rings.polynomial.skew_polynomial_ring.SkewPolynomialCenterInjection(domain, codomain, embed, order)

Bases: RingHomomorphism

Canonical injection of the center of a skew polynomial ring into this ring.

section()

Return a section of this morphism.

EXAMPLES:

Sage

sage: # needs sage.rings.finite_rings
sage: k.<a> = GF(5^3)
sage: S.<x> = SkewPolynomialRing(k, k.frobenius_endomorphism())
sage: Z = S.center()
sage: iota = S.convert_map_from(Z)
sage: sigma = iota.section()
sage: sigma(x^3)
z

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> k = GF(Integer(5)**Integer(3), names=('a',)); (a,) = k._first_ngens(1)
>>> S = SkewPolynomialRing(k, k.frobenius_endomorphism(), names=('x',)); (x,) = S._first_ngens(1)
>>> Z = S.center()
>>> iota = S.convert_map_from(Z)
>>> sigma = iota.section()
>>> sigma(x**Integer(3))
z

Sage Live

# needs sage.rings.finite_rings
k.<a> = GF(5^3)
S.<x> = SkewPolynomialRing(k, k.frobenius_endomorphism())
Z = S.center()
iota = S.convert_map_from(Z)
sigma = iota.section()
sigma(x^3)

class sage.rings.polynomial.skew_polynomial_ring.SkewPolynomialRing(base_ring, morphism, derivation, name, sparse, category=None)

Bases: OrePolynomialRing

Initialize self.

INPUT:

• base_ring – a commutative ring

• twisting_morphism – an automorphism of the base ring

• name – string or list of strings representing the name of the variables of ring

• sparse – boolean (default: False)

• category – a category

EXAMPLES:

Sage

sage: R.<t> = ZZ[]
sage: sigma = R.hom([t + 1])
sage: S.<x> = SkewPolynomialRing(R,sigma)
sage: S.category()
Category of algebras over Univariate Polynomial Ring in t over Integer Ring
sage: S([1]) + S([-1])
0
sage: TestSuite(S).run()

Python

>>> from sage.all import *
>>> R = ZZ['t']; (t,) = R._first_ngens(1)
>>> sigma = R.hom([t + Integer(1)])
>>> S = SkewPolynomialRing(R,sigma, names=('x',)); (x,) = S._first_ngens(1)
>>> S.category()
Category of algebras over Univariate Polynomial Ring in t over Integer Ring
>>> S([Integer(1)]) + S([-Integer(1)])
0
>>> TestSuite(S).run()

Sage Live

R.<t> = ZZ[]
sigma = R.hom([t + 1])
S.<x> = SkewPolynomialRing(R,sigma)
S.category()
S([1]) + S([-1])
TestSuite(S).run()

lagrange_polynomial(points)

Return the minimal-degree polynomial which interpolates the given points.

More precisely, given \(n\) pairs \((x_1, y_1), \ldots, (x_n, y_n) \in R^2\), where \(R\) is self.base_ring(), compute a skew polynomial \(p(x)\) such that \(p(x_i) = y_i\) for each \(i\), under the condition that the \(x_i\) are linearly independent over the fixed field of self.twisting_morphism().

If the \(x_i\) are linearly independent over the fixed field of self.twisting_morphism() then such a polynomial is guaranteed to exist. Otherwise, it might exist depending on the \(y_i\), but the algorithm used in this implementation does not support that, and so an error is always raised.

INPUT:

• points – list of pairs \((x_1, y_1), \ldots, (x_n, y_n)\) of elements of the base ring of self; the \(x_i\) should be linearly independent over the fixed field of self.twisting_morphism()

OUTPUT: the Lagrange polynomial

EXAMPLES:

Sage

sage: # needs sage.rings.finite_rings
sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x', Frob]
sage: points = [(t, 3*t^2 + 4*t + 4), (t^2, 4*t)]
sage: d = S.lagrange_polynomial(points); d
x + t

sage: R.<t> = ZZ[]
sage: sigma = R.hom([t + 1])
sage: T.<x> = R['x', sigma]
sage: points = [(1, t^2 + 3*t + 4), (t, 2*t^2 + 3*t + 1), (t^2, t^2 + 3*t + 4)]
sage: p = T.lagrange_polynomial(points); p
((-t^4 - 2*t - 3)/-2)*x^2 + (-t^4 - t^3 - t^2 - 3*t - 2)*x
 + (-t^4 - 2*t^3 - 4*t^2 - 10*t - 9)/-2
sage: p.multi_point_evaluation([1, t, t^2]) == [t^2 + 3*t + 4, 2*t^2 + 3*t + 1, t^2 + 3*t + 4]
True

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> k = GF(Integer(5)**Integer(3), names=('t',)); (t,) = k._first_ngens(1)
>>> Frob = k.frobenius_endomorphism()
>>> S = k['x', Frob]; (x,) = S._first_ngens(1)
>>> points = [(t, Integer(3)*t**Integer(2) + Integer(4)*t + Integer(4)), (t**Integer(2), Integer(4)*t)]
>>> d = S.lagrange_polynomial(points); d
x + t

>>> R = ZZ['t']; (t,) = R._first_ngens(1)
>>> sigma = R.hom([t + Integer(1)])
>>> T = R['x', sigma]; (x,) = T._first_ngens(1)
>>> points = [(Integer(1), t**Integer(2) + Integer(3)*t + Integer(4)), (t, Integer(2)*t**Integer(2) + Integer(3)*t + Integer(1)), (t**Integer(2), t**Integer(2) + Integer(3)*t + Integer(4))]
>>> p = T.lagrange_polynomial(points); p
((-t^4 - 2*t - 3)/-2)*x^2 + (-t^4 - t^3 - t^2 - 3*t - 2)*x
 + (-t^4 - 2*t^3 - 4*t^2 - 10*t - 9)/-2
>>> p.multi_point_evaluation([Integer(1), t, t**Integer(2)]) == [t**Integer(2) + Integer(3)*t + Integer(4), Integer(2)*t**Integer(2) + Integer(3)*t + Integer(1), t**Integer(2) + Integer(3)*t + Integer(4)]
True

Sage Live

# needs sage.rings.finite_rings
k.<t> = GF(5^3)
Frob = k.frobenius_endomorphism()
S.<x> = k['x', Frob]
points = [(t, 3*t^2 + 4*t + 4), (t^2, 4*t)]
d = S.lagrange_polynomial(points); d
R.<t> = ZZ[]
sigma = R.hom([t + 1])
T.<x> = R['x', sigma]
points = [(1, t^2 + 3*t + 4), (t, 2*t^2 + 3*t + 1), (t^2, t^2 + 3*t + 4)]
p = T.lagrange_polynomial(points); p
p.multi_point_evaluation([1, t, t^2]) == [t^2 + 3*t + 4, 2*t^2 + 3*t + 1, t^2 + 3*t + 4]

If the \(x_i\) are linearly dependent over the fixed field of self.twisting_morphism(), then an error is raised:

Sage

sage: T.lagrange_polynomial([(t, 1), (2*t, 3)])
Traceback (most recent call last):
...
ValueError: the given evaluation points are linearly dependent over the fixed field of the twisting morphism,
so a Lagrange polynomial could not be determined (and might not exist)

Python

>>> from sage.all import *
>>> T.lagrange_polynomial([(t, Integer(1)), (Integer(2)*t, Integer(3))])
Traceback (most recent call last):
...
ValueError: the given evaluation points are linearly dependent over the fixed field of the twisting morphism,
so a Lagrange polynomial could not be determined (and might not exist)

Sage Live

T.lagrange_polynomial([(t, 1), (2*t, 3)])

minimal_vanishing_polynomial(eval_pts)

Return the minimal-degree, monic skew polynomial which vanishes at all the given evaluation points.

The degree of the vanishing polynomial is at most the length of eval_pts. Equality holds if and only if the elements of eval_pts are linearly independent over the fixed field of self.twisting_morphism().

• eval_pts – list of evaluation points which are linearly independent over the fixed field of the twisting morphism of the associated skew polynomial ring

OUTPUT: the minimal vanishing polynomial

EXAMPLES:

Sage

sage: # needs sage.rings.finite_rings
sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x', Frob]
sage: eval_pts = [1, t, t^2]
sage: b = S.minimal_vanishing_polynomial(eval_pts); b
x^3 + 4

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> k = GF(Integer(5)**Integer(3), names=('t',)); (t,) = k._first_ngens(1)
>>> Frob = k.frobenius_endomorphism()
>>> S = k['x', Frob]; (x,) = S._first_ngens(1)
>>> eval_pts = [Integer(1), t, t**Integer(2)]
>>> b = S.minimal_vanishing_polynomial(eval_pts); b
x^3 + 4

Sage Live

# needs sage.rings.finite_rings
k.<t> = GF(5^3)
Frob = k.frobenius_endomorphism()
S.<x> = k['x', Frob]
eval_pts = [1, t, t^2]
b = S.minimal_vanishing_polynomial(eval_pts); b

The minimal vanishing polynomial evaluates to 0 at each of the evaluation points:

Sage

sage: eval = b.multi_point_evaluation(eval_pts); eval                       # needs sage.rings.finite_rings
[0, 0, 0]

Python

>>> from sage.all import *
>>> eval = b.multi_point_evaluation(eval_pts); eval                       # needs sage.rings.finite_rings
[0, 0, 0]

Sage Live

eval = b.multi_point_evaluation(eval_pts); eval                       # needs sage.rings.finite_rings

If the evaluation points are linearly dependent over the fixed field of the twisting morphism, then the returned polynomial has lower degree than the number of evaluation points:

Sage

sage: S.minimal_vanishing_polynomial([t])                                   # needs sage.rings.finite_rings
x + 3*t^2 + 3*t
sage: S.minimal_vanishing_polynomial([t, 3*t])                              # needs sage.rings.finite_rings
x + 3*t^2 + 3*t

Python

>>> from sage.all import *
>>> S.minimal_vanishing_polynomial([t])                                   # needs sage.rings.finite_rings
x + 3*t^2 + 3*t
>>> S.minimal_vanishing_polynomial([t, Integer(3)*t])                              # needs sage.rings.finite_rings
x + 3*t^2 + 3*t

Sage Live

S.minimal_vanishing_polynomial([t])                                   # needs sage.rings.finite_rings
S.minimal_vanishing_polynomial([t, 3*t])                              # needs sage.rings.finite_rings

class sage.rings.polynomial.skew_polynomial_ring.SkewPolynomialRing_finite_field(base_ring, morphism, derivation, names, sparse, category=None)

Bases: SkewPolynomialRing_finite_order

A specialized class for skew polynomial rings over finite fields.

See also

• sage.rings.polynomial.skew_polynomial_ring.SkewPolynomialRing

• sage.rings.polynomial.skew_polynomial_finite_field

Todo

Add methods related to center of skew polynomial ring, irreducibility, karatsuba multiplication and factorization.

class sage.rings.polynomial.skew_polynomial_ring.SkewPolynomialRing_finite_order(base_ring, morphism, derivation, name, sparse, category=None)

Bases: SkewPolynomialRing

A specialized class for skew polynomial rings whose twising morphism has finite order.

See also

• sage.rings.polynomial.skew_polynomial_ring.SkewPolynomialRing

• sage.rings.polynomial.skew_polynomial_finite_order

center(name=None, names=None, default=False)

Return the center of this skew polynomial ring.

Note

If \(F\) denotes the subring of \(R\) fixed by \(\sigma\) and \(\sigma\) has order \(r\), the center of \(K[x,\sigma]\) is \(F[x^r]\), that is a univariate polynomial ring over \(F\).

INPUT:

• name – string or None (default: None); the name for the central variable (namely \(x^r\))

• default – boolean (default: False); if True, set the default variable name for the center to name

EXAMPLES:

Sage

sage: # needs sage.rings.finite_rings
sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x',Frob]; S
Ore Polynomial Ring in x over Finite Field in t of size 5^3
 twisted by t |--> t^5
sage: Z = S.center(); Z
Univariate Polynomial Ring in z over Finite Field of size 5
sage: Z.gen()
z

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> k = GF(Integer(5)**Integer(3), names=('t',)); (t,) = k._first_ngens(1)
>>> Frob = k.frobenius_endomorphism()
>>> S = k['x',Frob]; (x,) = S._first_ngens(1); S
Ore Polynomial Ring in x over Finite Field in t of size 5^3
 twisted by t |--> t^5
>>> Z = S.center(); Z
Univariate Polynomial Ring in z over Finite Field of size 5
>>> Z.gen()
z

Sage Live

# needs sage.rings.finite_rings
k.<t> = GF(5^3)
Frob = k.frobenius_endomorphism()
S.<x> = k['x',Frob]; S
Z = S.center(); Z
Z.gen()

We can pass in another variable name:

Sage

sage: S.center(name='y')                                                    # needs sage.rings.finite_rings
Univariate Polynomial Ring in y over Finite Field of size 5

Python

>>> from sage.all import *
>>> S.center(name='y')                                                    # needs sage.rings.finite_rings
Univariate Polynomial Ring in y over Finite Field of size 5

Sage Live

S.center(name='y')                                                    # needs sage.rings.finite_rings

or use the bracket notation:

Sage

sage: Zy.<y> = S.center(); Zy                                               # needs sage.rings.finite_rings
Univariate Polynomial Ring in y over Finite Field of size 5
sage: y.parent() is Zy                                                      # needs sage.rings.finite_rings
True

Python

>>> from sage.all import *
>>> Zy = S.center(names=('y',)); (y,) = Zy._first_ngens(1); Zy                                               # needs sage.rings.finite_rings
Univariate Polynomial Ring in y over Finite Field of size 5
>>> y.parent() is Zy                                                      # needs sage.rings.finite_rings
True

Sage Live

Zy.<y> = S.center(); Zy                                               # needs sage.rings.finite_rings
y.parent() is Zy                                                      # needs sage.rings.finite_rings

A coercion map from the center to the skew polynomial ring is set:

Sage

sage: # needs sage.rings.finite_rings
sage: S.has_coerce_map_from(Zy)
True
sage: P = y + x; P
x^3 + x
sage: P.parent()
Ore Polynomial Ring in x over Finite Field in t of size 5^3
 twisted by t |--> t^5
sage: P.parent() is S
True

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> S.has_coerce_map_from(Zy)
True
>>> P = y + x; P
x^3 + x
>>> P.parent()
Ore Polynomial Ring in x over Finite Field in t of size 5^3
 twisted by t |--> t^5
>>> P.parent() is S
True

Sage Live

# needs sage.rings.finite_rings
S.has_coerce_map_from(Zy)
P = y + x; P
P.parent()
P.parent() is S

together with a conversion map in the reverse direction:

Sage

sage: Zy(x^6 + 2*x^3 + 3)                                                   # needs sage.rings.finite_rings
y^2 + 2*y + 3

sage: Zy(x^2)                                                               # needs sage.rings.finite_rings
Traceback (most recent call last):
...
ValueError: x^2 is not in the center

Python

>>> from sage.all import *
>>> Zy(x**Integer(6) + Integer(2)*x**Integer(3) + Integer(3))                                                   # needs sage.rings.finite_rings
y^2 + 2*y + 3

>>> Zy(x**Integer(2))                                                               # needs sage.rings.finite_rings
Traceback (most recent call last):
...
ValueError: x^2 is not in the center

Sage Live

Zy(x^6 + 2*x^3 + 3)                                                   # needs sage.rings.finite_rings
Zy(x^2)                                                               # needs sage.rings.finite_rings

Two different skew polynomial rings can share the same center:

Sage

sage: S1.<x1> = k['x1', Frob]                                               # needs sage.rings.finite_rings
sage: S2.<x2> = k['x2', Frob]                                               # needs sage.rings.finite_rings
sage: S1.center() is S2.center()                                            # needs sage.rings.finite_rings
True

Python

>>> from sage.all import *
>>> S1 = k['x1', Frob]; (x1,) = S1._first_ngens(1)# needs sage.rings.finite_rings
>>> S2 = k['x2', Frob]; (x2,) = S2._first_ngens(1)# needs sage.rings.finite_rings
>>> S1.center() is S2.center()                                            # needs sage.rings.finite_rings
True

Sage Live

S1.<x1> = k['x1', Frob]                                               # needs sage.rings.finite_rings
S2.<x2> = k['x2', Frob]                                               # needs sage.rings.finite_rings
S1.center() is S2.center()                                            # needs sage.rings.finite_rings

About the default name of the central variable

A priori, the default is z.

However, a variable name is given the first time this method is called, the given name become the default for the next calls:

Sage

sage: # needs sage.rings.finite_rings
sage: K.<t> = GF(11^3)
sage: phi = K.frobenius_endomorphism()
sage: A.<X> = K['X', phi]
sage: C.<u> = A.center()  # first call
sage: C
Univariate Polynomial Ring in u over Finite Field of size 11
sage: A.center()  # second call: the variable name is still u
Univariate Polynomial Ring in u over Finite Field of size 11
sage: A.center() is C
True

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> K = GF(Integer(11)**Integer(3), names=('t',)); (t,) = K._first_ngens(1)
>>> phi = K.frobenius_endomorphism()
>>> A = K['X', phi]; (X,) = A._first_ngens(1)
>>> C = A.center(names=('u',)); (u,) = C._first_ngens(1)# first call
>>> C
Univariate Polynomial Ring in u over Finite Field of size 11
>>> A.center()  # second call: the variable name is still u
Univariate Polynomial Ring in u over Finite Field of size 11
>>> A.center() is C
True

Sage Live

# needs sage.rings.finite_rings
K.<t> = GF(11^3)
phi = K.frobenius_endomorphism()
A.<X> = K['X', phi]
C.<u> = A.center()  # first call
C
A.center()  # second call: the variable name is still u
A.center() is C

We can update the default variable name by passing in the argument default=True:

Sage

sage: # needs sage.rings.finite_rings
sage: D.<v> = A.center(default=True)
sage: D
Univariate Polynomial Ring in v over Finite Field of size 11
sage: A.center()
Univariate Polynomial Ring in v over Finite Field of size 11
sage: A.center() is D
True

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> D = A.center(default=True, names=('v',)); (v,) = D._first_ngens(1)
>>> D
Univariate Polynomial Ring in v over Finite Field of size 11
>>> A.center()
Univariate Polynomial Ring in v over Finite Field of size 11
>>> A.center() is D
True

Sage Live

# needs sage.rings.finite_rings
D.<v> = A.center(default=True)
D
A.center()
A.center() is D

Make live