Hashing elements from the same ring

[Stefan]

I ran into the following issue:

sage: H5.<a,b,c> = FractionField(PolynomialRing(ZZ, ['a', 'b', 'c']))
sage: S = set([1/(1-c)])
sage: (-1)/(c-1) in S
False

I know Sage doesn't promise that equal objects have equal hashes, but surely this should be valid for objects from *a single ring*?

I looked at the hash function implementation, and it's not straightforward to fix this, since it's the generic FractionField method. In particular, we can assume nothing about the ring on which the FractionField is based. I can come up with some examples of rings, and try to do something for them, but my imagination is kind of limited. Subclassing FractionField feels like overkill, but a long list of try... Except clauses inside __hash__ is bad too.

Thoughts?

--Stefan

[Robert Bradshaw]

What could perhaps be added is some kind of a normalization routine
(to be implemented by subclasses) that is called before performing a
hash. This might be quite expensive. There's also some fuzziness about
what equality should be used, e.g. is this OK?

sage: S = set([(x+1)^2])
sage: x^2 + 2*x + 1 in S
False

That really depends on what you want.

> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> To post to this group, send email to sage-...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/groups/opt_out.

[Simon King]

Hi Robert, hi Stefan,

On 2013-08-28, Robert Bradshaw <robe...@math.washington.edu> wrote:
> What could perhaps be added is some kind of a normalization routine
> (to be implemented by subclasses) that is called before performing a
> hash. This might be quite expensive.

Sorry, I intended to answer yesterday evening along the same lines, but
my internet connection broke.

I think we should look at how equality of fraction field elements is
defined, and what we can learn from it for the hash function.

By definition, n1/d1 is equal to n2/d2 if and only if n1*d2==n2*d1. But
because of mixing terms from right and left, this is not useful for the
hash, because the hash only knows about *one* element.

But there is also a generically implemented method .reduce() for
fraction field elements (so, not necessarily needed to implement it in
subclasses). Of course, it is expensive and it may fail (if
the gcd is not defined). But *if* it works, then fraction f1 is equal to
fraction f2 if and only if numerator and denominator of f1.reduce() are
equal to those of f2.reduce(). Hence, this is the right thing to do for
the hash: Just insert self.reduce() at the beginning of self.__hash__().

I'd rather have a slow hash than a totally broken hash.

One point needs to be fixed, though. self.reduce() would do the same
expensive computations even if self already *is* reduced. Hence,
.reduce() should do some caching. And if self.reduce() fails, then I
think self should not be hashable!

> There's also some fuzziness about
> what equality should be used, e.g. is this OK?
>
> sage: S = set([(x+1)^2])
> sage: x^2 + 2*x + 1 in S
> False

This is OK, because (x+1)^2 and x^2+2*x+1 do not compare equal, in terms
of cmp:

sage: cmp((x+1)^2, x^2 + 2*x + 1)
1

If I am not mistaken, containment in sets and dicts relies on cmp and
not on ==. Hence, in this case, I think the hash is not to blame.

Best regards,
Simon

[John H Palmieri]

On Thursday, August 29, 2013 2:08:49 AM UTC-7, Simon King wrote:

Hi Robert, hi Stefan,

 

If I am not mistaken, containment in sets and dicts relies on cmp and
not on ==. Hence, in this case, I think the hash is not to blame.

Indeed, comparing using == works:

sage: H5.<a,b,c> = FractionField(PolynomialRing(ZZ, ['a', 'b', 'c']))
sage: S = set([1/(1-c)])
sage: (-1)/(c-1) in S
False

sage: [(-1)/(c-1) == _ for _ in S]
[True]
sage: any([(-1)/(c-1) == _ for _ in S])
True

--
John

[Stefan]

But there is also a generically implemented method .reduce() for
fraction field elements (so, not necessarily needed to implement it in
subclasses). Of course, it is expensive and it may fail (if
the gcd is not defined). But *if* it works, then fraction f1 is equal to
fraction f2 if and only if numerator and denominator of f1.reduce() are
equal to those of f2.reduce(). Hence, this is the right thing to do for
the hash: Just insert self.reduce() at the beginning of self.__hash__().

Actually, this is not quite true. reduce() is, by default, called automatically for elements of exact rings at creation time. It will correctly get rid of common factors, but it does not normalize the leading coefficients:

sage: H5.<a,b,c> = FractionField(PolynomialRing(ZZ, ['a', 'b', 'c']))

sage: p1 = 1/(1-c)

sage: p2 = (-1)/(c-1)

sage: p3 = (c+1)/(c^2 - 1); p3

1/(c - 1)

sage: p1.reduce(); p1

1/(-c + 1)

sage: p2.reduce(); p2

(-1)/(c - 1)

 

I'd rather have a slow hash than a totally broken hash.

Meh. I still want to do this billions of times. 

This is OK, because (x+1)^2 and x^2+2*x+1 do not compare equal, in terms
of cmp:

 sage: cmp((x+1)^2, x^2 + 2*x + 1)
 1

Actually, this does not hold in my example (with the polynomial ring defined above):

sage: cmp((c+1)^2, c^2 + 2*c+1)

0

Again, my main issue is that the elements are *from the same ring*. 

Cheers,

Stefan.

[Vincent Delecroix]

Hello,

The following is I guess for the symbolic ring and is what we want

sage: cmp((x+1)^2, x^2 + 2*x + 1)
1

while the following is in a polynomial ring and is also what we want

sage: cmp((c+1)^2, c^2 + 2*c+1)
0

The only issue is about hashing and not == vs cmp, right ?

Note that there are other similar troubles with hashing, equality and
comparisons:
- http://wiki.sagemath.org/EqualityCoercion
- #14608 on trac

Cheers,
Vincent

[Simon King]

Hi Stefan,

On 2013-08-29, Stefan <stefan...@gmail.com> wrote:
> Actually, this is not quite true. reduce() is, by default, called
> automatically for elements of exact rings at creation time. It will
> correctly get rid of common factors, but it does not normalize the leading
> coefficients:

Bad. But of course, it is all only defined up to units.

>> I'd rather have a slow hash than a totally broken hash.
>>
>
> Meh. I still want to do this billions of times.

Well, with a broken hash, it would work wrong billions of times.

> Actually, this does not hold in my example (with the polynomial ring
> defined above):
>
> sage: cmp((c+1)^2, c^2 + 2*c+1)
> 0

It is a totally different problem. My example was about symbolic variables,
which is a totally different story, even though on the surface it seems
to be almost the same as your original example ("we have two equal elements
a and b of a ring, but Sage does not recognise that a is in set([b])").

Best regards,
Simon

[Nils Bruin]

On Thursday, August 29, 2013 8:52:02 AM UTC-7, Simon King wrote:

Hi Stefan,

On 2013-08-29, Stefan <stefan...@gmail.com> wrote:
> Actually, this is not quite true. reduce() is, by default, called
> automatically for elements of exact rings at creation time. It will
> correctly get rid of common factors, but it does not normalize the leading
> coefficients:

Bad. But of course, it is all only defined up to units.

On the other hand, in a lot of cases there are ways of normalizing, such as making the leading coefficient of the denominator monic.

There are also many fields where there is no GCD, but a "denominator" can still be uniquely defined: think number fields and function fields that are a finite extension of a rational function field.

I suspect avoiding normalization is only seemingly a saving: When you start adding elements together, you'll quickly see things explode if you're not normalizing fractions.

Of course, keeping elements in product form can be a very large saving if you really need to compute in the multiplicative group of the function field, so there is room for using multiple internal representations of elements.

So I'd say: equip domains with an optional normalize_fraction routine that normalizes a tuple (N,D) to (N',D') with a unique denominator D'. If that method is available, use it (always!) in FractionField and make elements hashable.

[Stefan]

I like this solution! Maybe I'll get around to working on it soon(ish).

--Stefan