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
andg
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()
forG
which is approximated by or approximatesvaluation
.INPUT:
G
– a monic squarefree integral polynomial in a univariate polynomial ring over the domain of this valuationvaluation
– a valuation on the parent ofG
approximants
– the output ofmac_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 valuationassume_squarefree
– a boolean (default:False
), whether to assume thatG
is squarefree. IfTrue
, the squafreeness ofG
is not verified though it is necessary whenrequire_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 toL
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 ofG
, when set toTrue
, 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 valuationassume_squarefree
– a boolean (default:False
), whether to assumeG
to be squarefreerequired_precision
– a number or infinity (default: infinity); ifinfinity
, the returned polynomials are actual factors ofG
, otherwise they are only factors with precision at leastrequired_precision
.
ALGORITHM:
We compute
mac_lane_approximants()
withrequired_precision
. The key polynomials approximate factors ofG
. This can be very slow unlessrequired_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)
wherev
is an approximant, i.e., a valuation, ef is a boolean,p
is the parent of this vertex, andcoeffs
andvals
are cached values. (Onlyv
andef
are relevant, everything else are caches/debug info.) The booleanef
denotes whetherv
already has the final ramification index E and residue degree F of this approximant. An edge V – P represents the relationP.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