1"""Computations with ideals of polynomial rings."""
2
3from functools import reduce
4
5from sympy.polys.polyerrors import CoercionFailed
6
7
8class Ideal:
9    """
10    Abstract base class for ideals.
11
12    Do not instantiate - use explicit constructors in the ring class instead:
13
14    >>> from sympy import QQ
15    >>> from sympy.abc import x
16    >>> QQ.old_poly_ring(x).ideal(x+1)
17    <x + 1>
18
19    Attributes
20
21    - ring - the ring this ideal belongs to
22
23    Non-implemented methods:
24
25    - _contains_elem
26    - _contains_ideal
27    - _quotient
28    - _intersect
29    - _union
30    - _product
31    - is_whole_ring
32    - is_zero
33    - is_prime, is_maximal, is_primary, is_radical
34    - is_principal
35    - height, depth
36    - radical
37
38    Methods that likely should be overridden in subclasses:
39
40    - reduce_element
41    """
42
43    def _contains_elem(self, x):
44        """Implementation of element containment."""
45        raise NotImplementedError
46
47    def _contains_ideal(self, I):
48        """Implementation of ideal containment."""
49        raise NotImplementedError
50
51    def _quotient(self, J):
52        """Implementation of ideal quotient."""
53        raise NotImplementedError
54
55    def _intersect(self, J):
56        """Implementation of ideal intersection."""
57        raise NotImplementedError
58
59    def is_whole_ring(self):
60        """Return True if ``self`` is the whole ring."""
61        raise NotImplementedError
62
63    def is_zero(self):
64        """Return True if ``self`` is the zero ideal."""
65        raise NotImplementedError
66
67    def _equals(self, J):
68        """Implementation of ideal equality."""
69        return self._contains_ideal(J) and J._contains_ideal(self)
70
71    def is_prime(self):
72        """Return True if ``self`` is a prime ideal."""
73        raise NotImplementedError
74
75    def is_maximal(self):
76        """Return True if ``self`` is a maximal ideal."""
77        raise NotImplementedError
78
79    def is_radical(self):
80        """Return True if ``self`` is a radical ideal."""
81        raise NotImplementedError
82
83    def is_primary(self):
84        """Return True if ``self`` is a primary ideal."""
85        raise NotImplementedError
86
87    def is_principal(self):
88        """Return True if ``self`` is a principal ideal."""
89        raise NotImplementedError
90
91    def radical(self):
92        """Compute the radical of ``self``."""
93        raise NotImplementedError
94
95    def depth(self):
96        """Compute the depth of ``self``."""
97        raise NotImplementedError
98
99    def height(self):
100        """Compute the height of ``self``."""
101        raise NotImplementedError
102
103    # TODO more
104
105    # non-implemented methods end here
106
107    def __init__(self, ring):
108        self.ring = ring
109
110    def _check_ideal(self, J):
111        """Helper to check ``J`` is an ideal of our ring."""
112        if not isinstance(J, Ideal) or J.ring != self.ring:
113            raise ValueError(
114                'J must be an ideal of %s, got %s' % (self.ring, J))
115
116    def contains(self, elem):
117        """
118        Return True if ``elem`` is an element of this ideal.
119
120        Examples
121        ========
122
123        >>> from sympy.abc import x
124        >>> from sympy import QQ
125        >>> QQ.old_poly_ring(x).ideal(x+1, x-1).contains(3)
126        True
127        >>> QQ.old_poly_ring(x).ideal(x**2, x**3).contains(x)
128        False
129        """
130        return self._contains_elem(self.ring.convert(elem))
131
132    def subset(self, other):
133        """
134        Returns True if ``other`` is is a subset of ``self``.
135
136        Here ``other`` may be an ideal.
137
138        Examples
139        ========
140
141        >>> from sympy.abc import x
142        >>> from sympy import QQ
143        >>> I = QQ.old_poly_ring(x).ideal(x+1)
144        >>> I.subset([x**2 - 1, x**2 + 2*x + 1])
145        True
146        >>> I.subset([x**2 + 1, x + 1])
147        False
148        >>> I.subset(QQ.old_poly_ring(x).ideal(x**2 - 1))
149        True
150        """
151        if isinstance(other, Ideal):
152            return self._contains_ideal(other)
153        return all(self._contains_elem(x) for x in other)
154
155    def quotient(self, J, **opts):
156        r"""
157        Compute the ideal quotient of ``self`` by ``J``.
158
159        That is, if ``self`` is the ideal `I`, compute the set
160        `I : J = \{x \in R | xJ \subset I \}`.
161
162        Examples
163        ========
164
165        >>> from sympy.abc import x, y
166        >>> from sympy import QQ
167        >>> R = QQ.old_poly_ring(x, y)
168        >>> R.ideal(x*y).quotient(R.ideal(x))
169        <y>
170        """
171        self._check_ideal(J)
172        return self._quotient(J, **opts)
173
174    def intersect(self, J):
175        """
176        Compute the intersection of self with ideal J.
177
178        Examples
179        ========
180
181        >>> from sympy.abc import x, y
182        >>> from sympy import QQ
183        >>> R = QQ.old_poly_ring(x, y)
184        >>> R.ideal(x).intersect(R.ideal(y))
185        <x*y>
186        """
187        self._check_ideal(J)
188        return self._intersect(J)
189
190    def saturate(self, J):
191        r"""
192        Compute the ideal saturation of ``self`` by ``J``.
193
194        That is, if ``self`` is the ideal `I`, compute the set
195        `I : J^\infty = \{x \in R | xJ^n \subset I \text{ for some } n\}`.
196        """
197        raise NotImplementedError
198        # Note this can be implemented using repeated quotient
199
200    def union(self, J):
201        """
202        Compute the ideal generated by the union of ``self`` and ``J``.
203
204        Examples
205        ========
206
207        >>> from sympy.abc import x
208        >>> from sympy import QQ
209        >>> 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)
210        True
211        """
212        self._check_ideal(J)
213        return self._union(J)
214
215    def product(self, J):
216        r"""
217        Compute the ideal product of ``self`` and ``J``.
218
219        That is, compute the ideal generated by products `xy`, for `x` an element
220        of ``self`` and `y \in J`.
221
222        Examples
223        ========
224
225        >>> from sympy.abc import x, y
226        >>> from sympy import QQ
227        >>> QQ.old_poly_ring(x, y).ideal(x).product(QQ.old_poly_ring(x, y).ideal(y))
228        <x*y>
229        """
230        self._check_ideal(J)
231        return self._product(J)
232
233    def reduce_element(self, x):
234        """
235        Reduce the element ``x`` of our ring modulo the ideal ``self``.
236
237        Here "reduce" has no specific meaning: it could return a unique normal
238        form, simplify the expression a bit, or just do nothing.
239        """
240        return x
241
242    def __add__(self, e):
243        if not isinstance(e, Ideal):
244            R = self.ring.quotient_ring(self)
245            if isinstance(e, R.dtype):
246                return e
247            if isinstance(e, R.ring.dtype):
248                return R(e)
249            return R.convert(e)
250        self._check_ideal(e)
251        return self.union(e)
252
253    __radd__ = __add__
254
255    def __mul__(self, e):
256        if not isinstance(e, Ideal):
257            try:
258                e = self.ring.ideal(e)
259            except CoercionFailed:
260                return NotImplemented
261        self._check_ideal(e)
262        return self.product(e)
263
264    __rmul__ = __mul__
265
266    def __pow__(self, exp):
267        if exp < 0:
268            raise NotImplementedError
269        # TODO exponentiate by squaring
270        return reduce(lambda x, y: x*y, [self]*exp, self.ring.ideal(1))
271
272    def __eq__(self, e):
273        if not isinstance(e, Ideal) or e.ring != self.ring:
274            return False
275        return self._equals(e)
276
277    def __ne__(self, e):
278        return not (self == e)
279
280
281class ModuleImplementedIdeal(Ideal):
282    """
283    Ideal implementation relying on the modules code.
284
285    Attributes:
286
287    - _module - the underlying module
288    """
289
290    def __init__(self, ring, module):
291        Ideal.__init__(self, ring)
292        self._module = module
293
294    def _contains_elem(self, x):
295        return self._module.contains([x])
296
297    def _contains_ideal(self, J):
298        if not isinstance(J, ModuleImplementedIdeal):
299            raise NotImplementedError
300        return self._module.is_submodule(J._module)
301
302    def _intersect(self, J):
303        if not isinstance(J, ModuleImplementedIdeal):
304            raise NotImplementedError
305        return self.__class__(self.ring, self._module.intersect(J._module))
306
307    def _quotient(self, J, **opts):
308        if not isinstance(J, ModuleImplementedIdeal):
309            raise NotImplementedError
310        return self._module.module_quotient(J._module, **opts)
311
312    def _union(self, J):
313        if not isinstance(J, ModuleImplementedIdeal):
314            raise NotImplementedError
315        return self.__class__(self.ring, self._module.union(J._module))
316
317    @property
318    def gens(self):
319        """
320        Return generators for ``self``.
321
322        Examples
323        ========
324
325        >>> from sympy import QQ
326        >>> from sympy.abc import x, y
327        >>> list(QQ.old_poly_ring(x, y).ideal(x, y, x**2 + y).gens)
328        [x, y, x**2 + y]
329        """
330        return (x[0] for x in self._module.gens)
331
332    def is_zero(self):
333        """
334        Return True if ``self`` is the zero ideal.
335
336        Examples
337        ========
338
339        >>> from sympy.abc import x
340        >>> from sympy import QQ
341        >>> QQ.old_poly_ring(x).ideal(x).is_zero()
342        False
343        >>> QQ.old_poly_ring(x).ideal().is_zero()
344        True
345        """
346        return self._module.is_zero()
347
348    def is_whole_ring(self):
349        """
350        Return True if ``self`` is the whole ring, i.e. one generator is a unit.
351
352        Examples
353        ========
354
355        >>> from sympy.abc import x
356        >>> from sympy import QQ, ilex
357        >>> QQ.old_poly_ring(x).ideal(x).is_whole_ring()
358        False
359        >>> QQ.old_poly_ring(x).ideal(3).is_whole_ring()
360        True
361        >>> QQ.old_poly_ring(x, order=ilex).ideal(2 + x).is_whole_ring()
362        True
363        """
364        return self._module.is_full_module()
365
366    def __repr__(self):
367        from sympy import sstr
368        return '<' + ','.join(sstr(x) for [x] in self._module.gens) + '>'
369
370    # NOTE this is the only method using the fact that the module is a SubModule
371    def _product(self, J):
372        if not isinstance(J, ModuleImplementedIdeal):
373            raise NotImplementedError
374        return self.__class__(self.ring, self._module.submodule(
375            *[[x*y] for [x] in self._module.gens for [y] in J._module.gens]))
376
377    def in_terms_of_generators(self, e):
378        """
379        Express ``e`` in terms of the generators of ``self``.
380
381        Examples
382        ========
383
384        >>> from sympy.abc import x
385        >>> from sympy import QQ
386        >>> I = QQ.old_poly_ring(x).ideal(x**2 + 1, x)
387        >>> I.in_terms_of_generators(1)
388        [1, -x]
389        """
390        return self._module.in_terms_of_generators([e])
391
392    def reduce_element(self, x, **options):
393        return self._module.reduce_element([x], **options)[0]
394