Coverage for local/lib/python2.7/site-packages/sage/rings/valuation/inductive_valuation.py : 83%

# -*- coding: utf-8 -*- 

r""" 

Inductive valuations on polynomial rings 

This module provides functionality for inductive valuations, i.e., finite 

chains of :mod:`augmented valuations <sage.rings.valuation.augmented_valuation>` on top of a :mod:`Gauss valuation <sage.rings.valuation.gauss_valuation>`. 

AUTHORS: 

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

EXAMPLES: 

A :mod:`Gauss valuation <sage.rings.valuation.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]_. 

""" 

#***************************************************************************** 

# Copyright (C) 2016-2017 Julian Rüth <julian.rueth@fsfe.org> 

# 

# Distributed under the terms of the GNU General Public License (GPL) 

# as published by the Free Software Foundation; either version 2 of 

# the License, or (at your option) any later version. 

# http://www.gnu.org/licenses/ 

#***************************************************************************** 

from __future__ import absolute_import 

from .valuation import DiscreteValuation, InfiniteDiscretePseudoValuation 

from .developing_valuation import DevelopingValuation 

from sage.misc.cachefunc import cached_method 

from sage.misc.abstract_method import abstract_method 

class InductiveValuation(DevelopingValuation): 

r""" 

Abstract base class for iterated :mod:`augmented valuations <sage.rings.valuation.augmented_valuation>` on top of a :mod:`Gauss valuation <sage.rings.valuation.gauss_valuation>`. 

EXAMPLES:: 

sage: R.<x> = QQ[] 

sage: v = GaussValuation(R, QQ.valuation(5)) 

TESTS:: 

sage: TestSuite(v).run() # long time 

""" 

def is_equivalence_unit(self, f, valuations=None): 

r""" 

Return whether the polynomial ``f`` is an equivalence unit, i.e., an 

element of :meth:`~sage.rings.valuation.developing_valuation.DevelopingValuation.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 

""" 

f = self.domain().coerce(f) 

if f.is_zero(): 

return False 

return self.effective_degree(f, valuations=valuations) == 0 

def equivalence_reciprocal(self, f, coefficients=None, valuations=None, check=True): 

r""" 

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 

:meth:`equivalence_unit` 

- ``coefficients`` -- the coefficients of ``f`` in the :meth:`~sage.rings.valuation.developing_valuation.DevelopingValuation.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 

TESTS: 

A case that caused problems at some point:: 

sage: K = Qp(2, 4) 

sage: R.<x> = K[] 

sage: L.<a> = K.extension(x^4 + 4*x^3 + 6*x^2 + 4*x + 2) 

sage: R.<t> = L[] 

sage: v = GaussValuation(R) 

sage: w = v.augmentation(t + 1, 5/16) 

sage: w = w.augmentation(t^4 + (a^8 + a^12 + a^14 + a^16 + a^17 + a^19 + a^20 + a^23)*t^3 + (a^6 + a^9 + a^13 + a^15 + a^18 + a^19 + a^21)*t^2 + a^10*t + 1 + a^4 + a^5 + a^8 + a^13 + a^14 + a^15, 17/8) 

sage: f = a^-15*t^2 + (a^-11 + a^-9 + a^-6 + a^-5 + a^-3 + a^-2)*t + a^-15 

sage: f_ = w.equivalence_reciprocal(f) 

sage: w.reduce(f*f_) 

1 

sage: f = f.parent()([f[0], f[1].add_bigoh(1), f[2]]) 

sage: f_ = w.equivalence_reciprocal(f) 

sage: w.reduce(f*f_) 

1 

""" 

f = self.domain().coerce(f) 

if check: 

if coefficients is None: 

coefficients = list(self.coefficients(f)) 

if valuations is None: 

valuations = list(self.valuations(f, coefficients=coefficients)) 

if not self.is_equivalence_unit(f, valuations=valuations): 

raise ValueError("f must be an equivalence unit but %r is not"%(f,)) 

if coefficients is None: 

e0 = next(self.coefficients(f)) 

else: 

e0 = coefficients[0] 

# f is an equivalence unit, its valuation is given by the constant coefficient 

if valuations is None: 

vf = self(e0) 

else: 

vf = valuations[0] 

e0 = self.simplify(e0, error=vf) 

s_ = self.equivalence_unit(-vf) 

residue = self.reduce(e0 * s_) 

if not isinstance(self, FinalInductiveValuation): 

assert residue.is_constant() 

residue = residue[0] 

h = self.lift(~residue) * s_ 

h = self.simplify(h, -vf) 

# it might be the case that f*h has non-zero valuation because h has 

# insufficient precision, so we must not assert that here but only 

# until we lifted to higher precision 

# We do not actually need g*phi + h*e0 = 1, it is only important that 

# the RHS is 1 in reduction. 

# This allows us to do two things: 

# - we may lift h to arbitrary precision 

# - we can add anything which times e0 has positive valuation, e.g., we 

# may drop coefficients of positive valuation 

h = h.map_coefficients(lambda c:_lift_to_maximal_precision(c)) 

return h 

@cached_method 

def mu(self): 

r""" 

Return the valuation of :meth:`~sage.rings.valuation.developing_valuation.DevelopingValuation.phi`. 

EXAMPLES:: 

sage: R.<x> = QQ[] 

sage: v = GaussValuation(R, QQ.valuation(2)) 

sage: v.mu() 

0 

""" 

return self(self.phi()) 

@abstract_method 

def equivalence_unit(self, s, reciprocal=False): 

""" 

Return an equivalence unit of valuation ``s``. 

INPUT: 

- ``s`` -- an element of the :meth:`~sage.rings.valuation.valuation_space.DiscretePseudoValuationSpace.ElementMethods.value_group` 

- ``reciprocal`` -- a boolean (default: ``False``); whether or not to 

return the equivalence unit as the :meth:`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 

""" 

@abstract_method 

def augmentation_chain(self): 

r""" 

Return a list with the chain of augmentations down to the underlying 

:mod:`Gauss valuation <sage.rings.valuation.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] 

""" 

@abstract_method 

def is_gauss_valuation(self): 

r""" 

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 

""" 

@abstract_method 

def E(self): 

""" 

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 

""" 

@abstract_method 

def F(self): 

""" 

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 

""" 

@abstract_method 

def monic_integral_model(self, G): 

r""" 

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) 

""" 

@abstract_method 

def element_with_valuation(self, s): 

r""" 

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 

""" 

def _test_element_with_valuation_inductive_valuation(self, **options): 

r""" 

Test the correctness of :meth:`element_with_valuation`. 

EXAMPLES:: 

sage: R.<x> = QQ[] 

sage: v = GaussValuation(R, QQ.valuation(2)) 

sage: v._test_element_with_valuation_inductive_valuation() 

""" 

tester = self._tester(**options) 

chain = self.augmentation_chain() 

for s in tester.some_elements(self.value_group().some_elements()): 

try: 

R = self.element_with_valuation(s) 

except (ValueError, NotImplementedError): 

# this is often not possible unless the underlying ring of 

# constants is a field 

from sage.categories.fields import Fields 

if self.domain().base() not in Fields(): 

continue 

raise 

tester.assertEqual(self(R), s) 

if chain != [self]: 

base = chain[1] 

if s in base.value_group(): 

S = base.element_with_valuation(s) 

tester.assertEqual(self(S), s) 

tester.assertGreaterEqual(S.degree(), R.degree()) 

def _test_EF(self, **options): 

r""" 

Test the correctness of :meth:`E` and :meth:`F`. 

EXAMPLES:: 

sage: R.<u> = Qq(4,5) 

sage: S.<x> = R[] 

sage: v = GaussValuation(S) 

sage: v._test_EF() 

""" 

tester = self._tester(**options) 

chain = self.augmentation_chain() 

for w,v in zip(chain, chain[1:]): 

from sage.rings.all import infinity, ZZ 

if w(w.phi()) is infinity: 

tester.assertEqual(w.E(), v.E()) 

tester.assertIn(w.E(), ZZ) 

tester.assertIn(w.F(), ZZ) 

tester.assertGreaterEqual(w.E(), v.E()) 

tester.assertGreaterEqual(w.F(), v.F()) 

def _test_augmentation_chain(self, **options): 

r""" 

Test the correctness of :meth:`augmentation_chain`. 

EXAMPLES:: 

sage: R.<x> = QQ[] 

sage: v = GaussValuation(R, valuations.TrivialValuation(QQ)) 

sage: v._test_augmentation_chain() 

""" 

tester = self._tester(**options) 

chain = self.augmentation_chain() 

tester.assertIs(chain[0], self) 

tester.assertTrue(chain[-1].is_gauss_valuation()) 

for w,v in zip(chain, chain[1:]): 

tester.assertGreaterEqual(w, v) 

def _test_equivalence_unit(self, **options): 

r""" 

Test the correctness of :meth:`lift_to_key`. 

EXAMPLES:: 

sage: R.<x> = QQ[] 

sage: v = GaussValuation(R, valuations.TrivialValuation(QQ)) 

sage: v._test_equivalence_unit() 

""" 

tester = self._tester(**options) 

if self.is_gauss_valuation(): 

value_group = self.value_group() 

else: 

value_group = self.augmentation_chain()[1].value_group() 

for s in tester.some_elements(value_group.some_elements()): 

try: 

R = self.equivalence_unit(s) 

except (ValueError, NotImplementedError): 

# this is often not possible unless the underlying ring of 

# constants is a field 

from sage.categories.fields import Fields 

if self.domain().base() not in Fields(): 

continue 

raise 

tester.assertIs(R.parent(), self.domain()) 

tester.assertEqual(self(R), s) 

tester.assertTrue(self.is_equivalence_unit(R)) 

def _test_is_equivalence_unit(self, **options): 

r""" 

Test the correctness of :meth:`is_equivalence_unit`. 

EXAMPLES:: 

sage: R.<x> = QQ[] 

sage: v = GaussValuation(R, valuations.TrivialValuation(QQ)) 

sage: v._test_is_equivalence_unit() 

""" 

tester = self._tester(**options) 

tester.assertFalse(self.is_equivalence_unit(self.phi())) 

def _test_equivalence_reciprocal(self, **options): 

r""" 

Test the correctness of :meth:`equivalence_reciprocal`. 

EXAMPLES:: 

sage: R.<x> = QQ[] 

sage: v = GaussValuation(R, valuations.TrivialValuation(QQ)) 

sage: v._test_equivalence_reciprocal() 

""" 

tester = self._tester(**options) 

S = tester.some_elements(self.domain().some_elements()) 

for f in S: 

if self.is_equivalence_unit(f): 

try: 

g = self.equivalence_reciprocal(f) 

except (ValueError, NotImplementedError): 

# this is often not possible unless the underlying ring of 

# constants is a field 

from sage.categories.fields import Fields 

if self.domain().base() not in Fields(): 

continue 

raise 

tester.assertEqual(self.reduce(f*g), 1) 

def _test_inductive_valuation_inheritance(self, **options): 

r""" 

Test that every instance that is a :class:`InductiveValuation` is 

either a :class:`FiniteInductiveValuation` or a 

:class:`InfiniteInductiveValuation`. Same for 

:class:`FinalInductiveValuation` and 

:class:`NonFinalInductiveValuation`. 

EXAMPLES:: 

sage: R.<x> = QQ[] 

sage: v = GaussValuation(R, valuations.TrivialValuation(QQ)) 

sage: v._test_inductive_valuation_inheritance() 

""" 

tester = self._tester(**options) 

tester.assertTrue(isinstance(self, InfiniteInductiveValuation) != isinstance(self, FiniteInductiveValuation)) 

tester.assertTrue(isinstance(self, FinalInductiveValuation) != isinstance(self, NonFinalInductiveValuation)) 

class FiniteInductiveValuation(InductiveValuation, DiscreteValuation): 

r""" 

Abstract base class for iterated :mod:`augmented valuations <sage.rings.valuation.augmented_valuation>` 

on top of a :mod:`Gauss valuation <sage.rings.valuation.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)) 

""" 

def __init__(self, parent, phi): 

r""" 

TESTS:: 

sage: R.<x> = QQ[] 

sage: v = GaussValuation(R, valuations.TrivialValuation(QQ)) 

sage: from sage.rings.valuation.inductive_valuation import FiniteInductiveValuation 

sage: isinstance(v, FiniteInductiveValuation) 

True 

""" 

InductiveValuation.__init__(self, parent, phi) 

DiscreteValuation.__init__(self, parent) 

def extensions(self, other): 

r""" 

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.categories.function_fields import FunctionFields 

if other in FunctionFields() and other.ngens() == 1: 

# extend to K[x] and from there to K(x) 

v = self.extension(self.domain().change_ring(self.domain().base().fraction_field())) 

return [other.valuation(v)] 

return super(FiniteInductiveValuation, self).extensions(other) 

class NonFinalInductiveValuation(FiniteInductiveValuation, DiscreteValuation): 

r""" 

Abstract base class for iterated :mod:`augmented valuations <sage.rings.valuation.augmented_valuation>` 

on top of a :mod:`Gauss valuation <sage.rings.valuation.gauss_valuation>` which can be extended further 

through :meth:`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) 

""" 

def __init__(self, parent, phi): 

r""" 

TESTS:: 

sage: R.<u> = Qq(4,5) 

sage: S.<x> = R[] 

sage: v = GaussValuation(S) 

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

sage: from sage.rings.valuation.inductive_valuation import NonFinalInductiveValuation 

sage: isinstance(v, NonFinalInductiveValuation) 

True 

""" 

FiniteInductiveValuation.__init__(self, parent, phi) 

DiscreteValuation.__init__(self, parent) 

def augmentation(self, phi, mu, check=True): 

r""" 

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 :meth:`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 ] 

TESTS: 

Make sure that we do not make the assumption that the degrees of the 

key polynomials are strictly increasing:: 

sage: v_K = QQ.valuation(3) 

sage: A.<t> = QQ[] 

sage: v0 = GaussValuation(A,v_K) 

sage: v1 = v0.augmentation(t, 1/12) 

sage: v2 = v1.augmentation(t^12 + 3, 7/6) 

sage: v3 = v2.augmentation(t^12 + 3*t^2 + 3, 9/4) 

sage: v4 = v1.augmentation(t^12 + 3*t^2 + 3, 9/4) 

sage: v3 <= v4 and v3 >= v4  

True 

.. SEEALSO:: 

:mod:`~sage.rings.valuation.augmented_valuation` 

""" 

from .augmented_valuation import AugmentedValuation 

return AugmentedValuation(self, phi, mu, check) 

def mac_lane_step(self, G, principal_part_bound=None, assume_squarefree=False, assume_equivalence_irreducible=False, report_degree_bounds_and_caches=False, coefficients=None, valuations=None, check=True): 

r""" 

Perform an approximation step towards the squarefree monic non-constant 

integral polynomial ``G`` which is not an :meth:`equivalence unit <InductiveValuation.is_equivalence_unit>`. 

This performs the individual steps that are used in 

:meth:`~sage.rings.valuation.valuation.DiscreteValuation.mac_lane_approximants`. 

INPUT: 

- ``G`` -- a sqaurefree monic non-constant integral polynomial ``G`` 

which is not an :meth:`equivalence unit <InductiveValuation.is_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 :meth:`~sage.rings.valuation.valuation.DiscreteValuation.mac_lane_approximants` to speed up sequential calls) 

- ``coefficients`` -- the coefficients of ``G`` in the :meth:`~sage.rings.valuation.developing_valuation.DevelopingValuation.phi`-adic expansion if known (default: ``None``) 

- ``valauations`` -- 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 :meth:`equivalence unit <InductiveValuation.is_equivalence_unit>` 

(default: ``True``) 

TESTS:: 

sage: K.<x> = FunctionField(QQ) 

sage: S.<y> = K[] 

sage: F = y^2 - x^2 - x^3 - 3 

sage: v0 = GaussValuation(K._ring, QQ.valuation(3)) 

sage: v1 = v0.augmentation(K._ring.gen(), 1/3) 

sage: mu0 = K.valuation(v1) 

sage: eta0 = GaussValuation(S, mu0) 

sage: eta1 = eta0.mac_lane_step(F)[0] 

sage: eta2 = eta1.mac_lane_step(F)[0] 

sage: eta2 

[ Gauss valuation induced by Valuation on rational function field induced by [ Gauss valuation induced by 3-adic valuation, v(x) = 1/3 ], v(y + x) = 2/3 ] 

""" 

G = self.domain().coerce(G) 

if G.is_constant(): 

raise ValueError("G must not be constant") 

from itertools import islice 

from sage.misc.misc import verbose 

verbose("Augmenting %s towards %s"%(self, G), level=10) 

if not G.is_monic(): 

raise ValueError("G must be monic") 

if coefficients is None: 

coefficients = self.coefficients(G) 

if principal_part_bound: 

coefficients = islice(coefficients, 0, principal_part_bound + 1, 1) 

coefficients = list(coefficients) 

if valuations is None: 

valuations = self.valuations(G, coefficients=coefficients) 

if principal_part_bound: 

valuations = islice(valuations, 0, principal_part_bound + 1, 1) 

valuations = list(valuations) 

if check and min(valuations) < 0: 

raise ValueError("G must be integral") 

if check and self.is_equivalence_unit(G, valuations=valuations): 

raise ValueError("G must not be an equivalence-unit") 

if check and not assume_squarefree and not G.is_squarefree(): 

raise ValueError("G must be squarefree") 

from sage.rings.all import infinity 

assert self(G) is not infinity # this is a valuation and G is non-zero 

ret = [] 

F = self.equivalence_decomposition(G, assume_not_equivalence_unit=True, coefficients=coefficients, valuations=valuations, compute_unit=False, degree_bound=principal_part_bound) 

assert len(F), "%s equivalence-decomposes as an equivalence-unit %s"%(G, F) 

if len(F) == 1 and F[0][1] == 1 and F[0][0].degree() == G.degree(): 

assert self.is_key(G, assume_equivalence_irreducible=assume_equivalence_irreducible) 

ret.append((self.augmentation(G, infinity, check=False), G.degree(), principal_part_bound, None, None)) 

else: 

for phi,e in F: 

if G == phi: 

# Something strange happened here: 

# G is not a key (we checked that before) but phi==G is; so phi must have less precision than G 

# this can happen if not all coefficients of G have the same precision 

# if we drop some precision of G then it will be a key (but is 

# that really what we should do?) 

assert not G.base_ring().is_exact() 

prec = min([c.precision_absolute() for c in phi.list()]) 

g = G.map_coefficients(lambda c:c.add_bigoh(prec)) 

assert self.is_key(g) 

ret.append((self.augmentation(g, infinity, check=False), g.degree(), principal_part_bound, None, None)) 

assert len(F) == 1 

break 

if phi == self.phi(): 

# a factor phi in the equivalence decomposition means that we 

# found an actual factor of G, i.e., we can set 

# v(phi)=infinity 

# However, this should already have happened in the last step 

# (when this polynomial had -infinite slope in the Newton 

# polygon.) 

if self.is_gauss_valuation(): # unless in the first step 

pass 

else: 

continue 

verbose("Determining the augmentation of %s for %s"%(self, phi), level=11) 

old_mu = self(phi) 

w = self.augmentation(phi, old_mu, check=False) 

# we made some experiments here: instead of computing the 

# coefficients again from scratch, update the coefficients when 

# phi - self.phi() is a constant. 

# It turned out to be slightly slower than just recomputing the 

# coefficients. The main issue with the approach was that we 

# needed to keep track of all the coefficients and not just of 

# the coefficients up to principal_part_bound. 

w_coefficients = w.coefficients(G) 

if principal_part_bound: 

w_coefficients = islice(w_coefficients, 0, principal_part_bound + 1, 1) 

w_coefficients = list(w_coefficients) 

w_valuations = w.valuations(G, coefficients=w_coefficients) 

if principal_part_bound: 

w_valuations = islice(w_valuations, 0, principal_part_bound + 1, 1) 

w_valuations = list(w_valuations) 

from sage.geometry.newton_polygon import NewtonPolygon 

NP = NewtonPolygon(w.newton_polygon(G, valuations=w_valuations).vertices(), last_slope=0) 

verbose("Newton-Polygon for v(phi)=%s : %s"%(self(phi), NP), level=11) 

slopes = NP.slopes(repetition=True) 

multiplicities = {slope : len([s for s in slopes if s == slope]) for slope in slopes} 

slopes = multiplicities.keys() 

if NP.vertices()[0][0] != 0: 

slopes = [-infinity] + slopes 

multiplicities[-infinity] = 1 

for i, slope in enumerate(slopes): 

verbose("Slope = %s"%slope, level=12) 

new_mu = old_mu - slope 

new_valuations = [val - (j*slope if slope is not -infinity else (0 if j == 0 else -infinity)) 

for j,val in enumerate(w_valuations)] 

base = self 

if phi.degree() == base.phi().degree(): 

# very frequently, the degree of the key polynomials 

# stagnate for a bit while the valuation of the key 

# polynomial is slowly increased. 

# In this case, we can drop previous key polynomials 

# of the same degree. (They have no influence on the 

# phi-adic expansion.) 

assert new_mu > self(phi) 

if not base.is_gauss_valuation(): 

base = base._base_valuation 

w = base.augmentation(phi, new_mu, check=False) 

assert slope is -infinity or 0 in w.newton_polygon(G).slopes(repetition=False) 

from sage.rings.all import ZZ 

assert (phi.degree() / self.phi().degree()) in ZZ 

degree_bound = multiplicities[slope] * phi.degree() 

assert degree_bound <= G.degree() 

assert degree_bound >= phi.degree() 

ret.append((w, degree_bound, multiplicities[slope], w_coefficients, new_valuations)) 

assert ret 

if not report_degree_bounds_and_caches: 

ret = [v for v,_,_,_,_ in ret] 

return ret 

def is_key(self, phi, explain=False, assume_equivalence_irreducible=False): 

r""" 

Return whether ``phi`` is a key polynomial for this valuation, i.e., 

whether it is monic, whether it :meth:`is_equivalence_irreducible`, and 

whether it is :meth:`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') 

""" 

phi = self.domain().coerce(phi) 

reason = None 

if not phi.is_monic(): 

reason = "phi must be monic" 

elif not assume_equivalence_irreducible and not self.is_equivalence_irreducible(phi): 

reason = "phi must be equivalence irreducible" 

elif not self.is_minimal(phi, assume_equivalence_irreducible=True): 

reason = "phi must be minimal" 

if explain: 

return reason is None, reason 

else: 

return reason is None 

def is_minimal(self, f, assume_equivalence_irreducible=False): 

r""" 

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` :meth:`~sage.rings.valuation.valuation.DiscretePseudoValuation.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 

TESTS:: 

sage: K = Qp(2, 10) 

sage: R.<x> = K[] 

sage: vp = K.valuation() 

sage: v0 = GaussValuation(R, vp) 

sage: v1 = v0.augmentation(x, 1/4) 

sage: v2 = v1.augmentation(x^4 + 2, 5/4) 

sage: v2.is_minimal(x^5 + x^4 + 2) 

False 

Polynomials which are equivalent to the key polynomial are minimal if 

and only if they have the same degree as the key polynomial:: 

sage: v2.is_minimal(x^4 + 2) 

True 

sage: v2.is_minimal(x^4 + 4) 

False 

""" 

f = self.domain().coerce(f) 

if f.is_constant(): 

return False