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)

Bases: sage.rings.valuation.inductive_valuation.InductiveValuation

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

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

Bases: sage.rings.valuation.inductive_valuation.InductiveValuation, sage.rings.valuation.valuation.DiscreteValuation

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)

Bases: sage.rings.valuation.developing_valuation.DevelopingValuation

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:

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

Bases: sage.rings.valuation.inductive_valuation.FinalInductiveValuation, sage.rings.valuation.valuation.InfiniteDiscretePseudoValuation

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))
2-adic valuation

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

Bases: sage.rings.valuation.inductive_valuation.FiniteInductiveValuation, sage.rings.valuation.valuation.DiscreteValuation

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 ]

See also

augmented_valuation

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:

• 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 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 sqaurefree 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[1].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[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)
[[ 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[0][0])
True
sage: v.is_equivalent(F.prod(), f)
True