Coverage for local/lib/python2.7/site-packages/sage/rings/valuation/gauss_valuation.py : 91%
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 -*- Gauss valuations on polynomial rings
This file implements Gauss valuations for polynomial rings, i.e. discrete valuations which assign to a polynomial the minimal valuation of its coefficients.
AUTHORS:
- Julian Rüth (2013-04-15): initial version
EXAMPLES:
A Gauss valuation maps a polynomial to the minimal valuation of any of its coefficients::
sage: R.<x> = QQ[] sage: v0 = QQ.valuation(2) sage: v = GaussValuation(R, v0); v Gauss valuation induced by 2-adic valuation sage: v(2*x + 2) 1
Gauss valuations can also be defined iteratively based on valuations over polynomial rings::
sage: v = v.augmentation(x, 1/4); v [ Gauss valuation induced by 2-adic valuation, v(x) = 1/4 ] sage: v = v.augmentation(x^4+2*x^3+2*x^2+2*x+2, 4/3); v [ Gauss valuation induced by 2-adic valuation, v(x) = 1/4, v(x^4 + 2*x^3 + 2*x^2 + 2*x + 2) = 4/3 ] sage: S.<T> = R[] sage: w = GaussValuation(S, v); w Gauss valuation induced by [ Gauss valuation induced by 2-adic valuation, v(x) = 1/4, v(x^4 + 2*x^3 + 2*x^2 + 2*x + 2) = 4/3 ] sage: w(2*T + 1) 0
""" #***************************************************************************** # Copyright (C) 2013-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""" Create a Gauss valuation on ``domain``.
INPUT:
- ``domain`` -- a univariate polynomial ring
- ``v`` -- a valuation on the base ring of ``domain``, the underlying valuation on the constants of the polynomial ring (if unspecified take the natural valuation on the valued ring ``domain``.)
EXAMPLES:
The Gauss valuation is the minimum of the valuation of the coefficients::
sage: v = QQ.valuation(2) sage: R.<x> = QQ[] sage: w = GaussValuation(R, v) sage: w(2) 1 sage: w(x) 0 sage: w(x + 2) 0
""" r""" Normalize and check the parameters to create a Gauss valuation.
TESTS::
sage: v = QQ.valuation(2) sage: R.<x> = ZZ[] sage: GaussValuation.create_key(R, v) Traceback (most recent call last): ... ValueError: the domain of v must be the base ring of domain but 2-adic valuation is not defined over Integer Ring but over Rational Field
""" raise TypeError("GaussValuations can only be created over polynomial rings but %r is not a polynomial ring"%(domain,)) raise NotImplementedError("domain must be univariate but %r is not univariate"%(domain,))
raise ValueError("v must be a discrete valuation but %r is not"%(v,))
r""" Create a Gauss valuation from normalized parameters.
TESTS::
sage: v = QQ.valuation(2) sage: R.<x> = QQ[] sage: GaussValuation.create_object(0, (R, v)) Gauss valuation induced by 2-adic valuation
"""
""" A Gauss valuation on a polynomial ring ``domain``.
INPUT:
- ``domain`` -- a univariate polynomial ring over a valued ring `R`
- ``v`` -- a discrete valuation on `R`
EXAMPLES::
sage: R = Zp(3,5) sage: S.<x> = R[] sage: v0 = R.valuation() sage: v = GaussValuation(S, v0); v Gauss valuation induced by 3-adic valuation
sage: S.<x> = QQ[] sage: v = GaussValuation(S, QQ.valuation(5)); v Gauss valuation induced by 5-adic valuation
TESTS::
sage: TestSuite(v).run() # long time
""" """ TESTS::
sage: from sage.rings.valuation.gauss_valuation import GaussValuation_generic sage: S.<x> = QQ[] sage: v = GaussValuation(S, QQ.valuation(5)) sage: isinstance(v, GaussValuation_generic) True
"""
""" Return the value group of this valuation.
EXAMPLES::
sage: S.<x> = QQ[] sage: v = GaussValuation(S, QQ.valuation(5)) sage: v.value_group() Additive Abelian Group generated by 1
"""
r""" Return the value semigroup of this valuation.
EXAMPLES::
sage: S.<x> = QQ[] sage: v = GaussValuation(S, QQ.valuation(5)) sage: v.value_semigroup() Additive Abelian Semigroup generated by -1, 1
"""
""" Return a printable representation of this valuation.
EXAMPLES::
sage: S.<x> = QQ[] sage: v = GaussValuation(S, QQ.valuation(5)) sage: v # indirect doctest Gauss valuation induced by 5-adic valuation
"""
def uniformizer(self): """ Return a uniformizer of this valuation, i.e., a uniformizer of the valuation of the base ring.
EXAMPLES::
sage: S.<x> = QQ[] sage: v = GaussValuation(S, QQ.valuation(5)) sage: v.uniformizer() 5 sage: v.uniformizer().parent() is S True
"""
""" Return the valuations of the `f_i\phi^i` in the expansion `f=\sum f_i\phi^i`.
INPUT:
- ``f`` -- a polynomial in the domain of this valuation
- ``coefficients`` -- the coefficients of ``f`` as produced by :meth:`~sage.rings.valuation.developing_valuation.DevelopingValuation.coefficients` or ``None`` (default: ``None``); this can be used to speed up the computation when the expansion of ``f`` is already known from a previous computation.
- ``call_error`` -- whether or not to speed up the computation by assuming that the result is only used to compute the valuation of ``f`` (default: ``False``)
OUTPUT:
A list, each entry a rational numbers or infinity, the valuations of `f_0, f_1\phi, \dots`
EXAMPLES::
sage: R = ZZ sage: S.<x> = R[] sage: v = GaussValuation(S, R.valuation(2)) sage: f = x^2 + 2*x + 16 sage: list(v.valuations(f)) [4, 1, 0]
"""
def residue_ring(self): """ Return the residue ring of this valuation, i.e., the elements of valuation zero module the elements of positive valuation.
EXAMPLES::
sage: S.<x> = Qp(2,5)[] sage: v = GaussValuation(S) sage: v.residue_ring() Univariate Polynomial Ring in x over Finite Field of size 2 (using ...)
"""
""" Return the reduction of ``f`` modulo this valuation.
INPUT:
- ``f`` -- an integral element of the domain of this valuation
- ``check`` -- whether or not to check whether ``f`` has non-negative valuation (default: ``True``)
- ``degree_bound`` -- an a-priori known bound on the degree of the result which can speed up the computation (default: not set)
- ``coefficients`` -- the coefficients of ``f`` as produced by :meth:`~sage.rings.valuation.developing_valuation.DevelopingValuation.coefficients` or ``None`` (default: ``None``); ignored
- ``valuations`` -- the valuations of ``coefficients`` or ``None`` (default: ``None``); ignored
OUTPUT:
A polynomial in the :meth:`residue_ring` of this valuation.
EXAMPLES::
sage: S.<x> = Qp(2,5)[] sage: v = GaussValuation(S) sage: f = x^2 + 2*x + 16 sage: v.reduce(f) x^2 sage: v.reduce(f).parent() is v.residue_ring() True
The reduction is only defined for integral elements::
sage: f = x^2/2 sage: v.reduce(f) Traceback (most recent call last): ... ValueError: reduction not defined for non-integral elements and (2^-1 + O(2^4))*x^2 is not integral over Gauss valuation induced by 2-adic valuation
.. SEEALSO::
:meth:`lift`
"""
raise
""" Return a lift of ``F``.
INPUT:
- ``F`` -- a polynomial over the :meth:`residue_ring` of this valuation
OUTPUT:
a (possibly non-monic) polynomial in the domain of this valuation which reduces to ``F``
EXAMPLES::
sage: S.<x> = Qp(3,5)[] sage: v = GaussValuation(S) sage: f = x^2 + 2*x + 16 sage: F = v.reduce(f); F x^2 + 2*x + 1 sage: g = v.lift(F); g (1 + O(3^5))*x^2 + (2 + O(3^5))*x + (1 + O(3^5)) sage: v.is_equivalent(f,g) True sage: g.parent() is v.domain() True
.. SEEALSO::
:meth:`reduce`
"""
""" Lift the irreducible polynomial ``F`` from the :meth:`residue_ring` to a key polynomial over this valuation.
INPUT:
- ``F`` -- an irreducible non-constant monic polynomial in :meth:`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, for a suitable equivalence unit `R`, satifies that the reduction of `Rf` is ``F``
EXAMPLES::
sage: R.<u> = QQ sage: S.<x> = R[] sage: v = GaussValuation(S, QQ.valuation(2)) sage: y = v.residue_ring().gen() sage: f = v.lift_to_key(y^2 + y + 1); f x^2 + x + 1
"""
raise ValueError("F must not be constant but %r is constant"%(F,)) raise ValueError("F must be monic but %r is not monic"%(F,)) raise ValueError("F must be irreducible but %r factors"%(F,))
""" Return an equivalence unit of valuation ``s``.
INPUT:
- ``s`` -- an element of the :meth:`value_group`
- ``reciprocal`` -- a boolean (default: ``False``); whether or not to return the equivalence unit as the :meth:`~sage.rings.valuation.inductive_valuation.InductiveValuation.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))
"""
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
"""
""" Return the ramification index of this valuation over its underlying Gauss valuation, i.e., 1.
EXAMPLES::
sage: R.<u> = Qq(4,5) sage: S.<x> = R[] sage: v = GaussValuation(S) sage: v.E() 1
"""
""" Return the degree of the residue field extension of this valuation over the Gauss valuation, i.e., 1.
EXAMPLES::
sage: R.<u> = Qq(4,5) sage: S.<x> = R[] sage: v = GaussValuation(S) sage: v.F() 1
"""
r""" Return this valuation as a valuation over ``ring``.
EXAMPLES::
sage: v = ZZ.valuation(2) sage: R.<x> = ZZ[] sage: w = GaussValuation(R, v) sage: w.change_domain(QQ['x']) Gauss valuation induced by 2-adic valuation
""" return super(GaussValuation_generic, self).change_domain(ring)
r""" Return the extensions of this valuation to ``ring``.
EXAMPLES::
sage: v = ZZ.valuation(2) sage: R.<x> = ZZ[] sage: w = GaussValuation(R, v) sage: w.extensions(GaussianIntegers()['x']) [Gauss valuation induced by 2-adic valuation]
"""
r""" Return the restriction of this valuation to ``ring``.
EXAMPLES::
sage: v = ZZ.valuation(2) sage: R.<x> = ZZ[] sage: w = GaussValuation(R, v) sage: w.restriction(ZZ) 2-adic valuation
""" return super(GaussValuation_generic, self).restriction(ring)
r""" Return whether this valuation is a Gauss valuation.
EXAMPLES::
sage: R.<u> = Qq(4,5) sage: S.<x> = R[] sage: v = GaussValuation(S) sage: v.is_gauss_valuation() True
"""
r""" Return a list with the chain of augmentations down to the underlying Gauss valuation.
EXAMPLES::
sage: R.<u> = Qq(4,5) sage: S.<x> = R[] sage: v = GaussValuation(S) sage: v.augmentation_chain() [Gauss valuation induced by 2-adic valuation]
"""
r""" Return whether this is a trivial valuation (sending everything but zero to zero.)
EXAMPLES::
sage: R.<x> = QQ[] sage: v = GaussValuation(R, valuations.TrivialValuation(QQ)) sage: v.is_trivial() True
"""
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> = Qp(2, 5)[] sage: v = GaussValuation(R) sage: v.monic_integral_model(5*x^2 + 1/2*x + 1/4) (Ring endomorphism of Univariate Polynomial Ring in x over 2-adic Field with capped relative precision 5 Defn: (1 + O(2^5))*x |--> (2^-1 + O(2^4))*x, Ring endomorphism of Univariate Polynomial Ring in x over 2-adic Field with capped relative precision 5 Defn: (1 + O(2^5))*x |--> (2 + O(2^6))*x, (1 + O(2^5))*x^2 + (1 + 2^2 + 2^3 + O(2^5))*x + (1 + 2^2 + 2^3 + O(2^5)))
""" # this might fail if the base ring is not a field
# this might fail if the base ring is not a field
r""" Return whether this valuation is greater than or equal to ``other`` everywhere.
EXAMPLES::
sage: R.<x> = QQ[] sage: v = GaussValuation(R, QQ.valuation(2)) sage: w = GaussValuation(R, QQ.valuation(3)) sage: v >= w False sage: w >= v False
""" from .augmented_valuation import AugmentedValuation_base if isinstance(other, AugmentedValuation_base): return False if other.is_trivial(): return other.is_discrete_valuation() return super(GaussValuation_generic, self)._ge_(other)
r""" Return this valuation scaled by ``scalar``.
EXAMPLES::
sage: R.<x> = QQ[] sage: v = GaussValuation(R, QQ.valuation(2)) sage: 3*v # indirect doctest Gauss valuation induced by 3 * 2-adic valuation
""" return super(GaussValuation_generic, self).scale(scalar)
r""" Return an estimate on the coefficient size of ``f``.
The number returned is an estimate on the factor between the number of Bits used by ``f`` and the minimal number of bits used by an element Congruent to ``f``.
This is used by :meth:`simplify` to decide whether simplification of Coefficients is going to lead to a significant shrinking of the Coefficients of ``f``.
EXAMPLES::
sage: R.<x> = QQ[] sage: v = GaussValuation(R, QQ.valuation(2)) sage: v._relative_size(x + 1024) 6
For performance reasons, only the constant coefficient is considered. (In common appplications, the constant coefficient shows the most critical coefficient growth)::
sage: v._relative_size(1024*x + 1) 1
"""
r""" Return a simplified version of ``f``.
Produce an element which differs from ``f`` by an element of valuation strictly greater than the valuation of ``f`` (or strictly greater than ``error`` if set.)
INPUT:
- ``f`` -- an element in the domain of this valuation
- ``error`` -- a rational, infinity, or ``None`` (default: ``None``), the error allowed to introduce through the simplification
- ``force`` -- whether or not to simplify ``f`` even if there is heuristically no change in the coefficient size of ``f`` expected (default: ``False``)
- ``effective_degree`` -- when set, assume that coefficients beyond ``effective_degree`` can be safely dropped (default: ``None``)
- ``size_heuristic_bound`` -- when ``force`` is not set, the expected factor by which the coefficients need to shrink to perform an actual simplification (default: 32)
- ``phiadic`` -- whether to simplify in the `x`-adic expansion; the parameter is ignored as no other simplification is implemented
EXAMPLES::
sage: R.<u> = Qq(4, 5) sage: S.<x> = R[] sage: v = GaussValuation(S) sage: f = x^10/2 + 1 sage: v.simplify(f) (2^-1 + O(2^4))*x^10 + 1 + O(2^5)
"""
# if the caller was sure that we should simplify, then we should try to do the best simplification possible error = self(f) if force else self.uppper_bound(f)
r""" Return an lower bound of this valuation at ``f``.
Use this method to get an approximation of the valuation of ``f`` when speed is more important than accuracy.
EXAMPLES::
sage: R.<u> = Qq(4, 5) sage: S.<x> = R[] sage: v = GaussValuation(S) sage: v.lower_bound(1024*x + 2) 1 sage: v(1024*x + 2) 1
"""
r""" Return an upper bound of this valuation at ``f``.
Use this method to get an approximation of the valuation of ``f`` when speed is more important than accuracy.
EXAMPLES::
sage: R.<u> = Qq(4, 5) sage: S.<x> = R[] sage: v = GaussValuation(S) sage: v.upper_bound(1024*x + 1) 10 sage: v(1024*x + 1) 0
""" else: |