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
>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> v0 = QQ.valuation(Integer(2))
>>> v = GaussValuation(R, v0); v
Gauss valuation induced by 2-adic valuation
>>> v(Integer(2)*x + Integer(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
>>> from sage.all import *
>>> v = v.augmentation(x, Integer(1)/Integer(4)); v
[ Gauss valuation induced by 2-adic valuation, v(x) = 1/4 ]
>>> v = v.augmentation(x**Integer(4)+Integer(2)*x**Integer(3)+Integer(2)*x**Integer(2)+Integer(2)*x+Integer(2), Integer(4)/Integer(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 ]
>>> S = R['T']; (T,) = S._first_ngens(1)
>>> 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 ]
>>> w(Integer(2)*T + Integer(1))
0
- class sage.rings.valuation.gauss_valuation.GaussValuationFactory[source]#
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
>>> from sage.all import * >>> v = QQ.valuation(Integer(2)) >>> R = QQ['x']; (x,) = R._first_ngens(1) >>> w = GaussValuation(R, v) >>> w(Integer(2)) 1 >>> w(x) 0 >>> w(x + Integer(2)) 0
- class sage.rings.valuation.gauss_valuation.GaussValuation_generic(parent, v)[source]#
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
>>> from sage.all import * >>> R = Zp(Integer(3),Integer(5)) >>> S = R['x']; (x,) = S._first_ngens(1)# needs sage.libs.ntl >>> v0 = R.valuation() >>> v = GaussValuation(S, v0); v # needs sage.libs.ntl Gauss valuation induced by 3-adic valuation >>> S = QQ['x']; (x,) = S._first_ngens(1) >>> v = GaussValuation(S, QQ.valuation(Integer(5))); v Gauss valuation induced by 5-adic valuation
- E()[source]#
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
>>> from sage.all import * >>> # needs sage.libs.ntl >>> R = Qq(Integer(4),Integer(5), names=('u',)); (u,) = R._first_ngens(1) >>> S = R['x']; (x,) = S._first_ngens(1) >>> v = GaussValuation(S) >>> v.E() 1
- F()[source]#
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
>>> from sage.all import * >>> # needs sage.libs.ntl >>> R = Qq(Integer(4),Integer(5), names=('u',)); (u,) = R._first_ngens(1) >>> S = R['x']; (x,) = S._first_ngens(1) >>> v = GaussValuation(S) >>> v.F() 1
- augmentation_chain()[source]#
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]
>>> from sage.all import * >>> # needs sage.libs.ntl >>> R = Qq(Integer(4),Integer(5), names=('u',)); (u,) = R._first_ngens(1) >>> S = R['x']; (x,) = S._first_ngens(1) >>> v = GaussValuation(S) >>> v.augmentation_chain() [Gauss valuation induced by 2-adic valuation]
- change_domain(ring)[source]#
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
>>> from sage.all import * >>> v = ZZ.valuation(Integer(2)) >>> R = ZZ['x']; (x,) = R._first_ngens(1) >>> w = GaussValuation(R, v) >>> w.change_domain(QQ['x']) Gauss valuation induced by 2-adic valuation
- element_with_valuation(s)[source]#
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
>>> from sage.all import * >>> R = QQ['x']; (x,) = R._first_ngens(1) >>> v = GaussValuation(R, QQ.valuation(Integer(2))) >>> v.element_with_valuation(-Integer(2)) 1/4
- equivalence_unit(s, reciprocal=False)[source]#
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)
>>> from sage.all import * >>> # needs sage.libs.ntl >>> S = Qp(Integer(3),Integer(5))['x']; (x,) = S._first_ngens(1) >>> v = GaussValuation(S) >>> v.equivalence_unit(Integer(2)) 3^2 + O(3^7) >>> v.equivalence_unit(-Integer(2)) 3^-2 + O(3^3)
- extensions(ring)[source]#
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]
>>> from sage.all import * >>> v = ZZ.valuation(Integer(2)) >>> R = ZZ['x']; (x,) = R._first_ngens(1) >>> w = GaussValuation(R, v) >>> w.extensions(GaussianIntegers()['x']) # needs sage.rings.number_field [Gauss valuation induced by 2-adic valuation]
- is_gauss_valuation()[source]#
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
>>> from sage.all import * >>> # needs sage.libs.ntl >>> R = Qq(Integer(4),Integer(5), names=('u',)); (u,) = R._first_ngens(1) >>> S = R['x']; (x,) = S._first_ngens(1) >>> v = GaussValuation(S) >>> v.is_gauss_valuation() True
- is_trivial()[source]#
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
>>> from sage.all import * >>> R = QQ['x']; (x,) = R._first_ngens(1) >>> v = GaussValuation(R, valuations.TrivialValuation(QQ)) >>> v.is_trivial() True
- lift(F)[source]#
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
>>> from sage.all import * >>> # needs sage.libs.ntl >>> S = Qp(Integer(3),Integer(5))['x']; (x,) = S._first_ngens(1) >>> v = GaussValuation(S) >>> f = x**Integer(2) + Integer(2)*x + Integer(16) >>> F = v.reduce(f); F x^2 + 2*x + 1 >>> g = v.lift(F); g (1 + O(3^5))*x^2 + (2 + O(3^5))*x + 1 + O(3^5) >>> v.is_equivalent(f,g) True >>> g.parent() is v.domain() True
See also
- lift_to_key(F)[source]#
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
>>> from sage.all import * >>> R = QQ; (u,) = R._first_ngens(1) >>> S = R['x']; (x,) = S._first_ngens(1) >>> v = GaussValuation(S, QQ.valuation(Integer(2))) >>> y = v.residue_ring().gen() >>> f = v.lift_to_key(y**Integer(2) + y + Integer(1)); f x^2 + x + 1
- lower_bound(f)[source]#
Return a 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
>>> from sage.all import * >>> # needs sage.libs.ntl >>> R = Qq(Integer(4), Integer(5), names=('u',)); (u,) = R._first_ngens(1) >>> S = R['x']; (x,) = S._first_ngens(1) >>> v = GaussValuation(S) >>> v.lower_bound(Integer(1024)*x + Integer(2)) 1 >>> v(Integer(1024)*x + Integer(2)) 1
- monic_integral_model(G)[source]#
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))
>>> from sage.all import * >>> R = Qp(Integer(2), Integer(5))['x']; (x,) = R._first_ngens(1)# needs sage.libs.ntl >>> v = GaussValuation(R) # needs sage.libs.ntl >>> v.monic_integral_model(Integer(5)*x**Integer(2) + Integer(1)/Integer(2)*x + Integer(1)/Integer(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)[source]#
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
>>> from sage.all import * >>> # needs sage.libs.ntl >>> S = Qp(Integer(2),Integer(5))['x']; (x,) = S._first_ngens(1) >>> v = GaussValuation(S) >>> f = x**Integer(2) + Integer(2)*x + Integer(16) >>> v.reduce(f) x^2 >>> 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
>>> from sage.all import * >>> f = x**Integer(2)/Integer(2) # needs sage.libs.ntl >>> 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()[source]#
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 ...)
>>> from sage.all import * >>> S = Qp(Integer(2),Integer(5))['x']; (x,) = S._first_ngens(1)# needs sage.libs.ntl >>> v = GaussValuation(S) # needs sage.libs.ntl >>> v.residue_ring() # needs sage.libs.ntl Univariate Polynomial Ring in x over Finite Field of size 2 (using ...)
- restriction(ring)[source]#
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
>>> from sage.all import * >>> v = ZZ.valuation(Integer(2)) >>> R = ZZ['x']; (x,) = R._first_ngens(1) >>> w = GaussValuation(R, v) >>> w.restriction(ZZ) 2-adic valuation
- scale(scalar)[source]#
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
>>> from sage.all import * >>> R = QQ['x']; (x,) = R._first_ngens(1) >>> v = GaussValuation(R, QQ.valuation(Integer(2))) >>> Integer(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)[source]#
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)
>>> from sage.all import * >>> # needs sage.libs.ntl >>> R = Qq(Integer(4), Integer(5), names=('u',)); (u,) = R._first_ngens(1) >>> S = R['x']; (x,) = S._first_ngens(1) >>> v = GaussValuation(S) >>> f = x**Integer(10)/Integer(2) + Integer(1) >>> v.simplify(f) (2^-1 + O(2^4))*x^10 + 1 + O(2^5)
- uniformizer()[source]#
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
>>> from sage.all import * >>> S = QQ['x']; (x,) = S._first_ngens(1) >>> v = GaussValuation(S, QQ.valuation(Integer(5))) >>> v.uniformizer() 5 >>> v.uniformizer().parent() is S True
- upper_bound(f)[source]#
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
>>> from sage.all import * >>> # needs sage.libs.ntl >>> R = Qq(Integer(4), Integer(5), names=('u',)); (u,) = R._first_ngens(1) >>> S = R['x']; (x,) = S._first_ngens(1) >>> v = GaussValuation(S) >>> v.upper_bound(Integer(1024)*x + Integer(1)) 10 >>> v(Integer(1024)*x + Integer(1)) 0
- valuations(f, coefficients=None, call_error=False)[source]#
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]
>>> from sage.all import * >>> R = ZZ >>> S = R['x']; (x,) = S._first_ngens(1) >>> v = GaussValuation(S, R.valuation(Integer(2))) >>> f = x**Integer(2) + Integer(2)*x + Integer(16) >>> list(v.valuations(f)) [4, 1, 0]
- value_group()[source]#
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
>>> from sage.all import * >>> S = QQ['x']; (x,) = S._first_ngens(1) >>> v = GaussValuation(S, QQ.valuation(Integer(5))) >>> v.value_group() Additive Abelian Group generated by 1
- value_semigroup()[source]#
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
>>> from sage.all import * >>> S = QQ['x']; (x,) = S._first_ngens(1) >>> v = GaussValuation(S, QQ.valuation(Integer(5))) >>> v.value_semigroup() Additive Abelian Semigroup generated by -1, 1