Example GrpPerm_BlocksActions-2 (H65E29)

> G := sub<Sym(48) |
>     (1,3,8,6)(2,5,7,4)(9,48,15,12)(10,47,16,13)(11,46,17,14),
>     (6,15,35,26)(7,22,34,19)(8,30,33,11)(12,14,29,27)(13,21,28,20),
>     (1,12,33,41)(4,20,36,44)(6,27,38,46)(9,11,26,24)(10,19,25,18),
>     (1,24,40,17)(2,18,39,23)(3,9,38,32)(41,43,48,46)(42,45,47,44),
>     (3,43,35,14)(5,45,37,21)(8,48,40,29)(15,17,32,30)(16,23,31,22),
>     (24,27,30,43)(25,28,31,42)(26,29,32,41)(33,35,40,38)(34,37,39,36) >;
> O1 := Orbits(G);
> O1;
[
    GSet{@ 1, 3, 6, 8, 9, 11, 12, 14, 15, 17, 24, 26, 27, 29,
     30, 32, 33, 35, 38, 40, 41, 43, 46, 48 @} ,
    GSet{@ 2, 4, 5, 7, 10, 13, 16, 18, 19, 20, 21, 22, 23, 25, 28,
     31, 34, 36, 37, 39, 42, 44, 45, 47 @} ]

Thus, G has two orbits, each of size 24. We consider the restriction of the action of G to the first of these orbits.

> f1, Im1, Ker1 := OrbitAction(G, O1[1]);
> FactoredOrder(Im1);
[ <2, 7>, <3, 9>, <5, 1>, <7, 1> ]
> IsPrimitive(Im1);
false
> P1 := MinimalPartition(Im1);
> #P1;
8
> f2, Im2, Ker2 := BlocksAction(Im1, P1);
> FactoredOrder(Im2);
[ <2, 7>, <3, 2>, <5, 1>, <7, 1> ]
> IsPrimitive(Im2);
true
> IsSymmetric(Im2);
true
> FactoredOrder(Ker2);
[ <3, 7> ]
> IsElementaryAbelian(Ker2);
true

Hence the group obtained by restricting G to its first orbit is isomorphic to Sym(8) acting on an elementary abelian normal subgroup of order 3⁷. We next investigate the kernel Ker1 of the restriction of G to the first orbit of length 24. We know that Ker1 must fix all the points in the first orbit of G so we first take its restriction to the second orbit.

> f3, Im3, Ker3 := OrbitAction(Ker1, O1[2]);
> IsTransitive(Im3);
true
> FactoredOrder(Im3);
[ <2, 20>, <3, 5>, <5, 2>, <7, 1>, <11, 1> ]
> FactoredOrder(Ker3);
[]
> IsPrimitive(Im3);
false

The kernel acts transitively and faithfully on the second orbit. As it is imprimitive, we look at its action on a system of imprimitivity.

> P := MinimalPartition(Im3);
> f4, Im4, Ker4 := BlocksAction(Im3, P);
> Im4;
Permutation group Im4 acting on a set of cardinality 12
Order = 239500800 = 2^9 * 3^5 * 5^2 * 7 * 11
    (10, 12, 11)
    (9, 12, 11)
    (8, 12, 9)
    (7, 9)(8, 12)
    (6, 9, 10)
    (5, 6, 9)
    (4, 6, 9)
    (3, 6, 9)
    (2, 6, 9, 5)(4, 10)
    (1, 9, 6, 5)(4, 10)
> IsPrimitive(Im4);
true
> IsAlternating(Im4);
true
> FactoredOrder(Ker4);
[ <2, 11> ]
> IsElementaryAbelian(Ker4);
true

The kernel of the restriction of G to the first orbit is isomorphic to Alt(12) acting on an elementary abelian group of order 2¹¹. So we now know the composition factors of G together with an indication of how they fit together.

Action on a Coset Space

CosetAction(G, H: parameters) : Grp, Grp -> Hom(Grp), GrpPerm, GrpPerm

RegularRepresentation(G, H: parameters) : Grp, Grp -> Hom(Grp), GrpPerm, GrpPerm

Given a subgroup H of the group G, construct the permutation representation of G given by the action of G on the set of (right) cosets of H in G. The function returns:

(a)

The natural homomorphism f: G -> L;

(b)

The induced group L;

(c)

The kernel K of the action (a subgroup of G).

Note that G may be any type of group. If G is a finitely presented group, then K may be returned undefined.

     Al: MonStgElt                       Default: em "Default"

Al := "Wang": Construct the coset action using Wang da Fang's algorithm which builds the action up the stabilizer chains of G and H, using a sequence of induction and block image operations. This algorithm is particularly efficient when H has fixed points that are not fixed points of G, and is the default choice when H is trivial.

Al := "Canonical": Compute the cosets using an orbit algorithm, which describes each coset found by computing a canonical element of that coset. The canonical element is one with the minimal base image in the group G. The algorithm is due to Richardson, [Ric73].

Al := "Default": Choose one of the above to use.

CosetImage(G, H: parameters) : Grp, Grp -> GrpPerm

Given a subgroup H of the group G, construct the image L of G given by the action of G on the set of (right) cosets of H in G. L is returned as a permutation group. Possible parameters are as for the previous function.

CosetKernel(G, H) : Grp, Grp -> Grp

Given a subgroup H of the group G, construct the kernel of the action of G on the set of (right) cosets of H in G.

Reduced Permutation Actions

If a permutation group is intransitive or imprimitive, then orbit actions and blocks actions provide natural permutation representations of lower degree.

TransitiveQuotient(G) : GrpPerm -> GrpPerm, Hom, GrpPerm

Returns the transitive constituent of G acting on its longest orbit, together with the action homomorphism and the kernel of the action. If G is transitive then the return values are G, the identity map on G, and the trivial subgroup of G.

PrimitiveQuotient(G) : GrpPerm -> GrpPerm, Hom, GrpPerm

For a transitive group G, returns the blocks image of G acting on a maximal block system, together with the action homomorphism and the kernel of the action. If G is primitive then the return values are G, the identity map on G, and the trivial subgroup of G.

DegreeReduction(G) : GrpPerm -> GrpPerm, Hom

Use a combination of orbit images and blocks images to attempt to find a faithful permutation representation of G with lower degree than G. The second return value is the isomorphism from G to the representation found. If no lower degree faithful representation is found then G and the identity map on G is returned.

The Jellyfish Algorithm

The Jellyfish reduction algorithm was introduced in [LNPS06]. See this article for an explanation of the name "Jellyfish". It attempts to find faithful low degree permutation representations for a family of large-base primitive permutation groups. We now define the target family as given in [LNPS06]. Consider the group W = S_n wreath S_r, as a permutation group in its primitive action on the set of r-tuples of k-subsets of the chosen n-set (see PrimitiveWreathProduct). Let M be the socle of W, M = A_n^r. Let G be any subgroup of W, with M≤G, such that the conjugation action of G on the r copies of A_n in M is transitive. A group T is in the target family of the algorithm if T is permutation isomorphic to some such G, having n > 2rk², and rk > 1. The degree of such a T is (n choose k)^r, and any such T is primitive. The image sought by the algorithm has degree nk. The utility of the algorithm is that any primitive group not in the target family is either alternating, symmetric, or has a short base.

The algorithm is one-sided Monte-Carlo in that, if it reports success, then it has found a faithful representation of the group. There is a small probability that the algorithm will find no faithful representation, even when the group given is in the target family.

Note that the Jellyfish algorithm implemented in Magma may succeed even when the input group is not in the target family. In all cases, success of the algorithm guarantees a faithful representation of the group.

The Magma implementation offers functions for testing the group for applicability of the Jellyfish algorithm. If successful, this test constructs data structures as in the cited article for quick evaluation of the homomorphism to the low-degree representation found and stores these with the group. There are also functions to compute the image and preimage of elements under the representation map. The preimage function is an addition to the algorithms given in [LNPS06], using an extension of their data structure. The preimage algorithm is nearly linear in the degree of the large degree primitive group.

JellyfishConstruction(G: parameters) : GrpPerm -> BoolElt

    Limit: RngIntElt                    Default: 

Attempt to construct a set of jellyfish for G. If unsuccessful, return false. Otherwise, construct data structures corresponding to T1 and T5 of [LNPS06], attach them to G, and return true. The parameter Limit controls how many attempts are made to find the orbits of the point stabilizer of G, which is the initial step in constructing a jellyfish. This construction phase terminates after a sequence of Limit random elements of G fails to change the orbits found. If the orbits found so far are not the orbits of a point stabilizer in G, the algorithm may fail. The same limit is used in the next phase, constructing the first jellyfish. The current default is the maximum of 15 and 2⌊log₂ d⌋, where d is the degree of G.

JellyfishImage(G) : GrpPerm -> GrpPerm

If the JellyfishConstruction function applied to G has returned true, return the faithful image of G found by the jellyfish algorithm. Otherwise an error results. If the JellyfishConstruction has not yet been applied to G, then it is applied first with default parameters. A failure here results in an error.

JellyfishImage(G, x: parameters) : GrpPerm, GrpPermElt -> GrpPermElt

JellyfishImage(G, H: parameters) : GrpPerm, GrpPerm -> GrpPermElt

    KnownInGroup: BoolElt               Default: false

If the JellyfishConstruction function applied to G has returned true, return the image of x as a permutation of the jellyfish, or the image of H as a permutation group acting on the jellyfish. The function will attempt this for any x in the same symmetric group as G and any subgroup of this symmetric group. The algorithm may fail when x∉G or H is not a subgroup of G, in which cases an error results. It is possible for this map to succeed when x is not in G or H is not a subset of G. In recognition of this, the parent of the result will be a symmetric group. This can be varied by setting the texttt{KnownInGroup} parameter to be true, which should only be done when it is known that x∈G or H≤G, which will dispense with checking the validity of the operation, and give an element (or group) that is flagged as contained in the jellyfish image of G. If the JellyfishConstruction has not yet been applied to G, then it is applied first with default parameters. A failure here results in an error.

JellyfishPreimage(G, x: parameters) : GrpPerm, GrpPermElt -> GrpPermElt

JellyfishPreimage(G, I: parameters) : GrpPerm, GrpPerm -> GrpPermElt

    KnownInGroup: BoolElt               Default: false

If the JellyfishConstruction function applied to G has returned true, return the preimage of x as a permutation in the symmetric group of G. The element x is assumed to be a permutation of the jellyfish for G. The function will attempt this for any x in the same symmetric group as the JellyfishImage of G. The algorithm may fail when x is not in the image group, in which case an error results. It is possible for this map to succeed when x is not in the image group. In recognition of this, the parent of the result will be a symmetric group. The function may also gbe applied to a subgroup, I of the jellyfish image group of G. If the texttt{KnownInGroup} parameter is set to true then it will be assumed that taking the preimage of x (or I) will be valid and that the result will lie in G. If the JellyfishConstruction has not yet been applied to G, then it is applied first with default parameters. A failure here results in an error.