Opened 7 years ago

Closed 7 years ago

#14084 closed defect (fixed)

Wrong domain of the fraction field construction functor

Reported by: SimonKing Owned by: roed
Priority: major Milestone: sage-5.8
Component: padics Keywords:
Cc: Merged in: sage-5.8.beta0
Authors: Simon King Reviewers: Julian Rueth
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

The construction functor for fraction fields pretends that it takes any ring as input:

sage: Fract,R = QQ.construction()
sage: Fract.domain()
Category of rings
sage: Fract.codomain()
Category of fields

But of course that's wrong:

sage: Fract(ZZ.quo(15))
Traceback (most recent call last):
...
TypeError: self must be an integral domain.

Hence, it would be better to declare right away that its domain is the category of integral domains.

Attachments (1)

trac14084_integral_domains.patch (8.6 KB) - added by SimonKing 7 years ago.

Download all attachments as: .zip

Change History (34)

comment:1 Changed 7 years ago by SimonKing

First two problems:

sage: Zp(7) in IntegralDomains()
False
sage: ZZ[['x']] in IntegralDomains()
False

comment:2 Changed 7 years ago by SimonKing

And similarly:

sage: Qp(7).category()
Category of commutative rings
sage: Qp(7).is_field()
True

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

... but

sage: k=Qp(7)
sage: k.category()
Category of commutative rings
sage: k in Fields()
True
sage: k.category()
Category of fields

which is a little uncomfortable in its own right. You'd think that a category is part of the defining properties of the parent, so changing it seems to fly into the face of immutability of parents.

If we have to keep it like this, we'd have to be very clear that one should only test if a parent is IN a given category; never rely on the category reported by "<parent>.category()". It certainly flies in the face of what I thought sage did: I thought specifying a parent implied specifying the category in which you want to consider it, and that if you want to consider a number field as a QQ-vector space instead, one should explicitly apply a functor and use a map (or perhaps conversion if you want to be implicit about it) to go between the two.

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

Replying to nbruin:

... but

sage: k=Qp(7)
sage: k.category()
Category of commutative rings
sage: k in Fields()
True
sage: k.category()
Category of fields

which is a little uncomfortable in its own right.

No, this is very important for making the test k in Fields() fast without caching.

You'd think that a category is part of the defining properties of the parent, so changing it seems to fly into the face of immutability of parents.

No. It is just "learning more and more about immutable properties of the parent".

If we have to keep it like this, we'd have to be very clear that one should only test if a parent is IN a given category; never rely on the category reported by "<parent>.category()".

Sure. It could always be that the reported category is a subcategory of what one wants to have. R in C is recommended, but R.category() is C is not.

It certainly flies in the face of what I thought sage did: I thought specifying a parent implied specifying the category in which you want to consider it, and that if you want to consider a number field as a QQ-vector space instead, one should explicitly apply a functor and use a map (or perhaps conversion if you want to be implicit about it) to go between the two.

I think this is currently not supported.

comment:5 in reply to: ↑ 3 ; follow-up: Changed 7 years ago by nthiery

Replying to nbruin:

... but

sage: k=Qp(7)
sage: k.category()
Category of commutative rings
sage: k in Fields()
True
sage: k.category()
Category of fields

which is a little uncomfortable in its own right. You'd think that a category is part of the defining properties of the parent, so changing it seems to fly into the face of immutability of parents.

If we have to keep it like this, we'd have to be very clear that one should only test if a parent is IN a given category; never rely on the category reported by "<parent>.category()". It certainly flies in the face of what I thought sage did: I thought specifying a parent implied specifying the category in which you want to consider it, and that if you want to consider a number field as a QQ-vector space instead, one should explicitly apply a functor and use a map (or perhaps conversion if you want to be implicit about it) to go between the two.

The above is in fact alright because Fields is a full subcategory of Rings. So by going from one to the other, one don't change the structure under consideration. One is just learning more properties of this structure.

I certainly agree that I would not want the category of my parent to change from Vector Space to Ring, because then I am adding a new structure (the multiplication).

Full subcategories are not yet modeled in Sage, but this is in the plans, because that's what we want to go further with homsets.

Cheers,

Nicolas

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

At first glance, changing the categories of Zp(p) and Qp(p) seems not totally easy, simply because the code base is formed by a lot of slightly differently sounding base classes. But, as it says in sage.rings.padic.local_generic:

Local Generic

Superclass for `p`-adic and power series rings.

So, if we are lucky, both Zp, Qp and power series rings can be fixed at the same time.

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

Replying to SimonKing:

Local Generic

Superclass for `p`-adic and power series rings.

So, if we are lucky, both Zp, Qp and power series rings can be fixed at the same time.

We are not lucky.

sage: P = QQ[['x']]
sage: isinstance(P,sage.rings.padics.local_generic.LocalGeneric)
False

comment:8 Changed 7 years ago by SimonKing

  • Component changed from categories to padics
  • Owner changed from nthiery to roed

Part of the problem is that the padic rings and fields inherit from sage.rings.ring.Ring, but they never call ring initialisation.

There are cases in which calling __init__ of the super-classes is a bad idea, as it gives a speed regression. Question to users of padics: Are there cases in which one needs to create very many different padic rings and fields? If "yes", then shortcutting __init__ makes sense. If not, it would be cleaner to call __init__ of the base classes.

comment:9 Changed 7 years ago by SimonKing

PS: Part of the problem is that sage.padics.local_generic.LocalGeneric inherits from CommutativeRing, but calls Parent.__init__(self, base, element_constructor=element_class, names=(names,), normalize=False, category=category or _CommutativeRings).

Where is the problem? Well, CommutativeRing.__init__ does not know about the argument element_constructor...

comment:10 Changed 7 years ago by SimonKing

Aha! Instead of passing the element_class to Parent.__init__, one can simply assign it to self.Element! Then, the category framework can be initialised as usual, namely by calling CommutativeRing.__init__.

comment:11 Changed 7 years ago by SimonKing

It is becoming odder and odder.

sage: P = Zp(15, check=False)
sage: P.__class__.mro()
[sage.rings.padics.padic_base_leaves.pAdicRingCappedRelative_with_category,
 sage.rings.padics.padic_base_leaves.pAdicRingCappedRelative,
 sage.rings.padics.generic_nodes.pAdicRingBaseGeneric,
 sage.rings.padics.padic_base_generic.pAdicBaseGeneric,
 sage.rings.padics.generic_nodes.pAdicCappedRelativeRingGeneric,
 sage.rings.padics.generic_nodes.pAdicRingGeneric,
 sage.rings.padics.padic_generic.pAdicGeneric,
 sage.rings.ring.EuclideanDomain,
 sage.rings.ring.PrincipalIdealDomain,
 sage.rings.ring.IntegralDomain,
sage: P.is_integral_domain()
True

So, if one creates a p-adic ring where p is not prime, then it still inherits from EuclideanDomain, and is convinced that it is an integral domain. That makes me wonder whether we could actually always initialise a p-adic ring in the category of Euclidean domains, regardless whether check=True or check=False is used.

comment:12 Changed 7 years ago by SimonKing

Aha!! Finally, the old ways of programming are helpful! The old base classes have an attribute _default_category. Hence, in LocalGeneric, one can simply do

        self.Element = element_class
        Parent.__init__(self, base, names=(names,), normalize=False, category=getattr(self,'_default_category',None))

and then one immediately gets

sage: P = Zp(5)
sage: TestSuite(P).run()
sage: K = Qp(7)
sage: TestSuite(K).run()

Since (in spite of the comment in the doc string of sage.rings.padics.local_generic) power series rings do not inherit from that class, they need to be dealt with independently.

comment:13 Changed 7 years ago by SimonKing

Good!

sage: P = ZZ[['x']]
sage: P._default_category
Category of integral domains
sage: P._is_category_initialized()
True
sage: P.category()
Category of commutative rings

So, again, one should be able to simply use self._default_category when initialising the power series ring.

comment:14 Changed 7 years ago by SimonKing

Argh. Multivariate power series rings appear to not have an attribute _default_category. So, they need to be provided with it.

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

Replying to nthiery:

The above is in fact alright because Fields is a full subcategory of Rings. So by going from one to the other, one don't change the structure under consideration. One is just learning more properties of this structure.

For the most part I probably agree with that. However, how does this relate to additional concepts such as "finitely generated"?

The following is probably not entirely kosher in terms of mathematical categories, but it may affect the colloquial use of them in computer algebra:

The Gaussian field QQ(i) would generally be considered a finitely generated field, but as a ring it would not be finitely generated (no characteristic 0 field is). Of course one should specify over what object they are finitely generated, and the discrepancy comes from the different default choices for fields and rings: The prime fields QQ and GF(p) for fields versus ZZ for commutative rings.

I would love to see that we can use the "category" field as a dynamic attribute as suggested, because it does make these is_field tests wonderfully fast without requiring complicated additional caching. But I am concerned that phenomena (or misconceptions) as above might come back and bite us if we're coming to depend on such tricks extensively. Can you ease that concern?

comment:16 Changed 7 years ago by SimonKing

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

I think I made it work. See attachment.

Implementing the category can result in a slow-down in the creation of parents. Let's see what happens here. Without the patch:

sage: %time L = [Zp(p) for p in prime_range(2,10^4)]
CPU times: user 2.00 s, sys: 0.09 s, total: 2.09 s
Wall time: 2.09 s

With the patch:

sage: %time L = [Zp(p) for p in prime_range(2,10^4)]
CPU times: user 2.10 s, sys: 0.05 s, total: 2.15 s
Wall time: 2.15 s

I hope that's acceptable.

comment:17 in reply to: ↑ 15 ; follow-up: Changed 7 years ago by nthiery

Replying to nbruin:

Replying to nthiery:

The above is in fact alright because Fields is a full subcategory of Rings. So by going from one to the other, one don't change the structure under consideration. One is just learning more properties of this structure.

For the most part I probably agree with that. However, how does this relate to additional concepts such as "finitely generated"?

The following is probably not entirely kosher in terms of mathematical categories, but it may affect the colloquial use of them in computer algebra:

The Gaussian field QQ(i) would generally be considered a finitely generated field, but as a ring it would not be finitely generated (no characteristic 0 field is). Of course one should specify over what object they are finitely generated, and the discrepancy comes from the different default choices for fields and rings: The prime fields QQ and GF(p) for fields versus ZZ for commutative rings.

I would love to see that we can use the "category" field as a dynamic attribute as suggested, because it does make these is_field tests wonderfully fast without requiring complicated additional caching. But I am concerned that phenomena (or misconceptions) as above might come back and bite us if we're coming to depend on such tricks extensively. Can you ease that concern?

I guess you pointed the key fact above: one can have some shortcuts for the users convenience, but for a robust answer one should always specify for which category the thing is finitely generated. For the same reason .gens should only be a shortcut. For robust results, one should always specify the category. Which is my motivation for promoting the use of semigroup_generators / monoid_generators / algebra_generators / ... Luckily, in some cases we have nice names (finite dimensional, basis,...) for those.

Cheers,

Nicolas

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

Replying to nthiery:

For robust results, one should always specify the category.

But that's the issue: The category is specified:

Hypothetical dialogue (I'm sorry it has to be this academic--I don't presently have an actual example).

sage: QQ.category()
Category of Commutative Rings
sage: QQ.is_finitely_generated()
False

Sage confirms that at this point, it's considering QQ as a commutative ring and as such is not finitely generated.

sage: QQ in Fields()
True
sage: QQ.category()
Category of Fields
sage: QQ.is_finitely_generated()
True

Since the category here is Fields the question about finite generation should be considered there. Since it's a prime field I don't see how any other answer than True could be considered there.

This suggests to me that the concept of finite generation is not well-behaved w.r.t. restricting to full subcategories. I don't think that disqualifies it as a reasonable thing to ask. Instead, it suggests to me that it's not safe to implicitly change categories to full subcategories, since that change can affect what the answers to certain perfectly reasonable questions are.

It's important to keep in mind that by insisting on unique parents, sage is deviating from what most computer algebra systems choose to do. It makes the immutability of parents extremely important, because mutations can have extremely non-local consequences. Hence, every time immutability is violated one has to argue extremely carefully that the effect is immaterial. Changing categories sounds like a very dangerous thing to me.

Normally I'm not a fan of discussions about hypothetical code. However, here I think this issue is worth serious thinking because we're touching on fundamental infrastructure in sage:

The parent you get back when you ask for its construction can either be a fresh one, or one that is already referenced somewhere, or one that was already deleted but not yet found by the garbage collector (perhaps because it got trapped in a permanent cache somewhere), depending on what happened before.

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

I do agree that changing the category on the fly looks suspicious. The true reason for originally implementing it in that way was speed: There were many fields that have not been initialised as fields, but had a method is_field; hence, the test K in Fields() used to first check the category and then the answer of is_field (similar to what is done now). Repeating this test used to be incredibly slow, which was quite visible in some examples.

Note that this change of class and category---changing from (the parent class of) one category to (the parent class of) the join of this category with the category of fields---is not a regression. Actually, it fixes a bug. Namely, in the good old times, one could very well have P in Fields() return true and P in IntegralDomains() return false. Now, P in IntegralDomains() would return true---at least when it is called after P in Fields().

If all fields would be initialised as fields right away, we could certainly avoid this dangerous game. But the original rationale for working with the is_field methods is still valid: Sometimes the test of something really is a field is very expensive (primality tests, etc). So, one should avoid the expensive test as long as possible.

comment:20 in reply to: ↑ 19 ; follow-ups: Changed 7 years ago by nbruin

I think we really need another way to cache whether a ring is a field then. What you describe is indeed the case:

sage: R=ZZ.quo(7)
sage: R in IntegralDomains() ##1
False
sage: R in Fields()
True
sage: R in IntegralDomains() ##2
True

you can see that the call R in Fields() has mutated the parent in an essential way. The kind of call that people HAVE to use to look at the category field because it is not trustworthy by itself even can change depending on what happens with the parent elsewhere!

Whether ##1 is a bug or not depends on how you interpret the question: Are we asking the mathematical truth (which in general might be undecidable) or are we asking what sage knows about the object by construction? The first would of course be nicer, but computer algebra systems often settle for the second.

The important thing here is to illustrate how easy it is to mutate parents in a significant way if you start mucking with their category.

Personally I think it's fine if ZZ.quo(7) doesn't advertise itself as a field by construction. People can ask for GF(7) instead, which luckily does give back a non-identical parent:

sage: R=ZZ.quo(7)
sage: R2=GF(7)
sage: id(R)
85206256
sage: id(R2)
17095856

By the way:

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: R2.category()
Join of Category of subquotients of monoids and Category of quotients of semigroups and Category of finite fields

I have to say those values do a good job of dissuading people from ever looking at them!

Also, this discussion is not of direct relevance to this ticket, so perhaps we should take the discussion to sage-devel instead.

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

Replying to nbruin:

I think we really need another way to cache whether a ring is a field then.

Another instance of a weak cache perhaps? But if I recall correctly, I played with weak caches of the "is_Field" function -- and the speed was not competitive.

Also note that changing the category of the ring has indirect advantages: There may be more parent and element methods become available when passing to a sub-category.

I would say the change of category is allowed when one could have chosen that category during initialisation, and if the only reason for not doing so during initialisation is efficiency: I have seen applications involving matrix spaces, for which it really did not matter whether the matrix space is a vector space or an algebra or just a set -- I just don't remember the ticket number. Hence, in these applications, one would postpone the initialisation of the category of a matrix space, and only do it when necessary.

And in the case of ring versus field, I could imagine that there are examples in which one just needs to know that a given parent is a ring. In these applications, it would be a waste of time to determine during creation of the parent whether it actually is a field or not (which may involve primality tests). Hence, for efficiency, one should postpone the test of "being a field" until it is really needed.

Also, this discussion is not of direct relevance to this ticket, so perhaps we should take the discussion to sage-devel instead.

+1.

The "change of category" has not been introduced here, and not in #13370 either. In fact, in the good old times, it was possible to have P in Fields() and P not in IntegralDomains(). Hence, I think of the refinement of categories as a progress.

I therefore suggest to use a new ticket, if someone finds a more satisfying solution of the "speed versus immutability problem".

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

Replying to nbruin:

Replying to nthiery:

For robust results, one should always specify the category.

But that's the issue: The category is specified:

Hypothetical dialogue (I'm sorry it has to be this academic--I don't presently have an actual example).

sage: QQ.category()
Category of Commutative Rings
sage: QQ.is_finitely_generated()
False

Sage confirms that at this point, it's considering QQ as a commutative ring and as such is not finitely generated.

sage: QQ in Fields()
True
sage: QQ.category()
Category of Fields
sage: QQ.is_finitely_generated()
True

Since the category here is Fields the question about finite generation should be considered there. Since it's a prime field I don't see how any other answer than True could be considered there.

Sorry, I have been ambiguous. What I mean is that, for the answer to be well defined, one should specify the category at the time one asks whether the object is finitely generated. Something like:

     sage: Q.is_finitely_generated(Fields())

or

     sage: Q.is_finitely_generated_field()

Then,

     sage: Q.is_finitely_generated()

would return the answer for the current category of Q; but that's just a lousy syntactic sugar, for the user convenience, when there is no ambiguity.

This suggests to me that the concept of finite generation is not well-behaved w.r.t. restricting to full subcategories.

It's just not well defined if you don't specify explicitly for which category you are asking the question.

Cheers,

Nicolas

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

Replying to nthiery: [...] Would you take this discussion to sage-devel, please? These are very important points that will need good thought and solutions, so there are likely more people interested in them. Also, these issues are not really directly relevant to this ticket.

comment:24 in reply to: ↑ 20 Changed 7 years ago by nthiery

Replying to nbruin:

I think we really need another way to cache whether a ring is a field then. What you describe is indeed the case:

sage: R=ZZ.quo(7)
sage: R in IntegralDomains() ##1
False
sage: R in Fields()
True
sage: R in IntegralDomains() ##2
True

you can see that the call R in Fields() has mutated the parent in an essential way. The kind of call that people HAVE to use to look at the category field because it is not trustworthy by itself even can change depending on what happens with the parent elsewhere!

Whether ##1 is a bug or not depends on how you interpret the question: Are we asking the mathematical truth (which in general might be undecidable) or are we asking what sage knows about the object by construction? The first would of course be nicer, but computer algebra systems often settle for the second.

By design, the category of an object in Sage describes:

(a) It's "operations" (additive structure, multiplicative

structure). This conditions what the morphisms are in the category.

(b) The properties of the operations that Sage is aware of at this

point in time (either because they were specified by the user or discovered during some computation).

Note that the distinction between (a) and (b) will be made clearer with the upcoming functorial construction patch #10963 which introduces an infrastructure for "axioms" for (b).

I totally agree that (a) should not change over the lifetime of an object. But I consider it a very important feature that (b) can change over time: when we discover new properties of an object, we want to exploit them to use better algorithms. And we might as well have every reference to that object in the current Sage session benefit from the improvement.

Of course, for that to make sense, changing (b) should only influence efficiency, and not change the *semantic* of questions; for that the questions should be unambiguous.

Note that GAP is doing (b) intensively for precisely that reason (although they use a different mechanism, through method selection rather than object orientation).

By the way:

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: R2.category()
Join of Category of subquotients of monoids and Category of quotients of semigroups and Category of finite fields

I have to say those values do a good job of dissuading people from ever looking at them!

Working on that :-) With my current functorial patch, this should be roughly "Category of finite commutative quotient fields."

Cheers,

Nicolas

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

Replying to nbruin:

Replying to nthiery: [...] Would you take this discussion to sage-devel, please? These are very important points that will need good thought and solutions, so there are likely more people interested in them. Also, these issues are not really directly relevant to this ticket.

I totally agree. Now to start a constructive discussion on sage-devel one would need to write a short synthesis of the above discussion. With Sage Days 45 just starting, I just don't have the time now for that. But please proceed if you can!

comment:26 Changed 7 years ago by nthiery

Sorry I had missed the thread you had already created ...

comment:27 follow-up: Changed 7 years ago by saraedum

  • Reviewers set to Julian Rueth
  • Status changed from needs_review to needs_info

Simon, in local_generic.py you add a category parameter but seem to ignore it. Was that intended?

Changed 7 years ago by SimonKing

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

  • Status changed from needs_info to needs_review

Replying to saraedum:

Simon, in local_generic.py you add a category parameter but seem to ignore it. Was that intended?

No. Originally I thought of a different way to initialise stuff, because I thought that LocalGeneric is the base class of both power series rings and p-adic rings. So, I expected that the sub-classes would eventually like to pass a category to the init method of LocalGeneric.

But since it is only used for p-adic rings, it isn't needed.

The questions remain:

  • Should power series inherit from LocalGeneric? This would be for a different ticket.
  • Since power series do not inherit from LocalGeneric, shouldn't the documentation of local_generic.py be corrected accordingly?

Anyway. I have updated the patch.

comment:29 in reply to: ↑ 28 Changed 7 years ago by saraedum

Replying to SimonKing:

The questions remain:

  • Should power series inherit from LocalGeneric? This would be for a different ticket.

In theory they should. Otherwise we would not need the distinction of pAdicGeneric and LocalGeneric. I guess we should open a new ticket and see if anything bad happens if they do.

Anyway. I have updated the patch.

Great. I'll wait for the patchbot to test this, and then I'll set it to positive review.

comment:30 Changed 7 years ago by SimonKing

The patchbot seems to like it...

comment:31 Changed 7 years ago by saraedum

  • Status changed from needs_review to positive_review

comment:32 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-5.7 to sage-5.8

comment:33 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.8.beta0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.