Skew Univariate 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:

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: sage.categories.map.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: sage.rings.morphism.RingHomomorphism

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

section()

Return a section of this morphism.

EXAMPLES:

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
class sage.rings.polynomial.skew_polynomial_ring.SkewPolynomialRing(base_ring, morphism, derivation, name, sparse, category=None)

Bases: sage.rings.polynomial.ore_polynomial_ring.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: 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()
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 – a 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: 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

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

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

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

sage: eval = b.multi_point_evaluation(eval_pts); eval
[0, 0, 0]

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: S.minimal_vanishing_polynomial([t])
x + 3*t^2 + 3*t
sage: S.minimal_vanishing_polynomial([t, 3*t])
x + 3*t^2 + 3*t
class sage.rings.polynomial.skew_polynomial_ring.SkewPolynomialRing_finite_field(base_ring, morphism, derivation, names, sparse, category=None)

Bases: sage.rings.polynomial.skew_polynomial_ring.SkewPolynomialRing_finite_order

A specialized class for skew polynomial rings over finite fields.

See also

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: sage.rings.polynomial.skew_polynomial_ring.SkewPolynomialRing

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

See also

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 – a string or None (default: None); the name for the central variable (namely \(x^r\))

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

EXAMPLES:

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

We can pass in another variable name:

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

or use the bracket notation:

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

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

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

together with a conversion map in the reverse direction:

sage: Zy(x^6 + 2*x^3 + 3)
y^2 + 2*y + 3

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

Two different skew polynomial rings can share the same center:

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

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

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

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