IntegerVectorsModPermutationGroup confuses groups whose domains are different

[jukkakohonen]

Steps To Reproduce

In SageMath version 9.0, running this:

A = PermutationGroup([(1,2)], domain=[1,2])
print("with domain ", A.domain())
print(IntegerVectorsModPermutationGroup(A, 3).list())

B = PermutationGroup([(1,2)], domain=[1,2,3])
print("with domain ", B.domain())
print(IntegerVectorsModPermutationGroup(B, 3).list())

Expected Behavior

In A , the domain has two elements, so I am expecting lists of two elements that add up to 3:

with domain  {1, 2}
[[3, 0], [2, 1]]

In B, the domain has three elements, so I am expecting lists of three elements that add up to 3:

with domain  {1, 2, 3}
[[3, 0, 0], [2, 1, 0], [2, 0, 1], [1, 1, 1], [1, 0, 2], [0, 0, 3]]

Actual Behavior

From both groups we get the same listing:

with domain  {1, 2}
[[3, 0], [2, 1]]
with domain  {1, 2, 3}
[[3, 0], [2, 1]]

Additional Information

If the order of execution is reversed, so that we do B first and A second, then B gives the correct three-element lists, and A gives incorrectly the three-element lists.

So, the first one gets computed correctly, and the second one incorrectly. It looks like IntegerVectorsModPermutationGroup is remembering that it has already seen this group, not noticing that is in fact a different permutation group with different domain.

Environment

- **OS**: Ubuntu 20.04
- **Sage Version**: 9.0

Checklist

• I have searched the existing issues for a bug report that matches the one I want to file, without success.
• I have read the documentation and troubleshoot guide

[TheShiveshNetwork]

I'd like to work on this issue. Can it be assigned to me?

[jukkakohonen]

According to my rudimentary tests, for the second group, the __init__ method of the auxiliary class IntegerVectorsModPermutationGroup_with_constraints is never even called. This seems to be because the auxiliary class inherits from UniqueRepresentation. When called with a group argument that it has seen before, it just takes the existing, cached instance.

And indeed, those two permutation groups are "Sage-equal" as in

sage: A = PermutationGroup([(1,2)], domain=[1,2])                               
sage: B = PermutationGroup([(1,2)], domain=[1,2,3])                             
sage: A == B                                                                    
True

even though they have domains of different sizes, so they are supposed to act on integer vectors of different lengths. This is related to my Ask Sagemath question Equality of permutation groups.

Since the SageMath behaviour of permutation group equality is not likely to change (or at least, it would be a big change), and it makes sense to keep the cached behaviour here, one simply needs a way to differentiate situations that are different but have the "Sage-same" permutation group. What if the auxiliary class is simply given an extra domain argument?

[jukkakohonen]

A workaround is to always compute a strong generating system for the permutation group, and provide it as an argument. Permutation groups with different domains will have different systems, so this differentiates them.

sage: A = PermutationGroup([(1,2)], domain=[1,2])                                                                  
sage: B = PermutationGroup([(1,2)], domain=[1,2,3])                                                                
sage: SA = tuple(tuple(sa) for sa in A.strong_generating_system())                                                                           
sage: SB = tuple(tuple(sb) for sb in B.strong_generating_system())                                                                           
sage: list(IntegerVectorsModPermutationGroup(A, 3, sgs=SA))                                                        
[[3, 0], [2, 1]]
sage: list(IntegerVectorsModPermutationGroup(B, 3, sgs=SB))                                                        
[[3, 0, 0], [2, 1, 0], [2, 0, 1], [1, 1, 1], [1, 0, 2], [0, 0, 3]]

[jukkakohonen]

Are there any thoughts on how this would be fixed? Note that this is not some funny artificial corner case, but a real issue when working with several different permutation groups. In my work with graph isomorphisms I have to use the "sgs" workaround, otherwise all my results would be incorrect.

The bug is somewhat nasty because it silently causes mathematically wrong results, even unpredictably (depending on what groups have been handled in the SageMath session previously, and in what order). At the very least, if not fixed, the bug should be documented to the users.

[dimpase]

I can confirm it's still the same bug in Sage 10.2

[dimpase]

the problem is in IntegerVectorsModPermutationGroup derived from UniqueRepresentation, and as from the point of view UniqueRepresentation A and B are equal - and it's not only from its point of view, it's just cause A==B evaluates to True, you get this bug.
Mathematically speaking, A==B must not return True, it must check that A.domain()==B.domain() as well.
It's not so hard to change this, provide an implementation of __richcmp_method__ for PermutationGroup_generic
which takes this into account, but I don't know how much Sage code this will break.

Maybe @tscrim can say more about it.

[tscrim]

I am not sure how the group theory people would react to that since the groups are "equal." Although here this means <= compares by subgroups and then A == B is A <= B and B <= A. So they look at the permutations themselves, not the domain they are defined on.

I would instead just pass the domain as part of the constructor for IntegerVectorsModPermutationGroup as an additional named argument; in particular to the super().__classcall__(..., domain=D) to avoid backwards compatibility issues.

[dimpase]

Permutation group is a pair (group, domain), not just a group. So this would be fixing a maths bug.
(yes, my PhD is in group theory, and I published a couple of papers on permutation groups :-))

[tscrim]

Indeed. :) I don't disagree with you, but there are people who use the permutation groups and might expect them to be equal as their repr() does not reference the domain:

sage: PermutationGroup([(1,2)], domain=[1,2,3])
Permutation Group with generators [(1,2)]

This just might also end up breaking a fair bit of code in the wild. I guess we could get some sense of this by what breaks within library code. It is just such a change we might need to approach with some caution. (We can fix the bug at hand another way at least.)

[jukkakohonen]

Sage's concept of equality of permutation groups is not that well-defined. It is not documented, it is not transitive, it does not conform to "equal if the permutations are equal", and it does not conform to "equal if repr are equal".

sage: S0=SymmetricGroup(0)                                                                                                      
sage: S1=SymmetricGroup(1)                                                                                                      
sage: P1=PermutationGroup([],domain=(1,))                                                                                       
sage: S0==S1, S1==P1, S0==P1                   # Not transitive.                                                                             
(False, True, True)
sage: list(S0)==list(S1), list(S1)==list(P1), list(S0)==list(P1)                                                                
(True, True, True)

Another example showing that sometimes different domain causes the permutation groups to be different, and sometimes it does not. All of the following four groups contain the same permutations, as compared with ==. All have the same __repr__().

sage: A = PermutationGroup([(1,3)], domain=[1,3])                                                                               
sage: B = PermutationGroup([(1,3)], domain=[1,3,4])                                                                             
sage: C = PermutationGroup([(1,3)], domain=[1,2,3])                                                                             
sage: D = PermutationGroup([(1,3)], domain=[1,2,3,4])                                                                           
sage: GG = [A,B,C,D]                                                                                                            
sage: [[G==H for G in GG] for H in GG]                                                                                          
[[True, True, False, False],
 [True, True, False, False],
 [False, False, True, True],
 [False, False, True, True]]
sage: [[list(G)==list(H) for G in GG] for H in GG]                                                                              
[[True, True, True, True],
 [True, True, True, True],
 [True, True, True, True],
 [True, True, True, True]]
sage: A                                                                                                                         
Permutation Group with generators [(1,3)]
sage: B                                                                                                                         
Permutation Group with generators [(1,3)]
sage: C                                                                                                                         
Permutation Group with generators [(1,3)]
sage: D                                                                                                                         
Permutation Group with generators [(1,3)]

It is also not true that A==B would be equivalent to A<=B and B<=A.

sage: A==B, A<=B, B<=A                                                                                                          
(True, False, False)
sage: C==D, C<=D, D<=C                                                                                                          
(True, False, False)

Now what is the well-defined equality notion here? Can it be documented?

[tscrim]

Please don’t use corner cases as general examples (S_0 is not really well-defined as a group as you likely know). Please don’t assume that equality is broken and assume everything is built around the lists of permutations. It is documented what the behavior is in the comparison method and it is well-defined. Stop assuming that the issue is with the definition and actually look at what the code is doing before claiming where a problem is. It’s good that you are finding these inconsistencies, but I would appreciate it if you could tone done the amount of sensationalism.

I am pretty sure the reason the comparison is failing is because internally the domain is set as {0, …, n-1} and basing the comparisons on that. So the permutations for A and B are permutations on [0, 1] internally but for C and D are on [0, 2]. When this implementation was done, it just did not take into account someone giving a “strange” domain (which also affects what the identity map is). This has been known to cause issues in the past.

I made the assumption that <= was equivalent to is_subgroup(), but that is not the case (surprisingly to me). The == is by subgroup. There is also an oddity with the symmetry:

sage: D >= C
True
sage: C >= D
True

This might also be an upstream issue with GAP.

[jukkakohonen]

For my part I have made it very sure that I address facts, not other people or what I imagine to be their assumptions, in this discussion.

• Perhaps I may clarify that it was not my idea that permutation group equality would be based on "the permutations themselves, not the domain". I merely pointed out that they do not work that way even now.

• Perhaps I may clarify that it was not my idea that permutation group equality would be based on the repr text. I merely pointed out that they do not work that way even now.

• Perhaps I may clarify that it was not my idea that A == B is A <= B and B <= A.

So I find strange that I am told, in a commanding voice, to "stop assuming". It was not I who was assuming.

About the equality notion being documented, I guess I just have to take your word that it is, somewhere. Although in Permutation groups I am finding absolutely nothing about when would permutation groups be defined equal, or how they compare. In the source file permgroup.py, not visible in the published documentation, the method __rich_cmp__ has a comment about the subgroups. Even that comment says nothing about domains. It just says the ordering of groups is whatever it is in GAP. Some may call this "documenting" the equality notion, I do not.

As said, I made sure of keeping to the plain facts, and presenting evidence for what I claim. I can see that there is a different kind of discussion culture here at play. I find Travis's response unwelcoming and impolite.

I apologize for bringing out these shortcomings of SageMath. I find this discussion unfitting and, for my part, will end it here.

[dimpase]

Good morning, I apologise for somewhat abrasive tone here. No need to apologise on your side here, you did very well by bringing up the bug(s) here.
I agree with you that these have to be fixed, and let us try to do this.

Perhaps it's also lost in translation here, but there is no commanding tone, it's more of an apology for the mess here. "Please don't assume that Sage is doing things in such and such way" is an acknowledgement that not all is good, it's not a command to stop talking about it!

The background for this mess is the way GAP (https://www.gap-system.org), which is the backend called for many operations, treats permutation groups. For GAP, permutations all live in the symmetric group of a very big degree, and so their domain is always the natural numbers.
Sage's attempt to bolt on finite domains here is, as you rightly point out, not very good.

[dimpase]

@tscrim - what kind of a potential issue with GAP you have in mind?
I think what GAP does is very clean - the domain is always the set of natural numbers, all permutation groups are subgroups of the finitary infinite symmetric group, and GAP's IsSubgroup() works as expected in such a context.

[dimpase]

@tscrim - what's the main use of domain for permutation groups in Sage? Maybe we should just abolish it, and follow GAP? This of course will be a serious change, but it might be actually less intrusive than fixing it...

[dimpase]

I would appreciate it if you could tone done the amount of sensationalism.

@tscrim - please... It's a quite bad problem, acknowledge it.

[mantepse]

@tscrim - what's the main use of domain for permutation groups in Sage? Maybe we should just abolish it, and follow GAP? This of course will be a serious change, but it might be actually less intrusive than fixing it...

It seems to me that the situation is somewhat similar to the vertex labels of graphs or posets. Some applications need arbitrary vertex labels, for example, I want to define a poset (or a graph) on some set of combinatorial objects, think of the flip graph of triangulations.

Similarly, I (personally) want to have permutation groups on arbitrary (hashable) domains - that's what combinatorial species should be.

I don't know whether standardising the labels should be the job of the permutation group class (or graph class), or not. A similar question applies to, for example SetPartition or Permutation. It seems to methat sage is quite inconsistent with respect to this question, and I would very much like to have this improved.

[dimpase]

@mantepse - I agree. What GAP does is OK for group theory itself, but for applications it's suboptimal, and Sage not doing the mathematically correct things while e.g. comparing permutation groups with explicitly given domains is a big problem.

The latter is the cause of the original problem posted here.

[tscrim]

@tscrim - what kind of a potential issue with GAP you have in mind? I think what GAP does is very clean - the domain is always the set of natural numbers, all permutation groups are subgroups of the finitary infinite symmetric group, and GAP's IsSubgroup() works as expected in such a context.

I am not sure. There seems to be a symmetry issue as I mentioned as we have C >= D giving us something different than D <= C. However, do have

sage: C._libgap_().IsSubgroup(D._libgap_())
true
sage: D._libgap_().IsSubgroup(C._libgap_())
true
sage: C._libgap_() >= D._libgap_()
True
sage: C._libgap_() <= D._libgap_()
True

So I don't understand what is going on here from just looking at the code and running examples. It doesn't seem like the bug is within GAP from this. I am very confused why this is not working.

[dimpase]

my guess would be UniqueRepresentation somewhere, caching with data missing - just like in IntegerVectorsModPermutationGroup.

[jukkakohonen]

It is not very difficult to see that PermutationGroup_generic.__richcmp__ is asymmetric as it is coded (Sage 10.2).

        if self is right:
            return rich_to_bool(op, 0)    # Branch 1

        gSelf = self._libgap_()
        gRight = right._libgap_()
        if op in [op_EQ,op_NE]:
            return gSelf._richcmp_(gRight, op)    # Branch 2

        if gSelf.IsSubgroup(gRight):
            return rich_to_bool(op, 1)    # Branch 3
        if gRight.IsSubgroup(gSelf):
            return rich_to_bool(op, -1)    # Branch 4

Suppose we are performing one of the comparisons self <= right or self >= right, in a situation where self is not right and both are subgroups of each other. Because they are not the same object, branch 1 is not executed. Because the comparison is not op_EQ or op_NE, branch 2 is not executed either.

Then the code always goes to branch 3, and the old-style comparison result 1 effectively says that self > right. Meaning, if the comparison being performed is <=, it is False, and if it is >=, it is True.

Because both groups are subgroups of each other, it does not matter which one is left and which one is right. If A and B are not same and are subgroups of each other, then A <= B and B <= A are both false, and A >= B and B >= A are both true.

This is certainly well-defined and documented, if the definition is "the result of a comparison is whatever the comparison code does" and the documentation is "read the source".

[dimpase]

Indeed. :) I don't disagree with you, but there are people who use the permutation groups and might expect them to be equal as their repr() does not reference the domain:

sage: PermutationGroup([(1,2)], domain=[1,2,3])
Permutation Group with generators [(1,2)]

This just might also end up breaking a fair bit of code in the wild. I guess we could get some sense of this by what breaks within library code. It is just such a change we might need to approach with some caution. (We can fix the bug at hand another way at least.)

How about adding domain to repr() ? I imagine it's a cosmetic change, no functionality depends on it, doctests will need fixes, but that's OK.

[mantepse]

I tried a slightly less intrusive change:

diff --git a/src/sage/groups/perm_gps/permgroup.py b/src/sage/groups/perm_gps/permgroup.py
index b0083394cb..aa9b469506 100644
--- a/src/sage/groups/perm_gps/permgroup.py
+++ b/src/sage/groups/perm_gps/permgroup.py
@@ -2075,7 +2075,9 @@ class PermutationGroup_generic(FiniteGroup):
             sage: AlternatingGroup(4)._repr_()
             'Alternating group of order 4!/2 as a permutation group'
         """
-        return "Permutation Group with generators %s" % list(self.gens())
+        if self._has_natural_domain():
+            return "Permutation Group with generators %s" % list(self.gens())
+        return "Permutation Group with generators %s and domain %s" % (list(self.gens()), self.domain())
 
     def _latex_(self):
         r"""

This just produces 6 obvious doctests failures in groups, all in groups/perm_gps/permgroup.py, a few in combinat/designs/incidence_structures.py, a few in sage/geometry/polyhedron/.

In any case, this seems like a very obvious improvement.

However, I think we should also insist that two permutation groups are only equal if their domains are the same - and add a relabel method.

[jukkakohonen]

I tried a slightly less intrusive change:

•    return "Permutation Group with generators %s and domain %s" % (list(self.gens()), self.domain())
  

Reminds me of something I've been wondering, and did not find documented. (Yeah, it's just me. It certainly is documented somewhere.)

Are SageMath objects supposed to have repr texts that uniquely determine the value of the object?

In Python it is documented that

For many types, this function makes an attempt to return a string that would yield an object with the same value when passed to eval(), otherwise the representation is a string enclosed in angle brackets that contains the name of the type of the object together with additional information often including the name and address of the object.

I wonder if SageMath simply inherits the same idea from Python, or if there are house rules.

[mantepse]

Are SageMath objects supposed to have repr texts that uniquely determine the value of the object?

No, only if this would be easily done and helpful. For example:

sage: Graph([[1,2,3], [(1,2), (2,3)]])
Graph on 3 vertices

If I understand correctly, the focus is on usability for mathematicians, and - as a mathematician - I can say, that works well for me.

[mantepse]

Doesn't this mean that for domains other than {1,...n} we are only able to test equality up to conjugacy. I admit I'm not sure. With 'Set' I am quite sure that we cannot guarantee a fixed order, can we guarantee it with 'set'?

[dimpase]

no, that's certainly not desirable.

Maybe @dcoudert can share some wisdom from fixing these issues in Graph() ?

[dimpase]

Doesn't this mean that for domains other than {1,...n} we are only able to test equality up to conjugacy. I admit I'm not sure. With 'Set' I am quite sure that we cannot guarantee a fixed order, can we guarantee it with 'set'?

If we cannot even consistently test two finite S(s)ets for equality, it's pretty much end of the project...

[mantepse]

We can test sets for equality, but I m less sure that we can put a total order on a set consistently.

[dcoudert]

no, that's certainly not desirable.

Maybe @dcoudert can share some wisdom from fixing these issues in Graph() ?

I have not fully read this long thread, so I'm not fully sure of the question ;)

In graphs, equality takes the domain (i.e., the labels of the vertices) into account. This is different from isomorphisms.
This is clearly written in the documentation of __eq__:

   Two graphs are considered equal if the following hold:
      * they are either both directed, or both undirected;

      * they have the same settings for loops, multiedges, and
        weightedness;

      * they have the same set of vertices;

      * they have the same (multi)set of arrows/edges, where labels of
        arrows/edges are taken into account if *and only if* the
        graphs are considered weighted. See "weighted()".

   Note that this is *not* an isomorphism test.

[dimpase]

How are sets of vertices and (directed) edges implemented? Are these set(), or Set(), or some other types?

Is there an internal conversion to a canonical {0,1,...,n} domain?

[jukkakohonen]

This is because the domains, being two Sets, can have their elements listed in different order even though the Sets themselves compare equal. Then the GAP embeddings are different and the groups compare inequal.

I'd consider this a bug (how often does it pop up - I don't get this error if I tried two times or so).

It happens all the time. I ran the script 1000 times consecutively (each time a new Sage invocation) and got 42 different results.

You can see the Set behaviour more directly by just running list(Set("abcd")) in each new Sage session. Or set if you prefer, they give random order too.

Here are three consecutive runs, with 1's marking equality and 0 inequality between A, B, C, D, S, T. The order of the elements in the Sets determines whether the single swap ("a","c") happens to be in the same two positions in different permutation groups.

kohonej1@t30200-lr248:~/sage/src/sage/combinat$ ~/sage/sage madness.sage
Comparing group equality
[1, 1, 1, 1, 0, 0]
[1, 1, 1, 1, 0, 0]
[1, 1, 1, 1, 0, 0]
[1, 1, 1, 1, 0, 0]
[0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 1]
kohonej1@t30200-lr248:~/sage/src/sage/combinat$ ~/sage/sage madness.sage
Comparing group equality
[1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 0]
[1, 1, 1, 1, 0, 1]
kohonej1@t30200-lr248:~/sage/src/sage/combinat$ ~/sage/sage madness.sage
Comparing group equality
[1, 1, 0, 0, 0, 0]
[1, 1, 0, 0, 0, 0]
[0, 0, 1, 0, 0, 0]
[0, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 1]

[jukkakohonen]

In graphs, equality takes the domain (i.e., the labels of the vertices) into account. This is different from isomorphisms. This is clearly written in the documentation of __eq__:

   Two graphs are considered equal if the following hold:
...

Very good. That is what I call defining something in Sage.

The situation with the permutation group equality falls far short of this.

[dcoudert]

How are sets of vertices and (directed) edges implemented? Are these set(), or Set(), or some other types?

This is quite complex, depends on the backend (dense, sparse, immutable, etc.) and some parts remain unclear to me.
For vertices, we internally associate each vertex to an integer that is the smallest unused integer.
If the graph is static, we can easily associate each vertex label to an integer in range 0..n-1. But for mutable graphs, we have to take into account the addition and removal of vertices so the integer associated to a vertex can be very large compared to the actual number of vertices in the graph (e.g., create a graph with 1000 vertices and then remove 999 of them. The remaining vertex may be associated with integer 999).

For edges, we also have different data structures for static/dynamic, sparse/dense, (im)mutable (di)graphs.

Is there an internal conversion to a canonical {0,1,...,n} domain?

Only for static (immutable) graphs.

[mantepse]

Doesn't this mean that for domains other than {1,...n} we are only able to test equality up to conjugacy. I admit I'm not sure. With 'Set' I am quite sure that we cannot guarantee a fixed order, can we guarantee it with 'set'?

I think I should clarify my statement: If we exclusively use gap to check for equality and we do not have the same total ordering of a set (we shouldn't use Set anyway) throughout a sage session, then we can test only up to conjugacy.

However, it may well be that python guarantees that list(set(X)) always produces the same result within one session, I don't know.

I think it doesn't matter that the ordering differs in different sessions.

[jukkakohonen]

Doesn't this mean that for domains other than {1,...n} we are only able to test equality up to conjugacy. I admit I'm not sure. With 'Set' I am quite sure that we cannot guarantee a fixed order, can we guarantee it with 'set'?

If we cannot even consistently test two finite S(s)ets for equality, it's pretty much end of the project...

Surely we can test two finite S(s)ets for equality. And if they are equal, presumably it means they contain the same objects. If you have X == Set("abcd") and Y == Set("abcd"), you also have X==Y and each element of X appears, just once, in Y.

Sure, if you list X and Y independently, in arbitrary orders, and map the elements to integers in that order, your "a" of X can map to a different integer than your "a" of Y. That is what happens now, and leads to inconsistency (really equal groups becoming inequal in GAP).

But I don't see anything preventing just choosing a common mapping when performing the equality test: If you list X and get ["b","d","a","c"], mapping them in that order to 1,2,3,4, surely you can use the same mapping for the elements of Y. Then the elements of your two groups are mapped consistently: if "a" from X maps to 3, then also "a" from Y maps to 3.

This, of course, relies on the two domains having the same elements.

If someone wants to define some kind of "consistent" mapping from two arbitrarily different sets into small integers, that is going to be a very different kind of a project.

[jukkakohonen]

However, it may well be that python guarantees that list(set(X)) always produces the same result within one session, I don't know.

It does not guarantee that two sets that are equal would have equal lists in one session. This is consecutive commands on one session:

sage: X = set("aceh")
....: Y = set("heca")
....: X==Y
....: list(X)
....: list(Y)
....: list(X)==list(Y)
True
['c', 'e', 'a', 'h']
['e', 'c', 'a', 'h']
False

If two groups have domains that are equal (==), and one wants to convert them to GAP in a consistent manner, the point is not to hope that they happen to be listed in the same order (they won't). The point is to map the same elements to the same integers.

[mantepse]

@jukkakohonen, excellent, then it is clear that the mapping must be done in PermutationGroup_generic.__richcmp__. That is, essentially, compute the permutation Permutation([self._domain_to_gap[self._domain_from_gap[i]] for i in range(1, n+1)]) and conjugate by that. Do I understand correctly?

As the other experiment (printing the domain if it is not {1,...,n}) shows special domains are rarely used, mostly for the automorphism group of a graph. I am guessing that especially there we actually would like to take the domain into account.

[jukkakohonen]

@jukkakohonen, excellent, then it is clear that the mapping must be done in PermutationGroup_generic.__richcmp__. That is, essentially, compute the permutation Permutation([self._domain_to_gap[self._domain_from_gap[i]] for i in range(1, n+1)]) and conjugate by that. Do I understand correctly?

I'm not well familiar with the call interface between Sage and GAP, but something like that. Indeed it seems it must be in __richcmp__, because that is the place where we have access to the two groups being compared, so we can simply match the elements between the domains.

If each group creates their own GAP mapping (from domain elements to integers) separately, then it seems much more difficult to ensure that each group will choose the same mapping. If one of them maps "a" to 17, then how does the other know that -- if their domains are just equal (==), and not same (is)? This is possible if the domain has a way to list the elements in a canonical order.

Perhaps this code snippet explains what I'm after (or perhaps it was clear already):

sage: G = PermutationGroup([("a","c")], domain=set("aceh"))
sage: H = PermutationGroup([("a","c")], domain=set("heca"))
sage: list(G.domain())
['c', 'a', 'e', 'h']
sage: list(H.domain())
['c', 'h', 'a', 'e']
sage: g = G.gap()
sage: g
Group([ (1,2) ])
sage: G._domain_to_gap
{'c': 1, 'a': 2, 'e': 3, 'h': 4}

We see that the GAP mapping from G happens to map 'c' to 1. So, simply make a GAP mapping from H that maps 'c' to 1. In fact map all elements of H to integers using G._domain_to_gap.

Then we have the two GAP objects which should have consistently the same integers for the same elements both in G and H.

Not sure what is the best low-level technique of doing it. Do we need to create a new GAP object just for the purpose of the richcmp, and then throw it away? H might already have a GAP object but it could be using different numbering than the object in G.

[jukkakohonen]

One point I should mention: Only one of the two "directions" of confusion is really harmful with respect to what this issue was originally about, namely IntegerVectorsModPermutationGroup thinking that two groups are the same when they aren't.

If a mistake happens the other way, that two groups compare inequal while they "should" be equal (by whatever reasoning), the result is that IntegerVectorsModPermutationGroup simply does the calculations separately (creating a new strong generating system and whatever). It will work correctly, just a bit slower than if it could use the cached instance.

Thus, although for many other reasons it might be nice to have a permutation group equality machinery in Sage that is consistent by all accounts, it is not necessary for fixing this particular bug. For this bug we just need something that certainly differentiates the groups that are not "really" equal. Either by fixing group equality at least in that direction, or even more easily, make a local change in IntegerVectorsModPermutationGroup.

Seeing what a can of worms it is to "really" fix permutation group equality, a local change might be the best option for now. Then open a new issue for discussing the general notion.

[mantepse]

I don't think it is a good idea to postpone the fix for equality, if there is consensus. I don't see a can of worms, just an oversight.

[jukkakohonen]

I have no informed opinion on that (when to fix equality and by what protocol). Certainly it is something that I would like to have, but I trust others will have a better hunch on just how intrusive it is going to be. Also, there could be performance issues in creating a new GAP object within __richcmp__ just for the sake of one comparison? I don't have data on how expensive it is to create them.

In any case the equality fix deserves to be an issue with a more prominent name than "IntegerVectorsModPermutationGroup confuses group whose domains are different", no?

[dimpase]

at the moment (and already for a while, cf #26902) Sage has 2 interfaces to GAP

1. old and slow expect interface (.gap, _gap_, etc)
2. fast interface via libgap (.libgap, _libgap_, etc)

The plan is to move to libgap, largely done, but not quite. Old interface should be avoided.
I think that PermutationGroup already uses libgap, so the overhead using it is minimal if any

• unless GAP is not used at all, IIRC this is also possible, as GAP is slower on some tasks compared to Cython (basically C with Python syntax), so people wanted to use Cython.

[dimpase]

note that _domain_to_gap = {key: i+1 for i, key in enumerate(self._domain)} - i.e. there is no GAP calls here, it's just Python iteration

[mantepse]

@dimpase I don't see how constructing a gap group can be avoided if pi = Permutation([self._domain_to_gap[self._domain_from_gap[i]] for i in range(1, n+1)]) is not the identity. If it's not we have to conjugate the other.gapj() with pi, if I'm not mistaken.

NB: PermutationGroup_generic.conjugate ignores the domain (and only allows PermutationGroupElement, i.e., permutations with domain 1,...,n as input). This should also be fixed.

[jukkakohonen]

If the consensus is to fix the equality (to respect domains, and also other bug fixes like the GAP encoding), a couple of questions:

• Does it entail fixing also the subgroup relation to respect domains? (Currently SymmetricGroup(2) is a subgroup of SymmetricGroup(3), and trivial groups are always subgroups both ways regardless of domain).
• How exactly is "the same domain" defined? Do they have to be equal objects or is it enough that they contain the same elements? Could be different types [1,2,3] and set((1,2,3)), or ordered lists in different orders. I guess we could again look how Graphs did it.

[mantepse]

* How exactly is "the same domain" defined? Do they have to be equal objects or is it enough that they contain the same elements? Could be different types `[1,2,3]` and `set((1,2,3))`, or ordered lists in different orders. I guess we could again look how `Graph`s did it.

Shouldn't the domain be a set? I see that currently it is a FiniteEnumeratedSet, but that looks like a mistake to me.

[jukkakohonen]

Shouldn't the domain be a set? I see that currently it is a FiniteEnumeratedSet, but that looks like a mistake to me.

Oh I see, whatever the user is giving is always converted to the same type. That makes sense, so we don't need to worry about different types of domain objects. Now FiniteEnumeratedSet is ordered, so one needs to decide (and document) whether e.g. symmetric groups on [1,2,3] and on [3,1,2] are the same group or not.

[dimpase]

IMHO the domain in permutation groups theory is a set, mathematically speaking.

Also, I think I explained above that we cannot fix equality without fixing inequalities, as we want $B\leq A\leq B$ to be equivalent to $A=B$.

[dimpase]

It seems that strict containment $A\lt B$ might be left alone, as inequality of domains here doesn't lead to contradictions.
But this is confusing to the user.

[jukkakohonen]

I have now added a warning of this issue in the docstring of IntegerVectorsModPermutationGroup.

[mantepse]

IMHO the domain in permutation groups theory is a set, mathematically speaking.

I just realized: the reason for the domain being a FiniteEnumeratedSet is that we allow one-line-notation for group elements:

    Permutation groups can work on any domain. In the following
    examples, the permutations are specified in list notation,
    according to the order of the elements of the domain::

        sage: list(PermutationGroup([['b','c','a']], domain=['a','b','c']))
        [(), ('a','b','c'), ('a','c','b')]
        sage: list(PermutationGroup([['b','c','a']], domain=['b','c','a']))
        [()]
        sage: list(PermutationGroup([['b','c','a']], domain=['a','c','b']))
        [(), ('a','b')]