Sets of multivariate rational functions

[Peter Mueller]

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.

-- Peter Mueller

PS: I have spent half a day debugging some complicated code, when it finally turned out to be caused  by this unexpected behavior.

[Nils Bruin]

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.

[Martin R]

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

[Nils Bruin]

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)

[Vincent Delecroix]

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

> --
> 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 sage-support...@googlegroups.com.
> To view this discussion visit https://groups.google.com/d/msgid/sage-support/43c4110d-3238-4039-b47f-4c593e453338n%40googlegroups.com.

[julian...@gmail.com]

There is already a bug report from 2023 for this one at https://github.com/sagemath/sage/issues/35238.

julian

[julian...@gmail.com]

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

[Nils Bruin]

This is now fixed by https://github.com/sagemath/sage/pull/40019 which is merged into the development branch.