Opened 4 years ago

Bug in comparison of finite matrix groups

Reported by: Owned by: davidloeffler major sage-8.1 group theory N/A

Here are two matrix groups over a finite ring which compare as unequal, despite having the same elements:

sage: gens1 = ([52,0,0,103],[104,0,0,104],[1,1,0,1])
sage: gens2 = ([52, 0, 0, 103],[59,0,0,89],[104,0,0,104],[1,1,0,1])
sage: H1 = MatrixGroup(list(matrix(Zmod(105), 2,2, u) for u in gens1))
sage: H2 = MatrixGroup(list(matrix(Zmod(105), 2,2, u) for u in gens2))
sage: H1 == H2
False
sage: sorted(list(x.matrix() for x in H1)) == sorted(list(x.matrix() for x in H2))
True

(This was originally discovered because it was getting called from the equality-testing code of GammaH groups. This is no longer the case, but the underlying bug remains.)

comment:1 Changed 4 years ago by chapoton

This works for me in 8.1.rc3 (ie G1==G2). Which version of sage are you using ?

comment:2 Changed 4 years ago by davidloeffler

It fails in the current stable release (8.0) but I can confirm that it also works for me with 8.1.rc2.

Looking at the git log, it seems that this got fixed as a side-effect of one of your commits, b0f1552f8e07d80c529f349fa3ce2898636d65f4 (there is no trac ticket number in the commit message, but the message says something about Python3 and cmp).

There is still some shadow of the bug left in 8.1.rc2, but it is much harder to expose:

sage: G1 = GammaH(105, [52, 104])
sage: G2 = GammaH(105, kronecker_character_upside_down(105).kernel())
sage: G1.image_mod_n() == G2.image_mod_n()
False
Last edited 4 years ago by davidloeffler (previous) (diff)

comment:3 Changed 4 years ago by tscrim

FYI - the ticket is #23150 (I just searched for the commit on trac).

comment:4 Changed 4 years ago by davidloeffler

Actually I was wrong about what precisely it was that fixed this issue. Ticket #23150 was already merged in 8.0, in which the bug is still present, so whatever fixed this, it wasn't that ticket. Anyway, the point is that something happened between 8.0 and 8.1.rc2 which fixed this -- it doesn't matter what! :-)

comment:5 Changed 4 years ago by chapoton

could you please recycle the ticket (title and description) for the remaining bug ?

comment:6 Changed 4 years ago by davidloeffler

• Component changed from modular forms to group theory
• Description modified (diff)
• Summary changed from nonsensical comparison of GammaH groups to Bug in comparison of finite matrix groups

comment:7 Changed 4 years ago by davidloeffler

• Description modified (diff)

comment:8 follow-up: ↓ 9 Changed 4 years ago by davidloeffler

This behaviour probably counts as "broken by design", since the docstring for the method FinitelyGeneratedMatrixGroup_gap.__richcmp__ states

"We treat two matrix groups as equal if their generators are the same in the same order."

This is a very strange notion of "equality" if you ask me!

comment:9 in reply to: ↑ 8 Changed 4 years ago by tscrim

This behaviour probably counts as "broken by design", since the docstring for the method FinitelyGeneratedMatrixGroup_gap.__richcmp__ states

"We treat two matrix groups as equal if their generators are the same in the same order."

This is a very strange notion of "equality" if you ask me!

It's not uncommon for objects to compare equality differently than isomorphism. For example, two graphs can be not equal but isomorphic, or two symbolic expressions can give the same function but not be equal (under ==). This is done because it can be expensive to compute isomorphism, whereas a general quick trivial "equals" can get somewhat far. So this is a feature, not a bug. If you need real isomorphism testing, then use is_isomorphic.

comment:10 follow-up: ↓ 11 Changed 4 years ago by davidloeffler

This isn't about isomorphism testing. Both H1 and H2 are, by definition, subgroups of the same ambient group, namely GL2(Z / 105 Z). I claim there is one and only one sensible way to define what it means for two subgroups of the same group to be "equal".

comment:11 in reply to: ↑ 10 ; follow-up: ↓ 13 Changed 4 years ago by tscrim

This isn't about isomorphism testing. Both H1 and H2 are, by definition, subgroups of the same ambient group, namely GL2(Z / 105 Z). I claim there is one and only one sensible way to define what it means for two subgroups of the same group to be "equal".

No, there is not. What I think you are asking for is secretly a check for isomorphism and taking advantage of the extra structure, but this can still be very expensive to compute. Imagine the subgroups are big, testing all elements are the same means iterating over the subgroups (which in general means also storing all of the elements) and then comparing equality of each of the set of elements (rather than by looking at sorted lits).

I find that I am usually constructing algebraic objects, such as groups, where it is sufficient to check the generating set. There has been other points in Sage where Python == versus math = differs and causes confusion, but there could be some major speed regressions with changing the comparison code to be closer to math =.

I understand why you disagree with == returning false, but IMO it is not practical to have a test that is basically isomorphism testing. However, you are free to ask about this on sage-devel and if there is a consensus for changing this, then I will do the review. My opinion is that either you should be calling is_isomorphic (which could have a special case for when two groups are finite subgroups of the same group) or do the same functionality in a new method is_equal(_subgroup or other name).

comment:12 follow-up: ↓ 14 Changed 4 years ago by davidloeffler

This isn't about isomorphism testing. Both H1 and H2 are, by definition, subgroups of the same ambient group, namely GL2(Z / 105 Z). I claim there is one and only one sensible way to define what it means for two subgroups of the same group to be "equal".

No, there is not. [...] Imagine the subgroups are big, testing all elements are the same means iterating over the subgroups (which in general means also storing all of the elements) and then comparing equality of each of the set of elements (rather than by looking at sorted lits).

I wasn't talking about algorithms. I'm saying there's one and only one mathematically meaningful interpretation of the relation of "equality" in this case, which is "having the same elements". Of course there may be good and bad algorithms to compute this relation; listing all elements is probably a bad algorithm; and it may be the case that there is no good algorithm computing this relation, and one has to make do with an algorithm that checks some other relation instead. But I claim that no other relation deserves to be called "equality" in this setting.

If you disagree and want to close this ticket, then go ahead, I'm not that bothered.

comment:13 in reply to: ↑ 11 Changed 4 years ago by jdemeyer

No, there is not. What I think you are asking for is secretly a check for isomorphism and taking advantage of the extra structure, but this can still be very expensive to compute.

I agree with David that this is not an isomorphism check. It is a check of having the same elements. Two matrix groups can be isomorphic but not equal (say, they are both cyclic groups of the same order but containing different matrices).

comment:14 in reply to: ↑ 12 Changed 4 years ago by tscrim

Right, this is a pure equality check. Sorry.

This isn't about isomorphism testing. Both H1 and H2 are, by definition, subgroups of the same ambient group, namely GL2(Z / 105 Z). I claim there is one and only one sensible way to define what it means for two subgroups of the same group to be "equal".

No, there is not. [...] Imagine the subgroups are big, testing all elements are the same means iterating over the subgroups (which in general means also storing all of the elements) and then comparing equality of each of the set of elements (rather than by looking at sorted lits).

I wasn't talking about algorithms. I'm saying there's one and only one mathematically meaningful interpretation of the relation of "equality" in this case, which is "having the same elements". Of course there may be good and bad algorithms to compute this relation; listing all elements is probably a bad algorithm; and it may be the case that there is no good algorithm computing this relation, and one has to make do with an algorithm that checks some other relation instead. But I claim that no other relation deserves to be called "equality" in this setting.

What I am saying is there are good reasons for Python == to not always be the same as mathematical =. I agree that there is only one mathematically equals, but I think that would be ineffective for subgroups given by a set of generators. With the example in the description:

sage: _ = H1.gap(), H2.gap()
sage: %time H1.gap() == H2.gap()
CPU times: user 1.7 s, sys: 120 ms, total: 1.82 s
Wall time: 1.82 s
True

So GAP does mathematical equality testing, but as you can see, it takes a lot of time even for a somewhat small group (2520 elements). So algorithms are part of the question in my mind as it goes to usability. I cannot see a better algorithm other than listing all of the elements of at least one group and checking the generators of the other are included (with appropriate short-circuiting for returning True), but we can always just pass this off to GAP when it will take it.

I think we should give the user more control over how strict they want equality to be tested. So if you insist on making == be mathematical equals, then you need to provide a method is_trivially_equal. Yet, my experience is that in most cases if the generators are different, than the groups are different. Although in fairness, I work with Coxeter groups, which have extra structure, can utilize UniqueRepresentation, and would not be affected by this change.

Perhaps a good comparison is what is done with permutation groups. For them, it feeds it off to GAP and lets GAP return the equality. So maybe what we should do is just let GAP handle things and hope that the cases where the equality-by-gens-check is not a common occurrence that people are relying on.

comment:16 Changed 4 years ago by wuthrich

Here is another annoying bug. It may or may not be related to this ticket.

sage: G = GL(2,5)
sage: g = G( matrix([[1,0],[0,4]]))
sage: H = G.subgroup([g])
sage: g in H
False

In any case, it makes me dream of going back to magma.

Note: See TracTickets for help on using tickets.