Ask Your Question
2

comparison of ideals

asked 2011-01-19 22:37:05 +0100

niceq gravatar image

What does the output mean when you type A<=B where A and B are ideals in a polynomial ring?

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted
3

answered 2011-01-19 23:34:30 +0100

DSM gravatar image

To find out, you can look in the __cmp__ special method of the object you're interested in. This function returns negative if x<y, zero if x==y, and positive if x>y. Looking in __cmp__ interactively is probably a better idea than browsing the source, because if you do that you may guess wrong about which __cmp__ is being used (like I did!).

For example:

sage: P.<x> = PolynomialRing(QQ)
sage: I = Ideal([x^2-2*x+1, x^2-1])
sage: J = Ideal([4 + 3*x + x^2, 1 + x^2])
sage: I.__cmp__??
Type:       instancemethod
Base Class: <type 'instancemethod'>
String Form:    <bound method Ideal_1poly_field.__cmp__ of Principal ideal (x - 1) of Univariate Polynomial Ring in x over Rational Field>
Namespace:  Interactive
File:       /Applications/sage/local/lib/python2.6/site-packages/sage/rings/ideal.py
Definition: I.__cmp__(self, other) 
Source:
    def __cmp__(self, other):
        if not isinstance(other, Ideal_generic):
            other = self.ring().ideal(other)

    if not other.is_principal():
        return -1

    if self.is_zero():
        if not other.is_zero():
            return -1
        return 0

    # is other.gen() / self.gen() a unit in the base ring?
    g0 = other.gen()
    g1 = self.gen()
    if g0.divides(g1) and g1.divides(g0):
        return 0
    return 1
sage: I.gen(), J.gen()
(x - 1, 1)
sage: I == J, I <= J, I >= J
(False, False, True)

sage: # or exactly the same case but now (potentially) multivariate
sage: P.<x,y> = PolynomialRing(QQ,2)
sage: I = Ideal([x^2-2*x+1, x^2-1])
sage: J = Ideal([4 + 3*x + x^2, 1 + x^2])
sage: I.__cmp__??
[docstring removed]
    # first check the type
    if not isinstance(other, MPolynomialIdeal):
        return 1

    # the ideals may be defined w.r.t. to different term orders
    # but are still the same.
    R = self.ring()
    S = other.ring()
    if R is not S: # rings are unique
        if type(R) == type(S) and (R.base_ring() == S.base_ring()) and (R.ngens() == S.ngens()):
            other = other.change_ring(R)
        else:
            return cmp((type(R), R.base_ring(), R.ngens()), (type(S), S.base_ring(), S.ngens()))

    # now, check whether the GBs are cached already
    if self.groebner_basis.is_in_cache() and other.groebner_basis.is_in_cache():
        l = self.groebner_basis()
        r = other.groebner_basis()
    else: # use easy GB otherwise
        try:
            l = self.change_ring(R.change_ring(order="degrevlex")).groebner_basis()
            r = other.change_ring(R.change_ring(order="degrevlex")).groebner_basis()
        except AttributeError: # e.g. quotient rings
            l = self.groebner_basis()
            r = other.groebner_basis()
    return cmp(l,r)

sage: I.groebner_basis(), J.groebner_basis()
([x - 1], [1])

sage: I == J, I <= J, I >= J (False, False, True)

So it seems (modulo some details) it's basically comparing the Sequences of the groebner bases, and that appears to fall through to simply sorting the underlying lists of polynomials. I don't know how useful that is, but that looks like what it's doing.

edit flag offensive delete link more

Comments

Oh no, that does not seem useful. Thank you for your response. Now I am doubting that A==B being True even means that the ideals are equal, which I was assuming. Does sage have built in functions for ideal equality and ideal containment? I would like to have a function like equality(A,B) and containment(A,B) whose value being true means A=B as ideal and A is contained in B, respectively? Does such a function exist? I know I can compute reduced Grob bases of both ideals and visually check if they are the same but I would like have a sage function that will check that for me.

niceq gravatar imageniceq ( 2011-01-20 00:17:45 +0100 )edit

IIUC the above logic should get equality right, so if that's all you need you're set. (It'd be a bug if it doesn't!) I'm a little rusty, but I gather you'd like A <= B iff all the terms in the generators of A (or the fewer but more expensive to compute terms in the groebner basis) are contained in B? If so, would something like def containment(A, B): return all(gen in B for gen in A.gens()) or def containment(A, B): return all(gb in B for gb in A.groebner_basis()) work?

DSM gravatar imageDSM ( 2011-01-20 01:32:07 +0100 )edit

Yes, that is right. I just need a function that checks if all the generators of A are contained in the ideal B. Easy enough, and I think your costom function does work but I am wondering if there is a predefined sage function(command) that does this or if I have to define one.

niceq gravatar imageniceq ( 2011-01-20 01:46:38 +0100 )edit

Every time I say that there isn't a predefined function to do something it turns out there is one in an obvious location and I just didn't see it, so to prevent embarrassment I won't say there's not. :^) But I didn't find it on a cursory scan.

DSM gravatar imageDSM ( 2011-01-20 02:24:28 +0100 )edit

I understand. Thanks for looking though. You probably wont like the other question I just posted then. I prefer to use built in functions rather that make them myself.

niceq gravatar imageniceq ( 2011-01-20 02:41:30 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2011-01-19 22:37:05 +0100

Seen: 1,543 times

Last updated: Jan 19 '11