(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.
