Discrete valuations¶
This file defines abstract base classes for discrete (pseudo)valuations.
AUTHORS:
 Julian Rüth (20130316): initial version
EXAMPLES:
Discrete valuations can be created on a variety of rings:
sage: ZZ.valuation(2)
2adic valuation
sage: GaussianIntegers().valuation(3)
3adic valuation
sage: QQ.valuation(5)
5adic valuation
sage: Zp(7).valuation()
7adic 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 2adic valuation, v(x) = 3 ]
We can also define discrete pseudovaluations, i.e., discrete valuations that send more than just zero to infinity:
sage: w.augmentation(x, infinity)
[ Gauss valuation induced by 2adic valuation, v(x) = +Infinity ]

class
sage.rings.valuation.valuation.
DiscretePseudoValuation
(parent)¶ Bases:
sage.categories.morphism.Morphism
Abstract base class for discrete pseudovaluations, 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 2adic valuation

is_equivalent
(f, g)¶ 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

class
sage.rings.valuation.valuation.
DiscreteValuation
(parent)¶ Bases:
sage.rings.valuation.valuation.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 2adic 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()
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
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 2adic 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 2adic 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 2adic 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 2adic valuation, v(x) = 1/2 ] is not an approximant for a valuation which extends 2adic 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 2adic valuation does not approximate a unique extension of 2adic 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 2adic valuation, v(x + 1) = 1 ] does not approximate a unique extension of 2adic 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 2adic 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 2adic 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 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 onetoone 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 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 (deault: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) [[ Gauss valuation induced by 2adic valuation, v(x + 1) = 1/2 ]] sage: v.mac_lane_approximants(x^2 + 1, required_precision=infinity) [[ Gauss valuation induced by 2adic valuation, v(x + 1) = 1/2, v(x^2 + 1) = +Infinity ]] sage: v.mac_lane_approximants(x^2 + x + 1) [[ Gauss valuation induced by 2adic 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 2adic valuation, v(x + 1) = +Infinity ], [ Gauss valuation induced by 2adic 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
sage: R = ZpFM(3, 7, print_mode='terse') sage: S.<x> = R[] sage: v = R.valuation() sage: f = x^4 + 234 sage: len(v.mac_lane_approximants(f, assume_squarefree=True)) # is_squarefree() is not properly implemented yet 2
sage: R = ZpFM(2, 50, print_mode='terse') sage: S.<x> = R[] sage: f = (x^32 + 16)*(x^32 + 16 + 2^16*x^2) + 2^34 sage: v = R.valuation() sage: len(v.mac_lane_approximants(f, assume_squarefree=True)) # is_squarefree() is not properly implemented yet 2
A case that triggered an assertion at some point:
sage: v = QQ.valuation(3) sage: R.<x> = QQ[] sage: f = x^36 + 60552000*x^33 + 268157412*x^30 + 173881701*x^27 + 266324841*x^24 + 83125683*x^21 + 111803814*x^18 + 31925826*x^15 + 205726716*x^12 +17990262*x^9 + 351459648*x^6 + 127014399*x^3 + 359254116 sage: v.mac_lane_approximants(f) [[ Gauss valuation induced by 3adic valuation, v(x) = 1/3, v(x^3  3) = 3/2, v(x^12  3*x^9 + 54*x^6 + 27/2*x^3 + 405/2) = 13/2, v(x^36 + 60552000*x^33 + 268157412*x^30 + 173881701*x^27 + 266324841*x^24 + 83125683*x^21 + 111803814*x^18 + 31925826*x^15 + 205726716*x^12 + 17990262*x^9 + 351459648*x^6 + 127014399*x^3 + 359254116) = +Infinity ]]

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 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: 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:
sage.rings.valuation.valuation.DiscretePseudoValuation
Abstract base class for infinite discrete pseudovaluations, i.e., discrete pseudovaluations 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 2adic 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)
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)¶ Bases:
sage.rings.valuation.valuation.InfiniteDiscretePseudoValuation
Abstract base class for pseudovaluations 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
