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:
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 fromSkewPolynomialRing
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
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 ringtwisting_morphism
– an automorphism of the base ringname
– string or list of strings representing the name of the variables of ringsparse
– 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 ofself.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 ofself
; the \(x_i\) should be linearly independent over the fixed field ofself.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 ofeval_pts
are linearly independent over the fixed field ofself.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 orNone
(default:None
); the name for the central variable (namely \(x^r\))default
– a boolean (default:False
); ifTrue
, set the default variable name for the center toname
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