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

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

class sage.rings.valuation.gauss_valuation.GaussValuationFactory

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

create_key(domain, v=None)

Normalize and check the parameters to create a Gauss valuation.

create_object(version, key, **extra_args)

Create a Gauss valuation from normalized parameters.

class sage.rings.valuation.gauss_valuation.GaussValuation_generic(parent, v)

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

E()

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

F()

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

augmentation_chain()

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]

change_domain(ring)

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

element_with_valuation(s)

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

equivalence_unit(s, reciprocal=False)

Return an equivalence unit of valuation s.

INPUT:

• s – an element of the value_group()

• reciprocal – a 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)

extensions(ring)

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]

is_gauss_valuation()

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

is_trivial()

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

lift(F)

Return a lift of F.

INPUT:

• F – a polynomial over the residue_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

See also

reduce()

lift_to_key(F)

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

lower_bound(f)

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

monic_integral_model(G)

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

reduce(f, check=True, degree_bound=None, coefficients=None, valuations=None)

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

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

See also

lift()

residue_ring()

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

restriction(ring)

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

scale(scalar)

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

simplify(f, error=None, force=False, size_heuristic_bound=32, effective_degree=None, phiadic=True)

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)

uniformizer()

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

upper_bound(f)

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

valuations(f, coefficients=None, call_error=False)

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:

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]

value_group()

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

value_semigroup()

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