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: |
Description (last modified by )
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
Branch: | → public/rings/turn_reduce_of_generic_ideals_into_abstract_method_32291 |
---|---|
Commit: | → fb1950673a5dbe5d13c530dfb0873a0e52e7f38a |
comment:2 Changed 16 months ago by
- I would propose to modify the method in
Ideal_generic
instead of adding a new one tononcommutative_ideals
.
- Sage provides a decorator for abstract methods.
- The error message is imo slightly misleading in the sense that reduction can be supported in general, but must be individually implemented when subclassed.
comment:3 Changed 16 months ago by
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
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/).
comment:5 Changed 16 months ago by
Cc: | Matthias Köppe added |
---|---|
Description: | modified (diff) |
Summary: | Turn reduce of generic ideals into abstract method → Generic quotient yields wrong comparison |
comment:6 Changed 16 months ago by
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.
comment:7 Changed 16 months ago by
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
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
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
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 Changed 16 months ago by
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 TrueI 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
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.
comment:13 Changed 16 months ago by
Cc: | John Palmieri added |
---|
comment:14 Changed 16 months ago by
Milestone: | sage-9.4 → sage-9.5 |
---|
comment:15 Changed 12 months ago by
Milestone: | sage-9.5 → sage-9.6 |
---|
comment:16 Changed 7 months ago by
Milestone: | sage-9.6 → sage-9.7 |
---|
comment:17 Changed 3 months ago by
Milestone: | sage-9.7 → sage-9.8 |
---|
There is still something not quite right about what I pushed, but it is a start.
New commits:
Initial commit