x==y while hash(x)!=hash(y) with SchemeMorphism_point_projective_field

[ncohen]

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

[bhutz]

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.

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

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

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

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

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

[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

[git]

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

​4d6c87e

17427: adjusted formatting and added comments

[bhutz]

There is a doctest in elliptic curves that fails until #17433 is fixed.

[jdefaria]

Looks good to me, setting to positive review

[vbraun]

Author name missing

[vbraun]

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]

[git]

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

​067e325

17427: fixed 32-bit doctests

[jdefaria]

Everything looks good on my end, setting to positive review