Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
# -*- coding: utf-8 -*- 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/ #*****************************************************************************
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
""" 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
"""
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
"""
raise ValueError("f must be an equivalence unit but %r is not"%(f,))
else:
# f is an equivalence unit, its valuation is given by the constant coefficient else:
# 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
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 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
"""
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]
"""
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
"""
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
"""
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
"""
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)
"""
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
"""
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()
""" 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 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())
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()
""" 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())
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.assertGreaterEqual(w, v)
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()
"""
else: value_group = self.augmentation_chain()[1].value_group()
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
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()
"""
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()
""" 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
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()
"""
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))
""" 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
"""
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]
""" # extend to K[x] and from there to K(x) return super(FiniteInductiveValuation, self).extensions(other)
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)
""" 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
"""
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`
"""
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 ]
"""
raise ValueError("G must not be constant")
raise ValueError("G must be monic")
raise ValueError("G must be integral")
raise ValueError("G must not be an equivalence-unit")
raise ValueError("G must be squarefree")
else: # 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
# 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.) else: continue
# 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.
for j,val in enumerate(w_valuations)] # 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.)
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')
"""
else:
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
"""
return False
# any factor divides f with respect to this valuation return False
# divide out the leading factor, it does not change minimality v = self if not self.domain().base_ring().is_field(): domain = self.domain().change_ring(self.domain().base_ring().fraction_field()) v = self.extension(domain) f = domain(f) return v.is_minimal(f / f.leading_coefficient())
else: assert(self(f) <= 0) # f is monic # f is not minimal: # Let g be f stripped of its leading term, i.e., g = f - x^n. # Then g and f are equivalent with respect to this valuation # and in particular g divides f with respect to this valuation return False
# If an h divides f with respect to this valuation, then it also divides phi: # v(f - c*h) > v(f) = v(c*h) => v(phi - c*h) = v((phi - f) + (f - c*h)) > v(phi) = v(c*h) # So if f were not minimal then phi would not be minimal but it is.
else: # see Theorem 9.4 of [Mac1936II] list(self.coefficients(f))[-1].is_constant() and \ list(self.valuations(f))[0] == self(f) and \ tau.divides(len(list(self.coefficients(f))) - 1)
r""" Helper method for :meth:`is_equivalence_irreducible` and :meth:`equivalence_decomposition` which essentially returns the reduction of ``f`` after multiplication with an ``R`` which :meth:`is_equivalence_unit`.
This only works when ``f`` is not divisible by :meth:`phi` with respect to this valuation. Therefore, we also return the number of times that we took out :meth:`phi` of ``f`` before we computed the reduction.
EXAMPLES::
sage: R.<x> = QQ[] sage: v = GaussValuation(R, QQ.valuation(2)) sage: v._equivalence_reduction(2*x^6 + 4*x^5 + 2*x^4 + 8) (1, 4, x^2 + 1)
"""
# base change from R[x] to K[x], so divisions work and sufficient # elements of negative valuation exist domain = self.domain().change_ring(self.domain().base_ring().fraction_field()) v = self.extension(domain) assert self.residue_ring() is v.residue_ring() return v._equivalence_reduction(f)
# count how many times phi divides f
for c,v in zip(coefficients,fR_valuations)]
r""" Return whether the polynomial ``f`` is equivalence-irreducible, i.e., whether its :meth:`equivalence_decomposition` is trivial.
ALGORITHM:
We use the same algorithm as in :meth:`equivalence_decomposition` we just do not lift the result to key polynomials.
INPUT:
- ``f`` -- a non-constant polynomial in the domain of this valuation
EXAMPLES::
sage: R.<u> = Qq(4,5) sage: S.<x> = R[] sage: v = GaussValuation(S) sage: v.is_equivalence_irreducible(x) True sage: v.is_equivalence_irreducible(x^2) False sage: v.is_equivalence_irreducible(x^2 + 2) False
"""
raise ValueError("f must not be constant")
r""" Return an equivalence decomposition of ``f``, i.e., a polynomial `g(x)=e(x)\prod_i \phi_i(x)` with `e(x)` an :meth:`equivalence unit <InductiveValuation.is_equivalence_unit>` and the `\phi_i` :meth:`key polynomials <is_key>` such that ``f`` :meth:`~sage.rings.valuation.valuation.DiscretePseudoValuation.is_equivalent` to `g`.
INPUT:
- ``f`` -- a non-zero polynomial in the domain of this valuation
- ``assume_not_equivalence_unit`` -- whether or not to assume that ``f`` is not an :meth:`equivalence unit <InductiveValuation.is_equivalence_unit>` (default: ``False``)
- ``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``)
- ``compute_unit`` -- whether or not to compute the unit part of the decomposition (default: ``True``)
- ``degree_bound`` -- a bound on the degree of the :meth:`_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 :meth:`~sage.rings.valuation.valuation_space.DiscretePseudoValuationSpace.ElementMethods.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 :meth:`lift_to_key`). Taking `R'` an :meth:`~InductiveValuation.equivalence_reciprocal` of `R`, we have `f` equivalent to `(R'\prod_i R_i)\prod_i\phi_i`.
EXAMPLES::
sage: R.<u> = Qq(4,10) sage: S.<x> = R[] sage: v = GaussValuation(S) sage: v.equivalence_decomposition(S.zero()) Traceback (most recent call last): ... ValueError: equivalence decomposition of zero is not defined sage: v.equivalence_decomposition(S.one()) 1 + O(2^10) sage: v.equivalence_decomposition(x^2+2) ((1 + O(2^10))*x)^2 sage: v.equivalence_decomposition(x^2+1) ((1 + O(2^10))*x + 1 + O(2^10))^2
A polynomial that is an equivalence unit, is returned as the unit part of a :class:`~sage.structure.factorization.Factorization`, leading to a unit non-minimal degree::
sage: w = v.augmentation(x, 1) sage: F = w.equivalence_decomposition(x^2+1); F (1 + O(2^10))*x^2 + 1 + O(2^10) sage: F.unit() (1 + O(2^10))*x^2 + 1 + O(2^10)
However, if the polynomial has a non-unit factor, then the unit might be replaced by a factor of lower degree::
sage: f = x * (x^2 + 1) sage: F = w.equivalence_decomposition(f); F (1 + O(2^10))*x sage: F.unit() 1 + O(2^10)
Examples over an iterated unramified extension::
sage: v = v.augmentation(x^2 + x + u, 1) sage: v = v.augmentation((x^2 + x + u)^2 + 2*x*(x^2 + x + u) + 4*x, 3)
sage: v.equivalence_decomposition(x) (1 + O(2^10))*x sage: F = v.equivalence_decomposition( v.phi() ) sage: len(F) 1 sage: F = v.equivalence_decomposition( v.phi() * (x^4 + 4*x^3 + (7 + 2*u)*x^2 + (8 + 4*u)*x + 1023 + 3*u) ) sage: len(F) 2
TESTS::
sage: R.<x> = QQ[] sage: K1.<pi>=NumberField(x^3 - 2) sage: K.<alpha>=K1.galois_closure() sage: R.<x>=K[] sage: vp = QQ.valuation(2) sage: vp = vp.extension(K) sage: v0 = GaussValuation(R, vp) sage: G=x^36 + 36*x^35 + 630*x^34 + 7144*x^33 + 59055*x^32 + 379688*x^31 +1978792*x^30 + 8604440*x^29 + 31895428*x^28 + 102487784*x^27 + 289310720*x^26 + 725361352*x^25 + 1629938380*x^24 + 3307417800*x^23 + 6098786184*x^22+10273444280*x^21 + 15878121214*x^20 + 22596599536*x^19 + 29695703772*x^18 +36117601976*x^17 + 40722105266*x^16 + 42608585080*x^15 + 41395961848*x^14 +37344435656*x^13 + 31267160756*x^12 + 24271543640*x^11 + 17439809008*x^10 + 11571651608*x^9 + 7066815164*x^8 + 3953912472*x^7 + 2013737432*x^6 + 925014888*x^5 + 378067657*x^4 + 134716588*x^3 + 40441790*x^2 + 9532544*x + 1584151 sage: v1 = v0.mac_lane_step(G)[0] sage: V = v1.mac_lane_step(G) sage: v2 = V[0] sage: F = v2.equivalence_decomposition(G); F (x^4 + 2*x^2 + alpha^4 + alpha^3 + 1)^3 * (x^4 + 2*x^2 + 1/2*alpha^4 + alpha^3 + 5*alpha + 1)^3 * (x^4 + 2*x^2 + 3/2*alpha^4 + alpha^3 + 5*alpha + 1)^3 sage: v2.is_equivalent(F.prod(), G) True
"""
for (g,e) in ret], unit=self._eliminate_denominators(ret.unit()))
# A potential speedup that we tried to implement here: # When F factors as T^n - a, then instead of using any lift of T^n - a # we tried to take a lift that approximates well an n-th root of the # constant coefficient of f[0]. Doing so saved a few invocations of # mac_lane_step but in the end made hardly any difference.
F[i] = (self.phi(),e+phi_divides) break else:
r""" Return a minimal representative for ``f``, i.e., a pair `e, a` such that ``f`` :meth:`~sage.rings.valuation.valuation.DiscretePseudoValuation.is_equivalent` to `e a`, `e` is an :meth:`equivalence unit <InductiveValuation.is_equivalence_unit>`, and `a` :meth:`is_minimal` and monic.
INPUT:
- ``f`` -- a non-zero polynomial which is not an equivalence unit
OUTPUT:
A factorization which has `e` as its unit and `a` as its unique factor.
ALGORITHM:
We use the algorithm described in the proof of Lemma 4.1 of [Mac1936II]_. In the expansion `f=\sum_i f_i\phi^i` take `e=f_i` for the largest `i` with `f_i\phi^i` minimal (see :meth:`~sage.rings.valuation.developing_valuation.DevelopingValuation.effective_degree`). Let `h` be the :meth:`~InductiveValuation.equivalence_reciprocal` of `e` and take `a` given by the terms of minimal valuation in the expansion of `e f`.
EXAMPLES::
sage: R.<u> = Qq(4,10) sage: S.<x> = R[] sage: v = GaussValuation(S) sage: v.minimal_representative(x + 2) (1 + O(2^10))*x
sage: v = v.augmentation(x, 1) sage: v.minimal_representative(x + 2) (1 + O(2^10))*x + 2 + O(2^11) sage: f = x^3 + 6*x + 4 sage: F = v.minimal_representative(f); F (2 + 2^2 + O(2^11)) * ((1 + O(2^10))*x + 2 + O(2^11)) sage: v.is_minimal(F[0][0]) True sage: v.is_equivalent(F.prod(), f) True
"""
raise NotImplementedError("only implemented for polynomial rings over fields")
raise ValueError("zero has no minimal representative")
raise ValueError("equivalence units can not have a minimal representative")
def lift_to_key(self, F): """ Lift the irreducible polynomial ``F`` from the :meth:`~sage.rings.valuation.valuation_space.DiscretePseudoValuationSpace.ElementMethods.residue_ring` to a key polynomial over this valuation.
INPUT:
- ``F`` -- an irreducible non-constant monic polynomial in :meth:`~sage.rings.valuation.valuation_space.DiscretePseudoValuationSpace.ElementMethods.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 :meth:`augmentation` with this polynomial adjoins a root of ``F`` to the resulting :meth:`~sage.rings.valuation.valuation_space.DiscretePseudoValuationSpace.ElementMethods.residue_ring`.
More specifically, if ``F`` is not the generator of the residue ring, then multiplying ``f`` with the :meth:`~InductiveValuation.equivalence_reciprocal` of the :meth:`~InductiveValuation.equivalence_unit` of the valuation of ``f``, produces a unit which reduces to ``F``.
EXAMPLES::
sage: R.<u> = Qq(4,10) sage: S.<x> = R[] sage: v = GaussValuation(S) sage: y = v.residue_ring().gen() sage: u0 = v.residue_ring().base_ring().gen() sage: f = v.lift_to_key(y^2 + y + u0); f (1 + O(2^10))*x^2 + (1 + O(2^10))*x + u + O(2^10)
"""
r""" Return a polynomial in the domain of this valuation that :meth:`is_equivalent` to ``f``.
INPUT:
- ``f`` -- a polynomial with coefficients in the fraction field of the base ring of the domain of this valuation.
EXAMPLES::
sage: R.<x> = ZZ[] sage: v = GaussValuation(R, ZZ.valuation(2)) sage: v._eliminate_denominators(x/3) x
In general such a polynomial may not exist::
sage: w = v.augmentation(x, 1) sage: w._eliminate_denominators(x/2) Traceback (most recent call last): ... ValueError: element has no approximate inverse in this ring
In general it exists iff the coefficients of minimal valuation in the `\phi`-adic expansion of ``f`` do not have denominators of positive valuation and if the same is true for these coefficients in their expansion; at least if the coefficient ring's residue ring is already a field::
sage: w._eliminate_denominators(x^3/2 + x) x
"""
# drop coefficients whose valuation is not minimal (recursively)
# if this fails then there is no equivalent polynomial in the domain of this valuation lambda c: c.numerator()*nonfraction_valuation.inverse(c.denominator(), valuation + nonfraction_valuation(c.denominator()) - nonfraction_valuation(c.numerator()) + nonfraction_valuation.value_group().gen()), nonfractions) assert w.is_equivalent(f, ret) return ret
r""" Test the correctness of :meth:`_eliminate_denominators`.
EXAMPLES::
sage: R.<x> = ZZ[] sage: v = GaussValuation(R, ZZ.valuation(2)) sage: v._test_eliminate_denominators()
"""
r""" Test the correctness of :meth:`lift_to_key`.
EXAMPLES::
sage: R.<x> = QQ[] sage: v = GaussValuation(R, valuations.TrivialValuation(QQ)) sage: v._test_lift_to_key()
"""
except NotImplementedError: from sage.categories.fields import Fields if self.domain().base() in Fields(): raise return
except NotImplementedError: from sage.categories.fields import Fields if self.domain().base() in Fields(): raise continue
# check that augmentation produces a valuation with roots of F # in the residue ring
# check that f has the right reduction else:
r""" Test the correctness of :meth:`is_equivalence_irreducible`.
EXAMPLES::
sage: R.<x> = QQ[] sage: v = GaussValuation(R, valuations.TrivialValuation(QQ)) sage: v._test_is_equivalence_irreducible()
""" tester.assertTrue(f.is_constant() or self.is_equivalence_irreducible(f))
r""" Abstract base class for an inductive valuation which can not be augmented further.
TESTS::
sage: R.<x> = QQ[] sage: v = GaussValuation(R, valuations.TrivialValuation(QQ)) sage: w = v.augmentation(x^2 + x + 1, infinity) sage: from sage.rings.valuation.inductive_valuation import FinalInductiveValuation sage: isinstance(w, FinalInductiveValuation) True
"""
r""" 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)
""" r""" TESTS::
sage: R.<x> = QQ[] sage: v = GaussValuation(R, QQ.valuation(2)) sage: w = v.augmentation(x^2 + x + 1, infinity) sage: from sage.rings.valuation.inductive_valuation import InfiniteInductiveValuation sage: isinstance(w, InfiniteInductiveValuation) True
"""
r""" 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
""" return super(InfiniteInductiveValuation, self).change_domain(ring)
r""" Lift ``c`` to maximal precision if the parent is not exact.
EXAMPLES::
sage: R = Zp(2,5) sage: x = R(1,2); x 1 + O(2^2) sage: from sage.rings.valuation.inductive_valuation import _lift_to_maximal_precision sage: _lift_to_maximal_precision(x) 1 + O(2^5)
sage: x = 1 sage: _lift_to_maximal_precision(x) 1
"""
|