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

• [X] I have searched the existing issues for a bug report that matches the one I want to file, without success.
• [X] 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.

[jukkakohonen]

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.

It is exactly as my learned friends say here.

For many algebraic and/or combinatorial objects, there exists a definite distinction between labeled and unlabeled objects (the latter being, in effect, isomorphism classes of the former). For e.g. graphs this is well known. Somewhere in the middle is the idea of having a "standard" domain, often integers from 0 to $n$ or from 1 to $n$. This may be useful for abstract work, and for applications one may embellish the object with arbitrary labels.

All of this is well-known. And it should be clear that when implementing such an object, one has to make a clear decision between "standard domain", "arbitrary domain", or "up to isomorphism". It may be possible to do mix them in one class -- so that "by default" it is using the standard domain, but one can change it to "arbitrary domain". However, if that is done, it cannot (meaningfully and usefully) be done halfway. If one decides that permutation groups can have arbitrary domains such as [1,3,10] or ['a', 'c', 'z'], one cannot just go on ignoring the domain for half of the methods -- such as equality, or subgroup relation.

[jukkakohonen]

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

This is certainly a possible interpretation, and perhaps a useful one -- if one views the "repr" as a concise reminder of what kind of object it is. Indeed a "full" representation might often be unseemly.

If this is the received meaning, I sure hope it is documented somewhere. Is it?

If it is documented that way, then nobody should expect that two objects labeled "Permutation Group with generators [(1,2)]" would or should be equal.

I wonder how the Python description (otherwise the representation is a string enclosed in angle brackets that contains the name of the type of the object together with additional information) is faring here.

[mantepse]

@jukkakohonen, I appreciate you are having fun here, but I must say that I do not share this kind of humour. I am not interested in working in this kind of atmosphere.

[jukkakohonen]

@jukkakohonen, I appreciate you are having fun here, but I must say that I do not share this kind of humour. I am not interested in working in this kind of atmosphere.

What? I am trying to query about what is documented and what is not. It is no humour. It is a serious thing whether key assumptions, such as what a repr text is supposed to be, are documented. Or what one can assume based on repr text being equal or not. If they are documented, perhaps someone can tell where. If not, perhaps we can agree that indeed they are not documented.

[dimpase]

@jukkakohonen, I appreciate you are having fun here, but I must say that I do not share this kind of humour. I am not interested in working in this kind of atmosphere.

I don't see where you see humour there. It's probably all stems from a misunderstanding that repr() and UniqueRepresentation have anything to do with each other (they don't AFAIK)

[dimpase]

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".

As you see, it's easy to add a check for equality of domains of self and right.

[jukkakohonen]

As you see, it's easy to add a check for equality of domains of self and right.

I believe it is! At least, it is easy to do. I admit it is a valid concern if some existing code would be broken by the sudden change in the semantics of permutation group "equality".

On the other hand, given that the current semantics of equality are so vague (and -- may I say it aloud? -- erratic and undocumented), it would be a bit surprising if there existed a lot of code really relying on these particular vague semantics.

[jukkakohonen]

Here is a nice self-test to verify whether permutation group equality in Sage is (a) documented and (b) well-defined.

For (a), see if you can, based on the documentation, tell which of the following six groups are equal (==). No peeking at the code or tracing through the debugger. The external documentation of permutation groups is here, but well, we all know it does not define the equality, so let us be generous and allow reading the docstrings of the functions PermutationGroup_with_category.__richcmp__ and SymmetricGroup.__richcmp__, conveniently attached at the end of this message. Is equality defined there?

For part (b), try and see if you obtain the predicted results.

A = PermutationGroup([("a","c")], domain=Set("aceh"))
B = PermutationGroup([("a","c")], domain=Set("cahe"))
C = PermutationGroup([("a","c")], domain=Set("ecah"))
D = PermutationGroup([("a","c")], domain=Set("mace"))
S = SymmetricGroup(Set("ac"))
T = SymmetricGroup(Set("ce"))
GG = [A,B,C,D,S,T]

[[int(G==H) for G in GG] for H in GG]

Hint: Groups A,B,C have the same domain(), as can be verified with ==.

Hint 2: Do you think equality is transitive?

Hint 3: Predicting may be a tad difficult because the results are actually unpredictable. On my machine, with Sage 10.3.beta0, I have so far obtained 42 different results on different Sage runs. By a "different result", I mean a different value of the list of the 36 pairwise comparisons.

Here are the docstrings of the two comparison functions from Sage 10.3.beta0. It may be helpful to read what they say about "domain".

sage: ?PermutationGroup_generic.__richcmp__
Signature:      PermutationGroup_generic.__richcmp__(self, right, op)
Docstring:     
   Compare "self" and "right".

   The comparison extends the subgroup relation. Hence, it is first
   checked whether one of the groups is subgroup of the other. If this
   is not the case then the ordering is whatever it is in GAP.

   Note:

     The comparison does not provide a total ordering, as can be seen
     in the examples below.

   EXAMPLES:

      sage: G1 = PermutationGroup([[(1,2,3),(4,5)],[(3,4)]])
      sage: G2 = PermutationGroup([[(1,2,3),(4,5)]])
      sage: G1 > G2 # since G2 is a subgroup of G1
      True
      sage: G1 < G2
      False

   The following example shows that the comparison does not yield a
   total ordering:

      sage: H1 = PermutationGroup([[(1,2)],[(5,6)]])
      sage: H2 = PermutationGroup([[(3,4)]])
      sage: H3 = PermutationGroup([[(1,2)]])
      sage: H1 < H2 # according to GAP's ordering
      True
      sage: H2 < H3 # according to GAP's ordering
      True
      sage: H3 < H1 # since H3 is a subgroup of H1
      True

sage: ?SymmetricGroup.__richcmp__
Signature:      SymmetricGroup.__richcmp__(self, x, op)
Docstring:     
   Fast comparison for SymmetricGroups.

   EXAMPLES:

      sage: S8 = SymmetricGroup(8)
      sage: S3 = SymmetricGroup(3)
      sage: S8 > S3
      True

[tscrim]

@jukkakohonen You’re forgetting one very simple, fundamental fact: taking subgroups is a (very nice) partial order. Consequently, equality is well-defined and matches exactly what the documentation says.

What we either have a bug in the subgroup implementation (which is most likely) or there is a subtle issue with how we are defining what a subgroup is. It is a really bad idea to work under the assumption that the code is bug free.

I completely agree with what is happening with the __richcmp__ code, which is what was confusing me. However, your conclusions are completely wrong. The problem is that subgroup (clearly should have) is reflective, but richcmp_to_bool(op, -1) does not take into account this possibility (the -1 is saying the comparison is <). We need to have the comparison take this into account.

[jukkakohonen]

I have never here been under the assumption that the code is bug free. I know very well that it isn't.

I have heard the "there are people working with permutation groups" so let's not break the equality notion. Let me tell that I am one of those people, and I know from my experience that it is already broken, to the point that I simply must disable any attempt (in IntegerVectorsModPermutationGroup) to identify if groups are equal.

It is not just that there are bugs, but the whole notion of permutation group equality in SageMath is undefined and undocumented.

You can say "it is based on the subgroup" but then that is in turn undefined and undocumented in Sage. I do not see anything in, say, is_subgroup documentation about what it defines to be a subgroup if the domains are different. Perhaps it would make sense to define that if the domains are different, then the groups are not subgroups either way. But is does not say so. Perhaps for someone else it would make sense to define that SymmetricGroup([1,2]) is a subgroup of SymmetricGroup([1,2,3]), and that's what happens (in the code), even though the domains are different. But it does not say that in the documentation either.

In order to fix bugs, one would need a clear definition of the intended behaviour. Any attempt of such definition would at least have to acknowledge the notion of the domain of a permutation group. Indeed, some of the existing code tries to do it, and some does not, as anyone would know if they followed my advice of looking at those six example groups. The notions of how domain affects equality are in flat conflict between the two comparison methods. This is not so surprising because there is no common definition of that in Sage documentation.

I have been telling this, but mostly the response is flat out denial, unverified guesswork (<=), and simple false claims (like the notion being defined and documented in the first place, or that "they look at the permutations themselves, not the domain").

[dimpase]

I think it's obvious that equality of permutation groups needs to include equality of domains. The remaining question is how to deal with subgroup containment ($\leq$ or $<$, the opposite one should be symmetric). There are basically 2 options here I can think of

1. demand the equality of domains
2. demand containment of domains, i.e. $A\leq B$, or $A\lt B$, only if $dom(A) \subseteq dom(B)$.

We cannot ignore domains here, as $A\leq B$ and $B\leq A$ must imply $A=B$. However, I think that 2. is bad as well, as this means that we can have several subgroups $A$, $A'$ of $B$ with the same sets of permutations, which only differ in their domains - and this means potentially the same sort of trouble with UniqueRepresentation. This leaves 1. as the only choice.

@jukkakohonen - did you check whether starting to use domains in _richcmp_ leads to lots of doctests failures?

We also need to decide whether we can just change this code, or go via the deprecation route

[jukkakohonen]

I think it's obvious that equality of permutation groups needs to include equality of domains.

That would agree with the strict mathematical notion usually found in group theoretical texts, when they are defining what a permutation group is. Either they say it is a group $G$ whose elements happen to be permutations on a given domain $\Omega$, which makes them automatically different whenever the domains are different. (e.g. Cameron's Permutation groups, or Dixon and Mortimer). Or they go even more explicit and define a permutation group to be a pair $(G, \Omega)$ so it is even more explicit that $(G',\Omega') \ne (G,\Omega)$ if $\Omega' \ne \Omega$. (e.g. Encyclopedia of Mathematics)

Also, the strict mathematical definition of a subgroup entails that the subgroup's elements are permutations on the same domain. So, in this mathematical sense it is clear that e.g. $(S_2, \{1,2\})$ is not a subgroup of $(S_3, \{1,2,3\})$. And the permutation $(1,2)$ is not the same permutation as $(1,2)(3)$.

GAP, of course, deviates from this fundamentally. In GAP already two permutations are defined equal "if and only if they move the same points and if the images of the moved points are the same under the operation of both permutations." No notion of domain. This goes on with the equality of permutation groups.

Incidentally, this means that any attempt to "define" something in Sage by saying "it is whatever happens in GAP" is likely to dodge the issue of "how is this Sage object mapped to a GAP object" and is thus potentially an underdefinition.

Sage, in its current implementation, deviates from the mathematical definition on many accounts. We have, for example, SymmetricGroup([1,2].is_subgroup(SymmetricGroup([1,2,3])) even though the domains are different. The permutations that are elements of the groups are different (in the strict mathematical definition: they are functions that have different domains and codomains) but in Sage some of the permutations in those groups are actually equal as in ==.

Perhaps people think this lax subgroup definition is convenient. I don't disagree. But it has implications. For the lax subgroup definition to be true mathematically, you need to change some definitions. It is possible to provide alternative definitions (as we can see from what GAP does), but then one would need to do it all the way, and not rely on "duh, it's the common mathematical thing" when one has already decided to deviate from it.

The lax subgroup definition (and I don't even know exactly how much of it has been formally defined in SageMath, and how much just happens) has implications on group equality, of course.

@jukkakohonen - did you check whether starting to use domains in _richcmp_ leads to lots of doctests failures?

No, did not dare touch it that much quite yet.

We also need to decide whether we can just change this code, or go via the deprecation route

I am beginning to think that the issue of permutation group equality (and subgroup relation, and permutation equality, and...) is a bit too big to handle here, as a side effect of a particular bug. It would deserve its own issue, and hopefully one that begins with laying out the relevant definitions (from SageMath documentation), observing what they really say, what they don't say, what is just a common practice in SageMath, and so on. Trying to sort it out here is next to impossible. It is a mess; it is possible to clear a mess, but one would first need to acknowledge it.

[dimpase]

GAP, of course, deviates from this fundamentally. In GAP already two permutations are defined equal "if and only if they move the same points and if the images of the moved points are the same under the operation of both permutations." No notion of domain.

I tend to think of it as the domain is always there, it's just always $\mathbb{N}$.

[jukkakohonen]

I tend to think of it as the domain is always there, it's just always N.

Yes, that's what I meant (but failed to express). GAP clearly defines that permutations operate on positive integers, so yes, in the mathematical sense they are functions $Z+ \to Z+$, so that is the domain. I meant to say GAP has no notion of permutations having any other domain than that.

[jukkakohonen]

There is one aspect of equality comparison (or subgroup relations if you prefer) that has probably been missed by most, and is exemplified by my 6-group example above.

It is not really enough just to take the existing comparisons, and augment them with "must have same domain". That will solve "half" of the problem, by ensuring that different domain implies different group.

But there is the other direction: If two groups have the same domain (==) and the same generators and elements (==), does it mean that the groups are the same? Mathematically, and in my mind, it should. By current implementation, it does not. Even if A.domain() == B.domain(), there is no guarantee that they get mapped to the GAP integers in the same way. Just look at the first two groups

A = PermutationGroup([("a","c")], domain=Set("aceh"))
B = PermutationGroup([("a","c")], domain=Set("cahe"))

Clearly the domains are the same, the generators are the same, yet this can happen:

sage: A.domain() == B.domain()
True
sage: A.gens() == B.gens()
True
sage: list(A) == list(B)
True
sage: A==B
False

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.

An implementation issue, sure, but also a matter of definition: if equality (or subgroup) is defined by "whatever comes from GAP", then one must also fix the embedding, otherwise it is a non-definition.

[dimpase]

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). As far as I understand, Set does not have UniqueRepresentation, and the translation of domains to the canonical domain $\mathbb{N}$ doesn't always go well.

[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.