# source:sage/rings/ideal.py@6646:204e55045453

Revision 6646:204e55045453, 13.7 KB checked in by William Stein <wstein@…>, 6 years ago (diff)

Fix some doctest failures.

Line
1r"""
2Ideals
3
4SAGE provides functionality for computing with ideals.  One can create
5an ideal in any commutative ring $R$ by giving a list of generators,
6using the notation \code{R.ideal([a,b,...])}.
7"""
8
9#*****************************************************************************
10#       Copyright (C) 2005 William Stein <wstein@gmail.com>
11#
13#
14#    This code is distributed in the hope that it will be useful,
15#    but WITHOUT ANY WARRANTY; without even the implied warranty of
16#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
17#    General Public License for more details.
18#
19#  The full text of the GPL is available at:
20#
22#*****************************************************************************
23
24import sage.misc.latex as latex
25import sage.rings.ring
26import sage.rings.principal_ideal_domain
27import commutative_ring
28from sage.structure.sage_object import SageObject
29from sage.structure.element import MonoidElement
30from sage.interfaces.singular import singular as singular_default, is_SingularElement
31import sage.rings.infinity
32from sage.structure.sequence import Sequence
33
34def Ideal(R, gens=[], coerce=True):
35    r"""
36    Create the ideal in ring with given generators.
37
38    There are some shorthand notations for creating an ideal, in addition
39    to use the Ideal function:
40    \begin{verbatim}
41        --  R.ideal(gens, coerce=True)
42        --  gens*R
43        --  R*gens
44    \end{verbatim}
45
46    INPUT:
47        R -- a ring
48        gens -- list of elements
49        coerce -- bool (default: True); whether gens need to be coerced into ring.
50
51    Alternatively, one can also call this function with the syntax
52         Ideal(gens)
53    where gens is a nonempty list of generators or a single generator.
54
55    OUTPUT:
56        The ideal of ring generated by gens.
57
58    EXAMPLES:
59        sage: R, x = PolynomialRing(ZZ, 'x').objgen()
60        sage: I = R.ideal([4 + 3*x + x^2, 1 + x^2])
61        sage: I
62        Ideal (x^2 + 3*x + 4, x^2 + 1) of Univariate Polynomial Ring in x over Integer Ring
63        sage: Ideal(R, [4 + 3*x + x^2, 1 + x^2])
64        Ideal (x^2 + 3*x + 4, x^2 + 1) of Univariate Polynomial Ring in x over Integer Ring
65        sage: Ideal((4 + 3*x + x^2, 1 + x^2))
66        Ideal (x^2 + 3*x + 4, x^2 + 1) of Univariate Polynomial Ring in x over Integer Ring
67
68        sage: ideal(x^2-2*x+1, x^2-1)
69        Ideal (x^2 - 1, x^2 - 2*x + 1) of Univariate Polynomial Ring in x over Integer Ring
70        sage: ideal([x^2-2*x+1, x^2-1])
71        Ideal (x^2 - 1, x^2 - 2*x + 1) of Univariate Polynomial Ring in x over Integer Ring
72
73
74    This example illustrates how SAGE finds a common ambient ring for the ideal, even though
75    1 is in the integers (in this case).
76        sage: R.<t> = ZZ['t']
77        sage: i = ideal(1,t,t^2)
78        sage: i
79        Ideal (t, 1, t^2) of Univariate Polynomial Ring in t over Integer Ring
80        sage: ideal(1/2,t,t^2)
81        Principal ideal (1) of Univariate Polynomial Ring in t over Rational Field
82
83    TESTS:
84        sage: R, x = PolynomialRing(ZZ, 'x').objgen()
85        sage: I = R.ideal([4 + 3*x + x^2, 1 + x^2])
87        True
88
89        sage: I = Ideal(R, [4 + 3*x + x^2, 1 + x^2])
91        True
92
93        sage: I = Ideal((4 + 3*x + x^2, 1 + x^2))
95        True
96
97    """
98    if isinstance(R, Ideal_generic):
99        return Ideal(R.ring(), R.gens())
100
101    if isinstance(R, (list, tuple)) and len(R) > 0:
102        R = Sequence(R)
103        if not isinstance(R.universe(), sage.rings.ring.Ring):
104            raise TypeError, "unable to find common ring into which all ideal generators map"
105        return R[0].parent().ideal(R)
106
107    if not isinstance(R, sage.rings.ring.Ring):
108        try:
109            S = R.parent()
110        except AttributeError:
111            raise TypeError, "ring must be a ring, list, or element."
112        if isinstance(S, sage.rings.ring.Ring):
113            return Ideal(S, [R])
114        else:
115            raise TypeError, "ring must be a ring, list, or element."
116
117    if not commutative_ring.is_CommutativeRing(R):
118        raise TypeError, "R must be a commutative ring"
119
120    if isinstance(gens, Ideal_generic):
121        gens = gens.gens()
122
123    if not isinstance(gens, (list, tuple)):
124        gens = [R(gens)]
125        coerce = False
126
127    elif len(gens) == 0:
128        gens = [R(0)]
129        coerce = False
130
131    if coerce:
132        gens = [R(g) for g in gens]
133
134    gens = list(set(gens))
135    if isinstance(R, sage.rings.principal_ideal_domain.PrincipalIdealDomain):
136        # Use GCD algorithm to obtain a principal ideal
137        g = gens[0]
138        for h in gens[1:]:
139            g = R.gcd(g, h)
140        return Ideal_pid(R, g)
141
142    if len(gens) == 1:
143        return Ideal_principal(R, gens[0])
144
145    return Ideal_generic(R, gens, coerce=False)
146
147def is_Ideal(x):
148    return isinstance(x, Ideal_generic)
149
150
151class Ideal_generic(MonoidElement):
152    """
153    An ideal.
154    """
155    def __init__(self, ring, gens, coerce=True):
156        self.__ring = ring
157        if not isinstance(gens, (list, tuple)):
158            gens = [gens]
159        if coerce:
160            gens = [ring(x) for x in gens]
161
162        self.__gens = tuple(gens)
163        MonoidElement.__init__(self, ring.ideal_monoid())
164
165    def _repr_short(self):
166        return '(%s)'%(', '.join([str(x) for x in self.gens()]))
167
168    def __repr__(self):
169        return "Ideal %s of %s"%(self._repr_short(), self.ring())
170
171    def __cmp__(self, other):
172        S = set(self.gens())
173        T = set(other.gens())
174        if S == T:
175            return 0
176        return cmp(self.gens(), other.gens())
177
178    def __contains__(self, x):
179        try:
180            return self._contains_(self.__ring(x))
181        except TypeError:
182            return False
183
184    def _contains_(self, x):
185        # check if x, which is assumed to be in the ambient ring, is actually in this ideal.
186        raise NotImplementedError
187
188    def __nonzero__(self):
189        return self.gens() != [self.ring()(0)]
190
191    def base_ring(self):
192        return self.ring().base_ring()
193
194    def _latex_(self):
195        return '\\left(%s\\right)%s'%(", ".join([latex.latex(g) for g in \
196                                                 self.gens()]),
197                                      latex.latex(self.ring()))
198
199    def ring(self):
200        """
201        Return the ring in which this ideal is contained.
202        """
203        return self.__ring
204
205    def reduce(self, f):
206        r"""
207        Return the reduction the element of $f$ modulo the ideal $I$
208        (=self).  This is an element of $R$ that is equivalent modulo
209        $I$ to $f$.
210
211        EXAMPLES:
212            sage: ZZ.ideal(5).reduce(17)
213            2
214            sage: parent(ZZ.ideal(5).reduce(17))
215            Integer Ring
216        """
217        return f       # default
218
219    def gens(self):
220        """
221        Return a set of generators / a basis of self. This is usually
222        the set of generators provided during object creation.
223
224        EXAMPLE:
225            sage: P.<x,y> = PolynomialRing(QQ,2)
226            sage: I = Ideal([x,y+1]); I
227            Ideal (x, y + 1) of Multivariate Polynomial Ring in x, y over Rational Field
228            sage: I.gens()
229            (x, y + 1)
230
231            sage: ZZ.ideal(5,10).gens()
232            (5,)
233        """
234        return self.__gens
235
236    def gens_reduced(self):
237        r"""
238        Same as gens() for this ideal, since there is currently no
239        special gens_reduced algorithm implemented for this ring.
240
241        This method is provided so that ideals in ZZ have the method
242        gens_reduced(), just like ideals of number fields.
243
244        EXAMPLES:
245            sage: ZZ.ideal(5).gens_reduced()
246            (5,)
247        """
248        return self.gens()
249
250    def is_maximal(self):
251        raise NotImplementedError
252
253    def is_prime(self):
254        raise NotImplementedError
255
256    def is_principal(self):
257        if len(self.gens()) <= 1:
258            return True
259        raise NotImplementedError
260
261    def is_trivial(self):
262        if self.is_zero():
263            return True
264        elif self.is_principal():
265            return self.gen().is_unit()
266        raise NotImplementedError
267
268    def category(self):
269        """
270        Return the category of this ideal.
271
272
273        """
274        import sage.categories.all
275        return sage.categories.all.Ideals(self.__ring)
276
278        if not isinstance(other, Ideal_generic):
279            other = self.ring().ideal(other)
280        return self.ring().ideal(self.gens() + other.gens())
281
283        if not isinstance(other, Ideal_generic):
284            other = self.ring().ideal(other)
285        return self.ring().ideal(self.gens() + other.gens())
286
287    def __mul__(self, other):
288        if not isinstance(other, Ideal_generic):
289            other = self.ring().ideal(other)
290        return self.ring().ideal([x*y for x in self.gens() for y in other.gens()])
291
292    def __rmul__(self, other):
293        if not isinstance(other, Ideal_generic):
294            other = self.ring().ideal(other)
295        return self.ring().ideal([y*x for x in self.gens() for y in other.gens()])
296
297
298class Ideal_principal(Ideal_generic):
299    """
300    A principal ideal.
301    """
302    def __init__(self, ring, gen):
303        Ideal_generic.__init__(self, ring, [gen])
304
305    def __repr__(self):
306        return "Principal ideal (%s) of %s"%(self.gen(), self.ring())
307
308    def is_principal(self):
309        return True
310
311    def gen(self):
312        return self.gens()[0]
313
314    def __contains__(self, x):
315        if self.gen().is_zero():
316            return x.is_zero()
317        return self.gen().divides(x)
318
319    def __cmp__(self, other):
320        if not isinstance(other, Ideal_generic):
321            other = self.ring().ideal(other)
322
323        if not other.is_principal():
324            return -1
325
326        if self.is_zero():
327            if not other.is_zero():
328                return -1
329            return 0
330
331        # is other.gen() / self.gen() a unit in the base ring?
332        g0 = other.gen()
333        g1 = self.gen()
334        if g0.divides(g1) and g1.divides(g0):
335            return 0
336        return 1
337
338    def divides(self, other):
339        """
340        Returns True if self divides other.
341        """
342        if isinstance(other, Ideal_principal):
343            return self.gen().divides(other.gen())
344        raise NotImplementedError
345
346class Ideal_pid(Ideal_principal):
347    """
348    An ideal of a principal ideal domain.
349    """
350    def __init__(self, ring, gen):
351        Ideal_principal.__init__(self, ring, gen)
352
354        if not isinstance(other, Ideal_generic):
355            other = self.ring().ideal(other)
356        return self.ring().ideal(self.gcd(other))
357
358    def reduce(self, f):
359        """
360        Return the reduction of f modulo self.
361
362        EXAMPLES:
363            sage: I = 8*ZZ
364            sage: I.reduce(10)
365            2
366            sage: n = 10; n.mod(I)
367            2
368        """
369        f = self.ring()(f)
370        if self.gen() == 0:
371            return f
372        q, r = f.quo_rem(self.gen())
373        return r
374
375    def gcd(self, other):
376        if isinstance(other, Ideal_principal):
377            return self.ring().ideal(self.gen().gcd(other.gen()))
378        elif self.gen() in other:
379            return other
380        else:
381            raise NotImplementedError
382
383class Ideal_fractional(Ideal_generic):
384    def __init__(self, ring, gen):
385        Ideal_generic.__init__(self, ring, [gen])
386    def __repr__(self):
387        return "Fractional ideal %s of %s"%(self._repr_short(), self.ring())
388
389
390
391# constructors for standard (benchmark) ideals, written uppercase as
392# these are constructors
393
394def Cyclic(R, n=None, homog=False, singular=singular_default):
395    """
396    ideal of cyclic n-roots from 1-st n variables of R if R is
397    coercable to Singular. If n==None n is set to R.ngens()
398
399    INPUT:
400        R -- base ring to construct ideal for
401        n -- number of cyclic roots (default: None)
402        homog -- if True a homogenous ideal is returned using the last
403                 variable in the ideal (default: False)
404        singular -- singular instance to use
405
406    \note{R will be set as the active ring in Singular}
407    """
408    if n:
409        if n > R.ngens():
410            raise ArithmeticError, "n must be <= R.ngens()"
411    else:
412        n = R.ngens()
413
414    singular.lib("poly")
415    R._singular_().set_ring()
416    if not homog:
417        I = singular.cyclic(n)
418    else:
419        I = singular.cyclic(n).homog(R.gen(n-1))
420    return R.ideal(I)
421
422
423def Katsura(R, n=None, homog=False, singular=singular_default):
424    """
425    n-th katsura ideal of R if R is coercable to Singular.  If n==None
426    n is set to R.ngens()
427
428    INPUT:
429        R -- base ring to construct ideal for
430        n -- which katsura ideal of R
431        homog -- if True a homogenous ideal is returned using the last
432                 variable in the ideal (default: False)
433        singular -- singular instance to use
434    """
435    if n:
436        if n > R.ngens():
437            raise ArithmeticError, "n must be <= R.ngens()"
438    else:
439        n = R.ngens()
440    singular.lib("poly")
441    R._singular_().set_ring()
442    if not homog:
443        I = singular.katsura(n)
444    else:
445        I = singular.katsura(n).homog(R.gen(n-1))
446    return R.ideal(I)
447
448def FieldIdeal(R):
449    """
450    Let q = R.base_ring().order() and (x0,...,x_n) = R.gens() then if
451    q is finite this constructor returns
452
453    $\langle x_0^q - x_0, \dots , x_n^q - x_n \rangle.$
454
455    We call this ideal the field ideal and the generators the field
456    equations.
457    """
458
459    q = R.base_ring().order()
460
461    if q is sage.rings.infinity.infinity:
462        raise TypeError, "Cannot construct field ideal for R.base_ring().order()==infinity"
463
464    return R.ideal([x**q - x for x in R.gens() ])
Note: See TracBrowser for help on using the repository browser.