Sage: Ticket #17427: x==y while hash(x)!=hash(y) with SchemeMorphism_point_projective_field
https://trac.sagemath.org/ticket/17427
<p>
As reported on sage-devel [1], but I do not know these objects at all.
</p>
<p>
There is also some code in the report to build such objects.
</p>
<p>
Nathann
</p>
<p>
[1] <a class="ext-link" href="https://groups.google.com/forum/#!topic/sage-devel/xaW-qj-79PY"><span class="icon"></span>https://groups.google.com/forum/#!topic/sage-devel/xaW-qj-79PY</a>
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/17427
Trac 1.1.6ncohenMon, 01 Dec 2014 18:24:31 GMTsummary changed
https://trac.sagemath.org/ticket/17427#comment:1
https://trac.sagemath.org/ticket/17427#comment:1
<ul>
<li><strong>summary</strong>
changed from <em>x==y while hash(x)!=hash(y) with DIfferent SchemeMorphism_point_projective_field</em> to <em>x==y while hash(x)!=hash(y) with SchemeMorphism_point_projective_field</em>
</li>
</ul>
TicketncohenMon, 01 Dec 2014 18:27:17 GMTcc set
https://trac.sagemath.org/ticket/17427#comment:2
https://trac.sagemath.org/ticket/17427#comment:2
<ul>
<li><strong>cc</strong>
<em>vbraun</em> added
</li>
</ul>
TicketbhutzTue, 02 Dec 2014 13:33:54 GMTcc changed
https://trac.sagemath.org/ticket/17427#comment:3
https://trac.sagemath.org/ticket/17427#comment:3
<ul>
<li><strong>cc</strong>
<em>bhutz</em> added
</li>
</ul>
<p>
These are actually quite easy to build
</p>
<pre class="wiki">P.<x,y>=ProjectiveSpace(ZZ,1)
p1=P(1,1)
p2=P(2,2)
p1==p2, hash(p1)==hash(p2)
</pre><p>
Although, I'm not sure why this is bad.
</p>
TicketnbruinTue, 02 Dec 2014 16:24:52 GMT
https://trac.sagemath.org/ticket/17427#comment:4
https://trac.sagemath.org/ticket/17427#comment:4
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17427#comment:3" title="Comment 3">bhutz</a>:
</p>
<blockquote class="citation">
<p>
Although, I'm not sure why this is bad.
</p>
</blockquote>
<p>
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>
<pre class="wiki">{P(1,1):1, P(n,n):2}
</pre><p>
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.
</p>
<p>
Without<code>a==b</code> implies <code>hash(a)==hash(b)</code> a hash is useless (it's the only property a hash MUST have)
</p>
TicketbhutzTue, 02 Dec 2014 17:56:48 GMT
https://trac.sagemath.org/ticket/17427#comment:5
https://trac.sagemath.org/ticket/17427#comment:5
<p>
Notice that the sage developers guide says the following about hash:
</p>
<p>
'“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!'
</p>
<p>
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:
</p>
<pre class="wiki">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
</pre><p>
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?
</p>
TicketnbruinTue, 02 Dec 2014 19:13:26 GMT
https://trac.sagemath.org/ticket/17427#comment:6
https://trac.sagemath.org/ticket/17427#comment:6
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17427#comment:5" title="Comment 5">bhutz</a>:
</p>
<blockquote class="citation">
<p>
Notice that the sage developers guide says the following about hash:
</p>
<p>
'“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!'
</p>
</blockquote>
<p>
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:
</p>
<pre class="wiki">sage: 1 == GF(5)(1)
True
sage: GF(5)(1) == 6
True
sage: 1 == 6
False
</pre><p>
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.
</p>
<p>
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 <code>==</code> 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 <a class="closed ticket" href="https://trac.sagemath.org/ticket/11895" title="defect: Make p-adic numbers unhashable (closed: invalid)">#11895</a>)
</p>
<pre class="wiki">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
</pre><p>
(note it's the same issue as with ZZ and finite fields, but now inside the same parent)
</p>
<p>
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 :-).
</p>
<p>
If you want to take projective space over non-integral domains, I think you'll have bigger problems elsewhere.
</p>
TicketbhutzTue, 02 Dec 2014 19:32:54 GMT
https://trac.sagemath.org/ticket/17427#comment:7
https://trac.sagemath.org/ticket/17427#comment:7
<p>
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.
</p>
<p>
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.
</p>
<p>
Overall, it seems like an ok proposal to me.
</p>
TicketnbruinTue, 02 Dec 2014 20:23:24 GMT
https://trac.sagemath.org/ticket/17427#comment:8
https://trac.sagemath.org/ticket/17427#comment:8
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17427#comment:7" title="Comment 7">bhutz</a>:
</p>
<blockquote class="citation">
<p>
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.
</p>
</blockquote>
<p>
Equality of hash values is never a correctness problem, only a source of performance problems. The constant function would be a legitimate hash function.
</p>
TicketbhutzFri, 05 Dec 2014 16:00:11 GMTchangetime, time changed; branch set
https://trac.sagemath.org/ticket/17427#comment:9
https://trac.sagemath.org/ticket/17427#comment:9
<ul>
<li><strong>changetime</strong>
changed from <em>12/02/14 20:23:24</em> to <em>12/02/14 20:23:24</em>
</li>
<li><strong>branch</strong>
set to <em>u/bhutz/ticket/17427</em>
</li>
<li><strong>time</strong>
changed from <em>12/01/14 18:23:54</em> to <em>12/01/14 18:23:54</em>
</li>
</ul>
TicketbhutzFri, 05 Dec 2014 16:05:12 GMTcomponent changed; owner, commit set
https://trac.sagemath.org/ticket/17427#comment:10
https://trac.sagemath.org/ticket/17427#comment:10
<ul>
<li><strong>owner</strong>
changed from <em>(none)</em> to <em>bhutz</em>
</li>
<li><strong>commit</strong>
set to <em>0eebe9015c55f3f5a349a1605e3cafa070f17014</em>
</li>
<li><strong>component</strong>
changed from <em>PLEASE CHANGE</em> to <em>algebraic geometry</em>
</li>
</ul>
<p>
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.
</p>
<p>
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 <a class="closed ticket" href="https://trac.sagemath.org/ticket/17433" title="defect: projective point equality fails for quotient base rings (closed: fixed)">#17433</a> as it is a related problem.
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=0eebe9015c55f3f5a349a1605e3cafa070f17014"><span class="icon"></span>0eebe90</a></td><td><code>17427: improve hash for projective points</code>
</td></tr></table>
TicketgitMon, 08 Dec 2014 18:55:17 GMTcommit changed
https://trac.sagemath.org/ticket/17427#comment:11
https://trac.sagemath.org/ticket/17427#comment:11
<ul>
<li><strong>commit</strong>
changed from <em>0eebe9015c55f3f5a349a1605e3cafa070f17014</em> to <em>4d6c87e5d2ba91cb16156f0dfb266180e0af9e2f</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=4d6c87e5d2ba91cb16156f0dfb266180e0af9e2f"><span class="icon"></span>4d6c87e</a></td><td><code>17427: adjusted formatting and added comments</code>
</td></tr></table>
TicketbhutzMon, 08 Dec 2014 18:57:32 GMTstatus changed; dependencies set
https://trac.sagemath.org/ticket/17427#comment:12
https://trac.sagemath.org/ticket/17427#comment:12
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>dependencies</strong>
set to <em>#17433</em>
</li>
</ul>
<p>
There is a doctest in elliptic curves that fails until <a class="closed ticket" href="https://trac.sagemath.org/ticket/17433" title="defect: projective point equality fails for quotient base rings (closed: fixed)">#17433</a> is fixed.
</p>
TicketjdefariaFri, 12 Dec 2014 13:32:17 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/17427#comment:13
https://trac.sagemath.org/ticket/17427#comment:13
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>reviewer</strong>
set to <em>Joao Alberto de Faria</em>
</li>
</ul>
<p>
Looks good to me, setting to positive review
</p>
TicketjdefariaFri, 12 Dec 2014 13:32:40 GMTstatus changed
https://trac.sagemath.org/ticket/17427#comment:14
https://trac.sagemath.org/ticket/17427#comment:14
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>positive_review</em>
</li>
</ul>
TicketvbraunFri, 02 Jan 2015 15:48:04 GMTstatus changed
https://trac.sagemath.org/ticket/17427#comment:15
https://trac.sagemath.org/ticket/17427#comment:15
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Author name missing
</p>
TicketbhutzFri, 02 Jan 2015 16:08:40 GMTstatus changed; author set
https://trac.sagemath.org/ticket/17427#comment:16
https://trac.sagemath.org/ticket/17427#comment:16
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>positive_review</em>
</li>
<li><strong>author</strong>
set to <em>Ben Hutz</em>
</li>
</ul>
TicketvbraunSun, 04 Jan 2015 10:22:51 GMTstatus changed
https://trac.sagemath.org/ticket/17427#comment:17
https://trac.sagemath.org/ticket/17427#comment:17
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
On 32-bit:
</p>
<pre class="wiki">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]
</pre>
TicketgitSun, 04 Jan 2015 15:22:36 GMTcommit changed
https://trac.sagemath.org/ticket/17427#comment:18
https://trac.sagemath.org/ticket/17427#comment:18
<ul>
<li><strong>commit</strong>
changed from <em>4d6c87e5d2ba91cb16156f0dfb266180e0af9e2f</em> to <em>067e3256e38168f98b772a7308b79021e0f8dfd8</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=067e3256e38168f98b772a7308b79021e0f8dfd8"><span class="icon"></span>067e325</a></td><td><code>17427: fixed 32-bit doctests</code>
</td></tr></table>
TicketbhutzSun, 04 Jan 2015 15:23:28 GMTstatus changed
https://trac.sagemath.org/ticket/17427#comment:19
https://trac.sagemath.org/ticket/17427#comment:19
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
TicketjdefariaFri, 16 Jan 2015 18:09:15 GMTstatus changed
https://trac.sagemath.org/ticket/17427#comment:20
https://trac.sagemath.org/ticket/17427#comment:20
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
Everything looks good on my end, setting to positive review
</p>
TicketvbraunFri, 23 Jan 2015 23:40:43 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/17427#comment:21
https://trac.sagemath.org/ticket/17427#comment:21
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>u/bhutz/ticket/17427</em> to <em>067e3256e38168f98b772a7308b79021e0f8dfd8</em>
</li>
</ul>
Ticket