The Montes Algorithm

The Montes algorithm can be considered as a factorization algorithm for polynomials over local fields. For a defining polynomial \(f\) of a function field \(K\) and a prime polynomial \(p\) the Montes algorithm produces OM representations for all prime ideals of \(K\) lying of over \(p\), which parametrize the irreducible factors of \(f\) over the \(p\)-adic series. The OM representation for prime ideals leads to an OM presentation of fractional ideals. The basic algorithms are explained in [Bau14, Bau16a, GMN13] These OM representations allow the construction of ideals and divisors without the computation of a maximal order, which the construction of ideals of type RngFunOrdIdl require. The Montes algorithm can also be used to efficiently compute integral bases which can be use to construct maximal orders.

This section explains the use of the Montes Algorithm. For how to use the Montes algorithm to compute maximal orders of function fields see Section Construction of Orders of Algebraic Function Fields, and decomposition of primes in function fields see Sections Further Ideal Operations and Creation of Elements.

Montes(f, p): RngUPolElt, RngUPolElt -> SeqEnum, SeqEnum, RngIntElt

Field: BoolElt                    Default: false

Let \(f\) be a monic polynomial with polynomial coefficients and \(p\) be a prime polynomial. The Montes algorithm outputs the triple:

A sequence of OM representations for the \(p\)-adic irreducible factors of \(f\).
A sequence of intervals with the position of the prime ideals in each disconnected tree of OM representations.
The \(p\)-index of \(f\).

If the parameter Field is set to true the \(\psi\) polynomial at the last level of each type of each OM representation will be computed.

Example: Montes Algorithm for a Polynomial (ex-531fa2)

Run in calculator (opens in a new tab)

Here is an example of how to use it:

> k := GF(13);
> A<t> := PolynomialRing(k);
> Ax<x> := PolynomialRing(A);
> f := x^5 + (t^2 + 2*t + 1)*x^4 + (t^4 + 4*t^3 + 6*t^2 + 4*t + 1)*x^3 +
>      (t^3 + 3*t^2 + 3*t + 1)*x^2 + (t^4 + 4*t^3 + 6*t^2 + 4*t + 1)*x + t;
> p := t;
> Montes(f,p);
[
    ,

]
[
    [ 1 ],
    [ 2 ]
]
0

Run in calculator (opens in a new tab)

The Montes algorithm can also be called for a function field \(K\) if it is defined by a monic polynomial with polynomial coefficients.

Montes(K, p): FldArith, RngElt

The Montes algorithm is applied to the defining polynomial of the function field \(K\) at the prime \(p\).

A sequence of OM representations for the prime ideals of \(K\) is stored in K`PrimeIdeals[p].
The \(p\)-adic valuation of the index \([{\mathbb{Z}}_K:{\mathbb{Z}}[\theta]]\) is stored in K`LocalIndex[p]

Example: Montes Algorithm for a Function Field (ex-bec397)

Run in calculator (opens in a new tab)

Here’s an example of how to use it for a field :

> k := GF(13);
> A<t> := PolynomialRing(k);
> Ax<x> := PolynomialRing(A);
> f := x^5 + (t^2 + 2*t + 1)*x^4 + (t^4 + 4*t^3 + 6*t^2 + 4*t + 1)*x^3 +
>     (t^3 + 3*t^2 + 3*t + 1)*x^2 + (t^4 + 4*t^3 + 6*t^2 + 4*t + 1)*x + t;
> L := FunctionField(f);
> p := t+1;
> Montes(L,p);
> L`PrimeIdeals[p];
[
    OM prime ideal over t + 1
    of Algebraic function field defined over Univariate rational function field
    over GF(13) by
    x^5 + (t^2 + 2*t + 1)*x^4 + (t^4 + 4*t^3 + 6*t^2 + 4*t + 1)*x^3 + (t^3 +
    3*t^2 + 3*t + 1)*x^2 + (t^4 + 4*t^3 + 6*t^2 + 4*t + 1)*x + t
    having residual degree   1
    and ramification index   1
    Last phi polynomial is x + 12,
    OM prime ideal over t + 1
    of Algebraic function field defined over Univariate rational function field
    over GF(13) by
    x^5 + (t^2 + 2*t + 1)*x^4 + (t^4 + 4*t^3 + 6*t^2 + 4*t + 1)*x^3 + (t^3 +
    3*t^2 + 3*t + 1)*x^2 + (t^4 + 4*t^3 + 6*t^2 + 4*t + 1)*x + t
    having residual degree   4
    and ramification index   1
    Last phi polynomial is x^4 + x^3 + x^2 + x + 1
]
> L`LocalIndex[p];
0

Run in calculator (opens in a new tab)

SFL(P, s): OMIdl, RngIntElt: Perform the single factor lifting algorithm, [GNP12], on the prime ideal \(P\) in OM representation until the slope is at least \(s\).

Example: Refining an OM Prime Ideal Approximation (ex-8aed80)

Run in calculator (opens in a new tab)

> k := GF(13);
> A<t> := PolynomialRing(k);
> Ax<x> := PolynomialRing(A);
> f := x^5 + (t^2 + 2*t + 1)*x^4 + (t^4 + 4*t^3 + 6*t^2 + 4*t + 1)*x^3 + (t^3
> + 3*t^2 + 3*t + 1)*x^2 + (t^4 + 4*t^3 + 6*t^2 + 4*t + 1)*x + t;
> L := FunctionField(f);
> p := t+1;
> Montes(L,p);
> P := L`PrimeIdeals[p,1];
> P`Type[#P`Type]`slope;
1
> P`Type[#P`Type]`Phi; // the approximation
x + 12
> SFL(~P,10:update := true);
> P`Type[#P`Type]`slope;
10
> P`Type[#P`Type]`Phi; // the approximation
x + 6*t^9 + 2*t^8 + 11*t^7 + 3*t^6 + 2*t^5 + 2*t^4 + 11*t^3 + 3*t^2 + 12*t + 5

Run in calculator (opens in a new tab)

SetUseMontes(f): BoolElt
SetUseMontes(t, f): Cat, BoolElt: Set whether the Montes algorithm is to be used for maximal order and prime decomposition calculations. The type \(t\) can be FldFun. This setting can be overwritten by setting the Al parameter of the MaximalOrder and Decomposition intrinsics to "Montes".

GetUseMontes(t): Cat -> BoolElt: Return whether the Montes algorithm will be used by default for computations of maximal orders and decompositions for types inheriting from type \(t\), where \(t\) can be FldFun.

SetVerbose("Montes", v): MonStgElt, RngIntElt: Set the level for verbose printing for the Montes algorithm to be \(v \le 3\).

The Montes Algorithm#

The Montes Algorithm