# Source code for sympy.polys.agca.ideals

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

from __future__ import print_function, division

from sympy.polys.polyerrors import CoercionFailed

from sympy.core.compatibility import reduce

[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_principal
- height, depth

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

"""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

"""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.

>>> 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.

>>> 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 \}.

>>> 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.

>>> 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.

>>> 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):
"""
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.

>>> 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

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)

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.

>>> 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.

>>> 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.

>>> 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.

>>> 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]