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 )
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
comment:2 Changed 5 years ago by
- Description modified (diff)
comment:3 Changed 5 years ago by
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
- Cc ncohen added
comment:5 follow-up: ↓ 6 Changed 5 years ago by
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
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.
One case Gap can handle is that of finite groups:
and we're getting it wrong presently. (Perhaps if #19016 gets fixed, we just won't have a hash at all)
We can improve the situation in the following way:
whith these definitions:
Gap correctly find from this finite presentation that the group is A5 and the map f is its standard permutation representation in Sym(6).