Inductive valuations on polynomial rings¶
This module provides functionality for inductive valuations, i.e., finite
chains of augmented valuations
on top of a Gauss valuation
.
AUTHORS:
 Julian Rüth (20161101): initial version
EXAMPLES:
A Gauss valuation
is an example of an inductive valuation:
sage: R.<x> = QQ[]
sage: v = GaussValuation(R, QQ.valuation(2))
Generally, an inductive valuation is an augmentation of an inductive valuation, i.e., a valuation that was created from a Gauss valuation in a finite number of augmentation steps:
sage: w = v.augmentation(x, 1)
sage: w = w.augmentation(x^2 + 2*x + 4, 3)
REFERENCES:
Inductive valuations are originally discussed in [Mac1936I] and [Mac1936II]. An introduction is also given in Chapter 4 of [Rüt2014].

class
sage.rings.valuation.inductive_valuation.
FinalInductiveValuation
(parent, phi)¶ Bases:
sage.rings.valuation.inductive_valuation.InductiveValuation
Abstract base class for an inductive valuation which can not be augmented further.

class
sage.rings.valuation.inductive_valuation.
FiniteInductiveValuation
(parent, phi)¶ Bases:
sage.rings.valuation.inductive_valuation.InductiveValuation
,sage.rings.valuation.valuation.DiscreteValuation
Abstract base class for iterated
augmented valuations
on top of aGauss valuation
which is a discrete valuation, i.e., the last key polynomial has finite valuation.EXAMPLES:
sage: R.<x> = QQ[] sage: v = GaussValuation(R, valuations.TrivialValuation(QQ))

extensions
(other)¶ Return the extensions of this valuation to
other
.EXAMPLES:
sage: R.<x> = ZZ[] sage: v = GaussValuation(R, valuations.TrivialValuation(ZZ)) sage: K.<x> = FunctionField(QQ) sage: v.extensions(K) [Trivial valuation on Rational Field]


class
sage.rings.valuation.inductive_valuation.
InductiveValuation
(parent, phi)¶ Bases:
sage.rings.valuation.developing_valuation.DevelopingValuation
Abstract base class for iterated
augmented valuations
on top of aGauss valuation
.EXAMPLES:
sage: R.<x> = QQ[] sage: v = GaussValuation(R, QQ.valuation(5))

E
()¶ Return the ramification index of this valuation over its underlying Gauss valuation.
EXAMPLES:
sage: R.<u> = Qq(4,5) sage: S.<x> = R[] sage: v = GaussValuation(S) sage: v.E() 1

F
()¶ Return the residual degree of this valuation over its Gauss extension.
EXAMPLES:
sage: R.<u> = Qq(4,5) sage: S.<x> = R[] sage: v = GaussValuation(S) sage: v.F() 1

augmentation_chain
()¶ Return a list with the chain of augmentations down to the underlying
Gauss valuation
.EXAMPLES:
sage: R.<u> = Qq(4,5) sage: S.<x> = R[] sage: v = GaussValuation(S) sage: v.augmentation_chain() [Gauss valuation induced by 2adic valuation]

element_with_valuation
(s)¶ Return a polynomial of minimal degree with valuation
s
.EXAMPLES:
sage: R.<x> = QQ[] sage: v = GaussValuation(R, QQ.valuation(2)) sage: v.element_with_valuation(2) 1/4
Depending on the base ring, an element of valuation
s
might not exist:sage: R.<x> = ZZ[] sage: v = GaussValuation(R, ZZ.valuation(2)) sage: v.element_with_valuation(2) Traceback (most recent call last): ... ValueError: s must be in the value semigroup of this valuation but 2 is not in Additive Abelian Semigroup generated by 1

equivalence_reciprocal
(f, coefficients=None, valuations=None, check=True)¶ Return an equivalence reciprocal of
f
.An equivalence reciprocal of \(f\) is a polynomial \(h\) such that \(f\cdot h\) is equivalent to 1 modulo this valuation (see [Mac1936II] p.497.)
INPUT:
f
– a polynomial in the domain of this valuation which is anequivalence_unit()
coefficients
– the coefficients off
in thephi()
adic expansion if known (default:None
)valuations
– the valuations ofcoefficients
if known (default:None
)check
– whether or not to check the validity off
(default:True
)
Warning
This method may not work over \(p\)adic rings due to problems with the xgcd implementation there.
EXAMPLES:
sage: R = Zp(3,5) sage: S.<x> = R[] sage: v = GaussValuation(S) sage: f = 3*x + 2 sage: h = v.equivalence_reciprocal(f); h 2 + O(3^5) sage: v.is_equivalent(f*h, 1) True
In an extended valuation over an extension field:
sage: R.<u> = Qq(4,5) sage: S.<x> = R[] sage: v = GaussValuation(S) sage: v = v.augmentation(x^2 + x + u, 1) sage: f = 2*x + u sage: h = v.equivalence_reciprocal(f); h (u + 1) + O(2^5) sage: v.is_equivalent(f*h, 1) True
Extending the valuation once more:
sage: v = v.augmentation((x^2 + x + u)^2 + 2*x*(x^2 + x + u) + 4*x, 3) sage: h = v.equivalence_reciprocal(f); h (u + 1) + O(2^5) sage: v.is_equivalent(f*h, 1) True

equivalence_unit
(s, reciprocal=False)¶ Return an equivalence unit of valuation
s
.INPUT:
s
– an element of thevalue_group()
reciprocal
– a boolean (default:False
); whether or not to return the equivalence unit as theequivalence_reciprocal()
of the equivalence unit of valuations
.
EXAMPLES:
sage: S.<x> = Qp(3,5)[] sage: v = GaussValuation(S) sage: v.equivalence_unit(2) 3^2 + O(3^7) sage: v.equivalence_unit(2) 3^2 + O(3^3)
Note that this might fail for negative
s
if the domain is not defined over a field:sage: v = ZZ.valuation(2) sage: R.<x> = ZZ[] sage: w = GaussValuation(R, v) sage: w.equivalence_unit(1) 2 sage: w.equivalence_unit(1) Traceback (most recent call last): ... ValueError: s must be in the value semigroup of this valuation but 1 is not in Additive Abelian Semigroup generated by 1

is_equivalence_unit
(f, valuations=None)¶ Return whether the polynomial
f
is an equivalence unit, i.e., an element ofeffective_degree()
zero (see [Mac1936II] p.497.)INPUT:
f
– a polynomial in the domain of this valuation
EXAMPLES:
sage: R = Zp(2,5) sage: S.<x> = R[] sage: v = GaussValuation(S) sage: v.is_equivalence_unit(x) False sage: v.is_equivalence_unit(S.zero()) False sage: v.is_equivalence_unit(2*x + 1) True

is_gauss_valuation
()¶ Return whether this valuation is a Gauss valuation over the domain.
EXAMPLES:
sage: R.<u> = Qq(4,5) sage: S.<x> = R[] sage: v = GaussValuation(S) sage: v.is_gauss_valuation() True

monic_integral_model
(G)¶ Return a monic integral irreducible polynomial which defines the same extension of the base ring of the domain as the irreducible polynomial
G
together with maps between the old and the new polynomial.EXAMPLES:
sage: R.<x> = QQ[] sage: v = GaussValuation(R, QQ.valuation(2)) sage: v.monic_integral_model(5*x^2 + 1/2*x + 1/4) (Ring endomorphism of Univariate Polynomial Ring in x over Rational Field Defn: x > 1/2*x, Ring endomorphism of Univariate Polynomial Ring in x over Rational Field Defn: x > 2*x, x^2 + 1/5*x + 1/5)


class
sage.rings.valuation.inductive_valuation.
InfiniteInductiveValuation
(parent, base_valuation)¶ Bases:
sage.rings.valuation.inductive_valuation.FinalInductiveValuation
,sage.rings.valuation.valuation.InfiniteDiscretePseudoValuation
Abstract base class for an inductive valuation which is not discrete, i.e., which assigns infinite valuation to its last key polynomial.
EXAMPLES:
sage: R.<x> = QQ[] sage: v = GaussValuation(R, QQ.valuation(2)) sage: w = v.augmentation(x^2 + x + 1, infinity)

change_domain
(ring)¶ Return this valuation over
ring
.EXAMPLES:
We can turn an infinite valuation into a valuation on the quotient:
sage: R.<x> = QQ[] sage: v = GaussValuation(R, QQ.valuation(2)) sage: w = v.augmentation(x^2 + x + 1, infinity) sage: w.change_domain(R.quo(x^2 + x + 1)) 2adic valuation


class
sage.rings.valuation.inductive_valuation.
NonFinalInductiveValuation
(parent, phi)¶ Bases:
sage.rings.valuation.inductive_valuation.FiniteInductiveValuation
,sage.rings.valuation.valuation.DiscreteValuation
Abstract base class for iterated
augmented valuations
on top of aGauss valuation
which can be extended further throughaugmentation()
.EXAMPLES:
sage: R.<u> = Qq(4,5) sage: S.<x> = R[] sage: v = GaussValuation(S) sage: v = v.augmentation(x^2 + x + u, 1)

augmentation
(phi, mu, check=True)¶ Return the inductive valuation which extends this valuation by mapping
phi
tomu
.INPUT:
phi
– a polynomial in the domain of this valuation; this must be a key polynomial, seeis_key()
for properties of key polynomials.mu
– a rational number or infinity, the valuation ofphi
in the extended valuationcheck
– a boolean (default:True
), whether or not to check the correctness of the parameters
EXAMPLES:
sage: R.<u> = Qq(4,5) sage: S.<x> = R[] sage: v = GaussValuation(S) sage: v = v.augmentation(x^2 + x + u, 1) sage: v = v.augmentation((x^2 + x + u)^2 + 2*x*(x^2 + x + u) + 4*x, 3) sage: v [ Gauss valuation induced by 2adic valuation, v((1 + O(2^5))*x^2 + (1 + O(2^5))*x + u + O(2^5)) = 1, v((1 + O(2^5))*x^4 + (2^2 + O(2^6))*x^3 + (1 + (u + 1)*2 + O(2^5))*x^2 + ((u + 1)*2^2 + O(2^6))*x + (u + 1) + (u + 1)*2 + (u + 1)*2^2 + (u + 1)*2^3 + (u + 1)*2^4 + O(2^5)) = 3 ]
See also

equivalence_decomposition
(f, assume_not_equivalence_unit=False, coefficients=None, valuations=None, compute_unit=True, degree_bound=None)¶ Return an equivalence decomposition of
f
, i.e., a polynomial \(g(x)=e(x)\prod_i \phi_i(x)\) with \(e(x)\) anequivalence unit
and the \(\phi_i\)key polynomials
such thatf
is_equivalent()
to \(g\).INPUT:
f
– a nonzero polynomial in the domain of this valuationassume_not_equivalence_unit
– whether or not to assume thatf
is not anequivalence unit
(default:False
)coefficients
– the coefficients off
in thephi()
adic expansion if known (default:None
)valuations
– the valuations ofcoefficients
if known (default:None
)compute_unit
– whether or not to compute the unit part of the decomposition (default:True
)degree_bound
– a bound on the degree of the_equivalence_reduction()
off
(default:None
)
ALGORITHM:
We use the algorithm described in Theorem 4.4 of [Mac1936II]. After removing all factors \(\phi\) from a polynomial \(f\), there is an equivalence unit \(R\) such that \(Rf\) has valuation zero. Now \(Rf\) can be factored as \(\prod_i \alpha_i\) over the
residue_field()
. Lifting all \(\alpha_i\) to key polynomials \(\phi_i\) gives \(Rf=\prod_i R_i f_i\) for suitable equivalence units \(R_i\) (seelift_to_key()
). Taking \(R'\) anequivalence_reciprocal()
of \(R\), we have \(f\) equivalent to \((R'\prod_i R_i)\prod_i\phi_i\).EXAMPLES:
sage: R.<u> = Qq(4,10) sage: S.<x> = R[] sage: v = GaussValuation(S) sage: v.equivalence_decomposition(S.zero()) Traceback (most recent call last): ... ValueError: equivalence decomposition of zero is not defined sage: v.equivalence_decomposition(S.one()) 1 + O(2^10) sage: v.equivalence_decomposition(x^2+2) ((1 + O(2^10))*x)^2 sage: v.equivalence_decomposition(x^2+1) ((1 + O(2^10))*x + 1 + O(2^10))^2
A polynomial that is an equivalence unit, is returned as the unit part of a
Factorization
, leading to a unit nonminimal degree:sage: w = v.augmentation(x, 1) sage: F = w.equivalence_decomposition(x^2+1); F (1 + O(2^10))*x^2 + 1 + O(2^10) sage: F.unit() (1 + O(2^10))*x^2 + 1 + O(2^10)
However, if the polynomial has a nonunit factor, then the unit might be replaced by a factor of lower degree:
sage: f = x * (x^2 + 1) sage: F = w.equivalence_decomposition(f); F (1 + O(2^10))*x sage: F.unit() 1 + O(2^10)
Examples over an iterated unramified extension:
sage: v = v.augmentation(x^2 + x + u, 1) sage: v = v.augmentation((x^2 + x + u)^2 + 2*x*(x^2 + x + u) + 4*x, 3) sage: v.equivalence_decomposition(x) (1 + O(2^10))*x sage: F = v.equivalence_decomposition( v.phi() ) sage: len(F) 1 sage: F = v.equivalence_decomposition( v.phi() * (x^4 + 4*x^3 + (7 + 2*u)*x^2 + (8 + 4*u)*x + 1023 + 3*u) ) sage: len(F) 2

is_equivalence_irreducible
(f, coefficients=None, valuations=None)¶ Return whether the polynomial
f
is equivalenceirreducible, i.e., whether itsequivalence_decomposition()
is trivial.ALGORITHM:
We use the same algorithm as in
equivalence_decomposition()
we just do not lift the result to key polynomials.INPUT:
f
– a nonconstant polynomial in the domain of this valuation
EXAMPLES:
sage: R.<u> = Qq(4,5) sage: S.<x> = R[] sage: v = GaussValuation(S) sage: v.is_equivalence_irreducible(x) True sage: v.is_equivalence_irreducible(x^2) False sage: v.is_equivalence_irreducible(x^2 + 2) False

is_key
(phi, explain=False, assume_equivalence_irreducible=False)¶ Return whether
phi
is a key polynomial for this valuation, i.e., whether it is monic, whether itis_equivalence_irreducible()
, and whether it isis_minimal()
.INPUT:
phi
– a polynomial in the domain of this valuationexplain
– a boolean (default:False
), ifTrue
, return a string explaining whyphi
is not a key polynomial
EXAMPLES:
sage: R.<u> = Qq(4, 5) sage: S.<x> = R[] sage: v = GaussValuation(S) sage: v.is_key(x) True sage: v.is_key(2*x, explain = True) (False, 'phi must be monic') sage: v.is_key(x^2, explain = True) (False, 'phi must be equivalence irreducible') sage: w = v.augmentation(x, 1) sage: w.is_key(x + 1, explain = True) (False, 'phi must be minimal')

is_minimal
(f, assume_equivalence_irreducible=False)¶ Return whether the polynomial
f
is minimal with respect to this valuation.A polynomial \(f\) is minimal with respect to \(v\) if it is not a constant and any nonzero polynomial \(h\) which is \(v\)divisible by \(f\) has at least the degree of \(f\).
A polynomial \(h\) is \(v\)divisible by \(f\) if there is a polynomial \(c\) such that \(fc\)
is_equivalent()
to \(h\).ALGORITHM:
Based on Theorem 9.4 of [Mac1936II].
EXAMPLES:
sage: R.<u> = Qq(4, 5) sage: S.<x> = R[] sage: v = GaussValuation(S) sage: v.is_minimal(x + 1) True sage: w = v.augmentation(x, 1) sage: w.is_minimal(x + 1) False

lift_to_key
(F)¶ Lift the irreducible polynomial
F
from theresidue_ring()
to a key polynomial over this valuation.INPUT:
F
– an irreducible nonconstant monic polynomial inresidue_ring()
of this valuation
OUTPUT:
A polynomial \(f\) in the domain of this valuation which is a key polynomial for this valuation and which is such that an
augmentation()
with this polynomial adjoins a root ofF
to the resultingresidue_ring()
.More specifically, if
F
is not the generator of the residue ring, then multiplyingf
with theequivalence_reciprocal()
of theequivalence_unit()
of the valuation off
, produces a unit which reduces toF
.EXAMPLES:
sage: R.<u> = Qq(4,10) sage: S.<x> = R[] sage: v = GaussValuation(S) sage: y = v.residue_ring().gen() sage: u0 = v.residue_ring().base_ring().gen() sage: f = v.lift_to_key(y^2 + y + u0); f (1 + O(2^10))*x^2 + (1 + O(2^10))*x + u + O(2^10)

mac_lane_step
(G, principal_part_bound=None, assume_squarefree=False, assume_equivalence_irreducible=False, report_degree_bounds_and_caches=False, coefficients=None, valuations=None, check=True, allow_equivalent_key=True)¶ Perform an approximation step towards the squarefree monic nonconstant integral polynomial
G
which is not anequivalence unit
.This performs the individual steps that are used in
mac_lane_approximants()
.INPUT:
G
– a sqaurefree monic nonconstant integral polynomialG
which is not anequivalence unit
principal_part_bound
– an integer orNone
(default:None
), a bound on the length of the principal part, i.e., the section of negative slope, of the Newton polygon ofG
assume_squarefree
– whether or not to assume thatG
is squarefree (default:False
)assume_equivalence_irreducible
– whether or not to assume thatG
is equivalence irreducible (default:False
)report_degree_bounds_and_caches
– whether or not to include internal state with the returned value (used bymac_lane_approximants()
to speed up sequential calls)coefficients
– the coefficients ofG
in thephi()
adic expansion if known (default:None
)valuations
– the valuations ofcoefficients
if known (default:None
)check
– whether to check thatG
is a squarefree monic nonconstant integral polynomial and not anequivalence unit
(default:True
)allow_equivalent_key
– whether to return valuations which end in essentially the same key polynomial as this valuation but have a higher valuation assigned to that key polynomial (default:True
)
EXAMPLES:
We can use this method to perform the individual steps of
mac_lane_approximants()
:sage: R.<x> = QQ[] sage: v = QQ.valuation(2) sage: f = x^36 + 1160/81*x^31 + 9920/27*x^30 + 1040/81*x^26 + 52480/81*x^25 + 220160/81*x^24  5120/81*x^21  143360/81*x^20  573440/81*x^19 + 12451840/81*x^18  266240/567*x^16  20316160/567*x^15  198737920/189*x^14  1129840640/81*x^13  1907359744/27*x^12 + 8192/81*x^11 + 655360/81*x^10 + 5242880/21*x^9 + 2118123520/567*x^8 + 15460204544/567*x^7 + 6509559808/81*x^6  16777216/567*x^2  268435456/567*x  1073741824/567 sage: v.mac_lane_approximants(f) [[ Gauss valuation induced by 2adic valuation, v(x + 2056) = 23/2 ], [ Gauss valuation induced by 2adic valuation, v(x) = 11/9 ], [ Gauss valuation induced by 2adic valuation, v(x) = 2/5, v(x^5 + 4) = 7/2 ], [ Gauss valuation induced by 2adic valuation, v(x) = 3/5, v(x^10 + 8*x^5 + 64) = 7 ], [ Gauss valuation induced by 2adic valuation, v(x) = 3/5, v(x^5 + 8) = 5 ]]
Starting from the Gauss valuation, a MacLane step branches off with some linear key polynomials in the above example:
sage: v0 = GaussValuation(R, v) sage: V1 = v0.mac_lane_step(f); V1 [[ Gauss valuation induced by 2adic valuation, v(x) = 3/5 ], [ Gauss valuation induced by 2adic valuation, v(x) = 2/5 ], [ Gauss valuation induced by 2adic valuation, v(x) = 3 ], [ Gauss valuation induced by 2adic valuation, v(x) = 11/9 ]]
The computation of MacLane approximants would now perform a MacLane step on each of these branches, note however, that a direct call to this method might produce some unexpected results:
sage: V1[0].mac_lane_step(f) [[ Gauss valuation induced by 2adic valuation, v(x) = 3/5, v(x^5 + 8) = 5 ], [ Gauss valuation induced by 2adic valuation, v(x) = 3/5, v(x^10 + 8*x^5 + 64) = 7 ], [ Gauss valuation induced by 2adic valuation, v(x) = 3 ], [ Gauss valuation induced by 2adic valuation, v(x) = 11/9 ]]
Note how this detected the two augmentations of
V1[0]
but also two other valuations that we had seen in the previous step and that are greater thanV1[0]
. To ignore such trivial augmentations, we can setallow_equivalent_key
:sage: V1[0].mac_lane_step(f, allow_equivalent_key=False) [[ Gauss valuation induced by 2adic valuation, v(x) = 3/5, v(x^5 + 8) = 5 ], [ Gauss valuation induced by 2adic valuation, v(x) = 3/5, v(x^10 + 8*x^5 + 64) = 7 ]]

minimal_representative
(f)¶ Return a minimal representative for
f
, i.e., a pair \(e, a\) such thatf
is_equivalent()
to \(e a\), \(e\) is anequivalence unit
, and \(a\)is_minimal()
and monic.INPUT:
f
– a nonzero polynomial which is not an equivalence unit
OUTPUT:
A factorization which has \(e\) as its unit and \(a\) as its unique factor.
ALGORITHM:
We use the algorithm described in the proof of Lemma 4.1 of [Mac1936II]. In the expansion \(f=\sum_i f_i\phi^i\) take \(e=f_i\) for the largest \(i\) with \(f_i\phi^i\) minimal (see
effective_degree()
). Let \(h\) be theequivalence_reciprocal()
of \(e\) and take \(a\) given by the terms of minimal valuation in the expansion of \(e f\).EXAMPLES:
sage: R.<u> = Qq(4,10) sage: S.<x> = R[] sage: v = GaussValuation(S) sage: v.minimal_representative(x + 2) (1 + O(2^10))*x sage: v = v.augmentation(x, 1) sage: v.minimal_representative(x + 2) (1 + O(2^10))*x + 2 + O(2^11) sage: f = x^3 + 6*x + 4 sage: F = v.minimal_representative(f); F (2 + 2^2 + O(2^11)) * ((1 + O(2^10))*x + 2 + O(2^11)) sage: v.is_minimal(F[0][0]) True sage: v.is_equivalent(F.prod(), f) True
