If the problem is the computation of the Cayley graph on finitely presented groups, fixing the hash is not the solution.
Computing the Cayley graph means being able to solve the word problem in the group, which is, in general, hopeless. There are some techniques that can be used in big families of groups though: - if the group happens to be finite, one can find a representation in a symmetric group - one can take the rewriting system given by the presentation and run Knuth-Bendix algorithm on it. If you are very lucky, it will give you a confluent rewriting system (and hence a way to compute a normal form of every group element) in finite time. - one can try to find an automatic structure on the group (the GAP package kbmag has some functions for that). All of these techniques can be used to try to stablish a normal form of each element (which would solve the problem with Cayley graphs, hashes and what not), but none of them is granted to finish in finite time for a given finitely presented group. We actually already have the methods needed for the first two, so we could try to implement some method like .word_problem() that, when called, tries to apply these methods and, if one of them succeeds, implements the normal form from that moment on. what that would be a solution only for certain groups. For the rest, it would take forever (and maybe also consume all the system memory). 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. El viernes, 2 de octubre de 2015, 11:18:47 (UTC+2), Simon King escribió: > > Hi Vincent, > > On 2015-10-02, Vincent Delecroix <20100.d...@gmail.com <javascript:>> > wrote: > > #19331: return 0 as a default hash for Element > > Sounds reasonable to me. Always returning 0 may slow things down, but it > will certainly not violate Python's "axiom" that elements evaluating > equal must have equal hashes. And we talk here about the default, i.e., > all specialised (fast) hash implementations will still be available. > > And on second thought: Always returning 0 may actually speed things > *up*! There will be more hash collisions. But determining the string > representation to determine the hash can be very slow. > > Best regards, > Simon > > -- 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.
