[GAP Forum] Re: Blocks and block systems

Alexander Hulpke hulpke at math.colostate.edu
Wed Dec 1 19:40:28 GMT 2004

Dear GAP-Forum,

Warwick wrote:

> needs to work even if the group is not transitive.  Most of the GAP
> functions I found in the documentation include things like "The action must
> be transitive." or "... for a permutation group G acting transitively ...".
> (Incidentally, MaximalBlocks doesn't specify it but does require it.)
> 1)  It doesn't make sense to talk about blocks and block systems for
>     non-transitive groups for some reason I haven't thought of.
In general, the definition of imprimitivity assumes a transitive domain,
i.e. the block system comes from a transitive action.

The reson for this is that any orbit makes up a block system with one block.
If you have any other block which meets the orbit in more than one point
then the intersection with the orbit is also a block and the system it
generates lies entirely within the orbit.
So, for almost all purposes it is better to split into orbits first and find
blocks within each orbit separately.

The general functions for groups (apart from `AllBlocks', which is a small
wrapper that was intended specifically for the case of small degree
transitive groups) let you specify a domain (and a function for the action).
For finding blocks specify this domain to be a single orbit.
(The case of only specifying a transitive permutation group is only a special

Thus simply specifying one transitive domain (or running through the orbits
one by one) presumably solves your problem:

gap> g:=DirectProduct(TransitiveGroup(10,8),TransitiveGroup(10,5)); 
Group([ (2,7)(5,10), (1,3,5,7,9)(2,4,6,8,10), (11,12,13,14,15,16,17,18,19,20),
  (11,17,19,13)(12,14,18,16) ])
gap> o:=Orbits(g,MovedPoints(g));
[ [ 1, 3, 5, 10, 7, 2, 9, 4, 6, 8 ], 
  [ 11, 12, 17, 13, 14, 18, 19, 15, 16, 20 ] ]
gap> RepresentativesMinimalBlocks(g,o[1]);    
[ [ 1, 6 ] ]
gap> RepresentativesMinimalBlocks(g,o[2]);
[ [ 11, 13, 15, 17, 19 ], [ 11, 16 ] ]

If you wanted to use `AllBlocks' (which only supports transitive groups,
mainly for historical reasons) I would restrict the action to the orbit and
translate the points back:

gap> List(AllBlocks(Action(g,o[2])),i->o[2]{i});
[ [ 11, 17, 13, 19, 15 ], [ 11, 16 ] ]

I hope this helps,

   Alexander Hulpke (with additions by Steve Linton)

-- Colorado State University, Department of Mathematics,
Weber Building, 1874 Campus Delivery, Fort Collins, CO 80523-1874, USA
email: hulpke at math.colostate.edu, Phone: ++1-970-4914288

More information about the Forum mailing list