Quelle chap1_mj.html Sprache: HTML

products/Sources/formale Sprachen/GAP/pkg/wpe/doc/chap1_mj.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>
<script type="text/javascript"
 src="https://cdn.jsdelivr.net/npm/mathjax@2/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<title>GAP (WPE) - Chapter 1: Introduction</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="chap1" onload="jscontent()">

<div class="chlinktop">Goto Chapter: <a href="chap0_mj.html">Top</a> <a href="chap1_mj.html">1</a> <a href="chap2_mj.html">2</a> <a href="chap3_mj.html">3</a> <a href="chap4_mj.html">4</a> <a href="chap5_mj.html">5</a> <a href="chapBib_mj.html">Bib</a> <a href="chapInd_mj.html">Ind</a> </div>

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

<a href="chap1.html">[MathJax off]</a>
<a id="X7DFB63A97E67C0A1" name="X7DFB63A97E67C0A1"></a>
<div class="ChapSects"><a href="chap1_mj.html#X7DFB63A97E67C0A1">1 Introduction</a>
<div class="ContSect"> <a href="chap1_mj.html#X8389AD927B74BA4A">1.1 Overview</a>

</div>
<div class="ContSect"> <a href="chap1_mj.html#X7950ED88879EE36F">1.2 Intuitive Research</a>

<div class="ContSSBlock">
 <a href="chap1_mj.html#X83C9D5E6846B299E">1.2-1 The Power of Component-wise Representation</a>

</div></div>
<div class="ContSect"> <a href="chap1_mj.html#X7D96C25680814773">1.3 Efficient Computing</a>

</div>
</div>

<h3>1 Introduction</h3>

This chapter serves as an introduction and showcases some highlights of the package WPE.

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

<h4>1.1 Overview</h4>

The package WPE (Wreath Product Elements) provides methods to work with elements of finite groups which are wreath products. It contributes to <center> intuitive research and efficient computing </center> in wreath products of groups.

It allows access to a representation of wreath products, which we refer to as the generic representation, that is more intuitive to the User when working with wreath products of groups. Access is as straight-forward as using the provided command <code class="code">IsomorphismWreathProduct</code> on a wreath product created by the native GAP command <code class="code">WreathProduct</code>, see <a href="chap1_mj.html#X7950ED88879EE36F">1.2</a> for an example.

Additionally, this representation may have computational benefits over other representations. Note, that just by loading the package WPE and without any additional setup, all optimizations are applied to computations in wreath products created by the native GAP command <code class="code">WreathProduct</code>, by exploiting the generic representation under the hood when appropiate. See <a href="chap1_mj.html#X7D96C25680814773">1.3</a> for a highlight showcase of such computational problems.

In particular, this package provides efficient methods for finding conjugating elements, conjugacy classes, and centralizers in wreath products. The implementations are based on an accompanying publication <a href="chapBib_mj.html#biBWPE">[BNRW22]</a>, that generalizes results from <a href="chapBib_mj.html#biBSpecht">[Spe32]</a> and <a href="chapBib_mj.html#biBOre">[Ore42]</a> on monomial groups, wreath products whose top group is the full symmetric group.

For example, the computation of all \(886\,640\) conjugacy classses of elements of the wreath product \(W = \textrm{M}_{22} \wr \textrm{A}_9\) takes about 12 seconds with WPE. With native GAP this computation is not feasible.

<div class="example"><pre>
gap> LoadPackage("WPE");;
gap> K := MathieuGroup(22);;
gap> H := AlternatingGroup(9);;
gap> G := WreathProduct(K, H);;
gap> C := ConjugacyClasses(G);;
gap> Size(C);
886640
</pre></div>

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

<h4>1.2 Intuitive Research</h4>

One of the two main goals of the package is to provide the User with tools to conduct intuitive research in wreath products of groups on the computer.

In this section we present an example session which demonstrates how we can access the generic representation of a wreath product. As noted in the introduction, no additional setup is required if one wants to benefit from the optimizations for computations in wreath products (see <a href="chap1_mj.html#X7D96C25680814773">1.3</a> for examples on this).

First we construct the wreath product \(G = \textrm{Alt}(5) \wr \textrm{Sym}(7)\) (see <a href="chap2_mj.html#X7DF2AEBC8518FFA4">2.1</a>). For this we use the native GAP command <code class="func">WreathProduct</code> (<a href="../../../doc/ref/chap49_mj.html#X8786EFBC78D7D6ED">Reference: WreathProduct</a>). The resulting group is embedded into a symmetric group on \(5 \cdot 7 = 35\) points via the imprimitive action of the wreath product. The size of the group is

\[
\vert G \vert = \vert\textrm{Alt}(5)\vert^7 \cdot \vert\textrm{Sym}(7)\vert = 60^7 \cdot 5\,040 = 14\,108\,774\,400\,000\,000\;.
\]

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

Now we construct an isomorphism to a wreath product given in generic representation that is provided in WPE. For this, we need to load the package WPE.

<div class="example"><pre>
gap> LoadPackage("WPE");;
gap> iso := IsomorphismWreathProduct(G);;
gap> W := Image(iso);
<group of size 14108774400000000 with 4 generators>
</pre></div>

Let us compare how GAP displays elements of \(G\) and \(W\) respectively. Elements of \(G\) are represented as permutations. In this representation it is hard to identify the base and top components of this element (see <a href="chap2_mj.html#X7DF2AEBC8518FFA4">2.1</a>).

<div class="example"><pre>
gap> g := (1,13,3,14,4,12,2,15,5,11)
> (6,31,21,7,35,25,9,33,23,8,34,24,10,32,22)
> (18,19,20);;
gap> g in G;
true
</pre></div>

Elements of \(W\) however are represented as generic wreath product elements (see <a href="chap2_mj.html#X7DF2AEBC8518FFA4">2.1</a>). This allows us to read off the base and top component of the element easily by either printing or displaying the element. Otherwise, by default the element is viewed in compressed form (see <a href="chap4_mj.html#X8227AD6B7FC637DE">4.4</a>). This printing behaviour is similar to the behaviour of matrices in GAP.

<div class="example"><pre>
gap> w := g ^ iso;
< wreath product element with 7 base components >
gap> Print(w);
[ (1,3,4,2,5), (2,5)(3,4), (), (3,4,5), (1,2)(4,5), (), (), (1,3)(2,7,5) ]
gap> Display(w);
 1 2 3 4 5 6 7 top
( (1,3,4,2,5), (2,5)(3,4), (), (3,4,5), (1,2)(4,5), (), (); (1,3)(2,7,5) )
</pre></div>

Furthermore, we can display and access each component easily with the provided commands.

<div class="example"><pre>
gap> BaseComponentOfWreathProductElement(w, 2);
(2,5)(3,4)
gap> TopComponentOfWreathProductElement(w);
(1,3)(2,7,5)
</pre></div>

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

<h5>1.2-1 The Power of Component-wise Representation</h5>

This component-wise representation is often exactly the one that we encounter in research on wreath products. Thus having it available on the computer greatly sharpens our intuition. We can make very non-trivial statements by looking at the components of such an element, and for the case of the element \(w\) even without a computer.

Let us start off with an easy observation. Just by looking at the top component of \(w\), i.e. \((1,3)(2,7,5)\), we can see that the smallest power of \(w\) that lies in the base group of \(W\) has exponent \(6\), since it has to be equal to the order of the top component.

<div class="example"><pre>
gap> m := Order(w);
30
gap> First( [1 .. m], k -> IsOne(TopComponentOfWreathProductElement(w ^ k)) );
6
gap> Display(w ^ 6);
 1 2 3 4 5 6 7 top
( (1,2,3,5,4), (1,4,5,2,3), (1,2,3,5,4), (), (1,3,2,5,4), (), (1,3,2,5,4); () )
</pre></div>

Now let us be more advanced. Just by looking at the element \(w\), we can deduce structural information on the conjugacy class \(w^W\). All elements conjugate to \(w\) in \(W = K \wr H\) must have at least one trivial base component, since the territory of \(w\) (see <a href="chap2_mj.html#X83A8F3308644ACFA">2.2</a>) contains exactly six elements, whereas the top group acts on seven points.

<div class="example"><pre>
gap> Length(Territory(w));
6
gap> NrMovedPoints(H);
7
</pre></div>

On the other hand, all such elements must have at least three non-trivial base components, since the wreath cycle decomposition of \(w\) (see <a href="chap2_mj.html#X83A8F3308644ACFA">2.2</a>) contains exactly three wreath cycles with non-trivial yades (see <a href="chap2_mj.html#X872BE72F7B2BBD6B">2.3</a>).

<div class="example"><pre>
gap> Number(WreathCycleDecomposition(w), c -> not IsOne(Yade(c)));
3
</pre></div>

Moreover, for each integer \(k\) with \(3 \leq k \leq 6\) there exists at least one conjugate element with exactly \(k\) non-trivial base components.

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

<h4>1.3 Efficient Computing</h4>

One of the two main goals of the package is to empower the User to carry out efficient computations in wreath products of groups on the computer.

In this section we present a highlight showcase of computational problems that benefit from the generic representation. 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_mj.html#X8786EFBC78D7D6ED">Reference: WreathProduct</a>), and the generic representation provided by WPE is used under the hood whenever appropiate.

We only give a summary of some computational problems that now become approachable on the computer, and include examples for such computations in Chapter <a href="chap3_mj.html#X81932F777898AD72">3</a> containing extensive GAP sessions that can be followed like a tutorial.

In the following let \(G = K \wr H\) be a wreath product of finite groups, where \(H \leq \textrm{Sym}(m)\). Further let \(x, y \in P = K \wr \textrm{Sym}(m)\) be elements of the parent wreath product \(P\) which is given in the same representation as \(G\).

<dl>
<dt> Conjugacy Problem </dt>
<dd>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\).

</dd>
<dt> Conjugacy Classes </dt>
<dd>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\).

</dd>
<dt> Centralizer </dt>
<dd>Compute the centralizer of \(x\) in \(G\), i.e. compute a generating set of \(C_G(x)\).

</dd>
<dt> Cycle Index Polynomial</dt>
<dd>Compute the cycle index polynomial of \(G\) either for the imprimitive action or the product action.

</dd>
</dl>

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

<div class="chlinkbot">Goto Chapter: <a href="chap0_mj.html">Top</a> <a href="chap1_mj.html">1</a> <a href="chap2_mj.html">2</a> <a href="chap3_mj.html">3</a> <a href="chap4_mj.html">4</a> <a href="chap5_mj.html">5</a> <a href="chapBib_mj.html">Bib</a> <a href="chapInd_mj.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.11 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.