Opened 5 years ago

# Better hash on FPGroups

Reported by: Owned by: nbruin major sage-6.9 algebra ncohen N/A

As is pointed out on #19016 the hash on FPGroup elements is currently based on the (non-canonical) representation, whereas the equality test is a more elaborate one borrowed from Gap. That means currently, there are elements that are equal but have different hashes

```sage: G.<a,b>=FreeGroup()
sage: Q=G.quotient([a*b])
sage: U=Q(a)*Q(b)
sage: V=Q(1)
sage: U==V
True
sage: hash(U)==hash(V)
False
```

When Gap does succeed in testing equality, it does so via a normal form of its elements. One way of equipping FPGroups with a well-behaved hash is by getting that normal form from gap and hash that.

The main inspiration for how to do this would come from Gap's MakeFpGroupCompMethod source

### comment:1 Changed 5 years ago by nbruin

One case Gap can handle is that of finite groups:

```sage: G.<a,b>=FreeGroup()
sage: A5=G.quotient([a^3,b^3,(a/b/a/b)^2,(a^(-1)*b/a/b)^2])
```

and we're getting it wrong presently. (Perhaps if #19016 gets fixed, we just won't have a hash at all)

```sage: A5(a^3)==A5(1)
True
sage: hash(A5(a^3))==hash(A5(1))
False
```

We can improve the situation in the following way:

```FamilyObj=libgap.function_factory("FamilyObj")
ElementsFamily=libgap.function_factory("ElementsFamily")
FPFaithHom=libgap.function_factory("FPFaithHom")
Image=libgap.function_factory("Image")
```

whith these definitions:

```sage: f=FPFaithHom(ElementsFamily(FamilyObj(A5.gap())))
sage: newhash=lambda a: hash(Image(f,a.gap()))
sage: newhash(A5(a^3))==newhash(A5(1))
True
sage: import collections
sage: collections.Counter((u==v,newhash(u)==newhash(v) ) for (u,v) in ( (A5.random_element(),A5.random_element()) for j in range(6000)) )
Counter({(False, False): 5899, (True, True): 101})
```

Gap correctly find from this finite presentation that the group is A5 and the map f is its standard permutation representation in Sym(6).

### comment:2 Changed 5 years ago by nbruin

• Description modified (diff)

### comment:3 Changed 5 years ago by nbruin

For a non-finite group we'd end up doing something like this:

```FpElementNFFunction=libgap.function_factory("FpElementNFFunction")
UnderlyingElement=libgap.function_factory("UnderlyingElement")
```
```sage: Q=G.quotient([a*b])
sage: f=FpElementNFFunction(ElementsFamily(FamilyObj(Q.gap())))
sage: newhash=lambda q: hash(f(UnderlyingElement(q.gap())))
sage: L=[Q.0^i*Q.1^j*Q.0^k for i in range(-2,2) for j in range(-2,2) for k in range(-2,2)]
sage: collections.Counter((u==v,newhash(u)==newhash(v) ) for u in L for v in L)
Counter({(False, False): 3516, (True, True): 580})
```

### comment:5 follow-up: ↓ 6 Changed 5 years ago by mmarco

Are you sure that gap can always get it right for finite groups? It sounds hard to believe, since just deciding if the group is trivial or not is an undecidable problem.