Ziele Untersuchung
mit Columbo Integrität von
Datenbanken Interaktion und
Portierbarkeit Ergonomie der
Schnittstellen

Angebot Produkte Projekt Beratung

Mittel Analytik Modellierung Sprachen Algebra Logik Hardware Denken Kreativität

Zusammenhänge Gesellschaft Wirtschaft Branche Firma

Benutzer


products/Sources/formale Sprachen/GAP/pkg/wpe/doc/ (GAP Algebra Version 4.15.1^©) Datei vom 21.9.2024 mit Größe 13 kB

Quelle chap2_mj.html Sprache: HTML

products/Sources/formale Sprachen/GAP/pkg/wpe/doc/chap2_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 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_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="chap1_mj.html">[Previous Chapter]</a> <a href="chap3_mj.html">[Next Chapter]</a> </div>

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

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

</div>
<div class="ContSect"> <a href="chap2_mj.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_mj.html#biBWPE">[BNRW22]</a>.

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

<h4>2.1 Wreath Products</h4>

Let \(G = K \wr 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 \(\pi \in H\) acts on \(f \in K^m\) by setting \(f^{{\pi}} : \{1, \ldots, m\} \rightarrow K, i \mapsto [(i)\pi^{{-1}}]f\). Note that \(G\) naturally embeds into the parent wreath product, that is \(P = K \wr \textrm{Sym}(m) \geq G\).

Formally we can write an element of \(G\) as a tuple \(g = (f, \pi) \in G\), where \(f \in K^m \) is a function \(f : \{1, \ldots, m\} \rightarrow K \) and \(\pi \in H \leq \textrm{Sym}(m)\) is a permutation on \(m\) points. We call \(f\) the base component and \(\pi\) the top component of \(g\).

We can naturally identify a map \(f \in K^m\) with a tuple \((g_1, \ldots, g_m)\), where each \(g_i \in K\) is the image of \(i \in \{1, \ldots, m\}\) under \(f\). This yields a second useful notation for elements in \(G\) by writing \(g = (g_1, \ldots, g_m; \pi)\). 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 \times \langle 1_H \rangle \leq G\) is called the base group of \(G\) and the subgroup \(T = \langle 1_K \rangle^m \times H \leq G\) is called the top group of \(G\).

With the above notation, the multiplication of two elements

\[
g = (f, \pi) = (g_1, \ldots, g_m; \pi),\\
h = (d, \sigma) = (h_1, \ldots, h_m; \sigma)
\]

of \(G = K \wr H\), a wreath product of finite groups, can be written as

\[
g \cdot h = (f \cdot d^{(\pi^{-1})}, \pi \cdot \sigma) = (g_1 \cdot h_{1^\pi}, \ldots, g_m \cdot h_{m^\pi}; \pi \cdot \sigma)\,.
\]

<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_mj.html#biBWPE">[BNRW22]</a>. Chapters 3-5 in <a href="chapBib_mj.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_mj.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_mj.html#X7DF2AEBC8518FFA4">2.1</a> in order to introduce the following concepts.

\(\bf{Definition:}\) We define the territory of an element \(g = (g_1, \ldots, g_m; \pi) \in G\) by \(\textrm{terr}(g) := \textrm{supp}(\pi) \cup \{i : g_i \neq 1\}\), where \(\textrm{supp}(\pi)\) denotes the set of moved points of \(\pi\).

\(\bf{Definition:}\) Two elements \(g, h \in G\) are said to be disjoint if their territories are disjoint.

\(\bf{Lemma:}\) Disjoint elements in \(G\) commute.

\(\bf{Definition:}\) An element \(g = (g_1, \ldots, g_m; \pi) \in G\) is called a wreath cycle if either \(\pi\) is a cycle in \(\textrm{Sym}(n)\) and \(\textrm{terr}(g) = \textrm{supp}(\pi)\), or \(|\textrm{terr}(g)| = 1\).

\(\bf{Example:}\) For example, if we consider the wreath product \( \textrm{Sym}(4) \wr \textrm{Sym}(5) \), the element

\[
{\bf(} \;\; (),\, (1,2,3),\, (),\, (1,2),\, ();\, (1,2,4) \;\; {\bf)}
\]

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

\[
{\bf(} \; (),\, (),\, (1,3),\, (),\, ();\, () \;\; {\bf)}
\]

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

\(\bf{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_mj.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 \in P\) in \(G\) by conjugating it in \(P\) to a restricted representative \(h = g^c \in 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_mj.html#biBWPE">[BNRW22]</a>.

\(\bf{Definition:}\) We say that a wreath cycle \(g = (g_1, \ldots, g_m; \pi) \in G\) is a sparse wreath cycle, if there exists an \(i_0\) such that \(g_i = 1\) for all \(i \neq i_0\).

\(\bf{Example:}\) For example, if we consider the wreath product \( \textrm{Sym}(4) \wr \textrm{Sym}(5) \), the element

\[
{\bf(} \;\; (),\, (1,2,3),\, (),\, (),\, ();\, (1,2,4) \;\; {\bf)}
\]

is a sparse wreath cycle, as well as the element

\[
{\bf(} \;\; (),\, (),\, (1,3),\, (),\, ();\, () \;\; {\bf)} \;.
\]

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

\(\bf{Definition:}\) For a wreath cycle \(g = (f, \pi) \in G\) and a point \(i \in \textrm{terr}(g)\) we define the yade of \(g\) in \(i\) as

\[
[(i)\pi^{0}]f \cdot [(i)\pi^{1}]f \cdots [(i)\pi^{|\pi| - 1}]f \;.
\]

\(\bf{Example:}\) Consider the wreath product \( \textrm{Sym}(4) \wr \textrm{Sym}(5) \), and the wreath cycle

\[
g = (f, \pi) = {\bf(} \;\; (),\, (1,2,3),\, (),\, (1,2),\, ();\, (1,2,4) \;\; {\bf)}.
\]

The yade evaluated at \(i = 1\) is given by

\[
[(1)\pi^{0}]f \cdot [(1)\pi^{1}]f \cdot [(1)\pi^{2}]f = [1]f \cdot [2]f \cdot [4]f = () \cdot (1,2,3) \cdot (1,2) = (2,3)
\]

and the yade evaluated at \(j = 4\) is given by

\[
[(4)\pi^{0}]f \cdot [(4)\pi^{1}]f \cdot [(4)\pi^{2}]f = [4]f \cdot [1]f \cdot [2]f = (1,2) \cdot () \cdot (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.

\(\bf{Theorem:}\) Every element \(g \in P\) can be conjugated by some \(c \in K^m \times \langle 1_H \rangle \leq P\) to an element \(h = g^c \in P\) such that the wreath cycle decomposition of \(h\) consists only of sparse wreath cycles.

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

Messung
C	H	Z	G
89	98	100	95

¤ Dauer der Verarbeitung: 0.8 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.