Opened 10 years ago

Test if the assumptions made by quotient rings are fulfilled

Reported by: Owned by: tfeulner AlexGhitza major sage-6.4 algebra mstreng, slelievre Thomas Feulner Ralf Stephan N/A #13347 todo

In the definition of a QuotientRing there is the following assumption

ASSUMPTION:

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


On the other hand, the default definition of reduce in sage/rings/ideal.py says

    def reduce(self, f):
return f       # default


As a consequence one gets

sage: Z4x.<x> = Integers(4)[]
sage: GR.<y> = Z4x.quotient_ring(x**2+x+1)
sage: R = GR.quo(GR.ideal(2))
sage: R(y+2) == R(y)
False


This patch adds a deprecation warning in reduce(). It also introduces a test in QuotientRing_nc.__init__(), which determines if the ideal class overwrites the definition of reduce().

comment:1 Changed 10 years ago by tfeulner

I know that there are more doctest failures but maybe someone could first tell me if my approach is correct.

comment:2 follow-up: ↓ 3 Changed 10 years ago by sluther

Does this patch lead to test failures?

If yes, are the tests wrong or did they pass only by accident in the past?

I don't know the involved math, but it sounds to me like sage currently returns wrong answers. If this is the case, the bug should be fixed and not deprecated. This means: a) use NotImplementedError right away and b) reimplement reduce() where necessary.

Last edited 2 years ago by slelievre (previous) (diff)

comment:3 in reply to: ↑ 2 ; follow-up: ↓ 4 Changed 10 years ago by tfeulner

Does this patch lead to test failures?

I was talking about the failures where I did not catch the deprecation warning. I will start this work as soon as there is a decision if there should be some deprecation warning or a NotImplementedError? at those places.

I don't know the involved math, but it sounds to me like sage currently returns wrong answers. If this is the case, the bug should be fixed and not deprecated. This means: a) use NotImplementedError? right away and b) reimplement reduce() where necessary.

This is definitely a bug. I am not sure if I will be able to reimplement all occurrences of reduce.

comment:4 in reply to: ↑ 3 Changed 10 years ago by sluther

This is definitely a bug. I am not sure if I will be able to reimplement all occurrences of reduce.

Then start new tickets as needed and make them block this one.

comment:5 follow-up: ↓ 6 Changed 10 years ago by mstreng

Judging just from reading the patch, I think you make the assumption very clear :)

I don't have any experience with deprecation, but what you're doing to sage/rings/ideal.py looks fine to me.

About the DeprecationWarning you are adding to sage/rings/quotient_ring.py:

1) Any existing Sage doctest where your patch gives this warning is very likely a Sage bug. Thanks for finding them, you can list them in a separate ticket.

2) For your final patch, please remove this test and this warning. There is not much added benefit of this warning (you get an indirect warning from reduce when you use the quotient ring anyway), and it tests something different from what it claims to check (reduce being implemented is not equivalent to the assumption being satisfied, so lots of potential false positives and false negatives), while it also forces people to do extra work later (when the deprecated function "reduce" is changed to NotImplementedError). Also, you are not deprecating any functionality at this location in the source code.

comment:6 in reply to: ↑ 5 Changed 10 years ago by tfeulner

• Dependencies set to 13347

I removed the DeprecationWarning from sage/rings/quotient_ring.py as you proposed and started a new ticket, see ticket:13347.

I suppose that the documentation of mod() in sage/structure/element.pyx should also be modified:

Return a unique representative for self modulo the ideal I (or the ideal generated by the elements of I if I is not an ideal.) I.e. it is required that x.mod(I) == y.mod(I) \iff x-y \in I, and x-x.mod(I) in I, for all x,y\in R.

comment:7 Changed 10 years ago by tfeulner

• Status changed from new to needs_review

comment:8 Changed 9 years ago by saraedum

• Dependencies changed from 13347 to #13347
• Description modified (diff)

comment:9 Changed 9 years ago by jdemeyer

• Milestone changed from sage-5.11 to sage-5.12

comment:10 Changed 9 years ago by vbraun_spam

• Milestone changed from sage-6.1 to sage-6.2

comment:11 Changed 8 years ago by rws

The changes themselves look reasonable. The patch rebases with some fuzz 2 only on 6.2.base5. The links to the ticket in the docs should be given as :trac:13345 Note also the proposed document change in comment:5 could be added. If you please make these changes (rebase, trac links, doc fix) then you can set positive review yourself, so that you need not wait for another round of review.

comment:12 Changed 8 years ago by rws

• Reviewers set to Ralf Stephan

comment:13 Changed 8 years ago by vbraun_spam

• Milestone changed from sage-6.2 to sage-6.3

comment:14 Changed 8 years ago by malb

• Status changed from needs_review to needs_work

comment:15 Changed 8 years ago by vbraun_spam

• Milestone changed from sage-6.3 to sage-6.4

comment:16 Changed 7 years ago by jakobkroeker

• Stopgaps set to todo

comment:17 Changed 7 years ago by saraedum

Should we not simply remove the default implementation of reduce? It is wrong for anything but the zero ideal, right? At least we should add a stopgap I guess?

comment:18 Changed 7 years ago by saraedum

• Status changed from needs_work to needs_info