Coverage for local/lib/python2.7/site-packages/sage/rings/padics/padic_valuation.py : 92%

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

r""" 

`p`-adic valuations on number fields and their subrings and completions 

EXAMPLES:: 

sage: ZZ.valuation(2) 

2-adic valuation 

sage: QQ.valuation(3) 

3-adic valuation 

sage: CyclotomicField(5).valuation(5) 

5-adic valuation 

sage: GaussianIntegers().valuation(7) 

7-adic valuation 

sage: Zp(11).valuation() 

11-adic valuation 

These valuations can then, e.g., be used to compute approximate factorizations 

in the completion of a ring:: 

sage: v = ZZ.valuation(2) 

sage: R.<x> = ZZ[] 

sage: f = x^5 + x^4 + x^3 + x^2 + x - 1 

sage: v.montes_factorization(f, required_precision=20) 

(x + 676027) * (x^4 + 372550*x^3 + 464863*x^2 + 385052*x + 297869) 

AUTHORS: 

- Julian Rüth (2013-03-16): initial version 

REFERENCES: 

The theory used here was originally developed in [Mac1936I]_ and [Mac1936II]_. An 

overview can also be found in Chapter 4 of [Rüt2014]_. 

""" 

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

# Copyright (C) 2013-2016 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 sage.rings.valuation.valuation import DiscreteValuation 

from sage.rings.valuation.value_group import DiscreteValueSemigroup 

from sage.rings.valuation.mapped_valuation import FiniteExtensionFromLimitValuation 

from sage.structure.factory import UniqueFactory 

from sage.misc.cachefunc import cached_method 

from sage.misc.fast_methods import WithEqualityById 

from sage.rings.all import infinity 

class PadicValuationFactory(UniqueFactory): 

r""" 

Create a ``prime``-adic valuation on ``R``. 

INPUT: 

- ``R`` -- a subring of a number field or a subring of a local field in 

characteristic zero 

- ``prime`` -- a prime that does not split, a discrete (pseudo-)valuation, 

a fractional ideal, or ``None`` (default: ``None``) 

EXAMPLES: 

For integers and rational numbers, ``prime`` is just a prime of the 

integers:: 

sage: valuations.pAdicValuation(ZZ, 3) 

3-adic valuation 

sage: valuations.pAdicValuation(QQ, 3) 

3-adic valuation 

``prime`` may be ``None`` for local rings:: 

sage: valuations.pAdicValuation(Qp(2)) 

2-adic valuation 

sage: valuations.pAdicValuation(Zp(2)) 

2-adic valuation 

But it must be specified in all other cases:: 

sage: valuations.pAdicValuation(ZZ) 

Traceback (most recent call last): 

... 

ValueError: prime must be specified for this ring 

It can sometimes be beneficial to define a number field extension as a 

quotient of a polynomial ring (since number field extensions always compute 

an absolute polynomial defining the extension which can be very costly):: 

sage: R.<x> = QQ[] 

sage: K.<a> = NumberField(x^2 + 1) 

sage: R.<x> = K[] 

sage: L.<b> = R.quo(x^2 + a) 

sage: valuations.pAdicValuation(L, 2) 

2-adic valuation 

.. SEEALSO:: 

:meth:`NumberField_generic.valuation() <sage.rings.number_field.number_field.NumberField_generic.valuation>`, 

:meth:`Order.valuation() <sage.rings.number_field.order.Order.valuation>`, 

:meth:`pAdicGeneric.valuation() <sage.rings.padics.padic_generic.pAdicGeneric.valuation>`, 

:meth:`RationalField.valuation() <sage.rings.rational_field.RationalField.valuation>`, 

:meth:`IntegerRing_class.valuation() <sage.rings.integer_ring.IntegerRing_class.valuation>`. 

""" 

def create_key_and_extra_args(self, R, prime=None, approximants=None): 

r""" 

Create a unique key identifying the valuation of ``R`` with respect to 

``prime``. 

EXAMPLES:: 

sage: QQ.valuation(2) # indirect doctest 

2-adic valuation 

""" 

from sage.rings.all import ZZ, QQ 

from sage.rings.padics.padic_generic import pAdicGeneric 

from sage.rings.number_field.number_field import is_NumberField 

from sage.rings.polynomial.polynomial_quotient_ring import is_PolynomialQuotientRing 

if R.characteristic() != 0: 

# We do not support equal characteristic yet 

raise ValueError("R must be a ring of characteristic zero.") 

if R is ZZ or R is QQ: 

return self.create_key_for_integers(R, prime), {} 

elif isinstance(R, pAdicGeneric): 

return self.create_key_for_local_ring(R, prime), {} 

elif is_NumberField(R.fraction_field()) or is_PolynomialQuotientRing(R): 

return self.create_key_and_extra_args_for_number_field(R, prime, approximants=approximants) 

else: 

raise NotImplementedError("p-adic valuations not implemented for %r"%(R,)) 

def create_key_for_integers(self, R, prime): 

r""" 

Create a unique key identifying the valuation of ``R`` with respect to 

``prime``. 

EXAMPLES:: 

sage: QQ.valuation(2) # indirect doctest 

2-adic valuation 

""" 

from sage.rings.all import ZZ 

if prime is None: 

raise ValueError("prime must be specified for this ring") 

from sage.rings.valuation.valuation import DiscretePseudoValuation 

if isinstance(prime, DiscretePseudoValuation): 

prime = prime.uniformizer() 

if prime not in ZZ or not ZZ(prime).is_prime(): 

raise ValueError("prime must be a prime in the integers but %s is not"%(prime,)) 

return R, prime 

def create_key_for_local_ring(self, R, prime): 

r""" 

Create a unique key identifying the valuation of ``R`` with respect to 

``prime``. 

EXAMPLES:: 

sage: Qp(2).valuation() # indirect doctest 

2-adic valuation 

""" 

# We do not care much about the value of prime since there is only one 

# reasonable p-adic valuation here 

if prime is not None: 

if prime in R: 

if R(prime).valuation() <= 0: 

raise ValueError("prime must be an element of positive valuation") 

elif prime(R.prime()) <= 0: 

raise ValueError("prime must be an element of positive valuation") 

return (R,) 

def create_key_and_extra_args_for_number_field(self, R, prime, approximants): 

r""" 

Create a unique key identifying the valuation of ``R`` with respect to 

``prime``. 

EXAMPLES:: 

sage: GaussianIntegers().valuation(2) # indirect doctest 

2-adic valuation 

""" 

K, L, G = self._normalize_number_field_data(R) 

from sage.rings.number_field.number_field_ideal import NumberFieldFractionalIdeal 

from sage.rings.valuation.valuation import DiscretePseudoValuation 

if isinstance(prime, DiscretePseudoValuation): 

return self.create_key_and_extra_args_for_number_field_from_valuation(R, prime, prime, approximants=approximants) 

elif prime in K: 

return self.create_key_and_extra_args_for_number_field_from_valuation(R, K.valuation(prime), prime, approximants=approximants) 

elif prime in L or isinstance(prime, NumberFieldFractionalIdeal): 

return self.create_key_and_extra_args_for_number_field_from_ideal(R, L.fractional_ideal(prime), prime) 

else: 

raise ValueError("prime must be a discrete pseudo-valuation, a prime in the base ring, or a fractional ideal") 

def create_key_and_extra_args_for_number_field_from_valuation(self, R, v, prime, approximants): 

r""" 

Create a unique key identifying the valuation of ``R`` with respect to 

``v``. 

.. NOTE:: 

``prime``, the original parameter that was passed to 

:meth:`create_key_and_extra_args`, is only used to provide more 

meaningful error messages 

EXAMPLES:: 

sage: GaussianIntegers().valuation(ZZ.valuation(2)) # indirect doctest 

2-adic valuation 

TESTS: 

We can extend to the field of fractions of a quotient ring:: 

sage: R.<x> = ZZ[] 

sage: S = R.quo(x^2 + 1) 

sage: v = valuations.pAdicValuation(S, 2) 

sage: R.<x> = QQ[] 

sage: S = R.quo(x^2 + 1) 

sage: v = valuations.pAdicValuation(S, v) 

""" 

K, L, G = self._normalize_number_field_data(R) 

if v.domain().is_subring(G.parent()): 

# v is defined on a subring of K[x]. 

# We try to lift v to a pseudo-valuation on K[x]. 

if _fraction_field(v.domain()) is not _fraction_field(G.parent()): 

# First, we lift valuations defined on subrings of K to 

# valuations on K[x]. 

if v.domain().is_subring(K): 

if v.domain() is not K: 

v = K.valuation(v) 

from sage.rings.valuation.gauss_valuation import GaussValuation 

v = GaussValuation(G.parent(), v) 

if v.domain() != G.parent(): 

# Then, we lift valuations defined on polynomial rings which are 

# subrings of K[x] to K[x] 

v = v.extension(G.parent()) 

elif _fraction_field(v.domain()) == L: 

# v is defined on a ring whose field of fractions is L 

v = v._base_valuation._initial_approximation.change_domain(G.parent()) 

else: 

raise NotImplementedError("can not rewrite %r which is defined on %r as a pseudo-valuation on %r"%(v, v.domain(), G.parent())) 

assert(v.domain() is G.parent()) 

# To obtain uniqueness of p-adic valuations, we need a canonical 

# description of v. We consider all extensions of vK to L and select 

# the one approximated by v. 

vK = v.restriction(v.domain().base_ring()).extension(K) 

if approximants is None: 

approximants = vK.mac_lane_approximants(G, require_incomparability=True) 

approximants = [approximant.extension(v.domain()) for approximant in approximants] 

approximant = vK.mac_lane_approximant(G, v, approximants=tuple(approximants)) 

return (R, approximant), {'approximants': approximants} 

def create_key_and_extra_args_for_number_field_from_ideal(self, R, I, prime): 

r""" 

Create a unique key identifying the valuation of ``R`` with respect to 

``I``. 

.. NOTE:: 

``prime``, the original parameter that was passed to 

:meth:`create_key_and_extra_args`, is only used to provide more 

meaningful error messages 

EXAMPLES:: 

sage: GaussianIntegers().valuation(GaussianIntegers().ideal(2)) # indirect doctest 

2-adic valuation 

""" 

K, L, G = self._normalize_number_field_data(R) 

# To obtain uniqueness of p-adic valuations, we need a canonical 

# description of v. We consider all extensions of vK to L and select 

# the one approximated by v. 

# Of course, this only works if I comes from a single prime downstairs. 

p = I.relative_norm() 

F = p.factor() 

if len(F) != 1: 

raise ValueError("%r does not lie over a single prime of %r"%(I, K)) 

vK = K.valuation(F[0][0]) 

candidates = vK.mac_lane_approximants(G, require_incomparability=True) 

candidates_for_I = [c for c in candidates if all(c(g.polynomial()) > 0 for g in I.gens())] 

assert(len(candidates_for_I) > 0) # This should not be possible, unless I contains a unit 

if len(candidates_for_I) > 1: 

raise ValueError("%s does not single out a unique extension of %s to %s"%(prime, vK, L)) 

else: 

return (R, candidates_for_I[0]), {'approximants': candidates} 

def _normalize_number_field_data(self, R): 

r""" 

Helper method which returns the defining data of the number field 

``R``. 

EXAMPLES:: 

sage: R.<x> = QQ[] 

sage: K = R.quo(x^2 + 1) 

sage: valuations.pAdicValuation._normalize_number_field_data(K) 

(Rational Field, 

Univariate Quotient Polynomial Ring in xbar over Rational Field with modulus x^2 + 1, 

x^2 + 1) 

""" 

from sage.rings.polynomial.polynomial_quotient_ring import is_PolynomialQuotientRing 

from sage.rings.number_field.number_field import is_NumberField 

from sage.rings.fraction_field import is_FractionField 

if is_NumberField(R.fraction_field()): 

L = R.fraction_field() 

G = L.relative_polynomial() 

K = L.base_ring() 

elif is_PolynomialQuotientRing(R): 

from sage.categories.all import NumberFields 

if R.base_ring().fraction_field() not in NumberFields(): 

raise NotImplementedError("can not normalize quotients over %r"%(R.base_ring(),)) 

L = R.fraction_field() 

K = R.base_ring().fraction_field() 

G = R.modulus().change_ring(K) 

else: 

raise NotImplementedError("can not normalize %r"%(R,)) 

return K, L, G 

def create_object(self, version, key, **extra_args): 

r""" 

Create a `p`-adic valuation from ``key``. 

EXAMPLES:: 

sage: ZZ.valuation(5) # indirect doctest 

5-adic valuation 

""" 

from sage.rings.all import ZZ, QQ 

from sage.rings.padics.padic_generic import pAdicGeneric 

from sage.rings.valuation.valuation_space import DiscretePseudoValuationSpace 

from sage.rings.polynomial.polynomial_quotient_ring import is_PolynomialQuotientRing 

from sage.rings.number_field.number_field import is_NumberField 

R = key[0] 

parent = DiscretePseudoValuationSpace(R) 

if isinstance(R, pAdicGeneric): 

assert(len(key)==1) 

return parent.__make_element_class__(pAdicValuation_padic)(parent) 

elif R is ZZ or R is QQ: 

prime = key[1] 

assert(len(key)==2) 

return parent.__make_element_class__(pAdicValuation_int)(parent, prime) 

else: 

v = key[1] 

approximants = extra_args['approximants'] 

parent = DiscretePseudoValuationSpace(R) 

K = R.fraction_field() 

if is_NumberField(K): 

G = K.relative_polynomial() 

elif is_PolynomialQuotientRing(R): 

G = R.modulus() 

else: 

raise NotImplementedError 

return parent.__make_element_class__(pAdicFromLimitValuation)(parent, v, G.change_ring(R.base_ring()), approximants) 

pAdicValuation = PadicValuationFactory("sage.rings.padics.padic_valuation.pAdicValuation") 

class pAdicValuation_base(DiscreteValuation): 

r""" 

Abstract base class for `p`-adic valuations. 

INPUT: 

- ``ring`` -- an integral domain 

- ``p`` -- a rational prime over which this valuation lies, not 

necessarily a uniformizer for the valuation 

EXAMPLES:: 

sage: ZZ.valuation(3) 

3-adic valuation 

sage: QQ.valuation(5) 

5-adic valuation 

For `p`-adic rings, ``p`` has to match the `p` of the ring. 

sage: v = valuations.pAdicValuation(Zp(3), 2); v 

Traceback (most recent call last): 

... 

ValueError: prime must be an element of positive valuation 

TESTS:: 

sage: TestSuite(ZZ.valuation(3)).run() # long time 

sage: TestSuite(QQ.valuation(5)).run() # long time 

sage: TestSuite(Zp(5).valuation()).run() # long time 

""" 

def __init__(self, parent, p): 

r""" 

TESTS:: 

sage: from sage.rings.padics.padic_valuation import pAdicValuation_base 

sage: isinstance(ZZ.valuation(3), pAdicValuation_base) 

True 

""" 

DiscreteValuation.__init__(self, parent) 

from sage.rings.all import ZZ 

self._p = ZZ(p) 

def p(self): 

r""" 

Return the `p` of this `p`-adic valuation. 

EXAMPLES:: 

sage: GaussianIntegers().valuation(2).p() 

2 

""" 

return self._p 

def reduce(self, x): 

r""" 

Reduce ``x`` modulo the ideal of elements of positive valuation. 

INPUT: 

- ``x`` -- an element in the domain of this valuation 

OUTPUT: 

An element of the :meth:`~sage.rings.valuation.valuation_space.DiscretePseudoValuationSpace.ElementMethods.residue_field`. 

EXAMPLES:: 

sage: v = ZZ.valuation(3) 

sage: v.reduce(4) 

1 

""" 

x = self.domain().coerce(x) 

if self(x) < 0: 

raise ValueError("reduction is only defined for elements of non-negative valuation") 

return self.residue_field()(x) 

def lift(self, x): 

r""" 

Lift ``x`` from the residue field to the domain of this valuation. 

INPUT: 

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

EXAMPLES:: 

sage: v = ZZ.valuation(3) 

sage: xbar = v.reduce(4) 

sage: v.lift(xbar) 

1 

""" 

x = self.residue_field().coerce(x) 

return self.domain()(x) 

def is_unramified(self, G, include_steps=False, assume_squarefree=False): 

r""" 

Return whether ``G`` defines a single unramified extension of the 

completion of the domain of this valuation. 

INPUT: 

- ``G`` -- a monic squarefree polynomial over the domain of this valuation 

- ``include_steps`` -- a boolean (default: ``False``); whether to 

include the approximate valuations that were used to determine the 

result in the return value. 

- ``assume_squarefree`` -- a boolean (default: ``False``); whether to 

assume that ``G`` is square-free over the completion of the domain of 

this valuation. Setting this to ``True`` can significantly improve 

the performance. 

EXAMPLES: 

We consider an extension as unramified if its ramification index is 1. 

Hence, a trivial extension is unramified:: 

sage: R.<x> = QQ[] 

sage: v = QQ.valuation(2) 

sage: v.is_unramified(x) 

True 

If ``G`` remains irreducible in reduction, then it defines an 

unramified extension:: 

sage: v.is_unramified(x^2 + x + 1) 

True 

However, even if ``G`` factors, it might define an unramified 

extension:: 

sage: v.is_unramified(x^2 + 2*x + 4) 

True 

""" 

R = G.parent() 

from sage.rings.polynomial.polynomial_ring import is_PolynomialRing 

if not is_PolynomialRing(R) or R.base_ring() is not self.domain() or not G.is_monic(): 

raise ValueError("G must be a monic univariate polynomial over the domain of this valuation") 

if not assume_squarefree and not G.is_squarefree(): 

raise ValueError("G must be squarefree") 

from sage.rings.valuation.gauss_valuation import GaussValuation 

steps = [ GaussValuation(R, self) ] 

while True: 

v = steps[-1] 

if v.E() > 1: 

ret = False 

break 

if v.F() == G.degree(): 

ret = True 

break 

assert v(G) is not infinity 

if v.is_key(G): 

ret = True 

break 

next = v.mac_lane_step(G, assume_squarefree=True) 

if len(next)>1: 

ret = False 

break 

steps.append(next[0]) 

if include_steps: 

return ret, steps 

else: 

return ret 

def is_totally_ramified(self, G, include_steps=False, assume_squarefree=False): 

r""" 

Return whether ``G`` defines a single totally ramified extension of the 

completion of the domain of this valuation. 

INPUT: 

- ``G`` -- a monic squarefree polynomial over the domain of this valuation 

- ``include_steps`` -- a boolean (default: ``False``); where to include 

the valuations produced during the process of checking whether ``G`` 

is totally ramified in the return value 

- ``assume_squarefree`` -- a boolean (default: ``False``); whether to 

assume that ``G`` is square-free over the completion of the domain of 

this valuation. Setting this to ``True`` can significantly improve 

the performance. 

ALGORITHM: 

This is a simplified version of :meth:`sage.rings.valuation.valuation.DiscreteValuation.mac_lane_approximants`. 

EXAMPLES:: 

sage: k = Qp(5,4) 

sage: v = k.valuation() 

sage: R.<x> = k[] 

sage: G = x^2 + 1 

sage: v.is_totally_ramified(G) 

False 

sage: G = x + 1 

sage: v.is_totally_ramified(G) 

True 

sage: G = x^2 + 2 

sage: v.is_totally_ramified(G) 

False 

sage: G = x^2 + 5 

sage: v.is_totally_ramified(G) 

True 

sage: v.is_totally_ramified(G, include_steps=True) 

(True, [Gauss valuation induced by 5-adic valuation, [ Gauss valuation induced by 5-adic valuation, v((1 + O(5^4))*x) = 1/2 ]]) 

We consider an extension as totally ramified if its ramification index 

matches the degree. Hence, a trivial extension is totally ramified:: 

sage: R.<x> = QQ[] 

sage: v = QQ.valuation(2) 

sage: v.is_totally_ramified(x) 

True 

TESTS: 

An example that Sebastian Pauli used at Sage Days 87:: 

sage: R = ZpFM(3, 20) 

sage: S.<x> = R[] 

sage: f = x^9 + 9*x^2 + 3 

sage: R.valuation().is_totally_ramified(f) 

True 

""" 

R = G.parent() 

from sage.rings.polynomial.polynomial_ring import is_PolynomialRing 

if not is_PolynomialRing(R) or R.base_ring() is not self.domain() or not G.is_monic(): 

raise ValueError("G must be a monic univariate polynomial over the domain of this valuation") 

if not assume_squarefree and not G.is_squarefree(): 

raise ValueError("G must be squarefree") 

from sage.rings.valuation.gauss_valuation import GaussValuation 

steps = [ GaussValuation(R, self) ] 

while True: 

v = steps[-1] 

if v.F() > 1: 

ret = False 

break 

if v.E() == G.degree(): 

ret = True 

break 

assert v(G) is not infinity 

if v.is_key(G): 

ret = False 

break 

next = v.mac_lane_step(G, assume_squarefree=True) 

if len(next)>1: 

ret = False 

break 

steps.append(next[0]) 

if include_steps: 

return ret, steps 

else: 

return ret 

def change_domain(self, ring): 

r""" 

Change the domain of this valuation to ``ring`` if possible. 

EXAMPLES:: 

sage: v = ZZ.valuation(2) 

sage: v.change_domain(QQ).domain() 

Rational Field 

""" 

return pAdicValuation(ring, self.p()) 

def _extensions_to_quotient(self, ring, approximants=None): 

r""" 

Return the extensions of this valuation to an integral quotient over 

the domain of this valuation. 

EXAMPLES:: 

sage: R.<x> = QQ[] 

sage: QQ.valuation(2)._extensions_to_quotient(R.quo(x^2 + x + 1)) 

[2-adic valuation] 

""" 

from sage.rings.valuation.valuation_space import DiscretePseudoValuationSpace 

parent = DiscretePseudoValuationSpace(ring) 

approximants = approximants or self.mac_lane_approximants(ring.modulus().change_ring(self.domain()), assume_squarefree=True, require_incomparability=True) 

return [pAdicValuation(ring, approximant, approximants) for approximant in approximants] 

def extensions(self, ring): 

r""" 

Return the extensions of this valuation to ``ring``. 

EXAMPLES:: 

sage: v = ZZ.valuation(2) 

sage: v.extensions(GaussianIntegers()) 

[2-adic valuation] 

TESTS:: 

sage: R.<a> = QQ[] 

sage: L.<a> = QQ.extension(x^3 - 2) 

sage: R.<b> = L[] 

sage: M.<b> = L.extension(b^2 + 2*b + a) 

sage: M.valuation(2) 

2-adic valuation 

Check that we can extend to a field written as a quotient:: 

sage: R.<x> = QQ[] 

sage: K.<a> = QQ.extension(x^2 + 1) 

sage: R.<y> = K[] 

sage: L.<b> = R.quo(x^2 + a) 

sage: QQ.valuation(2).extensions(L) 

[2-adic valuation] 

A case where there was at some point an internal error in the 

approximants code:: 

sage: R.<x> = QQ[] 

sage: L.<a> = NumberField(x^4 + 2*x^3 + 2*x^2 + 8) 

sage: QQ.valuation(2).extensions(L) 

[[ 2-adic valuation, v(x + 2) = 3/2 ]-adic valuation, 

[ 2-adic valuation, v(x) = 1/2 ]-adic valuation] 

A case where the extension was incorrect at some point:: 

sage: v = QQ.valuation(2) 

sage: L.<a> = NumberField(x^2 + 2) 

sage: M.<b> = L.extension(x^2 + 1) 

sage: w = v.extension(L).extension(M) 

sage: w(w.uniformizer()) 

1/4 

A case where the extensions could not be separated at some point:: 

sage: v = QQ.valuation(2) 

sage: R.<x> = QQ[] 

sage: F = x^48 + 120*x^45 + 56*x^42 + 108*x^36 + 32*x^33 + 40*x^30 + 48*x^27 + 80*x^24 + 112*x^21 + 96*x^18 + 96*x^15 + 24*x^12 + 96*x^9 + 16*x^6 + 96*x^3 + 68 

sage: L.<a> = QQ.extension(F) 

sage: v.extensions(L) 

[[ 2-adic valuation, v(x) = 1/24, v(x^24 + 4*x^18 + 10*x^12 + 12*x^6 + 8*x^3 + 6) = 29/8 ]-adic valuation, 

[ 2-adic valuation, v(x) = 1/24, v(x^24 + 4*x^18 + 2*x^12 + 12*x^6 + 8*x^3 + 6) = 29/8 ]-adic valuation] 

""" 

if self.domain() is ring: 

return [self] 

domain_fraction_field = _fraction_field(self.domain()) 

if domain_fraction_field is not self.domain(): 

if domain_fraction_field.is_subring(ring): 

return pAdicValuation(domain_fraction_field, self).extensions(ring) 

if self.domain().is_subring(ring): 

from sage.rings.polynomial.polynomial_quotient_ring import is_PolynomialQuotientRing 

if is_PolynomialQuotientRing(ring): 

if is_PolynomialQuotientRing(self.domain()): 

if self.domain().modulus() == ring.modulus(): 

base_extensions = self._base_valuation.extensions(self._base_valuation.domain().change_ring(self._base_valuation.domain().base_ring().fraction_field())) 

return [pAdicValuation(ring, base._initial_approximation) for base in base_extensions] 

if ring.base_ring() is self.domain(): 

from sage.categories.all import IntegralDomains 

if ring in IntegralDomains(): 

return self._extensions_to_quotient(ring) 

elif self.domain().is_subring(ring.base_ring()): 

return sum([w.extensions(ring) for w in self.extensions(ring.base_ring())], []) 

from sage.rings.number_field.number_field import is_NumberField 

if is_NumberField(ring.fraction_field()): 

if ring.base_ring().fraction_field() is self.domain().fraction_field(): 

from sage.rings.valuation.valuation_space import DiscretePseudoValuationSpace 

parent = DiscretePseudoValuationSpace(ring) 

approximants = self.mac_lane_approximants(ring.fraction_field().relative_polynomial().change_ring(self.domain()), assume_squarefree=True, require_incomparability=True) 

return [pAdicValuation(ring, approximant, approximants) for approximant in approximants] 

if ring.base_ring() is not ring and self.domain().is_subring(ring.base_ring()): 

return sum([w.extensions(ring) for w in self.extensions(ring.base_ring())], []) 

return super(pAdicValuation_base, self).extensions(ring) 

def restriction(self, ring): 

r""" 

Return the restriction of this valuation to ``ring``. 

EXAMPLES:: 

sage: v = GaussianIntegers().valuation(2) 

sage: v.restriction(ZZ) 

2-adic valuation 

""" 

if ring is self.domain(): 

return self 

if not ring.is_subring(self.domain()): 

raise ValueError("ring must be a subring of the domain of this valuation but %r is not a subring of %r"%(ring, self.domain())) 

return pAdicValuation(ring, self.p()) 

@cached_method 

def value_semigroup(self): 

r""" 

Return the value semigroup of this valuation. 

EXAMPLES:: 

sage: v = GaussianIntegers().valuation(2) 

sage: v.value_semigroup() 

Additive Abelian Semigroup generated by 1/2 

""" 

from sage.categories.all import Fields 

v = self(self.uniformizer()) 

if self.domain() in Fields(): 

return DiscreteValueSemigroup([-v,v]) 

else: 

return DiscreteValueSemigroup([v]) 

class pAdicValuation_padic(pAdicValuation_base): 

""" 

The `p`-adic valuation of a complete `p`-adic ring. 

INPUT: 

- ``R`` -- a `p`-adic ring 

EXAMPLES:: 

sage: v = Qp(2).valuation(); v #indirect doctest 

2-adic valuation 

TESTS:: 

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

""" 

def __init__(self, parent): 

""" 

TESTS:: 

sage: from sage.rings.padics.padic_valuation import pAdicValuation_padic 

sage: isinstance(Qp(2).valuation(), pAdicValuation_padic) 

True 

""" 

pAdicValuation_base.__init__(self, parent, parent.domain().prime()) 

def reduce(self, x): 

""" 

Reduce ``x`` modulo the ideal of elements of positive valuation. 

INPUT: 

- ``x`` -- an element of the domain of this valuation 

OUTPUT: 

An element of the :meth:`~sage.rings.valuation.valuation_space.DiscretePseudoValuationSpace.ElementMethods.residue_field`. 

EXAMPLES:: 

sage: R = Zp(3) 

sage: Zp(3).valuation().reduce(R(4)) 

1 

""" 

x = self.domain().coerce(x) 

return self.residue_field()(x.residue()) 

def lift(self, x): 

""" 

Lift ``x`` from the :meth:`~sage.rings.valuation.valuation_space.DiscretePseudoValuationSpace.ElementMethods.residue_field` to the domain of this 

valuation. 

INPUT: 

- ``x`` -- an element of the residue field of this valuation 

EXAMPLES:: 

sage: R = Zp(3) 

sage: v = R.valuation() 

sage: xbar = v.reduce(R(4)) 

sage: v.lift(xbar) 

1 + O(3^20) 

""" 

x = self.residue_field().coerce(x) 

return self.domain()(x).lift_to_precision() 

def uniformizer(self): 

""" 

Return a uniformizer of this valuation. 

EXAMPLES:: 

sage: v = Zp(3).valuation() 

sage: v.uniformizer() 

3 + O(3^21) 

""" 

return self.domain().uniformizer() 

def element_with_valuation(self, v): 

""" 

Return an element of valuation ``v``. 

INPUT: 

- ``v`` -- an element of the :meth:`pAdicValuation_base.value_semigroup` of this valuation 

EXAMPLES:: 

sage: R = Zp(3) 

sage: v = R.valuation() 

sage: v.element_with_valuation(3) 

3^3 + O(3^23) 

sage: K = Qp(3) 

sage: R.<y> = K[] 

sage: L.<y> = K.extension(y^2 + 3*y + 3) 

sage: L.valuation().element_with_valuation(3/2) 

y^3 + O(y^43) 

""" 

from sage.rings.all import QQ, ZZ 

v = QQ(v) 

if v not in self.value_semigroup(): 

raise ValueError("%r is not in the value semigroup of %r"%(v, self)) 

v = ZZ(v * self.domain().ramification_index()) 

return self.domain().one() << v 

def _repr_(self): 

""" 

Return a printable representation of this valuation. 

EXAMPLES:: 

sage: ZZ.valuation(3)._repr_() 

'3-adic valuation' 

""" 

return "%s-adic valuation"%(self.p()) 

def _call_(self, x): 

r""" 

Evaluate this valuation at ``x``. 

EXAMPLES:: 

sage: K = Qp(3) 

sage: R.<y> = K[] 

sage: L.<y> = K.extension(y^2 - 3) 

sage: L.valuation()(3) 

1 

""" 

return x.ordp() 

def residue_ring(self): 

r""" 

Return the residue field of this valuation. 

EXAMPLES:: 

sage: Qq(9, names='a').valuation().residue_ring() 

Finite Field in a0 of size 3^2 

""" 

return self.domain().residue_field() 

def shift(self, x, s): 

r""" 

Shift ``x`` in its expansion with respect to :meth:`uniformizer` by 

``s`` "digits". 

For non-negative ``s``, this just returns ``x`` multiplied by a 

power of the uniformizer `\pi`. 

For negative ``s``, it does the same but when not over a field, it 

drops coefficients in the `\pi`-adic expension which have negative 

valuation. 

EXAMPLES:: 

sage: R = ZpCA(2) 

sage: v = R.valuation() 

sage: v.shift(R.one(), 1) 

2 + O(2^20) 

sage: v.shift(R.one(), -1) 

O(2^19) 

sage: S.<y> = R[] 

sage: S.<y> = R.extension(y^3 - 2)