About the "default" hash function from sage.structure.element.__hash__

[Nathann Cohen]

Hello everybody,

I have been playing with groups recently, and fought very hard with my code
before I noticed the usual bug:

    sage: a == b
    True
    sage: hash(a) == hash(b)
    False

Which has (among others) the following consequence:

    sage: G = groups.presentation.Cyclic(4)
    sage: G.cayley_graph().vertices()
    [1, a, a^2, a^-2, a^3, a^-1]

To me, the problem comes from the "default" implementation of __hash__ that can
be found in sage.structure.element:

    def __hash__(self):
       return hash(str(self))

Of course, with such a definition it is very likely that "__hash__" and "__eq__"
will never agree. As I expect that removing this dangerous default
implementation may break a *lot* of things, I created a ticket (needs_review)
that replaces it with "return 0".

http://trac.sagemath.org/ticket/19016

Nathann

[Volker Braun]

IMHO the real bug is that == is group-comparison instead of presentation-comparison. This obviously breaks hashes, and therefor makes associative containers useless. Getting rid of the hashes just means that associative containers are now useless because the word problem is not decidable. At least you just run out of memory instead of getting the wrong result, yay.  

[Nathann Cohen]

> IMHO the real bug is that == is group-comparison instead of
> presentation-comparison.

I take it as a design choice in that class. I opened this thread
because no standard on earth defines that two equal elements must have
the same __repr__, and that this is what the current implementation
assumes.

Unless you think there is a justification for that, I persist in
believing that this __hash__ function is dangerous.

Nathann

[Nathann Cohen]

> IMHO the real bug is that == is group-comparison instead of
> presentation-comparison.

P.S.: If you want to change it and make it a
"presentation-comparison", this class should not be considered as a
Group anymore, for the axioms would not be satisfied then. Your call.

Nathann

[Volker Braun]

"==" isn't used in any group theory textbook to my knowledge...  Of course group-equality should be a method, all I'm saying is that naming it __eq__() really badly interacts with associative containers.

[Nathann Cohen]

> "==" isn't used in any group theory textbook to my knowledge... Of course
> group-equality should be a method, all I'm saying is that naming it __eq__()
> really badly interacts with associative containers.

I find your proposition very entertaining, and I suggest that you open
an independent thread to request to change '==' in groups to be
something different.

Nathann

[Jeroen Demeyer]

On 2015-08-12 19:14, Volker Braun wrote:
> "==" isn't used in any group theory textbook to my knowledge... Of
> course group-equality should be a method, all I'm saying is that naming
> it __eq__() really badly interacts with associative containers.

To be clear, this isn't about comparing groups, but about comparing
elements of the same(?) group. Most certainly, textbooks use == (with
this, I really mean $=$) to compare elements of a group. It's like
comparing 6/3 with 4/2, you really want those to be equal.

For comparing groups, I agree that __eq__ should compare
construction/presentation and not be an isomorphism test.

Jeroen.

[Nils Bruin]

On Wednesday, August 12, 2015 at 1:08:00 PM UTC-7, Jeroen Demeyer wrote:

On 2015-08-12 19:14, Volker Braun wrote:
> "==" isn't used in any group theory textbook to my knowledge...  Of
> course group-equality should be a method, all I'm saying is that naming
> it __eq__() really badly interacts with associative containers.

To be clear, this isn't about comparing groups, but about comparing
elements of the same(?) group. Most certainly, textbooks use == (with
this, I really mean $=$) to compare elements of a group. It's like
comparing 6/3 with 4/2, you really want those to be equal.

Yes, and I agree that we'd be deviating very far from the mathematical norm if we'd let `==` mean anything else for group elements. It also means, as Volker points out, that in group presentations where we don't have a solution to the word problem, we don't have equality testing (and hence, certainly no hash either). There are groups, though, where we can solve the word problem. There `==` works. As Nathann points out, groups.presentation.Cyclic(4) is one.

Reading the doc of the wrapped Gap class http://www.gap-system.org/Manuals/doc/ref/chap47.html (section 47.3) we see that
in many cases GAP internally does do the work to get a decent hash function (an isomorphism to a permutation group or a normal form via Knuth-Bendix). If GAP doesn't expose this stuff automatically and having decent hashes (when possible) on FPgroups is valuable, we should reach into GAP to get the data out.

[Nathann Cohen]

I have been discussing this out with my girlfriend.

Appalled as I was at witnessing computer scientists debate whether
"==" should (or not) be what everybody on earth expects from a "=="
sgn (don't trust me? Poll it), I felt rather down. But then we
discussed it.

And we thought that it would be a vibrant message of Love to the
universe if we decided that everything (all of us, and numbers too)
were equal.

I propose to solve this problem by having the default __eq__ function
return 'True', regardless of its arguments. It would not be any less
stupid, but it would be optimistic. And that matters.

Nathann

> --
> You received this message because you are subscribed to a topic in the
> Google Groups "sage-devel" group.
> To unsubscribe from this topic, visit
> https://groups.google.com/d/topic/sage-devel/6rXKkF87Gtc/unsubscribe.
> To unsubscribe from this group and all its topics, 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/d/optout.

[Volker Braun]

On Wednesday, August 12, 2015 at 10:32:49 PM UTC+2, Nils Bruin wrote:

Yes, and I agree that we'd be deviating very far from the mathematical norm if we'd let `==` mean anything else for group elements. It also means, as Volker points out, that in group presentations where we don't have a solution to the word problem, we don't have equality testing (and hence, certainly no hash either). There are groups, though, where we can solve the word problem. There `==` works. As Nathann points out, groups.presentation.Cyclic(4) is one.

In many cases where we can solve the word problem we just use canonical representatives from the get-go. So there == would still do what you would naively expect even when comparing presentations in a given parent. But when we can't we should't pretend that we can magically solve the word problem. I'd take something that lets me write effective algorithms any time over an ideologically pure but useless implementation.

[Nils Bruin]

On Wednesday, August 12, 2015 at 2:49:26 PM UTC-7, Volker Braun wrote:

In many cases where we can solve the word problem we just use canonical representatives from the get-go. So there == would still do what you would naively expect even when comparing presentations in a given parent. But when we can't we should't pretend that we can magically solve the word problem. I'd take something that lets me write effective algorithms any time over an ideologically pure but useless implementation.

But we don't in the example that Nathann points out! In the finite FP group < a | a^4 >  of course we can solve the word problem, and Gap uses it to answer equality questions (via an isomorphism to a permutation group, if I understand their documentation). Yet we do NOT rewrite group elements into canonical form.

Do you really just want equality and hash on FP groups to be what we have on the covering free presentation? GAP doesn't do that itself (and as a result computations there can lead to unbounded running times and outright failures). I would propose that we follow the library that we wrap and do the same. For hashing that means that we must get a hold of the canonical form that GAP computes internally somewhere, though.

[Volker Braun]

On Thursday, August 13, 2015 at 12:32:27 AM UTC+2, Nils Bruin wrote:

Do you really just want equality and hash on FP groups to be what we have on the covering free presentation? GAP doesn't do that itself (and as a result computations there can lead to unbounded running times and outright failures)

The GAP language doesn't have many associative containers to start with; E.g. dictionary ("rec") keys must be strings there. Unless you intentionally create a GAP Set you won't accidentally invoke comparison under the hood. Thats fundamentally different in Python. It does make implementing fast algorithms so much easier in Python, but only if you can actually compare stuff.