Quelle chap3_mj.html Sprache: HTML

products/Sources/formale Sprachen/GAP/pkg/twistedconjugacy/doc/chap3_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 (TwistedConjugacy) - Chapter 3: Twisted conjugacy</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_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="chap6_mj.html">6</a> <a href="chap7_mj.html">7</a> <a href="chap8_mj.html">8</a> <a href="chap9_mj.html">9</a> <a href="chap10_mj.html">10</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="chap2_mj.html">[Previous Chapter]</a> <a href="chap4_mj.html">[Next Chapter]</a> </div>

<a href="chap3.html">[MathJax off]</a>
<a id="X78DFA75A82655B7F" name="X78DFA75A82655B7F"></a>
<div class="ChapSects"><a href="chap3_mj.html#X78DFA75A82655B7F">3 Twisted conjugacy</a>
<div class="ContSect"> <a href="chap3_mj.html#X86BE54A080E991A8">3.1 The twisted conjugation action</a>

<div class="ContSSBlock">
 <a href="chap3_mj.html#X79CF6BDA7851496D">3.1-1 TwistedConjugation</a>
</div></div>
<div class="ContSect"> <a href="chap3_mj.html#X7838A5A678158C68">3.2 The twisted conjugacy (search) problem</a>

<div class="ContSSBlock">
 <a href="chap3_mj.html#X809D34107CFE8082">3.2-1 IsTwistedConjugate</a>
 <a href="chap3_mj.html#X8493E3818276A562">3.2-2 RepresentativeTwistedConjugation</a>
</div></div>
<div class="ContSect"> <a href="chap3_mj.html#X8554A80A7A7430C4">3.3 The multiple twisted conjugacy (search) problem</a>

</div>
</div>

<h3>3 Twisted conjugacy</h3>

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

<h4>3.1 The twisted conjugation action</h4>

Let \(G\) and \(H\) be groups and let \(\varphi\) and \(\psi\) be group homomorphisms from \(H\) to \(G\). The pair \((\varphi,\psi)\) induces a (right) group action of \(H\) on \(G\) given by the map

\[G \times H \to G
\colon (g,h) \mapsto \varphi(h)^{-1} g\,\psi(h).\]

This group action is called \((\varphi,\psi)\)-twisted conjugation.

If \(G = H\), \(\varphi\) is an endomorphism of \(G\) and \(\psi = \operatorname{id}_G\), then the action is usually called \(\varphi\)-twisted conjugation. In general, for the TwistedConjugacy package, many functions will take two homomorphisms <var class="Arg">hom1</var> and <var class="Arg">hom2</var> as arguments. However, if <var class="Arg">hom1</var> is an endomorphism, <var class="Arg">hom2</var> can be omitted, in which case it is automatically taken to be the identity map.

Similarly, some functions will take two elements <var class="Arg">g1</var> and <var class="Arg">g2</var> as arguments. If <var class="Arg">g2</var> is omitted, it is automatically taken to be the identity element.

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

<h5>3.1-1 TwistedConjugation</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; TwistedConjugation</code>( <var class="Arg">hom1</var>[, <var class="Arg">hom2</var>] )</td><td class="tdright">( function )</td></tr></table></div>
Returns: a function that maps the pair <code class="code">(g,h)</code> to <var class="Arg">hom1</var><code class="code">(h)⁻¹</code> <code class="code">g</code> <var class="Arg">hom2</var><code class="code">(h)</code>.

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

<h4>3.2 The twisted conjugacy (search) problem</h4>

Given groups \(G\) and \(H\), group homomorphisms \(\varphi\) and \(\psi\) from \(H\) to \(G\) and elements \(g_1, g_2 \in G\), the twisted conjugacy problem is the decision problem that asks whether \(g_1\) and \(g_2\) are \((\varphi,\psi)\)-twisted conjugate. The twisted conjugacy search problem is the problem of determining an explicit \(h\) such that \(\varphi(h)^{-1}g_1\psi(h) = g_2\) (under the assumption that such \(h\) exists).

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

<h5>3.2-1 IsTwistedConjugate</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsTwistedConjugate</code>( <var class="Arg">hom1</var>[, <var class="Arg">hom2</var>], <var class="Arg">g1</var>[, <var class="Arg">g2</var>] )</td><td class="tdright">( function )</td></tr></table></div>
Returns: <code class="keyw">true</code> if <var class="Arg">g1</var> and <var class="Arg">g2</var> are <code class="code">(<var class="Arg">hom1</var>,<var class="Arg">hom2</var>)</code>-twisted conjugate, otherwise <code class="keyw">false</code>.

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

<h5>3.2-2 RepresentativeTwistedConjugation</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; RepresentativeTwistedConjugation</code>( <var class="Arg">hom1</var>[, <var class="Arg">hom2</var>], <var class="Arg">g1</var>[, <var class="Arg">g2</var>] )</td><td class="tdright">( function )</td></tr></table></div>
Returns: an element that maps <var class="Arg">g1</var> to <var class="Arg">g2</var> under the <code class="code">(<var class="Arg">hom1</var>,<var class="Arg">hom2</var>)</code>-twisted conjugacy action, or <code class="keyw">fail</code> if no such element exists.

If the source group is finite, this function relies on orbit-stabiliser algorithms provided by GAP. Otherwise, it relies on a mixture of the algorithms described in <a href="chapBib_mj.html#biBroma16-a">[Rom16, Thm. 3]</a>, <a href="chapBib_mj.html#biBbkl20-a">[BKL+20, Sec. 5.4]</a>, <a href="chapBib_mj.html#biBroma21-a">[Rom21, Sec. 7]</a> and <a href="chapBib_mj.html#biBdt21-a">[DT21]</a>.

<div class="example"><pre>
gap> G := AlternatingGroup( 6 );;
gap> H := SymmetricGroup( 5 );;
gap> phi := GroupHomomorphismByImages( H, G, [ (1,2)(3,5,4), (2,3)(4,5) ],
> [ (1,4)(3,6), () ] );;
gap> psi := GroupHomomorphismByImages( H, G, [ (1,2)(3,5,4), (2,3)(4,5) ],
> [ (1,2)(3,4), () ] );;
gap> tc := TwistedConjugation( phi, psi );;
gap> g1 := (4,6,5);;
gap> g2 := (1,6,4,2)(3,5);;
gap> IsTwistedConjugate( psi, phi, g1, g2 );
false
gap> h := RepresentativeTwistedConjugation( phi, psi, g1, g2 );
(1,2)
gap> tc( g1, h ) = g2;
true
</pre></div>

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

<h4>3.3 The multiple twisted conjugacy (search) problem</h4>

Let \(H\) and \(G_1, \ldots, G_n\) be groups. For each \(i \in \{1,\ldots,n\}\), let \(g_i,g_i' \in G_i\) and let \(\varphi_i,\psi_i\colon H \to G_i\) be group homomorphisms. The multiple twisted conjugacy problem is the decision problem that asks whether there exists some \(h \in H\) such that \(\varphi_i(h)^{-1}g_i\psi_i(h) = g_i'\) for all \(i \in \{1,\ldots,n\}\). The multiple twisted conjugacy search problem is the problem of determining an explicit \(h\) such that \(\varphi_i(h)^{-1}g_i\psi_i(h) = g_i'\) for all \(i \in \{1,\ldots,n\}\) (under the assumption that such \(h\) exists).

<code class="func">IsTwistedConjugate</code> (<a href="chap3_mj.html#X809D34107CFE8082">3.2-1</a>) and <code class="func">RepresentativeTwistedConjugation</code> (<a href="chap3_mj.html#X8493E3818276A562">3.2-2</a>) can take lists instead of their usual arguments to solve these problems.

<div class="example"><pre>
gap> H := SymmetricGroup( 5 );;
gap> G := AlternatingGroup( 6 );;
gap> phi := GroupHomomorphismByImages( H, G, [ (1,2)(3,5,4), (2,3)(4,5) ],
> [ (1,4)(3,6), () ] );;
gap> psi := GroupHomomorphismByImages( H, G, [ (1,2)(3,5,4), (2,3)(4,5) ],
> [ (1,2)(3,4), () ] );;
gap> tau := GroupHomomorphismByImages( H, G, [ (1,2)(3,5,4), (2,3)(4,5) ],
> [ (1,2)(3,6), () ] );;
gap> khi := GroupHomomorphismByImages( H, G, [ (1,2)(3,5,4), (2,3)(4,5) ],
> [ (1,3)(4,6), () ] );;
gap> IsTwistedConjugate( [ phi, psi ], [ khi, tau ],
> [ (1,5)(4,6), (1,4)(3,5) ], [ (1,4,5,3,6), (2,4,5,6,3) ] );
true
gap> RepresentativeTwistedConjugation( [ phi, psi ], [ khi, tau ],
> [ (1,5)(4,6), (1,4)(3,5) ], [ (1,4,5,3,6), (2,4,5,6,3) ] );
(1,2)
</pre></div>

<div class="chlinkprevnextbot"> <a href="chap0_mj.html">[Top of Book]</a> <a href="chap0_mj.html#contents">[Contents]</a> <a href="chap2_mj.html">[Previous Chapter]</a> <a href="chap4_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="chap6_mj.html">6</a> <a href="chap7_mj.html">7</a> <a href="chap8_mj.html">8</a> <a href="chap9_mj.html">9</a> <a href="chap10_mj.html">10</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
81	100	100	93

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