important ingredient: there is no normal form in general! This is an
undecidable problem... there is no algorithm that takes as input a
presentation and outputs whether this group has more than one element.
Though, there are some results about specific presentations (e.g. only
one relation, small simplifications, etc).
On 02/10/15 08:57, Nathann Cohen wrote:
(this is a new independent thread for a sub-conversation of the
Element.__hash__ thread)
Bottom line: the hash bug is not really the reason why Cayley graphs are
broken. Maybe there is some little examples where the Cayley graph is
computed wrong with the current hash and gets correctly computed with the
proposed changes, but that case is purelly incidental. Even if we fix the
hash, there would still be finitely presented groups for which the Cayley
graph gets a wrong answer, for the same reason: we cannot determine if two
elements are equal or not in general, we can only do so in some lucky cases.
What I read in your explanation is that solving the word problem is
hard in general, and (consequently) computing a normal form for an
element of a finitely presented group is also hard.
Definitely, to build the cayley graph of a finitely presented group
one must test equality between elements of the group (even if it is
very slow). If the elements of a given group do not carry a
"practical" implementation of word equality, then I would expect
__eq__ to raise a NotImplementedError. This would prevent anybody from
building the cayley graph and is, all in all, a normal behaviour
urging people to implement a decent __eq__ in that finitely presented
group.
Computing a normal form seems (to me) harder than testing equality.
However, it is not required in order to build a cayley graph: having a
hash that defaults to int(0) may be bad performance-wise, but still
return correct results as long as __eq__ is correct.
Is there anything that seems incorrect in what I said above? It seemed
to me that building the cayley graph of cyclic groups (which are those
used in the bug report you had in mind) would work fine, if we end up
rewriting the hash function so that it agrees with the equality that
is already defined on those elements.
Nathann
P.S.: Re-reading your message again, it seems that you hint that some
of the __eq__ functions defined on some finitely presented groups
return wrong results. Indeed, you say that "even with a fixed hash,
cayley_graph() could still return wrong answers".
--
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+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
