Subgroups of subgroups aren't subgroups?

[Peter Mueller]

I had a hard to track down error which eventually relied on sage permutation groups behave odd in regard to subgroups. A subgroup y of a subgroup x of g isn't always considered as a subgroup of g. Compare

sage: g = SymmetricGroup(2)

....: x = g.subgroup([])

....: y = x.subgroup([])

....: x == y

....: 

False

with

sage: G = gap(g)

....: X = G.Subgroup([])

....: Y = X.Subgroup([])

....: X == Y

....: 

True

A probably related strange phenomenon arises with subgroups of g only:

 sage: g = SymmetricGroup(3)

....: x = g.subgroup(['(1, 2)', '(2, 3)'])

....: y = g.subgroup(['(1, 3)', '(2, 3)'])

....: x == y; len({x, y})

....: 

True

2

On the Gap level, same subgroups given by different generators apparently get hashed correctly:

sage: gap.eval('G := SymmetricGroup(3);;')

....: gap.eval('U := Subgroup(G, [(1, 2), (2, 3)]);;')

....: gap.eval('V := Subgroup(G, [(1, 3), (2, 3)]);;')

....: gap.eval('Length(Set([U, V]))')

....: 

'1'

-- Peter Mueller

[Dima Pasechnik]

On Sun, Aug 16, 2020 at 11:44 AM 'Peter Mueller' via sage-support
<sage-s...@googlegroups.com> wrote:
>
> I had a hard to track down error which eventually relied on sage permutation groups behave odd in regard to subgroups. A subgroup y of a subgroup x of g isn't always considered as a subgroup of g. Compare
>
> sage: g = SymmetricGroup(2)
> ....: x = g.subgroup([])
> ....: y = x.subgroup([])
> ....: x == y
> ....:
> False
>

this seems to be a "GAP pexpect interface" bug:

sage: g = libgap.SymmetricGroup(2)
sage: x = g.Subgroup([])
sage: y = x.Subgroup([])
sage: x==y
True
sage: len({x,y})
1

> with
>
> sage: G = gap(g)
> ....: X = G.Subgroup([])
> ....: Y = X.Subgroup([])
> ....: X == Y
> ....:
> True
>
> A probably related strange phenomenon arises with subgroups of g only:
>
> sage: g = SymmetricGroup(3)
> ....: x = g.subgroup(['(1, 2)', '(2, 3)'])
> ....: y = g.subgroup(['(1, 3)', '(2, 3)'])
> ....: x == y; len({x, y})
> ....:
> True
> 2

I guess this has to do with Python hashing; objects are not checked
for `==` equality when you do {},
but for equality w.r.t. to certain internal representation:
sage: g = libgap.SymmetricGroup(3)
sage: x = g.Subgroup(libgap.eval('[(1, 2), (2, 3)]'))
sage: y = g.Subgroup(libgap.eval('[(1, 3), (2, 3)]'))
sage: z = g.Subgroup(libgap.eval('[(1, 3), (2, 3)]'))
sage: len(libgap.Set([x,y,z])) # so this is sane on GAP/libgap level
sage: len({x,y,z}) # but!
2
sage: x==y, y==z, x==z # while this makes sense
(True, True, True)

>
> On the Gap level, same subgroups given by different generators apparently get hashed correctly:
>
> sage: gap.eval('G := SymmetricGroup(3);;')
> ....: gap.eval('U := Subgroup(G, [(1, 2), (2, 3)]);;')
> ....: gap.eval('V := Subgroup(G, [(1, 3), (2, 3)]);;')
> ....: gap.eval('Length(Set([U, V]))')
> ....:
> '1'
>
> -- Peter Mueller
>

> --
> You received this message because you are subscribed to the Google Groups "sage-support" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-support...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-support/a18bc5e8-a1d0-4c8c-8f77-e47e7abc6e49o%40googlegroups.com.

[Nils Bruin]

On Sunday, August 16, 2020 at 4:22:22 AM UTC-7, Dima Pasechnik wrote:

I guess this has to do with Python hashing; objects are not checked
for `==` equality when you do {},
but for equality w.r.t. to certain internal representation:
sage: g = libgap.SymmetricGroup(3)
sage: x = g.Subgroup(libgap.eval('[(1, 2), (2, 3)]'))
sage: y = g.Subgroup(libgap.eval('[(1, 3), (2, 3)]'))
sage: z = g.Subgroup(libgap.eval('[(1, 3), (2, 3)]'))
sage: len(libgap.Set([x,y,z]))     # so this is sane on GAP/libgap level
sage: len({x,y,z})   # but!
2
sage: x==y, y==z, x==z # while this makes sense
(True, True, True)

No, it means that libgap breaks the __hash__/__eq__ contract in python. Python sets do not compare wrt. internal representation. They just assume that objects that test equal have equal hashes. When you can't compute a hash that respects equality, then you shouldn't make your object hashable. Given the variety of objects that libgap implements, I think libgap should not support hashing. It may be possible to skirt the rules a bit and make some nicer objects hashable, but if we're just going to allow hashing of everything, I think errors like this are unavoidable. Alternatively, we can implement a constant hash function for them. That would revert everything to equality testing, and would completely break performance in python.