Equality of permutation groups

asked 2023-11-02 08:42:00 +0200

What does it mean for two permutation groups to be "equal", as in G==H ? I have searched the documentation back and forth, and could not find an answer. Even looking at the source I could not decipher how the comparison is done.

I can think of two meaningful definitions:

  1. Permutation groups are equal if they contain the same permutations (as in == between permutations)
  2. Permutation groups are equal if they contain the same permutations and have the same domain.

But neither definition complies with actual performance. Here is a minimal demonstration in SageMath version 9.0, Release Date: 2020-01-01, using Python 3.8.10.

sage: A = PermutationGroup([(1,3)], domain=[1,3])
sage: B = PermutationGroup([(1,3)], domain=[1,2,3])
sage: C = PermutationGroup([(1,3)], domain=[1,2,3,4])
sage: list(A)
[(), (1,3)]
sage: list(B)
[(), (1,3)]
sage: list(C)
[(), (1,3)]

Looks like all three groups contain the same two permutations as their elements. Let us verify.

sage: [A[i]==B[i] for i in [0,1]]
[True, True]
sage: [A[i]==C[i] for i in [0,1]]
[True, True]
sage: [B[i]==C[i] for i in [0,1]]
[True, True]

Yes, the elements compare equal. However, some of the groups compare equal, and some do not.

sage: A==B
sage: A==C
sage: B==C

Note: This might be related to SageMath issue #36527 (sorry, not enough karma to post the link), where IntegerVectorsModPermutationGroup is getting confused with permutations groups that have different domains but otherwise look the same. However, the above demonstration suggests that this is a more general thing.

Perhaps the question is: is there, or is there supposed to be, a meaningful notion of permutation group equality in Sage? If yes, what is it exactly?

edit retag flag offensive close merge delete


As it is checked by the code, the code is ignoring any structural mathematical human information on the objects and compares them (probably by using the .__eq method inherited from some upper class) as pythonic objects. And objectively, we have different groups also for the human eye, the groups are isomorphic in an obvious manner for the human, but have definitively different incarnations. A way to sieve this information would be to ask for the structure:

A, B, C = [PermutationGroup([(1,3)], domain=dom) for dom in [[1,3], [1, 2, 3], [1, 2, 3, 4]]]
print(f"A has the structure: {A.structure_description()}")
print(f"B has the structure: {B.structure_description()}")
print(f"C has the structure: {C.structure_description()}")

This gives the C2 structure in all cases.

dan_fulea gravatar imagedan_fulea ( 2023-11-02 19:27:01 +0200 )edit

Yes, obviously these three are isomorphic as groups. What I am asking is what (if any) meaningful mathematical information we are gaining, or should be gaining from the ==, beyond mere isomorphism. From the empirical findings, and from the word "pythonic" in your comment, I am beginning to think that the answer is perhaps "nothing much". Perhaps == is not even meant to be any kind of mathematical equality on permutation groups, but simply something reflecting some "pythonic" implementation details?

Jukka Kohonen gravatar imageJukka Kohonen ( 2023-11-02 21:16:33 +0200 )edit

Perhaps I should mention that I am not asking out of idle curiosity. Yes, those three are isomorphic as groups, but that is not the point. The point is that this "equality" or lack thereof is at the center of a very real bug in IntegerVectorsModPermutationGroup. That class is inheriting from UniqueRepresentation, so that a new call with the "same" permutation group can simply reuse the cached instance. However, since "same" is ==, this means that permutation groups with different domains are getting confused by the code.

So, is the verdict now that == is not even meant to be a reliable, meaningful mathematical equality of permutation groups? Then its use in IntegerVectorsModPermutationGroup is a mistake.

Jukka Kohonen gravatar imageJukka Kohonen ( 2023-11-04 17:56:43 +0200 )edit