Univariate Skew Polynomials¶
This module provides the
SkewPolynomial
,
which constructs a single univariate skew polynomial over commutative
base rings and an automorphism over the base ring. Skew polynomials are
noncommutative and so principal methods such as gcd, lcm, monic,
multiplication, and division are given in left and right forms.
The generic implementation of dense skew polynomials is
SkewPolynomial_generic_dense
.
The classes
ConstantSkewPolynomialSection
and SkewPolynomialBaseringInjection
handle conversion from a skew polynomial ring to its base ring and vice versa respectively.
Warning
The current semantics of
__call__()
are experimental, so a warning is thrown when a skew polynomial is evaluated
for the first time in a session. See the method documentation for details.
AUTHORS:
 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_element.
ConstantSkewPolynomialSection
¶ Bases:
sage.categories.map.Map
Representation of the canonical homomorphism from the constants of a skew polynomial ring to the base ring.
This class is necessary for automatic coercion from zerodegree skew polynomial ring into the base ring.
EXAMPLES:
sage: from sage.rings.polynomial.skew_polynomial_element import ConstantSkewPolynomialSection sage: R.<t> = QQ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: m = ConstantSkewPolynomialSection(S, R); m Generic map: From: Skew Polynomial Ring in x over Univariate Polynomial Ring in t over Rational Field twisted by t > t + 1 To: Univariate Polynomial Ring in t over Rational Field

class
sage.rings.polynomial.skew_polynomial_element.
SkewPolynomial
¶ Bases:
sage.structure.element.AlgebraElement
Abstract base class for skew polynomials.
This class must be inherited from and have key methods overridden.
Definition
Let \(R\) be a commutative ring equipped with an automorphism \(\sigma\).
Then, a skew polynomial is given by the equation:
\[F(X) = a_{n} X^{n} + \cdots + a_0,\]where the coefficients \(a_i \in R\) and \(X\) is a formal variable.
Addition between two skew polynomials is defined by the usual addition operation and the modified multiplication is defined by the rule \(X a = \sigma(a) X\) for all \(a\) in \(R\). Skew polynomials are thus noncommutative and the degree of a product is equal to the sum of the degrees of the factors.
Let \(a\) and \(b\) be two skew polynomials in the same ring \(S\). The left (resp. right) euclidean division of \(a\) by \(b\) is a couple \((q,r)\) of elements in \(S\) such that
 \(a = q b + r\) (resp. \(a = b q + r\))
 the degree of \(r\) is less than the degree of \(b\)
\(q\) (resp. \(r\)) is called the quotient (resp. the remainder) of this euclidean division.
Properties
Keeping the previous notation, if the leading coefficient of \(b\) is a unit (e.g. if \(b\) is monic) then the quotient and the remainder in the right euclidean division exist and are unique.
The same result holds for the left euclidean division if in addition the twist map defining the skew polynomial ring is invertible.
Evaluation
The value of a given a skew polynomial \(p(x) = \sum_{i=0}^d a_i x^i\) at \(r\) is calculated using the formula:
\[p(r) = \sum_{i=0}^d a_i \sigma^i(r)\]where \(\sigma\) is the base ring automorphism. This is called the operator evaluation method.
EXAMPLES:
We illustrate some functionalities implemented in this class.
We create the skew polynomial ring:
sage: R.<t> = ZZ[] 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 Integer Ring twisted by t > t + 1
and some elements in it:
sage: a = t + x + 1; a x + t + 1 sage: b = S([t^2,t+1,1]); b x^2 + (t + 1)*x + t^2 sage: c = S.random_element(degree=3,monic=True); c x^3 + (2*t  1)*x
Ring operations are supported:
sage: a + b x^2 + (t + 2)*x + t^2 + t + 1 sage: a  b x^2  t*x  t^2 + t + 1 sage: a * b x^3 + (2*t + 3)*x^2 + (2*t^2 + 4*t + 2)*x + t^3 + t^2 sage: b * a x^3 + (2*t + 4)*x^2 + (2*t^2 + 3*t + 2)*x + t^3 + t^2 sage: a * b == b * a False sage: b^2 x^4 + (2*t + 4)*x^3 + (3*t^2 + 7*t + 6)*x^2 + (2*t^3 + 4*t^2 + 3*t + 1)*x + t^4 sage: b^2 == b*b True
Sage also implements arithmetic over skew polynomial rings. You will find below a short panorama:
sage: q,r = c.right_quo_rem(b) sage: q x  t  2 sage: r 3*t*x + t^3 + 2*t^2 sage: c == q*b + r True
The operators
//
and%
give respectively the quotient and the remainder of the right euclidean division:sage: q == c // b True sage: r == c % b True
Left euclidean division won’t work over our current \(S\) because Sage can’t invert the twist map:
sage: q,r = c.left_quo_rem(b) Traceback (most recent call last): ... NotImplementedError: inversion of the twist map Ring endomorphism of Univariate Polynomial Ring in t over Integer Ring Defn: t > t + 1
Here we can see the effect of the operator evaluation compared to the usual polynomial evaluation:
sage: a = x^2 sage: a(t) t + 2
Here is a working example over a finite field:
sage: k.<t> = GF(5^3) sage: Frob = k.frobenius_endomorphism() sage: S.<x> = k['x',Frob] sage: a = x^4 + (4*t + 1)*x^3 + (t^2 + 3*t + 3)*x^2 + (3*t^2 + 2*t + 2)*x + (3*t^2 + 3*t + 1) sage: b = (2*t^2 + 3)*x^2 + (3*t^2 + 1)*x + 4*t + 2 sage: q,r = a.left_quo_rem(b) sage: q (4*t^2 + t + 1)*x^2 + (2*t^2 + 2*t + 2)*x + 2*t^2 + 4*t + 3 sage: r (t + 2)*x + 3*t^2 + 2*t + 4 sage: a == b*q + r True
Once we have euclidean divisions, we have for free gcd and lcm (at least if the base ring is a field):
sage: a = (x + t) * (x + t^2)^2 sage: b = (x + t) * (t*x + t + 1) * (x + t^2) sage: a.right_gcd(b) x + t^2 sage: a.left_gcd(b) x + t
The left lcm has the following meaning: given skew polynomials \(a\) and \(b\), their left lcm is the least degree polynomial \(c = ua = vb\) for some skew polynomials \(u, v\). Such a \(c\) always exist if the base ring is a field:
sage: c = a.left_lcm(b); c x^5 + (4*t^2 + t + 3)*x^4 + (3*t^2 + 4*t)*x^3 + 2*t^2*x^2 + (2*t^2 + t)*x + 4*t^2 + 4 sage: c.is_right_divisible_by(a) True sage: c.is_right_divisible_by(b) True
The right lcm is defined similarly as the least degree polynomial \(c = au = bv\) for some \(u,v\):
sage: d = a.right_lcm(b); d x^5 + (t^2 + 1)*x^4 + (3*t^2 + 3*t + 3)*x^3 + (3*t^2 + t + 2)*x^2 + (4*t^2 + 3*t)*x + 4*t + 4 sage: d.is_left_divisible_by(a) True sage: d.is_left_divisible_by(b) True
See also

base_ring
()¶ Return the base ring of
self
.EXAMPLES:
sage: R.<t> = ZZ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: a = S.random_element() sage: a.base_ring() Univariate Polynomial Ring in t over Integer Ring sage: a.base_ring() is R True

change_variable_name
(var)¶ Change the name of the variable of
self
.This will create the skew polynomial ring with the new name but same base ring and twist map. The returned skew polynomial will be an element of that skew polynomial ring.
INPUT:
var
– the name of the new variable
EXAMPLES:
sage: R.<t> = ZZ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x', sigma] sage: a = x^3 + (2*t + 1)*x + t^2 + 3*t + 5 sage: b = a.change_variable_name('y'); b y^3 + (2*t + 1)*y + t^2 + 3*t + 5
Note that a new parent is created at the same time:
sage: b.parent() Skew Polynomial Ring in y over Univariate Polynomial Ring in t over Integer Ring twisted by t > t + 1

coefficients
(sparse=True)¶ Return the coefficients of the monomials appearing in
self
.If
sparse=True
(the default), return only the nonzero coefficients. Otherwise, return the same value asself.list()
.Note
This should be overridden in subclasses.
EXAMPLES:
sage: R.<t> = QQ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: a = 1 + x^4 + (t+1)*x^2 + t^2 sage: a.coefficients() [t^2 + 1, t + 1, 1] sage: a.coefficients(sparse=False) [t^2 + 1, 0, t + 1, 0, 1]

conjugate
(n)¶ Return
self
conjugated by \(x^n\), where \(x\) is the variable ofself
.The conjugate is obtained from
self
by applying the \(n\)th iterate of the twist map to each of its coefficients.INPUT:
 \(n\) – an integer, the power of conjugation
EXAMPLES:
sage: R.<t> = QQ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: a = t*x^3 + (t^2 + 1)*x^2 + 2*t sage: b = a.conjugate(2); b (t + 2)*x^3 + (t^2 + 4*t + 5)*x^2 + 2*t + 4 sage: x^2*a == b*x^2 True
In principle, negative values for \(n\) are allowed, but Sage needs to be able to invert the twist map:
sage: b = a.conjugate(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
Here is a working example:
sage: k.<t> = GF(5^3) sage: Frob = k.frobenius_endomorphism() sage: T.<y> = k['y',Frob] sage: u = T.random_element(); u (2*t^2 + 3)*y^2 + (4*t^2 + t + 4)*y + 2*t^2 + 2 sage: v = u.conjugate(1); v (3*t^2 + t)*y^2 + (4*t^2 + 2*t + 4)*y + 3*t^2 + t + 4 sage: u*y == y*v True

constant_coefficient
()¶ Return the constant coefficient (i.e. the coefficient of term of degree \(0\)) of
self
.EXAMPLES:
sage: R.<t> = ZZ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: a = x + t^2 + 2 sage: a.constant_coefficient() t^2 + 2

degree
()¶ Return the degree of
self
.By convention, the zero skew polynomial has degree \(1\).
EXAMPLES:
sage: R.<t> = ZZ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: a = x^2 + t*x^3 + t^2*x + 1 sage: a.degree() 3 sage: S.zero().degree() 1 sage: S(5).degree() 0

exponents
()¶ Return the exponents of the monomials appearing in
self
.EXAMPLES:
sage: R.<t> = QQ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: a = 1 + x^4 + (t+1)*x^2 + t^2 sage: a.exponents() [0, 2, 4]

hamming_weight
()¶ Return the number of nonzero coefficients of
self
.This is also known as the weight, hamming weight or sparsity.
EXAMPLES:
sage: R.<t> = QQ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: a = 1 + x^4 + (t+1)*x^2 + t^2 sage: a.number_of_terms() 3
This is also an alias for
hamming_weight
:sage: a.hamming_weight() 3

is_constant
()¶ Return whether
self
is a constant polynomial.EXAMPLES:
sage: R.<t> = QQ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: R(2).is_constant() True sage: (x + 1).is_constant() False

is_left_divisible_by
(other)¶ Check if
self
is divisible byother
on the left.INPUT:
other
– a skew polynomial in the same ring asself
OUTPUT:
Return
True
orFalse
.EXAMPLES:
sage: k.<t> = GF(5^3) sage: Frob = k.frobenius_endomorphism() sage: S.<x> = k['x',Frob] sage: a = x^2 + t*x + t^2 + 3 sage: b = x^3 + (t + 1)*x^2 + 1 sage: c = a*b sage: c.is_left_divisible_by(a) True sage: c.is_left_divisible_by(b) False
Divisibility by \(0\) does not make sense:
sage: c.is_left_divisible_by(S(0)) Traceback (most recent call last): ... ZeroDivisionError: division by zero is not valid

is_monic
()¶ Return
True
if this skew polynomial is monic.The zero polynomial is by definition not monic.
EXAMPLES:
sage: R.<t> = ZZ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: a = x + t sage: a.is_monic() True sage: a = 0*x sage: a.is_monic() False sage: a = t*x^3 + x^4 + (t+1)*x^2 sage: a.is_monic() True sage: a = (t^2 + 2*t)*x^2 + x^3 + t^10*x^5 sage: a.is_monic() False

is_monomial
()¶ Return
True
ifself
is a monomial, i.e., a power of the generator.EXAMPLES:
sage: R.<t> = ZZ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: x.is_monomial() True sage: (x+1).is_monomial() False sage: (x^2).is_monomial() True sage: S(1).is_monomial() True
The coefficient must be 1:
sage: (2*x^5).is_monomial() False sage: S(t).is_monomial() False
To allow a non1 leading coefficient, use is_term():
sage: (2*x^5).is_term() True sage: S(t).is_term() True

is_nilpotent
()¶ Check if
self
is nilpotent.Given a commutative ring \(R\) and a base ring automorphism \(\sigma\) of order \(n\), an element \(f\) of \(R[X, \sigma]\) is nilpotent if and only if all coefficients of \(f^n\) are nilpotent in \(R\).
Note
The paper “Nilpotents and units in skew polynomial rings over commutative rings” by M. Rimmer and K.R. Pearson describes the method to check whether a given skew polynomial is nilpotent. That method however, requires one to know the order of the automorphism which is not available in Sage. This method is thus not yet implemented.
EXAMPLES:
sage: R.<t> = ZZ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: x.is_nilpotent() Traceback (most recent call last): ... NotImplementedError

is_one
()¶ Test whether this polynomial is \(1\).
EXAMPLES:
sage: R.<t> = QQ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: R(1).is_one() True sage: (x + 3).is_one() False

is_right_divisible_by
(other)¶ Check if
self
is divisible byother
on the right.INPUT:
other
– a skew polynomial in the same ring asself
OUTPUT:
Return
True
orFalse
.EXAMPLES:
sage: k.<t> = GF(5^3) sage: Frob = k.frobenius_endomorphism() sage: S.<x> = k['x',Frob] sage: a = x^2 + t*x + t^2 + 3 sage: b = x^3 + (t + 1)*x^2 + 1 sage: c = a*b sage: c.is_right_divisible_by(a) False sage: c.is_right_divisible_by(b) True
Divisibility by \(0\) does not make sense:
sage: c.is_right_divisible_by(S(0)) Traceback (most recent call last): ... ZeroDivisionError: division by zero is not valid
This function does not work if the leading coefficient of the divisor is not a unit:
sage: R.<t> = QQ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: a = x^2 + 2*x + t sage: b = (t+1)*x + t^2 sage: c = a*b sage: c.is_right_divisible_by(b) Traceback (most recent call last): ... NotImplementedError: the leading coefficient of the divisor is not invertible

is_term
()¶ Return
True
ifself
is an element of the base ring times a power of the generator.EXAMPLES:
sage: R.<t> = ZZ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: x.is_term() True sage: R(1).is_term() True sage: (3*x^5).is_term() True sage: (1+3*x^5).is_term() False
If you want to test that
self
also has leading coefficient 1, useis_monomial()
instead:sage: (3*x^5).is_monomial() False

is_unit
()¶ Return
True
if this skew polynomial is a unit.When the base ring \(R\) is an integral domain, then a skew polynomial \(f\) is a unit if and only if degree of \(f\) is \(0\) and \(f\) is then a unit in \(R\).
Note
The case when \(R\) is not an integral domain is not yet implemented.
EXAMPLES:
sage: R.<t> = ZZ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: a = x + (t+1)*x^5 + t^2*x^3  x^5 sage: a.is_unit() False

is_zero
()¶ Return
True
ifself
is the zero polynomial.EXAMPLES:
sage: R.<t> = ZZ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: a = x + 1 sage: a.is_zero() False sage: b = S.zero() sage: b.is_zero() True

leading_coefficient
()¶ Return the coefficient of the highestdegree monomial of
self
.EXAMPLES:
sage: R.<t> = ZZ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: a = (t+1)*x^5 + t^2*x^3 + x sage: a.leading_coefficient() t + 1

left_divides
(other)¶ Check if
self
dividesother
on the left.INPUT:
other
– a skew polynomial in the same ring asself
OUTPUT:
Return
True
orFalse
.EXAMPLES:
sage: k.<t> = GF(5^3) sage: Frob = k.frobenius_endomorphism() sage: S.<x> = k['x',Frob] sage: a = x^2 + t*x + t^2 + 3 sage: b = x^3 + (t + 1)*x^2 + 1 sage: c = a*b sage: a.left_divides(c) True sage: b.left_divides(c) False
Divisibility by \(0\) does not make sense:
sage: S(0).left_divides(c) Traceback (most recent call last): ... ZeroDivisionError: division by zero is not valid

left_gcd
(other, monic=True)¶ Return the left gcd of
self
andother
.INPUT:
other
– a skew polynomial in the same ring asself
monic
– boolean (default:True
). Return whether the left gcd should be normalized to be monic.
OUTPUT:
The left gcd of
self
andother
, that is a skew polynomial \(g\) with the following property: any skew polynomial is divisible on the left by \(g\) iff it is divisible on the left by bothself
andother
. If monic isTrue
, \(g\) is in addition monic. (With this extra condition, it is uniquely determined.)Note
Works only if two following conditions are fulfilled (otherwise left gcd do not exist in general): 1) the base ring is a field and 2) the twist map on this field is bijective.
EXAMPLES:
sage: k.<t> = GF(5^3) sage: Frob = k.frobenius_endomorphism() sage: S.<x> = k['x',Frob] sage: a = (x + t) * (x^2 + t*x + 1) sage: b = 2 * (x + t) * (x^3 + (t+1)*x^2 + t^2) sage: a.left_gcd(b) x + t
Specifying
monic=False
, we can get a nonmonic gcd:sage: a.left_gcd(b,monic=False) 2*t*x + 4*t + 2
The base ring needs to be a field:
sage: R.<t> = QQ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: a = (x + t) * (x^2 + t*x + 1) sage: b = 2 * (x + t) * (x^3 + (t+1)*x^2 + t^2) sage: a.left_gcd(b) Traceback (most recent call last): ... TypeError: the base ring must be a field
And the twist map needs to be bijective:
sage: FR = R.fraction_field() sage: f = FR.hom([FR(t)^2]) sage: S.<x> = FR['x',f] sage: a = (x + t) * (x^2 + t*x + 1) sage: b = 2 * (x + t) * (x^3 + (t+1)*x^2 + t^2) sage: a.left_gcd(b) Traceback (most recent call last): ... NotImplementedError: inversion of the twist map Ring endomorphism of Fraction Field of Univariate Polynomial Ring in t over Rational Field Defn: t > t^2

left_lcm
(other, monic=True)¶ Return the left lcm of
self
andother
.INPUT:
other
– a skew polynomial in the same ring asself
monic
– boolean (default:True
). Return whether the left lcm should be normalized to be monic.
OUTPUT:
The left lcm of
self
andother
, that is a skew polynomial \(g\) with the following property: any skew polynomial divides \(g\) on the right iff it divides bothself
andother
on the right. If monic isTrue
, \(g\) is in addition monic. (With this extra condition, it is uniquely determined.)Note
Works only if the base ring is a field (otherwise left lcm do not exist in general).
EXAMPLES:
sage: k.<t> = GF(5^3) sage: Frob = k.frobenius_endomorphism() sage: S.<x> = k['x',Frob] sage: a = (x + t^2) * (x + t) sage: b = 2 * (x^2 + t + 1) * (x * t) sage: c = a.left_lcm(b); c x^5 + (2*t^2 + t + 4)*x^4 + (3*t^2 + 4)*x^3 + (3*t^2 + 3*t + 2)*x^2 + (t^2 + t + 2)*x sage: c.is_right_divisible_by(a) True sage: c.is_right_divisible_by(b) True sage: a.degree() + b.degree() == c.degree() + a.right_gcd(b).degree() True
Specifying
monic=False
, we can get a nonmonic gcd:sage: a.left_lcm(b,monic=False) (t^2 + t)*x^5 + (4*t^2 + 4*t + 1)*x^4 + (t + 1)*x^3 + (t^2 + 2)*x^2 + (3*t + 4)*x
The base ring needs to be a field:
sage: R.<t> = QQ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: a = (x + t^2) * (x + t) sage: b = 2 * (x^2 + t + 1) * (x * t) sage: a.left_lcm(b) Traceback (most recent call last): ... TypeError: the base ring must be a field

left_mod
(other)¶ Return the remainder of left division of
self
byother
.EXAMPLES:
sage: k.<t> = GF(5^3) sage: Frob = k.frobenius_endomorphism() sage: S.<x> = k['x',Frob] sage: a = 1 + t*x^2 sage: b = x + 1 sage: a.left_mod(b) 2*t^2 + 4*t

left_monic
()¶ Return the unique monic skew polynomial \(m\) which divides
self
on the left and has the same degree.Given a skew polynomial \(p\) of degree \(n\), its left monic is given by \(m = p \sigma^{n}(1/k)\), where \(k\) is the leading coefficient of \(p\), i.e. by the appropriate scalar multiplication on the right.
EXAMPLES:
sage: k.<t> = GF(5^3) sage: Frob = k.frobenius_endomorphism() sage: S.<x> = k['x',Frob] sage: a = (3*t^2 + 3*t + 2)*x^3 + (2*t^2 + 3)*x^2 + (4*t^2 + t + 4)*x + 2*t^2 + 2 sage: b = a.left_monic(); b x^3 + (4*t^2 + 3*t)*x^2 + (4*t + 2)*x + 2*t^2 + 4*t + 3
Check list:
sage: b.degree() == a.degree() True sage: b.is_left_divisible_by(a) True sage: twist = S.twist_map(a.degree()) sage: a == b * twist(a.leading_coefficient()) True
Note that \(b\) does not divide \(a\) on the right:
sage: a.is_right_divisible_by(b) False
This function does not work if the leading coefficient is not a unit:
sage: R.<t> = QQ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: a = t*x sage: a.left_monic() Traceback (most recent call last): ... NotImplementedError: the leading coefficient is not a unit

left_xgcd
(other, monic=True)¶ Return the left gcd of
self
andother
along with the coefficients for the linear combination.If \(a\) is
self
and \(b\) isother
, then there are skew polynomials \(u\) and \(v\) such that \(g = a u + b v\), where \(g\) is the left gcd of \(a\) and \(b\). This method returns \((g, u, v)\).INPUT:
other
– a skew polynomial in the same ring asself
monic
– boolean (default:True
). Return whether the left gcd should be normalized to be monic.
OUTPUT:
The left gcd of
self
andother
, that is a skew polynomial \(g\) with the following property: any skew polynomial is divisible on the left by \(g\) iff it is divisible on the left by bothself
andother
. If monic isTrue
, \(g\) is in addition monic. (With this extra condition, it is uniquely determined.)Two skew polynomials \(u\) and \(v\) such that:
\[g = a * u + b * v,\]where \(s\) is
self
and \(b\) isother
.
Note
Works only if following two conditions are fulfilled (otherwise left gcd do not exist in general): 1) the base ring is a field and 2) the twist map on this field is bijective.
EXAMPLES:
sage: k.<t> = GF(5^3) sage: Frob = k.frobenius_endomorphism() sage: S.<x> = k['x',Frob] sage: a = (x + t) * (x^2 + t*x + 1) sage: b = 2 * (x + t) * (x^3 + (t+1)*x^2 + t^2) sage: g,u,v = a.left_xgcd(b); g x + t sage: a*u + b*v == g True
Specifying
monic=False
, we can get a nonmonic gcd:sage: g,u,v = a.left_xgcd(b, monic=False); g 2*t*x + 4*t + 2 sage: a*u + b*v == g True
The base ring must be a field:
sage: R.<t> = QQ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: a = (x + t) * (x^2 + t*x + 1) sage: b = 2 * (x + t) * (x^3 + (t+1)*x^2 + t^2) sage: a.left_xgcd(b) Traceback (most recent call last): ... TypeError: the base ring must be a field
And the twist map must be bijective:
sage: FR = R.fraction_field() sage: f = FR.hom([FR(t)^2]) sage: S.<x> = FR['x',f] sage: a = (x + t) * (x^2 + t*x + 1) sage: b = 2 * (x + t) * (x^3 + (t+1)*x^2 + t^2) sage: a.left_xgcd(b) Traceback (most recent call last): ... NotImplementedError: inversion of the twist map Ring endomorphism of Fraction Field of Univariate Polynomial Ring in t over Rational Field Defn: t > t^2

multi_point_evaluation
(eval_pts)¶ Evaluate
self
at list of evaluation points.INPUT:
eval_pts
– list of points at whichself
is to be evaluated
OUTPUT:
List of values of
self
at theeval_pts
.Todo
This method currently trivially calls the evaluation function repeatedly. If fast skew polynomial multiplication is available, an asymptotically faster method is possible using standard divide and conquer techniques and
sage.rings.polynomial.skew_polynomial_ring.SkewPolynomialRing_general.minimal_vanishing_polynomial()
.EXAMPLES:
sage: k.<t> = GF(5^3) sage: Frob = k.frobenius_endomorphism() sage: S.<x> = k['x',Frob] sage: a = x + t sage: eval_pts = [1, t, t^2] sage: c = a.multi_point_evaluation(eval_pts); c [t + 1, 3*t^2 + 4*t + 4, 4*t] sage: c == [ a(e) for e in eval_pts ] True

number_of_terms
()¶ Return the number of nonzero coefficients of
self
.This is also known as the weight, hamming weight or sparsity.
EXAMPLES:
sage: R.<t> = QQ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: a = 1 + x^4 + (t+1)*x^2 + t^2 sage: a.number_of_terms() 3
This is also an alias for
hamming_weight
:sage: a.hamming_weight() 3

operator_eval
(eval_pt)¶ Evaluate
self
ateval_pt
by the operator evaluation method.INPUT:
eval_pt
– element of the base ring ofself
OUTPUT:
The value of the polynomial at the point specified by the argument.
EXAMPLES:
sage: k.<t> = GF(5^3) sage: Frob = k.frobenius_endomorphism() sage: T.<x> = k['x',Frob] sage: a = 3*t^2*x^2 + (t + 1)*x + 2 sage: a(t) #indirect test 2*t^2 + 2*t + 3 sage: a.operator_eval(t) 2*t^2 + 2*t + 3
Evaluation points outside the base ring is usually not possible due to the twist map:
sage: R.<t> = QQ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: a = t*x + 1 sage: a.operator_eval(1/t) Traceback (most recent call last): ... TypeError: 1/t fails to convert into the map's domain Univariate Polynomial Ring in t over Rational Field, but a `pushforward` method is not properly implemented

padded_list
(n=None)¶ Return list of coefficients of
self
up to (but not including) degree \(n\).Includes \(0`s in the list on the right so that the list always has length exactly `n\).
INPUT:
n
– (default:None
); if given, an integer that is at least \(0\)
EXAMPLES:
sage: R.<t> = QQ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: a = 1 + t*x^3 + t^2*x^5 sage: a.padded_list() [1, 0, 0, t, 0, t^2] sage: a.padded_list(10) [1, 0, 0, t, 0, t^2, 0, 0, 0, 0] sage: len(a.padded_list(10)) 10 sage: a.padded_list(3) [1, 0, 0] sage: a.padded_list(0) [] sage: a.padded_list(1) Traceback (most recent call last): ... ValueError: n must be at least 0

prec
()¶ Return the precision of
self
.This is always infinity, since polynomials are of infinite precision by definition (there is no bigoh).
EXAMPLES:
sage: R.<t> = QQ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: x.prec() +Infinity

right_divides
(other)¶ Check if
self
dividesother
on the right.INPUT:
other
– a skew polynomial in the same ring asself
OUTPUT:
Return
True
orFalse
.EXAMPLES:
sage: k.<t> = GF(5^3) sage: Frob = k.frobenius_endomorphism() sage: S.<x> = k['x',Frob] sage: a = x^2 + t*x + t^2 + 3 sage: b = x^3 + (t + 1)*x^2 + 1 sage: c = a*b sage: a.right_divides(c) False sage: b.right_divides(c) True
Divisibility by \(0\) does not make sense:
sage: S(0).right_divides(c) Traceback (most recent call last): ... ZeroDivisionError: division by zero is not valid
This function does not work if the leading coefficient of the divisor is not a unit:
sage: R.<t> = QQ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: a = x^2 + 2*x + t sage: b = (t+1)*x + t^2 sage: c = a*b sage: b.right_divides(c) Traceback (most recent call last): ... NotImplementedError: the leading coefficient of the divisor is not invertible

right_gcd
(other, monic=True)¶ Return the right gcd of
self
andother
.INPUT:
other
– a skew polynomial in the same ring asself
monic
– boolean (default:True
). Return whether the right gcd should be normalized to be monic.
OUTPUT:
The right gcd of
self
andother
, that is a skew polynomial \(g\) with the following property: any skew polynomial is divisible on the right by \(g\) iff it is divisible on the right by bothself
andother
. If monic isTrue
, \(g\) is in addition monic. (With this extra condition, it is uniquely determined.)Note
Works only if the base ring is a field (otherwise right gcd do not exist in general).
EXAMPLES:
sage: k.<t> = GF(5^3) sage: Frob = k.frobenius_endomorphism() sage: S.<x> = k['x',Frob] sage: a = (x^2 + t*x + 1) * (x + t) sage: b = 2 * (x^3 + (t+1)*x^2 + t^2) * (x + t) sage: a.right_gcd(b) x + t
Specifying
monic=False
, we can get a nonmonic gcd:sage: a.right_gcd(b,monic=False) (4*t^2 + 4*t + 1)*x + 4*t^2 + 4*t + 3
The base ring need to be a field:
sage: R.<t> = QQ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: a = (x^2 + t*x + 1) * (x + t) sage: b = 2 * (x^3 + (t+1)*x^2 + t^2) * (x + t) sage: a.right_gcd(b) Traceback (most recent call last): ... TypeError: the base ring must be a field

right_lcm
(other, monic=True)¶ Return the right lcm of
self
andother
.INPUT:
other
– a skew polynomial in the same ring asself
monic
– boolean (default:True
). Return whether the right lcm should be normalized to be monic.
OUTPUT:
The right lcm of
self
andother
, that is a skew polynomial \(g\) with the following property: any skew polynomial divides \(g\) on the left iff it divides bothself
andother
on the left. If monic isTrue
, \(g\) is in addition monic. (With this extra condition, it is uniquely determined.)Note
Works only if two following conditions are fulfilled (otherwise right lcm do not exist in general): 1) the base ring is a field and 2) the twist map on this field is bijective.
EXAMPLES:
sage: k.<t> = GF(5^3) sage: Frob = k.frobenius_endomorphism() sage: S.<x> = k['x',Frob] sage: a = (x + t) * (x + t^2) sage: b = 2 * (x + t) * (x^2 + t + 1) sage: c = a.right_lcm(b); c x^4 + (2*t^2 + t + 2)*x^3 + (3*t^2 + 4*t + 1)*x^2 + (3*t^2 + 4*t + 1)*x + t^2 + 4 sage: c.is_left_divisible_by(a) True sage: c.is_left_divisible_by(b) True sage: a.degree() + b.degree() == c.degree() + a.left_gcd(b).degree() True
Specifying
monic=False
, we can get a nonmonic gcd:sage: a.right_lcm(b,monic=False) 2*t*x^4 + (3*t + 1)*x^3 + (4*t^2 + 4*t + 3)*x^2 + (3*t^2 + 4*t + 2)*x + 3*t^2 + 2*t + 3
The base ring needs to be a field:
sage: R.<t> = QQ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: a = (x + t) * (x + t^2) sage: b = 2 * (x + t) * (x^2 + t + 1) sage: a.right_lcm(b) Traceback (most recent call last): ... TypeError: the base ring must be a field
And the twist map needs to be bijective:
sage: FR = R.fraction_field() sage: f = FR.hom([FR(t)^2]) sage: S.<x> = FR['x',f] sage: a = (x + t) * (x + t^2) sage: b = 2 * (x + t) * (x^2 + t + 1) sage: a.right_lcm(b) Traceback (most recent call last): ... NotImplementedError: inversion of the twist map Ring endomorphism of Fraction Field of Univariate Polynomial Ring in t over Rational Field Defn: t > t^2

right_mod
(other)¶ Return the remainder of right division of
self
byother
.EXAMPLES:
sage: R.<t> = QQ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: a = 1 + t*x^2 sage: b = x + 1 sage: a % b t + 1 sage: (x^3 + x  1).right_mod(x^2  1) 2*x  1

right_monic
()¶ Return the unique monic skew polynomial \(m\) which divides
self
on the right and has the same degree.Given a skew polynomial \(p\) of degree \(n\), its left monic is given by \(m = (1/k) * p\), where \(k\) is the leading coefficient of \(p\), i.e. by the appropriate scalar multiplication on the left.
EXAMPLES:
sage: k.<t> = GF(5^3) sage: Frob = k.frobenius_endomorphism() sage: S.<x> = k['x',Frob] sage: a = (3*t^2 + 3*t + 2)*x^3 + (2*t^2 + 3)*x^2 + (4*t^2 + t + 4)*x + 2*t^2 + 2 sage: b = a.right_monic(); b x^3 + (2*t^2 + 3*t + 4)*x^2 + (3*t^2 + 4*t + 1)*x + 2*t^2 + 4*t + 3
Check list:
sage: b.degree() == a.degree() True sage: b.is_right_divisible_by(a) True sage: a == a.leading_coefficient() * b True
Note that \(b\) does not divide \(a\) on the right:
sage: a.is_left_divisible_by(b) False
This function does not work if the leading coefficient is not a unit:
sage: R.<t> = QQ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: a = t*x sage: a.right_monic() Traceback (most recent call last): ... NotImplementedError: the leading coefficient is not a unit

right_xgcd
(other, monic=True)¶ Return the right gcd of
self
andother
along with the coefficients for the linear combination.If \(a\) is
self
and \(b\) isother
, then there are skew polynomials \(u\) and \(v\) such that \(g = u a + v b\), where \(g\) is the right gcd of \(a\) and \(b\). This method returns \((g, u, v)\).INPUT:
other
– a skew polynomial in the same ring asself
monic
– boolean (default:True
). Return whether the right gcd should be normalized to be monic.
OUTPUT:
The right gcd of
self
andother
, that is a skew polynomial \(g\) with the following property: any skew polynomial is divisible on the right by \(g\) iff it is divisible on the right by bothself
andother
. If monic isTrue
, \(g\) is in addition monic. (With this extra condition, it is uniquely determined.)Two skew polynomials \(u\) and \(v\) such that:
\[g = u * a + v * b\]where \(a\) is
self
and \(b\) isother
.
Note
Works only if the base ring is a field (otherwise right gcd do not exist in general).
EXAMPLES:
sage: k.<t> = GF(5^3) sage: Frob = k.frobenius_endomorphism() sage: S.<x> = k['x',Frob] sage: a = (x^2 + t*x + 1) * (x + t) sage: b = 2 * (x^3 + (t+1)*x^2 + t^2) * (x + t) sage: g,u,v = a.right_xgcd(b); g x + t sage: u*a + v*b == g True
Specifying
monic=False
, we can get a nonmonic gcd:sage: g,u,v = a.right_xgcd(b,monic=False); g (4*t^2 + 4*t + 1)*x + 4*t^2 + 4*t + 3 sage: u*a + v*b == g True
The base ring must be a field:
sage: R.<t> = QQ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: a = (x^2 + t*x + 1) * (x + t) sage: b = 2 * (x^3 + (t+1)*x^2 + t^2) * (x + t) sage: a.right_xgcd(b) Traceback (most recent call last): ... TypeError: the base ring must be a field

shift
(n)¶ Return
self
multiplied on the right by the power \(x^n\).If \(n\) is negative, terms below \(x^n\) will be discarded.
EXAMPLES:
sage: R.<t> = QQ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: a = x^5 + t^4*x^4 + t^2*x^2 + t^10 sage: a.shift(0) x^5 + t^4*x^4 + t^2*x^2 + t^10 sage: a.shift(1) x^4 + t^4*x^3 + t^2*x sage: a.shift(5) 1 sage: a.shift(2) x^7 + t^4*x^6 + t^2*x^4 + t^10*x^2
One can also use the infix shift operator:
sage: a >> 2 x^3 + t^4*x^2 + t^2 sage: a << 2 x^7 + t^4*x^6 + t^2*x^4 + t^10*x^2

square
()¶ Return the square of
self
.EXAMPLES:
sage: R.<t> = QQ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: a = x + t; a x + t sage: a.square() x^2 + (2*t + 1)*x + t^2 sage: a.square() == a*a True

variable_name
()¶ Return the string name of the variable used in
self
.EXAMPLES:
sage: R.<t> = QQ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: a = x + t sage: a.variable_name() 'x'

class
sage.rings.polynomial.skew_polynomial_element.
SkewPolynomialBaseringInjection
¶ Bases:
sage.categories.morphism.Morphism
Representation of the canonical homomorphism from a ring \(R\) into a skew polynomial ring over \(R\).
This class is necessary for automatic coercion from the base ring to the skew polynomial ring.
See also
EXAMPLES:
sage: R.<t> = QQ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: S.coerce_map_from(S.base_ring()) #indirect doctest Skew Polynomial base injection morphism: From: Univariate Polynomial Ring in t over Rational Field To: Skew Polynomial Ring in x over Univariate Polynomial Ring in t over Rational Field twisted by t > t + 1

an_element
()¶ Return an element of the codomain of the ring homomorphism.
EXAMPLES:
sage: from sage.rings.polynomial.skew_polynomial_element import SkewPolynomialBaseringInjection sage: k.<t> = GF(5^3) sage: Frob = k.frobenius_endomorphism() sage: S.<x> = k['x',Frob] sage: m = SkewPolynomialBaseringInjection(k, k['x', Frob]) sage: m.an_element() x

section
()¶ Return the canonical homomorphism from the constants of a skew polynomial ring to the base ring according to
self
.


class
sage.rings.polynomial.skew_polynomial_element.
SkewPolynomial_generic_dense
¶ Bases:
sage.rings.polynomial.skew_polynomial_element.SkewPolynomial
Generic implementation of dense skew polynomial supporting any valid base ring and twist map.

coefficients
(sparse=True)¶ Return the coefficients of the monomials appearing in
self
.If
sparse=True
(the default), return only the nonzero coefficients. Otherwise, return the same value asself.list()
.EXAMPLES:
sage: R.<t> = QQ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: a = 1 + x^4 + (t+1)*x^2 + t^2 sage: a.coefficients() [t^2 + 1, t + 1, 1] sage: a.coefficients(sparse=False) [t^2 + 1, 0, t + 1, 0, 1]

degree
()¶ Return the degree of
self
.By convention, the zero skew polynomial has degree \(1\).
EXAMPLES:
sage: R.<t> = ZZ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: a = x^2 + t*x^3 + t^2*x + 1 sage: a.degree() 3
By convention, the degree of \(0\) is \(1\):
sage: S(0).degree() 1

dict
()¶ Return a dictionary representation of
self
.EXAMPLES:
sage: R.<t> = ZZ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: a = x^2012 + t*x^1006 + t^3 + 2*t sage: a.dict() {0: t^3 + 2*t, 1006: t, 2012: 1}

left_power_mod
(exp, modulus)¶ Return the remainder of
self**exp
in the left euclidean division bymodulus
.INPUT:
exp
– an Integermodulus
– a skew polynomial in the same ring asself
OUTPUT:
Remainder of
self**exp
in the left euclidean division bymodulus
.REMARK:
The quotient of the underlying skew polynomial ring by the principal ideal generated by
modulus
is in general not a ring.As a consequence, Sage first computes exactly
self**exp
and then reduce it modulomodulus
.EXAMPLES:
sage: k.<t> = GF(5^3) sage: Frob = k.frobenius_endomorphism() sage: S.<x> = k['x',Frob] sage: a = x + t sage: modulus = x^3 + t*x^2 + (t+3)*x  2 sage: a.left_power_mod(100,modulus) (4*t^2 + t + 1)*x^2 + (t^2 + 4*t + 1)*x + 3*t^2 + 3*t

left_quo_rem
(other)¶ Return the quotient and remainder of the left euclidean division of
self
byother
.INPUT:
other
– a skew polynomial in the same ring asself
OUTPUT:
 the quotient and the remainder of the left euclidean
division of this skew polynomial by
other
Note
This will fail if the leading coefficient of
other
is not a unit or if Sage can’t invert the twist map.EXAMPLES:
sage: k.<t> = GF(5^3) sage: Frob = k.frobenius_endomorphism() sage: S.<x> = k['x',Frob] sage: a = (3*t^2 + 3*t + 2)*x^3 + (2*t^2 + 3)*x^2 + (4*t^2 + t + 4)*x + 2*t^2 + 2 sage: b = (3*t^2 + 4*t + 2)*x^2 + (2*t^2 + 4*t + 3)*x + 2*t^2 + t + 1 sage: q,r = a.left_quo_rem(b) sage: a == b*q + r True
In the following example, Sage does not know the inverse of the twist map:
sage: R.<t> = ZZ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: a = (2*t^2  t + 1)*x^3 + (t^2 + t)*x^2 + (12*t  2)*x  t^2  95*t + 1 sage: b = x^2 + (5*t  6)*x  4*t^2 + 4*t  1 sage: a.left_quo_rem(b) Traceback (most recent call last): ... NotImplementedError: inversion of the twist map Ring endomorphism of Univariate Polynomial Ring in t over Integer Ring Defn: t > t + 1

list
(copy=True)¶ Return a list of the coefficients of
self
.EXAMPLES:
sage: R.<t> = QQ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: a = 1 + x^4 + (t+1)*x^2 + t^2 sage: l = a.list(); l [t^2 + 1, 0, t + 1, 0, 1]
Note that \(l\) is a list, it is mutable, and each call to the list method returns a new list:
sage: type(l) <... 'list'> sage: l[0] = 5 sage: a.list() [t^2 + 1, 0, t + 1, 0, 1]

right_power_mod
(exp, modulus)¶ Return the remainder of
self**exp
in the right euclidean division bymodulus
.INPUT:
exp
– an Integermodulus
– a skew polynomial in the same ring asself
OUTPUT:
Remainder of
self**exp
in the right euclidean division bymodulus
.REMARK:
The quotient of the underlying skew polynomial ring by the principal ideal generated by
modulus
is in general not a ring.As a consequence, Sage first computes exactly
self**exp
and then reduce it modulomodulus
.EXAMPLES:
sage: k.<t> = GF(5^3) sage: Frob = k.frobenius_endomorphism() sage: S.<x> = k['x',Frob] sage: a = x + t sage: b = a^10 # short form for ``a._pow_(10)`` sage: b == a*a*a*a*a*a*a*a*a*a True sage: modulus = x^3 + t*x^2 + (t+3)*x  2 sage: br = a.right_power_mod(10,modulus); br (t^2 + t)*x^2 + (3*t^2 + 1)*x + t^2 + t sage: rq, rr = b.right_quo_rem(modulus) sage: br == rr True sage: a.right_power_mod(100,modulus) (2*t^2 + 3)*x^2 + (t^2 + 4*t + 2)*x + t^2 + 2*t + 1

right_quo_rem
(other)¶ Return the quotient and remainder of the right euclidean division of
self
byother
.INPUT:
other
– a skew polynomial in the same ring asself
OUTPUT:
 the quotient and the remainder of the left euclidean
division of this skew polynomial by
other
Note
This will fail if the leading coefficient of the divisor is not a unit.
EXAMPLES:
sage: R.<t> = ZZ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: a = S.random_element(degree=4); a (t  95)*x^4 + x^3 + (2*t  1)*x sage: b = S.random_element(monic=True); b x^2 + (12*t  2)*x sage: q,r = a.right_quo_rem(b) sage: a == q*b + r True
The leading coefficient of the divisor need to be invertible:
sage: c = S.random_element(); c (t  1)*x^2 + t^2*x sage: a.right_quo_rem(c) Traceback (most recent call last): ... NotImplementedError: the leading coefficient of the divisor is not invertible

truncate
(n)¶ Return the polynomial resulting from discarding all monomials of degree at least \(n\).
EXAMPLES:
sage: R.<t> = ZZ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: a = t*x^3 + x^4 + (t+1)*x^2 sage: a.truncate(4) t*x^3 + (t + 1)*x^2 sage: a.truncate(3) (t + 1)*x^2

valuation
()¶ Return the minimal degree of a nonzero monomial of
self
.By convention, the zero skew polynomial has valuation \(+\infty\).
EXAMPLES:
sage: R.<t> = ZZ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: a = x^2 + t*x^3 + t^2*x sage: a.valuation() 1
By convention, the valuation of \(0\) is \(+\infty\):
sage: S(0).valuation() +Infinity
