possible bug in permutation/quotient group?
Robert Schwarz
puzzled me:
sage: G = SymmetricGroup(4)
sage: H = G.normal_subgroups()[1]
sage: H
Permutation Group with generators [(1,3)(2,4), (1,4)(2,3)]
sage: G.quotient_group(H)
Permutation Group with generators [(1,2)(3,6)(4,5), (1,3,5)(2,4,6)
Where do the 5 and 6 suddenly come from? In my understanding the
elements of the quotient group G/H are classes of elements of G, which
operates on {1, 2, 3, 4}.
Also, there is a method of G called "quotient", which raises and
NotImplementedError, which is a little confusing, given an
implementation of the quotient group is actually available.
Running Sage 4.1 on Arch Linux 64 bit.
--
Robert Schwarz <ma...@rschwarz.net>
Get my public key at http://rschwarz.net/key.asc
David Joyner
if G is a permutation group and H is a normal subgroup then
the quotient G/H embeds into G. Are you sure that is true?
Simon King
On Jul 31, 4:47 pm, David Joyner <wdjoy...@gmail.com> wrote:
> Maybe I don't understand your question. It seems you are claiming that
> if G is a permutation group and H is a normal subgroup then
> the quotient G/H embeds into G. Are you sure that is true?
> > elements of the quotient group G/H are classes of elements of G, which
> > operates on {1, 2, 3, 4}.
elements of G (namely cosets). One obvious way to represent a coset is
by picking one of its elements -- hence, an element of G. Then, it is
indeed surprising that higher numbers occur.
Aparently G.quotient_group(H) returns a permutation group that is
isomorphic to G/H. And then, it is of course not surprising that it
does not simply act on {1,2,3,4}.
But the following question arises:
Start with
sage: H = G.normal_subgroups()[1]
sage: H
Permutation Group with generators [(1,3)(2,4), (1,4)(2,3)]
Given an element g of G, how can one find the element of X that
corresponds to the coset of g wrt. H ?
sage: X(g)
would in general not work!
How can one construct the map from G to X that corresponds to taking
the quotient by H ?
Cheers,
Simon
javier
> if G is a permutation group and H is a normal subgroup then
> the quotient G/H embeds into G. Are you sure that is true?
1 --> H --> G --> G/H -->1
to embed G/H into G we would need it to split, which would mean that
the extension is trivial, or that G factorizes as a product of H and G/
H.
I haven't looked at the code, but looks like the presentation is built
by permutations on itself (sort of Cayley theorem-like). Since in the
example the quotient group should has order 6, it can always be
represented as a subgroup of S_6.
kcrisman
On Jul 31, 11:47 am, David Joyner <wdjoy...@gmail.com> wrote:
> Maybe I don't understand your question. It seems you are claiming that
> if G is a permutation group and H is a normal subgroup then
> the quotient G/H embeds into G. Are you sure that is true?
>
>
>
> On Fri, Jul 31, 2009 at 11:36 AM, Robert Schwarz<m...@rschwarz.net> wrote:
>
> > Hi all, I was just playing around with permutations, when something
> > puzzled me:
>
> > sage: G = SymmetricGroup(4)
> > sage: H = G.normal_subgroups()[1]
> > sage: H
> > Permutation Group with generators [(1,3)(2,4), (1,4)(2,3)]
> > sage: G.quotient_group(H)
> > Permutation Group with generators [(1,2)(3,6)(4,5), (1,3,5)(2,4,6)
sage: G.quotient_group??
It turns out that Sage asks GAP to create the image of the morphism G -
> G/H, as far as I can tell, and in so doing creates that image as a
separate (sub)permutation group. In particular, it using
RegularActionHomomorphism to do this, and at
http://www.gap-system.org/Manuals/doc/htm/ref/CHAP039.htm#SSEC007.2 it
says "returns an isomorphism from G onto the regular permutation
representation of G" and certainly in this case G/H (the relevant
group) has six elements!
Though I agree that this could be confusing, the good part is that
this creates (an isomorphic) group without having to talk about which
element of the coset you pick each time. It would be misleading to
say that (1234) was an element of G/H (which I think is what David was
getting at). There are ways to get cosets in GAP, of course (maybe
wrapped in Sage?) but I don't know much about them.
I hope this helps!
- kcrisman
>
> > Where do the 5 and 6 suddenly come from? In my understanding the
> > elements of the quotient group G/H are classes of elements of G, which
> > operates on {1, 2, 3, 4}.
>
> > Also, there is a method of G called "quotient", which raises and
> > NotImplementedError, which is a little confusing, given an
> > implementation of the quotient group is actually available.
>
> > Running Sage 4.1 on Arch Linux 64 bit.
>
> > --
>
> > Get my public key athttp://rschwarz.net/key.asc
Simon King
On Jul 31, 5:11 pm, kcrisman <kcris...@gmail.com> wrote:
...
> this creates (an isomorphic) group without having to talk about which
> element of the coset you pick each time. It would be misleading to
> say that (1234) was an element of G/H (which I think is what David was
> getting at). There are ways to get cosets in GAP, of course (maybe
> wrapped in Sage?) but I don't know much about them.
Is there a method that associates to an element g of G an element in
G.quotient_group(H) corresponding to its coset?
Cheers,
Simon
Robert Schwarz
> On Jul 31, 4:47 pm, David Joyner <wdjoy...@gmail.com> wrote:
>> Maybe I don't understand your question. It seems you are claiming
>> the quotient G/H embeds into G. Are you sure that is true?
>
> 1 --> H --> G --> G/H -->1
> to embed G/H into G we would need it to split, which would mean that
> the extension is trivial, or that G factorizes as a product of H and
> G/H.
OK, my fault, too much wishful thinking here.
kcrisman wrote:
>
> Look at
>
> sage: G.quotient_group??
>
> It turns out that Sage asks GAP to create the image of the morphism G -
>> G/H, as far as I can tell, and in so doing creates that image as a
> separate (sub)permutation group. In particular, it using
> RegularActionHomomorphism to do this, and at
> http://www.gap-system.org/Manuals/doc/htm/ref/CHAP039.htm#SSEC007.2 it
> says "returns an isomorphism from G onto the regular permutation
> representation of G" and certainly in this case G/H (the relevant
> group) has six elements!
>
> Though I agree that this could be confusing, the good part is that
> this creates (an isomorphic) group without having to talk about which
> element of the coset you pick each time. It would be misleading to
> say that (1234) was an element of G/H (which I think is what David was
> getting at). There are ways to get cosets in GAP, of course (maybe
> wrapped in Sage?) but I don't know much about them.
>
> I hope this helps!
>
Yes, the cosets are, what I really want (although generators would be
very nice, too, if they exist, e.g. if the quotient is normal).
The application was the following: Suppose you have a linear equation
with multi-indexed variables, like x_1,2 + x_2,3 + x_3,1 == 0, which
also holds for all permutations of {1, 2, 3}, and I want to enumerate
all possible equations, but without duplicates. I hoped it was possible
to first compute the permutations under whose operation the exact same
equation result, then take the subgroup H generated by those and use
representants from the cosets of S_n/H to get all unique equations.
Looks like it's not that simple, since H doesn't even have to be normal,
in general.
Thanks a lot , though.
javier
cosets = Set([Set([h*g for h in H]) for g in G])
or if you want to get a representative of each coset you can then use
reps = [x[0] for x in cosets]
this should work even if H is not normal, the only issue being that
the set of cosets is not a group. Not sure if it will help with your
problem, though.
Cheers
J.
On Jul 31, 5:27 pm, Robert Schwarz <m...@rschwarz.net> wrote:
> Yes, the cosets are, what I really want (although generators would be
> very nice, too, if they exist, e.g. if the quotient is normal).
>
> The application was the following: Suppose you have a linear equation
> with multi-indexed variables, like x_1,2 + x_2,3 + x_3,1 == 0, which
> also holds for all permutations of {1, 2, 3}, and I want to enumerate
> all possible equations, but without duplicates. I hoped it was possible
> to first compute the permutations under whose operation the exact same
> equation result, then take the subgroup H generated by those and use
> representants from the cosets of S_n/H to get all unique equations.
> Looks like it's not that simple, since H doesn't even have to be normal,
> in general.
>
> Thanks a lot , though.
>
> --
Robert Schwarz
> If that you want are the cosets you can get them simply using
>
> cosets = Set([Set([h*g for h in H]) for g in G])
>
> or if you want to get a representative of each coset you can then use
>
> reps = [x[0] for x in cosets]
>
> this should work even if H is not normal, the only issue being that
> the set of cosets is not a group. Not sure if it will help with your
> problem, though.
>
Yes, I will use that, for now, although I was hoping to get a "nice"
representation of the set of cosets, in terms of generators.
Anyway, it looks like I wasn't expecting too much after all. On
http://en.wikipedia.org/wiki/Group_action or S. Lang: Algebra (p. 28)
I find exactly what I want, supposing a group G acts transitively on a
set X:
"If G does not act faithfully on X, one can easily modify the group to
obtain a faithful action. If we define N = {g in G : g·x = x for all x
in X}, then N is a normal subgroup of G; indeed, it is the kernel of the
homomorphism G → Sym(X). The factor group G/N acts faithfully on X by
setting (gN)·x = g·x. The original action of G on X is faithful if and
only if N = {e}."
So what I need, computationally, is not a map from G -> G/N, but more
the other way round. More explicitly I want a (nice, simple, concise)
description of X (= orbit of G) in terms of elements of G. The cosets
will do that, but not really simpler than X itself. Provided I come up
with something sufficiently general, there will be a patch with a new
feature :-)
Thanks, again
Carlo Hamalainen
> If that you want are the cosets you can get them simply using
>
> cosets = Set([Set([h*g for h in H]) for g in G])
>
> or if you want to get a representative of each coset you can then use
>
> reps = [x[0] for x in cosets]
This will force you to enumerate the elements of the group G, and
that's not always a quick thing to do (e.g. what if you're working in
the Alternating group on 10 points?).
Gap provides RightCosets, CanonicalRightCosetElement and
Representative for working with cosets efficiently:
########################
G = gap.AlternatingGroup(4)
g = '(1,2,3)'
H = gap.Subgroup(G, [g])
rc = gap.RightCosets(G, H)
print "Canonical representatives:"
for x in gap.List(G):
print "H" + str(x) + ":", gap.CanonicalRightCosetElement(H, x)
print
print "Representatives:"
for C in gap.List(rc):
print C, ":", gap.Representative(C)
########################
Canonical representatives:
H(): ()
H(1,2)(3,4): (2,4,3)
H(1,3)(2,4): (2,3,4)
H(1,4)(2,3): (1,2,4)
H(2,3,4): (2,3,4)
H(1,2,4): (1,2,4)
H(1,3,2): ()
H(1,4,3): (2,4,3)
H(2,4,3): (2,4,3)
H(1,2,3): ()
H(1,3,4): (1,2,4)
H(1,4,2): (2,3,4)
Representatives:
RightCoset(Group( [ (1,2,3) ] ),()) : ()
RightCoset(Group( [ (1,2,3) ] ),(1,2)(3,4)) : (1,2)(3,4)
RightCoset(Group( [ (1,2,3) ] ),(1,3)(2,4)) : (1,3)(2,4)
RightCoset(Group( [ (1,2,3) ] ),(1,4)(2,3)) : (1,4)(2,3)
--
Carlo Hamalainen
http://carlo-hamalainen.net