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)                                               # needs sage.rings.number_field
3-adic valuation
sage: QQ.valuation(5)
5-adic valuation
sage: Zp(7).valuation()
7-adic valuation

>>> from sage.all import *
>>> ZZ.valuation(Integer(2))
2-adic valuation
>>> GaussianIntegers().valuation(Integer(3))                                               # needs sage.rings.number_field
3-adic valuation
>>> QQ.valuation(Integer(5))
5-adic valuation
>>> Zp(Integer(7)).valuation()
7-adic valuation


sage: # needs sage.rings.function_field
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

>>> from sage.all import *
>>> # needs sage.rings.function_field
>>> K = FunctionField(QQ, names=('x',)); (x,) = K._first_ngens(1)
>>> K.valuation(x)
(x)-adic valuation
>>> K.valuation(x**Integer(2) + Integer(1))
(x^2 + 1)-adic valuation
>>> K.valuation(Integer(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 ]

>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> v = QQ.valuation(Integer(2))
>>> w = GaussValuation(R, v)
>>> w.augmentation(x, Integer(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 ]

>>> from sage.all import *
>>> w.augmentation(x, infinity)
[ Gauss valuation induced by 2-adic valuation, v(x) = +Infinity ]
class sage.rings.valuation.valuation.DiscretePseudoValuation(parent)[source]

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

>>> from sage.all import *
>>> v = ZZ.valuation(Integer(2)); v  # indirect doctest
2-adic valuation
is_equivalent(f, g)[source]

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

>>> from sage.all import *
>>> v = QQ.valuation(Integer(2))
>>> v.is_equivalent(Integer(2), Integer(1))
False
>>> v.is_equivalent(Integer(2), -Integer(2))
True
>>> v.is_equivalent(Integer(2), Integer(0))
False
>>> v.is_equivalent(Integer(0), Integer(0))
True
class sage.rings.valuation.valuation.DiscreteValuation(parent)[source]

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 ]

>>> from sage.all import *
>>> v = QQ.valuation(Integer(2))
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> v = GaussValuation(R, v)
>>> w = v.augmentation(x, Integer(1337)); w  # indirect doctest
[ Gauss valuation induced by 2-adic valuation, v(x) = 1337 ]
is_discrete_valuation()[source]

Return whether this valuation is a discrete valuation.

EXAMPLES:

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

>>> from sage.all import *
>>> v = valuations.TrivialValuation(ZZ)
>>> v.is_discrete_valuation()
True
mac_lane_approximant(G, valuation, approximants=None)[source]

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

>>> from sage.all import *
>>> v = QQ.valuation(Integer(2))
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> G = x**Integer(2) + Integer(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)                                          # needs sage.geometry.polyhedron sage.rings.padics
[ Gauss valuation induced by 2-adic valuation, v(x + 1) = 1/2 ]

>>> from sage.all import *
>>> w = GaussValuation(R, v).augmentation(x + Integer(1), Integer(1)/Integer(2))
>>> v.mac_lane_approximant(G, w)                                          # needs sage.geometry.polyhedron sage.rings.padics
[ 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)                                          # needs sage.geometry.polyhedron sage.rings.padics
[ Gauss valuation induced by 2-adic valuation, v(x + 1) = 1/2 ]

>>> from sage.all import *
>>> w = GaussValuation(R, v)
>>> v.mac_lane_approximant(G, w)                                          # needs sage.geometry.polyhedron sage.rings.padics
[ 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)                                          # needs sage.geometry.polyhedron sage.rings.padics
[ Gauss valuation induced by 2-adic valuation, v(x + 1) = 1/2 ]

>>> from sage.all import *
>>> w = GaussValuation(R, v).augmentation(x + Integer(1), Integer(1)/Integer(2)).augmentation(G, infinity)
>>> v.mac_lane_approximant(G, w)                                          # needs sage.geometry.polyhedron sage.rings.padics
[ 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

>>> from sage.all import *
>>> w = GaussValuation(R, v).augmentation(x, Integer(1)/Integer(2))
>>> 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)                                          # needs sage.geometry.polyhedron sage.rings.padics
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)                                          # needs sage.geometry.polyhedron sage.rings.padics
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)                                          # needs sage.geometry.polyhedron sage.rings.padics
[ 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)                                          # needs sage.geometry.polyhedron sage.rings.padics
[ Gauss valuation induced by 2-adic valuation, v(x + 1) = 1 ]

>>> from sage.all import *
>>> G = x**Integer(2) - Integer(1)
>>> w = GaussValuation(R, v)
>>> v.mac_lane_approximant(G, w)                                          # needs sage.geometry.polyhedron sage.rings.padics
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

>>> w = GaussValuation(R, v).augmentation(x + Integer(1), Integer(1))
>>> v.mac_lane_approximant(G, w)                                          # needs sage.geometry.polyhedron sage.rings.padics
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

>>> w = GaussValuation(R, v).augmentation(x + Integer(1), Integer(2))
>>> v.mac_lane_approximant(G, w)                                          # needs sage.geometry.polyhedron sage.rings.padics
[ Gauss valuation induced by 2-adic valuation, v(x + 1) = +Infinity ]

>>> w = GaussValuation(R, v).augmentation(x + Integer(3), Integer(2))
>>> v.mac_lane_approximant(G, w)                                          # needs sage.geometry.polyhedron sage.rings.padics
[ 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')[source]

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 – 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 – 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 – 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 – 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)                                      # needs sage.geometry.polyhedron
[[ Gauss valuation induced by 2-adic valuation, v(x + 1) = 1/2 ]]
sage: v.mac_lane_approximants(x^2 + 1, required_precision=infinity)         # needs sage.geometry.polyhedron
[[ 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 ]]

>>> from sage.all import *
>>> v = QQ.valuation(Integer(2))
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> v.mac_lane_approximants(x**Integer(2) + Integer(1))                                      # needs sage.geometry.polyhedron
[[ Gauss valuation induced by 2-adic valuation, v(x + 1) = 1/2 ]]
>>> v.mac_lane_approximants(x**Integer(2) + Integer(1), required_precision=infinity)         # needs sage.geometry.polyhedron
[[ Gauss valuation induced by 2-adic valuation, v(x + 1) = 1/2,
   v(x^2 + 1) = +Infinity ]]
>>> v.mac_lane_approximants(x**Integer(2) + x + Integer(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)                                      # needs sage.geometry.polyhedron sage.rings.padics
[[ Gauss valuation induced by 2-adic valuation, v(x + 1) = +Infinity ],
 [ Gauss valuation induced by 2-adic valuation, v(x + 1) = 1 ]]

>>> from sage.all import *
>>> v.mac_lane_approximants(x**Integer(2) - Integer(1))                                      # needs sage.geometry.polyhedron sage.rings.padics
[[ 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

>>> from sage.all import *
>>> v.mac_lane_approximants(x**Integer(2))
Traceback (most recent call last):
...
ValueError: G must be squarefree
montes_factorization(G, assume_squarefree=False, required_precision=None)[source]

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

INPUT:

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

  • assume_squarefree – 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: # needs sage.libs.ntl
sage: k = Qp(5,4)
sage: v = k.valuation()
sage: R.<x> = k[]
sage: G = x^2 + 1
sage: v.montes_factorization(G)                                             # needs sage.geometry.polyhedron
((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))

>>> from sage.all import *
>>> # needs sage.libs.ntl
>>> k = Qp(Integer(5),Integer(4))
>>> v = k.valuation()
>>> R = k['x']; (x,) = R._first_ngens(1)
>>> G = x**Integer(2) + Integer(1)
>>> v.montes_factorization(G)                                             # needs sage.geometry.polyhedron
((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)                                       # needs sage.geometry.polyhedron sage.rings.padics
(x - 1) * (x + 1) * (x^2 - x + 1) * (x^2 + x + 1)

sage: v.montes_factorization(x^7 - 1)       # not tested                    # needs sage.rings.padics

sage: v.montes_factorization(x^7 - 1, required_precision=5)                 # needs sage.geometry.polyhedron sage.rings.padics
(x - 1) * (x^3 - 5*x^2 - 6*x - 1) * (x^3 + 6*x^2 + 5*x - 1)

>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> v = QQ.valuation(Integer(2))
>>> v.montes_factorization(x**Integer(6) - Integer(1))                                       # needs sage.geometry.polyhedron sage.rings.padics
(x - 1) * (x + 1) * (x^2 - x + 1) * (x^2 + x + 1)

>>> v.montes_factorization(x**Integer(7) - Integer(1))       # not tested                    # needs sage.rings.padics

>>> v.montes_factorization(x**Integer(7) - Integer(1), required_precision=Integer(5))                 # needs sage.geometry.polyhedron sage.rings.padics
(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)[source]

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 ]

>>> from sage.all import *
>>> v = QQ.valuation(Integer(2))
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> v = GaussValuation(R, v)
>>> w = v.augmentation(x, infinity); w  # indirect doctest
[ Gauss valuation induced by 2-adic valuation, v(x) = +Infinity ]
is_discrete_valuation()[source]

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

>>> from sage.all import *
>>> v = QQ.valuation(Integer(2))
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> v = GaussValuation(R, v)
>>> v.is_discrete_valuation()
True
>>> w = v.augmentation(x, infinity)
>>> w.is_discrete_valuation()
False
class sage.rings.valuation.valuation.MacLaneApproximantNode(valuation, parent, ef, principal_part_bound, coefficients, valuations)[source]

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)[source]

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)

>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> v = GaussValuation(R, valuations.TrivialValuation(QQ)).augmentation(x, infinity)
>>> K = FunctionField(QQ, names=('x',)); (x,) = K._first_ngens(1)
>>> w = K.valuation(v)
is_negative_pseudo_valuation()[source]

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

EXAMPLES:

sage: R.<x> = QQ[]
sage: u = GaussValuation(R, valuations.TrivialValuation(QQ))
sage: v = u.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

>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> u = GaussValuation(R, valuations.TrivialValuation(QQ))
>>> v = u.augmentation(x, infinity)
>>> v.is_negative_pseudo_valuation()
False
>>> K = FunctionField(QQ, names=('x',)); (x,) = K._first_ngens(1)
>>> w = K.valuation(v)
>>> w.is_negative_pseudo_valuation()
True