Opened 6 years ago
Closed 6 years ago
#17427 closed defect (fixed)
x==y while hash(x)!=hash(y) with SchemeMorphism_point_projective_field
Reported by:  ncohen  Owned by:  bhutz 

Priority:  major  Milestone:  sage6.5 
Component:  algebraic geometry  Keywords:  
Cc:  vbraun, bhutz  Merged in:  
Authors:  Ben Hutz  Reviewers:  Joao Alberto de Faria 
Report Upstream:  N/A  Work issues:  
Branch:  067e325 (Commits)  Commit:  067e3256e38168f98b772a7308b79021e0f8dfd8 
Dependencies:  #17433  Stopgaps: 
Description
As reported on sagedevel [1], but I do not know these objects at all.
There is also some code in the report to build such objects.
Nathann
[1] https://groups.google.com/forum/#!topic/sagedevel/xaWqj79PY
Change History (21)
comment:1 Changed 6 years ago by
 Summary changed from x==y while hash(x)!=hash(y) with DIfferent SchemeMorphism_point_projective_field to x==y while hash(x)!=hash(y) with SchemeMorphism_point_projective_field
comment:2 Changed 6 years ago by
 Cc vbraun added
comment:3 followup: ↓ 4 Changed 6 years ago by
 Cc bhutz added
comment:4 in reply to: ↑ 3 Changed 6 years ago by
Replying to bhutz:
Although, I'm not sure why this is bad.
It's against contract. It will make behaviour unpredictable if you use these objects as keys in a dictionary. Python will initially select a place in the dictionary based on some bits in the hash value, but if that spot is taken, python will test if the keys agree by testing for equality. So whether
{P(1,1):1, P(n,n):2}
leads to a dictionary with one or two elements will depend on the value of n. It's really hard to force hash collisions in python so the behaviour is very rare, which makes it even more dangerous.
Withouta==b
implies hash(a)==hash(b)
a hash is useless (it's the only property a hash MUST have)
comment:5 followup: ↓ 6 Changed 6 years ago by
Notice that the sage developers guide says the following about hash:
'“The only required property is that objects which compare equal have the same hash value.” This is an assumption made by the Python language, which in Sage we simply cannot make!'
Now, I'm not saying that we don't want to do everything reasonable we can to make the implication work, I have to ask if maybe this is one of those cases where it is not reasonable. Sure, the ZZ example was trivial, but for rings without GCDs, there are less trivial examples:
R.<x>=PolynomialRing(QQ) K.<w>=NumberField(x^2+3) O=K.maximal_order() P.<x,y>=ProjectiveSpace(O,1) Q1=P([1+w,2]) Q2=P([2,1w]) Q1==Q2
Is there a way to assign Q1 and Q2 the same hash value without searching through the list of previously made hash values for an == and then assigning the Q2 hash value to that value?
comment:6 in reply to: ↑ 5 Changed 6 years ago by
Replying to bhutz:
Notice that the sage developers guide says the following about hash:
'“The only required property is that objects which compare equal have the same hash value.” This is an assumption made by the Python language, which in Sage we simply cannot make!'
That's just because the use of noninjective coercion maps means that equality testing in sage isn't transitive when allowing elements from multiple parents:
sage: 1 == GF(5)(1) True sage: GF(5)(1) == 6 True sage: 1 == 6 False
which indeed means that you shouldn't have a dictionary where you use both integers and finite field elements as keys. But at least there's an easy rule there: If you use sage objects as keys in a dict, make sure they all have the same parent, or make sure that you really know what you're doing.
If you can't even have a hash that works properly between elements of the same parent then you shouldn't make those elements hashable. The hash will be useless and it's misleading to have. This happened to padics, where ==
was chosen to be too permissive to be transitive (they were considered equal if their associated disks had nonempty intersection), and indeed they are slated to lose their hash (see #11895)
sage: 1+O(k(9)) == 1+O(k(3)) True sage: 1+O(k(3)) == 4+O(k(9)) True sage: 1+O(k(9)) == 4+O(k(9)) False
(note it's the same issue as with ZZ and finite fields, but now inside the same parent)
As long as you're taking projective space over integral domains with a constructible field of fractions, you can just normalize a nonzero coordinate to 1 and hash that (provided the implementation of the field of fractions has an appropriate hash (fields that are a finite extension of a FoF of a PID should be OK, if implemented correctly, and Noether Normalization gives us that basically all fields we'll meet in sage are of that type)). Yes, hashing is hard :).
If you want to take projective space over nonintegral domains, I think you'll have bigger problems elsewhere.
comment:7 followup: ↓ 8 Changed 6 years ago by
Yes, I agree hashing over fields can just normalize the point before hashing. For rings with 'nice' field of fractions, it could be coerced to the FF, normalized, and then hashed. Over general rings (such as padics), it sounds like you are proposing making projective points unhashable (as is happening to padic numbers) instead of having a hash that doesn't behave like a hash.
I'd have to experiment a little with that setup to see if it causes any additional issues. For example the points defined over the ring and the fraction field with the same coordinates would then hash to the same value. At the moment those points would be != since there is not yet a coercion model for projective points and morphisms.
Overall, it seems like an ok proposal to me.
comment:8 in reply to: ↑ 7 Changed 6 years ago by
Replying to bhutz:
I'd have to experiment a little with that setup to see if it causes any additional issues. For example the points defined over the ring and the fraction field with the same coordinates would then hash to the same value. At the moment those points would be != since there is not yet a coercion model for projective points and morphisms.
Equality of hash values is never a correctness problem, only a source of performance problems. The constant function would be a legitimate hash function.
comment:9 Changed 6 years ago by
 Branch set to u/bhutz/ticket/17427
 Created changed from 12/01/14 18:23:54 to 12/01/14 18:23:54
 Modified changed from 12/02/14 20:23:24 to 12/02/14 20:23:24
comment:10 Changed 6 years ago by
 Commit set to 0eebe9015c55f3f5a349a1605e3cafa070f17014
 Component changed from PLEASE CHANGE to algebraic geometry
 Owner changed from (none) to bhutz
Well here is an initial version. As discussed, for rings it tries to normalize in the fraction. If its not an integral domain it returns a constant value (hash of the parent). For fields, it ensures that the point is normalized first. Please comment on possible issues or improvements.
However, there is a doctest in elliptic curves that fails with this. My initial diagnosis is that it is uncovering a problem related to points over quotient rings. I'll fix that issue in ticket #17433 as it is a related problem.
New commits:
0eebe90  17427: improve hash for projective points

comment:11 Changed 6 years ago by
 Commit changed from 0eebe9015c55f3f5a349a1605e3cafa070f17014 to 4d6c87e5d2ba91cb16156f0dfb266180e0af9e2f
Branch pushed to git repo; I updated commit sha1. New commits:
4d6c87e  17427: adjusted formatting and added comments

comment:12 Changed 6 years ago by
 Dependencies set to #17433
 Status changed from new to needs_review
There is a doctest in elliptic curves that fails until #17433 is fixed.
comment:13 Changed 6 years ago by
 Reviewers set to Joao Alberto de Faria
 Status changed from needs_review to needs_work
Looks good to me, setting to positive review
comment:14 Changed 6 years ago by
 Status changed from needs_work to positive_review
comment:15 Changed 6 years ago by
 Status changed from positive_review to needs_work
Author name missing
comment:16 Changed 6 years ago by
 Status changed from needs_work to positive_review
comment:17 Changed 6 years ago by
 Status changed from positive_review to needs_work
On 32bit:
sage t long src/sage/schemes/projective/projective_point.py ********************************************************************** File "src/sage/schemes/projective/projective_point.py", line 374, in sage.schemes.projective.projective_point.SchemeMorphism_point_projective_ring.__hash__ Failed example: hash(P([1,1])) Expected nothing Got: 1265304440 ********************************************************************** File "src/sage/schemes/projective/projective_point.py", line 376, in sage.schemes.projective.projective_point.SchemeMorphism_point_projective_ring.__hash__ Failed example: hash(P.point([2,2], False)) Expected nothing Got: 1265304440 ********************************************************************** File "src/sage/schemes/projective/projective_point.py", line 385, in sage.schemes.projective.projective_point.SchemeMorphism_point_projective_ring.__hash__ Failed example: hash(P([1+w, 2])) Expected nothing Got: 609701421 ********************************************************************** File "src/sage/schemes/projective/projective_point.py", line 387, in sage.schemes.projective.projective_point.SchemeMorphism_point_projective_ring.__hash__ Failed example: hash(P([2, 1w])) Expected nothing Got: 609701421 ********************************************************************** File "src/sage/schemes/projective/projective_point.py", line 393, in sage.schemes.projective.projective_point.SchemeMorphism_point_projective_ring.__hash__ Failed example: hash(P([2,5])) Expected nothing Got: 479010389 ********************************************************************** File "src/sage/schemes/projective/projective_point.py", line 1140, in sage.schemes.projective.projective_point.SchemeMorphism_point_projective_field.__hash__ Failed example: hash(P([1/2, 1])) Expected nothing Got: 1741117121 ********************************************************************** File "src/sage/schemes/projective/projective_point.py", line 1142, in sage.schemes.projective.projective_point.SchemeMorphism_point_projective_field.__hash__ Failed example: hash(P.point([1, 2], False)) Expected nothing Got: 1741117121 ********************************************************************** 2 items had failures: 2 of 4 in sage.schemes.projective.projective_point.SchemeMorphism_point_projective_field.__hash__ 5 of 12 in sage.schemes.projective.projective_point.SchemeMorphism_point_projective_ring.__hash__ [302 tests, 7 failures, 0.60 s]
comment:18 Changed 6 years ago by
 Commit changed from 4d6c87e5d2ba91cb16156f0dfb266180e0af9e2f to 067e3256e38168f98b772a7308b79021e0f8dfd8
Branch pushed to git repo; I updated commit sha1. New commits:
067e325  17427: fixed 32bit doctests

comment:19 Changed 6 years ago by
 Status changed from needs_work to needs_review
comment:20 Changed 6 years ago by
 Status changed from needs_review to positive_review
Everything looks good on my end, setting to positive review
comment:21 Changed 6 years ago by
 Branch changed from u/bhutz/ticket/17427 to 067e3256e38168f98b772a7308b79021e0f8dfd8
 Resolution set to fixed
 Status changed from positive_review to closed
These are actually quite easy to build
Although, I'm not sure why this is bad.