Opened 16 months ago

Last modified 3 months ago

#32291 new defect

Generic quotient yields wrong comparison

Reported by: Michael Jung Owned by:
Priority: major Milestone: sage-9.8
Component: algebra Keywords:
Cc: Trevor Karn, Travis Scrimshaw, Matthias Köppe, John Palmieri Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: public/rings/turn_reduce_of_generic_ideals_into_abstract_method_32291 (Commits, GitHub, GitLab) Commit: fb1950673a5dbe5d13c530dfb0873a0e52e7f38a
Dependencies: Stopgaps:

Status badges

Description (last modified by Michael Jung)

As reported in https://ask.sagemath.org/question/56243/quotients-of-exterior-algebras/, we currently have the following behavior for generic ideals and quotients:

sage: E.<x,y,z> = algebras.Exterior(QQ);
sage: I = E.ideal(x-y);
sage: Q = E.quo(I);
sage: xbar,ybar,zbar = Q.gens();
sage: xbar == ybar
False

Tracing that back, the comparison in quotient_ring_element is given by:

def _richcmp_(self, other, op):
    r"""
    ...
    """
    if self.__rep == other.__rep: # Use a shortpath, so that we
                                  # avoid expensive reductions
        return rich_to_bool(op, 0)
    I = self.parent().defining_ideal()
    return richcmp(I.reduce(self.__rep), I.reduce(other.__rep), op)

Taking a look at reduce of sage.rings.ideal.Ideal_generic, it gets clear why the comparison fails:

    def reduce(self, f):
        r"""
        Return the reduction of the element of `f` modulo ``self``.

        This is an element of `R` that is equivalent modulo `I` to `f` where
        `I` is ``self``.

        EXAMPLES::

            sage: ZZ.ideal(5).reduce(17)
            2
            sage: parent(ZZ.ideal(5).reduce(17))
            Integer Ring
        """
        return f       # default

Change History (17)

comment:1 Changed 16 months ago by Trevor Karn

Branch: public/rings/turn_reduce_of_generic_ideals_into_abstract_method_32291
Commit: fb1950673a5dbe5d13c530dfb0873a0e52e7f38a

There is still something not quite right about what I pushed, but it is a start.


New commits:

fb19506Initial commit

comment:2 Changed 16 months ago by Michael Jung

  1. I would propose to modify the method in Ideal_generic instead of adding a new one to noncommutative_ideals.
  1. Sage provides a decorator for abstract methods.
  1. The error message is imo slightly misleading in the sense that reduction can be supported in general, but must be individually implemented when subclassed.
Last edited 16 months ago by Michael Jung (previous) (diff)

comment:3 Changed 16 months ago by Travis Scrimshaw

I am a firm -1 on this because the reduce() method is just saying, "Give me a representative of p in the ideal I." So there is nothing mathematically wrong with this. Yes, it is less than ideal because we want it to be "minimal" but that is not strictly required.

comment:4 Changed 16 months ago by Michael Jung

That makes sense. However, we should at least document that the usage of generic ideals leads to unexpected results in quotient rings (see e.g. https://ask.sagemath.org/question/56243/quotients-of-exterior-algebras/).

Last edited 16 months ago by Michael Jung (previous) (diff)

comment:5 Changed 16 months ago by Michael Jung

Cc: Matthias Köppe added
Description: modified (diff)
Summary: Turn reduce of generic ideals into abstract methodGeneric quotient yields wrong comparison

comment:6 Changed 16 months ago by Michael Jung

Description: modified (diff)

It looks like the perturbator is rather _richcmp_ in rings.quotient_ring_element.QuotientRingElement comparing two elements on the level of the ring, and not of the quotient.

Long story short, the implementation of _richcmp_ in fact assumes that reduce returns the "minimal" reduction.

Last edited 16 months ago by Michael Jung (previous) (diff)

comment:7 Changed 16 months ago by Michael Jung

I would propose to boil the comparison in case of equality down to the check bool(self-other) instead. What do you think?

comment:8 Changed 16 months ago by Michael Jung

Type: enhancementdefect

Should we also remove _richcmp_ completely? I have the feeling this code returns nonsense most times.

comment:9 Changed 16 months ago by Michael Jung

ASSUMPTION:

I has a method I.reduce(x) returning the normal form of elements x∈R. In other words, it is required that I.reduce(x)==I.reduce(y) ⟺x−y∈I, and x-I.reduce(x) in I, for all x,y∈R.

This is an extract of https://doc.sagemath.org/html/en/reference/rings/sage/rings/quotient_ring.html#sage.rings.quotient_ring.QuotientRing. That means, the reduce function of an ideal is usually expected to return the normal form. This is currently not given.

comment:10 Changed 16 months ago by Trevor Karn

I'm now slightly confused. The example given in your sage-devel post is now working for me in the GCA case.

sage: A.<x,y,z> = GradedCommutativeAlgebra(QQ,degrees=(1,2,3))                                                                                                                                              
sage: I = A.ideal(x*y-z)                                                                                                                                                                                    
sage: J = A.ideal(x^2)                                                                                                                                                                                      
sage: Q1 = A.quotient(I)                                                                                                                                                                                    
sage: Q2 = A.quotient(J)                                                                                                                                                                                    
sage: Q1.gens()[0]*Q1.gens()[1] # x*y                                                                                                                                                                       
z
sage: Q2.gens()[0]^2 # x^2                                                                                                                                                                               
0
sage: Q2.gens()[0]^2 == 0  
True

I am running sage 9.4.beta5 so I'm not sure if it is fixed there or what is going on. On the other hand, the exterior algebra still has the same behavior as in the description.

comment:11 in reply to:  10 Changed 16 months ago by Michael Jung

Replying to tkarn:

I'm now slightly confused. The example given in your sage-devel post is now working for me in the GCA case.

sage: A.<x,y,z> = GradedCommutativeAlgebra(QQ,degrees=(1,2,3))                                                                                                                                              
sage: I = A.ideal(x*y-z)                                                                                                                                                                                    
sage: J = A.ideal(x^2)                                                                                                                                                                                      
sage: Q1 = A.quotient(I)                                                                                                                                                                                    
sage: Q2 = A.quotient(J)                                                                                                                                                                                    
sage: Q1.gens()[0]*Q1.gens()[1] # x*y                                                                                                                                                                       
z
sage: Q2.gens()[0]^2 # x^2                                                                                                                                                                               
0
sage: Q2.gens()[0]^2 == 0  
True

I am running sage 9.4.beta5 so I'm not sure if it is fixed there or what is going on. On the other hand, the exterior algebra still has the same behavior as in the description.

I was using my implementation in #32272. The class GCAlgebra uses a non-generic quotient.

comment:12 Changed 16 months ago by Travis Scrimshaw

We should not remove _richcmp_ either. Equality check is generally not mathematical equality. Unfortunately Python does not allow == (and similar) to return a Unknown, which would technically be the way out (yet knowing when to it is unknown or not is a hard problem too). Note that is an assumption that is not generically satisfied, so you should not expect the quotient ring to fully behave correctly. Rather than spending time trying to block users in cases when we haven't implemented (or don't have general answers) that will potentially break code in the wild, we should spend time implementing the cases we do know.

For example, the exterior algebra can use:

In some sense, all you need to do is linear algebra since the exterior algebra is finite dimensional. Compute a basis for the ideal as a subspace (again, finite dimensional), and then take the quotient as vector spaces. Of course, this is not likely to be fast, but it works with very minimal code needed to be added/changed.

Note that in the second paper, the exterior polynomial algebra is the ungraded version of a graded commutative algebra. So that gives a Gröbner basis algorithm in that case if we also rewrite the GCA code with a more basic implementation.

comment:13 Changed 16 months ago by Michael Jung

Cc: John Palmieri added

comment:14 Changed 16 months ago by Matthias Köppe

Milestone: sage-9.4sage-9.5

comment:15 Changed 12 months ago by Matthias Köppe

Milestone: sage-9.5sage-9.6

comment:16 Changed 7 months ago by Matthias Köppe

Milestone: sage-9.6sage-9.7

comment:17 Changed 3 months ago by Matthias Köppe

Milestone: sage-9.7sage-9.8
Note: See TracTickets for help on using tickets.