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 an Ore polynomial ring to its base ring and vice versa.

AUTHORS:

  • Xavier Caruso (2020-05)

class sage.rings.polynomial.ore_polynomial_element.ConstantOrePolynomialSection[source]#

Bases: Map

Representation of the canonical homomorphism from the constants of an 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

>>> from sage.all import *
>>> from sage.rings.polynomial.ore_polynomial_element import ConstantOrePolynomialSection
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> sigma = R.hom([t+Integer(1)])
>>> S = R['x',sigma]; (x,) = S._first_ngens(1)
>>> 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[source]#

Bases: 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\).

An 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 right (resp. left) 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

>>> from sage.all import *
>>> R = ZZ['t']; (t,) = R._first_ngens(1)
>>> sigma = R.hom([t+Integer(1)])
>>> S = R['x',sigma]; (x,) = S._first_ngens(1); 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)
sage: c.parent() is S
True

>>> from sage.all import *
>>> a = t + x + Integer(1); a
x + t + 1
>>> b = S([t**Integer(2),t+Integer(1),Integer(1)]); b
x^2 + (t + 1)*x + t^2
>>> c = S.random_element(degree=Integer(3),monic=True)
>>> c.parent() is S
True

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

>>> from sage.all import *
>>> a + b
x^2 + (t + 2)*x + t^2 + t + 1
>>> a - b
-x^2 - t*x - t^2 + t + 1

>>> a * b
x^3 + (2*t + 3)*x^2 + (2*t^2 + 4*t + 2)*x + t^3 + t^2
>>> b * a
x^3 + (2*t + 4)*x^2 + (2*t^2 + 3*t + 2)*x + t^3 + t^2
>>> a * b == b * a
False

>>> b**Integer(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
>>> b**Integer(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: c == q*b + r
True

>>> from sage.all import *
>>> q,r = c.right_quo_rem(b)
>>> 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

>>> from sage.all import *
>>> q == c // b
True
>>> 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 https://github.com/sagemath/sage/issues/13215 for details.
t + 2

>>> from sage.all import *
>>> a = x**Integer(2)
>>> 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 https://github.com/sagemath/sage/issues/13215 for details.
t + 2

Here is another example over a finite field:

sage: # needs sage.rings.finite_rings
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

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> k = GF(Integer(5)**Integer(3), names=('t',)); (t,) = k._first_ngens(1)
>>> Frob = k.frobenius_endomorphism()
>>> S = k['x',Frob]; (x,) = S._first_ngens(1)
>>> a = x**Integer(4) + (Integer(4)*t + Integer(1))*x**Integer(3) + (t**Integer(2) + Integer(3)*t + Integer(3))*x**Integer(2) + (Integer(3)*t**Integer(2) + Integer(2)*t + Integer(2))*x + (Integer(3)*t**Integer(2) + Integer(3)*t + Integer(1))
>>> b = (Integer(2)*t**Integer(2) + Integer(3))*x**Integer(2) + (Integer(3)*t**Integer(2) + Integer(1))*x + Integer(4)*t + Integer(2)
>>> q, r = a.left_quo_rem(b)
>>> q
(4*t^2 + t + 1)*x^2 + (2*t^2 + 2*t + 2)*x + 2*t^2 + 4*t + 3
>>> r
(t + 2)*x + 3*t^2 + 2*t + 4
>>> 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: # needs sage.rings.finite_rings
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

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> a = (x + t) * (x + t**Integer(2))**Integer(2)
>>> b = (x + t) * (t*x + t + Integer(1)) * (x + t**Integer(2))
>>> a.right_gcd(b)
x + t^2
>>> 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                                                      # needs sage.rings.finite_rings
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)                                                # needs sage.rings.finite_rings
True
sage: c.is_right_divisible_by(b)                                                # needs sage.rings.finite_rings
True

>>> from sage.all import *
>>> c = a.left_lcm(b); c                                                      # needs sage.rings.finite_rings
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
>>> c.is_right_divisible_by(a)                                                # needs sage.rings.finite_rings
True
>>> c.is_right_divisible_by(b)                                                # needs sage.rings.finite_rings
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                                                     # needs sage.rings.finite_rings
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)                                                 # needs sage.rings.finite_rings
True
sage: d.is_left_divisible_by(b)                                                 # needs sage.rings.finite_rings
True

>>> from sage.all import *
>>> d = a.right_lcm(b); d                                                     # needs sage.rings.finite_rings
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
>>> d.is_left_divisible_by(a)                                                 # needs sage.rings.finite_rings
True
>>> d.is_left_divisible_by(b)                                                 # needs sage.rings.finite_rings
True

See also

base_ring()[source]#

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

>>> from sage.all import *
>>> R = ZZ['t']; (t,) = R._first_ngens(1)
>>> sigma = R.hom([t+Integer(1)])
>>> S = R['x',sigma]; (x,) = S._first_ngens(1)
>>> a = S.random_element()
>>> a.base_ring()
Univariate Polynomial Ring in t over Integer Ring
>>> a.base_ring() is R
True
change_variable_name(var)[source]#

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

>>> from sage.all import *
>>> R = ZZ['t']; (t,) = R._first_ngens(1)
>>> sigma = R.hom([t+Integer(1)])
>>> S = R['x', sigma]; (x,) = S._first_ngens(1)
>>> a = x**Integer(3) + (Integer(2)*t + Integer(1))*x  + t**Integer(2) + Integer(3)*t + Integer(5)
>>> 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

>>> from sage.all import *
>>> b.parent()
Ore Polynomial Ring in y over Univariate Polynomial Ring in t over Integer Ring
 twisted by t |--> t + 1
coefficients(sparse=True)[source]#

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 as self.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]

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> sigma = R.hom([t+Integer(1)])
>>> S = R['x',sigma]; (x,) = S._first_ngens(1)
>>> a = Integer(1) + x**Integer(4) + (t+Integer(1))*x**Integer(2) + t**Integer(2)
>>> a.coefficients()
[t^2 + 1, t + 1, 1]
>>> a.coefficients(sparse=False)
[t^2 + 1, 0, t + 1, 0, 1]
constant_coefficient()[source]#

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

>>> from sage.all import *
>>> R = ZZ['t']; (t,) = R._first_ngens(1)
>>> sigma = R.hom([t+Integer(1)])
>>> S = R['x',sigma]; (x,) = S._first_ngens(1)
>>> a = x + t**Integer(2) + Integer(2)
>>> a.constant_coefficient()
t^2 + 2
degree()[source]#

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

>>> from sage.all import *
>>> R = ZZ['t']; (t,) = R._first_ngens(1)
>>> sigma = R.hom([t+Integer(1)])
>>> S = R['x',sigma]; (x,) = S._first_ngens(1)
>>> a = x**Integer(2) + t*x**Integer(3) + t**Integer(2)*x + Integer(1)
>>> a.degree()
3
>>> S.zero().degree()
-1
>>> S(Integer(5)).degree()
0
exponents()[source]#

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]

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> sigma = R.hom([t+Integer(1)])
>>> S = R['x',sigma]; (x,) = S._first_ngens(1)
>>> a = Integer(1) + x**Integer(4) + (t+Integer(1))*x**Integer(2) + t**Integer(2)
>>> a.exponents()
[0, 2, 4]
hamming_weight()[source]#

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

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> sigma = R.hom([t+Integer(1)])
>>> S = R['x',sigma]; (x,) = S._first_ngens(1)
>>> a = Integer(1) + x**Integer(4) + (t+Integer(1))*x**Integer(2) + t**Integer(2)
>>> a.number_of_terms()
3

This is also an alias for hamming_weight:

sage: a.hamming_weight()
3

>>> from sage.all import *
>>> a.hamming_weight()
3
is_constant()[source]#

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

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> sigma = R.hom([t+Integer(1)])
>>> S = R['x',sigma]; (x,) = S._first_ngens(1)
>>> R(Integer(2)).is_constant()
True
>>> (x + Integer(1)).is_constant()
False
is_left_divisible_by(other)[source]#

Check if self is divisible by other on the left.

INPUT:

  • other – an Ore polynomial in the same ring as self

OUTPUT:

Return True or False.

EXAMPLES:

sage: # needs sage.rings.finite_rings
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

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> k = GF(Integer(5)**Integer(3), names=('t',)); (t,) = k._first_ngens(1)
>>> Frob = k.frobenius_endomorphism()
>>> S = k['x',Frob]; (x,) = S._first_ngens(1)
>>> a = x**Integer(2) + t*x + t**Integer(2) + Integer(3)
>>> b = x**Integer(3) + (t + Integer(1))*x**Integer(2) + Integer(1)
>>> c = a*b
>>> c.is_left_divisible_by(a)
True
>>> c.is_left_divisible_by(b)
False

Divisibility by \(0\) does not make sense:

sage: c.is_left_divisible_by(S(0))                                          # needs sage.rings.finite_rings
Traceback (most recent call last):
...
ZeroDivisionError: division by zero is not valid

>>> from sage.all import *
>>> c.is_left_divisible_by(S(Integer(0)))                                          # needs sage.rings.finite_rings
Traceback (most recent call last):
...
ZeroDivisionError: division by zero is not valid
is_monic()[source]#

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

>>> from sage.all import *
>>> R = ZZ['t']; (t,) = R._first_ngens(1)
>>> sigma = R.hom([t+Integer(1)])
>>> S = R['x',sigma]; (x,) = S._first_ngens(1)
>>> a = x + t
>>> a.is_monic()
True
>>> a = Integer(0)*x
>>> a.is_monic()
False
>>> a = t*x**Integer(3) + x**Integer(4) + (t+Integer(1))*x**Integer(2)
>>> a.is_monic()
True
>>> a = (t**Integer(2) + Integer(2)*t)*x**Integer(2) + x**Integer(3) + t**Integer(10)*x**Integer(5)
>>> a.is_monic()
False
is_monomial()[source]#

Return True if self 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

>>> from sage.all import *
>>> R = ZZ['t']; (t,) = R._first_ngens(1)
>>> sigma = R.hom([t+Integer(1)])
>>> S = R['x',sigma]; (x,) = S._first_ngens(1)
>>> x.is_monomial()
True
>>> (x+Integer(1)).is_monomial()
False
>>> (x**Integer(2)).is_monomial()
True
>>> S(Integer(1)).is_monomial()
True

The coefficient must be 1:

sage: (2*x^5).is_monomial()
False
sage: S(t).is_monomial()
False

>>> from sage.all import *
>>> (Integer(2)*x**Integer(5)).is_monomial()
False
>>> 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

>>> from sage.all import *
>>> (Integer(2)*x**Integer(5)).is_term()
True
>>> S(t).is_term()
True
is_nilpotent()[source]#

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

>>> from sage.all import *
>>> R = ZZ['t']; (t,) = R._first_ngens(1)
>>> sigma = R.hom([t+Integer(1)])
>>> S = R['x',sigma]; (x,) = S._first_ngens(1)
>>> x.is_nilpotent()
Traceback (most recent call last):
...
NotImplementedError
is_one()[source]#

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

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> sigma = R.hom([t+Integer(1)])
>>> S = R['x',sigma]; (x,) = S._first_ngens(1)
>>> R(Integer(1)).is_one()
True
>>> (x + Integer(3)).is_one()
False
is_right_divisible_by(other)[source]#

Check if self is divisible by other on the right.

INPUT:

  • other – an Ore polynomial in the same ring as self

OUTPUT:

Return True or False.

EXAMPLES:

sage: # needs sage.rings.finite_rings
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

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> k = GF(Integer(5)**Integer(3), names=('t',)); (t,) = k._first_ngens(1)
>>> Frob = k.frobenius_endomorphism()
>>> S = k['x',Frob]; (x,) = S._first_ngens(1)
>>> a = x**Integer(2) + t*x + t**Integer(2) + Integer(3)
>>> b = x**Integer(3) + (t + Integer(1))*x**Integer(2) + Integer(1)
>>> c = a*b
>>> c.is_right_divisible_by(a)
False
>>> c.is_right_divisible_by(b)
True

Divisibility by \(0\) does not make sense:

sage: c.is_right_divisible_by(S(0))                                         # needs sage.rings.finite_rings
Traceback (most recent call last):
...
ZeroDivisionError: division by zero is not valid

>>> from sage.all import *
>>> c.is_right_divisible_by(S(Integer(0)))                                         # needs sage.rings.finite_rings
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

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> sigma = R.hom([t+Integer(1)])
>>> S = R['x',sigma]; (x,) = S._first_ngens(1)
>>> a = x**Integer(2) + Integer(2)*x + t
>>> b = (t+Integer(1))*x + t**Integer(2)
>>> c = a*b
>>> c.is_right_divisible_by(b)
Traceback (most recent call last):
...
NotImplementedError: the leading coefficient of the divisor is not invertible
is_term()[source]#

Return True if self 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

>>> from sage.all import *
>>> R = ZZ['t']; (t,) = R._first_ngens(1)
>>> sigma = R.hom([t+Integer(1)])
>>> S = R['x',sigma]; (x,) = S._first_ngens(1)
>>> x.is_term()
True
>>> R(Integer(1)).is_term()
True
>>> (Integer(3)*x**Integer(5)).is_term()
True
>>> (Integer(1)+Integer(3)*x**Integer(5)).is_term()
False

If you want to test that self also has leading coefficient 1, use is_monomial() instead:

sage: (3*x^5).is_monomial()
False

>>> from sage.all import *
>>> (Integer(3)*x**Integer(5)).is_monomial()
False
is_unit()[source]#

Return True if this Ore polynomial is a unit.

When the base ring \(R\) is an integral domain, then an 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

>>> from sage.all import *
>>> R = ZZ['t']; (t,) = R._first_ngens(1)
>>> sigma = R.hom([t+Integer(1)])
>>> S = R['x',sigma]; (x,) = S._first_ngens(1)
>>> a = x + (t+Integer(1))*x**Integer(5) + t**Integer(2)*x**Integer(3) - x**Integer(5)
>>> a.is_unit()
False
is_zero()[source]#

Return True if self 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

>>> from sage.all import *
>>> R = ZZ['t']; (t,) = R._first_ngens(1)
>>> sigma = R.hom([t+Integer(1)])
>>> S = R['x',sigma]; (x,) = S._first_ngens(1)
>>> a = x + Integer(1)
>>> a.is_zero()
False
>>> b = S.zero()
>>> b.is_zero()
True
leading_coefficient()[source]#

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

>>> from sage.all import *
>>> R = ZZ['t']; (t,) = R._first_ngens(1)
>>> sigma = R.hom([t+Integer(1)])
>>> S = R['x',sigma]; (x,) = S._first_ngens(1)
>>> a = (t+Integer(1))*x**Integer(5) + t**Integer(2)*x**Integer(3) + x
>>> a.leading_coefficient()
t + 1

By convention, the leading coefficient to the zero polynomial is zero:

sage: S(0).leading_coefficient()
0

>>> from sage.all import *
>>> S(Integer(0)).leading_coefficient()
0
left_divides(other)[source]#

Check if self divides other on the left.

INPUT:

  • other – an Ore polynomial in the same ring as self

OUTPUT:

Return True or False.

EXAMPLES:

sage: # needs sage.rings.finite_rings
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

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> k = GF(Integer(5)**Integer(3), names=('t',)); (t,) = k._first_ngens(1)
>>> Frob = k.frobenius_endomorphism()
>>> S = k['x',Frob]; (x,) = S._first_ngens(1)
>>> a = x**Integer(2) + t*x + t**Integer(2) + Integer(3)
>>> b = x**Integer(3) + (t + Integer(1))*x**Integer(2) + Integer(1)
>>> c = a * b
>>> a.left_divides(c)
True
>>> b.left_divides(c)
False

Divisibility by \(0\) does not make sense:

sage: S(0).left_divides(c)                                                  # needs sage.rings.finite_rings
Traceback (most recent call last):
...
ZeroDivisionError: division by zero is not valid

>>> from sage.all import *
>>> S(Integer(0)).left_divides(c)                                                  # needs sage.rings.finite_rings
Traceback (most recent call last):
...
ZeroDivisionError: division by zero is not valid
left_gcd(other, monic=True)[source]#

Return the left gcd of self and other.

INPUT:

  • other – an Ore polynomial in the same ring as self

  • monic – boolean (default: True); return whether the left gcd should be normalized to be monic

OUTPUT:

The left gcd of self and other, that is an 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 both self and other. If monic is True, \(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: # needs sage.rings.finite_rings
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

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> k = GF(Integer(5)**Integer(3), names=('t',)); (t,) = k._first_ngens(1)
>>> Frob = k.frobenius_endomorphism()
>>> S = k['x',Frob]; (x,) = S._first_ngens(1)
>>> a = (x + t) * (x**Integer(2) + t*x + Integer(1))
>>> b = Integer(2) * (x + t) * (x**Integer(3) + (t+Integer(1))*x**Integer(2) + t**Integer(2))
>>> a.left_gcd(b)
x + t

Specifying monic=False, we can get a nonmonic gcd:

sage: a.left_gcd(b,monic=False)                                             # needs sage.rings.finite_rings
2*t*x + 4*t + 2

>>> from sage.all import *
>>> a.left_gcd(b,monic=False)                                             # needs sage.rings.finite_rings
2*t*x + 4*t + 2

The base ring needs to be a field:

sage: # needs sage.rings.finite_rings
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

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> sigma = R.hom([t + Integer(1)])
>>> S = R['x',sigma]; (x,) = S._first_ngens(1)
>>> a = (x + t) * (x**Integer(2) + t*x + Integer(1))
>>> b = Integer(2) * (x + t) * (x**Integer(3) + (t+Integer(1))*x**Integer(2) + t**Integer(2))
>>> 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: # needs sage.rings.finite_rings
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

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> FR = R.fraction_field()
>>> f = FR.hom([FR(t)**Integer(2)])
>>> S = FR['x',f]; (x,) = S._first_ngens(1)
>>> a = (x + t) * (x**Integer(2) + t*x + Integer(1))
>>> b = Integer(2) * (x + t) * (x**Integer(3) + (t+Integer(1))*x**Integer(2) + t**Integer(2))
>>> 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)[source]#

Return the left lcm of self and other.

INPUT:

  • other – an Ore polynomial in the same ring as self

  • monic – boolean (default: True); return whether the left lcm should be normalized to be monic

OUTPUT:

The left lcm of self and other, that is an Ore polynomial \(l\) with the following property: any Ore polynomial is a left multiple of \(l\) (right divisible by \(l\)) iff it is a left multiple of both self and other (right divisible by self and other). If monic is True, \(l\) 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: # needs sage.rings.finite_rings
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

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> k = GF(Integer(5)**Integer(3), names=('t',)); (t,) = k._first_ngens(1)
>>> Frob = k.frobenius_endomorphism()
>>> S = k['x',Frob]; (x,) = S._first_ngens(1)
>>> a = (x + t**Integer(2)) * (x + t)
>>> b = Integer(2) * (x**Integer(2) + t + Integer(1)) * (x * t)
>>> 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
>>> c.is_right_divisible_by(a)
True
>>> c.is_right_divisible_by(b)
True
>>> a.degree() + b.degree() == c.degree() + a.right_gcd(b).degree()
True

Specifying monic=False, we can get a nonmonic lcm:

sage: a.left_lcm(b,monic=False)                                             # needs sage.rings.finite_rings
(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

>>> from sage.all import *
>>> a.left_lcm(b,monic=False)                                             # needs sage.rings.finite_rings
(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

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> sigma = R.hom([t+Integer(1)])
>>> S = R['x',sigma]; (x,) = S._first_ngens(1)
>>> a = (x + t**Integer(2)) * (x + t)
>>> b = Integer(2) * (x**Integer(2) + t + Integer(1)) * (x * t)
>>> a.left_lcm(b)
Traceback (most recent call last):
...
TypeError: the base ring must be a field
left_mod(other)[source]#

Return the remainder of left division of self by other.

EXAMPLES:

sage: # needs sage.rings.finite_rings
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

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> k = GF(Integer(5)**Integer(3), names=('t',)); (t,) = k._first_ngens(1)
>>> Frob = k.frobenius_endomorphism()
>>> S = k['x',Frob]; (x,) = S._first_ngens(1)
>>> a = Integer(1) + t*x**Integer(2)
>>> b = x + Integer(1)
>>> a.left_mod(b)
2*t^2 + 4*t
left_monic()[source]#

Return the unique monic Ore polynomial \(m\) which divides this polynomial on the left and has the same degree.

Given an 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: # needs sage.rings.finite_rings
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

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> k = GF(Integer(5)**Integer(3), names=('t',)); (t,) = k._first_ngens(1)
>>> Frob = k.frobenius_endomorphism()
>>> S = k['x',Frob]; (x,) = S._first_ngens(1)
>>> a = (Integer(3)*t**Integer(2) + Integer(3)*t + Integer(2))*x**Integer(3) + (Integer(2)*t**Integer(2) + Integer(3))*x**Integer(2) + (Integer(4)*t**Integer(2) + t + Integer(4))*x + Integer(2)*t**Integer(2) + Integer(2)
>>> 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: # needs sage.rings.finite_rings
sage: b.degree() == a.degree()
True
sage: a.is_left_divisible_by(b)
True
sage: twist = S.twisting_morphism(-a.degree())
sage: a == b * twist(a.leading_coefficient())
True

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> b.degree() == a.degree()
True
>>> a.is_left_divisible_by(b)
True
>>> twist = S.twisting_morphism(-a.degree())
>>> a == b * twist(a.leading_coefficient())
True

Note that \(b\) does not divide \(a\) on the right:

sage: a.is_right_divisible_by(b)                                            # needs sage.rings.finite_rings
False

>>> from sage.all import *
>>> a.is_right_divisible_by(b)                                            # needs sage.rings.finite_rings
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

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> der = R.derivation()
>>> S = R['x', der]; (x,) = S._first_ngens(1)
>>> a = t*x
>>> a.left_monic()
Traceback (most recent call last):
...
NotImplementedError: the leading coefficient is not a unit
left_quo_rem(other)[source]#

Return the quotient and remainder of the left Euclidean division of self by other.

INPUT:

  • other – an Ore polynomial in the same ring as self

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: # needs sage.rings.finite_rings
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

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> k = GF(Integer(5)**Integer(3), names=('t',)); (t,) = k._first_ngens(1)
>>> Frob = k.frobenius_endomorphism()
>>> S = k['x',Frob]; (x,) = S._first_ngens(1)
>>> a = (Integer(3)*t**Integer(2) + Integer(3)*t + Integer(2))*x**Integer(3) + (Integer(2)*t**Integer(2) + Integer(3))*x**Integer(2) + (Integer(4)*t**Integer(2) + t + Integer(4))*x + Integer(2)*t**Integer(2) + Integer(2)
>>> b = (Integer(3)*t**Integer(2) + Integer(4)*t + Integer(2))*x**Integer(2) + (Integer(2)*t**Integer(2) + Integer(4)*t + Integer(3))*x + Integer(2)*t**Integer(2) + t + Integer(1)
>>> q,r = a.left_quo_rem(b)
>>> 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)

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> K = R.fraction_field()
>>> sigma = K.hom([(t+Integer(1))/(t-Integer(1))])
>>> S = K['x',sigma]; (x,) = S._first_ngens(1)
>>> a = (-Integer(2)*t**Integer(2) - t + Integer(1))*x**Integer(3) + (-t**Integer(2) + t)*x**Integer(2) + (-Integer(12)*t - Integer(2))*x - t**Integer(2) - Integer(95)*t + Integer(1)
>>> b = x**Integer(2) + (Integer(5)*t - Integer(6))*x - Integer(4)*t**Integer(2) + Integer(4)*t - Integer(1)
>>> 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)[source]#

Return the left gcd of self and other along with the coefficients for the linear combination.

If \(a\) is self and \(b\) is other, 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 – an Ore polynomial in the same ring as self

  • monic – boolean (default: True); return whether the left gcd should be normalized to be monic

OUTPUT:

  • The left gcd of self and other, that is an 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 both self and other. If monic is True, \(g\) is in addition monic. (With this extra condition, it is uniquely determined.)

  • Two Ore polynomials \(u\) and \(v\) such that:

    \[g = a \cdot u + b \cdot v,\]

    where \(s\) is self and \(b\) is other.

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: # needs sage.rings.finite_rings
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

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> k = GF(Integer(5)**Integer(3), names=('t',)); (t,) = k._first_ngens(1)
>>> Frob = k.frobenius_endomorphism()
>>> S = k['x',Frob]; (x,) = S._first_ngens(1)
>>> a = (x + t) * (x**Integer(2) + t*x + Integer(1))
>>> b = Integer(2) * (x + t) * (x**Integer(3) + (t+Integer(1))*x**Integer(2) + t**Integer(2))
>>> g,u,v = a.left_xgcd(b); g
x + t
>>> 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                                # needs sage.rings.finite_rings
2*t*x + 4*t + 2
sage: a*u + b*v == g                                                        # needs sage.rings.finite_rings
True

>>> from sage.all import *
>>> g,u,v = a.left_xgcd(b, monic=False); g                                # needs sage.rings.finite_rings
2*t*x + 4*t + 2
>>> a*u + b*v == g                                                        # needs sage.rings.finite_rings
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

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> sigma = R.hom([t+Integer(1)])
>>> S = R['x',sigma]; (x,) = S._first_ngens(1)
>>> a = (x + t) * (x**Integer(2) + t*x + Integer(1))
>>> b = Integer(2) * (x + t) * (x**Integer(3) + (t+Integer(1))*x**Integer(2) + t**Integer(2))
>>> 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

>>> from sage.all import *
>>> FR = R.fraction_field()
>>> f = FR.hom([FR(t)**Integer(2)])
>>> S = FR['x',f]; (x,) = S._first_ngens(1)
>>> a = (x + t) * (x**Integer(2) + t*x + Integer(1))
>>> b = Integer(2) * (x + t) * (x**Integer(3) + (t+Integer(1))*x**Integer(2) + t**Integer(2))
>>> 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)[source]#

Return the left lcm \(L\) of self and other together with two Ore polynomials \(U\) and \(V\) such that

\[U \cdot \text{self} = V \cdot \text{other} = L.\]

EXAMPLES:

sage: # needs sage.rings.finite_rings
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                                                            # needs sage.rings.finite_rings
True
sage: V * Q == L                                                            # needs sage.rings.finite_rings
True

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> k = GF(Integer(5)**Integer(3), names=('t',)); (t,) = k._first_ngens(1)
>>> Frob = k.frobenius_endomorphism()
>>> S = k['x',Frob]; (x,) = S._first_ngens(1)
>>> P = (x + t**Integer(2)) * (x + t)
>>> Q = Integer(2) * (x**Integer(2) + t + Integer(1)) * (x * t)
>>> L, U, V = P.left_xlcm(Q)
>>> 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

>>> U * P == L                                                            # needs sage.rings.finite_rings
True
>>> V * Q == L                                                            # needs sage.rings.finite_rings
True
number_of_terms()[source]#

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

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> sigma = R.hom([t+Integer(1)])
>>> S = R['x',sigma]; (x,) = S._first_ngens(1)
>>> a = Integer(1) + x**Integer(4) + (t+Integer(1))*x**Integer(2) + t**Integer(2)
>>> a.number_of_terms()
3

This is also an alias for hamming_weight:

sage: a.hamming_weight()
3

>>> from sage.all import *
>>> a.hamming_weight()
3
padded_list(n=None)[source]#

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

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> sigma = R.hom([t+Integer(1)])
>>> S = R['x',sigma]; (x,) = S._first_ngens(1)
>>> a = Integer(1) + t*x**Integer(3) + t**Integer(2)*x**Integer(5)
>>> a.padded_list()
[1, 0, 0, t, 0, t^2]
>>> a.padded_list(Integer(10))
[1, 0, 0, t, 0, t^2, 0, 0, 0, 0]
>>> len(a.padded_list(Integer(10)))
10
>>> a.padded_list(Integer(3))
[1, 0, 0]
>>> a.padded_list(Integer(0))
[]
>>> a.padded_list(-Integer(1))
Traceback (most recent call last):
...
ValueError: n must be at least 0
prec()[source]#

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

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> sigma = R.hom([t+Integer(1)])
>>> S = R['x',sigma]; (x,) = S._first_ngens(1)
>>> x.prec()
+Infinity
right_divides(other)[source]#

Check if self divides other on the right.

INPUT:

  • other – an Ore polynomial in the same ring as self

OUTPUT:

Return True or False.

EXAMPLES:

sage: # needs sage.rings.finite_rings
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

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> k = GF(Integer(5)**Integer(3), names=('t',)); (t,) = k._first_ngens(1)
>>> Frob = k.frobenius_endomorphism()
>>> S = k['x',Frob]; (x,) = S._first_ngens(1)
>>> a = x**Integer(2) + t*x + t**Integer(2) + Integer(3)
>>> b = x**Integer(3) + (t + Integer(1))*x**Integer(2) + Integer(1)
>>> c = a * b
>>> a.right_divides(c)
False
>>> b.right_divides(c)
True

Divisibility by \(0\) does not make sense:

sage: S(0).right_divides(c)                                                 # needs sage.rings.finite_rings
Traceback (most recent call last):
...
ZeroDivisionError: division by zero is not valid

>>> from sage.all import *
>>> S(Integer(0)).right_divides(c)                                                 # needs sage.rings.finite_rings
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

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> sigma = R.hom([t+Integer(1)])
>>> S = R['x',sigma]; (x,) = S._first_ngens(1)
>>> a = x**Integer(2) + Integer(2)*x + t
>>> b = (t+Integer(1))*x + t**Integer(2)
>>> c = a*b
>>> b.right_divides(c)
Traceback (most recent call last):
...
NotImplementedError: the leading coefficient of the divisor is not invertible
right_gcd(other, monic=True)[source]#

Return the right gcd of self and other.

INPUT:

  • other – an Ore polynomial in the same ring as self

  • monic – boolean (default: True); return whether the right gcd should be normalized to be monic

OUTPUT:

The right gcd of self and other, that is an 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 both self and other. If monic is True, \(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: # needs sage.rings.finite_rings
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

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> k = GF(Integer(5)**Integer(3), names=('t',)); (t,) = k._first_ngens(1)
>>> Frob = k.frobenius_endomorphism()
>>> S = k['x',Frob]; (x,) = S._first_ngens(1)
>>> a = (x**Integer(2) + t*x + Integer(1)) * (x + t)
>>> b = Integer(2) * (x**Integer(3) + (t+Integer(1))*x**Integer(2) + t**Integer(2)) * (x + t)
>>> a.right_gcd(b)
x + t

Specifying monic=False, we can get a nonmonic gcd:

sage: a.right_gcd(b,monic=False)                                            # needs sage.rings.finite_rings
(4*t^2 + 4*t + 1)*x + 4*t^2 + 4*t + 3

>>> from sage.all import *
>>> a.right_gcd(b,monic=False)                                            # needs sage.rings.finite_rings
(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

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> sigma = R.hom([t+Integer(1)])
>>> S = R['x',sigma]; (x,) = S._first_ngens(1)
>>> a = (x**Integer(2) + t*x + Integer(1)) * (x + t)
>>> b = Integer(2) * (x**Integer(3) + (t+Integer(1))*x**Integer(2) + t**Integer(2)) * (x + t)
>>> a.right_gcd(b)
Traceback (most recent call last):
...
TypeError: the base ring must be a field
right_lcm(other, monic=True)[source]#

Return the right lcm of self and other.

INPUT:

  • other – an Ore polynomial in the same ring as self

  • monic – boolean (default: True); return whether the right lcm should be normalized to be monic

OUTPUT:

The right lcm of self and other, that is an Ore polynomial \(l\) with the following property: any Ore polynomial is a right multiple of \(g\) (left divisible by \(l\)) iff it is a right multiple of both self and other (left divisible by self and other). If monic is True, \(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: # needs sage.rings.finite_rings
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

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> k = GF(Integer(5)**Integer(3), names=('t',)); (t,) = k._first_ngens(1)
>>> Frob = k.frobenius_endomorphism()
>>> S = k['x',Frob]; (x,) = S._first_ngens(1)
>>> a = (x + t) * (x + t**Integer(2))
>>> b = Integer(2) * (x + t) * (x**Integer(2) + t + Integer(1))
>>> 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
>>> c.is_left_divisible_by(a)
True
>>> c.is_left_divisible_by(b)
True
>>> 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)                                            # needs sage.rings.finite_rings
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

>>> from sage.all import *
>>> a.right_lcm(b,monic=False)                                            # needs sage.rings.finite_rings
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

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> sigma = R.hom([t+Integer(1)])
>>> S = R['x',sigma]; (x,) = S._first_ngens(1)
>>> a = (x + t) * (x + t**Integer(2))
>>> b = Integer(2) * (x + t) * (x**Integer(2) + t + Integer(1))
>>> 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

>>> from sage.all import *
>>> FR = R.fraction_field()
>>> f = FR.hom([FR(t)**Integer(2)])
>>> S = FR['x',f]; (x,) = S._first_ngens(1)
>>> a = (x + t) * (x + t**Integer(2))
>>> b = Integer(2) * (x + t) * (x**Integer(2) + t + Integer(1))
>>> 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)[source]#

Return the remainder of right division of self by other.

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

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> sigma = R.hom([t+Integer(1)])
>>> S = R['x',sigma]; (x,) = S._first_ngens(1)
>>> a = Integer(1) + t*x**Integer(2)
>>> b = x + Integer(1)
>>> a % b
t + 1
>>> (x**Integer(3) + x - Integer(1)).right_mod(x**Integer(2) - Integer(1))
2*x - 1
right_monic()[source]#

Return the unique monic Ore polynomial which divides this polynomial on the right and has the same degree.

Given an Ore polynomial \(P\) of degree \(n\), its right monic is given by \((1/k) \cdot P\), where \(k\) is the leading coefficient of \(P\).

EXAMPLES:

sage: # needs sage.rings.finite_rings
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

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> k = GF(Integer(5)**Integer(3), names=('t',)); (t,) = k._first_ngens(1)
>>> Frob = k.frobenius_endomorphism()
>>> S = k['x',Frob]; (x,) = S._first_ngens(1)
>>> a = (Integer(3)*t**Integer(2) + Integer(3)*t + Integer(2))*x**Integer(3) + (Integer(2)*t**Integer(2) + Integer(3))*x**Integer(2) + (Integer(4)*t**Integer(2) + t + Integer(4))*x + Integer(2)*t**Integer(2) + Integer(2)
>>> 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()                                              # needs sage.rings.finite_rings
True
sage: a.is_right_divisible_by(b)                                            # needs sage.rings.finite_rings
True
sage: a == a.leading_coefficient() * b                                      # needs sage.rings.finite_rings
True

>>> from sage.all import *
>>> b.degree() == a.degree()                                              # needs sage.rings.finite_rings
True
>>> a.is_right_divisible_by(b)                                            # needs sage.rings.finite_rings
True
>>> a == a.leading_coefficient() * b                                      # needs sage.rings.finite_rings
True

Note that \(b\) does not divide \(a\) on the right:

sage: a.is_left_divisible_by(b)                                             # needs sage.rings.finite_rings
False

>>> from sage.all import *
>>> a.is_left_divisible_by(b)                                             # needs sage.rings.finite_rings
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

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> der = R.derivation()
>>> S = R['x', der]; (x,) = S._first_ngens(1)
>>> a = t*x
>>> a.right_monic()
Traceback (most recent call last):
...
NotImplementedError: the leading coefficient is not a unit
right_quo_rem(other)[source]#

Return the quotient and remainder of the right Euclidean division of self by other.

INPUT:

  • other – an Ore polynomial in the same ring as self

OUTPUT:

  • the quotient and the remainder of the right 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)
sage: b = S.random_element(monic=True)
sage: q,r = a.right_quo_rem(b)
sage: a == q*b + r
True

>>> from sage.all import *
>>> R = ZZ['t']; (t,) = R._first_ngens(1)
>>> sigma = R.hom([t+Integer(1)])
>>> S = R['x',sigma]; (x,) = S._first_ngens(1)
>>> a = S.random_element(degree=Integer(4))
>>> b = S.random_element(monic=True)
>>> q,r = a.right_quo_rem(b)
>>> a == q*b + r
True

The leading coefficient of the divisor need to be invertible:

sage: a.right_quo_rem(S(0))
Traceback (most recent call last):
...
ZeroDivisionError: division by zero is not valid
sage: c = S.random_element()
sage: while not c or c.leading_coefficient().is_unit():
....:     c = S.random_element()
sage: while a.degree() < c.degree():
....:     a = S.random_element(degree=4)
sage: a.right_quo_rem(c)
Traceback (most recent call last):
...
NotImplementedError: the leading coefficient of the divisor is not invertible

>>> from sage.all import *
>>> a.right_quo_rem(S(Integer(0)))
Traceback (most recent call last):
...
ZeroDivisionError: division by zero is not valid
>>> c = S.random_element()
>>> while not c or c.leading_coefficient().is_unit():
...     c = S.random_element()
>>> while a.degree() < c.degree():
...     a = S.random_element(degree=Integer(4))
>>> 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)[source]#

Return the right gcd of self and other along with the coefficients for the linear combination.

If \(a\) is self and \(b\) is other, 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 – an Ore polynomial in the same ring as self

  • monic – boolean (default: True); return whether the right gcd should be normalized to be monic

OUTPUT:

  • The right gcd of self and other, that is an 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 both self and other. If monic is True, \(g\) is in addition monic. (With this extra condition, it is uniquely determined.)

  • Two Ore polynomials \(u\) and \(v\) such that:

    \[g = u \cdot a + v \cdot b\]

    where \(a\) is self and \(b\) is other.

Note

Works only if the base ring is a field (otherwise right gcd do not exist in general).

EXAMPLES:

sage: # needs sage.rings.finite_rings
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

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> k = GF(Integer(5)**Integer(3), names=('t',)); (t,) = k._first_ngens(1)
>>> Frob = k.frobenius_endomorphism()
>>> S = k['x',Frob]; (x,) = S._first_ngens(1)
>>> a = (x**Integer(2) + t*x + Integer(1)) * (x + t)
>>> b = Integer(2) * (x**Integer(3) + (t+Integer(1))*x**Integer(2) + t**Integer(2)) * (x + t)
>>> g,u,v = a.right_xgcd(b); g
x + t
>>> 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                               # needs sage.rings.finite_rings
(4*t^2 + 4*t + 1)*x + 4*t^2 + 4*t + 3
sage: u*a + v*b == g                                                        # needs sage.rings.finite_rings
True

>>> from sage.all import *
>>> g,u,v = a.right_xgcd(b, monic=False); g                               # needs sage.rings.finite_rings
(4*t^2 + 4*t + 1)*x + 4*t^2 + 4*t + 3
>>> u*a + v*b == g                                                        # needs sage.rings.finite_rings
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

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> sigma = R.hom([t+Integer(1)])
>>> S = R['x',sigma]; (x,) = S._first_ngens(1)
>>> a = (x**Integer(2) + t*x + Integer(1)) * (x + t)
>>> b = Integer(2) * (x**Integer(3) + (t+Integer(1))*x**Integer(2) + t**Integer(2)) * (x + t)
>>> a.right_xgcd(b)
Traceback (most recent call last):
...
TypeError: the base ring must be a field
right_xlcm(other, monic=True)[source]#

Return the right lcm \(L\) of self and other together with two Ore polynomials \(U\) and \(V\) such that

\[\text{self} \cdot U = \text{other} \cdot V = L.\]

INPUT:

  • other – an Ore polynomial in the same ring as self

  • monic – a boolean (default: True); whether the right lcm should be normalized to be monic

EXAMPLES:

sage: # needs sage.rings.finite_rings
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

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> k = GF(Integer(5)**Integer(3), names=('t',)); (t,) = k._first_ngens(1)
>>> Frob = k.frobenius_endomorphism()
>>> S = k['x',Frob]; (x,) = S._first_ngens(1)
>>> P = (x + t) * (x + t**Integer(2))
>>> Q = Integer(2) * (x + t) * (x**Integer(2) + t + Integer(1))
>>> L, U, V = P.right_xlcm(Q)
>>> 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
>>> P * U == L
True
>>> Q * V == L
True
shift(n)[source]#

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

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> sigma = R.hom([t+Integer(1)])
>>> S = R['x',sigma]; (x,) = S._first_ngens(1)
>>> a = x**Integer(5) + t**Integer(4)*x**Integer(4) + t**Integer(2)*x**Integer(2) + t**Integer(10)
>>> a.shift(Integer(0))
x^5 + t^4*x^4 + t^2*x^2 + t^10
>>> a.shift(-Integer(1))
x^4 + t^4*x^3 + t^2*x
>>> a.shift(-Integer(5))
1
>>> a.shift(Integer(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

>>> from sage.all import *
>>> a >> Integer(2)
x^3 + t^4*x^2 + t^2
>>> a << Integer(2)
x^7 + t^4*x^6 + t^2*x^4 + t^10*x^2
square()[source]#

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

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> sigma = R.hom([t+Integer(1)])
>>> S = R['x', sigma]; (x,) = S._first_ngens(1)
>>> a = x + t; a
x + t
>>> a.square()
x^2 + (2*t + 1)*x + t^2
>>> a.square() == a*a
True

>>> der = R.derivation()
>>> A = R['d', der]; (d,) = A._first_ngens(1)
>>> (d + t).square()
d^2 + 2*t*d + t^2 + 1
variable_name()[source]#

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'

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> sigma = R.hom([t+Integer(1)])
>>> S = R['x',sigma]; (x,) = S._first_ngens(1)
>>> a = x + t
>>> a.variable_name()
'x'
class sage.rings.polynomial.ore_polynomial_element.OrePolynomialBaseringInjection[source]#

Bases: Morphism

Representation of the canonical homomorphism from a ring \(R\) into an Ore polynomial ring over \(R\).

This class is necessary for automatic coercion from the base ring to the Ore polynomial ring.

See also

PolynomialBaseringInjection

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

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> sigma = R.hom([t+Integer(1)])
>>> S = R['x',sigma]; (x,) = S._first_ngens(1)
>>> 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()[source]#

Return an element of the codomain of the ring homomorphism.

EXAMPLES:

sage: # needs sage.rings.finite_rings
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

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> from sage.rings.polynomial.ore_polynomial_element import OrePolynomialBaseringInjection
>>> k = GF(Integer(5)**Integer(3), names=('t',)); (t,) = k._first_ngens(1)
>>> Frob = k.frobenius_endomorphism()
>>> S = k['x',Frob]; (x,) = S._first_ngens(1)
>>> m = OrePolynomialBaseringInjection(k, k['x', Frob])
>>> m.an_element()
x
section()[source]#

Return the canonical homomorphism from the constants of an Ore polynomial ring to the base ring according to self.

class sage.rings.polynomial.ore_polynomial_element.OrePolynomial_generic_dense[source]#

Bases: OrePolynomial

Generic implementation of dense Ore polynomial supporting any valid base ring, twisting morphism and twisting derivation.

coefficients(sparse=True)[source]#

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 as self.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]

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> sigma = R.hom([t+Integer(1)])
>>> S = R['x',sigma]; (x,) = S._first_ngens(1)
>>> a = Integer(1) + x**Integer(4) + (t+Integer(1))*x**Integer(2) + t**Integer(2)
>>> a.coefficients()
[t^2 + 1, t + 1, 1]
>>> a.coefficients(sparse=False)
[t^2 + 1, 0, t + 1, 0, 1]
degree()[source]#

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

>>> from sage.all import *
>>> R = ZZ['t']; (t,) = R._first_ngens(1)
>>> sigma = R.hom([t+Integer(1)])
>>> S = R['x',sigma]; (x,) = S._first_ngens(1)
>>> a = x**Integer(2) + t*x**Integer(3) + t**Integer(2)*x + Integer(1)
>>> a.degree()
3

By convention, the degree of \(0\) is \(-1\):

sage: S(0).degree()
-1

>>> from sage.all import *
>>> S(Integer(0)).degree()
-1
dict()[source]#

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}

>>> from sage.all import *
>>> R = ZZ['t']; (t,) = R._first_ngens(1)
>>> sigma = R.hom([t+Integer(1)])
>>> S = R['x',sigma]; (x,) = S._first_ngens(1)
>>> a = x**Integer(2012) + t*x**Integer(1006) + t**Integer(3) + Integer(2)*t
>>> a.dict()
{0: t^3 + 2*t, 1006: t, 2012: 1}
hilbert_shift(s, var=None)[source]#

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 ring

  • var – 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

>>> from sage.all import *
>>> R = GF(Integer(7))['t']; (t,) = R._first_ngens(1)
>>> der = R.derivation()
>>> A = R['d', der]; (d,) = A._first_ngens(1)

>>> L = d**Integer(3) + t*d**Integer(2)
>>> L.hilbert_shift(t)
d^3 + 4*t*d^2 + (5*t^2 + 3)*d + 2*t^3 + 4*t
>>> (d+t)**Integer(3) + t*(d+t)**Integer(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

>>> from sage.all import *
>>> 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: # needs sage.rings.finite_rings
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

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> k = GF(Integer(5)**Integer(3), names=('a',)); (a,) = k._first_ngens(1)
>>> Frob = k.frobenius_endomorphism()
>>> S = k['x', Frob]; (x,) = S._first_ngens(1)
>>> P = x**Integer(2) + a*x + a**Integer(2)
>>> Q = P.hilbert_shift(a); Q
x^2 + (2*a^2 + a + 4)*x + a^2 + 3*a + 4
>>> 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)
>>> Q.parent() is S
False

This behavior ensures that the Hilbert shift by a fixed element defines a homomorphism of rings:

sage: # needs sage.rings.finite_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

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> U = S.random_element(degree=Integer(5))
>>> V = S.random_element(degree=Integer(5))
>>> s = k.random_element()
>>> (U+V).hilbert_shift(s) == U.hilbert_shift(s) + V.hilbert_shift(s)
True
>>> (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: # needs sage.rings.finite_rings
sage: P = S.random_element(degree=10)
sage: s = k.random_element()
sage: P.hilbert_shift(s).hilbert_shift(-s) == P
True

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> P = S.random_element(degree=Integer(10))
>>> s = k.random_element()
>>> P.hilbert_shift(s).hilbert_shift(-s) == P
True
list(copy=True)[source]#

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]

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> sigma = R.hom([t+Integer(1)])
>>> S = R['x',sigma]; (x,) = S._first_ngens(1)
>>> a = Integer(1) + x**Integer(4) + (t+Integer(1))*x**Integer(2) + t**Integer(2)
>>> 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]

>>> from sage.all import *
>>> type(l)
<... 'list'>
>>> l[Integer(0)] = Integer(5)
>>> a.list()
[t^2 + 1, 0, t + 1, 0, 1]
truncate(n)[source]#

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

>>> from sage.all import *
>>> R = ZZ['t']; (t,) = R._first_ngens(1)
>>> sigma = R.hom([t+Integer(1)])
>>> S = R['x',sigma]; (x,) = S._first_ngens(1)
>>> a = t*x**Integer(3) + x**Integer(4) + (t+Integer(1))*x**Integer(2)
>>> a.truncate(Integer(4))
t*x^3 + (t + 1)*x^2
>>> a.truncate(Integer(3))
(t + 1)*x^2
valuation()[source]#

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

>>> from sage.all import *
>>> R = ZZ['t']; (t,) = R._first_ngens(1)
>>> sigma = R.hom([t+Integer(1)])
>>> S = R['x',sigma]; (x,) = S._first_ngens(1)
>>> a = x**Integer(2) + t*x**Integer(3) + t**Integer(2)*x
>>> a.valuation()
1

By convention, the valuation of \(0\) is \(+\infty\):

sage: S(0).valuation()
+Infinity

>>> from sage.all import *
>>> S(Integer(0)).valuation()
+Infinity