Univariate dense skew polynomials over a field with a finite order automorphism

AUTHOR:

- Xavier Caruso (2012-06-29): initial version

  • Arpit Merchant (2016-08-04): improved docstrings, fixed doctests and refactored classes and methods

class sage.rings.polynomial.skew_polynomial_finite_order.SkewPolynomial_finite_order_dense[source]

Bases: SkewPolynomial_generic_dense

This method constructs a generic dense skew polynomial over a field equipped with an automorphism of finite order.

INPUT:

  • parent – parent of self

  • x – list of coefficients from which self can be constructed

  • check – flag variable to normalize the polynomial

  • construct – boolean (default: False)

bound()[source]

Return a bound of this skew polynomial (i.e. a multiple of this skew polynomial lying in the center).

Note

Since \(b\) is central, it divides a skew polynomial on the left iff it divides it on the right

ALGORITHM:

  1. Sage first checks whether self is itself in the center. It if is, it returns self

  2. If an optimal bound was previously computed and cached, Sage returns it

  3. Otherwise, Sage returns the reduced norm of self

As a consequence, the output of this function may depend on previous computations (an example is given below).

EXAMPLES:

sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x', Frob]
sage: Z = S.center(); Z
Univariate Polynomial Ring in z over Finite Field of size 5

sage: a = x^2 + (4*t + 2)*x + 4*t^2 + 3
sage: b = a.bound(); b
z^2 + z + 4

>>> from sage.all import *
>>> 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)
>>> Z = S.center(); Z
Univariate Polynomial Ring in z over Finite Field of size 5

>>> a = x**Integer(2) + (Integer(4)*t + Integer(2))*x + Integer(4)*t**Integer(2) + Integer(3)
>>> b = a.bound(); b
z^2 + z + 4

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

We observe that the bound is explicitly given as an element of the center (which is a univariate polynomial ring in the variable \(z\)). We can use conversion to send it in the skew polynomial ring:

sage: S(b)
x^6 + x^3 + 4

>>> from sage.all import *
>>> S(b)
x^6 + x^3 + 4

S(b)

We check that \(b\) is divisible by \(a\):

sage: S(b).is_right_divisible_by(a)
True
sage: S(b).is_left_divisible_by(a)
True

>>> from sage.all import *
>>> S(b).is_right_divisible_by(a)
True
>>> S(b).is_left_divisible_by(a)
True

S(b).is_right_divisible_by(a)
S(b).is_left_divisible_by(a)

Actually, \(b\) is the reduced norm of \(a\):

sage: b == a.reduced_norm()
True

>>> from sage.all import *
>>> b == a.reduced_norm()
True

b == a.reduced_norm()

Now, we compute the optimal bound of \(a\) and see that it affects the behaviour of bound():

sage: a.optimal_bound()
z + 3
sage: a.bound()
z + 3

>>> from sage.all import *
>>> a.optimal_bound()
z + 3
>>> a.bound()
z + 3

a.optimal_bound()
a.bound()
is_central()[source]

Return True if this skew polynomial lies in the center.

EXAMPLES:

sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x', Frob]

sage: x.is_central()
False
sage: (t*x^3).is_central()
False
sage: (x^6 + x^3).is_central()
True

>>> from sage.all import *
>>> 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)

>>> x.is_central()
False
>>> (t*x**Integer(3)).is_central()
False
>>> (x**Integer(6) + x**Integer(3)).is_central()
True

k.<t> = GF(5^3)
Frob = k.frobenius_endomorphism()
S.<x> = k['x', Frob]
x.is_central()
(t*x^3).is_central()
(x^6 + x^3).is_central()
optimal_bound()[source]

Return the optimal bound of this skew polynomial (i.e. the monic multiple of this skew polynomial of minimal degree lying in the center).

Note

The result is cached.

EXAMPLES:

sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x', Frob]
sage: Z = S.center(); Z
Univariate Polynomial Ring in z over Finite Field of size 5

sage: a = x^2 + (4*t + 2)*x + 4*t^2 + 3
sage: b = a.optimal_bound(); b
z + 3

>>> from sage.all import *
>>> 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)
>>> Z = S.center(); Z
Univariate Polynomial Ring in z over Finite Field of size 5

>>> a = x**Integer(2) + (Integer(4)*t + Integer(2))*x + Integer(4)*t**Integer(2) + Integer(3)
>>> b = a.optimal_bound(); b
z + 3

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

We observe that the bound is explicitly given as an element of the center (which is a univariate polynomial ring in the variable \(z\)). We can use conversion to send it in the skew polynomial ring:

sage: S(b)
x^3 + 3

>>> from sage.all import *
>>> S(b)
x^3 + 3

S(b)

We check that \(b\) is divisible by \(a\):

sage: S(b).is_right_divisible_by(a)
True
sage: S(b).is_left_divisible_by(a)
True

>>> from sage.all import *
>>> S(b).is_right_divisible_by(a)
True
>>> S(b).is_left_divisible_by(a)
True

S(b).is_right_divisible_by(a)
S(b).is_left_divisible_by(a)
reduced_charpoly(var=None)[source]

Return the reduced characteristic polynomial of this skew polynomial.

INPUT:

  • var – string, a pair of strings or None (default: None); the variable names used for the characteristic polynomial and the center

Note

The result is cached.

EXAMPLES:

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

>>> from sage.all import *
>>> k = GF(Integer(5)**Integer(3), names=('t',)); (t,) = k._first_ngens(1)
>>> Frob = k.frobenius_endomorphism()
>>> S = k['u', Frob]; (u,) = S._first_ngens(1)
>>> a = u**Integer(3) + (Integer(2)*t**Integer(2) + Integer(3))*u**Integer(2) + (Integer(4)*t**Integer(2) + t + Integer(4))*u + Integer(2)*t**Integer(2) + Integer(2)
>>> chi = a.reduced_charpoly()
>>> chi
x^3 + (2*z + 1)*x^2 + (3*z^2 + 4*z)*x + 4*z^3 + z^2 + 1

k.<t> = GF(5^3)
Frob = k.frobenius_endomorphism()
S.<u> = k['u', Frob]
a = u^3 + (2*t^2 + 3)*u^2 + (4*t^2 + t + 4)*u + 2*t^2 + 2
chi = a.reduced_charpoly()
chi

The reduced characteristic polynomial has coefficients in the center of \(S\), which is itself a univariate polynomial ring in the variable \(z = u^3\) over \(\GF{5}\). Hence it appears as a bivariate polynomial:

sage: chi.parent()
Univariate Polynomial Ring in x over Univariate Polynomial Ring in z over Finite Field of size 5

>>> from sage.all import *
>>> chi.parent()
Univariate Polynomial Ring in x over Univariate Polynomial Ring in z over Finite Field of size 5

chi.parent()

The constant coefficient of the reduced characteristic polynomial is the reduced norm, up to a sign:

sage: chi[0] == -a.reduced_norm()
True

>>> from sage.all import *
>>> chi[Integer(0)] == -a.reduced_norm()
True

chi[0] == -a.reduced_norm()

Its coefficient of degree \(\deg(a) - 1\) is the opposite of the reduced trace:

sage: chi[2] == -a.reduced_trace()
True

>>> from sage.all import *
>>> chi[Integer(2)] == -a.reduced_trace()
True

chi[2] == -a.reduced_trace()

By default, the name of the variable of the reduced characteristic polynomial is x and the name of central variable is usually z (see center() for more details about this). The user can speciify different names if desired:

sage: a.reduced_charpoly(var='T')  # variable name for the caracteristic polynomial
T^3 + (2*z + 1)*T^2 + (3*z^2 + 4*z)*T + 4*z^3 + z^2 + 1

sage: a.reduced_charpoly(var=('T', 'c'))
T^3 + (2*c + 1)*T^2 + (3*c^2 + 4*c)*T + 4*c^3 + c^2 + 1

>>> from sage.all import *
>>> a.reduced_charpoly(var='T')  # variable name for the caracteristic polynomial
T^3 + (2*z + 1)*T^2 + (3*z^2 + 4*z)*T + 4*z^3 + z^2 + 1

>>> a.reduced_charpoly(var=('T', 'c'))
T^3 + (2*c + 1)*T^2 + (3*c^2 + 4*c)*T + 4*c^3 + c^2 + 1

a.reduced_charpoly(var='T')  # variable name for the caracteristic polynomial
a.reduced_charpoly(var=('T', 'c'))

See also

reduced_trace(), reduced_norm()

reduced_norm(var=None)[source]

Return the reduced norm of this skew polynomial.

INPUT:

  • var – string or False or None (default: None); the variable name. If False, return the list of coefficients.

Note

The result is cached.

EXAMPLES:

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

>>> from sage.all import *
>>> 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(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)
>>> N = a.reduced_norm(); N
z^3 + 4*z^2 + 4

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

The reduced norm lies in the center of \(S\), which is a univariate polynomial ring in the variable \(z = x^3\) over \(\GF{5}\):

sage: N.parent()
Univariate Polynomial Ring in z over Finite Field of size 5
sage: N.parent() is S.center()
True

>>> from sage.all import *
>>> N.parent()
Univariate Polynomial Ring in z over Finite Field of size 5
>>> N.parent() is S.center()
True

N.parent()
N.parent() is S.center()

We can use explicit conversion to view N as a skew polynomial:

sage: S(N)
x^9 + 4*x^6 + 4

>>> from sage.all import *
>>> S(N)
x^9 + 4*x^6 + 4

S(N)

By default, the name of the central variable is usually z (see center() for more details about this). However, the user can specify a different variable name if desired:

sage: a.reduced_norm(var='u')
u^3 + 4*u^2 + 4

>>> from sage.all import *
>>> a.reduced_norm(var='u')
u^3 + 4*u^2 + 4

a.reduced_norm(var='u')

When passing in var=False, a tuple of coefficients (instead of an actual polynomial) is returned:

sage: a.reduced_norm(var=False)
(4, 0, 4, 1)

>>> from sage.all import *
>>> a.reduced_norm(var=False)
(4, 0, 4, 1)

a.reduced_norm(var=False)

ALGORITHM:

If \(r\) (= the order of the twist map) is small compared to \(d\) (= the degree of this skew polynomial), the reduced norm is computed as the determinant of the multiplication by \(P\) (= this skew polynomial) acting on \(K[X,\sigma]\) (= the underlying skew ring) viewed as a free module of rank \(r\) over \(K[X^r]\).

Otherwise, the reduced norm is computed as the characteristic polynomial of the left multiplication by \(X\) on the quotient \(K[X,\sigma] / K[X,\sigma] P\) (which is a \(K\)-vector space of dimension \(d\)).

See also

reduced_trace(), reduced_charpoly()

reduced_trace(var=None)[source]

Return the reduced trace of this skew polynomial.

INPUT:

  • var – string or False or None (default: None); the variable name. If False, return the list of coefficients.

EXAMPLES:

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

>>> from sage.all import *
>>> 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(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)
>>> tr = a.reduced_trace(); tr
3*z + 4

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

The reduced trace lies in the center of \(S\), which is a univariate polynomial ring in the variable \(z = x^3\) over \(\GF{5}\):

sage: tr.parent()
Univariate Polynomial Ring in z over Finite Field of size 5
sage: tr.parent() is S.center()
True

>>> from sage.all import *
>>> tr.parent()
Univariate Polynomial Ring in z over Finite Field of size 5
>>> tr.parent() is S.center()
True

tr.parent()
tr.parent() is S.center()

We can use explicit conversion to view tr as a skew polynomial:

sage: S(tr)
3*x^3 + 4

>>> from sage.all import *
>>> S(tr)
3*x^3 + 4

S(tr)

By default, the name of the central variable is usually z (see center() for more details about this). However, the user can specify a different variable name if desired:

sage: a.reduced_trace(var='u')
3*u + 4

>>> from sage.all import *
>>> a.reduced_trace(var='u')
3*u + 4

a.reduced_trace(var='u')

When passing in var=False, a tuple of coefficients (instead of an actual polynomial) is returned:

sage: a.reduced_trace(var=False)
(4, 3)

>>> from sage.all import *
>>> a.reduced_trace(var=False)
(4, 3)

a.reduced_trace(var=False)

See also

reduced_norm(), reduced_charpoly()