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 (2016-11-01): 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:
InductiveValuation
Abstract base class for an inductive valuation which cannot be augmented further.
- class sage.rings.valuation.inductive_valuation.FiniteInductiveValuation(parent, phi)#
Bases:
InductiveValuation
,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:
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: # needs sage.libs.ntl 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: # needs sage.libs.ntl 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: # needs sage.libs.ntl sage: R.<u> = Qq(4,5) sage: S.<x> = R[] sage: v = GaussValuation(S) sage: v.augmentation_chain() [Gauss valuation induced by 2-adic 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: # needs sage.libs.ntl 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: # needs sage.libs.ntl 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: # needs sage.libs.ntl 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 valuation-s
.
EXAMPLES:
sage: # needs sage.libs.ntl 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: # needs sage.libs.ntl 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: # needs sage.libs.ntl 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:
FinalInductiveValuation
,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)) 2-adic valuation
- class sage.rings.valuation.inductive_valuation.NonFinalInductiveValuation(parent, phi)#
Bases:
FiniteInductiveValuation
,DiscreteValuation
Abstract base class for iterated
augmented valuations
on top of aGauss valuation
which can be extended further throughaugmentation()
.EXAMPLES:
sage: # needs sage.libs.ntl 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: # needs sage.libs.ntl 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 2-adic 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 non-zero 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: # needs sage.libs.ntl 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 non-minimal degree:sage: w = v.augmentation(x, 1) # needs sage.libs.ntl sage: F = w.equivalence_decomposition(x^2+1); F # needs sage.libs.ntl (1 + O(2^10))*x^2 + 1 + O(2^10) sage: F.unit() # needs sage.libs.ntl (1 + O(2^10))*x^2 + 1 + O(2^10)
However, if the polynomial has a non-unit factor, then the unit might be replaced by a factor of lower degree:
sage: f = x * (x^2 + 1) # needs sage.libs.ntl sage: F = w.equivalence_decomposition(f); F # needs sage.libs.ntl (1 + O(2^10))*x sage: F.unit() # needs sage.libs.ntl 1 + O(2^10)
Examples over an iterated unramified extension:
sage: # needs sage.libs.ntl 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 equivalence-irreducible, 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 non-constant polynomial in the domain of this valuation
EXAMPLES:
sage: # needs sage.libs.ntl 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: # needs sage.libs.ntl 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 non-zero 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: # needs sage.libs.ntl 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 non-constant 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: # needs sage.libs.ntl 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 non-constant integral polynomial
G
which is not anequivalence unit
.This performs the individual steps that are used in
mac_lane_approximants()
.INPUT:
G
– a squarefree monic non-constant 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 non-constant 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) # needs sage.geometry.polyhedron [[ Gauss valuation induced by 2-adic valuation, v(x + 2056) = 23/2 ], [ Gauss valuation induced by 2-adic valuation, v(x) = 11/9 ], [ Gauss valuation induced by 2-adic valuation, v(x) = 2/5, v(x^5 + 4) = 7/2 ], [ Gauss valuation induced by 2-adic valuation, v(x) = 3/5, v(x^10 + 8*x^5 + 64) = 7 ], [ Gauss valuation induced by 2-adic 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 = sorted(v0.mac_lane_step(f)); V1 # needs sage.geometry.polyhedron [[ Gauss valuation induced by 2-adic valuation, v(x) = 2/5 ], [ Gauss valuation induced by 2-adic valuation, v(x) = 3/5 ], [ Gauss valuation induced by 2-adic valuation, v(x) = 11/9 ], [ Gauss valuation induced by 2-adic valuation, v(x) = 3 ]]
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[1].mac_lane_step(f) # needs sage.geometry.polyhedron [[ Gauss valuation induced by 2-adic valuation, v(x) = 3/5, v(x^5 + 8) = 5 ], [ Gauss valuation induced by 2-adic valuation, v(x) = 3/5, v(x^10 + 8*x^5 + 64) = 7 ], [ Gauss valuation induced by 2-adic valuation, v(x) = 3 ], [ Gauss valuation induced by 2-adic valuation, v(x) = 11/9 ]]
Note how this detected the two augmentations of
V1[1]
but also two other valuations that we had seen in the previous step and that are greater thanV1[1]
. To ignore such trivial augmentations, we can setallow_equivalent_key
:sage: V1[1].mac_lane_step(f, allow_equivalent_key=False) # needs sage.geometry.polyhedron [[ Gauss valuation induced by 2-adic valuation, v(x) = 3/5, v(x^5 + 8) = 5 ], [ Gauss valuation induced by 2-adic 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 non-zero 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: # needs sage.libs.ntl 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: # needs sage.libs.ntl 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