Quellcodebibliothek Statistik Leitseite products/sources/formale Sprachen/GAP/pkg/twistedconjugacy/doc/   (Algebra von RWTH Aachen Version 4.15.1©)  Datei vom 12.9.2025 mit Größe 13 kB image not shown  

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"><span class="chlink1">Goto Chapter: </span><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>

<p id="mathjaxlink" class="pcenter"><a href="chap3.html">[MathJax off]</a></p>
<p><a id="X78DFA75A82655B7F" name="X78DFA75A82655B7F"></a></p>
<div class="ChapSects"><a href="chap3_mj.html#X78DFA75A82655B7F">3 <span class="Heading">Twisted conjugacy</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3_mj.html#X86BE54A080E991A8">3.1 <span class="Heading">The twisted conjugation action</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X79CF6BDA7851496D">3.1-1 TwistedConjugation</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3_mj.html#X7838A5A678158C68">3.2 <span class="Heading">The twisted conjugacy (search) problem</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X809D34107CFE8082">3.2-1 IsTwistedConjugate</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X8493E3818276A562">3.2-2 RepresentativeTwistedConjugation</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3_mj.html#X8554A80A7A7430C4">3.3 <span class="Heading">The multiple twisted conjugacy (search) problem</span></a>
</span>
</div>
</div>

<h3>3 <span class="Heading">Twisted conjugacy</span></h3>

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

<h4>3.1 <span class="Heading">The twisted conjugation action</span></h4>

<p>Let <span class="SimpleMath">\(G\)</span> and <span class="SimpleMath">\(H\)</span> be groups and let <span class="SimpleMath">\(\varphi\)</span> and <span class="SimpleMath">\(\psi\)</span> be group homomorphisms from <span class="SimpleMath">\(H\)</span> to <span class="SimpleMath">\(G\)</span>. The pair <span class="SimpleMath">\((\varphi,\psi)\)</span> induces a (right) group action of <span class="SimpleMath">\(H\)</span> on <span class="SimpleMath">\(G\)</span> given by the map</p>

<p class="center">\[G \times H \to G
 \colon (g,h) \mapsto \varphi(h)^{-1} g\,\psi(h).\]</p>

<p>This group action is called <em><span class="SimpleMath">\((\varphi,\psi)\)</span>-twisted conjugation</em>.</p>

<p>If <span class="SimpleMath">\(G = H\)</span>, <span class="SimpleMath">\(\varphi\)</span> is an endomorphism of <span class="SimpleMath">\(G\)</span> and <span class="SimpleMath">\(\psi = \operatorname{id}_G\)</span>, then the action is usually called <em><span class="SimpleMath">\(\varphi\)</span>-twisted conjugation</em>. In general, for the <strong class="pkg">TwistedConjugacy</strong> 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.</p>

<p>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.</p>

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

<h5>3.1-1 TwistedConjugation</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ TwistedConjugation</code>( <var class="Arg">hom1</var>[, <var class="Arg">hom2</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>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>.</p>

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

<h4>3.2 <span class="Heading">The twisted conjugacy (search) problem</span></h4>

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

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

<h5>3.2-1 IsTwistedConjugate</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ 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>
<p>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>.</p>

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

<h5>3.2-2 RepresentativeTwistedConjugation</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ 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>
<p>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.</p>

<p>If the source group is finite, this function relies on orbit-stabiliser algorithms provided by <strong class="pkg">GAP</strong>. 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>.</p>


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

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

<h4>3.3 <span class="Heading">The multiple twisted conjugacy (search) problem</span></h4>

<p>Let <span class="SimpleMath">\(H\)</span> and <span class="SimpleMath">\(G_1, \ldots, G_n\)</span> be groups. For each <span class="SimpleMath">\(i \in \{1,\ldots,n\}\)</span>, let <span class="SimpleMath">\(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'\)</span> for all <span class="SimpleMath">\(i \in \{1,\ldots,n\}\)</span>. The <em>multiple twisted conjugacy search problem</em> is the problem of determining an explicit <span class="SimpleMath">\(h\)</span> such that <span class="SimpleMath">\(\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).



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


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">H := SymmetricGroup( 5 );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">G := AlternatingGroup( 6 );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">phi := GroupHomomorphismByImages( H, G, [ (1,2)(3,5,4), (2,3)(4,5) ],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [ (1,4)(3,6), () ] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">psi := GroupHomomorphismByImages( H, G, [ (1,2)(3,5,4), (2,3)(4,5) ],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [ (1,2)(3,4), () ] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">tau := GroupHomomorphismByImages( H, G, [ (1,2)(3,5,4), (2,3)(4,5) ],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [ (1,2)(3,6), () ] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">khi := GroupHomomorphismByImages( H, G, [ (1,2)(3,5,4), (2,3)(4,5) ],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [ (1,3)(4,6), () ] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsTwistedConjugate( [ phi, psi ], [ khi, tau ],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [ (1,5)(4,6), (1,4)(3,5) ], [ (1,4,5,3,6), (2,4,5,6,3) ] );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">RepresentativeTwistedConjugation( [ phi, psi ], [ khi, tau ],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [ (1,5)(4,6), (1,4)(3,5) ], [ (1,4,5,3,6), (2,4,5,6,3) ] );</span>
(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"><span class="chlink1">Goto Chapter: </span><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 />
<p class="foot">generated by <a href="https://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>

98%


¤ Dauer der Verarbeitung: 0.16 Sekunden  (vorverarbeitet)  ¤

*© Formatika GbR, Deutschland




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.