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

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

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

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

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

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

b = a.conjugate(-1)

Here is a working example:

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

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

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

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

# needs sage.rings.finite_rings
k.<t> = GF(5^3)
Frob = k.frobenius_endomorphism()
S.<x> = k['x',Frob]
a = x + t
modulus = x^3 + t*x^2 + (t+3)*x - 2
a.left_power_mod(100,modulus)
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: # 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

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

# needs sage.rings.finite_rings
k.<t> = GF(5^3)
Frob = k.frobenius_endomorphism()
S.<x> = k['x',Frob]
a = x + t
eval_pts = [1, t, t^2]
c = a.multi_point_evaluation(eval_pts); c
c == [ a(e) for e in eval_pts ]
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: # 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

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

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

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

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

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

R.<t> = QQ[]
sigma = R.hom([t+1])
S.<x> = R['x',sigma]
a = t*x + 1
a.operator_eval(1/t)
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: # 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

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

# needs sage.rings.finite_rings
k.<t> = GF(5^3)
Frob = k.frobenius_endomorphism()
S.<x> = k['x',Frob]
a = x + t
b = a^5  # indirect doctest
b
b == a * a * a * a * a
modulus = x^3 + t*x^2 + (t+3)*x - 2
br = a.right_power_mod(5, modulus); br
br == b % modulus
a.right_power_mod(100, modulus)

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: a.right_power_mod(-10, modulus)                                       # needs sage.rings.finite_rings
Traceback (most recent call last):
...
ValueError: modulus cannot be combined with negative exponent

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

a.right_power_mod(-10, modulus)                                       # needs sage.rings.finite_rings