Univariate Ore Polynomials¶
This module provides the
OrePolynomial
,
which constructs a single univariate Ore polynomial over a commutative
base equipped with an endomorphism and/or a derivation.
It provides generic implementation of standard arithmetical operations
on Ore polynomials as addition, multiplication, gcd, lcm, etc.
The generic implementation of dense Ore polynomials is
OrePolynomial_generic_dense
.
The classes
ConstantOrePolynomialSection
and OrePolynomialBaseringInjection
handle conversion from a Ore polynomial ring to its base ring and vice versa.
AUTHORS:
Xavier Caruso (2020-05)
- class sage.rings.polynomial.ore_polynomial_element.ConstantOrePolynomialSection¶
Bases:
sage.categories.map.Map
Representation of the canonical homomorphism from the constants of a Ore polynomial ring to the base ring.
This class is necessary for automatic coercion from zero-degree Ore polynomial ring into the base ring.
EXAMPLES:
sage: from sage.rings.polynomial.ore_polynomial_element import ConstantOrePolynomialSection sage: R.<t> = QQ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: m = ConstantOrePolynomialSection(S, R); m Generic map: From: Ore 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.ore_polynomial_element.OrePolynomial¶
Bases:
sage.structure.element.AlgebraElement
Abstract base class for Ore polynomials.
This class must be inherited from and have key methods overridden.
Definition
Let \(R\) be a commutative ring equipped with an automorphism \(\sigma\) and a \(\sigma\)-derivation \(\partial\).
A Ore 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 Ore polynomials is defined by the usual addition operation and the modified multiplication is defined by the rule \(X a = \sigma(a) X + \partial(a)\) for all \(a\) in \(R\). Ore polynomials are thus non-commutative and the degree of a product is equal to the sum of the degrees of the factors.
Let \(a\) and \(b\) be two Ore 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 twisting morphism defining the Ore polynomial ring is invertible.
EXAMPLES:
We illustrate some functionalities implemented in this class.
We create the Ore polynomial ring (here the derivation is zero):
sage: R.<t> = ZZ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma]; S Ore 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 Ore 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
Here we can see the effect of the operator evaluation compared to the usual polynomial evaluation:
sage: a = x^2 sage: a(t) doctest:...: FutureWarning: This class/method/function is marked as experimental. It, its functionality or its interface might change without a formal deprecation. See http://trac.sagemath.org/13215 for details. t + 2
Here is another 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 Ore polynomials \(a\) and \(b\), their left lcm is the least degree polynomial \(c = ua = vb\) for some Ore 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
- 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 Ore polynomial ring with the new name but same base ring, twisting morphism and twisting derivation. The returned Ore polynomial will be an element of that Ore 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() Ore 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 non-zero 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]
- 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 Ore 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 non-zero 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 Ore 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 Ore 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 non-1 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.Note
The paper “Nilpotents and units in skew polynomial rings over commutative rings” by M. Rimmer and K.R. Pearson describes a 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 Ore 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 Ore polynomial is a unit.When the base ring \(R\) is an integral domain, then a Ore 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 highest-degree 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
By convention, the leading coefficient to the zero polynomial is zero:
sage: S(0).leading_coefficient() 0
- left_divides(other)¶
Check if
self
dividesother
on the left.INPUT:
other
– a Ore 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 Ore 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 Ore polynomial \(g\) with the following property: any Ore 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 following two conditions are fulfilled (otherwise left gcd do not exist in general): 1) the base ring is a field and 2) the twisting morphism 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 twisting morphism 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 twisting morphism 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 Ore 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 Ore polynomial \(g\) with the following property: any Ore 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 Ore polynomial \(m\) which divides this polynomial on the left and has the same degree.
Given a Ore polynomial \(P\) of degree \(n\), its left monic is given by \(P \cdot \sigma^{-n}(1/k)\), where \(k\) is the leading coefficient of \(P\) and \(\sigma\) is the twisting morphism.
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.twisting_morphism(-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: der = R.derivation() sage: S.<x> = R['x', der] sage: a = t*x sage: a.left_monic() Traceback (most recent call last): ... NotImplementedError: the leading coefficient is not a unit
- left_quo_rem(other)¶
Return the quotient and remainder of the left euclidean division of
self
byother
.INPUT:
other
– a Ore polynomial in the same ring asself
OUTPUT:
the quotient and the remainder of the left euclidean division of this Ore polynomial by
other
Note
This will fail if the leading coefficient of
other
is not a unit or if Sage can’t invert the twisting morphism.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 twisting morphism:
sage: R.<t> = QQ[] sage: K = R.fraction_field() sage: sigma = K.hom([(t+1)/(t-1)]) sage: S.<x> = K['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 twisting morphism Ring endomorphism of Fraction Field of Univariate Polynomial Ring in t over Rational Field Defn: t |--> (t + 1)/(t - 1)
- 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 Ore 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 Ore 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 Ore polynomial \(g\) with the following property: any Ore 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 Ore 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 twisting morphism 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 twisting morphism 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 twisting morphism Ring endomorphism of Fraction Field of Univariate Polynomial Ring in t over Rational Field Defn: t |--> t^2
- left_xlcm(other, monic=True)¶
Return the left lcm \(L\) of
self
andother
together with two Ore polynomials \(U\) and \(V\) such that\[U \cdot \text{self} = V \cdot \text{other} = L.\]EXAMPLES:
sage: k.<t> = GF(5^3) sage: Frob = k.frobenius_endomorphism() sage: S.<x> = k['x',Frob] sage: P = (x + t^2) * (x + t) sage: Q = 2 * (x^2 + t + 1) * (x * t) sage: L, U, V = P.left_xlcm(Q) sage: L 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: U*P == L True sage: V*Q == L True
- number_of_terms()¶
Return the number of non-zero 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
- padded_list(n=None)¶
Return list of coefficients of
self
up to (but not including) degree \(n\).Includes \(0\).
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 big-oh).
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 Ore 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 Ore 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 Ore polynomial \(g\) with the following property: any Ore 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 Ore 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 Ore polynomial \(g\) with the following property: any Ore 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 twisting morphism 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 twisting morphism 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 twisting morphism 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 Ore polynomial which divides this polynomial on the right and has the same degree.
Given a Ore polynomial \(P\) of degree \(n\), its left monic is given by \((1/k) \cdot P\), where \(k\) is the leading coefficient of \(p\).
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: der = R.derivation() sage: S.<x> = R['x', der] sage: a = t*x sage: a.right_monic() Traceback (most recent call last): ... NotImplementedError: the leading coefficient is not a unit
- right_quo_rem(other)¶
Return the quotient and remainder of the right euclidean division of
self
byother
.INPUT:
other
– a Ore polynomial in the same ring asself
OUTPUT:
the quotient and the remainder of the left euclidean division of this Ore 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
- 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 Ore 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 Ore 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 Ore polynomial \(g\) with the following property: any Ore 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 Ore 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
- right_xlcm(other, monic=True)¶
Return the right lcm \(L\) of
self
andother
together with two Ore polynomials \(U\) and \(V\) such that\[\text{self} \cdot U = \text{other} \cdot V = L.\]INPUT:
other
– a Ore polynomial in the same ring asself
monic
– a boolean (default:True
); whether the right lcm should be normalized to be monic
EXAMPLES:
sage: k.<t> = GF(5^3) sage: Frob = k.frobenius_endomorphism() sage: S.<x> = k['x',Frob] sage: P = (x + t) * (x + t^2) sage: Q = 2 * (x + t) * (x^2 + t + 1) sage: L, U, V = P.right_xlcm(Q) sage: L 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: P*U == L True sage: Q*V == L True
- 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 sage: der = R.derivation() sage: A.<d> = R['d', der] sage: (d + t).square() d^2 + 2*t*d + t^2 + 1
- 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.ore_polynomial_element.OrePolynomialBaseringInjection¶
Bases:
sage.categories.morphism.Morphism
Representation of the canonical homomorphism from a ring \(R\) into a Ore polynomial ring over \(R\).
This class is necessary for automatic coercion from the base ring to the Ore 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 Ore Polynomial base injection morphism: From: Univariate Polynomial Ring in t over Rational Field To: Ore 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.ore_polynomial_element import OrePolynomialBaseringInjection sage: k.<t> = GF(5^3) sage: Frob = k.frobenius_endomorphism() sage: S.<x> = k['x',Frob] sage: m = OrePolynomialBaseringInjection(k, k['x', Frob]) sage: m.an_element() x
- section()¶
Return the canonical homomorphism from the constants of a Ore polynomial ring to the base ring according to
self
.
- class sage.rings.polynomial.ore_polynomial_element.OrePolynomial_generic_dense¶
Bases:
sage.rings.polynomial.ore_polynomial_element.OrePolynomial
Generic implementation of dense Ore polynomial supporting any valid base ring, twisting morphism and twisting derivation.
- coefficients(sparse=True)¶
Return the coefficients of the monomials appearing in
self
.If
sparse=True
(the default), return only the non-zero 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 Ore 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}
- hilbert_shift(s, var=None)¶
Return this Ore polynomial with variable shifted by \(s\), i.e. if this Ore polynomial is \(P(x)\), return \(P(x+s)\).
INPUT:
s
– an element in the base ringvar
– a string; the variable name
EXAMPLES:
sage: R.<t> = GF(7)[] sage: der = R.derivation() sage: A.<d> = R['d', der] sage: L = d^3 + t*d^2 sage: L.hilbert_shift(t) d^3 + 4*t*d^2 + (5*t^2 + 3)*d + 2*t^3 + 4*t sage: (d+t)^3 + t*(d+t)^2 d^3 + 4*t*d^2 + (5*t^2 + 3)*d + 2*t^3 + 4*t
One can specify another variable name:
sage: L.hilbert_shift(t, var='x') x^3 + 4*t*x^2 + (5*t^2 + 3)*x + 2*t^3 + 4*t
When the twisting morphism is not trivial, the output lies in a different Ore polynomial ring:
sage: k.<a> = GF(5^3) sage: Frob = k.frobenius_endomorphism() sage: S.<x> = k['x', Frob] sage: P = x^2 + a*x + a^2 sage: Q = P.hilbert_shift(a); Q x^2 + (2*a^2 + a + 4)*x + a^2 + 3*a + 4 sage: Q.parent() Ore Polynomial Ring in x over Finite Field in a of size 5^3 twisted by a |--> a^5 and a*([a |--> a^5] - id) sage: Q.parent() is S False
This behavior ensures that the Hilbert shift by a fixed element defines an homomorphism of rings:
sage: U = S.random_element(degree=5) sage: V = S.random_element(degree=5) sage: s = k.random_element() sage: (U+V).hilbert_shift(s) == U.hilbert_shift(s) + V.hilbert_shift(s) True sage: (U*V).hilbert_shift(s) == U.hilbert_shift(s) * V.hilbert_shift(s) True
We check that shifting by an element and then by its opposite gives back the initial Ore polynomial:
sage: P = S.random_element(degree=10) sage: s = k.random_element() sage: P.hilbert_shift(s).hilbert_shift(-s) == P True
- 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]
- 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 non-zero monomial of
self
.By convention, the zero Ore 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