Opened 7 years ago

Closed 6 years ago

#15229 closed defect (fixed)

Improved use of category framework for IntegerModRing

Reported by: SimonKing Owned by:
Priority: major Milestone: sage-6.4
Component: categories Keywords: sd53 category integermodring
Cc: cremona, nthiery, jpflori, novoselt Merged in:
Authors: Simon King Reviewers: Jean-Pierre Flori
Report Upstream: N/A Work issues:
Branch: 048aec7 (Commits) Commit: 048aec78e9546d0ab881f072482cfe9e0f220817
Dependencies: Stopgaps:

Description

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 #8562 and implemented in #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 #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...

Change History (69)

comment:1 Changed 7 years ago by SimonKing

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.

comment:2 Changed 7 years ago by SimonKing

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

comment:3 Changed 7 years ago by cremona

THis looks a very sensible soution to me.

comment:4 follow-up: Changed 7 years ago by SimonKing

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.

comment:5 in reply to: ↑ 4 Changed 7 years ago by nbruin

Replying to SimonKing:

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.

comment:6 follow-ups: Changed 7 years ago by nbruin

As I point out on http://trac.sagemath.org/ticket/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

comment:7 follow-up: Changed 7 years ago by 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

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.

comment:8 in reply to: ↑ 6 ; follow-up: Changed 7 years ago by SimonKing

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.

comment:9 in reply to: ↑ 7 Changed 7 years ago by SimonKing

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.

comment:10 in reply to: ↑ 6 ; follow-up: Changed 7 years ago by SimonKing

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".

comment:11 in reply to: ↑ 8 Changed 7 years ago by SimonKing

Replying to SimonKing:

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)?

comment:12 Changed 7 years ago by SimonKing

  • Branch set to u/SimonKing/ticket/15229
  • Created changed from 09/26/13 13:12:41 to 09/26/13 13:12:41
  • Modified changed from 09/26/13 16:57:24 to 09/26/13 16:57:24

comment:13 Changed 7 years ago by SimonKing

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

comment:14 Changed 7 years ago by git

  • Commit set to 1d2e2bcf623690bdaf81b63b5e200b1ea0feb4bb

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

[changeset:1d2e2bc]Document the "proof" argument of is_field.

comment:15 in reply to: ↑ 10 Changed 7 years ago by nbruin

  • Branch u/SimonKing/ticket/15229 deleted
  • Commit 1d2e2bcf623690bdaf81b63b5e200b1ea0feb4bb deleted

Replying to SimonKing:

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

comment:16 follow-up: Changed 7 years ago by nbruin

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

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

comment:17 Changed 7 years ago by SimonKing

  • Branch set to u/SimonKing/ticket/15229
  • Cc nthiery added
  • Commit set to 1d2e2bcf623690bdaf81b63b5e200b1ea0feb4bb

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.

Last edited 7 years ago by SimonKing (previous) (diff)

comment:18 in reply to: ↑ 16 Changed 7 years ago by SimonKing

Replying to nbruin:

Branch u/SimonKing/ticket/15229 deleted Commit 1d2e2bcf623690bdaf81b63b5e200b1ea0feb4bb 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

comment:19 follow-up: Changed 7 years ago by nbruin

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)

comment:20 in reply to: ↑ 19 Changed 7 years ago by SimonKing

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.

comment:21 follow-up: Changed 7 years ago by SimonKing

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

comment:22 in reply to: ↑ 21 ; follow-up: Changed 7 years ago by nbruin

Replying to SimonKing:

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

It might, but in my view an invalid one: I think we established that R in ... was faster (once initialized) because we end up co-opting python's highly efficient mro implementation. So I think it's more a argument to ensure the category stays sane.

Coming back to the category= keyword. The documentation would be something along the lines of

   category = C : Ensure that the object returned lies in a refinement
       of C. Note that the returned object may lie in a strict
       refinement. Additionally, note that, due to the fact that the
       object returned is globally unique, the object returned 
       may be identical to the result of independent constructions.
       These would naturally now also have a refined category.

By the time the doc looks like that, do you still think that's the best API to allow specifying that a quotient ring is a field upon construction?

Do you have a rationale to expose something that complex in the construction interface if the same can be accomplished using _refine_category_ afterwards?

comment:23 in reply to: ↑ 22 ; follow-up: Changed 7 years ago by SimonKing

Replying to nbruin:

Do you have a rationale to expose something that complex in the construction interface if the same can be accomplished using _refine_category_ afterwards?

Good point. If one has a potentially dangerous functionality, then it makes sense to hide it from the occasional user by making it underscore---and it may be a bad idea to make this "forbidden magic" available in the constructor.

To my rehabilitation: I introduced the category keyword because it was formulated as "todo" in the docs, and it was formulated as "todo" because of the mentioned discussion on sage-devel.

The question to the number theorists is: Is the category keyword actually used somewhere? If it is, then one might replace it by _refine_category_, so that the category keyword can be removed.

And the question to all of us is:

Testing R in Fields() may rely on a probabilistic primality test. Thus, it might be that R in Fields() and R.is_field() give the wrong answer and hence the category is automatically refined incorrectly. Do we want that R.is_field(proof=True) reverts the category refinement, if it finds that R is in fact not a field?

comment:24 Changed 7 years ago by SimonKing

A quick "grep" told me that the category argument is in fact not used. But I think it would make sense to make a poll on sage-devel or sage-algebra or sage-nt before removing it.

comment:25 in reply to: ↑ 23 Changed 7 years ago by nbruin

Replying to SimonKing:

Testing R in Fields() may rely on a probabilistic primality test. Thus, it might be that R in Fields() and R.is_field() give the wrong answer and hence the category is automatically refined incorrectly. Do we want that R.is_field(proof=True) reverts the category refinement, if it finds that R is in fact not a field?

If we use something like Baillie-PSW it shouldn't just revert the category, it should also file for $620 to be donated to the Sage foundation. Probabilistic primality tests are really good.

comment:26 follow-ups: Changed 7 years ago by SimonKing

  • Keywords sd53 category integermodring added

I guess at some point we should post a question/poll on either sage-devel or sage-nt. But before doing so, we should discuss here what exactly to ask. Here, I try to give arguments for several approaches to solve our problem.

It was requested in the old sage-devel discussion that the user should be able to indicate that a certain modulus is prime, so that the integer mod ring is mathematically a field. The question is mainly: How should be indicated that it is a field, and what consequences should providing this information imply?

How?

It could be by an optional argument, but what exactly should be provided?

  • "category=...": Most parent's constructors now have an optional category argument. So, it seems consistent with other parts of Sage to offer the same argument to integer mod rings.
  • "is_field=False/True?": All what we requested was a way to indicate whether the ring is a field or not. So, we just need a bool, and there is no need to allow an arbitrary fully fledged category in the constructor. On the other hand, there might be future applications which make use of categories beyond "is field/is not field".

Alternatively, one could indicate the "field-ness" only after initialisation. Hence:

  • There should be no optional argument to IntegerModRing. Instead, the user has the possibility to do R._refine_category_(Fields()) after initialisation, perhaps wrapped into a method .use_as_field().

Consequences

Mathematically, there is only one quotient ring ZZ/nZZ. But what shall happen computationally?

One could argue that it might make sense to computationally have two versions of the same ring, namely one version that knows it is a field, and another one that does not know it. Or perhaps we find constructions which equip certain quotient rings with other fancy structures (say, Hopf algebra or so). Then it might make sense to have a third version of the same ring, knowing that it is a Hopf algebra.

Or one could argue that the ring either is a field or it is not, and it either has a Hopf algebra structure or it has not. From this point of view, there should be a unique instance of this ring, and additional structures (field, Hopf algebras) are all accumulated in this single instance.

So, it is not clear whether an optional argument provided to the IntegerModRing factory should be ignored in the cache or not.

A potential argument against accumulating information in a globally unique instance is: Globally unique instances should be immutable. But what exactly does "immutable" mean? It means: It will not change its hash and its equivalence class with respect to cmp (because this is what is used to construct a set or dictionary).

Thus, in any case, we have a bug to fix, because _refine_category_ changes the class of the instance, and the class is currently having an impact in __cmp__.

Safety

As you have pointed out, providing the wrong category on purpose may result in a serious mess. You argued that this means we must not allow full freedom in choosing the category. But I think we should acknowledge that Python has a rather permissive policy: We must not be over-protective.

So, it might be good to have an "eraser" such as _unset_category(), but of course such an eraser will impossibly be able to fix all bad consequences of choosing a wrong category.

Proposal

These are my personal preferences; in some cases my preference is actually not clear...

  • Keep the optional argument "category", to be consistent with the rest of Sage.
  • Use the category to speed-up is_field(), unless "proof=True` is requested.
  • Keep refining the category if R.is_field() or R in Fields() succeeds with some primality check.
  • As you said, a wrong primality test would be a great discovery. And bad consequences of a wrong primality test are quite likely to be not easily fixable. Hence, I think it would not make sense to automatically fix the category, if R.is_field(proof=True) finds that R is not a field.
  • Fix: Since the category can be refined, but the object must be immutable, __cmp__ must be invariant under a change of category. This would also be consistent with the current bidirectional coercion maps between integer mod rings.
  • I am undecided whether there should be a globally unique quotient ring for a given modulus, accumulating information, or one should keep having different instances evaluating equal.

comment:27 Changed 7 years ago by SimonKing

  • Modified changed from 09/27/13 10:09:09 to 09/27/13 10:09:09

For what it's worth, I have created #15234, introducing the category eraser.

I chose to open a different ticket, because I think it makes sense to have the eraser indepently of the problem discussed here, and since it is not clear from the discussion whether we actually want to apply the eraser here.

Last edited 7 years ago by SimonKing (previous) (diff)

comment:28 Changed 7 years ago by git

  • Commit changed from 1d2e2bcf623690bdaf81b63b5e200b1ea0feb4bb to 75576e2d6f36e3a6d0edb2b6c368cc817ee34280

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

[changeset:75576e2]Warn if an integer mod ring is mistakenly found in Fields()

comment:29 in reply to: ↑ 26 ; follow-up: Changed 7 years ago by SimonKing

Replying to SimonKing:

Proposal

These are my personal preferences; in some cases my preference is actually not clear...

  • Keep the optional argument "category", to be consistent with the rest of Sage.
  • Use the category to speed-up is_field(), unless "proof=True` is requested.
  • Keep refining the category if R.is_field() or R in Fields() succeeds with some primality check.
  • As you said, a wrong primality test would be a great discovery. And bad consequences of a wrong primality test are quite likely to be not easily fixable. Hence, I think it would not make sense to automatically fix the category, if R.is_field(proof=True) finds that R is not a field.
  • Fix: Since the category can be refined, but the object must be immutable, __cmp__ must be invariant under a change of category. This would also be consistent with the current bidirectional coercion maps between integer mod rings.

All the above is achieved with the current commit and its ancestors. A warning is printed, that also asks to inform the developers, in the case that a probabilistic primality test has failed.

  • I am undecided whether there should be a globally unique quotient ring for a given modulus, accumulating information, or one should keep having different instances evaluating equal.

What do y'all think?

comment:30 in reply to: ↑ 29 Changed 7 years ago by SimonKing

  • Cc jpflori novoselt added

Replying to SimonKing:

  • I am undecided whether there should be a globally unique quotient ring for a given modulus, accumulating information, or one should keep having different instances evaluating equal.

What do y'all think?

I made a poll here at SD53: Would you think that there should be a unique instance of ZZ/nZZ that accumulates information, or should one have one instance that was told that it is a field (perhaps erroneously) and another instance that does not know about it?

It seems that all but two people said that one should have a unique instance, whose category is updated when one learns more on it or when the user provides more information on it.

I am not totally sure, but perhaps Jean-Pierre can chime in: What has been the argument of having distinct instances?

I also talked with Andrey, and he said (in my own summary): If the user explicitly provides certain wrong data on a ring (such as IntegerModRing(15, category=Fields())) and then later wants to construct the same ring without the wrong data, then it would not make sense to return a new instance of the ring. Namely, after IntegerModRing(15, category=Fields()) is done, the whole Sage session is compromised, and it would not help to have a second non-broken ring. Starting a new Sage session is the only reasonable thing to do in such situation.

So, I will now attempt to modify the IntegerModRing factory such that the additional category argument will be ignored in the cache, but used to refine the category of what is found in the cache. In other words, I try to make it so that there is a unique instance of ZZ/nZZ.

comment:31 in reply to: ↑ 26 ; follow-up: Changed 7 years ago by nbruin

Replying to SimonKing:

It was requested in the old sage-devel discussion that the user should be able to indicate that a certain modulus is prime, so that the integer mod ring is mathematically a field. The question is mainly: How should be indicated that it is a field, and what consequences should providing this information imply?

  • "is_field=False/True?": All what we requested was a way to indicate whether the ring is known to be a field or not.

(note correction in bold). For reasons I explain below, I'm not so sure using category=... is actually consistent with other uses in sage. Most category settings/changes should and do' affect equality and should result in distinct objects. This is not the case for the "is_field" case.

Alternatively, one could indicate the "field-ness" only after initialisation.

I suspect many people would consider that bothersome. It does better convey it is a mutation of something that (possibly) already exists, though, making it clearer that it may modify global state.

One could argue that it might make sense to computationally have two versions of the same ring, namely one version that knows it is a field, and another one that does not know it. Or perhaps we find constructions which equip certain quotient rings with other fancy structures (say, Hopf algebra or so).

Different situation! There's extra data (or perhaps you forget some data) so, for one thing, the homomorphisms on the object in that category are different.

Or one could argue that the ring either is a field or it is not, and it either has a Hopf algebra structure or it has not.

Being a field is indeed a property of a ring. To make a ring into a Hopf algebra you have to specify extra information. Even if there may be only one way to specify that extra information, this usually affects the category.

Thus, in any case, we have a bug to fix, because _refine_category_ changes the class of the instance, and the class is currently having an impact in __cmp__.

+1

So, it might be good to have an "eraser" such as _unset_category(), but of course such an eraser will impossibly be able to fix all bad consequences of choosing a wrong category.

I don't mind if it's there and it might be useful for debugging, but it won't actually help recover. It's just too hard to see what the ramifications of even a temporary lapse in consistency in the category settings does.

Proposal

These are my personal preferences; in some cases my preference is actually not clear...

  • Keep the optional argument "category", to be consistent with the rest of Sage.

Is it consistent? How does category get used in other cases? Do we have uses analogous to IntegersMod(17,category=AbelianGroups())? In that cases the specified category IS important.

The relation of Fields, IntegralDomains etc. to Rings is a bit special: The concept of homomorphism doesn't change, which is why the category refinement can happen automatically. So these are very limited category changes that are indeed "insignificant". Most other category changes are significant (because they arise from applying some forgetful functor or fixing some extra (arbitrary?) data.

If other uses of category are or a different type, we should definitely not try to be consistent with it for special is_field case.

Of course, we do want to be consistent with other ring quotient constructors, where testing primality or maximality of the ideal we mod out by might be even more involved.

  • Use the category to speed-up is_field(), unless "proof=True` is requested.

+1

  • Keep refining the category if R.is_field() or R in Fields() succeeds with some primality check.

+1

  • As you said, a wrong primality test would be a great discovery. And bad consequences of a wrong primality test are quite likely to be not easily fixable. Hence, I think it would not make sense to automatically fix the category, if R.is_field(proof=True) finds that R is not a field.

Given that at this point we've found that the global state of sage is really messed up, we should probably raise an error. The state is whatever it is at that point ...

  • Fix: Since the category can be refined, but the object must be immutable, __cmp__ must be invariant under a change of category. This would also be consistent with the current bidirectional coercion maps between integer mod rings.

+1 with caveat: What are the possible values of category we want to consider here?

  • I am undecided whether there should be a globally unique quotient ring for a given modulus, accumulating information, or one should keep having different instances evaluating equal.

We cannot do the latter if we want to be able to construct UniqueRepresentation parents with coefficients in these non-unique-but-equal bases: constructing a polynomial ring over one might return a polynomial ring over the other, which violates all kinds of assumptions in the coercion framework.

See this hypothetical example (yay, I found the reference).

Last edited 7 years ago by nbruin (previous) (diff)

comment:32 Changed 7 years ago by git

  • Commit changed from 75576e2d6f36e3a6d0edb2b6c368cc817ee34280 to cdc6806af14eb3353ad8fd4b6c2598ea6f33abca

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

[changeset:cdc6806]Replace optional "category" argument by "is_field"

comment:33 in reply to: ↑ 31 Changed 7 years ago by SimonKing

In the new commit I just pushed, I drop the "category" argument and replace it by "is_field". Note that old pickles using the category argument should still be unpicklable, but perhaps someone can test.

Moreover, I made ZZ/nZZ globally unique. Rationale: Being a field is a property that a ring either has or has not. Hence, it makes no sense to have different instances, one knowing that it is a field and the other not knowing. The unique instance is updated when one learns more on it, one way (primality test) or the other (user info).

Replying to nbruin:

Replying to SimonKing: For reasons I explain below, I'm not so sure using category=... is actually consistent with other uses in sage. Most category settings/changes should and do' affect equality and should result in distinct objects. This is not the case for the "is_field" case.

You say somewhere below that my example of a Hopf algebra structure is not good, because one could not say that this structure is a property of the ring, since it is an additional structure. Indeed this convinces me, and in this case, one should create a sub-class of IntegerModRing_generic.

Note that IntegerModRing is just a factory. Hence, while IntegerModRing_generic.__init__ should of course have a "category" argument (to be consistent with all base classes!), the factory does not need "category".

Alternatively, one could indicate the "field-ness" only after initialisation.

I suspect many people would consider that bothersome. It does better convey it is a mutation of something that (possibly) already exists, though, making it clearer that it may modify global state.

In the current branch, doing IntegerModRing(p, is_field=True) will put the result into the category of fields, either taking an existing non-field version of the ring from the cache, or creating a new instance.

Thus, in any case, we have a bug to fix, because _refine_category_ changes the class of the instance, and the class is currently having an impact in __cmp__.

+1

For the record, that's in some previous commit already.

So, it might be good to have an "eraser" such as _unset_category(), but of course such an eraser will impossibly be able to fix all bad consequences of choosing a wrong category.

I don't mind if it's there and it might be useful for debugging, but it won't actually help recover. It's just too hard to see what the ramifications of even a temporary lapse in consistency in the category settings does.

See #15234

The relation of Fields, IntegralDomains etc. to Rings is a bit special: The concept of homomorphism doesn't change, which is why the category refinement can happen automatically. So these are very limited category changes that are indeed "insignificant". Most other category changes are significant (because they arise from applying some forgetful functor or fixing some extra (arbitrary?) data.

If other uses of category are or a different type, we should definitely not try to be consistent with it for special is_field case.

Meanwhile, I made it "is_field"...

  • Use the category to speed-up is_field(), unless "proof=True` is requested.

+1

done

  • Keep refining the category if R.is_field() or R in Fields() succeeds with some primality check.

+1

done

  • As you said, a wrong primality test would be a great discovery. And bad consequences of a wrong primality test are quite likely to be not easily fixable. Hence, I think it would not make sense to automatically fix the category, if R.is_field(proof=True) finds that R is not a field.

Given that at this point we've found that the global state of sage is really messed up, we should probably raise an error. The state is whatever it is at that point ...

OK. Currently it just prints a warning, but raising a proper error would of course be an option. You think I should do it in the next commit?

  • Fix: Since the category can be refined, but the object must be immutable, __cmp__ must be invariant under a change of category. This would also be consistent with the current bidirectional coercion maps between integer mod rings.

+1 with caveat: What are the possible values of category we want to consider here?

Well, meanwhile there are only two possible values. Something like "join of Category of commutative rings, finite enumerated sets and (sub?)quotients of rings", and the same thing with "fields" instead of commutative rings.

The current __cmp__ removes the category information totally, which would of course be a mistake for sub-classes that are more than just "field" or "not field" (as in my Hopf algebra example). Hence, __cmp__ should be overridden on the subclasses.

  • I am undecided whether there should be a globally unique quotient ring for a given modulus, accumulating information, or one should keep having different instances evaluating equal.

We cannot do the latter if we want to be able to construct UniqueRepresentation parents with coefficients in these non-unique-but-equal bases: constructing a polynomial ring over one might return a polynomial ring over the other, which violates all kinds of assumptions in the coercion framework.

OK. I prefer uniqueness anyway. With the current commit, we have uniqueness.

Last edited 7 years ago by SimonKing (previous) (diff)

comment:34 Changed 7 years ago by SimonKing

Pickling Problem/Question:

Suppose that R is an integer mod ring, originally created not in the category of fields. Suppose that later we find out that it is in fact a field. Suppose that even later we save R to a file, and load this file into a new Sage session.

Do we want that the reloaded version of R is immediately initialised as a field?

With the current commit, the following would happen.

sage: R = IntegerModRing(7)
sage: R.category().is_subcategory(Fields())
False
sage: R.is_field()
True
sage: R.category().is_subcategory(Fields())
True
sage: save(R, 'tmp')

Quit sage and start a new session

sage: R = load('tmp.sobj')
sage: R.category().is_subcategory(Fields())
False
sage: R.is_field.cache
{}

So, the "field" information, that might have been obtained by a quite expensive primality test, has been completely lost.

Do we want that pickles remember the field-ness?

Last edited 7 years ago by SimonKing (previous) (diff)

comment:35 Changed 7 years ago by novoselt

I think pickles should remember everything, unless there are insurmountable technical difficulties to it! Especially if this ring was told by the user that it is a field to avoid doing any tests.

comment:36 Changed 7 years ago by git

  • Commit changed from cdc6806af14eb3353ad8fd4b6c2598ea6f33abca to 6ada7e07eca00256f3336f933cbddd3dfcbdf98f

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

[changeset:6ada7e0]Raise an error if a non-prime integer mod ring is found in Fields()

comment:37 Changed 7 years ago by SimonKing

Pickling is not addressed yet in the current commit, but now there is a BIG FAT error if a primality test fails on something that was supposed to be a field.

comment:38 Changed 7 years ago by SimonKing

It would be possible to make pickles store all cached information about the integer mod ring. Namely, we just need to append self.__dict__ to the current return value of self.__reduce__(). Do we want this?

comment:39 Changed 7 years ago by novoselt

I think reasons against pickling something are:

  • it takes too much space
  • it takes too much time to pickle
  • it takes too much time to unpickle

In most cases none of these applies, I suspect, so I don't think what is the problem with pickling everything by default. Having a convenient way to manually turn off pickling in the above cases would be nice, of course, as well as having a generic framework to deal automatically with circular references from cache and uniqueness (which is currently a problem with toric varieties).

comment:40 follow-up: Changed 7 years ago by SimonKing

The pickling thing is not so easy.

First of all, __setstate__ is inherited from ParentWithGens, that expects the dictionary to contain certain data that make no sense to pickle. It could mean that we have to override __setstate__.

Secondly, what happens if we have created a ring R in a sage session, and R.is_field already has cached values. If we then load a ring with the same modulus from a file, then (by uniqueness) R is returned---but R.__dict__ is updated with what we have found on the disc: The cached values would still be available to R.is_field, but the values would not be part of R.__dict__ any longer. Hence, if we then save R again to a new file, the new pickle would not contain the cached values.

Would it be worth it? It doesn't seem so.

But one thing would certainly be possible: If the category is updated to Fields(), either by providing the optional argument to the factory or by what is now happening inside R.is_field(), then the data used for pickling could be updated. Hence, when we now load R from a file, it would immediately be in Fields(), even though the cached values of is_field() will be lost.

Would this be an acceptable compromise?

comment:41 Changed 7 years ago by novoselt

Certainly fine with me! Someyear, hopefully, ParentWithGens will be gone and perhaps things will work smoother, but for now it can count as "insurmountable technical difficulties". I don't insist on pickling anything, just think that in general it should work.

comment:42 Changed 7 years ago by git

  • Commit changed from 6ada7e07eca00256f3336f933cbddd3dfcbdf98f to 2a08a447be22e4307372524c4b94ca0577d927c9

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

[changeset:2a08a44]Make pickling of ZZ/nZZ aware of being in Fields()

comment:43 Changed 7 years ago by SimonKing

  • Authors set to Simon King
  • Status changed from new to needs_review

With the current commit, one can do

sage: R = IntegerModRing(7)
sage: save(R, 'tmpR')
sage: R.category().is_subcategory(Fields())
False
sage: R in Fields()
True
sage: R.category().is_subcategory(Fields())
True
sage: save(R, 'tmpRcat')

and then in a new Sage session

sage: R = load('tmpR.sobj')
sage: R.category().is_subcategory(Fields())
False
sage: F = load('tmpRcat.sobj')
sage: F is R
True
sage: R.category().is_subcategory(Fields())
True

or, in another new Sage session

sage: F = load('tmpRcat.sobj')
sage: F.category().is_subcategory(Fields())
True
sage: R = load('tmpR.sobj')
sage: R is F
True
sage: R.category().is_subcategory(Fields())
True

So, we still have a globally unique integer mod ring, even after unpickling a ring and a field version of the same integer mod ring. And the information found in the pickle will be used to update the unique integer mod ring.

The cached data are not preserved in the pickle, but I hope we can do without it. I make it "needs review" now.

comment:44 in reply to: ↑ 40 ; follow-up: Changed 7 years ago by nbruin

Replying to SimonKing:

Secondly, what happens if we have created a ring R in a sage session, and R.is_field already has cached values. If we then load a ring with the same modulus from a file, then (by uniqueness) R is returned---but R.__dict__ is updated with what we have found on the disc: The cached values would still be available to R.is_field, but the values would not be part of R.__dict__ any longer.

What is the problem here? __setstate__ by default should update self.__dict__ with the pickled dictionary, not replace it. The python documentation makes quite clear that this is what is done in the default situation (i.e., when there's no __setstate__ at all). We should definitely follow that almost everywhere, unless we have very good reasons not to, which should be documented.

So if the pickled ring had no cached value for is_field, the value doesn't get clobbered. If the existing and the pickled version both have cached values stored, but they are conflicting then it's a mess anyway.

comment:45 follow-up: Changed 7 years ago by nbruin

I think ParentWithGens already mostly does the right thing. It's just a bit inflexible to either expect that all these required attributes must be filled from the dict or have no dict at all. I'm also doubtful that we should leave these entries in the dict. These are slot attributes, right, so it's useless:

sage: P=QQ['x']
sage: P.__dict__['base']=0
sage: P._base
Rational Field

so it would be cleaner to remove them anyway, e.g.

    def __setstate__(self, d):
        if d.has_key('_element_constructor'):
            return parent.Parent.__setstate__(self, d)
+       t=d.pop('_base',None); if t is not None: self._base = t
+       t=d.pop('_gens',None); if t is not None: self._gens = t
+       t=d.pop('_gens_dict',None); if t is not None: self._gens_dict = t
+       t=d.pop('_list',None); if t is not None: self._list = t
+       t=d.pop('_latex_names',None); if t is not None: self._latex_names = t
+       #if this attribute doesn't exist it has no business in the pickle either.
+       t=d.pop('_generator_orders',None); if t is not None: self._generator_orders = t
        try:
            self.__dict__.update(d)
-           self._generator_orders = d['_generator_orders']
        except (AttributeError,KeyError):
+           for key,value in d.iteritems():
+               setattr(self,key,value)
-       self._base = d['_base']        
-       self._gens = d['_gens']
-       self._gens_dict = d['_gens_dict']
-       self._list = d['_list']
-       self._names = d['_names']
-       self._latex_names = d['_latex_names']

Incidentally, if an InterModRing were to be part of a cycle in which it's important to know that it's a field, setstate may be too late to avoid triggering the primality test. So perhaps you should just pickle the is_field as part of the construction parameters if it's true. A {'is_field':True} kwargs won't create cycles.

There's of course the issue that unpickling the dictionary is almost certainly more expensive than doing the primality test for smallish moduli. In fact, if you look at what

Last edited 7 years ago by nbruin (previous) (diff)

comment:46 in reply to: ↑ 44 Changed 7 years ago by SimonKing

Replying to nbruin:

Replying to SimonKing: What is the problem here? __setstate__ by default should update self.__dict__ with the pickled dictionary, not replace it.

sage: R = IntegerModRing(7)
sage: R.is_field(proof=False)
True
sage: R.__dict__
{'_IntegerModRing_generic__factored_order': None,
 '_IntegerModRing_generic__factored_unit_order': None,
 '_IntegerModRing_generic__order': 7,
 '_IntegerModRing_generic__unit_group_exponent': None,
 '_QuotientRing_nc__I': Principal ideal (7) of Integer Ring,
 '_QuotientRing_nc__R': Integer Ring,
 '__reduce_ex__': <bound method ?.generic_factory_reduce of Ring of integers modulo 7>,
 '_cache__is_field': {((False,), ()): True},
 '_pyx_order': <sage.rings.finite_rings.integer_mod.NativeIntStruct at 0xbba9c8c>,
 'is_field': Cached version of <function is_field at 0x926dd4c>}
sage: R.is_field.cache is R._cache__is_field
True

Now we update the __dict__ by something that would come up when unpickling an old instance of the same ring that had called R.is_field() instead of R.is_field(proof=False). The effect would be:

sage: R.__dict__.update([('_cache__is_field', {((None,), ()):True})])

and, as I have promised, the cache of is_field is detached from the dictionary that is in __dict__:

sage: R.is_field.cache is R._cache__is_field
False

Hence, if we now do

sage: R.is_field(proof=True)
True

(which might be a particular expensive computation, as we do proof=True), and if we then pickle R, then the pickle would not store the result of the computations we had with proof=False and proof=True, but only the one without providing the proof argument. Reason:

sage: R._cache__is_field
{((None,), ()): True}

Do you see the problem now?

So if the pickled ring had no cached value for is_field, the value doesn't get clobbered.

Correct.

If the existing and the pickled version both have cached values stored, but they are conflicting then it's a mess anyway.

No, they are not conflicting in my example above. They simply are caches for different values of an optional argument.

Last edited 7 years ago by SimonKing (previous) (diff)

comment:47 in reply to: ↑ 45 ; follow-ups: Changed 7 years ago by SimonKing

Replying to nbruin:

These are slot attributes, right, so ... it would be cleaner to remove them anyway [in __setstate__]

No, that's wrong. The purpose of this __setstate__ is to fill the slots from a given dictionary. And I am sure that this is used somewhere in Sage, and thus removing it would break things.

Incidentally, if an InterModRing were to be part of a cycle in which it's important to know that it's a field, setstate may be too late to avoid triggering the primality test. So perhaps you should just pickle the is_field as part of the construction parameters if it's true.

This is what the current branch does. If the category gets updated either by providing the new optional argument is_field=True in the IntegerModRing factory, or by calling R.is_field() (which will also be called if you do R in Fields()), then the construction parameters used for pickling are updated.

In other words, my current branch does not use __setstate__.

comment:48 in reply to: ↑ 47 Changed 7 years ago by SimonKing

Replying to SimonKing:

In other words, my current branch does not use __setstate__.

Then you may ask: "Why did he start mentioning __setstate__?"

Well, easy. If the new optional argument is_field=True is provided to the IntegerModRing factory (e.g., by unpickling), then both R.is_field() and R.is_field(proof=False) will exploit this information, i.e., they will avoid the primality test. But R.is_field(proof=True) will do the primality test even if IntegerModRing(..., is_field=True) had been done.

Hence: Caching R.is_field() and R.is_field(proof=False) is not critical, because the "semantics" of the result is stored in the pickle via is_field=True. However, caching R.is_field(proof=True) is critical, because is_field=True is not good enough for avoiding the primality test.

This is why I wondered how one can pickle the cache of R.is_field, and I have shown that this is not easy.

comment:49 in reply to: ↑ 47 Changed 7 years ago by nbruin

Replying to SimonKing:

Replying to nbruin:

These are slot attributes, right, so ... it would be cleaner to remove them anyway [in __setstate__]

No, that's wrong. The purpose of this __setstate__ is to fill the slots from a given dictionary. And I am sure that this is used somewhere in Sage, and thus removing it would break things.

I agree with the latter bit, but I don't see what's wrong then. We're probably misunderstanding. The code I proposed does set attributes Do you mean we should copy d before we pop from it?.

In principle, __setstate__ should just do with the dictionary:

for key,value in d:
    setattr(self,key,value)

If we do that, we don't need any extra machinery. However, the observation is that for attributes that live in self.__dict__, an update is faster. However, slot attributes that for pickling reasons get put into d should not afterwards still be added to __dict__. Access to them is shadowed by slots anyway. So, by the time you do self.__dict__.update(d) you should make sure that attributes that are stored in slots have been scrubbed from d. I don't think it's usually a disaster to also have them in self.__dict__, but it's pointless and messy and it's not what the object looked like before pickling.

Thanks for explaining the caching problem. What we'd need is a merge of of the cache dictionary and that's hard to arrange. This problem will arise with all cachedmethods on unique objects. So regardless of cyclicity, pickling (unique) objects with cached methods is a bit broken anyway: restoring a pickle can delete information on an existing object. This only occurs for methods that take arguments, but unfortunately it includes optional arguments such as proof=.

While writing @cachedmethod for structural data seems like a convenient trick, I think we're increasingly finding that its implementation causes trouble that would likely not arise from manually implemented caching strategies (just test and assign an attribute). Perhaps we should stop advocating "you should just use @cachedmethod".

CachedMethodNoArgs is fine, but there a lazy_attribute is usually a tiny bit more efficient.


Come to think of it, the way cachedmethod stores its cache makes the problem more readily apparent, but the problem is more general.

The problem we're running into is basically the usual "merge conflict resolution". Our unique objects are supposed to be immutable, but they still have some stuff on them that can change/be refined during the lifetime. One would assume the "refinements" are ordered (perhaps form a lattice?), so given two different states of refinement there should be a common state that is a refinement of either, and that would be the appropriate state to be in after merging. Can we think of a low-cost framework to encode such info? If the "refining" state consists of a dict that grows more more entries, then the appropriate merge is indeed to merge the dictionaries (the fact that it's refinement should mean that if keys occur in both, then the values should agree)

In cases where the variable state is not ordered by "refinement" I doubt we can do anything, but in those cases, I suspect that our object really cannot be considered "immutable" and hence the thing shouldn't be unique.

So one way would be to have a list of attributes that are to be "merged" rather than be overwritten in setstate. Then the instantiation of @cachedmethod could include registering the relevant attribute for the setstate.

This could be similarly implemented to the "initialize upon construction" attributes in the RichPickle? draft on #15207.

I think such a protocol should be implemented on CachedRepresentation since that introduces the trouble. That would be the place to try and resolve the ensuing pickling problems.

It also means that classes that inherit from CachedRepresentation and implement a __setstate__ should either follow the protocol themselves or comply by calling the setstate of CachedRepresentation in an appropriate manner.

Last edited 7 years ago by nbruin (previous) (diff)

comment:50 follow-up: Changed 7 years ago by nthiery

Hi!

Lots of discussion here :-)

The current consensus makes full sense to me up to one detail. My personal preference would be to keep using the "category" argument to specify that the parent is a field.

I am using this idiom all the time to e.g. specify that my monoids are finite/commutative/J-Trivial/... And also, sometimes, to add actual structure to a parent by implementing it in the category that I pass to it. That might be a bit borderline, but it's super practical :-)

In a perfect world, where we would have a clean support for full subcategories, it would be nice to have, for any parent class P, the property that P(..., category=As()) and P(..., category=Bs()) are identical if and only if As() and Bs() are two full subcategories of the same category. Of course, axioms can help in this direction, but we probably don't have a complete enough infrastructure to implement this generically.

But maybe, as a step toward this, we can at this point implement this behavior by hand in the special cases that deserve it like IntegerModRing??

In any cases, keep up the good work!

Cheers,

Nicolas

comment:51 in reply to: ↑ 50 Changed 7 years ago by SimonKing

Replying to nthiery:

The current consensus makes full sense to me up to one detail. My personal preference would be to keep using the "category" argument to specify that the parent is a field.

So, would you think we should make it so that IntegerModRing understands both is_field=True and category=Fields(), namely with IntegerModRing(p, is_field=True) is IntegerModRing(p, category=Fields())?

BTW, I don't understand the errors that the patchbot is reporting. They seem unrelated...

comment:52 follow-ups: Changed 7 years ago by nthiery

I for myself would tend to just support the category=Fields() syntax.

Imagine a case where the parent could have five different axioms depening on the input; then you'd have to support five arguments when only one does the trick uniformly. That's not a completely insane thought: e.g. for non-commutative groebner basis your could have as axioms: finite dimensional, finite, commutative, nozerodivisors, ... ).

comment:53 in reply to: ↑ 52 Changed 7 years ago by nbruin

Replying to nthiery:

I for myself would tend to just support the category=Fields() syntax.

Imagine a case where the parent could have five different axioms depening on the input; then you'd have to support five arguments when only one does the trick uniformly. That's not a completely insane thought: e.g. for non-commutative groebner basis your could have as axioms: finite dimensional, finite, commutative, nozerodivisors, ... ).

What solution do you have in mind to model the equivalence classes of category arguments that need to be considered for "global unique instance" lookup?

Also, how do you determine which inputs for "category" are valid? Isn't that just going to be a list of "allowed" values? In that case, the equivalence classes are easy: you just group the "allowed" list. Note that we've found above that these category equivalence classes need to be closed under refinements that could possibly occur.

comment:54 Changed 7 years ago by SimonKing

Oops, I just see that I lost track of this one. Pulling the branch now...

comment:55 in reply to: ↑ 52 Changed 7 years ago by SimonKing

Replying to nthiery:

I for myself would tend to just support the category=Fields() syntax.

Imagine a case where the parent could have five different axioms depening on the input; then you'd have to support five arguments when only one does the trick uniformly. That's not a completely insane thought: e.g. for non-commutative groebner basis your could have as axioms: finite dimensional, finite, commutative, nozerodivisors, ... ).

I think the above discussion gives good arguments why the factory for integer mod rings should not allow general freedom in the choice of a category: The factory needs to ensure uniqueness of instances. Some choices of a category play well with uniqueness: You want full sub-categories, and you want that containment in the sub-category does not rely on additional data (a ring intrinsically either is or is not a field). But other categories should result in a non-equal copy of the ring; for example, a Hopf algebra structure is not an intrinsic property and should thus not use a globally unique copy of a ring.

Hence, the constructor of IntegerModRing_generic (or what's the name of the class?) should (and already does) of course accept a category argument. But here, we talk about the factory that manages quotients of the integer ring.

I say: The factory should make it possible that the user asserts that the resulting ring is in fact a field, to avoid expensive primality tests. However, if you want to prescribe any fancy category for the resulting ring, you should either refine the category after the ring has been returned by the factory, or you should create a new factory (for quotient rings providing a fancy Hopf algebra structure) that is orthogonal to the IntegerModRing factory.

In any case: Are there open questions from the discussion? AFAIK, the current branch addresses all questions. What is missing for a review?

comment:56 Changed 7 years ago by SimonKing

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

comment:57 Changed 7 years ago by git

  • Commit changed from 2a08a447be22e4307372524c4b94ca0577d927c9 to fae3f07320a2531901b9a0dac0d73b62e0fdf6aa

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

fae3f07Trac 15229: Complete a phrase in the doc, remove trailing whitespace
7b61761Merge branch 'master' into ticket/15229

comment:58 Changed 7 years ago by SimonKing

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!

comment:59 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:60 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:61 Changed 7 years ago by rws

  • Status changed from needs_review to needs_work
  • Work issues set to rebase

comment:62 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:63 follow-up: Changed 6 years ago by tscrim

  • Branch changed from u/SimonKing/ticket/15229 to public/categories/improve_integer_mod_ring-15229
  • Commit changed from fae3f07320a2531901b9a0dac0d73b62e0fdf6aa to b012bf33c9cc9319bc59e41136ac9ef12bb49f19
  • Work issues rebase deleted

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:

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

comment:64 Changed 6 years ago by tscrim

  • Status changed from needs_work to needs_review

comment:65 in reply to: ↑ 63 Changed 6 years ago by SimonKing

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.

comment:66 Changed 6 years ago by jpflori

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.

comment:67 Changed 6 years ago by git

  • Commit changed from b012bf33c9cc9319bc59e41136ac9ef12bb49f19 to 048aec78e9546d0ab881f072482cfe9e0f220817

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

8f728f1Merge remote-tracking branch 'trac/develop' into ticket/15229
048aec7Correct two minor typos for IntegerModRing category use improvements.

comment:68 Changed 6 years ago by jpflori

  • Reviewers set to Jean-Pierre Flori
  • Status changed from needs_review to positive_review

comment:69 Changed 6 years ago by vbraun

  • Branch changed from public/categories/improve_integer_mod_ring-15229 to 048aec78e9546d0ab881f072482cfe9e0f220817
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.