Source code for sympy.polys.agca.ideals

"""Computations with ideals of polynomial rings."""

from __future__ import print_function, division

from sympy.core.compatibility import reduce
from sympy.polys.polyerrors import CoercionFailed


[docs]class Ideal(object): """ Abstract base class for ideals. Do not instantiate - use explicit constructors in the ring class instead: >>> from sympy import QQ >>> from sympy.abc import x >>> QQ.old_poly_ring(x).ideal(x+1) <x + 1> Attributes - ring - the ring this ideal belongs to Non-implemented methods: - _contains_elem - _contains_ideal - _quotient - _intersect - _union - _product - is_whole_ring - is_zero - is_prime, is_maximal, is_primary, is_radical - is_principal - height, depth - radical Methods that likely should be overridden in subclasses: - reduce_element """ def _contains_elem(self, x): """Implementation of element containment.""" raise NotImplementedError def _contains_ideal(self, I): """Implementation of ideal containment.""" raise NotImplementedError def _quotient(self, J): """Implementation of ideal quotient.""" raise NotImplementedError def _intersect(self, J): """Implementation of ideal intersection.""" raise NotImplementedError
[docs] def is_whole_ring(self): """Return True if ``self`` is the whole ring.""" raise NotImplementedError
[docs] def is_zero(self): """Return True if ``self`` is the zero ideal.""" raise NotImplementedError
def _equals(self, J): """Implementation of ideal equality.""" return self._contains_ideal(J) and J._contains_ideal(self)
[docs] def is_prime(self): """Return True if ``self`` is a prime ideal.""" raise NotImplementedError
[docs] def is_maximal(self): """Return True if ``self`` is a maximal ideal.""" raise NotImplementedError
[docs] def is_radical(self): """Return True if ``self`` is a radical ideal.""" raise NotImplementedError
[docs] def is_primary(self): """Return True if ``self`` is a primary ideal.""" raise NotImplementedError
[docs] def is_principal(self): """Return True if ``self`` is a principal ideal.""" raise NotImplementedError
[docs] def radical(self): """Compute the radical of ``self``.""" raise NotImplementedError
[docs] def depth(self): """Compute the depth of ``self``.""" raise NotImplementedError
[docs] def height(self): """Compute the height of ``self``.""" raise NotImplementedError
# TODO more # non-implemented methods end here def __init__(self, ring): self.ring = ring def _check_ideal(self, J): """Helper to check ``J`` is an ideal of our ring.""" if not isinstance(J, Ideal) or J.ring != self.ring: raise ValueError( 'J must be an ideal of %s, got %s' % (self.ring, J))
[docs] def contains(self, elem): """ Return True if ``elem`` is an element of this ideal. Examples ======== >>> from sympy.abc import x >>> from sympy import QQ >>> QQ.old_poly_ring(x).ideal(x+1, x-1).contains(3) True >>> QQ.old_poly_ring(x).ideal(x**2, x**3).contains(x) False """ return self._contains_elem(self.ring.convert(elem))
[docs] def subset(self, other): """ Returns True if ``other`` is is a subset of ``self``. Here ``other`` may be an ideal. Examples ======== >>> from sympy.abc import x >>> from sympy import QQ >>> I = QQ.old_poly_ring(x).ideal(x+1) >>> I.subset([x**2 - 1, x**2 + 2*x + 1]) True >>> I.subset([x**2 + 1, x + 1]) False >>> I.subset(QQ.old_poly_ring(x).ideal(x**2 - 1)) True """ if isinstance(other, Ideal): return self._contains_ideal(other) return all(self._contains_elem(x) for x in other)
[docs] def quotient(self, J, **opts): r""" Compute the ideal quotient of ``self`` by ``J``. That is, if ``self`` is the ideal `I`, compute the set `I : J = \{x \in R | xJ \subset I \}`. Examples ======== >>> from sympy.abc import x, y >>> from sympy import QQ >>> R = QQ.old_poly_ring(x, y) >>> R.ideal(x*y).quotient(R.ideal(x)) <y> """ self._check_ideal(J) return self._quotient(J, **opts)
[docs] def intersect(self, J): """ Compute the intersection of self with ideal J. Examples ======== >>> from sympy.abc import x, y >>> from sympy import QQ >>> R = QQ.old_poly_ring(x, y) >>> R.ideal(x).intersect(R.ideal(y)) <x*y> """ self._check_ideal(J) return self._intersect(J)
[docs] def saturate(self, J): r""" Compute the ideal saturation of ``self`` by ``J``. That is, if ``self`` is the ideal `I`, compute the set `I : J^\infty = \{x \in R | xJ^n \subset I \text{ for some } n\}`. """ raise NotImplementedError
# Note this can be implemented using repeated quotient
[docs] def union(self, J): """ Compute the ideal generated by the union of ``self`` and ``J``. Examples ======== >>> from sympy.abc import x >>> from sympy import QQ >>> QQ.old_poly_ring(x).ideal(x**2 - 1).union(QQ.old_poly_ring(x).ideal((x+1)**2)) == QQ.old_poly_ring(x).ideal(x+1) True """ self._check_ideal(J) return self._union(J)
[docs] def product(self, J): r""" Compute the ideal product of ``self`` and ``J``. That is, compute the ideal generated by products `xy`, for `x` an element of ``self`` and `y \in J`. Examples ======== >>> from sympy.abc import x, y >>> from sympy import QQ >>> QQ.old_poly_ring(x, y).ideal(x).product(QQ.old_poly_ring(x, y).ideal(y)) <x*y> """ self._check_ideal(J) return self._product(J)
[docs] def reduce_element(self, x): """ Reduce the element ``x`` of our ring modulo the ideal ``self``. Here "reduce" has no specific meaning: it could return a unique normal form, simplify the expression a bit, or just do nothing. """ return x
def __add__(self, e): if not isinstance(e, Ideal): R = self.ring.quotient_ring(self) if isinstance(e, R.dtype): return e if isinstance(e, R.ring.dtype): return R(e) return R.convert(e) self._check_ideal(e) return self.union(e) __radd__ = __add__ def __mul__(self, e): if not isinstance(e, Ideal): try: e = self.ring.ideal(e) except CoercionFailed: return NotImplemented self._check_ideal(e) return self.product(e) __rmul__ = __mul__ def __pow__(self, exp): if exp < 0: raise NotImplementedError # TODO exponentiate by squaring return reduce(lambda x, y: x*y, [self]*exp, self.ring.ideal(1)) def __eq__(self, e): if not isinstance(e, Ideal) or e.ring != self.ring: return False return self._equals(e) def __ne__(self, e): return not (self == e)
class ModuleImplementedIdeal(Ideal): """ Ideal implementation relying on the modules code. Attributes: - _module - the underlying module """ def __init__(self, ring, module): Ideal.__init__(self, ring) self._module = module def _contains_elem(self, x): return self._module.contains([x]) def _contains_ideal(self, J): if not isinstance(J, ModuleImplementedIdeal): raise NotImplementedError return self._module.is_submodule(J._module) def _intersect(self, J): if not isinstance(J, ModuleImplementedIdeal): raise NotImplementedError return self.__class__(self.ring, self._module.intersect(J._module)) def _quotient(self, J, **opts): if not isinstance(J, ModuleImplementedIdeal): raise NotImplementedError return self._module.module_quotient(J._module, **opts) def _union(self, J): if not isinstance(J, ModuleImplementedIdeal): raise NotImplementedError return self.__class__(self.ring, self._module.union(J._module)) @property def gens(self): """ Return generators for ``self``. Examples ======== >>> from sympy import QQ >>> from sympy.abc import x, y >>> list(QQ.old_poly_ring(x, y).ideal(x, y, x**2 + y).gens) [x, y, x**2 + y] """ return (x[0] for x in self._module.gens) def is_zero(self): """ Return True if ``self`` is the zero ideal. Examples ======== >>> from sympy.abc import x >>> from sympy import QQ >>> QQ.old_poly_ring(x).ideal(x).is_zero() False >>> QQ.old_poly_ring(x).ideal().is_zero() True """ return self._module.is_zero() def is_whole_ring(self): """ Return True if ``self`` is the whole ring, i.e. one generator is a unit. Examples ======== >>> from sympy.abc import x >>> from sympy import QQ, ilex >>> QQ.old_poly_ring(x).ideal(x).is_whole_ring() False >>> QQ.old_poly_ring(x).ideal(3).is_whole_ring() True >>> QQ.old_poly_ring(x, order=ilex).ideal(2 + x).is_whole_ring() True """ return self._module.is_full_module() def __repr__(self): from sympy import sstr return '<' + ','.join(sstr(x) for [x] in self._module.gens) + '>' # NOTE this is the only method using the fact that the module is a SubModule def _product(self, J): if not isinstance(J, ModuleImplementedIdeal): raise NotImplementedError return self.__class__(self.ring, self._module.submodule( *[[x*y] for [x] in self._module.gens for [y] in J._module.gens])) def in_terms_of_generators(self, e): """ Express ``e`` in terms of the generators of ``self``. Examples ======== >>> from sympy.abc import x >>> from sympy import QQ >>> I = QQ.old_poly_ring(x).ideal(x**2 + 1, x) >>> I.in_terms_of_generators(1) [1, -x] """ return self._module.in_terms_of_generators([e]) def reduce_element(self, x, **options): return self._module.reduce_element([x], **options)[0]