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 [GMN13], [Bau16a], [Bau14]

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.

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

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:

1.

A sequence of OM representations for the p-adic irreducible factors of f.

2.

A sequence of intervals with the position of the prime ideals in each disconnected tree of OM representations.

3.

The p-index of f.

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

> 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

> 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

> 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