Opened 8 years ago
Closed 5 years ago
#11670 closed defect (fixed)
fix number fields being unique parents  this got broken over the years
Reported by:  was  Owned by:  davidloeffler 

Priority:  major  Milestone:  sage6.3 
Component:  number fields  Keywords:  
Cc:  Merged in:  
Authors:  Julian Rueth  Reviewers:  Simon King, Peter Bruin 
Report Upstream:  N/A  Work issues:  
Branch:  8b06ff7 (Commits)  Commit:  8b06ff7d7fef13bd3746a1524bc5744242f1a75e 
Dependencies:  Stopgaps: 
Description (last modified by )
For example, these are all wrong:
sage: K.<a> = NumberField(x^2  x  1) sage: loads(dumps(K)) is K False sage: K.<a> = NumberField(x^3  x  1) sage: loads(dumps(K)) is K False sage: K.<a> = CyclotomicField(7) sage: loads(dumps(K)) is K False
NOTE: To keep this project manageable for now, this ticket does *not* address similar issues for relative number fields, if there are any.
This is related to #10448.
Attachments (1)
Change History (43)
comment:1 Changed 8 years ago by
 Description modified (diff)
Changed 8 years ago by
comment:2 Changed 8 years ago by
 Status changed from new to needs_review
comment:3 Changed 8 years ago by
 Description modified (diff)
comment:4 Changed 8 years ago by
I should comment on UniqueFactory? and UniqueRepresentation? (from sage.structure.unique*). I made some attempt to use it, but decided against it for *this patch*. The main reason is that I want to fully maintain backward compatibility with old pickled objects, since there are a lot of pickled number field elements in the wild, and that is really opaque using UniqueRepresentation?. (Also, I am concerned using UniqueRepresentation? has some efficiency issues in terms of size and later changing how pickling works, since every time you pickle an object it wraps it in its own wrapper around other stuff, leading to another level of abstraction.) I don't claim that the current approach is the easiest to maintain in the long run  in fact, it got broke before by bad patches. But in this new patch, I've added a ton of comments and a big warning to help prevent this in the future.
comment:5 Changed 8 years ago by
I also applied the patch to sage4.7.2.alpha1 and ran "make ptestlong" with complete success.
comment:6 Changed 8 years ago by
Does that fix the issues discussed on #10448 as well?
There, I tried to fix the missing uniqueness of maximal orders in number fields using cached_method decorators. However, the most recent post on #10448 (five months ago) also mentions the problem that number fields aren't unique, and thus the maximal orders can only be as unique as the umber fields they are contained in.
comment:7 Changed 8 years ago by
comment:8 Changed 8 years ago by
Some brief remarks:
 In the test for
NumberField_absolute_v2
, you useNumberField_absolute_v1
(should be v2, not v1). The same forNumberField_cyclotomic_v2
andNumberField_quadratic_v2
.
 The format, if I am not mistaken, should be
OUTPUT:  tuple of parameters that define this field; used in caching and pickling
notOUTPUT:  tuple of parameters that define this field; used in caching and pickling
comment:9 Changed 8 years ago by
One problem bugging me at #10667 remains: If one calls the method point_exact
from sage.schemes.elliptic_curves.heegner with the option optimize=True
then a nonunique absolute number field (namely Number Field in a with defining polynomial x^12 + 4*x^11 + 56*x^10 + 170*x^9 + 1130*x^8 + 2564*x^7 + 10791*x^6 + 18054*x^5 + 51340*x^4 + 57530*x^3 + 102986*x^2 + 53724*x + 35001
) emerges.
If I can fix it then I'll post a patch here, not at #10667.
comment:10 Changed 8 years ago by
Yep. Here is an explicit example exposing the missing uniqueness:
sage: N = NumberField(x^12  4*x^11 + 6*x^10  5*x^9 + 5*x^8  9*x^7 + 21*x^6  9*x^5 + 5*x^4  5*x^3 + 6*x^2  4*x + 1, 'a') sage: M = N.optimized_representation()[0] sage: M Number Field in a6 with defining polynomial x^12  4*x^11 + 6*x^10  5*x^9 + 5*x^8  9*x^7 + 21*x^6  9*x^5 + 5*x^4  5*x^3 + 6*x^2  4*x + 1 sage: N is M.change_names(names='a') False sage: N == M.change_names(names='a') True
I guess it can be fixed in the change_names
method.
comment:11 Changed 8 years ago by
 Status changed from needs_review to needs_info
Aha, it boils down to one line in N.absolute_field
:
try: return self.__absolute_field[names] except KeyError: pass except AttributeError: self.__absolute_field = {} K = NumberField(self.defining_polynomial(), names, cache=False) K._set_structure(maps.NameChangeMap(K, self), maps.NameChangeMap(self, K)) self.__absolute_field[names] = K return K
Why is the option cache=False
used in that method?
comment:12 Changed 8 years ago by
I read the comment
# Note  never call this on a cached number field, since # that could eventually lead to problems.
in N._set_structure
. That might be a show stopper. But what actually happens if one applies it to a cached number field?
comment:13 Changed 8 years ago by
I see a potential workaround. In my example, we have
sage: N = NumberField(x^12  4*x^11 + 6*x^10  5*x^9 + 5*x^8  9*x^7 + 21*x^6  9*x^5 + 5*x^4  5*x^3 + 6*x^2  4*x + 1, 'a') sage: M = N.optimized_representation()[0] sage: K = M.change_names(names='a') sage: N == K True sage: N is K False sage: N.structure() (Ring Coercion endomorphism of Number Field in a with defining polynomial x^12  4*x^11 + 6*x^10  5*x^9 + 5*x^8  9*x^7 + 21*x^6  9*x^5 + 5*x^4  5*x^3 + 6*x^2  4*x + 1, Ring Coercion endomorphism of Number Field in a with defining polynomial x^12  4*x^11 + 6*x^10  5*x^9 + 5*x^8  9*x^7 + 21*x^6  9*x^5 + 5*x^4  5*x^3 + 6*x^2  4*x + 1) sage: K.structure() (Isomorphism given by variable name change map: From: Number Field in a with defining polynomial x^12  4*x^11 + 6*x^10  5*x^9 + 5*x^8  9*x^7 + 21*x^6  9*x^5 + 5*x^4  5*x^3 + 6*x^2  4*x + 1 To: Number Field in a6 with defining polynomial x^12  4*x^11 + 6*x^10  5*x^9 + 5*x^8  9*x^7 + 21*x^6  9*x^5 + 5*x^4  5*x^3 + 6*x^2  4*x + 1, Isomorphism given by variable name change map: From: Number Field in a6 with defining polynomial x^12  4*x^11 + 6*x^10  5*x^9 + 5*x^8  9*x^7 + 21*x^6  9*x^5 + 5*x^4  5*x^3 + 6*x^2  4*x + 1 To: Number Field in a with defining polynomial x^12  4*x^11 + 6*x^10  5*x^9 + 5*x^8  9*x^7 + 21*x^6  9*x^5 + 5*x^4  5*x^3 + 6*x^2  4*x + 1)
Would it make sense to declare two number fields different if they have different structure()
?
comment:14 Changed 8 years ago by
 Reviewers set to Simon King
comment:15 Changed 8 years ago by
 Status changed from needs_info to needs_review
comment:16 Changed 8 years ago by
 Status changed from needs_review to needs_work
comment:17 Changed 6 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:18 Changed 5 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:19 Changed 5 years ago by
 Branch set to u/saraedum/ticket/11670
 Modified changed from 01/30/14 21:20:52 to 01/30/14 21:20:52
comment:20 Changed 5 years ago by
 Commit set to cab3fe1eb4c425f0028b221494f95a03199f2936
With the branch I just pushed, I got rid of _set_structure
. The structure of a number field is now always set when it is created. I know that unpickling of old objects is currently broken, I'm working on a fix. Anyway, maybe somebody already wants to have a look at what I have done so far? Any comments would be appreciated.
Should I now add old number field pickles to the pickle jar? I could not find out how to do this from the reference manual. Or is this somehow done automagically?
New commits:
c9b7129  Removed number field's _set_structure() which breaks caching

16aa7ec  Create number fields in a factory to make sure they are unique parents.

835c817  Implemented NumberFieldStructure classes to improve caching of (absolute) number fields.

3a11836  Made assume_disc_small part of the key for the number field cache (as it used to be).

cab3fe1  added missing docstrings to number field factories

comment:21 Changed 5 years ago by
 Status changed from needs_work to needs_review
Pickling of old and new number fields should work now. I found these issues though.
Absolute number fields used to forget about their structure, this is fixed now (of course the structure can not be recovered for old pickles):
sage: K.<a> = QuadraticField(2) sage: L.<b> = K.change_names() sage: M=loads(dumps(L)) sage: M.structure() # old behaviour (Ring Coercion endomorphism of Number Field in b with defining polynomial x^2  2, Ring Coercion endomorphism of Number Field in b with defining polynomial x^2  2) sage: L.structure() # this is what M.structure() returns now (Isomorphism given by variable name change map: From: Number Field in b with defining polynomial x^2  2 To: Number Field in a with defining polynomial x^2  2, Isomorphism given by variable name change map: From: Number Field in a with defining polynomial x^2  2 To: Number Field in b with defining polynomial x^2  2)
Relative number fields also used to forget about their structure. Since I have not touched the pickling of relative number fields, I would rather put this into a separate ticket:
sage: sage: Z = var('Z') sage: sage: K.<w> = NumberField(Z^3 + Z + 1) sage: sage: L.<z> = K.extension(Z^3 + 2) sage: sage: M.<u,v> = L.change_names() sage: sage: M.structure() (Isomorphism given by variable name change map: From: Number Field in u with defining polynomial x^3 + 2 over its base field To: Number Field in z with defining polynomial Z^3 + 2 over its base field, Isomorphism given by variable name change map: From: Number Field in z with defining polynomial Z^3 + 2 over its base field To: Number Field in u with defining polynomial x^3 + 2 over its base field) sage: sage: M = loads(dumps(M)) sage: sage: M.structure() (Ring Coercion endomorphism of Number Field in u with defining polynomial x^3 + 2 over its base field, Ring Coercion endomorphism of Number Field in u with defining polynomial x^3 + 2 over its base field)
comment:22 Changed 5 years ago by
 Status changed from needs_review to needs_work
comment:23 Changed 5 years ago by
 Commit changed from cab3fe1eb4c425f0028b221494f95a03199f2936 to 70702aa690a31cc36b9febe36462c67ebd57dcee
Branch pushed to git repo; I updated commit sha1. New commits:
71532de  Hash function for absolute number fields.

af58e0c  Fixed unpickling of absolute number fields

7bb5b88  Added a test case to verify that pickling preserves the structure of a relative number field.

622b238  Pickling is broken for relative number fields. The structure of a number field is lost. Added a doctest to document this behaviour.

9e8de67  Relative and absolute number fields defined by the same (absolute) polynomial should not be equal.

0581f37  A number field's structure() may define conversion maps between number fields

baeeb5c  fixed a pickling test case

70702aa  Fixed a hash doctest.

comment:24 Changed 5 years ago by
 Modified changed from 04/09/14 14:52:46 to 04/09/14 14:52:46
 Status changed from needs_work to needs_review
comment:25 followup: ↓ 26 Changed 5 years ago by
I think it is indeed important that if one considers fields equipped with a structure
(in the sense of this ticket), then (1) the structure
should be fixed once and for all at the time of construction, and (2) no two fields with a different structure
should be considered as equal. Given (1), it would be good to to have a clear picture of what sort of things one can specify as a structure
, and I would be interested in finding out how flexible this concept of structure
is.
For example, it would be nice to be able to equip a number field K with an additional "piece of structure" z such that there is a category (in the mathematical sense) in which the objects are such pairs (K, z) and in which there exists at most one morphism between any two objects. Then (a suitable finite representation of) z could be taken as an especially nice type of structure
in the above sense.
One particular "piece of structure" that comes to mind is an embedding z of K into a fixed algebraic closure of Q. In Sage, this means an embedding into QQbar
. Since QQbar
encodes field elements (roughly speaking) by a polynomial and a complex root, represented by a sufficiently small complex region to determine the root uniquely, specifying z really means giving a small complex region representing a root of the defining polynomial of K.
Now it is already the case that one can specify an embedding
parameter when creating a number field. Hence (finally) the following question: does the concept of a structure
in the sense of this ticket allow the existing embedding
parameter to be implemented as a special case of a structure
?
comment:26 in reply to: ↑ 25 ; followup: ↓ 27 Changed 5 years ago by
Replying to pbruin:
Now it is already the case that one can specify an
embedding
parameter when creating a number field. Hence (finally) the following question: does the concept of astructure
in the sense of this ticket allow the existingembedding
parameter to be implemented as a special case of astructure
?
Not really. One difference is that two fields with different embedding
are not considered equal, but two fields with different structure
are. I think this makes sense since structure
currently tells you how a field has been created (e.g. as the absolute field of a relative field.) However, treating two number fields with different complex embedding as being the same would most probably lead to nasty bugs.
There might be a more general concept that structure
and embedding
are special cases of but I would not try to abuse one of them for this (right now). There is probably too much code that expects these two attributes to have a specific format to make such a change. It could be the content of a followup ticket.
comment:27 in reply to: ↑ 26 ; followup: ↓ 28 Changed 5 years ago by
Replying to saraedum:
Not really. One difference is that two fields with different
embedding
are not considered equal, but two fields with differentstructure
are.
OK, I misunderstood the discussion on this ticket so far (I did not yet look at the code carefully); I somehow concluded that your implementation answered Simon's question from comment:13 with "yes". So do I understand correctly that two number fields are explicitly allowed to be equal but not identical? Is this really desirable? From the manual page on unique representation:
"Instances of a class have a unique representation behavior when instances evaluate equal if and only if they are identical (i.e., share the same memory representation), if and only if they were created using equal arguments. [...] This behaviour is typically desirable for parents and categories."
comment:28 in reply to: ↑ 27 ; followup: ↓ 29 Changed 5 years ago by
Replying to pbruin:
OK, I misunderstood the discussion on this ticket so far (I did not yet look at the code carefully); I somehow concluded that your implementation answered Simon's question from comment:13 with "yes".
I agree that it makes sense that two number fields are different if they have a different structure. I had a feeling that this would break too much existing code, though. I think it is a natural first step to rewrite number fields to use a factory and make them unique parents (this ticket).
I could certainly imagine helping on a followup ticket which tries to make ==
and is
the same for number fields.
comment:29 in reply to: ↑ 28 ; followup: ↓ 30 Changed 5 years ago by
Replying to saraedum:
I agree that it makes sense that two number fields are different if they have a different structure. I had a feeling that this would break too much existing code, though.
Hmm, I wonder if one could test easily if this would indeed be a problem (within the Sage library, say).
I think it is a natural first step to rewrite number fields to use a factory and make them unique parents (this ticket).
Doesn't "unique parents" mean precisely that parents are equal if and only if they are identical (see the third paragraph of this page)?
(I'm only starting to understand the finer points of all this; I thought understanding the situation for number fields would be a good first step towards the similar problem for elliptic curves in #11474.)
comment:30 in reply to: ↑ 29 ; followup: ↓ 32 Changed 5 years ago by
Replying to pbruin:
Replying to saraedum:
I agree that it makes sense that two number fields are different if they have a different structure. I had a feeling that this would break too much existing code, though.
Hmm, I wonder if one could test easily if this would indeed be a problem (within the Sage library, say).
I think it is a natural first step to rewrite number fields to use a factory and make them unique parents (this ticket).
Doesn't "unique parents" mean precisely that parents are equal if and only if they are identical (see the third paragraph of this page)?
Ok. Maybe I am using the wrong vocabulary here. I meant, "uniue" as in "two fields generated from the same arguments are identical", not as in "unique representation".
comment:31 Changed 5 years ago by
I see what you mean. Maybe one could try to formalise the notion of "unique parents" more precisely as follows.
We have some Python callable NumberField()
that takes as input some key (defining datum) d
and outputs some Python object K
depending on d
and representing a number field. This NumberField()
uses (implicitly) some algorithm, say same(d, e)
, that given two keys d
and e
decides whether d
and e
define the same number field. (The meaning of "the same" is a bit vague; one could either use a mathematical definition involving extra structure on the number field, or one could take "the same" to mean by definition that same(d, e)
returns True.)
Of course, same
should behave like an equivalence relation (same(d, d) == True
, same(d, e) == same(e, d)
, and transitivity holds). I think that "K
and L
were created using the same arguments" should be interpreted as K
and L
being names assigned to the objects returned by NumberField(d)
and NumberField(e)
for some d
and e
for which same(d, e)
is True. I'm not sure if we have to assume any implication between same(d, e)
and d == e
; it is possible that same(d, e)
is actually implemented as d == e
.
Now consider the following booleanvalued statements about possible keys d
and e
:
d is e
same(d, e)
NumberField(d) is NumberField(e)
NumberField(d) == NumberField(e)
Clearly, the implications 1 => 2 and 3 => 4 are automatic, and 2 => 4 probably holds already. It seems that saying "number fields are unique parents" is the same as saying that the implementation of NumberField()
ensures that the implications 2 => 3 (hence 2 => 4) and 4 => 3 both hold, and maybe even 3 => 2.
If I understand correctly, this ticket makes sure that 2 => 3 holds, but not necessarily 4 => 3. From that perspective it makes sense to have a separate ticket to implement the "other half" of the unique parents property.
comment:32 in reply to: ↑ 30 Changed 5 years ago by
Replying to saraedum:
Ok. Maybe I am using the wrong vocabulary here. I meant, "uniue" as in "two fields generated from the same arguments are identical", not as in "unique representation".
If you want two fields generated from the same arguments to be identical, then you can either use CachedRepresentation
or UniqueFactory
.
If you additionally want unique parent behaviour (which means you cannot have two distinct instance of your class that evaluate equal), you can use UniqueRepresentation
, or you can add WithEqualityById
(it could be that I wrongly remember the name, but it is something similar to this) as a base class.
comment:33 followup: ↓ 35 Changed 5 years ago by
With your changes, Sage doesn't complain anymore if the user does not specify the name of the generator, but silently names it "a":
sage: K = NumberField(x^2 + 1); K Number Field in a with defining polynomial x^2 + 1
I don't like this; since the name is part of the defining data, I think we should insist on the user specifying the name. If you think this should be changed, I think it is better to create a new ticket so this interface issue can be discussed separately from the technical changes made in this ticket.
comment:34 Changed 5 years ago by
 Commit changed from 70702aa690a31cc36b9febe36462c67ebd57dcee to 8e968244cb356aaa863eb6a3caff46c74d48f182
comment:35 in reply to: ↑ 33 Changed 5 years ago by
Replying to pbruin:
With your changes, Sage doesn't complain anymore if the user does not specify the name of the generator, but silently names it "a":
You are right. I just implemented what the docstring used to say. I fixed the implementation and the docstring.
comment:36 Changed 5 years ago by
 Branch changed from u/saraedum/ticket/11670 to u/pbruin/11670NumberField_unique
 Commit changed from 8e968244cb356aaa863eb6a3caff46c74d48f182 to 9b4deffd7823cc4e71c6122b99615d765bd9d87f
 Reviewers changed from Simon King to Simon King, Peter Bruin
Thanks. I made a reviewer patch to fix some typos, formatting and Python 3 compatibility things; I changed the error message for name=None
back to what it was to fix one failing doctest.
I would be happy give this a positive review, but I think it is better if Simon or someone else with expertise in this area takes a quick look at it as well.
comment:37 Changed 5 years ago by
 Status changed from needs_review to needs_work
 Work issues set to merge conflicts with 6.2β8
comment:38 Changed 5 years ago by
 Commit changed from 9b4deffd7823cc4e71c6122b99615d765bd9d87f to 8b06ff7d7fef13bd3746a1524bc5744242f1a75e
Branch pushed to git repo; I updated commit sha1. New commits:
8b06ff7  Merge branch 'develop' into ticket/11670NumberField_unique

comment:39 Changed 5 years ago by
 Status changed from needs_work to needs_review
 Work issues merge conflicts with 6.2β8 deleted
New commits:
8b06ff7  Merge branch 'develop' into ticket/11670NumberField_unique

comment:40 Changed 5 years ago by
 Status changed from needs_review to positive_review
OK, let's not leave this to bitrot. As an additional test, I checked that #11669 (which depends on this ticket) still works correctly, and it does.
comment:41 Changed 5 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:42 Changed 5 years ago by
 Branch changed from u/pbruin/11670NumberField_unique to 8b06ff7d7fef13bd3746a1524bc5744242f1a75e
 Resolution set to fixed
 Status changed from positive_review to closed
When working on this ticket, I also found a potentially serious bug, which is that the parameters
assume_disc_small
andmaximize_at_primes
of a number field were both lost upon pickling and unpickling. This ticket fixes that. We used to have this bug:Attached patch fixes that.