Discrete valuations

This file defines abstract base classes for discrete (pseudo-)valuations.

AUTHORS:

• Julian Rüth (2013-03-16): initial version

EXAMPLES:

Discrete valuations can be created on a variety of rings:

sage: ZZ.valuation(2)
2-adic valuation
sage: GaussianIntegers().valuation(3)
3-adic valuation
sage: QQ.valuation(5)
5-adic valuation
sage: Zp(7).valuation()
7-adic valuation

sage: K.<x> = FunctionField(QQ)
sage: K.valuation(x)
(x)-adic valuation
sage: K.valuation(x^2 + 1)
(x^2 + 1)-adic valuation
sage: K.valuation(1/x)
Valuation at the infinite place

sage: R.<x> = QQ[]
sage: v = QQ.valuation(2)
sage: w = GaussValuation(R, v)
sage: w.augmentation(x, 3)
[ Gauss valuation induced by 2-adic valuation, v(x) = 3 ]

We can also define discrete pseudo-valuations, i.e., discrete valuations that send more than just zero to infinity:

sage: w.augmentation(x, infinity)
[ Gauss valuation induced by 2-adic valuation, v(x) = +Infinity ]

class sage.rings.valuation.valuation.DiscretePseudoValuation(parent)

Bases: Morphism

Abstract base class for discrete pseudo-valuations, i.e., discrete valuations which might send more that just zero to infinity.

INPUT:

• domain – an integral domain

EXAMPLES:

sage: v = ZZ.valuation(2); v # indirect doctest
2-adic valuation

is_equivalent(f, g)

Return whether f and g are equivalent.

EXAMPLES:

sage: v = QQ.valuation(2)
sage: v.is_equivalent(2, 1)
False
sage: v.is_equivalent(2, -2)
True
sage: v.is_equivalent(2, 0)
False
sage: v.is_equivalent(0, 0)
True

class sage.rings.valuation.valuation.DiscreteValuation(parent)

Bases: DiscretePseudoValuation

Abstract base class for discrete valuations.

EXAMPLES:

sage: v = QQ.valuation(2)
sage: R.<x> = QQ[]
sage: v = GaussValuation(R, v)
sage: w = v.augmentation(x, 1337); w # indirect doctest
[ Gauss valuation induced by 2-adic valuation, v(x) = 1337 ]

is_discrete_valuation()

Return whether this valuation is a discrete valuation.

EXAMPLES:

sage: v = valuations.TrivialValuation(ZZ)
sage: v.is_discrete_valuation()
True

mac_lane_approximant(G, valuation, approximants=None)

Return the approximant from mac_lane_approximants() for G which is approximated by or approximates valuation.

INPUT:

• G – a monic squarefree integral polynomial in a univariate polynomial ring over the domain of this valuation

• valuation – a valuation on the parent of G

• approximants – the output of mac_lane_approximants(). If not given, it is computed.

EXAMPLES:

sage: v = QQ.valuation(2)
sage: R.<x> = QQ[]
sage: G = x^2 + 1

We can select an approximant by approximating it:

sage: w = GaussValuation(R, v).augmentation(x + 1, 1/2)
sage: v.mac_lane_approximant(G, w)
[ Gauss valuation induced by 2-adic valuation, v(x + 1) = 1/2 ]

As long as this is the only matching approximant, the approximation can be very coarse:

sage: w = GaussValuation(R, v)
sage: v.mac_lane_approximant(G, w)
[ Gauss valuation induced by 2-adic valuation, v(x + 1) = 1/2 ]

Or it can be very specific:

sage: w = GaussValuation(R, v).augmentation(x + 1, 1/2).augmentation(G, infinity)
sage: v.mac_lane_approximant(G, w)
[ Gauss valuation induced by 2-adic valuation, v(x + 1) = 1/2 ]

But it must be an approximation of an approximant:

sage: w = GaussValuation(R, v).augmentation(x, 1/2)
sage: v.mac_lane_approximant(G, w)
Traceback (most recent call last):
...
ValueError: The valuation [ Gauss valuation induced by 2-adic valuation, v(x) = 1/2 ] is not an approximant for a valuation which extends 2-adic valuation with respect to x^2 + 1 since the valuation of x^2 + 1 does not increase in every step

The valuation must single out one approximant:

sage: G = x^2 - 1
sage: w = GaussValuation(R, v)
sage: v.mac_lane_approximant(G, w)
Traceback (most recent call last):
...
ValueError: The valuation Gauss valuation induced by 2-adic valuation does not approximate a unique extension of 2-adic valuation with respect to x^2 - 1

sage: w = GaussValuation(R, v).augmentation(x + 1, 1)
sage: v.mac_lane_approximant(G, w)
Traceback (most recent call last):
...
ValueError: The valuation [ Gauss valuation induced by 2-adic valuation, v(x + 1) = 1 ] does not approximate a unique extension of 2-adic valuation with respect to x^2 - 1

sage: w = GaussValuation(R, v).augmentation(x + 1, 2)
sage: v.mac_lane_approximant(G, w)
[ Gauss valuation induced by 2-adic valuation, v(x + 1) = +Infinity ]

sage: w = GaussValuation(R, v).augmentation(x + 3, 2)
sage: v.mac_lane_approximant(G, w)
[ Gauss valuation induced by 2-adic valuation, v(x + 1) = 1 ]

mac_lane_approximants(G, assume_squarefree=False, require_final_EF=True, required_precision=-1, require_incomparability=False, require_maximal_degree=False, algorithm='serial')

Return approximants on \(K[x]\) for the extensions of this valuation to \(L=K[x]/(G)\).

If \(G\) is an irreducible polynomial, then this corresponds to extensions of this valuation to the completion of \(L\).

INPUT:

• G – a monic squarefree integral polynomial in a univariate polynomial ring over the domain of this valuation

• assume_squarefree – a boolean (default: False), whether to assume that G is squarefree. If True, the squafreeness of G is not verified though it is necessary when require_final_EF is set for the algorithm to terminate.

• require_final_EF – a boolean (default: True); whether to require the returned key polynomials to be in one-to-one correspondance to the extensions of this valuation to L and require them to have the ramification index and residue degree of the valuations they correspond to.

• required_precision – a number or infinity (default: -1); whether to require the last key polynomial of the returned valuations to have at least that valuation.

• require_incomparability – a boolean (default: False); whether to require the returned valuations to be incomparable (with respect to the partial order on valuations defined by comparing them pointwise.)

• require_maximal_degree – a boolean (default: False); whether to require the last key polynomial of the returned valuation to have maximal degree. This is most relevant when using this algorithm to compute approximate factorizations of G, when set to True, the last key polynomial has the same degree as the corresponding factor.

• algorithm – one of "serial" or "parallel" (default: "serial"); whether or not to parallelize the algorithm

EXAMPLES:

sage: v = QQ.valuation(2)
sage: R.<x> = QQ[]
sage: v.mac_lane_approximants(x^2 + 1)
[[ Gauss valuation induced by 2-adic valuation, v(x + 1) = 1/2 ]]
sage: v.mac_lane_approximants(x^2 + 1, required_precision=infinity)
[[ Gauss valuation induced by 2-adic valuation, v(x + 1) = 1/2, v(x^2 + 1) = +Infinity ]]
sage: v.mac_lane_approximants(x^2 + x + 1)
[[ Gauss valuation induced by 2-adic valuation, v(x^2 + x + 1) = +Infinity ]]

Note that G does not need to be irreducible. Here, we detect a factor \(x + 1\) and an approximate factor \(x + 1\) (which is an approximation to \(x - 1\)):

sage: v.mac_lane_approximants(x^2 - 1)
[[ Gauss valuation induced by 2-adic valuation, v(x + 1) = +Infinity ],
 [ Gauss valuation induced by 2-adic valuation, v(x + 1) = 1 ]]

However, it needs to be squarefree:

sage: v.mac_lane_approximants(x^2)
Traceback (most recent call last):
...
ValueError: G must be squarefree

montes_factorization(G, assume_squarefree=False, required_precision=None)

Factor G over the completion of the domain of this valuation.

INPUT:

• G – a monic polynomial over the domain of this valuation

• assume_squarefree – a boolean (default: False), whether to assume G to be squarefree

• required_precision – a number or infinity (default: infinity); if infinity, the returned polynomials are actual factors of G, otherwise they are only factors with precision at least required_precision.

ALGORITHM:

We compute mac_lane_approximants() with required_precision. The key polynomials approximate factors of G. This can be very slow unless required_precision is set to zero. Single factor lifting could improve this significantly.

EXAMPLES:

sage: k=Qp(5,4)
sage: v = k.valuation()
sage: R.<x>=k[]
sage: G = x^2 + 1
sage: v.montes_factorization(G)
((1 + O(5^4))*x + 2 + 5 + 2*5^2 + 5^3 + O(5^4)) * ((1 + O(5^4))*x + 3 + 3*5 + 2*5^2 + 3*5^3 + O(5^4))

The computation might not terminate over incomplete fields (in particular because the factors can not be represented there):

sage: R.<x> = QQ[]
sage: v = QQ.valuation(2)
sage: v.montes_factorization(x^6 - 1)
(x - 1) * (x + 1) * (x^2 - x + 1) * (x^2 + x + 1)

sage: v.montes_factorization(x^7 - 1) # not tested, does not terminate

sage: v.montes_factorization(x^7 - 1, required_precision=5)
(x - 1) * (x^3 - 5*x^2 - 6*x - 1) * (x^3 + 6*x^2 + 5*x - 1)

REFERENCES:

The underlying algorithm is described in [Mac1936II] and thoroughly analyzed in [GMN2008].

class sage.rings.valuation.valuation.InfiniteDiscretePseudoValuation(parent)

Bases: DiscretePseudoValuation

Abstract base class for infinite discrete pseudo-valuations, i.e., discrete pseudo-valuations which are not discrete valuations.

EXAMPLES:

sage: v = QQ.valuation(2)
sage: R.<x> = QQ[]
sage: v = GaussValuation(R, v)
sage: w = v.augmentation(x, infinity); w # indirect doctest
[ Gauss valuation induced by 2-adic valuation, v(x) = +Infinity ]

is_discrete_valuation()

Return whether this valuation is a discrete valuation.

EXAMPLES:

sage: v = QQ.valuation(2)
sage: R.<x> = QQ[]
sage: v = GaussValuation(R, v)
sage: v.is_discrete_valuation()
True
sage: w = v.augmentation(x, infinity)
sage: w.is_discrete_valuation()
False

class sage.rings.valuation.valuation.MacLaneApproximantNode(valuation, parent, ef, principal_part_bound, coefficients, valuations)

Bases: object

A node in the tree computed by DiscreteValuation.mac_lane_approximants()

Leaves in the computation of the tree of approximants mac_lane_approximants(). Each vertex consists of a tuple (v,ef,p,coeffs,vals) where v is an approximant, i.e., a valuation, ef is a boolean, p is the parent of this vertex, and coeffs and vals are cached values. (Only v and ef are relevant, everything else are caches/debug info.) The boolean ef denotes whether v already has the final ramification index E and residue degree F of this approximant. An edge V – P represents the relation P.v \(≤\) V.v (pointwise on the polynomial ring K[x]) between the valuations.

class sage.rings.valuation.valuation.NegativeInfiniteDiscretePseudoValuation(parent)

Bases: InfiniteDiscretePseudoValuation

Abstract base class for pseudo-valuations which attain the value \(\infty\) and \(-\infty\), i.e., whose domain contains an element of valuation \(\infty\) and its inverse.

EXAMPLES:

sage: R.<x> = QQ[]
sage: v = GaussValuation(R, valuations.TrivialValuation(QQ)).augmentation(x, infinity)
sage: K.<x> = FunctionField(QQ)
sage: w = K.valuation(v)

is_negative_pseudo_valuation()

Return whether this valuation attains the value \(-\infty\).

EXAMPLES:

sage: R.<x> = QQ[]
sage: v = GaussValuation(R, valuations.TrivialValuation(QQ)).augmentation(x, infinity)
sage: v.is_negative_pseudo_valuation()
False
sage: K.<x> = FunctionField(QQ)
sage: w = K.valuation(v)
sage: w.is_negative_pseudo_valuation()
True