# 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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)
sage: F = w.equivalence_decomposition(x^2+1); F
(1 + O(2^10))*x^2 + 1 + O(2^10)
sage: F.unit()
(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)
sage: F = w.equivalence_decomposition(f); F
(1 + O(2^10))*x
sage: F.unit()
1 + O(2^10)


Examples over an iterated unramified extension:

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: 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: 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: 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: 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)
[[ 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
[[ 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.mac_lane_step(f)
[[ 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 but also two other valuations that we had seen in the previous step and that are greater than V1. To ignore such trivial augmentations, we can set allow_equivalent_key:

sage: V1.mac_lane_step(f, allow_equivalent_key=False)
[[ 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: 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: 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)
True
sage: v.is_equivalent(F.prod(), f)
True