Elements of finitely presented groups: hash function

[Nathann Cohen]

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

[Vincent Delecroix]

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

[mmarco]

Ups, I emailed my answer to Nathan and now I am no longer in my office so I have no access to it. Can you please paste it here?

[Nathann Cohen]

(Miguel's post follows)

On 2 October 2015 at 14:50, <mma...@unizar.es> wrote:
> What you say is pretty much correct, but something must be added.
>
> Solving the word problem (that is, testing equality) is not only very hard: it
> is an undecidable problem in general. That is: there can't be any algorithm
> that determines if two words correspond to the same element of an arbitrary
> finitely presented group. So "implementing a decent __eq__" is an impossible
> task.
>
> There is some hope though. It is impossible to solve the problem in general,
> but there are some techniques that can be succesful in many cases (and i guess
> most of the cases you would be interested in fall in this lucky category).
>
> As you said, computing a normal form is a harder problem than testing
> equality... but most of the techniques that can be used to attack the word
> problem happen to be based on some kind of normal form. So, even if in theory
> the normal form problem is harder than the word problem, in practice almost
> always the solution for both problems come together: either we are able to
> compute a normal form, or we are unable to decide equality.
>
> The case of cyclic groups that you mention is a very easy one. They are finite,
> abelian and have a very simple confluent rewriting system. Every possible
> techinque to solve the word problem works immediately. That is why, if you
> delegate the equality to gap (which is what happen when the hash does not
> distinguish), it is able to determine if two elements are the same or not.
>
> But as I said, that is incidental. It happens because we are dealing with very
> simple presentations, and the basic reductions that gap does internally are
> enough to distinguish the elements. If, for instance, we would present the
> same groups with a more complicated presentation, it could happen that those
> simple reductions wouldn't be enough to correctly distinguish the elements.
>
> In general, it is not a good idea to use the structure of a finitely presented
> group if you need to accurately distinguish elements. If that is your case,
> and you group allows any other way to be represented (PermutationGroup,
> AbelianGroup, MatrixGroup...), it is a much better idea to do so: in those
> structures equality testing is trivial (in fact you have a unique canonical
> form of each element), whereas in the finitely presented group theory it is
> undecidable.
>
> I hope i clarified things a bit.
>
> Best,
>
> Miguel

[Nils Bruin]

On Friday, October 2, 2015 at 5:02:43 AM UTC-7, vdelecroix wrote:

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

And, as far as Sage is concerned, we can easily do as well as gap for gap objects:

http://trac.sagemath.org/ticket/19016#comment:21

[mmarco]

That would be an improvement, but still wouldn't be a solution.

At some point, we have to live with the fact that comparison in finitely presented groups will only work reliably if we are lucky. What we can do is try to make the set of "lucky" groups bigger. And at some point that will come at the expense of time and/or memory.

But it would be definitely worth it to take advantage of what gap has already done in that direction. But beware, their approach consists in trying until it can prove that the elements are equal (or that they are not equal). That means that if you are in one of the unlucky cases, just comparing two elements will start  to consume 100% of your cpu for the eternity (or until the RAM is exhausted, whatever happens first).

If you want to play with a presentation with non decidable word problem, you can try to paste this in a gap session:

F := FreeGroup("a","b","c","d","e","p","q","r","t","k");
a:=F.1;

b:=F.2;

c:=F.3;

d:=F.4;

e:=F.5;

p:=F.6;

q:=F.7;

r:=F.8;

t:=F.9;

k:=F.10;

G:=F/[p^10*a/(a*p), p^10*b/(b*p), p^10*c/(c*p), p^10*d/(d*p), p^10*e/(e*p), q*a/(a*q^10), q*b/(b*q^10), q*c/(c*q^10), q*d/(d*q^10), q*e/(e*q^10),r*a/r/a,r*b/r/b, r*c/r/c, r*d/r/d, r*e/r/e, p*a*c*q*r/(r*p*c*a*q), p^2*a*d*q^2*r/(r*p^2*d*a*q^2), p^3*b*c*q^3*r/(r*p^3*c*b*q^3), p^4*b*d*q^4*r/(r*p^4*d*b*q^4),  p^5*c*e*q^5*r/(r*p^5*e*c*a*q^5), p^6*d*e*q^6*r/(r*p^6*e*d*q^6), p^7*c*d*c*q^7/(p^7*c*d*c*e*q^7), p^8*c*a*a*a*q^8/(r*p^8*a*a*a*q^8), p^9*d*a*a*a*q^9*r/(r*p^9*a*a*a*q^9), p*t/p/t, q*t/q/t, k*(a*a*a)^(-1)*t*(a*a*a)/(k/(a*a*a)*t*a*a*a )];

Then try to compare two elements of G.