Opened 16 months ago

# Generic quotient yields wrong comparison

Reported by: Owned by: Michael Jung major sage-9.8 algebra Trevor Karn, Travis Scrimshaw, Matthias Köppe, John Palmieri N/A public/rings/turn_reduce_of_generic_ideals_into_abstract_method_32291 fb1950673a5dbe5d13c530dfb0873a0e52e7f38a

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
```

### comment:1 Changed 16 months ago by Trevor Karn

Branch: → public/rings/turn_reduce_of_generic_ideals_into_abstract_method_32291 → fb1950673a5dbe5d13c530dfb0873a0e52e7f38a

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

New commits:

 ​fb19506 `Initial 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 modified (diff) Turn reduce of generic ideals into abstract method → Generic 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: enhancement → defect

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 follow-up:  11 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

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:14 Changed 16 months ago by Matthias Köppe

Milestone: sage-9.4 → sage-9.5

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

Milestone: sage-9.5 → sage-9.6

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

Milestone: sage-9.6 → sage-9.7

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

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