Augmented valuations on polynomial rings

Implements augmentations of (inductive) valuations.

AUTHORS:

• Julian Rüth (2013-04-15): initial version

EXAMPLES:

Starting from a Gauss valuation, we can create augmented valuations on polynomial rings:

sage: R.<x> = QQ[]
sage: v = GaussValuation(R, QQ.valuation(2))
sage: w = v.augmentation(x, 1); w
[ Gauss valuation induced by 2-adic valuation, v(x) = 1 ]
sage: w(x)
1

This also works for polynomial rings over base rings which are not fields. However, much of the functionality is only available over fields:

sage: R.<x> = ZZ[]
sage: v = GaussValuation(R, ZZ.valuation(2))
sage: w = v.augmentation(x, 1); w
[ Gauss valuation induced by 2-adic valuation, v(x) = 1 ]
sage: w(x)
1

REFERENCES:

Augmentations are described originally in [Mac1936I] and [Mac1936II]. An overview can also be found in Chapter 4 of [Rüt2014].

class sage.rings.valuation.augmented_valuation.AugmentedValuationFactory

Bases: sage.structure.factory.UniqueFactory

Factory for augmented valuations.

EXAMPLES:

This factory is not meant to be called directly. Instead, augmentation() of a valuation should be called:

sage: R.<x> = QQ[]
sage: v = GaussValuation(R, QQ.valuation(2))
sage: w = v.augmentation(x, 1) # indirect doctest

Note that trivial parts of the augmented valuation might be dropped, so you should not rely on _base_valuation to be the valuation you started with:

sage: ww = w.augmentation(x, 2)
sage: ww._base_valuation is v
True

create_key(base_valuation, phi, mu, check=True)

Create a key which uniquely identifies the valuation over base_valuation which sends phi to mu.

Note

The uniqueness that this factory provides is not why we chose to use a factory. However, it makes pickling and equality checks much easier. At the same time, going through a factory makes it easier to enforce that all instances correctly inherit methods from the parent Hom space.

create_object(version, key)

Create the augmented valuation represented by key.

class sage.rings.valuation.augmented_valuation.AugmentedValuation_base(parent, v, phi, mu)

Bases: sage.rings.valuation.inductive_valuation.InductiveValuation

An augmented valuation is a discrete valuation on a polynomial ring. It extends another discrete valuation \(v\) by setting the valuation of a polynomial \(f\) to the minumum of \(v(f_i)i\mu\) when writing \(f=\sum_i f_i\phi^i\).

INPUT:

• v – a InductiveValuation on a polynomial ring
• phi – a key polynomial over v
• mu – a rational number such that mu > v(phi) or infinity

EXAMPLES:

sage: K.<u> = CyclotomicField(5)
sage: R.<x> = K[]
sage: v = GaussValuation(R, K.valuation(2))
sage: w = v.augmentation(x, 1/2); w # indirect doctest
[ Gauss valuation induced by 2-adic valuation, v(x) = 1/2 ]
sage: ww = w.augmentation(x^4 + 2*x^2 + 4*u, 3); ww
[ Gauss valuation induced by 2-adic valuation, v(x) = 1/2, v(x^4 + 2*x^2 + 4*u) = 3 ]

E()

Return the ramification index of this valuation over its underlying Gauss valuation.

EXAMPLES:

sage: R.<u> = Qq(4, 5)
sage: S.<x> = R[]
sage: v = GaussValuation(S)

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

sage: w = v.augmentation(x, 1/2)
sage: w.E()
2

F()

Return the degree of the residue field extension of this valuation over the underlying Gauss valuation.

EXAMPLES:

sage: R.<u> = Qq(4, 5)
sage: S.<x> = R[]
sage: v = GaussValuation(S)

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

sage: w = v.augmentation(x, 1/2)
sage: w.F()
1

augmentation_chain()

Return a list with the chain of augmentations down to the underlying Gauss valuation.

EXAMPLES:

sage: R.<x> = QQ[]
sage: v = GaussValuation(R, QQ.valuation(2))
sage: w = v.augmentation(x, 1)
sage: w.augmentation_chain()
[[ Gauss valuation induced by 2-adic valuation, v(x) = 1 ],
     Gauss valuation induced by 2-adic valuation]

For performance reasons, (and to simplify the underlying implementation,) trivial augmentations might get dropped. You should not rely on augmentation_chain() to contain all the steps that you specified to create the current valuation:

sage: ww = w.augmentation(x, 2)
sage: ww.augmentation_chain()
[[ Gauss valuation induced by 2-adic valuation, v(x) = 2 ],
     Gauss valuation induced by 2-adic valuation]

change_domain(ring)

Return this valuation over ring.

EXAMPLES:

We can change the domain of an augmented valuation even if there is no coercion between rings:

sage: R.<x> = GaussianIntegers()[]
sage: v = GaussValuation(R, GaussianIntegers().valuation(2))
sage: v = v.augmentation(x, 1)
sage: v.change_domain(QQ['x'])
[ Gauss valuation induced by 2-adic valuation, v(x) = 1 ]

element_with_valuation(s)

Create an element of minimal degree and of valuation s.

INPUT:

• s – a rational number in the value group of this valuation

OUTPUT:

An element in the domain of this valuation

EXAMPLES:

sage: R.<u> = Qq(4, 5)
sage: S.<x> = R[]
sage: v = GaussValuation(S)
sage: w = v.augmentation(x^2 + x + u, 1/2)
sage: w.element_with_valuation(0)
1 + O(2^5)
sage: w.element_with_valuation(1/2)
(1 + O(2^5))*x^2 + (1 + O(2^5))*x + u + O(2^5)
sage: w.element_with_valuation(1)
2 + O(2^6)
sage: c = w.element_with_valuation(-1/2); c
(2^-1 + O(2^4))*x^2 + (2^-1 + O(2^4))*x + u*2^-1 + O(2^4)
sage: w(c)
-1/2
sage: w.element_with_valuation(1/3)
Traceback (most recent call last):
...
ValueError: s must be in the value group of the valuation but 1/3 is not in Additive Abelian Group generated by 1/2.

equivalence_unit(s, reciprocal=False)

Return an equivalence unit of minimal degree and valuation s.

INPUT:

• s – a rational number
• reciprocal – a boolean (default: False); whether or not to return the equivalence unit as the equivalence_reciprocal() of the equivalence unit of valuation -s.

OUTPUT:

A polynomial in the domain of this valuation which is_equivalence_unit() for this valuation.

EXAMPLES:

sage: R.<u> = Qq(4, 5)
sage: S.<x> = R[]
sage: v = GaussValuation(S)
sage: w = v.augmentation(x^2 + x + u, 1)

sage: w.equivalence_unit(0)
1 + O(2^5)
sage: w.equivalence_unit(-4)
2^-4 + O(2)

Since an equivalence unit is of effective degree zero, \(\phi\) must not divide it. Therefore, its valuation is in the value group of the base valuation:

sage: w = v.augmentation(x, 1/2)

sage: w.equivalence_unit(3/2)
Traceback (most recent call last):
...
ValueError: 3/2 is not in the value semigroup of 2-adic valuation
sage: w.equivalence_unit(1)
2 + O(2^6)

An equivalence unit might not be integral, even if s >= 0:

sage: w = v.augmentation(x, 3/4)
sage: ww = w.augmentation(x^4 + 8, 5)

sage: ww.equivalence_unit(1/2)
(2^-1 + O(2^4))*x^2

extensions(ring)

Return the extensions of this valuation to ring.

EXAMPLES:

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

sage: w.extensions(GaussianIntegers().fraction_field()['x'])
[[ Gauss valuation induced by 2-adic valuation, v(x^2 + x + 1) = 1 ]]

is_gauss_valuation()

Return whether this valuation is a Gauss valuation.

EXAMPLES:

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

sage: w.is_gauss_valuation()
False

is_negative_pseudo_valuation()

Return whether this valuation attains \(-\infty\).

EXAMPLES:

No element in the domain of an augmented valuation can have valuation \(-\infty\), so this method always returns False:

sage: R.<x> = QQ[]
sage: v = GaussValuation(R, valuations.TrivialValuation(QQ))
sage: w = v.augmentation(x, infinity)
sage: w.is_negative_pseudo_valuation()
False

is_trivial()

Return whether this valuation is trivial, i.e., zero outside of zero.

EXAMPLES:

sage: R.<x> = QQ[]
sage: v = GaussValuation(R, QQ.valuation(2))
sage: w = v.augmentation(x^2 + x + 1, 1)
sage: w.is_trivial()
False

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> = QQ[]
sage: v = GaussValuation(R, QQ.valuation(2))
sage: w = v.augmentation(x^2 + x + 1, 1)

sage: w.monic_integral_model(5*x^2 + 1/2*x + 1/4)
(Ring endomorphism of Univariate Polynomial Ring in x over Rational Field
   Defn: x |--> 1/2*x,
 Ring endomorphism of Univariate Polynomial Ring in x over Rational Field
   Defn: x |--> 2*x,
x^2 + 1/5*x + 1/5)

psi()

Return the minimal polynomial of the residue field extension of this valuation.

OUTPUT:

A polynomial in the residue ring of the base valuation

EXAMPLES:

sage: R.<u> = Qq(4, 5)
sage: S.<x> = R[]
sage: v = GaussValuation(S)

sage: w = v.augmentation(x^2 + x + u, 1/2)
sage: w.psi()
x^2 + x + u0

sage: ww = w.augmentation((x^2 + x + u)^2 + 2, 5/3)
sage: ww.psi()
x + 1

restriction(ring)

Return the restriction of this valuation to ring.

EXAMPLES:

sage: K = GaussianIntegers().fraction_field()
sage: R.<x> = K[]
sage: v = GaussValuation(R, K.valuation(2))
sage: w = v.augmentation(x^2 + x + 1, 1)

sage: w.restriction(QQ['x'])
[ Gauss valuation induced by 2-adic valuation, v(x^2 + x + 1) = 1 ]

scale(scalar)

Return this valuation scaled by scalar.

EXAMPLES:

sage: R.<x> = QQ[]
sage: v = GaussValuation(R, QQ.valuation(2))
sage: w = v.augmentation(x^2 + x + 1, 1)
sage: 3*w # indirect doctest
[ Gauss valuation induced by 3 * 2-adic valuation, v(x^2 + x + 1) = 3 ]

uniformizer()

Return a uniformizing element for this valuation.

EXAMPLES:

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

sage: w.uniformizer()
2

class sage.rings.valuation.augmented_valuation.FinalAugmentedValuation(parent, v, phi, mu)

Bases: sage.rings.valuation.augmented_valuation.AugmentedValuation_base, sage.rings.valuation.inductive_valuation.FinalInductiveValuation

An augmented valuation which can not be augmented anymore, either because it augments a trivial valuation or because it is infinite.

EXAMPLES:

sage: R.<x> = QQ[]
sage: v = GaussValuation(R, valuations.TrivialValuation(QQ))
sage: w = v.augmentation(x, 1)

lift(F)

Return a polynomial which reduces to F.

INPUT:

• F – an element of the residue_ring()

ALGORITHM:

We simply undo the steps performed in reduce().

OUTPUT:

A polynomial in the domain of the valuation with reduction F

EXAMPLES:

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

sage: w = v.augmentation(x, 1)
sage: w.lift(1/2)
1/2

sage: w = v.augmentation(x^2 + x + 1, infinity)
sage: w.lift(w.residue_ring().gen())
x

A case with non-trivial base valuation:

sage: R.<u> = Qq(4, 10)
sage: S.<x> = R[]
sage: v = GaussValuation(S)
sage: w = v.augmentation(x^2 + x + u, infinity)
sage: w.lift(w.residue_ring().gen())
(1 + O(2^10))*x

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

Reduce f module this valuation.

INPUT:

• f – an element in 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); this can be used to speed up the computation when the expansion of f is already known from a previous computation.
• valuations – the valuations of coefficients or None (default: None); ignored

OUTPUT:

an element of the residue_ring() of this valuation, the reduction modulo the ideal of elements of positive valuation

EXAMPLES:

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

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

sage: w = v.augmentation(x^2 + x + 1, infinity)
sage: w.reduce(x)
u1

residue_ring()

Return the residue ring of this valuation, i.e., the elements of non-negative valuation modulo the elements of positive valuation.

EXAMPLES:

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

sage: w = v.augmentation(x, 1)
sage: w.residue_ring()
Rational Field

sage: w = v.augmentation(x^2 + x + 1, infinity)
sage: w.residue_ring()
Number Field in u1 with defining polynomial x^2 + x + 1

An example with a non-trivial base valuation:

sage: v = GaussValuation(R, QQ.valuation(2))
sage: w = v.augmentation(x^2 + x + 1, infinity)
sage: w.residue_ring()
Finite Field in u1 of size 2^2

Since trivial extensions of finite fields are not implemented, the resulting ring might be identical to the residue ring of the underlying valuation:

sage: w = v.augmentation(x, infinity)
sage: w.residue_ring()
Finite Field of size 2

class sage.rings.valuation.augmented_valuation.FinalFiniteAugmentedValuation(parent, v, phi, mu)

Bases: sage.rings.valuation.augmented_valuation.FiniteAugmentedValuation, sage.rings.valuation.augmented_valuation.FinalAugmentedValuation

An augmented valuation which is discrete, i.e., which assigns a finite valuation to its last key polynomial, but which can not be further augmented.

EXAMPLES:

sage: R.<x> = QQ[]
sage: v = GaussValuation(R, valuations.TrivialValuation(QQ))
sage: w = v.augmentation(x, 1)

class sage.rings.valuation.augmented_valuation.FiniteAugmentedValuation(parent, v, phi, mu)

Bases: sage.rings.valuation.augmented_valuation.AugmentedValuation_base, sage.rings.valuation.inductive_valuation.FiniteInductiveValuation

A finite augmented valuation, i.e., an augmented valuation which is discrete, or equivalently an augmented valuation which assigns to its last key polynomial a finite valuation.

EXAMPLES:

sage: R.<u> = Qq(4, 5)
sage: S.<x> = R[]
sage: v = GaussValuation(S)
sage: w = v.augmentation(x^2 + x + u, 1/2)

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.

ALGORITHM:

The main cost of evaluation is the computation of the coefficients() of the phi()-adic expansion of f (which often leads to coefficient bloat.) So unless phi() is trivial, we fall back to valuation which this valuation augments since it is guaranteed to be smaller everywhere.

EXAMPLES:

sage: R.<u> = Qq(4, 5)
sage: S.<x> = R[]
sage: v = GaussValuation(S)
sage: w = v.augmentation(x^2 + x + u, 1/2)
sage: w.lower_bound(x^2 + x + u)
0

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

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 in the phi()-adic development 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 the coefficients in the \(\phi\)-adic expansion recursively. This often times leads to huge coefficients in the \(x\)-adic expansion (default: False, i.e., use an \(x\)-adic expansion.)

EXAMPLES:

sage: R.<u> = Qq(4, 5)
sage: S.<x> = R[]
sage: v = GaussValuation(S)
sage: w = v.augmentation(x^2 + x + u, 1/2)
sage: w.simplify(x^10/2 + 1, force=True)
(u + 1)*2^-1 + O(2^4)

Check that trac ticket #25607 has been resolved, i.e., the coefficients in the following example are small::`

sage: R.<x> = QQ[] sage: K.<a> = NumberField(x^3 + 6) sage: R.<x> = K[] sage: v = GaussValuation(R, K.valuation(2)) sage: v = v.augmentation(x, 3/2) sage: v = v.augmentation(x^2 + 8, 13/4) sage: v = v.augmentation(x^4 + 16*x^2 + 32*x + 64, 20/3) sage: F.<x> = FunctionField(K) sage: S.<y> = F[] sage: v = F.valuation(v) sage: G = y^2 - 2*x^5 + 8*x^3 + 80*x^2 + 128*x + 192 sage: v.mac_lane_approximants(G) [[ Gauss valuation induced by Valuation on rational function field induced by [ Gauss valuation induced by 2-adic valuation, v(x) = 3/2, v(x^2 + 8) = 13/4, v(x^4 + 16*x^2 + 32*x + 64) = 20/3 ], v(y + 4*x + 8) = 31/8 ]]

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.

ALGORITHM:

Any entry of valuations() serves as an upper bound. However, computation of the phi()-adic expansion of f is quite costly. Therefore, we produce an upper bound on the last entry of valuations(), namely the valuation of the leading coefficient of f plus the valuation of the appropriate power of phi().

EXAMPLES:

sage: R.<u> = Qq(4, 5)
sage: S.<x> = R[]
sage: v = GaussValuation(S)
sage: w = v.augmentation(x^2 + x + u, 1/2)
sage: w.upper_bound(x^2 + x + u)
1/2

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

Return the valuations of the \(f_i\phi^i\) in the expansion \(f=\sum_i 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:

An iterator over rational numbers (or infinity) \([v(f_0), v(f_1\phi), \dots]\)

EXAMPLES:

sage: R.<u> = Qq(4, 5)
sage: S.<x> = R[]
sage: v = GaussValuation(S)

sage: w = v.augmentation(x^2 + x + u, 1/2)
sage: list(w.valuations( x^2 + 1 ))
[0, 1/2]

sage: ww = w.augmentation((x^2 + x + u)^2 + 2, 5/3)
sage: list(ww.valuations( ((x^2 + x + u)^2 + 2)^3 ))
[+Infinity, +Infinity, +Infinity, 5]

value_group()

Return the value group of this valuation.

EXAMPLES:

sage: R.<u> = Qq(4, 5)
sage: S.<x> = R[]
sage: v = GaussValuation(S)

sage: w = v.augmentation(x^2 + x + u, 1/2)
sage: w.value_group()
Additive Abelian Group generated by 1/2

sage: ww = w.augmentation((x^2 + x + u)^2 + 2, 5/3)
sage: ww.value_group()
Additive Abelian Group generated by 1/6

value_semigroup()

Return the value semigroup of this valuation.

EXAMPLES:

sage: R.<u> = Zq(4, 5)
sage: S.<x> = R[]
sage: v = GaussValuation(S)

sage: w = v.augmentation(x^2 + x + u, 1/2)
sage: w.value_semigroup()
Additive Abelian Semigroup generated by 1/2

sage: ww = w.augmentation((x^2 + x + u)^2 + 2, 5/3)
sage: ww.value_semigroup()
Additive Abelian Semigroup generated by 1/2, 5/3

class sage.rings.valuation.augmented_valuation.InfiniteAugmentedValuation(parent, v, phi, mu)

Bases: sage.rings.valuation.augmented_valuation.FinalAugmentedValuation, sage.rings.valuation.inductive_valuation.InfiniteInductiveValuation

An augmented valuation which is infinite, i.e., which assigns valuation infinity to its last key polynomial (and which can therefore not be augmented further.)

EXAMPLES:

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

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: R.<u> = Qq(4, 5)
sage: S.<x> = R[]
sage: v = GaussValuation(S)
sage: w = v.augmentation(x^2 + x + u, infinity)
sage: w.lower_bound(x^2 + x + u)
+Infinity

simplify(f, error=None, force=False, effective_degree=None)

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 – ignored; for compatibility with other simplify methods

EXAMPLES:

sage: R.<u> = Qq(4, 5)
sage: S.<x> = R[]
sage: v = GaussValuation(S)
sage: w = v.augmentation(x^2 + x + u, infinity)
sage: w.simplify(x^10/2 + 1, force=True)
(u + 1)*2^-1 + O(2^4)

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: R.<u> = Qq(4, 5)
sage: S.<x> = R[]
sage: v = GaussValuation(S)
sage: w = v.augmentation(x^2 + x + u, infinity)
sage: w.upper_bound(x^2 + x + u)
+Infinity

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

Return the valuations of the \(f_i\phi^i\) in the expansion \(f=\sum_i 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:

An iterator over rational numbers (or infinity) \([v(f_0), v(f_1\phi), \dots]\)

EXAMPLES:

sage: R.<u> = Qq(4, 5)
sage: S.<x> = R[]
sage: v = GaussValuation(S)
sage: w = v.augmentation(x, infinity)
sage: list(w.valuations(x^2 + 1))
[0, +Infinity, +Infinity]

value_group()

Return the value group of this valuation.

EXAMPLES:

sage: R.<u> = Qq(4, 5)
sage: S.<x> = R[]
sage: v = GaussValuation(S)
sage: w = v.augmentation(x, infinity)
sage: w.value_group()
Additive Abelian Group generated by 1

value_semigroup()

Return the value semigroup of this valuation.

EXAMPLES:

sage: R.<u> = Zq(4, 5)
sage: S.<x> = R[]
sage: v = GaussValuation(S)
sage: w = v.augmentation(x, infinity)
sage: w.value_semigroup()
Additive Abelian Semigroup generated by 1

class sage.rings.valuation.augmented_valuation.NonFinalAugmentedValuation(parent, v, phi, mu)

Bases: sage.rings.valuation.augmented_valuation.AugmentedValuation_base, sage.rings.valuation.inductive_valuation.NonFinalInductiveValuation

An augmented valuation which can be augmented further.

EXAMPLES:

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

lift(F, report_coefficients=False)

Return a polynomial which reduces to F.

INPUT:

• F – an element of the residue_ring()
• report_coefficients – whether to return the coefficients of the phi()-adic expansion or the actual polynomial (default: False, i.e., return the polynomial)

OUTPUT:

A polynomial in the domain of the valuation with reduction F, monic if F is monic.

ALGORITHM:

Since this is the inverse of reduce(), we only have to go backwards through the algorithm described there.

EXAMPLES:

sage: R.<u> = Qq(4, 10)
sage: S.<x> = R[]
sage: v = GaussValuation(S)

sage: w = v.augmentation(x^2 + x + u, 1/2)
sage: y = w.residue_ring().gen()
sage: u1 = w.residue_ring().base().gen()

sage: w.lift(1)
1 + O(2^10)
sage: w.lift(0)
0
sage: w.lift(u1)
(1 + O(2^10))*x
sage: w.reduce(w.lift(y)) == y
True
sage: w.reduce(w.lift(y + u1 + 1)) == y + u1 + 1
True

sage: ww = w.augmentation((x^2 + x + u)^2 + 2, 5/3)
sage: y = ww.residue_ring().gen()
sage: u2 = ww.residue_ring().base().gen()

sage: ww.reduce(ww.lift(y)) == y
True
sage: ww.reduce(ww.lift(1)) == 1
True
sage: ww.reduce(ww.lift(y + 1)) == y +  1
True

A more complicated example:

sage: v = GaussValuation(S)
sage: w = v.augmentation(x^2 + x + u, 1)
sage: ww = w.augmentation((x^2 + x + u)^2 + 2*x*(x^2 + x + u) + 4*x, 3)
sage: u = ww.residue_ring().base().gen()

sage: F = ww.residue_ring()(u); F
u2
sage: f = ww.lift(F); f
(2^-1 + O(2^9))*x^2 + (2^-1 + O(2^9))*x + u*2^-1 + O(2^9)
sage: F == ww.reduce(f)
True

lift_to_key(F, check=True)

Lift the irreducible polynomial F to a key polynomial.

INPUT:

• F – an irreducible non-constant polynomial in the residue_ring() of this valuation
• check – whether or not to check correctness of F (default: True)

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

ALGORITHM:

We follow the algorithm described in Theorem 13.1 [Mac1936I] which, after a lift() of F, essentially shifts the valuations of all terms in the \(\phi\)-adic expansion up and then kills the leading coefficient.

EXAMPLES:

sage: R.<u> = Qq(4, 10)
sage: S.<x> = R[]
sage: v = GaussValuation(S)

sage: w = v.augmentation(x^2 + x + u, 1/2)
sage: y = w.residue_ring().gen()
sage: f = w.lift_to_key(y + 1); f
(1 + O(2^10))*x^4 + (2 + O(2^11))*x^3 + (1 + u*2 + O(2^10))*x^2 + (u*2 + O(2^11))*x + (u + 1) + u*2 + O(2^10)
sage: w.is_key(f)
True

A more complicated example:

sage: v = GaussValuation(S)
sage: w = v.augmentation(x^2 + x + u, 1)
sage: ww = w.augmentation((x^2 + x + u)^2 + 2*x*(x^2 + x + u) + 4*x, 3)

sage: u = ww.residue_ring().base().gen()
sage: y = ww.residue_ring().gen()
sage: f = ww.lift_to_key(y^3+y+u)
sage: f.degree()
12
sage: ww.is_key(f)
True

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

Reduce f module this valuation.

INPUT:

• f – an element in 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); this can be used to speed up the computation when the expansion of f is already known from a previous computation.
• valuations – the valuations of coefficients or None (default: None)

OUTPUT:

an element of the residue_ring() of this valuation, the reduction modulo the ideal of elements of positive valuation

ALGORITHM:

We follow the algorithm given in the proof of Theorem 12.1 of [Mac1936I]: If f has positive valuation, the reduction is simply zero. Otherwise, let \(f=\sum f_i\phi^i\) be the expansion of \(f\), as computed by coefficients(). Since the valuation is zero, the exponents \(i\) must all be multiples of \(\tau\), the index the value group of the base valuation in the value group of this valuation. Hence, there is an equivalence_unit() \(Q\) with the same valuation as \(\phi^\tau\). Let \(Q'\) be its equivalence_reciprocal(). Now, rewrite each term \(f_i\phi^{i\tau}=(f_iQ^i)(\phi^\tau Q^{-1})^i\); it turns out that the second factor in this expression is a lift of the generator of the residue_field(). The reduction of the first factor can be computed recursively.

EXAMPLES:

sage: R.<u> = Qq(4, 10)
sage: S.<x> = R[]
sage: v = GaussValuation(S)
sage: v.reduce(x)
x
sage: v.reduce(S(u))
u0

sage: w = v.augmentation(x^2 + x + u, 1/2)
sage: w.reduce(S.one())
1
sage: w.reduce(S(2))
0
sage: w.reduce(S(u))
u0
sage: w.reduce(x) # this gives the generator of the residue field extension of w over v
u1
sage: f = (x^2 + x + u)^2 / 2
sage: w.reduce(f)
x
sage: w.reduce(f + x + 1)
x + u1 + 1

sage: ww = w.augmentation((x^2 + x + u)^2 + 2, 5/3)
sage: g = ((x^2 + x + u)^2 + 2)^3 / 2^5
sage: ww.reduce(g)
x
sage: ww.reduce(f)
1
sage: ww.is_equivalent(f, 1)
True
sage: ww.reduce(f * g)
x
sage: ww.reduce(f + g)
x + 1

residue_ring()

Return the residue ring of this valuation, i.e., the elements of non-negative valuation modulo the elements of positive valuation.

EXAMPLES:

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

sage: w = v.augmentation(x^2 + x + 1, 1)
sage: w.residue_ring()
Univariate Polynomial Ring in x over Finite Field in u1 of size 2^2

Since trivial valuations of finite fields are not implemented, the resulting ring might be identical to the residue ring of the underlying valuation:

sage: w = v.augmentation(x, 1)
sage: w.residue_ring()
Univariate Polynomial Ring in x over Finite Field of size 2 (using ...)

class sage.rings.valuation.augmented_valuation.NonFinalFiniteAugmentedValuation(parent, v, phi, mu)

Bases: sage.rings.valuation.augmented_valuation.FiniteAugmentedValuation, sage.rings.valuation.augmented_valuation.NonFinalAugmentedValuation

An augmented valuation which is discrete, i.e., which assigns a finite valuation to its last key polynomial, and which can be augmented furter.

EXAMPLES:

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