The Ring of Twisted Polynomials

The ring of twisted polynomials plays a core role in the analytic side of class field theory of global function fields. Twisted polynomials can be viewed as additive polynomials where the multiplication is the composition of two polynomials. Alternatively, they are the ring of polynomials in the Frobenius automorphism of the base field as indeterminate and multiplication defined in terms of application of the corresponding endomorphism. Thus Twisted polynomials have two natural polynomial representations:

- as (arbitrary) polynomials in \(F\), the Frobenius automorphism

- as additive polynomials, ie. as polynomials where the only terms are \(T^{q^i}\).

In Magma the first representation is used (as the degrees are lower), but the second can always be obtained by converting to a polynomial.

Since every endomorphism in positive characteristic can be represented by an additive polynomial (or an additive power series), this section can also be viewed as making the endomorphism ring accessible.

In Magma the ring of twisted polynomials is of type RngUPolTwst and individual elements are of type RngUPolTwstElt. Twisted polynomial rings can be created over any ring of characteristic \(p>0\). They are left euclidean and therefore left PIR.

Creation of Twisted Polynomial Rings

TwistedPolynomials(R): Rng -> RngUPolTwst

q: RngIntElt                    Default: false

Given a ring \(R\) of characteristic \(p>0\), create the ring of twisted polynomials over \(R\). If q is given it has to be a power of the characteristic \(p\), it defaults to \(q := p\). The multiplication in this ring \(R<F>\) is defined by \(rF = Fr^q\) for all \(r\in R\). Elements if \(R<F>\) are represented as polynomials in \(F\).

Operations with the Ring of Twisted Polynomials

One(R): RngUPolTwst -> RngUPolTwstElt

For a ring \(R\) of twisted polynomials return the polynomial representing \(1\).

Zero(R): RngUPolTwst -> RngUPolTwstElt

For a ring \(R\) of twisted polynomials return the polynomial representing \(0\).

R eq S: RngUPolTwst, RngUPolTwst -> BoolElt

For two rings of twisted polynomials \(R\) and \(S\) test if they are equal, that is if the underlying polynomial ring is considered equal by Magma. Generically that means to test if the base rings of \(R\) and \(S\) coincide.

BaseRing(R): RngUPolTwst -> Rng

The coefficient ring of the ring \(R\) of twisted polynomials.

R . i: RngUPolTwst, RngIntElt -> RngUPolTwstElt

For a ring of twisted polynomials \(R\) and an integer \(i\) which should be \(1\), return the transcendental element of \(R\).

Creation of Twisted Polynomials

Apart from creation from polynomials directly, twisted polynomial can also be created by specifying some finite \({\mathbb{F}}_q\)-vector space where the corresponding additive polynomial will have its roots.

AdditivePolynomialFromRoots(x, P): RngElt, PlcFunElt -> RngUPolTwstElt

InfBound: RngIntElt                    Default: 5
Map     : Map                          Default: id
Class   : DivFunElt                    Default: 0
Limit   : RngIntElt                    Default: Infinity()
Scale   : RngElt                       Default: false

An additive polynomial is characterized by the fact that its set of zeros forms an \({\mathbb{F}}_q\) vector space. Conversely, given an \({\mathbb{F}}_p\)-vector space \(M\) in \(R\) there is essentially one additive polynomial that has \(M\) as its set of roots. Given a place \(P\) and a ring element \(x\), this function computes the additive polynomial with roots \(L(\)InfBound\(P)\), evaluated at \(x\), ie. the module \(M\) is a Riemann-Roch space. By choosing \(x\) to be for example a transcendental element in a polynomial ring, the actual additive polynomial can be computed. If the parameter Map is given, the elements of the Riemann-Roch space are first mapped by this map before the polynomial is computed, thus allowing the creation of polynomials over the completion of a function field. If the parameter Limit is given, the polynomial is reduced modulo \(x^{\tt Limit}\). If Class is set to a non-zero divisor, instead of \(L(nP)\), the Riemann-Roch space \(L(nP+\)Class\()\) is used. If Scale is set to a ring element that is either compatible with elements of the Riemann-Roch space or with elements in the codomain of the map, the module is scaled as well, thus allowing for normalization.

Random(F, n): RngUPolTwst, RngIntElt -> RngUPolTwstElt

For \(F\) the ring of twisted polynomials over a finite ring (ie. a ring that supports the generation of random elements, this function will return a polynomial of degree \(n-1\) with randomly chosen coefficients.

Example: Twisted and Additive Polynomials (ex-f3126f)

Run in calculator (opens in a new tab)Copy input

> Fq<w> := GF(4);
> k<t> := RationalFunctionField(Fq);
> R := TwistedPolynomials(k:q := 4);
> R![1,1];
T_4 + 1
> R![w*t, 1];
T_4 + w*t
> $2 * $1;
T_4^2 + (w*t^4 + 1)*T_4 + w*t
> $2 * $3;
T_4^2 + (w*t + 1)*T_4 + w*t
> p := Places(k, 1)[2];
> a := AdditivePolynomialFromRoots(PolynomialRing(k).1, p
>          :InfBound := 2);
> a;
T_4^3 + ($.1^96 + $.1^84 + $.1^81 + $.1^72 + $.1^69 + $.1^66 + $.1^60
+ $.1^57 + $.1^54 + $.1^51 + $.1^48 + $.1^45 + $.1^42 + $.1^39 +
$.1^36 + $.1^30 + $.1^27 + $.1^24 + $.1^15 + $.1^12 + 1)/$.1^96*T_4^2
+ ($.1^96 + $.1^93 + $.1^90 + $.1^87 + $.1^72 + $.1^69 + $.1^66 +
$.1^63 + $.1^33 + $.1^30 + $.1^27 + $.1^24 + $.1^9 + $.1^6 + $.1^3 +
1)/$.1^108*T_4 + ($.1^90 + $.1^87 + $.1^84 + $.1^81 + $.1^78 + $.1^60
+ $.1^57 + $.1^54 + $.1^51 + $.1^48 + $.1^42 + $.1^39 + $.1^36 +
$.1^33 + $.1^30 + $.1^12 + $.1^9 + $.1^6 + $.1^3 + 1)/$.1^108
> R, mR := RiemannRochSpace(2*p);
> b := Polynomial(a);
> [ Evaluate(b, mR(x)) eq 0 : x in R];
[ true, true, true, true, true, true, true, true, true, true, true,
true, true, true, true, true, true, true, true, true, true, true,
true, true, true, true, true, true, true, true, true, true, true,
true, true, true, true, true, true, true, true, true, true, true,
true, true, true, true, true, true, true, true, true, true, true,
true, true, true, true, true, true, true, true, true ]
> AdditivePolynomialFromRoots(PolynomialRing(k).1, p:InfBound := 2,
>   Map := func<x|Expand(x, p:RelPrec := 100)>);
T_4^3 + ($.1^-96 + $.1^-84 + $.1^-81 + $.1^-72 + $.1^-69 + $.1^-66 +
$.1^-60 + $.1^-57 + $.1^-54 + $.1^-51 + $.1^-48 + $.1^-45 + $.1^-42 +
$.1^-39 + $.1^-36 + $.1^-30 + $.1^-27 + $.1^-24 + $.1^-15 + $.1^-12 +
1 + O($.1^4))*T_4^2 + ($.1^-108 + $.1^-105 + $.1^-102 + $.1^-99 +
$.1^-84 + $.1^-81 + $.1^-78 + $.1^-75 + $.1^-45 + $.1^-42 + $.1^-39 +
$.1^-36 + $.1^-21 + $.1^-18 + $.1^-15 + $.1^-12 + O($.1^-8))*T_4 +
$.1^-108 + $.1^-105 + $.1^-102 + $.1^-99 + $.1^-96 + $.1^-78 + $.1^-75
+ $.1^-72 + $.1^-69 + $.1^-66 + $.1^-60 + $.1^-57 + $.1^-54 + $.1^-51
+ $.1^-48 + $.1^-30 + $.1^-27 + $.1^-24 + $.1^-21 + $.1^-18 +
O($.1^-8)

Run in calculator (opens in a new tab)Copy input

Operations with Twisted Polynomials

A + B: RngIntElt, RngUPolTwstElt -> RngUPolTwstElt

A + B: RngUPolTwstElt, RngIntElt -> RngUPolTwstElt

A + B: RngUPolTwstElt, RngUPolTwstElt -> RngUPolTwstElt

A - B: RngIntElt, RngUPolTwstElt -> RngUPolTwstElt

A - B: RngUPolTwstElt, RngIntElt -> RngUPolTwstElt

A - B: RngUPolTwstElt, RngUPolTwstElt -> RngUPolTwstElt

- A: RngUPolTwstElt -> RngUPolTwstElt

A * B: RngUPolTwstElt, RngUPolTwstElt -> RngUPolTwstElt

A ^ n: RngUPolTwstElt, RngIntElt -> RngUPolTwstElt

A eq B: RngUPolTwstElt, RngUPolTwstElt -> BoolElt

IsZero(A): RngUPolTwstElt -> BoolElt

LeadingCoefficient(F): RngUPolTwstElt -> RngElt

For a twisted polynomial \(F\), return the leading coefficient as an element of the coefficient ring.

ConstantCoefficient(F): RngUPolTwstElt -> RngElt

For a twisted polynomial \(F\), return the constant coefficient as an element of the coefficient ring.

Degree(F): RngUPolTwstElt -> RngIntElt

For a twisted polynomial \(F\), return its degree. The degree of the underlying additive polynomial is \(q\) times the degree of the twisted polynomial.

Quotrem(F, G): RngUPolTwstElt, RngUPolTwstElt -> RngUPolTwstElt, RngUPolTwstElt

For twisted polynomials \(F\) and \(G\) in the same ring, perform a right division with remainder: This function computes \(Q\) and \(R\) such that \(F = Q*G+R\) and the degree of \(R\) is less than the degree of \(G\). In general, unless the coefficient ring is algebraically closed or perfect, there is no left quotient, so the ring of twisted polynomials is a left-PID, but no right-PID.

GCD(F, G): RngUPolTwstElt, RngUPolTwstElt -> RngUPolTwstElt

For twisted polynomials \(F\) and \(G\) in the same ring, compute the creates common right divisor of \(F\) and \(G\), ie a twisted polynomial \(H\) such that \(F = f_1 H\) and \(G = f_2 H\) for some twisted polynomials \(f_1\) and \(f_2\) and such that \(H\) is monic of maximal degree.

BaseRing(F): RngUPolTwstElt -> Rng

For a twisted polynomial \(F\), return the coefficient ring of \(F\), ie. the ring where all the coefficients of \(F\) are from.

Polynomial(G): RngUPolTwstElt -> RngUPolElt

For a twisted polynomial \(G\), return the corresponding additive polynomial by replacing the transcendental element \(F\) by \(T^q\) and in general \(F^i\) by \(T^{q^i}\) for \(i=0\), \(\ldots\), degree of \(G\).

SpecialEvaluate(F, x): RngUPolTwstElt, RngElt -> RngElt

For a twisted polynomial \(F\), return the result of the evaluation of the corresponding additive polynomial at the point \(x\).

SpecialEvaluate(F, x): RngUPolElt, Any -> RngElt

For a univariate polynomial \(F\), return the evaluation of \(F\) at \(x\). This function in particular is optimized for sparse polynomials (for example additive polynomials) and imprecise coefficients. In the general case, a call to Evaluate will be faster.

Eltseq(F): RngUPolTwstElt -> [RngElt]

For a twisted polynomial \(F\), return a sequence containing its coefficients.