Valuations on polynomial rings based on \(\phi\)-adic expansions#
This file implements a base class for discrete valuations on polynomial rings, defined by a \(\phi\)-adic expansion.
AUTHORS:
Julian Rüth (2013-04-15): initial version
EXAMPLES:
The Gauss valuation
is a simple example of a valuation that relies on
\(\phi\)-adic expansions:
sage: R.<x> = QQ[]
sage: v = GaussValuation(R, QQ.valuation(2))
>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> v = GaussValuation(R, QQ.valuation(Integer(2)))
In this case, \(\phi = x\), so the expansion simply lists the coefficients of the polynomial:
sage: f = x^2 + 2*x + 2
sage: list(v.coefficients(f))
[2, 2, 1]
>>> from sage.all import *
>>> f = x**Integer(2) + Integer(2)*x + Integer(2)
>>> list(v.coefficients(f))
[2, 2, 1]
Often only the first few coefficients are necessary in computations, so for performance reasons, coefficients are computed lazily:
sage: v.coefficients(f)
<generator object ...coefficients at 0x...>
>>> from sage.all import *
>>> v.coefficients(f)
<generator object ...coefficients at 0x...>
Another example of a DevelopingValuation
is an augmented
valuation
:
sage: w = v.augmentation(x^2 + x + 1, 3)
>>> from sage.all import *
>>> w = v.augmentation(x**Integer(2) + x + Integer(1), Integer(3))
Here, the expansion lists the remainders of repeated division by \(x^2 + x + 1\):
sage: list(w.coefficients(f))
[x + 1, 1]
>>> from sage.all import *
>>> list(w.coefficients(f))
[x + 1, 1]
- class sage.rings.valuation.developing_valuation.DevelopingValuation(parent, phi)[source]#
Bases:
DiscretePseudoValuation
Abstract base class for a discrete valuation of polynomials defined over the polynomial ring
domain
by the \(\phi\)-adic development.EXAMPLES:
sage: R.<x> = QQ[] sage: v = GaussValuation(R, QQ.valuation(7))
>>> from sage.all import * >>> R = QQ['x']; (x,) = R._first_ngens(1) >>> v = GaussValuation(R, QQ.valuation(Integer(7)))
- coefficients(f)[source]#
Return the \(\phi\)-adic expansion of
f
.INPUT:
f
– a monic polynomial in the domain of this valuation
OUTPUT:
An iterator \(f_0, f_1, \dots, f_n\) of polynomials in the domain of this valuation such that \(f=\sum_i f_i\phi^i\)
EXAMPLES:
sage: # needs sage.libs.ntl sage: R = Qp(2,5) sage: S.<x> = R[] sage: v = GaussValuation(S) sage: f = x^2 + 2*x + 3 sage: list(v.coefficients(f)) # note that these constants are in the polynomial ring [1 + 2 + O(2^5), 2 + O(2^6), 1 + O(2^5)] sage: v = v.augmentation( x^2 + x + 1, 1) sage: list(v.coefficients(f)) [(1 + O(2^5))*x + 2 + O(2^5), 1 + O(2^5)]
>>> from sage.all import * >>> # needs sage.libs.ntl >>> R = Qp(Integer(2),Integer(5)) >>> S = R['x']; (x,) = S._first_ngens(1) >>> v = GaussValuation(S) >>> f = x**Integer(2) + Integer(2)*x + Integer(3) >>> list(v.coefficients(f)) # note that these constants are in the polynomial ring [1 + 2 + O(2^5), 2 + O(2^6), 1 + O(2^5)] >>> v = v.augmentation( x**Integer(2) + x + Integer(1), Integer(1)) >>> list(v.coefficients(f)) [(1 + O(2^5))*x + 2 + O(2^5), 1 + O(2^5)]
- effective_degree(f, valuations=None)[source]#
Return the effective degree of
f
with respect to this valuation.The effective degree of \(f\) is the largest \(i\) such that the valuation of \(f\) and the valuation of \(f_i\phi^i\) in the development \(f=\sum_j f_j\phi^j\) coincide (see [Mac1936II] p.497.)
INPUT:
f
– a non-zero 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.effective_degree(x) 1 sage: v.effective_degree(2*x + 1) 0
>>> from sage.all import * >>> # needs sage.libs.ntl >>> R = Zp(Integer(2),Integer(5)) >>> S = R['x']; (x,) = S._first_ngens(1) >>> v = GaussValuation(S) >>> v.effective_degree(x) 1 >>> v.effective_degree(Integer(2)*x + Integer(1)) 0
- newton_polygon(f, valuations=None)[source]#
Return the Newton polygon of the \(\phi\)-adic development of
f
.INPUT:
f
– a polynomial in the domain of this valuation
EXAMPLES:
sage: # needs sage.libs.ntl sage: R = Qp(2,5) sage: S.<x> = R[] sage: v = GaussValuation(S) sage: f = x^2 + 2*x + 3 sage: v.newton_polygon(f) # needs sage.geometry.polyhedron Finite Newton polygon with 2 vertices: (0, 0), (2, 0) sage: v = v.augmentation( x^2 + x + 1, 1) sage: v.newton_polygon(f) # needs sage.geometry.polyhedron Finite Newton polygon with 2 vertices: (0, 0), (1, 1) sage: v.newton_polygon( f * v.phi()^3 ) # needs sage.geometry.polyhedron Finite Newton polygon with 2 vertices: (3, 3), (4, 4)
>>> from sage.all import * >>> # needs sage.libs.ntl >>> R = Qp(Integer(2),Integer(5)) >>> S = R['x']; (x,) = S._first_ngens(1) >>> v = GaussValuation(S) >>> f = x**Integer(2) + Integer(2)*x + Integer(3) >>> v.newton_polygon(f) # needs sage.geometry.polyhedron Finite Newton polygon with 2 vertices: (0, 0), (2, 0) >>> v = v.augmentation( x**Integer(2) + x + Integer(1), Integer(1)) >>> v.newton_polygon(f) # needs sage.geometry.polyhedron Finite Newton polygon with 2 vertices: (0, 0), (1, 1) >>> v.newton_polygon( f * v.phi()**Integer(3) ) # needs sage.geometry.polyhedron Finite Newton polygon with 2 vertices: (3, 3), (4, 4)
- phi()[source]#
Return the polynomial \(\phi\), the key polynomial of this valuation.
EXAMPLES:
sage: R = Zp(2,5) sage: S.<x> = R[] # needs sage.libs.ntl sage: v = GaussValuation(S) # needs sage.libs.ntl sage: v.phi() # needs sage.libs.ntl (1 + O(2^5))*x
>>> from sage.all import * >>> R = Zp(Integer(2),Integer(5)) >>> S = R['x']; (x,) = S._first_ngens(1)# needs sage.libs.ntl >>> v = GaussValuation(S) # needs sage.libs.ntl >>> v.phi() # needs sage.libs.ntl (1 + O(2^5))*x
- valuations(f)[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 valuation
OUTPUT:
A list, each entry a rational numbers or infinity, the valuations of \(f_0, f_1\phi, \dots\)
EXAMPLES:
sage: # needs sage.libs.ntl sage: R = Qp(2,5) sage: S.<x> = R[] sage: v = GaussValuation(S, R.valuation()) sage: f = x^2 + 2*x + 16 sage: list(v.valuations(f)) [4, 1, 0]
>>> from sage.all import * >>> # needs sage.libs.ntl >>> R = Qp(Integer(2),Integer(5)) >>> S = R['x']; (x,) = S._first_ngens(1) >>> v = GaussValuation(S, R.valuation()) >>> f = x**Integer(2) + Integer(2)*x + Integer(16) >>> list(v.valuations(f)) [4, 1, 0]