Gauss valuations on polynomial rings#
This file implements Gauss valuations for polynomial rings, i.e. discrete valuations which assign to a polynomial the minimal valuation of its coefficients.
AUTHORS:
Julian Rüth (2013-04-15): initial version
EXAMPLES:
A Gauss valuation maps a polynomial to the minimal valuation of any of its coefficients:
sage: R.<x> = QQ[]
sage: v0 = QQ.valuation(2)
sage: v = GaussValuation(R, v0); v
Gauss valuation induced by 2-adic valuation
sage: v(2*x + 2)
1
Gauss valuations can also be defined iteratively based on valuations over polynomial rings:
sage: v = v.augmentation(x, 1/4); v
[ Gauss valuation induced by 2-adic valuation, v(x) = 1/4 ]
sage: v = v.augmentation(x^4+2*x^3+2*x^2+2*x+2, 4/3); v
[ Gauss valuation induced by 2-adic valuation, v(x) = 1/4, v(x^4 + 2*x^3 + 2*x^2 + 2*x + 2) = 4/3 ]
sage: S.<T> = R[]
sage: w = GaussValuation(S, v); w
Gauss valuation induced by [ Gauss valuation induced by 2-adic valuation, v(x) = 1/4, v(x^4 + 2*x^3 + 2*x^2 + 2*x + 2) = 4/3 ]
sage: w(2*T + 1)
0
- class sage.rings.valuation.gauss_valuation.GaussValuationFactory#
Bases:
UniqueFactory
Create a Gauss valuation on
domain
.INPUT:
domain
– a univariate polynomial ringv
– a valuation on the base ring ofdomain
, the underlying valuation on the constants of the polynomial ring (if unspecified take the natural valuation on the valued ringdomain
.)
EXAMPLES:
The Gauss valuation is the minimum of the valuation of the coefficients:
sage: v = QQ.valuation(2) sage: R.<x> = QQ[] sage: w = GaussValuation(R, v) sage: w(2) 1 sage: w(x) 0 sage: w(x + 2) 0
- create_key(domain, v=None)#
Normalize and check the parameters to create a Gauss valuation.
- create_object(version, key, **extra_args)#
Create a Gauss valuation from normalized parameters.
- class sage.rings.valuation.gauss_valuation.GaussValuation_generic(parent, v)#
Bases:
NonFinalInductiveValuation
A Gauss valuation on a polynomial ring
domain
.INPUT:
domain
– a univariate polynomial ring over a valued ring \(R\)v
– a discrete valuation on \(R\)
EXAMPLES:
sage: R = Zp(3,5) sage: S.<x> = R[] # needs sage.libs.ntl sage: v0 = R.valuation() sage: v = GaussValuation(S, v0); v # needs sage.libs.ntl Gauss valuation induced by 3-adic valuation sage: S.<x> = QQ[] sage: v = GaussValuation(S, QQ.valuation(5)); v Gauss valuation induced by 5-adic valuation
- E()#
Return the ramification index of this valuation over its underlying Gauss valuation, i.e., 1.
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 degree of the residue field extension of this valuation over the Gauss valuation, i.e., 1.
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]
- change_domain(ring)#
Return this valuation as a valuation over
ring
.EXAMPLES:
sage: v = ZZ.valuation(2) sage: R.<x> = ZZ[] sage: w = GaussValuation(R, v) sage: w.change_domain(QQ['x']) 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
- 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)
- extensions(ring)#
Return the extensions of this valuation to
ring
.EXAMPLES:
sage: v = ZZ.valuation(2) sage: R.<x> = ZZ[] sage: w = GaussValuation(R, v) sage: w.extensions(GaussianIntegers()['x']) # needs sage.rings.number_field [Gauss valuation induced by 2-adic valuation]
- is_gauss_valuation()#
Return whether this valuation is a Gauss valuation.
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
- is_trivial()#
Return whether this is a trivial valuation (sending everything but zero to zero.)
EXAMPLES:
sage: R.<x> = QQ[] sage: v = GaussValuation(R, valuations.TrivialValuation(QQ)) sage: v.is_trivial() True
- lift(F)#
Return a lift of
F
.INPUT:
F
– a polynomial over theresidue_ring()
of this valuation
OUTPUT:
a (possibly non-monic) polynomial in the domain of this valuation which reduces to
F
EXAMPLES:
sage: # needs sage.libs.ntl sage: S.<x> = Qp(3,5)[] sage: v = GaussValuation(S) sage: f = x^2 + 2*x + 16 sage: F = v.reduce(f); F x^2 + 2*x + 1 sage: g = v.lift(F); g (1 + O(3^5))*x^2 + (2 + O(3^5))*x + 1 + O(3^5) sage: v.is_equivalent(f,g) True sage: g.parent() is v.domain() True
See also
- 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, for a suitable equivalence unit \(R\), satisfies that the reduction of \(Rf\) is
F
EXAMPLES:
sage: R.<u> = QQ sage: S.<x> = R[] sage: v = GaussValuation(S, QQ.valuation(2)) sage: y = v.residue_ring().gen() sage: f = v.lift_to_key(y^2 + y + 1); f x^2 + x + 1
- lower_bound(f)#
Return an lower bound of this valuation at
f
.Use this method to get an approximation of the valuation of
f
when speed is more important than accuracy.EXAMPLES:
sage: # needs sage.libs.ntl sage: R.<u> = Qq(4, 5) sage: S.<x> = R[] sage: v = GaussValuation(S) sage: v.lower_bound(1024*x + 2) 1 sage: v(1024*x + 2) 1
- 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> = Qp(2, 5)[] # needs sage.libs.ntl sage: v = GaussValuation(R) # needs sage.libs.ntl sage: v.monic_integral_model(5*x^2 + 1/2*x + 1/4) # needs sage.libs.ntl (Ring endomorphism of Univariate Polynomial Ring in x over 2-adic Field with capped relative precision 5 Defn: (1 + O(2^5))*x |--> (2^-1 + O(2^4))*x, Ring endomorphism of Univariate Polynomial Ring in x over 2-adic Field with capped relative precision 5 Defn: (1 + O(2^5))*x |--> (2 + O(2^6))*x, (1 + O(2^5))*x^2 + (1 + 2^2 + 2^3 + O(2^5))*x + 1 + 2^2 + 2^3 + O(2^5))
- reduce(f, check=True, degree_bound=None, coefficients=None, valuations=None)#
Return the reduction of
f
modulo this valuation.INPUT:
f
– an integral element of the domain of this valuationcheck
– whether or not to check whetherf
has non-negative valuation (default:True
)degree_bound
– an a-priori known bound on the degree of the result which can speed up the computation (default: not set)coefficients
– the coefficients off
as produced bycoefficients()
orNone
(default:None
); ignoredvaluations
– the valuations ofcoefficients
orNone
(default:None
); ignored
OUTPUT:
A polynomial in the
residue_ring()
of this valuation.EXAMPLES:
sage: # needs sage.libs.ntl sage: S.<x> = Qp(2,5)[] sage: v = GaussValuation(S) sage: f = x^2 + 2*x + 16 sage: v.reduce(f) x^2 sage: v.reduce(f).parent() is v.residue_ring() True
The reduction is only defined for integral elements:
sage: f = x^2/2 # needs sage.libs.ntl sage: v.reduce(f) # needs sage.libs.ntl Traceback (most recent call last): ... ValueError: reduction not defined for non-integral elements and (2^-1 + O(2^4))*x^2 is not integral over Gauss valuation induced by 2-adic valuation
See also
- residue_ring()#
Return the residue ring of this valuation, i.e., the elements of valuation zero module the elements of positive valuation.
EXAMPLES:
sage: S.<x> = Qp(2,5)[] # needs sage.libs.ntl sage: v = GaussValuation(S) # needs sage.libs.ntl sage: v.residue_ring() # needs sage.libs.ntl Univariate Polynomial Ring in x over Finite Field of size 2 (using ...)
- restriction(ring)#
Return the restriction of this valuation to
ring
.EXAMPLES:
sage: v = ZZ.valuation(2) sage: R.<x> = ZZ[] sage: w = GaussValuation(R, v) sage: w.restriction(ZZ) 2-adic valuation
- scale(scalar)#
Return this valuation scaled by
scalar
.EXAMPLES:
sage: R.<x> = QQ[] sage: v = GaussValuation(R, QQ.valuation(2)) sage: 3*v # indirect doctest Gauss valuation induced by 3 * 2-adic valuation
- simplify(f, error=None, force=False, size_heuristic_bound=32, effective_degree=None, phiadic=True)#
Return a simplified version of
f
.Produce an element which differs from
f
by an element of valuation strictly greater than the valuation off
(or strictly greater thanerror
if set.)INPUT:
f
– an element in the domain of this valuationerror
– a rational, infinity, orNone
(default:None
), the error allowed to introduce through the simplificationforce
– whether or not to simplifyf
even if there is heuristically no change in the coefficient size off
expected (default:False
)effective_degree
– when set, assume that coefficients beyondeffective_degree
can be safely dropped (default:None
)size_heuristic_bound
– whenforce
is not set, the expected factor by which the coefficients need to shrink to perform an actual simplification (default: 32)phiadic
– whether to simplify in the \(x\)-adic expansion; the parameter is ignored as no other simplification is implemented
EXAMPLES:
sage: # needs sage.libs.ntl sage: R.<u> = Qq(4, 5) sage: S.<x> = R[] sage: v = GaussValuation(S) sage: f = x^10/2 + 1 sage: v.simplify(f) (2^-1 + O(2^4))*x^10 + 1 + O(2^5)
- uniformizer()#
Return a uniformizer of this valuation, i.e., a uniformizer of the valuation of the base ring.
EXAMPLES:
sage: S.<x> = QQ[] sage: v = GaussValuation(S, QQ.valuation(5)) sage: v.uniformizer() 5 sage: v.uniformizer().parent() is S True
- upper_bound(f)#
Return an upper bound of this valuation at
f
.Use this method to get an approximation of the valuation of
f
when speed is more important than accuracy.EXAMPLES:
sage: # needs sage.libs.ntl sage: R.<u> = Qq(4, 5) sage: S.<x> = R[] sage: v = GaussValuation(S) sage: v.upper_bound(1024*x + 1) 10 sage: v(1024*x + 1) 0
- valuations(f, coefficients=None, call_error=False)#
Return the valuations of the \(f_i\phi^i\) in the expansion \(f=\sum f_i\phi^i\).
INPUT:
f
– a polynomial in the domain of this valuationcoefficients
– the coefficients off
as produced bycoefficients()
orNone
(default:None
); this can be used to speed up the computation when the expansion off
is already known from a previous computation.call_error
– whether or not to speed up the computation by assuming that the result is only used to compute the valuation off
(default:False
)
OUTPUT:
A list, each entry a rational numbers or infinity, the valuations of \(f_0, f_1\phi, \dots\)
EXAMPLES:
sage: R = ZZ sage: S.<x> = R[] sage: v = GaussValuation(S, R.valuation(2)) sage: f = x^2 + 2*x + 16 sage: list(v.valuations(f)) [4, 1, 0]
- value_group()#
Return the value group of this valuation.
EXAMPLES:
sage: S.<x> = QQ[] sage: v = GaussValuation(S, QQ.valuation(5)) sage: v.value_group() Additive Abelian Group generated by 1
- value_semigroup()#
Return the value semigroup of this valuation.
EXAMPLES:
sage: S.<x> = QQ[] sage: v = GaussValuation(S, QQ.valuation(5)) sage: v.value_semigroup() Additive Abelian Semigroup generated by -1, 1