# Inductive valuations on polynomial rings#

This module provides functionality for inductive valuations, i.e., finite chains of augmented valuations on top of a Gauss valuation.

AUTHORS:

• Julian Rüth (2016-11-01): initial version

EXAMPLES:

A Gauss valuation is an example of an inductive valuation:

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


Generally, an inductive valuation is an augmentation of an inductive valuation, i.e., a valuation that was created from a Gauss valuation in a finite number of augmentation steps:

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


REFERENCES:

Inductive valuations are originally discussed in [Mac1936I] and [Mac1936II]. An introduction is also given in Chapter 4 of [Rüt2014].

class sage.rings.valuation.inductive_valuation.FinalInductiveValuation(parent, phi)#

Abstract base class for an inductive valuation which cannot be augmented further.

class sage.rings.valuation.inductive_valuation.FiniteInductiveValuation(parent, phi)#

Abstract base class for iterated augmented valuations on top of a Gauss valuation which is a discrete valuation, i.e., the last key polynomial has finite valuation.

EXAMPLES:

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

extensions(other)#

Return the extensions of this valuation to other.

EXAMPLES:

sage: R.<x> = ZZ[]
sage: v = GaussValuation(R, valuations.TrivialValuation(ZZ))
sage: K.<x> = FunctionField(QQ)
sage: v.extensions(K)
[Trivial valuation on Rational Field]

class sage.rings.valuation.inductive_valuation.InductiveValuation(parent, phi)#

Abstract base class for iterated augmented valuations on top of a Gauss valuation.

EXAMPLES:

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

E()#

Return the ramification index of this valuation over its 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.E()
1

F()#

Return the residual degree of this valuation over its Gauss extension.

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]

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


Depending on the base ring, an element of valuation s might not exist:

sage: R.<x> = ZZ[]
sage: v = GaussValuation(R, ZZ.valuation(2))
sage: v.element_with_valuation(-2)
Traceback (most recent call last):
...
ValueError: s must be in the value semigroup of this valuation
but -2 is not in Additive Abelian Semigroup generated by 1

equivalence_reciprocal(f, coefficients=None, valuations=None, check=True)#

Return an equivalence reciprocal of f.

An equivalence reciprocal of $$f$$ is a polynomial $$h$$ such that $$f\cdot h$$ is equivalent to 1 modulo this valuation (see [Mac1936II] p.497.)

INPUT:

• f – a polynomial in the domain of this valuation which is an equivalence_unit()

• coefficients – the coefficients of f in the phi()-adic expansion if known (default: None)

• valuations – the valuations of coefficients if known (default: None)

• check – whether or not to check the validity of f (default: True)

Warning

This method may not work over $$p$$-adic rings due to problems with the xgcd implementation there.

EXAMPLES:

sage: # needs sage.libs.ntl
sage: R = Zp(3,5)
sage: S.<x> = R[]
sage: v = GaussValuation(S)
sage: f = 3*x + 2
sage: h = v.equivalence_reciprocal(f); h
2 + O(3^5)
sage: v.is_equivalent(f*h, 1)
True


In an extended valuation over an extension field:

sage: # needs sage.libs.ntl
sage: R.<u> = Qq(4,5)
sage: S.<x> = R[]
sage: v = GaussValuation(S)
sage: v = v.augmentation(x^2 + x + u, 1)
sage: f = 2*x + u
sage: h = v.equivalence_reciprocal(f); h
(u + 1) + O(2^5)
sage: v.is_equivalent(f*h, 1)
True


Extending the valuation once more:

sage: # needs sage.libs.ntl
sage: v = v.augmentation((x^2 + x + u)^2 + 2*x*(x^2 + x + u) + 4*x, 3)
sage: h = v.equivalence_reciprocal(f); h
(u + 1) + O(2^5)
sage: v.is_equivalent(f*h, 1)
True

equivalence_unit(s, reciprocal=False)#

Return an equivalence unit of valuation s.

INPUT:

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)


Note that this might fail for negative s if the domain is not defined over a field:

sage: v = ZZ.valuation(2)
sage: R.<x> = ZZ[]
sage: w = GaussValuation(R, v)
sage: w.equivalence_unit(1)
2
sage: w.equivalence_unit(-1)
Traceback (most recent call last):
...
ValueError: s must be in the value semigroup of this valuation
but -1 is not in Additive Abelian Semigroup generated by 1

is_equivalence_unit(f, valuations=None)#

Return whether the polynomial f is an equivalence unit, i.e., an element of effective_degree() zero (see [Mac1936II] p.497.)

INPUT:

• f – a 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.is_equivalence_unit(x)
False
sage: v.is_equivalence_unit(S.zero())
False
sage: v.is_equivalence_unit(2*x + 1)
True

is_gauss_valuation()#

Return whether this valuation is a Gauss valuation over the domain.

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

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

mu()#

Return the valuation of phi().

EXAMPLES:

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

class sage.rings.valuation.inductive_valuation.InfiniteInductiveValuation(parent, base_valuation)#

Abstract base class for an inductive valuation which is not discrete, i.e., which assigns infinite valuation to its last key polynomial.

EXAMPLES:

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

change_domain(ring)#

Return this valuation over ring.

EXAMPLES:

We can turn an infinite valuation into a valuation on the quotient:

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

class sage.rings.valuation.inductive_valuation.NonFinalInductiveValuation(parent, phi)#

Abstract base class for iterated augmented valuations on top of a Gauss valuation which can be extended further through augmentation().

EXAMPLES:

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

augmentation(phi, mu, check=True)#

Return the inductive valuation which extends this valuation by mapping phi to mu.

INPUT:

• phi – a polynomial in the domain of this valuation; this must be a key polynomial, see is_key() for properties of key polynomials.

• mu – a rational number or infinity, the valuation of phi in the extended valuation

• check – a boolean (default: True), whether or not to check the correctness of the parameters

EXAMPLES:

sage: # needs sage.libs.ntl
sage: R.<u> = Qq(4,5)
sage: S.<x> = R[]
sage: v = GaussValuation(S)
sage: v = v.augmentation(x^2 + x + u, 1)
sage: v = v.augmentation((x^2 + x + u)^2 + 2*x*(x^2 + x + u) + 4*x, 3)
sage: v
[ Gauss valuation induced by 2-adic valuation,
v((1 + O(2^5))*x^2 + (1 + O(2^5))*x + u + O(2^5)) = 1,
v((1 + O(2^5))*x^4
+ (2^2 + O(2^6))*x^3
+ (1 + (u + 1)*2 + O(2^5))*x^2
+ ((u + 1)*2^2 + O(2^6))*x
+ (u + 1) + (u + 1)*2 + (u + 1)*2^2 + (u + 1)*2^3 + (u + 1)*2^4 + O(2^5)) = 3 ]

equivalence_decomposition(f, assume_not_equivalence_unit=False, coefficients=None, valuations=None, compute_unit=True, degree_bound=None)#

Return an equivalence decomposition of f, i.e., a polynomial $$g(x)=e(x)\prod_i \phi_i(x)$$ with $$e(x)$$ an equivalence unit and the $$\phi_i$$ key polynomials such that f is_equivalent() to $$g$$.

INPUT:

• f – a non-zero polynomial in the domain of this valuation

• assume_not_equivalence_unit – whether or not to assume that f is not an equivalence unit (default: False)

• coefficients – the coefficients of f in the phi()-adic expansion if known (default: None)

• valuations – the valuations of coefficients if known (default: None)

• compute_unit – whether or not to compute the unit part of the decomposition (default: True)

• degree_bound – a bound on the degree of the _equivalence_reduction() of f (default: None)

ALGORITHM:

We use the algorithm described in Theorem 4.4 of [Mac1936II]. After removing all factors $$\phi$$ from a polynomial $$f$$, there is an equivalence unit $$R$$ such that $$Rf$$ has valuation zero. Now $$Rf$$ can be factored as $$\prod_i \alpha_i$$ over the residue_field(). Lifting all $$\alpha_i$$ to key polynomials $$\phi_i$$ gives $$Rf=\prod_i R_i f_i$$ for suitable equivalence units $$R_i$$ (see lift_to_key()). Taking $$R'$$ an equivalence_reciprocal() of $$R$$, we have $$f$$ equivalent to $$(R'\prod_i R_i)\prod_i\phi_i$$.

EXAMPLES:

sage: # needs sage.libs.ntl
sage: R.<u> = Qq(4,10)
sage: S.<x> = R[]
sage: v = GaussValuation(S)
sage: v.equivalence_decomposition(S.zero())
Traceback (most recent call last):
...
ValueError: equivalence decomposition of zero is not defined
sage: v.equivalence_decomposition(S.one())
1 + O(2^10)
sage: v.equivalence_decomposition(x^2+2)
((1 + O(2^10))*x)^2
sage: v.equivalence_decomposition(x^2+1)
((1 + O(2^10))*x + 1 + O(2^10))^2


A polynomial that is an equivalence unit, is returned as the unit part of a Factorization, leading to a unit non-minimal degree:

sage: w = v.augmentation(x, 1)                                              # needs sage.libs.ntl
sage: F = w.equivalence_decomposition(x^2+1); F                             # needs sage.libs.ntl
(1 + O(2^10))*x^2 + 1 + O(2^10)
sage: F.unit()                                                              # needs sage.libs.ntl
(1 + O(2^10))*x^2 + 1 + O(2^10)


However, if the polynomial has a non-unit factor, then the unit might be replaced by a factor of lower degree:

sage: f = x * (x^2 + 1)                                                     # needs sage.libs.ntl
sage: F = w.equivalence_decomposition(f); F                                 # needs sage.libs.ntl
(1 + O(2^10))*x
sage: F.unit()                                                              # needs sage.libs.ntl
1 + O(2^10)


Examples over an iterated unramified extension:

sage: # needs sage.libs.ntl
sage: v = v.augmentation(x^2 + x + u, 1)
sage: v = v.augmentation((x^2 + x + u)^2 + 2*x*(x^2 + x + u) + 4*x, 3)
sage: v.equivalence_decomposition(x)
(1 + O(2^10))*x
sage: F = v.equivalence_decomposition( v.phi() )
sage: len(F)
1
sage: F = v.equivalence_decomposition( v.phi() * (x^4 + 4*x^3 + (7 + 2*u)*x^2 + (8 + 4*u)*x + 1023 + 3*u) )
sage: len(F)
2

is_equivalence_irreducible(f, coefficients=None, valuations=None)#

Return whether the polynomial f is equivalence-irreducible, i.e., whether its equivalence_decomposition() is trivial.

ALGORITHM:

We use the same algorithm as in equivalence_decomposition() we just do not lift the result to key polynomials.

INPUT:

• f – a non-constant polynomial in the domain of this valuation

EXAMPLES:

sage: # needs sage.libs.ntl
sage: R.<u> = Qq(4,5)
sage: S.<x> = R[]
sage: v = GaussValuation(S)
sage: v.is_equivalence_irreducible(x)
True
sage: v.is_equivalence_irreducible(x^2)
False
sage: v.is_equivalence_irreducible(x^2 + 2)
False

is_key(phi, explain=False, assume_equivalence_irreducible=False)#

Return whether phi is a key polynomial for this valuation, i.e., whether it is monic, whether it is_equivalence_irreducible(), and whether it is is_minimal().

INPUT:

• phi – a polynomial in the domain of this valuation

• explain – a boolean (default: False), if True, return a string explaining why phi is not a key polynomial

EXAMPLES:

sage: # needs sage.libs.ntl
sage: R.<u> = Qq(4, 5)
sage: S.<x> = R[]
sage: v = GaussValuation(S)
sage: v.is_key(x)
True
sage: v.is_key(2*x, explain=True)
(False, 'phi must be monic')
sage: v.is_key(x^2, explain=True)
(False, 'phi must be equivalence irreducible')
sage: w = v.augmentation(x, 1)
sage: w.is_key(x + 1, explain = True)
(False, 'phi must be minimal')

is_minimal(f, assume_equivalence_irreducible=False)#

Return whether the polynomial f is minimal with respect to this valuation.

A polynomial $$f$$ is minimal with respect to $$v$$ if it is not a constant and any non-zero polynomial $$h$$ which is $$v$$-divisible by $$f$$ has at least the degree of $$f$$.

A polynomial $$h$$ is $$v$$-divisible by $$f$$ if there is a polynomial $$c$$ such that $$fc$$ is_equivalent() to $$h$$.

ALGORITHM:

Based on Theorem 9.4 of [Mac1936II].

EXAMPLES:

sage: # needs sage.libs.ntl
sage: R.<u> = Qq(4, 5)
sage: S.<x> = R[]
sage: v = GaussValuation(S)
sage: v.is_minimal(x + 1)
True
sage: w = v.augmentation(x, 1)
sage: w.is_minimal(x + 1)
False

lift_to_key(F)#

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

INPUT:

OUTPUT:

A polynomial $$f$$ in the domain of this valuation which is a key polynomial for this valuation and which is such that an augmentation() with this polynomial adjoins a root of F to the resulting residue_ring().

More specifically, if F is not the generator of the residue ring, then multiplying f with the equivalence_reciprocal() of the equivalence_unit() of the valuation of f, produces a unit which reduces to F.

EXAMPLES:

sage: # needs sage.libs.ntl
sage: R.<u> = Qq(4,10)
sage: S.<x> = R[]
sage: v = GaussValuation(S)
sage: y = v.residue_ring().gen()
sage: u0 = v.residue_ring().base_ring().gen()
sage: f = v.lift_to_key(y^2 + y + u0); f
(1 + O(2^10))*x^2 + (1 + O(2^10))*x + u + O(2^10)

mac_lane_step(G, principal_part_bound=None, assume_squarefree=False, assume_equivalence_irreducible=False, report_degree_bounds_and_caches=False, coefficients=None, valuations=None, check=True, allow_equivalent_key=True)#

Perform an approximation step towards the squarefree monic non-constant integral polynomial G which is not an equivalence unit.

This performs the individual steps that are used in mac_lane_approximants().

INPUT:

• G – a squarefree monic non-constant integral polynomial G which is not an equivalence unit

• principal_part_bound – an integer or None (default: None), a bound on the length of the principal part, i.e., the section of negative slope, of the Newton polygon of G

• assume_squarefree – whether or not to assume that G is squarefree (default: False)

• assume_equivalence_irreducible – whether or not to assume that G is equivalence irreducible (default: False)

• report_degree_bounds_and_caches – whether or not to include internal state with the returned value (used by mac_lane_approximants() to speed up sequential calls)

• coefficients – the coefficients of G in the phi()-adic expansion if known (default: None)

• valuations – the valuations of coefficients if known (default: None)

• check – whether to check that G is a squarefree monic non-constant integral polynomial and not an equivalence unit (default: True)

• allow_equivalent_key – whether to return valuations which end in essentially the same key polynomial as this valuation but have a higher valuation assigned to that key polynomial (default: True)

EXAMPLES:

We can use this method to perform the individual steps of mac_lane_approximants():

sage: R.<x> = QQ[]
sage: v = QQ.valuation(2)
sage: f = x^36 + 1160/81*x^31 + 9920/27*x^30 + 1040/81*x^26 + 52480/81*x^25 + 220160/81*x^24 - 5120/81*x^21 - 143360/81*x^20 - 573440/81*x^19 + 12451840/81*x^18 - 266240/567*x^16 - 20316160/567*x^15 - 198737920/189*x^14 - 1129840640/81*x^13 - 1907359744/27*x^12 + 8192/81*x^11 + 655360/81*x^10 + 5242880/21*x^9 + 2118123520/567*x^8 + 15460204544/567*x^7 + 6509559808/81*x^6 - 16777216/567*x^2 - 268435456/567*x - 1073741824/567
sage: v.mac_lane_approximants(f)                                            # needs sage.geometry.polyhedron
[[ Gauss valuation induced by 2-adic valuation, v(x + 2056) = 23/2 ],
[ Gauss valuation induced by 2-adic valuation, v(x) = 11/9 ],
[ Gauss valuation induced by 2-adic valuation, v(x) = 2/5, v(x^5 + 4) = 7/2 ],
[ Gauss valuation induced by 2-adic valuation, v(x) = 3/5, v(x^10 + 8*x^5 + 64) = 7 ],
[ Gauss valuation induced by 2-adic valuation, v(x) = 3/5, v(x^5 + 8) = 5 ]]


Starting from the Gauss valuation, a MacLane step branches off with some linear key polynomials in the above example:

sage: v0 = GaussValuation(R, v)
sage: V1 = sorted(v0.mac_lane_step(f)); V1                                  # needs sage.geometry.polyhedron
[[ Gauss valuation induced by 2-adic valuation, v(x) = 2/5 ],
[ Gauss valuation induced by 2-adic valuation, v(x) = 3/5 ],
[ Gauss valuation induced by 2-adic valuation, v(x) = 11/9 ],
[ Gauss valuation induced by 2-adic valuation, v(x) = 3 ]]


The computation of MacLane approximants would now perform a MacLane step on each of these branches, note however, that a direct call to this method might produce some unexpected results:

sage: V1[1].mac_lane_step(f)                                                # needs sage.geometry.polyhedron
[[ Gauss valuation induced by 2-adic valuation, v(x) = 3/5, v(x^5 + 8) = 5 ],
[ Gauss valuation induced by 2-adic valuation, v(x) = 3/5, v(x^10 + 8*x^5 + 64) = 7 ],
[ Gauss valuation induced by 2-adic valuation, v(x) = 3 ],
[ Gauss valuation induced by 2-adic valuation, v(x) = 11/9 ]]


Note how this detected the two augmentations of V1[1] but also two other valuations that we had seen in the previous step and that are greater than V1[1]. To ignore such trivial augmentations, we can set allow_equivalent_key:

sage: V1[1].mac_lane_step(f, allow_equivalent_key=False)                    # needs sage.geometry.polyhedron
[[ Gauss valuation induced by 2-adic valuation, v(x) = 3/5, v(x^5 + 8) = 5 ],
[ Gauss valuation induced by 2-adic valuation, v(x) = 3/5, v(x^10 + 8*x^5 + 64) = 7 ]]

minimal_representative(f)#

Return a minimal representative for f, i.e., a pair $$e, a$$ such that f is_equivalent() to $$e a$$, $$e$$ is an equivalence unit, and $$a$$ is_minimal() and monic.

INPUT:

• f – a non-zero polynomial which is not an equivalence unit

OUTPUT:

A factorization which has $$e$$ as its unit and $$a$$ as its unique factor.

ALGORITHM:

We use the algorithm described in the proof of Lemma 4.1 of [Mac1936II]. In the expansion $$f=\sum_i f_i\phi^i$$ take $$e=f_i$$ for the largest $$i$$ with $$f_i\phi^i$$ minimal (see effective_degree()). Let $$h$$ be the equivalence_reciprocal() of $$e$$ and take $$a$$ given by the terms of minimal valuation in the expansion of $$e f$$.

EXAMPLES:

sage: # needs sage.libs.ntl
sage: R.<u> = Qq(4,10)
sage: S.<x> = R[]
sage: v = GaussValuation(S)
sage: v.minimal_representative(x + 2)
(1 + O(2^10))*x

sage: # needs sage.libs.ntl
sage: v = v.augmentation(x, 1)
sage: v.minimal_representative(x + 2)
(1 + O(2^10))*x + 2 + O(2^11)
sage: f = x^3 + 6*x + 4
sage: F = v.minimal_representative(f); F
(2 + 2^2 + O(2^11)) * ((1 + O(2^10))*x + 2 + O(2^11))
sage: v.is_minimal(F[0][0])
True
sage: v.is_equivalent(F.prod(), f)
True