# 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]#

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]