#25199 closed defect (fixed)
Dictionary substitutions don't work over Frac(QQbar[x,y])
Reported by: | gh-BrentBaccala | Owned by: | |
---|---|---|---|
Priority: | trivial | Milestone: | sage-8.6 |
Component: | algebra | Keywords: | QQbar, subs |
Cc: | vdelecroix, cheuberg, behackl, dkrenn | Merged in: | |
Authors: | Brent Baccala | Reviewers: | Daniel Krenn |
Report Upstream: | N/A | Work issues: | |
Branch: | c1a7508 (Commits, GitHub, GitLab) | Commit: | c1a7508722ac2197e6885e045146e5ee57eff700 |
Dependencies: | Stopgaps: |
Description
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 ofR
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
Change History (16)
comment:1 Changed 4 years ago by
- Branch set to u/gh-BrentBaccala/25199
- Commit set to 974186dc15698b1ea29b0f40df58265fe2885d9b
- Status changed from new to needs_review
comment:2 Changed 4 years ago by
The patch changes QQbar's hash function so that rational numbers always hash the same way.
comment:3 Changed 4 years ago by
- Cc vdelecroix cheuberg behackl dkrenn added
comment:4 in reply to: ↑ description Changed 4 years ago by
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
?
comment:5 Changed 4 years ago by
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
comment:6 Changed 4 years ago by
- Status changed from needs_review to needs_work
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.
comment:7 Changed 4 years ago by
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?
comment:8 Changed 4 years ago by
- Commit changed from 974186dc15698b1ea29b0f40df58265fe2885d9b to 237ef2016148512710db91cb13b4af683197e5b4
comment:9 Changed 4 years ago by
- Status changed from needs_work to needs_review
comment:10 follow-up: ↓ 11 Changed 4 years ago by
- Milestone changed from sage-8.2 to sage-duplicate/invalid/wontfix
Fixed by #16268
comment:11 in reply to: ↑ 10 ; follow-up: ↓ 13 Changed 4 years ago by
Replying to gh-BrentBaccala:
Fixed by #16268
Ok. Is there a doctest covering the issue of this ticket?
comment:12 Changed 4 years ago by
- Status changed from needs_review to needs_info
comment:13 in reply to: ↑ 11 Changed 4 years ago by
- Branch changed from u/gh-BrentBaccala/25199 to public/25199
- Commit changed from 237ef2016148512710db91cb13b4af683197e5b4 to c1a7508722ac2197e6885e045146e5ee57eff700
- Milestone changed from sage-duplicate/invalid/wontfix to sage-8.5
- Priority changed from major to trivial
- Status changed from needs_info to needs_review
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.
comment:14 Changed 4 years ago by
- Reviewers set to Daniel Krenn
- Status changed from needs_review to positive_review
LGTM, thanks.
comment:15 Changed 4 years ago by
- Branch changed from public/25199 to c1a7508722ac2197e6885e045146e5ee57eff700
- Resolution set to fixed
- Status changed from positive_review to closed
comment:16 Changed 4 years ago by
- Milestone changed from sage-8.5 to sage-8.6
This tickets were closed as fixed after the Sage 8.5 release.
New commits:
Trac #25199: dictionary substitutions over Frac(QQBar[x,y])