Dictionary substitutions don't work over Frac(QQbar[x,y])

[gh-BrentBaccala]

sage: R.<x,y> = QQbar[]
sage: (1/y).subs({y: 2})
1/y

The problem is that the hashes don't match up between the polynomial ring and its fraction field:

sage: hash(y) == hash(Frac(R)(y))
False

From source:src/sage/rings/fraction_field_element.pyx@8.1:316-318

This function hashes in a special way to ensure that generators of a ring R and generators of a fraction field of R have the same hash. This enables them to be used as keys interchangeably in a dictionary (since == will claim them equal). This is particularly useful for methods like subs on ParentWithGens if you are passing a dictionary of substitutions.

The reason that it's not working right is that the hashing code in fraction_field_element.pyx assumes that hash(1) == 1, and that's not true in QQbar:

sage: hash(QQbar(1))
-3730706066237751940

[gh-BrentBaccala]

New commits:

​974186d

Trac #25199: dictionary substitutions over Frac(QQBar[x,y])

[gh-BrentBaccala]

The patch changes QQbar's hash function so that rational numbers always hash the same way.

[dkrenn]

Replying to gh-BrentBaccala:

The reason that it's not working right is that the hashing code in fraction_field_element.pyx assumes that hash(1) == 1

This sounds strange; why should any code assume that hash(1) == 1?

[tscrim]

I think what is being referred to is substitution does something like a comparison by dicts:

sage: d1 = {ZZ(1): 1}
sage: d2 = {QQbar(1): 1}
sage: d1 == d2
False
sage: d3 = {QQ(1): 1}
sage: d1 == d3
True

The d1 == d2 uses a hash comparison before an equality comparison:

sage: hash(QQbar(1)) == hash(ZZ(1))
False
sage: QQbar(1) == ZZ(1)
True

[gh-BrentBaccala]

Didn't think that patch would break so many tests...

This sounds strange; why should any code assume that hash(1) == 1?

Yet the fraction field hashing code does make that assumption. If we're going to keep it that way, perhaps this assumption needs to be more clearly documented. QQbar might not be the only place that has problems with this.

[gh-BrentBaccala]

The problem with the patch that I submitted yesterday is that it can cause the hash value to change when an element is exactified, and there seems to be another assumption that an element's hash value never changes. Fixing this so that hash(one) == hash(1), no matter how 'one' was constructed, would require exactifying 'one' whenever we hash it. The most consistent action would be to exactify anything whenever we hash it, to see if it's rational. The current QQbar hash code goes out of its way to avoid this, though the comments state:

All of this effort to avoid exact computation is probably wasted, anyway... in almost all uses of hash codes, if the hash codes match, the next step is to compare for equality; and comparing for equality often requires exact computation

So we could drop this logic, and exactify every time we hash.

I'm also thinking of another way to fix this - patch the fraction field code to check the denominator with is_one, rather than just checking to see if the denominator hashes to 1. Then we no longer assume that hash(1) == 1, but is_one() might be slower than hash().

Comments?

[git]

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

​b542e0b	Revert "Trac #25199: dictionary substitutions over Frac(QQBar[x,y])"
​02219a5	Trac #25199: fraction field hash code no longer assumes hash(1)==1
​237ef20	Merge 'origin/develop' (8.2.rc3) into u/gh-BrentBaccala/25199

[gh-BrentBaccala]

Fixed by #16268

[dkrenn]

Replying to gh-BrentBaccala:

Fixed by #16268

Ok. Is there a doctest covering the issue of this ticket?

[gh-BrentBaccala]

Replying to dkrenn:

Ok. Is there a doctest covering the issue of this ticket?

There's an existing doctest in FractionFieldElement's __hash__ method (lines 360-364 in Sage 8.4) that checks similar behavior:

sage: R.<x,y,z>=QQ[]
sage: hash(R.0)==hash(FractionField(R).0)
True
sage: ((x+1)/(x^2+1)).subs({x:1})
1

However, this test is over QQ, not QQbar, and I've verified that it passed on Sage 7.5.1, while the test in the description of this ticket did not.

So, I suggest adding an additional test over QQbar below the existing one in FractionFieldElement __hash__.

I switched this ticket to a new branch with just that doctest on it.

[dkrenn]

LGTM, thanks.

[embray]

This tickets were closed as fixed after the Sage 8.5 release.