Opened 4 years ago

Closed 4 years ago

Last modified 4 years ago

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

Status badges

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

Change History (16)

comment:1 Changed 4 years ago by gh-BrentBaccala

  • Authors set to Brent Baccala
  • Branch set to u/gh-BrentBaccala/25199
  • Commit set to 974186dc15698b1ea29b0f40df58265fe2885d9b
  • Status changed from new to needs_review

New commits:

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

comment:2 Changed 4 years ago by gh-BrentBaccala

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

comment:3 Changed 4 years ago by tscrim

  • Cc vdelecroix cheuberg behackl dkrenn added

comment:4 in reply to: ↑ description Changed 4 years ago by 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?

comment:5 Changed 4 years ago by 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

comment:6 Changed 4 years ago by gh-BrentBaccala

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

comment:8 Changed 4 years ago by git

  • Commit changed from 974186dc15698b1ea29b0f40df58265fe2885d9b to 237ef2016148512710db91cb13b4af683197e5b4

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

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

comment:9 Changed 4 years ago by gh-BrentBaccala

  • Status changed from needs_work to needs_review

comment:10 follow-up: Changed 4 years ago by gh-BrentBaccala

  • Milestone changed from sage-8.2 to sage-duplicate/invalid/wontfix

Fixed by #16268

comment:11 in reply to: ↑ 10 ; follow-up: Changed 4 years ago by dkrenn

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 dkrenn

  • Status changed from needs_review to needs_info

comment:13 in reply to: ↑ 11 Changed 4 years ago by gh-BrentBaccala

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

  • Reviewers set to Daniel Krenn
  • Status changed from needs_review to positive_review

LGTM, thanks.

comment:15 Changed 4 years ago by vbraun

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

  • Milestone changed from sage-8.5 to sage-8.6

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

Note: See TracTickets for help on using tickets.