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

>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> v = GaussValuation(R, QQ.valuation(Integer(2)))

R.<x> = QQ[]
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)

>>> from sage.all import *
>>> w = v.augmentation(x, Integer(1))
>>> w = w.augmentation(x**Integer(2) + Integer(2)*x + Integer(4), Integer(3))

w = v.augmentation(x, 1)
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)[source]

Bases: InductiveValuation

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

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

Bases: InductiveValuation, 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))

>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> v = GaussValuation(R, valuations.TrivialValuation(QQ))

R.<x> = QQ[]
v = GaussValuation(R, valuations.TrivialValuation(QQ))
extensions(other)[source]

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]

>>> from sage.all import *
>>> R = ZZ['x']; (x,) = R._first_ngens(1)
>>> v = GaussValuation(R, valuations.TrivialValuation(ZZ))
>>> K = FunctionField(QQ, names=('x',)); (x,) = K._first_ngens(1)
>>> v.extensions(K)
[Trivial valuation on Rational Field]

R.<x> = ZZ[]
v = GaussValuation(R, valuations.TrivialValuation(ZZ))
K.<x> = FunctionField(QQ)
v.extensions(K)
class sage.rings.valuation.inductive_valuation.InductiveValuation(parent, phi)[source]

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

>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> v = GaussValuation(R, QQ.valuation(Integer(5)))

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

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

>>> from sage.all import *
>>> # needs sage.libs.ntl
>>> R = Qq(Integer(4),Integer(5), names=('u',)); (u,) = R._first_ngens(1)
>>> S = R['x']; (x,) = S._first_ngens(1)
>>> v = GaussValuation(S)
>>> v.E()
1

# needs sage.libs.ntl
R.<u> = Qq(4,5)
S.<x> = R[]
v = GaussValuation(S)
v.E()
F()[source]

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

>>> from sage.all import *
>>> # needs sage.libs.ntl
>>> R = Qq(Integer(4),Integer(5), names=('u',)); (u,) = R._first_ngens(1)
>>> S = R['x']; (x,) = S._first_ngens(1)
>>> v = GaussValuation(S)
>>> v.F()
1

# needs sage.libs.ntl
R.<u> = Qq(4,5)
S.<x> = R[]
v = GaussValuation(S)
v.F()
augmentation_chain()[source]

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]

>>> from sage.all import *
>>> # needs sage.libs.ntl
>>> R = Qq(Integer(4),Integer(5), names=('u',)); (u,) = R._first_ngens(1)
>>> S = R['x']; (x,) = S._first_ngens(1)
>>> v = GaussValuation(S)
>>> v.augmentation_chain()
[Gauss valuation induced by 2-adic valuation]

# needs sage.libs.ntl
R.<u> = Qq(4,5)
S.<x> = R[]
v = GaussValuation(S)
v.augmentation_chain()
element_with_valuation(s)[source]

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

>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> v = GaussValuation(R, QQ.valuation(Integer(2)))
>>> v.element_with_valuation(-Integer(2))
1/4

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

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

>>> from sage.all import *
>>> R = ZZ['x']; (x,) = R._first_ngens(1)
>>> v = GaussValuation(R, ZZ.valuation(Integer(2)))
>>> v.element_with_valuation(-Integer(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

R.<x> = ZZ[]
v = GaussValuation(R, ZZ.valuation(2))
v.element_with_valuation(-2)
equivalence_reciprocal(f, coefficients=None, valuations=None, check=True)[source]

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

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

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

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

>>> from sage.all import *
>>> # needs sage.libs.ntl
>>> R = Qq(Integer(4),Integer(5), names=('u',)); (u,) = R._first_ngens(1)
>>> S = R['x']; (x,) = S._first_ngens(1)
>>> v = GaussValuation(S)
>>> v = v.augmentation(x**Integer(2) + x + u, Integer(1))
>>> f = Integer(2)*x + u
>>> h = v.equivalence_reciprocal(f); h
(u + 1) + O(2^5)
>>> v.is_equivalent(f*h, Integer(1))
True

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

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

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

# needs sage.libs.ntl
v = v.augmentation((x^2 + x + u)^2 + 2*x*(x^2 + x + u) + 4*x, 3)
h = v.equivalence_reciprocal(f); h
v.is_equivalent(f*h, 1)
equivalence_unit(s, reciprocal=False)[source]

Return an equivalence unit of valuation s.

INPUT:

  • s – an element of the value_group()

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

>>> from sage.all import *
>>> # needs sage.libs.ntl
>>> S = Qp(Integer(3),Integer(5))['x']; (x,) = S._first_ngens(1)
>>> v = GaussValuation(S)
>>> v.equivalence_unit(Integer(2))
3^2 + O(3^7)
>>> v.equivalence_unit(-Integer(2))
3^-2 + O(3^3)

# needs sage.libs.ntl
S.<x> = Qp(3,5)[]
v = GaussValuation(S)
v.equivalence_unit(2)
v.equivalence_unit(-2)

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

>>> from sage.all import *
>>> v = ZZ.valuation(Integer(2))
>>> R = ZZ['x']; (x,) = R._first_ngens(1)
>>> w = GaussValuation(R, v)
>>> w.equivalence_unit(Integer(1))
2
>>> w.equivalence_unit(-Integer(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

v = ZZ.valuation(2)
R.<x> = ZZ[]
w = GaussValuation(R, v)
w.equivalence_unit(1)
w.equivalence_unit(-1)
is_equivalence_unit(f, valuations=None)[source]

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

>>> from sage.all import *
>>> # needs sage.libs.ntl
>>> R = Zp(Integer(2),Integer(5))
>>> S = R['x']; (x,) = S._first_ngens(1)
>>> v = GaussValuation(S)
>>> v.is_equivalence_unit(x)
False
>>> v.is_equivalence_unit(S.zero())
False
>>> v.is_equivalence_unit(Integer(2)*x + Integer(1))
True

# needs sage.libs.ntl
R = Zp(2,5)
S.<x> = R[]
v = GaussValuation(S)
v.is_equivalence_unit(x)
v.is_equivalence_unit(S.zero())
v.is_equivalence_unit(2*x + 1)
is_gauss_valuation()[source]

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

>>> from sage.all import *
>>> # needs sage.libs.ntl
>>> R = Qq(Integer(4),Integer(5), names=('u',)); (u,) = R._first_ngens(1)
>>> S = R['x']; (x,) = S._first_ngens(1)
>>> v = GaussValuation(S)
>>> v.is_gauss_valuation()
True

# needs sage.libs.ntl
R.<u> = Qq(4,5)
S.<x> = R[]
v = GaussValuation(S)
v.is_gauss_valuation()
monic_integral_model(G)[source]

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)

>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> v = GaussValuation(R, QQ.valuation(Integer(2)))
>>> v.monic_integral_model(Integer(5)*x**Integer(2) + Integer(1)/Integer(2)*x + Integer(1)/Integer(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)

R.<x> = QQ[]
v = GaussValuation(R, QQ.valuation(2))
v.monic_integral_model(5*x^2 + 1/2*x + 1/4)
mu()[source]

Return the valuation of phi().

EXAMPLES:

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

>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> v = GaussValuation(R, QQ.valuation(Integer(2)))
>>> v.mu()
0

R.<x> = QQ[]
v = GaussValuation(R, QQ.valuation(2))
v.mu()
class sage.rings.valuation.inductive_valuation.InfiniteInductiveValuation(parent, base_valuation)[source]

Bases: FinalInductiveValuation, 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)

>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> v = GaussValuation(R, QQ.valuation(Integer(2)))
>>> w = v.augmentation(x**Integer(2) + x + Integer(1), infinity)

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

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

>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> v = GaussValuation(R, QQ.valuation(Integer(2)))
>>> w = v.augmentation(x**Integer(2) + x + Integer(1), infinity)
>>> w.change_domain(R.quo(x**Integer(2) + x + Integer(1)))
2-adic valuation

R.<x> = QQ[]
v = GaussValuation(R, QQ.valuation(2))
w = v.augmentation(x^2 + x + 1, infinity)
w.change_domain(R.quo(x^2 + x + 1))
class sage.rings.valuation.inductive_valuation.NonFinalInductiveValuation(parent, phi)[source]

Bases: FiniteInductiveValuation, DiscreteValuation

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)

>>> from sage.all import *
>>> # needs sage.libs.ntl
>>> R = Qq(Integer(4),Integer(5), names=('u',)); (u,) = R._first_ngens(1)
>>> S = R['x']; (x,) = S._first_ngens(1)
>>> v = GaussValuation(S)
>>> v = v.augmentation(x**Integer(2) + x + u, Integer(1))

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

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

>>> from sage.all import *
>>> # needs sage.libs.ntl
>>> R = Qq(Integer(4),Integer(5), names=('u',)); (u,) = R._first_ngens(1)
>>> S = R['x']; (x,) = S._first_ngens(1)
>>> v = GaussValuation(S)
>>> v = v.augmentation(x**Integer(2) + x + u, Integer(1))
>>> v = v.augmentation((x**Integer(2) + x + u)**Integer(2) + Integer(2)*x*(x**Integer(2) + x + u) + Integer(4)*x, Integer(3))
>>> 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 ]

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

See also

augmented_valuation

equivalence_decomposition(f, assume_not_equivalence_unit=False, coefficients=None, valuations=None, compute_unit=True, degree_bound=None)[source]

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

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

# needs sage.libs.ntl
R.<u> = Qq(4,10)
S.<x> = R[]
v = GaussValuation(S)
v.equivalence_decomposition(S.zero())
v.equivalence_decomposition(S.one())
v.equivalence_decomposition(x^2+2)
v.equivalence_decomposition(x^2+1)

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)

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

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

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)

>>> from sage.all import *
>>> f = x * (x**Integer(2) + Integer(1))                                                     # needs sage.libs.ntl
>>> F = w.equivalence_decomposition(f); F                                 # needs sage.libs.ntl
(1 + O(2^10))*x
>>> F.unit()                                                              # needs sage.libs.ntl
1 + O(2^10)

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

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

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

# needs sage.libs.ntl
v = v.augmentation(x^2 + x + u, 1)
v = v.augmentation((x^2 + x + u)^2 + 2*x*(x^2 + x + u) + 4*x, 3)
v.equivalence_decomposition(x)
F = v.equivalence_decomposition( v.phi() )
len(F)
F = v.equivalence_decomposition( v.phi() * (x^4 + 4*x^3 + (7 + 2*u)*x^2 + (8 + 4*u)*x + 1023 + 3*u) )
len(F)
is_equivalence_irreducible(f, coefficients=None, valuations=None)[source]

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

>>> from sage.all import *
>>> # needs sage.libs.ntl
>>> R = Qq(Integer(4),Integer(5), names=('u',)); (u,) = R._first_ngens(1)
>>> S = R['x']; (x,) = S._first_ngens(1)
>>> v = GaussValuation(S)
>>> v.is_equivalence_irreducible(x)
True
>>> v.is_equivalence_irreducible(x**Integer(2))
False
>>> v.is_equivalence_irreducible(x**Integer(2) + Integer(2))
False

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

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

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

# needs sage.libs.ntl
R.<u> = Qq(4, 5)
S.<x> = R[]
v = GaussValuation(S)
v.is_key(x)
v.is_key(2*x, explain=True)
v.is_key(x^2, explain=True)
w = v.augmentation(x, 1)
w.is_key(x + 1, explain = True)
is_minimal(f, assume_equivalence_irreducible=False)[source]

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

>>> from sage.all import *
>>> # needs sage.libs.ntl
>>> R = Qq(Integer(4), Integer(5), names=('u',)); (u,) = R._first_ngens(1)
>>> S = R['x']; (x,) = S._first_ngens(1)
>>> v = GaussValuation(S)
>>> v.is_minimal(x + Integer(1))
True
>>> w = v.augmentation(x, Integer(1))
>>> w.is_minimal(x + Integer(1))
False

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

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

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

# needs sage.libs.ntl
R.<u> = Qq(4,10)
S.<x> = R[]
v = GaussValuation(S)
y = v.residue_ring().gen()
u0 = v.residue_ring().base_ring().gen()
f = v.lift_to_key(y^2 + y + u0); f
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)[source]

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

>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> v = QQ.valuation(Integer(2))
>>> f = x**Integer(36) + Integer(1160)/Integer(81)*x**Integer(31) + Integer(9920)/Integer(27)*x**Integer(30) + Integer(1040)/Integer(81)*x**Integer(26) + Integer(52480)/Integer(81)*x**Integer(25) + Integer(220160)/Integer(81)*x**Integer(24) - Integer(5120)/Integer(81)*x**Integer(21) - Integer(143360)/Integer(81)*x**Integer(20) - Integer(573440)/Integer(81)*x**Integer(19) + Integer(12451840)/Integer(81)*x**Integer(18) - Integer(266240)/Integer(567)*x**Integer(16) - Integer(20316160)/Integer(567)*x**Integer(15) - Integer(198737920)/Integer(189)*x**Integer(14) - Integer(1129840640)/Integer(81)*x**Integer(13) - Integer(1907359744)/Integer(27)*x**Integer(12) + Integer(8192)/Integer(81)*x**Integer(11) + Integer(655360)/Integer(81)*x**Integer(10) + Integer(5242880)/Integer(21)*x**Integer(9) + Integer(2118123520)/Integer(567)*x**Integer(8) + Integer(15460204544)/Integer(567)*x**Integer(7) + Integer(6509559808)/Integer(81)*x**Integer(6) - Integer(16777216)/Integer(567)*x**Integer(2) - Integer(268435456)/Integer(567)*x - Integer(1073741824)/Integer(567)
>>> 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 ]]

R.<x> = QQ[]
v = QQ.valuation(2)
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
v.mac_lane_approximants(f)                                            # needs sage.geometry.polyhedron

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

>>> from sage.all import *
>>> v0 = GaussValuation(R, v)
>>> 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 ]]

v0 = GaussValuation(R, v)
V1 = sorted(v0.mac_lane_step(f)); V1                                  # needs sage.geometry.polyhedron

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

>>> from sage.all import *
>>> V1[Integer(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 ]]

V1[1].mac_lane_step(f)                                                # needs sage.geometry.polyhedron

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

>>> from sage.all import *
>>> V1[Integer(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 ]]

V1[1].mac_lane_step(f, allow_equivalent_key=False)                    # needs sage.geometry.polyhedron
minimal_representative(f)[source]

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

>>> from sage.all import *
>>> # needs sage.libs.ntl
>>> R = Qq(Integer(4),Integer(10), names=('u',)); (u,) = R._first_ngens(1)
>>> S = R['x']; (x,) = S._first_ngens(1)
>>> v = GaussValuation(S)
>>> v.minimal_representative(x + Integer(2))
(1 + O(2^10))*x

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

# needs sage.libs.ntl
R.<u> = Qq(4,10)
S.<x> = R[]
v = GaussValuation(S)
v.minimal_representative(x + 2)
# needs sage.libs.ntl
v = v.augmentation(x, 1)
v.minimal_representative(x + 2)
f = x^3 + 6*x + 4
F = v.minimal_representative(f); F
v.is_minimal(F[0][0])
v.is_equivalent(F.prod(), f)