Quelle chap2.html Sprache: HTML

products/Sources/formale Sprachen/GAP/pkg/wpe/doc/chap2.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 2: Notation</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="chap2" 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="chap1.html">[Previous Chapter]</a> <a href="chap3.html">[Next Chapter]</a> </div>

<a href="chap2_mj.html">[MathJax on]</a>
<a id="X7DD31B407B9402A3" name="X7DD31B407B9402A3"></a>
<div class="ChapSects"><a href="chap2.html#X7DD31B407B9402A3">2 Notation</a>
<div class="ContSect"> <a href="chap2.html#X7DF2AEBC8518FFA4">2.1 Wreath Products</a>

</div>
<div class="ContSect"> <a href="chap2.html#X83A8F3308644ACFA">2.2 Wreath Cycles</a>

</div>
<div class="ContSect"> <a href="chap2.html#X872BE72F7B2BBD6B">2.3 Sparse Wreath Cycles</a>

</div>
</div>

<h3>2 Notation</h3>

This chapter explains the notation of the package WPE, mainly influenced by the accompanying publication <a href="chapBib.html#biBWPE">[BNRW22]</a>.

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

<h4>2.1 Wreath Products</h4>

Let G = K ≀ H be a wreath product of two groups, where H is a permutation group of degree m. The wreath product is defined as the semidirect product of the function space K^m with H, where π ∈ H acts on f ∈ K^m by setting f^{π} : {1, ..., m} → K, i ↦ [(i)π^{-1}]f. Note that G naturally embeds into the parent wreath product, that is P = K ≀ Sym(m) ≥ G.

Formally we can write an element of G as a tuple g = (f, π) ∈ G, where f ∈ K^m is a function f : {1, ..., m} → K and π ∈ H ≤ Sym(m) is a permutation on m points. We call f the base component and π the top component of g.

We can naturally identify a map f ∈ K^m with a tuple (g_1, ..., g_m), where each g_i ∈ K is the image of i ∈ {1, ..., m} under f. This yields a second useful notation for elements in G by writing g = (g_1, ..., g_m; π). Note that we use a semicolon to seperate the base component from the top component. Further we call the element g_i the i-th base component of g.

Analogously, the subgroup B = K^m × ⟨ 1_H ⟩ ≤ G is called the base group of G and the subgroup T = ⟨ 1_K ⟩^m × H ≤ G is called the top group of G.

With the above notation, the multiplication of two elements

g = (f, π) = (g_1, ..., g_m; π), h = (d, σ) = (h_1, ..., h_m; σ)

of G = K ≀ H, a wreath product of finite groups, can be written as

g ⋅ h = (f ⋅ d^(π^-1), π ⋅ σ) = (g_1 ⋅ h_1^π, ..., g_m ⋅ h_m^π; π ⋅ σ).

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

<h4>2.2 Wreath Cycles</h4>

In a permutation group we have the well-known concept of a cycle decomposition. For wreath products we have a similar concept called wreath cycle decomposition that allows us to solve certain computational tasks more efficiently.

Detailed information on wreath cycle decompositions can be found in Chapter 2 in <a href="chapBib.html#biBWPE">[BNRW22]</a>. Chapters 3-5 in <a href="chapBib.html#biBWPE">[BNRW22]</a> describe how these can be exploited for finding conjugating elements, conjugacy classes, and centralisers in wreath products, and Chapter 6 in <a href="chapBib.html#biBWPE">[BNRW22]</a> contains a table of timings of sample computations done with WPE vs. native GAP.

We use the notation from Section <a href="chap2.html#X7DF2AEBC8518FFA4">2.1</a> in order to introduce the following concepts.

Definition: We define the territory of an element g = (g_1, ..., g_m; π) ∈ G by terr(g) := supp(π) ∪ {i : g_i ≠ 1}, where supp(π) denotes the set of moved points of π.

Definition: Two elements g, h ∈ G are said to be disjoint if their territories are disjoint.

Lemma: Disjoint elements in G commute.

Definition: An element g = (g_1, ..., g_m; π) ∈ G is called a wreath cycle if either π is a cycle in Sym(n) and terr(g) = supp(π), or |terr(g)| = 1.

Example: For example, if we consider the wreath product Sym(4) ≀ Sym(5), the element

( (), (1,2,3), (), (1,2), (); (1,2,4) )

is a wreath cycle as described in the first case and the element

( (), (), (1,3), (), (); () )

is a wreath cycle as described in the second case. Moreover, these elements are disjoint and thus commute.

Theorem: Every element of G can be written as a finite product of disjoint wreath cycles in P. This decomposition is unique up to ordering of the factors. We call such a decomposition a wreath cycle decomposition.

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

<h4>2.3 Sparse Wreath Cycles</h4>

We use the notation from Section <a href="chap2.html#X7DF2AEBC8518FFA4">2.1</a> in order to introduce the following concepts.

The main motivation for introducing the concept of sparse wreath cycles is the efficient computation of centralisers of wreath product elements. Simply put, we compute the centraliser C_G(g) of an arbitrary element g ∈ P in G by conjugating it in P to a restricted representative h = g^c ∈ P, computing the centraliser of h in G and then conjugating it back. The wreath cycle decomposition of the representative h consists only of sparse wreath cycles.

More information on sparse wreath cycles and centralisers of wreath product elements can be found in Chapter 5 in <a href="chapBib.html#biBWPE">[BNRW22]</a>.

Definition: We say that a wreath cycle g = (g_1, ..., g_m; π) ∈ G is a sparse wreath cycle, if there exists an i_0 such that g_i = 1 for all i ≠ i_0.

Example: For example, if we consider the wreath product Sym(4) ≀ Sym(5), the element

( (), (1,2,3), (), (), (); (1,2,4) )

is a sparse wreath cycle, as well as the element

( (), (), (1,3), (), (); () ) .

A very important invariant under conjugation is the yade of a wreath cycle.

Definition: For a wreath cycle g = (f, π) ∈ G and a point i ∈ terr(g) we define the yade of g in i as

[(i)π^0]f ⋅ [(i)π^1]f ⋯ [(i)π^|π| - 1]f .

Example: Consider the wreath product Sym(4) ≀ Sym(5), and the wreath cycle

g = (f, π) = ( (), (1,2,3), (), (1,2), (); (1,2,4) ).

The yade evaluated at i = 1 is given by

[(1)π^0]f ⋅ [(1)π^1]f ⋅ [(1)π^2]f = [1]f ⋅ [2]f ⋅ [4]f = () ⋅ (1,2,3) ⋅ (1,2) = (2,3)

and the yade evaluated at j = 4 is given by

[(4)π^0]f ⋅ [(4)π^1]f ⋅ [(4)π^2]f = [4]f ⋅ [1]f ⋅ [2]f = (1,2) ⋅ () ⋅ (1,2,3) = (1,3) .

Up to conjugacy, the yade is independent under the chosen evaluation point i. Moreover, wreath cycles are conjugate over G if and only if the top components are conjugate over H and the yades are conjugate over K. More specific, we can conjugate a wreath cycle g to a sparse wreath cycle h such that the i-th base component of h contains the yade of g in i. This leads to the following result.

Theorem: Every element g ∈ P can be conjugated by some c ∈ K^m × ⟨ 1_H ⟩ ≤ P to an element h = g^c ∈ P such that the wreath cycle decomposition of h consists only of sparse wreath cycles.

<div class="chlinkprevnextbot"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap1.html">[Previous Chapter]</a> <a href="chap3.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>

Messung
C	H	Z	G
81	99	100	93

¤ Dauer der Verarbeitung: 0.10 Sekunden ¤

Wurzel

Suchen

PVS Prover

Isabelle Prover

Cephes Mathematical Library

Vienna Development Method

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 und die Messung sind noch experimentell.