Generic quotient yields wrong comparison

[mjungmath]

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

CC: @trevorkarn @tscrim @mkoeppe @jhpalmieri

Component: algebra

Branch/Commit: public/rings/turn_reduce_of_generic_ideals_into_abstract_method_32291 @ fb19506

Issue created by migration from https://trac.sagemath.org/ticket/32291

[trevorkarn]

Commit: fb19506

[trevorkarn]

comment:1

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

---

New commits:

fb19506

Initial commit

[trevorkarn]

Branch: public/rings/turn_reduce_of_generic_ideals_into_abstract_method_32291

[mjungmath]

comment:2

1. I would propose to modify the method in Ideal_generic instead of adding a new one to noncommutative_ideals.

2. Sage provides a decorator for abstract methods.

3. The error message is imo slightly misleading in the sense that reduction can be supported in general, but must be individually implemented when subclassed.

[tscrim]

comment:3

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.

[mjungmath]

comment:4

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

[mjungmath]

comment:6

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.

[mjungmath]

comment:7

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

[mjungmath]

comment:8

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

[mjungmath]

comment:9

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.

[trevorkarn]

comment:10

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.

[mjungmath]

comment:11

Replying to @trevorkarn:

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.

[tscrim]

comment:12

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:

• https://www.math.auckland.ac.nz/~slinko/Supervision/DominicSearlesMastersThesis.pdf
• https://link.springer.com/article/10.1007/BF00244487

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.