There is now a fix for this at https://github.com/sagemath/sage/pull/40000. This implements a mostly constant hash function which is not ideal but maybe better than what we currently have.
julian On Wednesday, April 23, 2025 at 1:17:28 AM UTC+3 [email protected] wrote: > There is already a bug report from 2023 for this one at > https://github.com/sagemath/sage/issues/35238. > > julian > > On Tuesday, April 22, 2025 at 11:47:32 PM UTC+3 vdelecroix wrote: > >> A simple way to fix the OP is to set FractionFieldElement.__hash__ to >> return 0 always. >> >> Though, if we want to keep x == y implies hash(x) == hash(y) through >> injective coercions then we are in trouble because of fraction fields. >> One could introduce a framework for canonical representatives of >> fraction field elements... but it looks like a can of worms. >> >> Vincent >> >> On Tue, 22 Apr 2025 at 19:06, Nils Bruin <[email protected]> wrote: >> > >> > Good find! Indeed, the fraction field of ZZ[x,y] is equally broken. >> It's just less pronounced because there are fewer units: >> > >> > sage: K.<x,y>=ZZ[] >> > sage: (-x)/(-y) >> > (-x)/(-y) >> > sage: (-x)/(-y) == x/y >> > True >> > sage: hash((x)/(y)) >> > -8752216344059172460 >> > sage: hash((-x)/(-y)) >> > -8752216196772797820 >> > >> > That hash is bad in other ways too: n^d is symmetric and generally >> looks quite likely to generate hash collisions (although that depends a bit >> on how garbled the hashes of the numerator and denominator are) >> > >> > On Tuesday, 22 April 2025 at 01:35:31 UTC-7 [email protected] wrote: >> >> >> >> I would think that the method `__hash__` of FractionFieldElement in >> fraction_field_element.pyx is broken, since >> >> >> >> sage: f1 = x/y >> >> sage: f2 = (2*x)/(2*y) >> >> sage: f1 == f2 >> >> True >> >> sage: hash(f1) >> >> -284264079394034550 >> >> sage: hash(f2) >> >> -284264773958195866 >> >> >> >> In `__hash__`, we do the following: >> >> >> >> if self._parent.is_exact(): >> >> ... >> >> self.reduce() >> >> # Same algorithm as for elements of QQ >> >> n = hash(self._numerator) >> >> d = hash(self._denominator) >> >> if d == 1: >> >> return n >> >> else: >> >> return n ^ d >> >> >> >> The problem is that `self.reduce()` doesn't have any effect: it >> divides out the gcd of numerator and denominator, which is 1, since QQ is a >> field. (Over ZZ it is 2, which is the reason why it works) >> >> >> >> I don't know how to fix this properly. Can we define a sensible hash >> generically for FractionFieldElement at all? >> >> >> >> Partially, this might also be my fault from >> https://github.com/sagemath/sage/pull/38924 >> >> >> >> There are other tickets that thought about this, e.g., >> https://github.com/sagemath/sage/issues/16268 >> >> >> >> :-( >> >> >> >> Martin >> >> >> >> On Wednesday, 16 April 2025 at 17:48:47 UTC+2 Nils Bruin wrote: >> >>> >> >>> On Wednesday, 16 April 2025 at 04:55:39 UTC-7 Peter Mueller wrote: >> >>> >> >>> The following code >> >>> >> >>> K.<x, y> = QQ[] >> >>> K = K.fraction_field() >> >>> print(len({x/y, (2*x)/(2*y)})) >> >>> >> >>> gives the answer 2, even though the two elements of course are the >> same! Is this a bug or a feature for a reason I cannot guess? Same on the >> SageMath Cell. >> >>> >> >>> >> >>> I don't think it's a feature but it might be that you're hitting >> general code that can't do much more than it does. In that case we should >> probably have a specialization that deals with that particular situation. >> >>> >> >>> In your case, we can just force the denominator to be monic. It can >> make for less nice representations because it might cause fractional >> coefficients in the numerator and denominator: >> >>> >> >>> >> f.numerator()/(c:=f.denominator().leading_coefficient())/(f.denominator()/c) >> >> >>> >> >>> For this standardization, we need that there's a monomial ordering >> (which would generally be met) and that the leading coefficient is a unit >> (true over a field). It's the last one that is generally problematic. In >> ZZ["x,y"].fraction_field(), you'd already need a different approach and >> over domains with more complicated unit groups and/or without unique >> factorization, normalizing the denominator is going to be very expensive. >> Note that it doesn't affect the ability to compute in the field of >> fractions: equality testing is still easy. It's just the normal form that's >> hard (and which is necessary to get to a well-defined hash). >> >>> >> >>> Funniliy enough: >> >>> >> >>> K.<x, y> = ZZ[] >> >>> >> >>> K = K.fraction_field() >> >>> print(len({x/y, (2*x)/(2*y)})) >> >>> >> >>> so it seems that the extra work was already done in that case. And >> that's also the representation in which you'll avoid denominators in the >> denominator! So probably it's better to switch to that representation. If >> you need polynomials you can use >> >>> >> >>> QQ['x,y'](f) >> >>> >> >>> when the denominator has degree 0. >> >>> >> > -- >> > You received this message because you are subscribed to the Google >> Groups "sage-support" group. >> > To unsubscribe from this group and stop receiving emails from it, send >> an email to [email protected]. >> > To view this discussion visit >> https://groups.google.com/d/msgid/sage-support/43c4110d-3238-4039-b47f-4c593e453338n%40googlegroups.com. >> >> >> > -- You received this message because you are subscribed to the Google Groups "sage-support" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion visit https://groups.google.com/d/msgid/sage-support/ac8118ed-6d81-4639-80b0-f362040ede89n%40googlegroups.com.
