Fix hashing of permutation group elements

[videlec]

As noticed on this sage-devel thread the hash function of PermutationGroupElement does not behave coherently with respect to the natural inclusions SymmetricGroup(n) c SymmetricGroup(n+1).

We design a hash function:

• whose value on the identity is 1
• which does only depend on the support (ie ignores fixed points so that the hash is consistent with permutation restriction)
• which is independent of the domain ordering

Component: group theory

Author: Vincent Delecroix

Branch/Commit: u/vdelecroix/31236 @ e2e4d1d

Reviewer: Dima Pasechnik, ​David Roe

Issue created by migration from https://trac.sagemath.org/ticket/31236

[dimpase]

comment:2

GAP has a function LargestMovedPoint() for permutations, so instead of using self.n, where n is the degree of the permutation group, one can use this value to iterate over while computing the hash.

While this does not ignore all the fixed points, this is still OK in terms of the consistency.

[videlec]

Branch: u/vdelecroix/31236

[videlec]

Commit: 462fdb1

[videlec]

New commits:

462fdb1

31236: fix hash function of permutations

[dimpase]

comment:5

What is 145623773L doing there?

Are you replacing something which looks to me as a perfect hash function (i.e. no collisions) with something that might have collisions?

[videlec]

comment:6

If you find a collision, I pay you a beer.

[dimpase]

comment:7

I asked a theory question.

[videlec]

comment:8

145623773L is an offset to ensure bit shuffling. See https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function (though I might not have used the best constants).

[dimpase]

comment:9

thanks. please add this info in the docs.

[sagetrac-git]

Changed commit from 462fdb1 to ba9d62d

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

ba9d62d

31326: reference for algorithm

[videlec]

comment:11

done

[dimpase]

comment:12

OK, looks good, thanks.

[dimpase]

Reviewer: Dima Pasechnik

[videlec]

comment:13

sage: S1 = SymmetricGroup(FiniteEnumeratedSet([1,2,3]))
sage: S2 = SymmetricGroup(FiniteEnumeratedSet([2,1,3]))
sage: S1("(1,3,2)") == S2("(1,3,2)")
True
sage: hash(S1("(1,3,2)")) == hash(S2("(1,3,2)"))
False

[sagetrac-git]

Changed commit from ba9d62d to 3e29948

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

3e29948

31326: change algorithm for consistency

[videlec]

comment:15

Consistent hashing with more tests.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

e2e4d1d

31236: use a hash array for non standard domains

[sagetrac-git]

Changed commit from 3e29948 to e2e4d1d

[videlec]

comment:36

Better now

sage: S = SymmetricGroup(['a','b','c','d','e','f','g','h','i'])
sage: %timeit -r5 for s in S: h = hash(s)
159 ms ± 1.17 ms per loop (mean ± std. dev. of 5 runs, 10 loops each)

Computing a single hash of an element triggers the creation of an array in the parent

sage: S._domain_hash_array
array('l', [-5034579376873000338, 5819885834672024805, -1342306816048582247, 4154873981948319473, -9080196639829811986, 3487762170233258304, -4059262801740968994, -1410151844174446032, -7454342532774124322])

This solution is not ideal as the hash array could be made available on the domain itself and not on the symmetric group. It could end up with many duplications of this array (ie when constructing subgroups).

[videlec]

comment:37

See #31269

[videlec]

comment:38

ping

[roed314]

comment:39

I'm happy giving this ticket positive review. Since Dima originally reviewed it, I'll give him a couple days to respond with an objection and suggestions for how he'd like to proceed.

[videlec]

Changed reviewer from Dima Pasechnik to Dima Pasechnik, ​David Roe

[dimpase]

comment:41

My objection is only on the level of documentation. Where the hell these huge constants come from, and why? It's totally unclear.

[videlec]

comment:42

As their names indicate mult1, mult2 are multipliers (for bit shuffling) and mask1, mask2 are masks so that the hasing of the pair (i, j) is non commutative (ie different from the hash of (j, i)). These numbers are not big, they are 64 bit integers.

[videlec]

comment:43

ping

[roed314]

comment:44

Sorry, I've been busy. This looks good to me.

[vbraun]

comment:45

I got this on Ubuntu 18.04 32 bit

**********************************************************************
File "src/sage/groups/perm_gps/permgroup_element.pyx", line 1485, in sage.groups.perm_gps.permgroup_element.PermutationGroupElement.__hash__
Failed example:
    for n in range(1, 10):
       G = SymmetricGroup(n)
       assert hash(G.one()) == 1
       assert len(set(map(hash, G))) == factorial(n)
Exception raised:
    Traceback (most recent call last):
      File "/var/lib/buildbot/slave/sage_git/build/local/lib/python3.9/site-packages/sage/doctest/forker.py", line 714, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/var/lib/buildbot/slave/sage_git/build/local/lib/python3.9/site-packages/sage/doctest/forker.py", line 1133, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.groups.perm_gps.permgroup_element.PermutationGroupElement.__hash__[3]>", line 4, in <module>
        assert len(set(map(hash, G))) == factorial(n)
    AssertionError
**********************************************************************
File "src/sage/groups/perm_gps/permgroup_element.pyx", line 1493, in sage.groups.perm_gps.permgroup_element.PermutationGroupElement.__hash__
Failed example:
    assert len(set(map(hash, A))) == A.cardinality()
Exception raised:
    Traceback (most recent call last):
      File "/var/lib/buildbot/slave/sage_git/build/local/lib/python3.9/site-packages/sage/doctest/forker.py", line 714, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/var/lib/buildbot/slave/sage_git/build/local/lib/python3.9/site-packages/sage/doctest/forker.py", line 1133, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.groups.perm_gps.permgroup_element.PermutationGroupElement.__hash__[7]>", line 1, in <module>
        assert len(set(map(hash, A))) == A.cardinality()
    AssertionError
**********************************************************************
1 item had failures:
   2 of  35 in sage.groups.perm_gps.permgroup_element.PermutationGroupElement.__hash__
    [426 tests, 2 failures, 3.64 s]

as a general bit of advice, consider using assert condition, message so you learn whats wrong from tracebacks...

[mkoeppe]

comment:46

Moving this ticket to 9.4, as it seems unlikely that it will be merged in 9.3, which is in the release candidate stage

[mkoeppe]

comment:47

Setting a new milestone for this ticket based on a cursory review.