Univariate Skew Polynomials¶

This module provides the SkewPolynomial, which constructs a single univariate skew polynomial over commutative base rings and an automorphism over the base ring. Skew polynomials are non-commutative and so principal methods such as gcd, lcm, monic, multiplication, and division are given in left and right forms.

The generic implementation of dense skew polynomials is SkewPolynomial_generic_dense. The classes ConstantSkewPolynomialSection and SkewPolynomialBaseringInjection handle conversion from a skew polynomial ring to its base ring and vice versa respectively.

Warning

The current semantics of __call__() are experimental, so a warning is thrown when a skew polynomial is evaluated for the first time in a session. See the method documentation for details.

AUTHORS:

Xavier Caruso (2012-06-29): initial version
Arpit Merchant (2016-08-04): improved docstrings, fixed doctests and refactored classes and methods
Johan Rosenkilde (2016-08-03): changes for bug fixes, docstring and doctest errors

class sage.rings.polynomial.skew_polynomial_element.ConstantSkewPolynomialSection¶

Bases: sage.categories.map.Map

Representation of the canonical homomorphism from the constants of a skew polynomial ring to the base ring.

This class is necessary for automatic coercion from zero-degree skew polynomial ring into the base ring.

EXAMPLES:

sage: from sage.rings.polynomial.skew_polynomial_element import ConstantSkewPolynomialSection
sage: R.<t> = QQ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: m = ConstantSkewPolynomialSection(S, R); m
Generic map:
    From: Skew Polynomial Ring in x over Univariate Polynomial Ring in t over Rational Field twisted by t |--> t + 1
    To:   Univariate Polynomial Ring in t over Rational Field

class sage.rings.polynomial.skew_polynomial_element.SkewPolynomial¶

Bases: sage.structure.element.AlgebraElement

Abstract base class for skew polynomials.

This class must be inherited from and have key methods overridden.

Definition

Let \(R\) be a commutative ring equipped with an automorphism \(\sigma\).

Then, a skew polynomial is given by the equation:

\[F(X) = a_{n} X^{n} + \cdots + a_0,\]

where the coefficients \(a_i \in R\) and \(X\) is a formal variable.

Addition between two skew polynomials is defined by the usual addition operation and the modified multiplication is defined by the rule \(X a = \sigma(a) X\) for all \(a\) in \(R\). Skew polynomials are thus 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 skew polynomials in the same ring \(S\). The left (resp. right) euclidean division of \(a\) by \(b\) is a couple \((q,r)\) of elements in \(S\) such that

\(a = q b + r\) (resp. \(a = b q + r\))
the degree of \(r\) is less than the degree of \(b\)

\(q\) (resp. \(r\)) is called the quotient (resp. the remainder) of this euclidean division.

Properties

Keeping the previous notation, if the leading coefficient of \(b\) is a unit (e.g. if \(b\) is monic) then the quotient and the remainder in the right euclidean division exist and are unique.

The same result holds for the left euclidean division if in addition the twist map defining the skew polynomial ring is invertible.

Evaluation

The value of a given a skew polynomial \(p(x) = \sum_{i=0}^d a_i x^i\) at \(r\) is calculated using the formula:

\[p(r) = \sum_{i=0}^d a_i \sigma^i(r)\]

where \(\sigma\) is the base ring automorphism. This is called the operator evaluation method.

EXAMPLES:

We illustrate some functionalities implemented in this class.

We create the skew polynomial ring:

sage: R.<t> = ZZ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]; S
Skew Polynomial Ring in x over Univariate Polynomial Ring in t over Integer Ring
 twisted by t |--> t + 1

and some elements in it:

sage: a = t + x + 1; a
x + t + 1
sage: b = S([t^2,t+1,1]); b
x^2 + (t + 1)*x + t^2
sage: c = S.random_element(degree=3,monic=True); c
x^3 + (2*t - 1)*x

Ring operations are supported:

sage: a + b
x^2 + (t + 2)*x + t^2 + t + 1
sage: a - b
-x^2 - t*x - t^2 + t + 1

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

sage: b^2
x^4 + (2*t + 4)*x^3 + (3*t^2 + 7*t + 6)*x^2
 + (2*t^3 + 4*t^2 + 3*t + 1)*x + t^4
sage: b^2 == b*b
True

Sage also implements arithmetic over skew polynomial rings. You will find below a short panorama:

sage: q,r = c.right_quo_rem(b)
sage: q
x - t - 2
sage: r
3*t*x + t^3 + 2*t^2
sage: c == q*b + r
True

The operators // and % give respectively the quotient and the remainder of the right euclidean division:

sage: q == c // b
True
sage: r == c % b
True

Left euclidean division won’t work over our current \(S\) because Sage can’t invert the twist map:

sage: q,r = c.left_quo_rem(b)
Traceback (most recent call last):
...
NotImplementedError: inversion of the twist map Ring endomorphism of Univariate Polynomial Ring in t over Integer Ring
    Defn: t |--> t + 1

Here we can see the effect of the operator evaluation compared to the usual polynomial evaluation:

sage: a = x^2
sage: a(t)
t + 2

Here is a working example over a finite field:

sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x',Frob]
sage: a = x^4 + (4*t + 1)*x^3 + (t^2 + 3*t + 3)*x^2 + (3*t^2 + 2*t + 2)*x + (3*t^2 + 3*t + 1)
sage: b = (2*t^2 + 3)*x^2 + (3*t^2 + 1)*x + 4*t + 2
sage: q,r = a.left_quo_rem(b)
sage: q
(4*t^2 + t + 1)*x^2 + (2*t^2 + 2*t + 2)*x + 2*t^2 + 4*t + 3
sage: r
(t + 2)*x + 3*t^2 + 2*t + 4
sage: a == b*q + r
True

Once we have euclidean divisions, we have for free gcd and lcm (at least if the base ring is a field):

sage: a = (x + t) * (x + t^2)^2
sage: b = (x + t) * (t*x + t + 1) * (x + t^2)
sage: a.right_gcd(b)
x + t^2
sage: a.left_gcd(b)
x + t

The left lcm has the following meaning: given skew polynomials \(a\) and \(b\), their left lcm is the least degree polynomial \(c = ua = vb\) for some skew polynomials \(u, v\). Such a \(c\) always exist if the base ring is a field:

sage: c = a.left_lcm(b); c
x^5 + (4*t^2 + t + 3)*x^4 + (3*t^2 + 4*t)*x^3 + 2*t^2*x^2 + (2*t^2 + t)*x + 4*t^2 + 4
sage: c.is_right_divisible_by(a)
True
sage: c.is_right_divisible_by(b)
True

The right lcm is defined similarly as the least degree polynomial \(c = au = bv\) for some \(u,v\):

sage: d = a.right_lcm(b); d
x^5 + (t^2 + 1)*x^4 + (3*t^2 + 3*t + 3)*x^3 + (3*t^2 + t + 2)*x^2 + (4*t^2 + 3*t)*x + 4*t + 4
sage: d.is_left_divisible_by(a)
True
sage: d.is_left_divisible_by(b)
True

See also

base_ring()¶

Return the base ring of self.

EXAMPLES:

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

change_variable_name(var)¶

Change the name of the variable of self.

This will create the skew polynomial ring with the new name but same base ring and twist map. The returned skew polynomial will be an element of that skew polynomial ring.

INPUT:

var – the name of the new variable

EXAMPLES:

sage: R.<t> = ZZ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x', sigma]
sage: a = x^3 + (2*t + 1)*x  + t^2 + 3*t + 5
sage: b = a.change_variable_name('y'); b
y^3 + (2*t + 1)*y  + t^2 + 3*t + 5

Note that a new parent is created at the same time:

sage: b.parent()
Skew Polynomial Ring in y over Univariate Polynomial Ring in t over Integer Ring
 twisted by t |--> t + 1

coefficients(sparse=True)¶

Return the coefficients of the monomials appearing in self.

If sparse=True (the default), return only the 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]

conjugate(n)¶

Return self conjugated by \(x^n\), where \(x\) is the variable of self.

The conjugate is obtained from self by applying the \(n\)-th iterate of the twist map to each of its coefficients.

INPUT:

\(n\) – an integer, the power of conjugation

EXAMPLES:

sage: R.<t> = QQ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: a = t*x^3 + (t^2 + 1)*x^2 + 2*t
sage: b = a.conjugate(2); b
(t + 2)*x^3 + (t^2 + 4*t + 5)*x^2 + 2*t + 4
sage: x^2*a == b*x^2
True

In principle, negative values for \(n\) are allowed, but Sage needs to be able to invert the twist map:

sage: b = a.conjugate(-1)
Traceback (most recent call last):
...
NotImplementedError: inversion of the twist map Ring endomorphism of Univariate Polynomial Ring in t over Rational Field
    Defn: t |--> t + 1

Here is a working example:

sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: T.<y> = k['y',Frob]
sage: u = T.random_element(); u
(2*t^2 + 3)*y^2 + (4*t^2 + t + 4)*y + 2*t^2 + 2
sage: v = u.conjugate(-1); v
(3*t^2 + t)*y^2 + (4*t^2 + 2*t + 4)*y + 3*t^2 + t + 4
sage: u*y == y*v
True

constant_coefficient()¶

Return the constant coefficient (i.e. the coefficient of term of degree \(0\)) of self.

EXAMPLES:

sage: R.<t> = ZZ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: a = x + t^2 + 2
sage: a.constant_coefficient()
t^2 + 2

degree()¶

Return the degree of self.

By convention, the zero skew polynomial has degree \(-1\).

EXAMPLES:

sage: R.<t> = ZZ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: a = x^2 + t*x^3 + t^2*x + 1
sage: a.degree()
3
sage: S.zero().degree()
-1
sage: S(5).degree()
0

exponents()¶

Return the exponents of the monomials appearing in self.

EXAMPLES:

sage: R.<t> = QQ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: a = 1 + x^4 + (t+1)*x^2 + t^2
sage: a.exponents()
[0, 2, 4]

hamming_weight()¶

Return the number of 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 by other on the left.

INPUT:

other – a skew polynomial in the same ring as self

OUTPUT:

Return True or False.

EXAMPLES:

sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x',Frob]
sage: a = x^2 + t*x + t^2 + 3
sage: b = x^3 + (t + 1)*x^2 + 1
sage: c = a*b
sage: c.is_left_divisible_by(a)
True
sage: c.is_left_divisible_by(b)
False

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

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

is_monic()¶

Return True if this skew polynomial is monic.

The zero polynomial is by definition not monic.

EXAMPLES:

sage: R.<t> = ZZ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: a = x + t
sage: a.is_monic()
True
sage: a = 0*x
sage: a.is_monic()
False
sage: a = t*x^3 + x^4 + (t+1)*x^2
sage: a.is_monic()
True
sage: a = (t^2 + 2*t)*x^2 + x^3 + t^10*x^5
sage: a.is_monic()
False

is_monomial()¶

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

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.

Given a commutative ring \(R\) and a base ring automorphism \(\sigma\) of order \(n\), an element \(f\) of \(R[X, \sigma]\) is nilpotent if and only if all coefficients of \(f^n\) are nilpotent in \(R\).

Note

The paper “Nilpotents and units in skew polynomial rings over commutative rings” by M. Rimmer and K.R. Pearson describes the method to check whether a given skew polynomial is nilpotent. That method however, requires one to know the order of the automorphism which is not available in Sage. This method is thus not yet implemented.

EXAMPLES:

sage: R.<t> = ZZ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: x.is_nilpotent()
Traceback (most recent call last):
...
NotImplementedError

is_one()¶

Test whether this polynomial is \(1\).

EXAMPLES:

sage: R.<t> = QQ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: R(1).is_one()
True
sage: (x + 3).is_one()
False

is_right_divisible_by(other)¶

Check if self is divisible by other on the right.

INPUT:

other – a skew polynomial in the same ring as self

OUTPUT:

Return True or False.

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 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

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

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

is_unit()¶

Return True if this skew polynomial is a unit.

When the base ring \(R\) is an integral domain, then a skew polynomial \(f\) is a unit if and only if degree of \(f\) is \(0\) and \(f\) is then a unit in \(R\).

Note

The case when \(R\) is not an integral domain is not yet implemented.

EXAMPLES:

sage: R.<t> = ZZ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: a = x + (t+1)*x^5 + t^2*x^3 - x^5
sage: a.is_unit()
False

is_zero()¶

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

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

left_divides(other)¶

Check if self divides other on the left.

INPUT:

other – a skew polynomial in the same ring as self

OUTPUT:

Return True or False.

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 and other.

INPUT:

other – a skew 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 a skew polynomial \(g\) with the following property: any skew polynomial is divisible on the left by \(g\) iff it is divisible on the left by 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 two following conditions are fulfilled (otherwise left gcd do not exist in general): 1) the base ring is a field and 2) the twist map on this field is bijective.

EXAMPLES:

sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x',Frob]
sage: a = (x + t) * (x^2 + t*x + 1)
sage: b = 2 * (x + t) * (x^3 + (t+1)*x^2 + t^2)
sage: a.left_gcd(b)
x + t

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

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

The base ring needs to be a field:

sage: R.<t> = QQ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: a = (x + t) * (x^2 + t*x + 1)
sage: b = 2 * (x + t) * (x^3 + (t+1)*x^2 + t^2)
sage: a.left_gcd(b)
Traceback (most recent call last):
...
TypeError: the base ring must be a field

And the twist map needs to be bijective:

sage: FR = R.fraction_field()
sage: f = FR.hom([FR(t)^2])
sage: S.<x> = FR['x',f]
sage: a = (x + t) * (x^2 + t*x + 1)
sage: b = 2 * (x + t) * (x^3 + (t+1)*x^2 + t^2)
sage: a.left_gcd(b)
Traceback (most recent call last):
...
NotImplementedError: inversion of the twist map Ring endomorphism of Fraction Field of Univariate Polynomial Ring in t over Rational Field
    Defn: t |--> t^2

left_lcm(other, monic=True)¶

Return the left lcm of self and other.

INPUT:

other – a skew 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 a skew polynomial \(g\) with the following property: any skew polynomial divides \(g\) on the right iff it divides both self and other on the right. 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 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 by other.

EXAMPLES:

sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x',Frob]
sage: a = 1 + t*x^2
sage: b = x + 1
sage: a.left_mod(b)
2*t^2 + 4*t

left_monic()¶

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

Given a skew polynomial \(p\) of degree \(n\), its left monic is given by \(m = p \sigma^{-n}(1/k)\), where \(k\) is the leading coefficient of \(p\), i.e. by the appropriate scalar multiplication on the right.

EXAMPLES:

sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x',Frob]
sage: a = (3*t^2 + 3*t + 2)*x^3 + (2*t^2 + 3)*x^2 + (4*t^2 + t + 4)*x + 2*t^2 + 2
sage: b = a.left_monic(); b
x^3 + (4*t^2 + 3*t)*x^2 + (4*t + 2)*x + 2*t^2 + 4*t + 3

Check list:

sage: b.degree() == a.degree()
True
sage: b.is_left_divisible_by(a)
True
sage: twist = S.twist_map(-a.degree())
sage: a == b * twist(a.leading_coefficient())
True

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

sage: a.is_right_divisible_by(b)
False

This function does not work if the leading coefficient is not a unit:

sage: R.<t> = QQ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: a = t*x
sage: a.left_monic()
Traceback (most recent call last):
...
NotImplementedError: the leading coefficient is not a unit

left_xgcd(other, monic=True)¶

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

If \(a\) is self and \(b\) is other, then there are skew polynomials \(u\) and \(v\) such that \(g = a u + b v\), where \(g\) is the left gcd of \(a\) and \(b\). This method returns \((g, u, v)\).

INPUT:

other – a skew polynomial in the same ring 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 a skew polynomial \(g\) with the following property: any skew polynomial is divisible on the left by \(g\) iff it is divisible on the left by both self and other. If monic is True, \(g\) is in addition monic. (With this extra condition, it is uniquely determined.)
Two skew polynomials \(u\) and \(v\) such that:

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

where \(s\) is self and \(b\) 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 twist map on this field is bijective.

EXAMPLES:

sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x',Frob]
sage: a = (x + t) * (x^2 + t*x + 1)
sage: b = 2 * (x + t) * (x^3 + (t+1)*x^2 + t^2)
sage: g,u,v = a.left_xgcd(b); g
x + t
sage: a*u + b*v == g
True

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

sage: g,u,v = a.left_xgcd(b, monic=False); g
2*t*x + 4*t + 2
sage: a*u + b*v == g
True

The base ring must be a field:

sage: R.<t> = QQ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: a = (x + t) * (x^2 + t*x + 1)
sage: b = 2 * (x + t) * (x^3 + (t+1)*x^2 + t^2)
sage: a.left_xgcd(b)
Traceback (most recent call last):
...
TypeError: the base ring must be a field

And the twist map must be bijective:

sage: FR = R.fraction_field()
sage: f = FR.hom([FR(t)^2])
sage: S.<x> = FR['x',f]
sage: a = (x + t) * (x^2 + t*x + 1)
sage: b = 2 * (x + t) * (x^3 + (t+1)*x^2 + t^2)
sage: a.left_xgcd(b)
Traceback (most recent call last):
...
NotImplementedError: inversion of the twist map Ring endomorphism of Fraction Field of Univariate Polynomial Ring in t over Rational Field
    Defn: t |--> t^2

multi_point_evaluation(eval_pts)¶

Evaluate self at list of evaluation points.

INPUT:

eval_pts – list of points at which self is to be evaluated

OUTPUT:

List of values of self at the eval_pts.

Todo

This method currently trivially calls the evaluation function repeatedly. If fast skew polynomial multiplication is available, an asymptotically faster method is possible using standard divide and conquer techniques and sage.rings.polynomial.skew_polynomial_ring.SkewPolynomialRing_general.minimal_vanishing_polynomial().

EXAMPLES:

sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x',Frob]
sage: a = x + t
sage: eval_pts = [1, t, t^2]
sage: c = a.multi_point_evaluation(eval_pts); c
[t + 1, 3*t^2 + 4*t + 4, 4*t]
sage: c == [ a(e) for e in eval_pts ]
True

number_of_terms()¶

Return the number of 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

operator_eval(eval_pt)¶

Evaluate self at eval_pt by the operator evaluation method.

INPUT:

eval_pt – element of the base ring of self

OUTPUT:

The value of the polynomial at the point specified by the argument.

EXAMPLES:

sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: T.<x> = k['x',Frob]
sage: a = 3*t^2*x^2 + (t + 1)*x + 2
sage: a(t) #indirect test
2*t^2 + 2*t + 3
sage: a.operator_eval(t)
2*t^2 + 2*t + 3

Evaluation points outside the base ring is usually not possible due to the twist map:

sage: R.<t> = QQ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: a = t*x + 1
sage: a.operator_eval(1/t)
Traceback (most recent call last):
...
TypeError: 1/t fails to convert into the map's domain Univariate Polynomial Ring in t over Rational Field, but a `pushforward` method is not properly implemented

padded_list(n=None)¶

Return list of coefficients of self up to (but not including) degree \(n\).

Includes \(0\).

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 divides other on the right.

INPUT:

other – a skew polynomial in the same ring as self

OUTPUT:

Return True or False.

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 and other.

INPUT:

other – a skew 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 a skew polynomial \(g\) with the following property: any skew polynomial is divisible on the right by \(g\) iff it is divisible on the right by 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: 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 and other.

INPUT:

other – a skew 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 a skew polynomial \(g\) with the following property: any skew polynomial divides \(g\) on the left iff it divides both self and other on the left. 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 twist map on this field is bijective.

EXAMPLES:

sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x',Frob]
sage: a = (x + t) * (x + t^2)
sage: b = 2 * (x + t) * (x^2 + t + 1)
sage: c = a.right_lcm(b); c
x^4 + (2*t^2 + t + 2)*x^3 + (3*t^2 + 4*t + 1)*x^2 + (3*t^2 + 4*t + 1)*x + t^2 + 4
sage: c.is_left_divisible_by(a)
True
sage: c.is_left_divisible_by(b)
True
sage: a.degree() + b.degree() == c.degree() + a.left_gcd(b).degree()
True

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

sage: a.right_lcm(b,monic=False)
2*t*x^4 + (3*t + 1)*x^3 + (4*t^2 + 4*t + 3)*x^2
 + (3*t^2 + 4*t + 2)*x + 3*t^2 + 2*t + 3

The base ring needs to be a field:

sage: R.<t> = QQ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: a = (x + t) * (x + t^2)
sage: b = 2 * (x + t) * (x^2 + t + 1)
sage: a.right_lcm(b)
Traceback (most recent call last):
...
TypeError: the base ring must be a field

And the twist map needs to be bijective:

sage: FR = R.fraction_field()
sage: f = FR.hom([FR(t)^2])
sage: S.<x> = FR['x',f]
sage: a = (x + t) * (x + t^2)
sage: b = 2 * (x + t) * (x^2 + t + 1)
sage: a.right_lcm(b)
Traceback (most recent call last):
...
NotImplementedError: inversion of the twist map Ring endomorphism of Fraction Field of Univariate Polynomial Ring in t over Rational Field
    Defn: t |--> t^2

right_mod(other)¶

Return the remainder of right division of self 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

right_monic()¶

Return the unique monic skew polynomial \(m\) which divides self on the right and has the same degree.

Given a skew polynomial \(p\) of degree \(n\), its left monic is given by \(m = (1/k) * p\), where \(k\) is the leading coefficient of \(p\), i.e. by the appropriate scalar multiplication on the left.

EXAMPLES:

sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x',Frob]
sage: a = (3*t^2 + 3*t + 2)*x^3 + (2*t^2 + 3)*x^2 + (4*t^2 + t + 4)*x + 2*t^2 + 2
sage: b = a.right_monic(); b
x^3 + (2*t^2 + 3*t + 4)*x^2 + (3*t^2 + 4*t + 1)*x + 2*t^2 + 4*t + 3

Check list:

sage: b.degree() == a.degree()
True
sage: b.is_right_divisible_by(a)
True
sage: a == a.leading_coefficient() * b
True

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

sage: a.is_left_divisible_by(b)
False

This function does not work if the leading coefficient is not a unit:

sage: R.<t> = QQ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: a = t*x
sage: a.right_monic()
Traceback (most recent call last):
...
NotImplementedError: the leading coefficient is not a unit

right_xgcd(other, monic=True)¶

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

If \(a\) is self and \(b\) is other, then there are skew polynomials \(u\) and \(v\) such that \(g = u a + v b\), where \(g\) is the right gcd of \(a\) and \(b\). This method returns \((g, u, v)\).

INPUT:

other – a skew polynomial in the same ring 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 a skew polynomial \(g\) with the following property: any skew polynomial is divisible on the right by \(g\) iff it is divisible on the right by both self and other. If monic is True, \(g\) is in addition monic. (With this extra condition, it is uniquely determined.)
Two skew polynomials \(u\) and \(v\) such that:

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

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

Note

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

EXAMPLES:

sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x',Frob]
sage: a = (x^2 + t*x + 1) * (x + t)
sage: b = 2 * (x^3 + (t+1)*x^2 + t^2) * (x + t)
sage: g,u,v = a.right_xgcd(b); g
x + t
sage: u*a + v*b == g
True

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

sage: g,u,v = a.right_xgcd(b,monic=False); g
(4*t^2 + 4*t + 1)*x + 4*t^2 + 4*t + 3
sage: u*a + v*b == g
True

The base ring must be a field:

sage: R.<t> = QQ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: a = (x^2 + t*x + 1) * (x + t)
sage: b = 2 * (x^3 + (t+1)*x^2 + t^2) * (x + t)
sage: a.right_xgcd(b)
Traceback (most recent call last):
...
TypeError: the base ring must be a field

shift(n)¶

Return self multiplied on the right by the power \(x^n\).

If \(n\) is negative, terms below \(x^n\) will be discarded.

EXAMPLES:

sage: R.<t> = QQ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: a = x^5 + t^4*x^4 + t^2*x^2 + t^10
sage: a.shift(0)
x^5 + t^4*x^4 + t^2*x^2 + t^10
sage: a.shift(-1)
x^4 + t^4*x^3 + t^2*x
sage: a.shift(-5)
1
sage: a.shift(2)
x^7 + t^4*x^6 + t^2*x^4 + t^10*x^2

One can also use the infix shift operator:

sage: a >> 2
x^3 + t^4*x^2 + t^2
sage: a << 2
x^7 + t^4*x^6 + t^2*x^4 + t^10*x^2

square()¶

Return the square of self.

EXAMPLES:

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

variable_name()¶

Return the string name of the variable used in self.

EXAMPLES:

sage: R.<t> = QQ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: a = x + t
sage: a.variable_name()
'x'

class sage.rings.polynomial.skew_polynomial_element.SkewPolynomialBaseringInjection¶

Bases: sage.categories.morphism.Morphism

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

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

Univariate Skew Polynomials¶

Previous topic

Next topic

This Page