Skew Univariate Polynomial Rings¶
This module provides the
SkewPolynomialRing_general
,
which constructs a general dense univariate skew polynomials over commutative
base rings with automorphisms over the base rings. This is usual accessed only
indirectly through the constructor
sage.rings.polynomial.skew_polynomial_constructor.SkewPolynomialRing()
.
See SkewPolynomialRing_general
for a definition of a univariate skew
polynomial ring.
AUTHOR:
 Xavier Caruso (20120629): initial version
 Arpit Merchant (20160804): improved docstrings, fixed doctests and refactored classes and methods
 Johan Rosenkilde (20160803): changes for bug fixes, docstring and doctest errors

class
sage.rings.polynomial.skew_polynomial_ring.
SkewPolynomialRing_general
(base_ring, twist_map, name, sparse, element_class)¶ Bases:
sage.rings.ring.Algebra
,sage.structure.unique_representation.UniqueRepresentation
A general implementation of univariate skew polynomialring over a commutative ring.
Let \(R\) be a commutative ring, and let \(\sigma\) be an automorphism of \(R\). The ring of skew polynomials \(R[X, \sigma]\) is the polynomial ring \(R[X]\), where the addition is the usual polynomial addition, but the multiplication operation is defined by the modified rule
\[X*a = \sigma(a) X.\]This means that \(R[X, \sigma]\) is a noncommutative ring. Skew polynomials were first introduced by Ore [Ore33].
EXAMPLES:
sage: R.<t> = ZZ[] sage: sigma = R.hom([t+1]) sage: S.<x> = SkewPolynomialRing(R,sigma); S Skew Polynomial Ring in x over Univariate Polynomial Ring in t over Integer Ring twisted by t > t + 1
One can also use a shorter syntax:
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
If we omit the diamond notation, the variable holding the indeterminate is not assigned:
sage: Sy = R['y',sigma] sage: y Traceback (most recent call last): ... NameError: name 'y' is not defined sage: Sy.gen() y
Note however that contrary to usual polynomial rings, we cannot omit the variable name on the RHS, since this collides with the notation for creating polynomial rings:
sage: Sz.<z> = R[sigma] Traceback (most recent call last): ... ValueError: variable name 'Ring endomorphism of Univariate Polynomial Ring in t over Integer Ring\n Defn: t > t + 1' is not alphanumeric
Of course, skew polynomial rings with different twist maps are not equal either:
sage: R['x',sigma] == R['x',sigma^2] False
Saving and loading of polynomial rings works:
sage: loads(dumps(R['x',sigma])) == R['x',sigma] True
There is a coercion map from the base ring of the skew polynomial rings:
sage: S.has_coerce_map_from(R) True sage: x.parent() Skew Polynomial Ring in x over Univariate Polynomial Ring in t over Integer Ring twisted by t > t + 1 sage: t.parent() Univariate Polynomial Ring in t over Integer Ring sage: y = x+t; y x + t sage: y.parent() is S True
See also
sage.rings.polynomial.skew_polynomial_ring_constructor.SkewPolynomialRing()
sage.rings.polynomial.skew_polynomial_element
REFERENCES:
[Ore33] Oystein Ore. Theory of NonCommutative Polynomials Annals of Mathematics, Second Series, Volume 34, Issue 3 (Jul., 1933), 480508. 
change_var
(var)¶ Return the skew polynomial ring in variable
var
with the same base ring and twist map asself
.INPUT:
var
– a string representing the name of the new variable.
OUTPUT:
self
with variable name changed tovar
.EXAMPLES:
sage: k.<t> = GF(5^3) sage: Frob = k.frobenius_endomorphism() sage: R.<x> = SkewPolynomialRing(k,Frob); R Skew Polynomial Ring in x over Finite Field in t of size 5^3 twisted by t > t^5 sage: Ry = R.change_var('y'); Ry Skew Polynomial Ring in y over Finite Field in t of size 5^3 twisted by t > t^5 sage: Ry is R.change_var('y') True

characteristic
()¶ Return the characteristic of the base ring of
self
.EXAMPLES:
sage: R.<t> = QQ[] sage: sigma = R.hom([t+1]) sage: R['x',sigma].characteristic() 0 sage: k.<u> = GF(5^3) sage: Frob = k.frobenius_endomorphism() sage: k['y',Frob].characteristic() 5

gen
(n=0)¶ Return the indeterminate generator of this skew polynomial ring.
INPUT:
n
– index of generator to return (default: 0). Exists for compatibility with other polynomial rings.
EXAMPLES:
sage: R.<t> = QQ[] 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 Rational Field twisted by t > t + 1 sage: y = S.gen(); y x sage: y == x True sage: y is x True sage: S.gen(0) x
This is also known as the parameter:
sage: S.parameter() is S.gen() True

gens_dict
()¶ Return a {name: variable} dictionary of the generators of
self
.EXAMPLES:
sage: R.<t> = ZZ[] sage: sigma = R.hom([t+1]) sage: S.<x> = SkewPolynomialRing(R,sigma) sage: S.gens_dict() {'x': x}

is_commutative
()¶ Return
True
if this skew polynomial ring is commutative, i.e. if the twist map is the identity.EXAMPLES:
sage: k.<t> = GF(5^3) sage: Frob = k.frobenius_endomorphism() sage: S.<x> = k['x',Frob] sage: S.is_commutative() False sage: T.<y> = k['y',Frob^3] sage: T.is_commutative() True

is_exact
()¶ Return
True
if elements of this skew polynomial ring are exact. This happens if and only if elements of the base ring are exact.EXAMPLES:
sage: k.<t> = GF(5^3) sage: Frob = k.frobenius_endomorphism() sage: S.<x> = k['x',Frob] sage: S.is_exact() True sage: S.base_ring().is_exact() True sage: R.<u> = k[[]] sage: sigma = R.hom([u+u^2]) sage: T.<y> = R['y',sigma] sage: T.is_exact() False sage: T.base_ring().is_exact() False

is_finite
()¶ Return
False
since skew polynomial rings are not finite (unless the base ring is \(0\).)EXAMPLES:
sage: k.<t> = GF(5^3) sage: k.is_finite() True sage: Frob = k.frobenius_endomorphism() sage: S.<x> = k['x',Frob] sage: S.is_finite() False

is_sparse
()¶ Return
True
if the elements of this polynomial ring are sparsely represented.Warning
Since sparse skew polynomials are not yet implemented, this function always returns
False
.EXAMPLES:
sage: R.<t> = RR[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: S.is_sparse() False

lagrange_polynomial
(points)¶ Return the minimaldegree polynomial which interpolates the given points.
More precisely, given \(n\) pairs \((x_1, y_1), ..., (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.twist_map()
.If the \(x_i\) are linearly independent over the fixed field of
self.twist_map()
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),..., (x_n, y_n)
of elements of the base ring ofself
. The \(x_i\) should be linearly independent over the fixed field ofself.twist_map()
.
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.twist_map()
, 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 twist map, so a Lagrange polynomial could not be determined (and might not exist).

minimal_vanishing_polynomial
(eval_pts)¶ Return the minimaldegree, 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.twist_map()
.INPUT:
eval_pts
– list of evaluation points which are linearly independent over the fixed field of the twist map 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 twist map, 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

ngens
()¶ Return the number of generators of this skew polynomial ring, which is 1.
EXAMPLES:
sage: R.<t> = RR[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: S.ngens() 1

parameter
(n=0)¶ Return the indeterminate generator of this skew polynomial ring.
INPUT:
n
– index of generator to return (default: 0). Exists for compatibility with other polynomial rings.
EXAMPLES:
sage: R.<t> = QQ[] 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 Rational Field twisted by t > t + 1 sage: y = S.gen(); y x sage: y == x True sage: y is x True sage: S.gen(0) x
This is also known as the parameter:
sage: S.parameter() is S.gen() True

random_element
(degree=2, monic=False, *args, **kwds)¶ Return a random skew polynomial in
self
.INPUT:
degree
– (default: 2) integer with degree or a tuple of integers with minimum and maximum degreesmonic
– (default:False
) ifTrue
, return a monic skew polynomial*args, **kwds
– passed on to therandom_element
method for the base ring
OUTPUT:
Skew polynomial such that the coefficients of \(x^i\), for \(i\) up to
degree
, are random elements from the base ring, randomized subject to the arguments*args
and**kwds
.EXAMPLES:
sage: k.<t> = GF(5^3) sage: Frob = k.frobenius_endomorphism() sage: S.<x> = k['x', Frob] sage: S.random_element() # random (2*t^2 + 3)*x^2 + (4*t^2 + t + 4)*x + 2*t^2 + 2 sage: S.random_element(monic=True) # random x^2 + (2*t^2 + t + 1)*x + 3*t^2 + 3*t + 2
Use
degree
to obtain polynomials of higher degreesage: p = S.random_element(degree=5) # random (t^2 + 3*t)*x^4 + (4*t + 4)*x^3 + (4*t^2 + 4*t)*x^2 + (2*t^2 + 1)*x + 3When
monic
isFalse
, the returned skew polynomial may have a degree less thandegree
(it happens when the random leading coefficient is zero). However, ifmonic
isTrue
, this can’t happen:sage: p = S.random_element(degree=4, monic=True) sage: p.leading_coefficient() == S.base_ring().one() True sage: p.degree() == 4 True
If a tuple of two integers is given for the degree argument, a random integer will be chosen between the first and second element of the tuple as the degree, both inclusive:
sage: S.random_element(degree=(2,7)) # random (3*t^2 + 1)*x^4 + (4*t + 2)*x^3 + (4*t + 1)*x^2 + (t^2 + 3*t + 3)*x + 3*t^2 + 2*t + 2
If the first tuple element is greater than the second, a a
ValueError
is raised:sage: S.random_element(degree=(5,4)) Traceback (most recent call last): ... ValueError: first degree argument must be less or equal to the second

twist_map
(n=1)¶ Return the twist map, the automorphism of the base ring of
self
, iteratedn
times.INPUT:
n
 an integer (default: 1)
OUTPUT:
n
th iterative of the twist map of this skew polynomial ring.EXAMPLES:
sage: R.<t> = QQ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: S.twist_map() Ring endomorphism of Univariate Polynomial Ring in t over Rational Field Defn: t > t + 1 sage: S.twist_map() == sigma True sage: S.twist_map(10) Ring endomorphism of Univariate Polynomial Ring in t over Rational Field Defn: t > t + 10
If
n
in negative, Sage tries to compute the inverse of the twist map:sage: k.<t> = GF(5^3) sage: Frob = k.frobenius_endomorphism() sage: T.<y> = k['y',Frob] sage: T.twist_map(1) Frobenius endomorphism t > t^(5^2) on Finite Field in t of size 5^3
Sometimes it fails, even if the twist map is actually invertible:
sage: S.twist_map(1) Traceback (most recent call last): ... NotImplementedError: inversion of the twist map Ring endomorphism of Univariate Polynomial Ring in t over Rational Field Defn: t > t + 1
