Opened 8 years ago

Last modified 4 years ago

#13345 needs_info defect

Test if the assumptions made by quotient rings are fulfilled

Reported by: tfeulner Owned by: AlexGhitza
Priority: major Milestone: sage-6.4
Component: algebra Keywords:
Cc: mstreng Merged in:
Authors: Thomas Feulner Reviewers: Ralf Stephan
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #13347 Stopgaps: todo

Description (last modified by saraedum)

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

There is also a discussion about this on https://groups.google.com/d/topic/sage-devel/s5y604ZPiQ8/discussion.

Attachments (1)

trac13345_quotient_ring_assumptions.patch (8.8 KB) - added by tfeulner 8 years ago.

Download all attachments as: .zip

Change History (19)

comment:1 Changed 8 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: Changed 8 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 deprectaed. This means: a) use NotImplemntedError? right away and b) reimplement reduce() where neccessary.

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

Replying to sluther:

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 8 years ago by sluther

Replying to tfeulner:

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: Changed 8 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.

Changed 8 years ago by tfeulner

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

  • Dependencies set to 13347

Replying to mstreng:

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 7 years ago by tfeulner

  • Status changed from new to needs_review

comment:8 Changed 7 years ago by saraedum

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

comment:9 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:10 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:11 Changed 6 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 6 years ago by rws

  • Reviewers set to Ralf Stephan

comment:13 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:14 Changed 6 years ago by malb

  • Status changed from needs_review to needs_work

comment:15 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:16 Changed 4 years ago by jakobkroeker

  • Stopgaps set to todo

comment:17 Changed 4 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 4 years ago by saraedum

  • Status changed from needs_work to needs_info
Note: See TracTickets for help on using tickets.