Valuations on polynomial rings based on $\varphi$-adic expansions

This file implements a base class for discrete valuations on polynomial rings, defined by a $\varphi$-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 $\varphi$-adic expansions:

Sage

sage: R.<x> = QQ[]
sage: v = GaussValuation(R, QQ.valuation(2))

Python

>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> v = GaussValuation(R, QQ.valuation(Integer(2)))

Sage Live

R.<x> = QQ[]
v = GaussValuation(R, QQ.valuation(2))

In this case, $\varphi =x$, so the expansion simply lists the coefficients of the polynomial:

Sage

sage: f = x^2 + 2*x + 2
sage: list(v.coefficients(f))
[2, 2, 1]

Python

>>> from sage.all import *
>>> f = x**Integer(2) + Integer(2)*x + Integer(2)
>>> list(v.coefficients(f))
[2, 2, 1]

Sage Live

f = x^2 + 2*x + 2
list(v.coefficients(f))

Often only the first few coefficients are necessary in computations, so for performance reasons, coefficients are computed lazily:

Sage

sage: v.coefficients(f)
<generator object ...coefficients at 0x...>

Python

>>> from sage.all import *
>>> v.coefficients(f)
<generator object ...coefficients at 0x...>

Sage Live

v.coefficients(f)

Another example of a DevelopingValuation is an augmented valuation:

Sage

sage: w = v.augmentation(x^2 + x + 1, 3)

Python

>>> from sage.all import *
>>> w = v.augmentation(x**Integer(2) + x + Integer(1), Integer(3))

Sage Live

w = v.augmentation(x^2 + x + 1, 3)

Here, the expansion lists the remainders of repeated division by $x^2+x+1$:

Sage

sage: list(w.coefficients(f))
[x + 1, 1]

Python

>>> from sage.all import *
>>> list(w.coefficients(f))
[x + 1, 1]

Sage Live

list(w.coefficients(f))

class sage.rings.valuation.developing_valuation.DevelopingValuation(parent, phi)

Bases: DiscretePseudoValuation

Abstract base class for a discrete valuation of polynomials defined over the polynomial ring domain by the $\varphi$-adic development.

EXAMPLES:

Sage

sage: R.<x> = QQ[]
sage: v = GaussValuation(R, QQ.valuation(7))

Python

>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> v = GaussValuation(R, QQ.valuation(Integer(7)))

Sage Live

R.<x> = QQ[]
v = GaussValuation(R, QQ.valuation(7))

coefficients(f)

Return the $\varphi$-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{\varphi }^i$

EXAMPLES:

Sage

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

Python

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

Sage Live

# needs sage.libs.ntl
R = Qp(2,5)
S.<x> = R[]
v = GaussValuation(S)
f = x^2 + 2*x + 3
list(v.coefficients(f))  # note that these constants are in the polynomial ring
v = v.augmentation( x^2 + x + 1, 1)
list(v.coefficients(f))

effective_degree(f, valuations=None)

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{\varphi }^i$ in the development $f=\sum _j{f}_j{\varphi }^j$ coincide (see [Mac1936II] p.497.)

INPUT:

• f – a nonzero polynomial in the domain of this valuation

EXAMPLES:

Sage

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

Python

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

Sage Live

# needs sage.libs.ntl
R = Zp(2,5)
S.<x> = R[]
v = GaussValuation(S)
v.effective_degree(x)
v.effective_degree(2*x + 1)

newton_polygon(f, valuations=None)

Return the Newton polygon of the $\varphi$-adic development of f.

INPUT:

• f – a polynomial in the domain of this valuation

EXAMPLES:

Sage

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)

Python

>>> 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)

Sage Live

# needs sage.libs.ntl
R = Qp(2,5)
S.<x> = R[]
v = GaussValuation(S)
f = x^2 + 2*x + 3
v.newton_polygon(f)                                                   # needs sage.geometry.polyhedron
v = v.augmentation( x^2 + x + 1, 1)
v.newton_polygon(f)                                                   # needs sage.geometry.polyhedron
v.newton_polygon( f * v.phi()^3 )                                     # needs sage.geometry.polyhedron

phi()

Return the polynomial $\varphi$, the key polynomial of this valuation.

EXAMPLES:

Sage

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

Python

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

Sage Live

R = Zp(2,5)
S.<x> = R[]                                                           # needs sage.libs.ntl
v = GaussValuation(S)                                                 # needs sage.libs.ntl
v.phi()                                                               # needs sage.libs.ntl

Use augmentation_chain() to obtain the sequence of key polynomials of an InductiveValuation:

Sage

sage: R.<x> = QQ[]
sage: v = GaussValuation(R, QQ.valuation(2))
sage: v = v.augmentation(x, 1)
sage: v = v.augmentation(x^2 + 2*x + 4, 3)

sage: v
[ Gauss valuation induced by 2-adic valuation, v(x) = 1, v(x^2 + 2*x + 4) = 3 ]

sage: [w.phi() for w in v.augmentation_chain()[:-1]]
[x^2 + 2*x + 4, x]

Python

>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> v = GaussValuation(R, QQ.valuation(Integer(2)))
>>> v = v.augmentation(x, Integer(1))
>>> v = v.augmentation(x**Integer(2) + Integer(2)*x + Integer(4), Integer(3))

>>> v
[ Gauss valuation induced by 2-adic valuation, v(x) = 1, v(x^2 + 2*x + 4) = 3 ]

>>> [w.phi() for w in v.augmentation_chain()[:-Integer(1)]]
[x^2 + 2*x + 4, x]

Sage Live

R.<x> = QQ[]
v = GaussValuation(R, QQ.valuation(2))
v = v.augmentation(x, 1)
v = v.augmentation(x^2 + 2*x + 4, 3)
v
[w.phi() for w in v.augmentation_chain()[:-1]]

A similar approach can be used to obtain the key polynomials and their corresponding valuations:

Sage

sage: [(w.phi(), w.mu()) for w in v.augmentation_chain()[:-1]]
[(x^2 + 2*x + 4, 3), (x, 1)]

Python

>>> from sage.all import *
>>> [(w.phi(), w.mu()) for w in v.augmentation_chain()[:-Integer(1)]]
[(x^2 + 2*x + 4, 3), (x, 1)]

Sage Live

[(w.phi(), w.mu()) for w in v.augmentation_chain()[:-1]]

valuations(f)

Return the valuations of the $f_i{\varphi }^i$ in the expansion $f=\sum f_i{\varphi }^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\varphi ,\dots$

EXAMPLES:

Sage

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]

Python

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

Sage Live

# needs sage.libs.ntl
R = Qp(2,5)
S.<x> = R[]
v = GaussValuation(S, R.valuation())
f = x^2 + 2*x + 16
list(v.valuations(f))

Make live