This chapter is a collection of tutorials that show how to work with wreath products in GAP in conjunction with the package WPE.
In this section we present an example session which demonstrates how we can create wreath products elements by specifying its components.
In the following we will work with the wreath product \(G = \textrm{Alt}(5) \wr \textrm{Sym}(4)\).
gap> LoadPackage("WPE");; gap> K := AlternatingGroup(5);; gap> H := SymmetricGroup(4);; gap> G := WreathProduct(K, H); <permutation group of size 311040000 with 10 generators>
The resulting group \(G\) is embedded into a symmetric group on \(5 \cdot 4 = 20\) points via the imprimitive action of the wreath product. The size of the group is
\[ \vert G \vert = \vert\textrm{Alt}(5)\vert^4 \cdot \vert\textrm{Sym}(4)\vert = 60^4 \cdot 24 = 311\,040\,000\;. \]
Suppose we would like to input the wreath product element
\[ g = (\; (1,5,2,4,3),\, (1,3,5,2,4),\, (1,5,3,4,2),\, (1,4,5);\; (1,3)(2,4) \;) \]
as an element of \(G\). The method WreathProductElementList is the preferred way to create a wreath product element by specifying its components. Note that we first specify the four base components and at the end the top component as the last entry.
gap> gList := [ (1,5,2,4,3), (1,3,5,2,4), (1,5,3,4,2), (1,4,5), (1,3)(2,4) ];; gap> g := WreathProductElementList(G, gList); (1,15,3,11,5,12)(2,14)(4,13)(6,18,8,20)(7,19,10,17)(9,16) gap> g in G; true
On the other hand, the method ListWreathProductElement can be used to get a list containing the components of a wreath product element.
gap> ListWreathProductElement(G, g); [ (1,5,2,4,3), (1,3,5,2,4), (1,5,3,4,2), (1,4,5), (1,3)(2,4) ] gap> last = gList; true
The package author has implemented the methods ListWreathProductElement (Reference: ListWreathProductElement) and WreathProductElementList (Reference: WreathProductElementList) in GAP in order to translate between list representations of wreath product elements and other representations. The naming conventions are the same as for ListPerm and PermList.
Moreover, all functions that work for IsWreathProductElement can also be used on these list representations. However, it is not checked if the list indeed represents a wreath product element.
gap> Territory(gList); [ 1, 2, 3, 4 ]
If the wreath product element is "sparse", i.e. has only a few non-trivial components, it might be easier to create it by embedding its non-trivial components into \(G\) directly and multiplying them. Note however, that WreathProductElementList might be faster as it avoids group multiplications.
gap> h := (1,2,3) ^ Embedding(G,2) > * (1,5,2,4,3) ^ Embedding(G,4) > * (1,2,4) ^ Embedding(G, 5); (1,6,17,4,9,19,3,8,16,5,10,20,2,7,18) gap> hList := ListWreathProductElement(G, h); [ (), (1,2,3), (), (1,5,2,4,3), (1,2,4) ] gap> IsWreathCycle(hList); true
In this section we present an example session which demonstrates how we can display wreath product elements in an intuitive way. Wreath product elements are viewed, printed and displayed (see section Reference: View and Print for the distinctions between these operations) as generic wreath product elements (see section 2.1).
Suppose we are given some element \(g\) in the wreath product \(G = \textrm{Alt}(5) \wr \textrm{Sym}(4)\), and would like to view its components in a nice way.
gap> LoadPackage("WPE");; gap> K := AlternatingGroup(5);; gap> H := SymmetricGroup(4);; gap> G := WreathProduct(K, H);; gap> iso := IsomorphismWreathProduct(G);; gap> W := Image(iso);; gap> g := (1,15,8,20)(2,14,7,19,5,12,6,18,3,11,10,17)(4,13,9,16);; gap> g in G; true
First we translate the element \(g\) into a generic wreath product element \(w\). GAP uses ViewObj to print \(w\) in a compressed form.
gap> w := g ^ iso; < wreath product element with 4 base components >
If we want to print this element in a "machine-readable" way, we could use one of the following methods.
gap> Print(w); [ (1,5,2,4,3), (1,3,5,2,4), (1,5,3,4,2), (1,4,5), (1,3,2,4) ] gap> L := ListWreathProductElement(W, w); [ (1,5,2,4,3), (1,3,5,2,4), (1,5,3,4,2), (1,4,5), (1,3,2,4) ] gap> L = ListWreathProductElement(G, g); true
Usually, we want to display this element in a nice format instead, which is "human-readable" and allows us to quickly distinguish components.
gap> Display(w); 1 2 3 4 top ( (1,5,2,4,3), (1,3,5,2,4), (1,5,3,4,2), (1,4,5); (1,3,2,4) )
There are many display options available for adjusting the display behaviour for wreath product elements to your liking (see 4.4). For example, we might want to display the element vertically. We can do this for a single call to the `Display` command without changing the global display options like this:
gap> Display(w, rec(horizontal := false)); 1: (1,5,2,4,3) 2: (1,3,5,2,4) 3: (1,5,3,4,2) 4: (1,4,5) top: (1,3,2,4) gap> Display(w); 1 2 3 4 top ( (1,5,2,4,3), (1,3,5,2,4), (1,5,3,4,2), (1,4,5); (1,3,2,4) )
We can also change the global display options via the following command.
gap> SetDisplayOptionsForWreathProductElements(rec(horizontal := false)); gap> Display(w); 1: (1,5,2,4,3) 2: (1,3,5,2,4) 3: (1,5,3,4,2) 4: (1,4,5) top: (1,3,2,4)
All changes to the global behaviour can be reverted to the default behaviour via the following command.
gap> ResetDisplayOptionsForWreathProductElements(); gap> Display(w); 1 2 3 4 top ( (1,5,2,4,3), (1,3,5,2,4), (1,5,3,4,2), (1,4,5); (1,3,2,4) )
But sometimes, it is sufficient to just look at some components of a wreath product element. We can directly use the list representation to access the components on a low-level or we can use high-level functions on wreath product elements instead.
gap> a := BaseComponentOfWreathProductElement(w, 3); (1,5,3,4,2) gap> a = L[3]; true gap> b := TopComponentOfWreathProductElement(w); (1,3,2,4) gap> b = L[5]; true
As noted in the introduction, no additional setup is required if one wants to benefit from the optimizations for computations in wreath products. We simply create the wreath products via the native GAP command WreathProduct (Reference: WreathProduct), and the generic representation is used under the hood whenever appropiate.
We include in the following sections examples for each computational problem listed in 1.3. For all such examples we fix the following wreath product.
gap> LoadPackage("WPE");; gap> K := Group([ (1,2,3,4,5), (1,2,4,3) ]);; # F(5) gap> H := Group([ (1,2,3,4,5,6), (2,6)(3,5) ]);; # D(12) gap> G := WreathProduct(K, H); <permutation group of size 768000000 with 4 generators> gap> P := WreathProduct(K, SymmetricGroup(NrMovedPoints(H))); <permutation group of size 46080000000 with 4 generators> gap> IsSubgroup(P, G); true gap> iso := IsomorphismWreathProduct(P);;
Moreover, we fix the following elements of the parent wreath product \(P\). We choose them in such a way, that they do not lie in the smaller wreath product \(G\) for demonstration purposes only.
gap> x := (1,23,12,6,4,24,13,9,5,21,15,10,2,25,14,7)(3,22,11,8)(16,30,20,28)(17,27,19,26)(18,29);; gap> y := (1,12,26,8,3,14,28,7,2,13,27,10,5,11,30,6)(4,15,29,9)(16,23,20,22)(17,24,19,21)(18,25);; gap> Display(x ^ iso); 1 2 3 4 5 6 top ( (1,3,2,5), (1,4,5,2), (1,3,4,2), (1,5,3,4), (1,5,4,3,2), (1,2,4,3); (1,5,3,2)(4,6) ) gap> Display(y ^ iso); 1 2 3 4 5 6 top ( (1,2,3,4,5), (), (1,5,4,3,2), (1,3,5,2,4), (1,2)(3,5), (1,3,2,5); (1,3,6,2)(4,5) ) gap> x in P and y in P; true gap> not x in G and not y in G; true
We now demonstrate how to solve the conjugacy problem for \(x\) and \(y\) over \(G\), i.e. decide whether there exists \(c \in G\) with \(x^c = y\) and if it does, explicitly compute such a conjugating element \(c\).
We continue the GAP session from Section 3.3.
To check in GAP whether two elements are conjugate in a group we use native GAP command RepresentativeAction (Reference: RepresentativeAction).
gap> RepresentativeAction(G, x, y); fail
The output fail indicates, that \(x\) and \(y\) are not conjugate over \(G\). But are \(x\) and \(y\) conjugate in the parent wreath product?
gap> c := RepresentativeAction(P, x, y); (2,5)(3,4)(6,8,9,7)(11,29,25)(12,26,21,13,28,22,15,27,24,14,30,23) gap> Display(c^iso); 1 2 3 4 5 6 top ( (2,5)(3,4), (1,3,4,2), (1,4,5,2), (), (1,3,2,5), (2,4,5,3); (3,6,5) ) gap> x ^ c = y; true
We see, that indeed these elements are conjugate over the larger wreath product \(P\) by the conjugating element \(c \in P\).
Enumerate representatives of all conjugacy classes of elements of \(G\), i.e. return elements \(g_1, \dots, g_\ell\) such that \(g_1^G, \dots, g_\ell^G\) are the conjugacy classes of \(G\).
We continue the GAP session from Section 3.3. In particular recall the definition of the isomorphism iso.
To compute in GAP the conjugacy classes of elements of a group we use ConjugacyClasses (Reference: ConjugacyClasses attribute).
gap> CC := ConjugacyClasses(G);; gap> Length(CC); 1960
We see that there are \(1\,960\) many conjugacy classes of elements of \(G\). Let us look at a single conjugacy class.
gap> A := CC[1617]; (2,4,5,3)(6,26)(7,29,9,30,10,28,8,27)(11,21)(12,22)(13,23)(14,24)(15,25)^G
We can compute additional information about a conjugacy class on the go. For example, we can ask GAP for the number of elements in this class.
gap> Size(A); 60000
To access the representative of this class, we do the following.
gap> a := Representative(A); (2,4,5,3)(6,26)(7,29,9,30,10,28,8,27)(11,21)(12,22)(13,23)(14,24)(15,25) gap> Display(a ^ iso); 1 2 3 4 5 6 top ( (2,4,5,3), (2,4,5,3), (), (), (), (); (2,6)(3,5) )
Representatives are always given in a sparse format, e.g. all cycles in the wreath cycle decomposition of \(a\) are sparse (see 2.3).
Compute the centralizer of \(x\) in \(G\), i.e. compute a generating set of \(C_G(x)\).
We continue the GAP session from 3.3. In particular recall the definition of the isomorphism iso.
To compute in GAP the centralizer of an element in a group we use Centralizer (Reference: centraliser).
gap> C := Centralizer(G, x); Group([ (16,20)(17,19)(26,27)(28,30), (16,19,20,17)(26,28,27,30), (1,4,5,2)(6,9,10,7)(12,13,15,14)(21,25,23,24) ])
We can compute additional information about the centralizer on the go. For example, we can ask GAP for the number of elements in \(G\) that centralize \(x\).
gap> Size(C); 16
The generators of a centralizer are always given in a sparse format, e.g. all cycles in the wreath cycle decomposition of a generator \(g\) are sparse (see 2.3).
gap> for g in GeneratorsOfGroup(C) do > Display(g ^ iso); > od; 1 2 3 4 5 6 top ( (), (), (), (1,5)(2,4), (), (1,2)(3,5); () ) 1 2 3 4 5 6 top ( (), (), (), (1,4,5,2), (), (1,3,2,5); () ) 1 2 3 4 5 6 top ( (1,4,5,2), (1,4,5,2), (2,3,5,4), (), (1,5,3,4), (); () )
Compute the cycle index polynomial of \(G\) either for the imprimitive action or the product action. We do not continue the GAP session from 3.3 since the wreath product is too large to make sense of the cycle index polynomial just by looking at it. Instead we use the following wreath product.
gap> LoadPackage("WPE");; gap> K := Group([ (1,2), (1,2,3) ]);; # S(3) gap> H := Group([ (1,2) ]);; # C(2) gap> G_impr := WreathProduct(K, H);; gap> NrMovedPoints(G_impr); 6 gap> Order(G_impr); 72
To compute in GAP the cycle index of a a group we use CycleIndex (Reference: CycleIndex). Note that by default, the wreath product is given in imprimitive action.
gap> c_impr := CycleIndex(G_impr); 1/72*x_1^6+1/12*x_1^4*x_2+1/18*x_1^3*x_3+1/8*x_1^2*x_2^2+1/6*x_1*x_2*x_3 +1/12*x_2^3+1/4*x_2*x_4+1/18*x_3^2+1/6*x_6
For example, the second monomial 1/12*x_1^4*x_2 tells us that there are exactly \(\frac{72}{12} = 6\) elements with cycle type \((4, 1)\), i.e. elements that have four fixed points and one \(2\)-cycle. If one wants to access these monomials on the computer, one needs to use ExtRepPolynomialRatFun (Reference: ExtRepPolynomialRatFun).
gap> Display(ExtRepPolynomialRatFun(c_impr)); [ [ 6, 1 ], 1/6, [ 3, 2 ], 1/18, [ 2, 1, 4, 1 ], 1/4, [ 2, 3 ], 1/12, [ 1, 1, 2, 1, 3, 1 ], 1/6, [ 1, 2, 2, 2 ], 1/8, [ 1, 3, 3, 1 ], 1/18, [ 1, 4, 2, 1 ], 1/12, [ 1, 6 ], 1/72 ]
The way how to read this representation is roughly the following. The list consists of alternating entries, the first one encoding the monomial and the second one the corresponding coefficient, for example consider [ 1, 4, 2, 1 ], 1/12. The coefficient is 1/12 and the monomial is encoded by [ 1, 4, 2, 1 ]. The encoding of the monomial again consists of alternating entries, the first one encoding the indeterminant and the second one its exponent. For example [ 1, 4, 2, 1 ] translates to x_1^4 * x_2^1. For more details, see Reference: The Defining Attributes of Rational Functions.
If we want to consider the wreath product given in product action, we need to use the command WreathProductProductAction (Reference: WreathProductProductAction)
gap> G_prod := WreathProductProductAction(K, H);; gap> NrMovedPoints(G_prod); 9 gap> c_prod := CycleIndex(G_prod); 1/72*x_1^9+1/6*x_1^3*x_2^3+1/8*x_1*x_2^4+1/4*x_1*x_4^2+1/9*x_3^3+1/3*x_3*x_6
However, we do not need to create the wreath product in order to compute the cycle index of the group. Thus the package provides the functions CycleIndexWreathProductImprimitiveAction (4.5-1) and CycleIndexWreathProductProductAction (4.5-2) to compute the cycle index directly from the components \(K\) and \(H\) without writing down a representation of \(K \wr H\).
gap> c1 := CycleIndexWreathProductImprimitiveAction(K, H);; gap> c_impr = c1; true gap> c2 := CycleIndexWreathProductProductAction(K, H);; gap> c_prod = c2; true
generated by GAPDoc2HTML