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 ring

  • v – a valuation on the base ring of domain, the underlying valuation on the constants of the polynomial ring (if unspecified take the natural valuation on the valued ring domain.)

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
create_key(domain, v=None)[source]

Normalize and check the parameters to create a Gauss valuation.

create_object(version, key, **extra_args)[source]

Create a Gauss valuation from normalized parameters.

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 the value_group()

  • reciprocal – boolean (default: False); whether or not to return the equivalence unit as the equivalence_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:

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

reduce()

lift_to_key(F)[source]

Lift the irreducible polynomial F from the residue_ring() to a key polynomial over this valuation.

INPUT:

  • F – an irreducible non-constant monic polynomial in residue_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 valuation

  • check – whether or not to check whether f has nonnegative 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 of f as produced by coefficients() or None (default: None); ignored

  • valuations – the valuations of coefficients or None (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

lift()

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 of f (or strictly greater than error if set.)

INPUT:

  • f – an element in the domain of this valuation

  • error – a rational, infinity, or None (default: None), the error allowed to introduce through the simplification

  • force – whether or not to simplify f even if there is heuristically no change in the coefficient size of f expected (default: False)

  • effective_degree – when set, assume that coefficients beyond effective_degree can be safely dropped (default: None)

  • size_heuristic_bound – when force 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 valuation

  • coefficients – the coefficients of f as produced by coefficients() or None (default: None); this can be used to speed up the computation when the expansion of f 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 of f (default: False)

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