generators given by as_permutation_group in the wrong order

[sagetrac-pguillot]

sage: MS=MatrixSpace(QQ,2)
sage: A=MS([0,1,1,0])
sage: B=MS.identity_matrix()
sage: G = MatrixGroup([A,B])
sage: G
Matrix group over Rational Field with 2 generators (
[0 1]  [1 0]
[1 0], [0 1]
)
sage: P = G.as_permutation_group()
sage: P
Permutation Group with generators [(), (2,3)]

One can see that the generators of the permutation group do not correspond to those of the matrix group. They should be given in the very same order.

This is a one-line change.

CC: @fchapoton @nathanncohen @dimpase

Component: group theory

Keywords: permutation groups

Author: Pierre Guillot

Branch: ffeb721

Reviewer: Frédéric Chapoton, Dima Pasechnik

Issue created by migration from https://trac.sagemath.org/ticket/19438

[sagetrac-pguillot]

New commits:

929d605	trac #19438 bug corrected in as_permutation_group method
cd3e801	Fixed the bug described in the ticket.

[sagetrac-pguillot]

Branch: u/pguillot/ticket_19438

[sagetrac-pguillot]

Commit: cd3e801

[dimpase]

comment:4

the whole thing looks a but dodgy, as permutation groups are handled by GAP's Group(), which is not guaranteed to create a group with exactly the same generators. Let me see...

[dimpase]

comment:5

LGTM

[fchapoton]

comment:6

there should be a blank line after TESTS::

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

9d7c09d

Added a blank line after TESTS::

[sagetrac-git]

Changed commit from cd3e801 to 9d7c09d

[dimpase]

comment:8

Could you trim the whitespaces on the empty lines you added? (we don't need any spaces there).

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

ffeb721

Trimmed the spaces on the blank lines.

[sagetrac-git]

Changed commit from 9d7c09d to ffeb721

[fchapoton]

Reviewer: Frédéric Chapoton, ​Dima Pasechnik

[fchapoton]

comment:10

ok, good to go.

Bravo, voila ton premier ticket !

[nbruin]

comment:11

Should it return the same generators literally? The basic routine doesn't do that:

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

It doesn't matter so much how the permutation group is represented, as long as the isomorphism to the permutation group is given. You should probably check if the cost of "canonicalize=false" is acceptable.

[sagetrac-pguillot]

comment:12

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

Precisely, here canonicalize=True is assumed. Adding canonicalize= False forces it to return the same generators, literally, yes.

I had assumed that canonicalize= False actually reduced the time needed for the computation, since it simply does a little less. This is confirmed by

(a) looking at the code for the class PermutationGroup_generic, which has

if canonicalize:
            gens = sorted(set(gens))

and as far as I can tell, this is the one and only place where the flag is used.

(b) When using GAP directly, if you try

G:= Group([(1,2,3), (1,3,2), (1,2), (1,3), (2,3), (1,2,3)]);
GeneratorsOfGroup(G);

then you get

[ (1,2,3), (1,3,2), (1,2), (1,3), (2,3), (1,2,3) ]

that is, they are kept in the same order by default.

It doesn't matter so much how the permutation group is represented, as long as the isomorphism to the permutation group is given.

It would be best to just return the isomorphism itself (that is what GAP does), yes. I'm not sure that Sage has anything on group homomorphisms, though.

[nbruin]

comment:13

OK, thanks.

The basic infrastructure for homomorphisms and isomorphisms is there, so it should be fairly straightforward to interface with the gap computations. That's for another ticket, though.

[vbraun]

Changed branch from u/pguillot/ticket_19438 to ffeb721

[jdemeyer]

Changed commit from ffeb721 to none

[jdemeyer]

Changed reviewer from Frédéric Chapoton, ​Dima Pasechnik to Frédéric Chapoton, Dima Pasechnik