Improved use of category framework for IntegerModRing

[simon-king-jena]

On sage-devel, some discussion on IntegerModRing and its relation to categories took place. I would summarize the discussion and its consequences as follows:

• It should be possible for the user to indicate that the modulus of an IntegerModRing is prime, so that the ring is a field, without Sage performing a primality test. However (not part of the discussion) GF(n) does a primality test (actually it factors n---is this really needed?). So, the user can not simply use GF(n) if n is a huge number that the user knows to be a prime number.
• It was suggested that the user can instead do IntegerModRing(n, category=Fields()). This feature was asked for in Categories for IntegerMod rings #8562 and implemented in Categories for all rings #9138.
• .is_field() should do a primality test, unless it is already known that the ring is a field. It has been suggested in the discussion on sage-devel to let .is_field() change the category of the ring. At the time of the discussion, this did not seem possible, but in Serious regression caused by #9138 #11900 this feature has been added.

By #11900, refinement of category happens when it is tested whether the IntegerModRing is a field by R in Fields(). However, there is some inconsistency:

sage: S = IntegerModRing(5)
sage: S.category()
Join of Category of commutative rings and Category of subquotients of monoids and Category of quotients of semigroups and Category of finite enumerated sets
sage: S in Fields()
True
sage: S.category()
Join of Category of fields and Category of subquotients of monoids and Category of quotients of semigroups and Category of finite enumerated sets
sage: R = IntegerModRing(5, Fields())
sage: R.category()
Join of Category of fields and Category of subquotients of monoids and Category of quotients of semigroups

I think we would want that R and S are in the same category after the category refinement of S.

So, the first aim of this ticket is to make the categories consistent.

Secondly, comparison of IntegerModRing includes comparison of types. Originally, this has been introduced since one wanted GF(p) and IntegerModRing(p) evaluate differently. However, changing the category changes the type, and thus changes the ==-equivalence class. I think this must not happen. Hence, the second aim of this ticket is to make == independent of the category, while still letting GF(p) and IntegerModRing(p, category=Fields()) evaluate unequal.

Thirdly, in the discussion on sage-devel, it was suggested to refine the category of R when R.is_field() returns true. Currently, refinement only happens when R in Fields() returns true. So, the third aim of this ticket to do the refinement as suggested.

Cc to John Cremona, since it was he who brought the "category refinement in is_field()" topic up...

CC: @JohnCremona @nthiery @jpflori @novoselt

Component: categories

Keywords: sd53 category integermodring

Author: Simon King

Branch/Commit: 048aec7

Reviewer: Jean-Pierre Flori

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

[simon-king-jena]

comment:1

I just notice: We have IntegerModRing.is_field(self, proof=True), but the proof argument gets ignored! I think it should instead be passed to is_prime(), which also accepts a proof keyword. Hence, regardless whether proof=None, False or True, there will always the default arithmetic proof flag be used.

John, do you think it would make sense to set proof=None by default, and pass it to is_prime()? In this way, the "default arithmetic proof flag" would still be used by default, but it would be possible to override it.

[simon-king-jena]

comment:2

If one did

R = IntegerModRing(5, category=Fields())

then R.is_field() would still do a primality test.

Question: Shouldn't R.is_field() trust the user and first check whether R.category() is a subclass of Fields() before doing an expensive test?

The following seems reasonable to me:

def is_field(self, proof=None):
    if not proof:
        if self.category().is_subcategory(Fields()):
            return True
    is_prime = self.order().is_prime(proof=proof)
    if is_prime:
        self._refine_category_(Fields())
    return is_prime

[JohnCremona]

comment:3

THis looks a very sensible soution to me.

[simon-king-jena]

comment:4

Thank you, John. Concerning GF, I stand corrected: It only does a full factorisation after it has already been found that the modulus is a prime power.

[nbruin]

comment:5

Replying to @simon-king-jena:

Thank you, John. Concerning GF, I stand corrected: It only does a full factorisation after it has already been found that the modulus is a prime power.

That's probably OK because the factorization routine in question is quick in recognizing perfect powers and primes. Calling a generic factorization algorithm to find out what prime power we're dealing with is bad, of course.

[nbruin]

comment:6

As I point out on [#15223 comment:18], if we do (in a fresh sage session)

sage: R=IntegerModRing(19)
sage: C1=R.category()
sage: R in Fields()
sage: C2=R.category()

we have C1 is not C2. But if we run that same code again, we do find that C1 is C2. That's the normal result from R being a globally unique object and the conclusion one must draw is that R.category() is not an important attribute. Otherwise, the call R in Fields() would significantly modify global state, which means that a simple sanity check of input in a library routine somewhere could really foul up computations elsewhere!

So why would one care to specify the category upon construction if the thing doesn't matter? Worse, presently specifying category upon construction can cause multiple copies to exist. This implies that the category DOES matter, and hence should not be changed on global copies.

Another solution to forcing category refinement then would be

R.is_field(proof=True) #primality proof
R.is_field(proof=False) #only probable prime power check
R.is_field(proof=None) #no check at all

where the spelling of None is up for discussion. Perhaps it should be "I_know_I_can_screw_up_this_sage_session_with_this_never_mind_the_consequences_of_pickling_this".

So I think we can't have both automatic category refinement on global objects (indicating categories are not important for equality/identity) and category specification upon construction (which raises the expectation that they are and presently actually makes that the case).

The consequence of automatic category refinement is that you can't actually control the category that you get back even if you specify it: you might get back an answer in a finer category if that refinement happened to have been made before. Quoting from #15223 again:

sage: A1=IntegerModRing(19,category=Rings())
sage: A1.category()
Join of Category of commutative rings and Category of subquotients of monoids and Category of quotients of semigroups
sage: A1 in Fields()
True
sage: A2=IntegerModRing(19,category=Rings())
sage: A2.category()
Join of Category of subquotients of monoids and Category of quotients of semigroups and Category of fields

[nbruin]

comment:7

Concerning making non-identical parents equal, e.g., if we were to have

sage: R1=IntegerModRing(19)
sage: R2=IntegerModRing(19,distinguishing_flag)
sage: R1 == R2, R1 is R2
(True, False)

Then

sage: P1=PolynomialRing(R1,'x')
sage: P2=PolynomialRing(R2,'x')

wreaks havoc: Since the construction parameters of P1 and P2 are equal, we'll have P1 is P2, so the P2.base_ring() will actually be R1, not R2. This can lead to horrible surprises. I think we had some really convincing examples of that at some point, but I can't find the reference right now.

[simon-king-jena]

comment:8

Replying to @nbruin:

So why would one care to specify the category upon construction if the thing doesn't matter? Worse, presently specifying category upon construction can cause multiple copies to exist. This implies that the category DOES matter, and hence should not be changed on global copies.

That's related with one of the question I raised in #15223:

Would we like that there is precisely one instance of an integer mod ring for a given modulus, that is automatically updated if the user later provides more information?

Isn't GAP using a similar approach? It creates one object, and then its behaviour may change, when one learns more about it.

Hence, in this scenario, we would like that IntegerModRing (which is a factory) does not use the category argument for caching, but still passes it to the quotient ring.

I guess this is again a question to the number theorists (hence, John...): Would we like the following behaviour (not implemented yet)?

sage: R = IntegerModRing(5)
sage: R.category().is_subcategory(Fields())
False
sage: S = IntegerModRing(5, category=Fields())
sage: S is R    # currently False!
True
sage: R.category().is_subcategory(Fields())  # would currently only hold for S.category()
True

We would have a unique instance of IntegerModRing(5), and this unique instance would be refined, the more we learn about it, respectively the more the user tells us about it.

Another solution to forcing category refinement then would be

R.is_field(proof=True) #primality proof
R.is_field(proof=False) #only probable prime power check
R.is_field(proof=None) #no check at all

I wouldn't like that proof=False did more tests than proof=None.

[simon-king-jena]

comment:9

Replying to @nbruin:

Concerning making non-identical parents equal, e.g., if we were to have

sage: R1=IntegerModRing(19)
sage: R2=IntegerModRing(19,distinguishing_flag)
sage: R1 == R2, R1 is R2
(True, False)

Then ... this can lead to horrible surprises.

You are right. This would be no good.

[simon-king-jena]

comment:10

Replying to @nbruin:

So I think we can't have both automatic category refinement on global objects (indicating categories are not important for equality/identity) and category specification upon construction (which raises the expectation that they are and presently actually makes that the case).

We can! Namely, if the additional argument is ignored for the cache, but is still used to refine the existing object.

The consequence of automatic category refinement is that you can't actually control the category that you get back even if you specify it: ...

If we decide to ignore the additional argument for the cache and only use it to refine the unique global object, then this is a desired consequence. But phrased like "you can't actually make Sage forget what it found out about the category of the quotient ring".

[simon-king-jena]

comment:11

Replying to @simon-king-jena:

We would have a unique instance of IntegerModRing(5), and this unique instance would be refined, the more we learn about it, respectively the more the user tells us about it.

Perhaps it would make sense then to introduce a method Parent._unset_category(self), that would change the class of self to self.__class__.__base__ (I tested: This would actually be possible) and set the cdef ._category attribute to None?

Using such method, it would be possible to revert the changes, if the user was wrong in assuming that the modulus was prime. For example:

sage: R = IntegerModRing(15, category=Fields()) # 15 is odd, and hence it is prime
sage: R in Fields()
True
sage: R.is_field()
True
sage: R.is_field(proof=True)    # Ooops, there are odd numbers that aren't prime
False
sage: R._unset_category()
sage: R._init_category_(<put appropriate category here>)

And then, R would be in the same state as with originally defining R = IntegerModRing(15).

Perhaps erasing of wrong assumptions on primality can automatically be done in R.is_field(proof=True)?

[simon-king-jena]

Branch: u/SimonKing/ticket/15229

[simon-king-jena]

comment:13

I have pushed a preliminary version of the branch.

It addresses the three points from the ticket description. But, as Nils has reminded me, we should not use the additional argument for the cache key (because of polynomial rings over integer mod rings). This, and perhaps an automatic update of a globally unique version of ZZ/nZZ, may be in the next commit...

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

[changeset:1d2e2bc]

Document the "proof" argument of is_field.

[sagetrac-git]

Commit: 1d2e2bc

[nbruin]

comment:15

Replying to @simon-king-jena:

Sure, having a way to do R.is_field(proof="believe_me") upon construction is fine. But is specifying category=Fields() the most economic/obvious interface for doing so? What other meaningful values are there? Wouldn't it be better to do

IntegerModRing(19,is_field=True)

instead? If the only meaningful value is Fields(), it seems to me that allowing the caller to specify any category there is just handing him extra rope for hanging only.

Concerning GAP's approach: I'm not familiar, but allowing the behaviour of global objects to significantly change sounds like a bad idea. It makes it really hard to argue about any piece of code if you have to take into account the whole history of the system all the time.

As far as I understand, presently, category refinement is simply used as a "cache" of computed data, but that means one shouldn't attach much further value to it either. Note how easily it can change:

sage: R=IntegerModRing(19)
sage: R.category()
Join of Category of commutative rings and Category of subquotients of monoids and Category of quotients of semigroups and Category of finite enumerated sets
sage: P=R['x']
sage: (P.0^2-1).roots()
[(18, 1), (1, 1)]
sage: R.category()
Join of Category of subquotients of monoids and Category of quotients of semigroups and Category of finite enumerated sets and Category of fields

[nbruin]

Changed commit from 1d2e2bc to none

[nbruin]

Changed branch from u/SimonKing/ticket/15229 to none

[nbruin]

comment:16

Branch u/SimonKing/ticket/15229 deleted
Commit 1d2e2bc deleted

Ouch, that doesn't look good. I don't know why trac did that. I definitely didn't selected those things to happen.

[simon-king-jena]

Branch: u/SimonKing/ticket/15229

[simon-king-jena]

comment:17

My "category eraser" works. With it, one can do the following:

        Let us create a parent in the category of rings::

            sage: class MyParent(Parent):
            ....:     def __init__(self):
            ....:         Parent.__init__(self, category=Rings())
            ....:
            sage: P = MyParent()
            sage: P.category()
            Category of rings

        Of course, its category is initialised::

            sage: P._is_category_initialized()
            True

        We may now refine the category to the category to the
        category of fields. Note that this changes the class::

            sage: C = type(P)
            sage: C == MyParent
            False
            sage: P._refine_category_(Fields())
            sage: P.category()
            Category of fields
            sage: C == type(P)
            False

        Now we notice that the category refinement was a mistake.
        Hence, we undo category initialisation totally::

            sage: P._unset_category()
            sage: P._is_category_initialized()
            False
            sage: type(P) == MyParent
            True

        And finally, we initialise the parent again in the original
        category, i.e., the category of rings, finding that the
        class of the parent is brought back to what it was after
        the original category initialisation::

            sage: P._init_category_(Rings())
            sage: type(P) == C
            True

Question (e.g. to Nicolas):

Do we want to have such a category eraser? Then, refining the category of a quotient ring would not hurt so much, because it could easily be reverted when one finds that the refinement was a mistake.

[simon-king-jena]

Commit: 1d2e2bc

[simon-king-jena]

comment:18

Replying to @nbruin:

Branch u/SimonKing/ticket/15229 deleted
Commit 1d2e2bc deleted

Ouch, that doesn't look good. I don't know why trac did that. I definitely didn't selected those things to happen.

Dunno. Anyway, trac chose to revert the deletion.

Hmm. It is ironical that trac reverted a mistake exactly when I suggested a new method to revert a mistaken category refinement... :-D

[nbruin]

comment:19

I don't know about playing around with categories too much that way. Could we have something like the following:

sage: R = SomeRing()
sage: F = FieldOfFractions(R)
ValueError: R is not an integral domain
sage: R._refine_category_(IntegralDomains())
sage: F = FieldOfFractions(R)
sage: R._unset_category()
sage: R._init_category_(Rings())
sage: R in IntegralDomains()
False
sage: F
Field of fractions of R

That would seem bad to me. Of course, as a debugging tool it may be OK, but I don't thing unrefining a category should be an advertised/supported feature. There may be objects around that rely on the category of the object as it was (and it may well be too expensive to ensure the category gets re-refined any time it relies on it)

[simon-king-jena]

comment:20

Replying to @nbruin:

I don't know about playing around with categories too much that way. Could we have something like the following:

Yes, of course.

All these _refine_category_ and _unset_category methods start with an underscore for a reason: You should only use them if you know what you are doing. And similarly, with the category=Fields() option of IntegerModRing, you should be ready to bear the consequences of any misuse.

That would seem bad to me. Of course, as a debugging tool it may be OK, but I don't thing unrefining a category should be an advertised/supported feature.

You can see it in this way: If you are in the fourth line of your example, then you are in a total mess. Unsetting the category might help you to clean some mess after the mess was created, but it wouldn't be appropriate to expect that it can clean everything.

However, being able to clean some mess is still better than nothing.

[simon-king-jena]

comment:21

And, by the way, we have:

sage: R = IntegerModRing(15, category=Fields())
sage: Frac(R)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-2-d5df03326cb5> in <module>()
----> 1 Frac(R)

/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/rings/fraction_field.pyc in FractionField(R, names)
    126         raise TypeError, "R must be a ring"
    127     if not R.is_integral_domain():
--> 128         raise TypeError, "R must be an integral domain."
    129     return R.fraction_field()
    130 

TypeError: R must be an integral domain.

So, this might actually be an argument of using the R.is_bla() methods, rather than relying on R in CategoryOfBla().

[simon-king-jena]

comment:56

All tests pass, but I guess I should remove some trailing whitespace.

[sagetrac-git]

Changed commit from 2a08a44 to fae3f07

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

fae3f07	Trac 15229: Complete a phrase in the doc, remove trailing whitespace
7b61761	Merge branch 'master' into ticket/15229

[simon-king-jena]

comment:58

Oops, I didn't know that I had merged (an old version of) master into the branch. Meanwhile I have learnt that one shouldn't do such merges. In any case: There was some trailing whitespace, and there was a phrase that ended somewhere in the middle and needed completion.

And this ticket needs review!

[rwst]

Work Issues: rebase

[tscrim]

Changed commit from fae3f07 to b012bf3

[tscrim]

Changed branch from u/SimonKing/ticket/15229 to public/categories/improve_integer_mod_ring-15229

[tscrim]

comment:63

This solves an issue noted in #15475 (and #11979). I've rebased it and (non-long) doctests in the file pass, what needs review to finalize this?

---

New commits:

77f733d	Merge branch 'u/SimonKing/ticket/15229' of trac.sagemath.org:sage into public/categories/improve_integer_mod_ring-15229
b012bf3	Some tweaks to get doctests passing from the merge.

[tscrim]

Changed work issues from rebase to none

[simon-king-jena]

comment:65

Replying to @tscrim:

This solves an issue noted in #15475 (and #11979). I've rebased it and (non-long) doctests in the file pass, what needs review to finalize this?

Sorry, no idea. It has been too long since I last had a look at the patch.

[jpflori]

comment:66

I had a look and am mostly happy with this ticket, though I might still prefer to let coexisted different instances of Z/nZ.
Anyway I know how to hack the cache so I can live with the current solution.

Two minor typos:

• an integer 1
• 21 is hardcoded in an error message.

[sagetrac-git]

Changed commit from b012bf3 to 048aec7

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

8f728f1	Merge remote-tracking branch 'trac/develop' into ticket/15229
048aec7	Correct two minor typos for IntegerModRing category use improvements.

[jpflori]

Reviewer: Jean-Pierre Flori

[vbraun]

Changed branch from public/categories/improve_integer_mod_ring-15229 to 048aec7