Univariate skew polynomials¶

This module provides the SkewPolynomial. In the class hierarchy in Sage, the locution Skew Polynomial is used for a Ore polynomial without twisting derivation.

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.SkewPolynomial_generic_dense[source]¶

Bases: OrePolynomial_generic_dense

Generic implementation of dense skew polynomial supporting any valid base ring and twisting morphism.

conjugate(n)[source]¶

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 twisting morphism to each of its coefficients.

INPUT:

n – integer; the power of conjugation

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> K = R.fraction_field()
>>> sigma = K.hom([Integer(1) + Integer(1)/t])
>>> S = K['x',sigma]; (x,) = S._first_ngens(1)
>>> a = t*x**Integer(3) + (t**Integer(2) + Integer(1))*x**Integer(2) + Integer(2)*t
>>> b = a.conjugate(Integer(2)); b
((2*t + 1)/(t + 1))*x^3 + ((5*t^2 + 6*t + 2)/(t^2 + 2*t + 1))*x^2 + (4*t + 2)/(t + 1)
>>> x**Integer(2)*a == b*x**Integer(2)
True

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

Sage

sage: b = a.conjugate(-1)
Traceback (most recent call last):
...
NotImplementedError: inverse not implemented for morphisms of
Fraction Field of Univariate Polynomial Ring in t over Rational Field

Python

>>> from sage.all import *
>>> b = a.conjugate(-Integer(1))
Traceback (most recent call last):
...
NotImplementedError: inverse not implemented for morphisms of
Fraction Field of Univariate Polynomial Ring in t over Rational Field

Here is a working example:

Sage

sage: # needs sage.rings.finite_rings
sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: T.<y> = k['y',Frob]
sage: u = T.random_element()
sage: v = u.conjugate(-1)
sage: u*y == y*v
True

Python

>>> 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()
>>> T = k['y',Frob]; (y,) = T._first_ngens(1)
>>> u = T.random_element()
>>> v = u.conjugate(-Integer(1))
>>> u*y == y*v
True

left_power_mod(exp, modulus)[source]¶

Return the remainder of self**exp in the left euclidean division by modulus.

INPUT:

exp – an Integer
modulus – a skew polynomial in the same ring as self

OUTPUT:

Remainder of self**exp in the left euclidean division by modulus.

REMARK:

The quotient of the underlying skew polynomial ring by the principal ideal generated by modulus is in general not a ring.

As a consequence, Sage first computes exactly self**exp and then reduce it modulo modulus.

EXAMPLES:

Sage

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
sage: modulus = x^3 + t*x^2 + (t+3)*x - 2
sage: a.left_power_mod(100,modulus)
(4*t^2 + t + 1)*x^2 + (t^2 + 4*t + 1)*x + 3*t^2 + 3*t

Python

>>> 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
>>> modulus = x**Integer(3) + t*x**Integer(2) + (t+Integer(3))*x - Integer(2)
>>> a.left_power_mod(Integer(100),modulus)
(4*t^2 + t + 1)*x^2 + (t^2 + 4*t + 1)*x + 3*t^2 + 3*t

multi_point_evaluation(eval_pts)[source]¶

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 minimal_vanishing_polynomial().

EXAMPLES:

Sage

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

Python

>>> 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
>>> eval_pts = [Integer(1), t, t**Integer(2)]
>>> c = a.multi_point_evaluation(eval_pts); c
[t + 1, 3*t^2 + 4*t + 4, 4*t]
>>> c == [ a(e) for e in eval_pts ]
True

operator_eval(eval_pt)[source]¶

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

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

Python

>>> 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()
>>> T = k['x',Frob]; (x,) = T._first_ngens(1)
>>> a = Integer(3)*t**Integer(2)*x**Integer(2) + (t + Integer(1))*x + Integer(2)
>>> a(t) #indirect test
2*t^2 + 2*t + 3
>>> a.operator_eval(t)
2*t^2 + 2*t + 3

Evaluation points outside the base ring is usually not possible due to the twisting morphism:

Sage

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

Python

>>> 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 = t*x + Integer(1)
>>> a.operator_eval(Integer(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

right_power_mod(exp, modulus)[source]¶

Return the remainder of self**exp in the right euclidean division by modulus.

INPUT:

exp – integer
modulus – a skew polynomial in the same ring as self

OUTPUT:

Remainder of self**exp in the right euclidean division by modulus.

REMARK:

The quotient of the underlying skew polynomial ring by the principal ideal generated by modulus is in general not a ring.

As a consequence, Sage first computes exactly self**exp and then reduce it modulo modulus.

EXAMPLES:

Sage

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
sage: b = a^5  # indirect doctest
sage: b
x^5 + (2*t^2 + 4)*x^4 + (t^2 + 2)*x^3 + 2*x^2 + (4*t^2 + 2)*x + 2*t^2 + 4*t + 4
sage: b == a * a * a * a * a
True
sage: modulus = x^3 + t*x^2 + (t+3)*x - 2
sage: br = a.right_power_mod(5, modulus); br
(t + 1)*x^2 + (2*t^2 + t + 1)*x + 2*t^2 + 4*t + 2
sage: br == b % modulus
True
sage: a.right_power_mod(100, modulus)
(2*t^2 + 3)*x^2 + (t^2 + 4*t + 2)*x + t^2 + 2*t + 1

Python

>>> 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
>>> b = a**Integer(5)  # indirect doctest
>>> b
x^5 + (2*t^2 + 4)*x^4 + (t^2 + 2)*x^3 + 2*x^2 + (4*t^2 + 2)*x + 2*t^2 + 4*t + 4
>>> b == a * a * a * a * a
True
>>> modulus = x**Integer(3) + t*x**Integer(2) + (t+Integer(3))*x - Integer(2)
>>> br = a.right_power_mod(Integer(5), modulus); br
(t + 1)*x^2 + (2*t^2 + t + 1)*x + 2*t^2 + 4*t + 2
>>> br == b % modulus
True
>>> a.right_power_mod(Integer(100), modulus)
(2*t^2 + 3)*x^2 + (t^2 + 4*t + 2)*x + t^2 + 2*t + 1

Negative exponents are supported:

sage: # needs sage.rings.finite_rings sage: a^(-5) (x^5 + (2*t^2 + 4)*x^4 + (t^2 + 2)*x^3 + 2*x^2 + (4*t^2 + 2)*x + 2*t^2 + 4*t + 4)^(-1) sage: b * a^(-5) 1

However, they cannot be combined with modulus:

Sage

sage: a.right_power_mod(-10, modulus)                                       # needs sage.rings.finite_rings
Traceback (most recent call last):
...
ValueError: modulus cannot be combined with negative exponent

Python

>>> from sage.all import *
>>> a.right_power_mod(-Integer(10), modulus)                                       # needs sage.rings.finite_rings
Traceback (most recent call last):
...
ValueError: modulus cannot be combined with negative exponent