Opened 5 years ago

Last modified 5 years ago

#19038 new defect

Better hash on FPGroups

Reported by: nbruin Owned by:
Priority: major Milestone: sage-6.9
Component: algebra Keywords:
Cc: ncohen Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by nbruin)

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

Change History (6)

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:4 Changed 5 years ago by ncohen

  • Cc ncohen added

comment:5 follow-up: 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.

comment:6 in reply to: ↑ 5 Changed 5 years ago by nbruin

Replying to 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.

The gap documentation indeed doesn't claim that it does.

Note: See TracTickets for help on using tickets.