Quelle chap3.html Sprache: HTML

products/Sources/formale Sprachen/GAP/pkg/wpe/doc/chap3.html

<?xml version="1.0" encoding="UTF-8"?>

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<title>GAP (WPE) - Chapter 3: Tutorial</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap3" onload="jscontent()">

<div class="chlinktop">Goto Chapter: <a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>

<div class="chlinkprevnexttop"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap2.html">[Previous Chapter]</a> <a href="chap4.html">[Next Chapter]</a> </div>

<a href="chap3_mj.html">[MathJax on]</a>
<a id="X81932F777898AD72" name="X81932F777898AD72"></a>
<div class="ChapSects"><a href="chap3.html#X81932F777898AD72">3 Tutorial</a>
<div class="ContSect"> <a href="chap3.html#X820D3CEF8368DB04">3.1 Creating Wreath Product Elements</a>

</div>
<div class="ContSect"> <a href="chap3.html#X7C85A3718343D842">3.2 Displaying Wreath Product Elements</a>

</div>
<div class="ContSect"> <a href="chap3.html#X8345CC25855C9406">3.3 Computing in Wreath Products</a>

</div>
<div class="ContSect"> <a href="chap3.html#X8017E4AF7EBB72D2">3.4 Conjugacy Problem</a>

</div>
<div class="ContSect"> <a href="chap3.html#X7D474F8F87E4E5D9">3.5 Conjugacy Classes</a>

</div>
<div class="ContSect"> <a href="chap3.html#X7A2BF4527E08803C">3.6 Centralizer</a>

</div>
<div class="ContSect"> <a href="chap3.html#X87A59E867A83A798">3.7 Cycle Index Polynomial</a>

</div>
</div>

<h3>3 Tutorial</h3>

This chapter is a collection of tutorials that show how to work with wreath products in GAP in conjunction with the package WPE.

<a id="X820D3CEF8368DB04" name="X820D3CEF8368DB04"></a>

<h4>3.1 Creating Wreath Product Elements</h4>

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 = Alt(5) ≀ Sym(4).

<div class="example"><pre>
gap> LoadPackage("WPE");;
gap> K := AlternatingGroup(5);;
gap> H := SymmetricGroup(4);;
gap> G := WreathProduct(K, H);
<permutation group of size 311040000 with 10 generators>
</pre></div>

The resulting group G is embedded into a symmetric group on 5 ⋅ 4 = 20 points via the imprimitive action of the wreath product. The size of the group is

| G | = |Alt(5)|^4 ⋅ |Sym(4)| = 60^4 ⋅ 24 = 311040000 .

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 <code class="code">WreathProductElementList</code> 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.

<div class="example"><pre>
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
</pre></div>

On the other hand, the method <code class="code">ListWreathProductElement</code> can be used to get a list containing the components of a wreath product element.

<div class="example"><pre>
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
</pre></div>

The package author has implemented the methods <code class="func">ListWreathProductElement</code> (<a href="../../../doc/ref/chap49.html#X801A358E879A0FF0">Reference: ListWreathProductElement</a>) and <code class="func">WreathProductElementList</code> (<a href="../../../doc/ref/chap49.html#X7ECB076E81D8D402">Reference: WreathProductElementList</a>) in GAP in order to translate between list representations of wreath product elements and other representations. The naming conventions are the same as for <code class="code">ListPerm</code> and <code class="code">PermList</code>.

Moreover, all functions that work for <code class="code">IsWreathProductElement</code> can also be used on these list representations. However, it is not checked if the list indeed represents a wreath product element.

<div class="example"><pre>
gap> Territory(gList);
[ 1, 2, 3, 4 ]
</pre></div>

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 <code class="code">WreathProductElementList</code> might be faster as it avoids group multiplications.

<div class="example"><pre>
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
</pre></div>

<a id="X7C85A3718343D842" name="X7C85A3718343D842"></a>

<h4>3.2 Displaying Wreath Product Elements</h4>

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 <a href="../../../doc/ref/chap6.html#X8074A8387C9DB9A8">Reference: View and Print</a> for the distinctions between these operations) as generic wreath product elements (see section <a href="chap2.html#X7DF2AEBC8518FFA4">2.1</a>).

Suppose we are given some element g in the wreath product G = Alt(5) ≀ Sym(4), and would like to view its components in a nice way.

<div class="example"><pre>
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
</pre></div>

First we translate the element g into a generic wreath product element w. GAP uses <code class="code">ViewObj</code> to print w in a compressed form.

<div class="example"><pre>
gap> w := g ^ iso;
< wreath product element with 4 base components >
</pre></div>

If we want to print this element in a "machine-readable" way, we could use one of the following methods.

<div class="example"><pre>
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
</pre></div>

Usually, we want to display this element in a nice format instead, which is "human-readable" and allows us to quickly distinguish components.

<div class="example"><pre>
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) )
</pre></div>

There are many display options available for adjusting the display behaviour for wreath product elements to your liking (see <a href="chap4.html#X8227AD6B7FC637DE">4.4</a>). 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:

<div class="example"><pre>
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) )
</pre></div>

We can also change the global display options via the following command.

<div class="example"><pre>
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)
</pre></div>

All changes to the global behaviour can be reverted to the default behaviour via the following command.

<div class="example"><pre>
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) )
</pre></div>

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.

<div class="example"><pre>
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
</pre></div>

<a id="X8345CC25855C9406" name="X8345CC25855C9406"></a>

<h4>3.3 Computing in Wreath Products</h4>

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 <code class="func">WreathProduct</code> (<a href="../../../doc/ref/chap49.html#X8786EFBC78D7D6ED">Reference: WreathProduct</a>), and the generic representation is used under the hood whenever appropiate.

We include in the following sections examples for each computational problem listed in <a href="chap1.html#X7D96C25680814773">1.3</a>. For all such examples we fix the following wreath product.

<div class="example"><pre>
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);;
</pre></div>

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.

<div class="example"><pre>
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
</pre></div>

<a id="X8017E4AF7EBB72D2" name="X8017E4AF7EBB72D2"></a>

<h4>3.4 Conjugacy Problem</h4>

We now demonstrate how to solve the conjugacy problem for x and y over G, i.e. decide whether there exists c ∈ G with x^c = y and if it does, explicitly compute such a conjugating element c.

We continue the GAP session from Section <a href="chap3.html#X8345CC25855C9406">3.3</a>.

To check in GAP whether two elements are conjugate in a group we use native GAP command <code class="func">RepresentativeAction</code> (<a href="../../../doc/ref/chap41.html#X857DC7B085EB0539">Reference: RepresentativeAction</a>).

<div class="example"><pre>
gap> RepresentativeAction(G, x, y);
fail
</pre></div>

The output <code class="code">fail</code> indicates, that x and y are not conjugate over G. But are x and y conjugate in the parent wreath product?

<div class="example"><pre>
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
</pre></div>

We see, that indeed these elements are conjugate over the larger wreath product P by the conjugating element c ∈ P.

<a id="X7D474F8F87E4E5D9" name="X7D474F8F87E4E5D9"></a>

<h4>3.5 Conjugacy Classes</h4>

Enumerate representatives of all conjugacy classes of elements of G, i.e. return elements g_1, dots, g_ℓ such that g_1^G, dots, g_ℓ^G are the conjugacy classes of G.

We continue the GAP session from Section <a href="chap3.html#X8345CC25855C9406">3.3</a>. In particular recall the definition of the isomorphism <code class="code">iso</code>.

To compute in GAP the conjugacy classes of elements of a group we use <code class="func">ConjugacyClasses</code> (<a href="../../../doc/ref/chap39.html#X871B570284BBA685">Reference: ConjugacyClasses attribute</a>).

<div class="example"><pre>
gap> CC := ConjugacyClasses(G);;
gap> Length(CC);
1960
</pre></div>

We see that there are 1960 many conjugacy classes of elements of G. Let us look at a single conjugacy class.

<div class="example"><pre>
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
</pre></div>

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.

<div class="example"><pre>
gap> Size(A);
60000
</pre></div>

To access the representative of this class, we do the following.

<div class="example"><pre>
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) )
</pre></div>

Representatives are always given in a sparse format, e.g. all cycles in the wreath cycle decomposition of a are sparse (see <a href="chap2.html#X872BE72F7B2BBD6B">2.3</a>).

<a id="X7A2BF4527E08803C" name="X7A2BF4527E08803C"></a>

<h4>3.6 Centralizer</h4>

Compute the centralizer of x in G, i.e. compute a generating set of C_G(x).

We continue the GAP session from <a href="chap3.html#X8345CC25855C9406">3.3</a>. In particular recall the definition of the isomorphism <code class="code">iso</code>.

To compute in GAP the centralizer of an element in a group we use <code class="func">Centralizer</code> (<a href="../../../doc/ref/chap35.html#X7A2BF4527E08803C">Reference: centraliser</a>).

<div class="example"><pre>
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) ])
</pre></div>

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.

<div class="example"><pre>
gap> Size(C);
16
</pre></div>

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 <a href="chap2.html#X872BE72F7B2BBD6B">2.3</a>).

<div class="example"><pre>
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), (); () )
</pre></div>

<a id="X87A59E867A83A798" name="X87A59E867A83A798"></a>

<h4>3.7 Cycle Index Polynomial</h4>

Compute the cycle index polynomial of G either for the imprimitive action or the product action. We do not continue the GAP session from <a href="chap3.html#X8345CC25855C9406">3.3</a> 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.

<div class="example"><pre>
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
</pre></div>

To compute in GAP the cycle index of a a group we use <code class="func">CycleIndex</code> (<a href="../../../doc/ref/chap41.html#X87FDA6838065CDCB">Reference: CycleIndex</a>). Note that by default, the wreath product is given in imprimitive action.

<div class="example"><pre>
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
</pre></div>

For example, the second monomial <code class="code">1/12*x_1^4*x_2</code> tells us that there are exactly frac7212 = 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 <code class="func">ExtRepPolynomialRatFun</code> (<a href="../../../doc/ref/chap66.html#X8406EE2E8775FBAB">Reference: ExtRepPolynomialRatFun</a>).

<div class="example"><pre>
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 ]
</pre></div>

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 <code class="code">[ 1, 4, 2, 1 ], 1/12</code>. The coefficient is <code class="code">1/12</code> and the monomial is encoded by <code class="code">[ 1, 4, 2, 1 ]</code>. The encoding of the monomial again consists of alternating entries, the first one encoding the indeterminant and the second one its exponent. For example <code class="code">[ 1, 4, 2, 1 ]</code> translates to <code class="code">x_1^4 * x_2^1</code>. For more details, see <a href="../../../doc/ref/chap66.html#X7F44CF87801DB965">Reference: The Defining Attributes of Rational Functions</a>.

If we want to consider the wreath product given in product action, we need to use the command <code class="func">WreathProductProductAction</code> (<a href="../../../doc/ref/chap49.html#X82B8DD1C868A3726">Reference: WreathProductProductAction</a>)

<div class="example"><pre>
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
</pre></div>

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 <code class="func">CycleIndexWreathProductImprimitiveAction</code> (<a href="chap4.html#X871F79767C6BC7C0">4.5-1</a>) and <code class="func">CycleIndexWreathProductProductAction</code> (<a href="chap4.html#X799B029E79EACCC3">4.5-2</a>) to compute the cycle index directly from the components K and H without writing down a representation of K ≀ H.

<div class="example"><pre>
gap> c1 := CycleIndexWreathProductImprimitiveAction(K, H);;
gap> c_impr = c1;
true
gap> c2 := CycleIndexWreathProductProductAction(K, H);;
gap> c_prod = c2;
true
</pre></div>

<div class="chlinkprevnextbot"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap2.html">[Previous Chapter]</a> <a href="chap4.html">[Next Chapter]</a> </div>

<div class="chlinkbot">Goto Chapter: <a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>

<hr />
generated by <a href="https://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a>
</body>
</html>

quality100%

¤ Dauer der Verarbeitung: 0.23 Sekunden ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.