Opened 3 years ago

Closed 3 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: sage-6.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 sage-devel [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/sage-devel/xaW-qj-79PY

Change History (21)

comment:1 Changed 3 years ago by ncohen

  • 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 3 years ago by ncohen

  • Cc vbraun added

comment:3 follow-up: Changed 3 years ago by bhutz

  • Cc bhutz added

These are actually quite easy to build

P.<x,y>=ProjectiveSpace(ZZ,1)
p1=P(1,1)
p2=P(2,2)
p1==p2, hash(p1)==hash(p2)

Although, I'm not sure why this is bad.

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

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 follow-up: Changed 3 years ago by 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!'

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,1-w])
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 3 years ago by nbruin

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 non-injective 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 p-adics, where == was chosen to be too permissive to be transitive (they were considered equal if their associated disks had non-empty 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 non-zero 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 non-integral domains, I think you'll have bigger problems elsewhere.

comment:7 follow-up: Changed 3 years ago by bhutz

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 p-adics), it sounds like you are proposing making projective points unhashable (as is happening to p-adic numbers) instead of having a hash that doesn't behave like a hash.

I'd have to experiment a little with that set-up 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 3 years ago by nbruin

Replying to bhutz:

I'd have to experiment a little with that set-up 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 3 years ago by bhutz

  • 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 3 years ago by bhutz

  • 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:

0eebe9017427: improve hash for projective points

comment:11 Changed 3 years ago by git

  • Commit changed from 0eebe9015c55f3f5a349a1605e3cafa070f17014 to 4d6c87e5d2ba91cb16156f0dfb266180e0af9e2f

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

4d6c87e17427: adjusted formatting and added comments

comment:12 Changed 3 years ago by bhutz

  • 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 3 years ago by jdefaria

  • 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 3 years ago by jdefaria

  • Status changed from needs_work to positive_review

comment:15 Changed 3 years ago by vbraun

  • Status changed from positive_review to needs_work

Author name missing

comment:16 Changed 3 years ago by bhutz

  • Authors set to Ben Hutz
  • Status changed from needs_work to positive_review

comment:17 Changed 3 years ago by vbraun

  • Status changed from positive_review to needs_work

On 32-bit:

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, 1-w]))
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 3 years ago by git

  • Commit changed from 4d6c87e5d2ba91cb16156f0dfb266180e0af9e2f to 067e3256e38168f98b772a7308b79021e0f8dfd8

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

067e32517427: fixed 32-bit doctests

comment:19 Changed 3 years ago by bhutz

  • Status changed from needs_work to needs_review

comment:20 Changed 3 years ago by jdefaria

  • Status changed from needs_review to positive_review

Everything looks good on my end, setting to positive review

comment:21 Changed 3 years ago by vbraun

  • Branch changed from u/bhutz/ticket/17427 to 067e3256e38168f98b772a7308b79021e0f8dfd8
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.