[GAP Forum] Looking for automorphisms of triple steiner systems

Tue Mar 23 03:35:31 GMT 2010

Hi Leonard,

I suppose your definition of a Unix system includes Windows with
Cygwin installed, and with
GAP installed via the Cygwin route, right?

Best,
Dima

On 23 March 2010 01:53, Leonard Soicher <L.H.Soicher at qmul.ac.uk> wrote:
> Dear Forum,
>
> I would suggest making use of the DESIGN package and its
> function to compute the automorphism group of a block
> design, as illustrated in the logfile, below.
> The DESIGN package uses GRAPE for this computation, which
> in turn makes use of Brendan McKay's nauty package, and so
> this will only work on a Unix system on which GAP, GRAPE
> and DESIGN have been fully installed.
>
> Regards,
> Leonard
>
> gap> LoadPackage("design");
>
> Loading  GRAPE 4.3  (GRaph Algorithms using PErmutation groups),
> by L.H.Soicher at qmul.ac.uk.
>
> -----------------------------------------------------------------------------
> Loading  DESIGN 1.4 (The Design Package for GAP)
> by Leonard H. Soicher (http://www.maths.qmul.ac.uk/~leonard/).
> -----------------------------------------------------------------------------
> true
> gap> st:=[ [ 2, 4, 11 ], [ 7, 10, 12 ], [ 3, 8, 10 ], [ 2, 6, 12 ], [ 3, 6, 13 ], [
>> 1, 6, 10 ], [ 5, 11, 13 ], [ 1, 2, 3 ],
>>   [ 3, 4, 9 ], [ 5, 7, 8 ], [ 3, 7, 11 ], [ 4, 8, 12 ], [ 1, 8, 13 ], [ 5,
>> 6, 9 ], [ 9, 12, 13 ], [ 1, 7, 9 ],
>>   [ 2, 5, 10 ], [ 2, 7, 13 ], [ 2, 8, 9 ], [ 6, 8, 11 ], [ 9, 10, 11 ], [ 4,
>> 10, 13 ], [ 1, 11, 12 ], [ 1, 4, 5 ],
>>   [ 4, 6, 7 ], [ 3, 5, 12 ] ];;
> gap> S:=BlockDesign(13,st);
> rec( isBlockDesign := true, v := 13,
>  blocks := [ [ 1, 2, 3 ], [ 1, 4, 5 ], [ 1, 6, 10 ], [ 1, 7, 9 ],
>      [ 1, 8, 13 ], [ 1, 11, 12 ], [ 2, 4, 11 ], [ 2, 5, 10 ], [ 2, 6, 12 ],
>      [ 2, 7, 13 ], [ 2, 8, 9 ], [ 3, 4, 9 ], [ 3, 5, 12 ], [ 3, 6, 13 ],
>      [ 3, 7, 11 ], [ 3, 8, 10 ], [ 4, 6, 7 ], [ 4, 8, 12 ], [ 4, 10, 13 ],
>      [ 5, 6, 9 ], [ 5, 7, 8 ], [ 5, 11, 13 ], [ 6, 8, 11 ], [ 7, 10, 12 ],
>      [ 9, 10, 11 ], [ 9, 12, 13 ] ] )
> gap> AllTDesignLambdas(S);
> [ 26, 6, 1 ]
> gap> G:=AutomorphismGroup(S);
> Group([ (1,7,9)(2,11,4)(5,13,10)(6,8,12), (4,11)(5,12)(6,10)(7,9)(8,13) ])
> gap> Size(G);
> 6
> gap>
>
> On Mon, Mar 22, 2010 at 11:36:12AM -0600, Alexander Hulpke wrote:
>>
>>
>> Dear Forum,
>>
>> Mbg Nimda asked:
>>
>> > I'm trying to determine the automorphism group of Steiner(2,3,13) but I get
>> > a memory exceeded error.
>> > Here is the session:
>> >
>> > gap> st;
>> > [ [ 2, 4, 11 ], [ 7, 10, 12 ], [ 3, 8, 10 ], [ 2, 6, 12 ], [ 3, 6, 13 ], [
>> > 1, 6, 10 ], [ 5, 11, 13 ], [ 1, 2, 3 ],
>> >  [ 3, 4, 9 ], [ 5, 7, 8 ], [ 3, 7, 11 ], [ 4, 8, 12 ], [ 1, 8, 13 ], [ 5,
>> > 6, 9 ], [ 9, 12, 13 ], [ 1, 7, 9 ],
>> >  [ 2, 5, 10 ], [ 2, 7, 13 ], [ 2, 8, 9 ], [ 6, 8, 11 ], [ 9, 10, 11 ], [ 4,
>> > 10, 13 ], [ 1, 11, 12 ], [ 1, 4, 5 ],
>> >  [ 4, 6, 7 ], [ 3, 5, 12 ] ]
>> > gap>
>> > gap>
>> > gap> g:=SymmetricGroup(13);
>> > Sym( [ 1 .. 13 ] )
>> > gap> h:=Stabilizer(g,st,OnSetsSets);
>>
>> First, `st' should be sorted to be a set:
>> st:=Set(st);
>>
>> Then, alas, the OnSetsSets action only does a naive orbit algorithm, and has no backtrack implementation. The stabilizer calculation therefore needs to form the whole orbit, which is unlikely to succeed.
>>
>> The best way to deal with this would be to use the GRAPE package, encode the steiner system in a graph and use the graph automorphism function.
>>
>> Alternatively (as 13 choose 3= 286 is still small), you could take the action on 3-sets, and in this action compute a set stabilizer (a single set stabilizer has a backtrack implementation and therefore much faster):
>>
>> gap> comb:=Combinations([1..13],3);;
>> gap> act:=ActionHomomorphism(g,comb,OnSets,"surjective");
>> <action epimorphism>
>>
>> Now translate st to a set of points in this action of degree 286
>> gap> stp:=Set(List(st,x->Position(comb,x)));
>> [ 1, 22, 42, 47, 56, 64, 83, 90, 99, 106, 107, 126, 137, 145, 149, 153, 175,
>>   191, 199, 205, 210, 229, 239, 262, 277, 282 ]
>>
>> stabilize, and transfer back to S13:
>> gap> u:=Stabilizer(Image(act),stp,OnSets);
>> <permutation group of size 6 with 2 generators>
>> gap> u:=PreImage(act,u);
>> Group([ (4,11)(5,12)(6,10)(7,9)(8,13), (1,9)(2,4)(5,8)(6,13)(10,12) ])
>>
>> I hope this helps,
>>
>>    Alexander Hulpke
>>
>> -- 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
>> http://www.math.colostate.edu/~hulpke
>>
>>
>>
>>
>> _______________________________________________
>> Forum mailing list
>> Forum at mail.gap-system.org
>> http://mail.gap-system.org/mailman/listinfo/forum
>
> _______________________________________________
> Forum mailing list
> Forum at mail.gap-system.org
> http://mail.gap-system.org/mailman/listinfo/forum
>

--
Dmitrii Pasechnik
-----
DISCLAIMER: Any text following this sentence does not constitute a
part of this message, and was added automatically during transmission.

CONFIDENTIALITY: This email is intended solely for the person(s) named. The contents may be confidential and/or privileged. If you are not the intended recipient, please delete it, notify us, and do not copy or use it, nor disclose its contents. Thank you.

Towards A Sustainable Earth: Print Only When Necessary