[GAP Forum] Wreath Product Decomposition

[Richard Barraclough]

Dear Alastair,

Transitive imprimitive permutation groups can be decomposed as wreath
products. All intransitive permutation groups are imprimitive: The orbits
are the blocks. I guess that's not what you had in mind though.

The usual way of dealing with permutation groups is to write them as a
direct product of transitive permutation groups, then deal with the
transitive groups separately.

You probably then want at least one transitive constituent in order to be
imprimitive.


Here are some calculations.

gens :=  [ (1,2), (2,3), (1,4)(2,5)(3,6)(19,20), (26,27), (28,29),
(1,7)(2,8)(3,9)(4,10)(5,11)(6,12)(19,21)(20,22)(25,30)(26,31)(27,32)(28,33)(
29,34)(40,41), 
(7,13)(8,14)(9,15)(10,16)(11,17)(12,18)(21,23)(22,24)(30,35)(31,36)(32,37)(3
3,38)(34,39)(41,42)
];

gp := Group(gens);
orbs := Orbits(gp);
gpsGens := []; gps := [];
for i in [1..Length(orbs)] do
  gpsGens[i] := List([1..Length(gens)], j -> RestrictedPerm( gens[j],
orbs[i]));
  gps[i] := Group(gpsGens[i]);
od;

gp is the direct product of the gps

You can now investigate them using GAP's built in functions, which have
already been proved correct.

looks relatively interesting.
gap> Order(gps[1]);
2239488
gap> # looks relatively interesting
gap> IsTransitive(gps[1]);
true
gap> IsPrimitive(gps[1]);
false

So that may be all you need.


You can write gps[1] as a wreath product as follows:

gap> bl := MaximalBlocks(gps[1],MovedPoints(gps[1]));
[ [ 1, 2, 3, 4, 5, 6 ], [ 7, 8, 9, 10, 11, 12 ], [ 13, 14, 15, 16, 17, 18 ]
]
# (Explained in Chapter 39 of the Ref. Manual.)

gap> H := Stabilizer(gps[1], bl[1], OnSets);
<permutation group of size 746496 with 16 generators>

gap> HH := Group(List(GeneratorsOfGroup(H), g -> RestrictedPerm(g,bl[1])));
<permutation group with 16 generators>

gap> K := Action(gps[1],bl,OnSets);
Group([ (1,2,3), (2,3) ])

gap> wr := WreathProduct(HH,K);
<permutation group of size 2239488 with 50 generators>

By construction, wr embeds in gps[1]. (I've assumed that gps[1] is acting
the same way on each block.) Burkhard Hoefling suggests comparing orders:

gap> Order(gps[1]);
2239488
gap> Order(wr);    
2239488

They're the same, therefore the groups are isomorphic.

gap> # This will take a while and is probably not a good idea unless you're
gap> # _really_ sceptical
gap> iso := IsomorphismGroups(wr,gps[1]);



Once you've done this for all the gps you have gp as a direct product of
wreath products, say
(H1 wr K1) x (H2 wr K2) x ... x (Hn wr Kn)
You can then write this as a subgroup of the wreath product
(H1 x H2 x ... x Hn) wr (K1 x K2 x ... x Kn)
but that seems a bit silly because it needs many more points to support its
action.


If you're interested in the actual algorithms, I seem to remember Greg
Butler's 'Fundamental algorithms for permutation groups' being easy reading
(if your library has it).

Richard.


-------------
Richard Barraclough
School of Mathematical Sciences
Queen Mary College                 web: www.maths.qmul.ac.uk/~rwb
Mile End Road                    email: R.W.Barraclough at qmul.ac.uk
London E1 4NS



On 13/2/06 3:12 pm, "Alastair Donaldson" <ally at dcs.gla.ac.uk> wrote:

> Dear Forum members
> 
> I am trying to write an algorithm which, given a permutation group G
> acting (not necessarily transitively) on {1,2,.....,n} for some n>0, will
> determine whether or not G is a wreath product of subgroups H and K.
> 
> According to a previous posting by Burkhard Hoefling, I think this should
> be fairly easy:
> 
> "Wreath products of permutation groups can easily be recognized by looking
> at their block structure, see `Blocks' in the GAP reference manual. In
> general, a transitive permutation group G embeds in the wreath
> product (action of block stabilizer on block) wr (action of G on
> orbit of block), and you can easily check equality by comparing orders."
> 
> However, the groups which crop up in my application domain do not tend to
> act transitively.  As an example, consider the group
> 
> G := Group( [ (1,2), (2,3), (1,4)(2,5)(3,6)(19,20), (26,27), (28,29),
> (1,7)(2,8)(3,9)(4,10)(5,11)(6,12)(19,21)(20,22)(25,30)(26,31)(27,32)(28,33)(29
> ,34)(40,41), 
> (7,13)(8,14)(9,15)(10,16)(11,17)(12,18)(21,23)(22,24)(30,35)(31,36)(32,37)(33,
> 38)(34,39)(41,42)
> ]);
> 
> I have worked out that this decomposes in several possible ways as H wr K,
> one of which is
> 
> H := Group([ (33,34), (31,32), (11,12), (8,9), (10,11,12), (7,8,9),
> (7,10)(8,11)(9,12)(21,22) ]);
> 
> and
> 
> K := Group([ 
> (7,13)(8,14)(9,15)(10,16)(11,17)(12,18)(21,23)(22,24)(30,35)(31,36)(32,37)(33,
> 38)(34,39)(41,42),
> (1,7,13)(2,8,14)(3,9,15)(4,10,16)(5,11,17)(6,12,18)(19,21,23)(20,22,24)(25,30,
> 35)(26,31,36)(27,32,37)(28,33,38)(29,34,39)(40,41,42) ]
> 
> (the group H can then be decomposed further as a direct product, one
> factor of which is itself a wreath product).
> 
> I have written a rather complex algorithm which does this decomposition
> correctly for my example.  However, I'm having trouble proving the
> correctness of my algorithm, which is not nearly as simple as Buckhard's
> approach of looking at blocks
> and comparing orders.  However, since blocks are not immediately
> applicable when the group does not act transitively, I'm not sure how to
> extend his suggested approach.
> 
> Any ideas would be greatly appreciated
> 
> -Alastair
> 
> _______________________________________________
> Forum mailing list
> Forum at mail.gap-system.org
> http://mail.gap-system.org/mailman/listinfo/forum