| products/Sources/formale Sprachen/GAP/pkg/difsets/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://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.0/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<title>GAP (DifSets) - Chapter 1: Definitions</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"><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> </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>
<p id="mathjaxlink" class="pcenter"><a href="chap1.html">[MathJax off]</a></p>
<p><a id="X84541F61810C741D" name="X84541F61810C741D"></a></p>
<div class="ChapSects"><a href="chap1_mj.html#X84541F61810C741D">1 <span class="Heading">Definitions</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap1_mj.html#X8248A9AB7E689C64">1.1 <span class="Heading">Difference Sets</span></a>
</span>
</div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap1_mj.html#X7A3AC90D79A6AA3B">1.2 <span class="Heading">Difference Sums</span></a>
</span>
</div>
</div>
<h3>1 <span class="Heading">Definitions</span></h3>
<p><a id="X8248A9AB7E689C64" name="X8248A9AB7E689C64"></a></p>
<h4>1.1 <span class="Heading">Difference Sets</span></h4>
<p>A <span class="SimpleMath">\(\langle v, k, \lambda \rangle\)</span>-difference set is a nonempty proper subset <span class="SimpleMath">\(D\)</span> of a finite group <span class="SimpleMath">\(G\)</span> such that <span class="SimpleMath">\(|G| = v\)</span>, <span class="SimpleMath">\(|D| = k\)</span>, and each nonidentity element of <span class="SimpleMath">\(G\)</span> can be written as <span class="SimpleMath">\(d_id_j^{-1}\)</span> for <span class="SimpleMath">\(d_i, d_j \in D\)</span> in exactly <span class="SimpleMath">\(\lambda\)</span> different ways. The standard example is the <span class="SimpleMath">\(\langle 7, 3, 1\rangle\)</span>-difference set <span class="SimpleMath">\(\{1, 2, 4\}\)</span> of the group <span class="SimpleMath">\(\mathbb{Z}/7\mathbb{Z}\)</span> under addition. Additionally, it can easily be shown that every one element subset of a group is a difference set, and the complement of any difference set is also a difference set.</p>
<p>We will often abuse notation and let <span class="SimpleMath">\(D\)</span> denote both the set <span class="SimpleMath">\(D\)</span> and the element</p>
<p class="center">\[D = \sum_{d \in D} d\]</p>
<p>of the group ring <span class="SimpleMath">\(\mathbb{Z}[G]\)</span>. Then define</p>
<p class="center">\[gD = \sum_{d \in D} gd,\]</p>
<p class="center">\[D^\phi = \sum_{d \in D} \phi(d),\]</p>
<p class="center">\[D^{(-1)} = \sum_{d \in D} d^{-1},\]</p>
<p>where <span class="SimpleMath">\(g \in G\)</span> and <span class="SimpleMath">\(\phi\)</span> is a homomorphism with domain <span class="SimpleMath">\(G\)</span>. Using this notation, a difference set in <span class="SimpleMath">\(G\)</span> is an element of the group ring <span class="SimpleMath">\(\mathbb{Z}[G]\)</span> with coefficients from <span class="SimpleMath">\(\{0, 1\}\)</span> such that <span class="SimpleMath">\(DD^{(-1)} = (k-\lambda) + \lambda G\)</span>, where by convention the isolated coefficients <span class="SimpleMath">\((k-\lambda)\)</span> are assumed to be coefficients of the identity.</p>
<p>Two difference sets <span class="SimpleMath">\(D_1, D_2\)</span> are equivalent if both are in the same group <span class="SimpleMath">\(G\)</span> and <span class="SimpleMath">\(D_1 = gD_2^\phi\)</span> for some <span class="SimpleMath">\(g \in G\)</span> and <span class="SimpleMath">\(\phi \in \mathrm{Aut}(G)\)</span>. In other words, <span class="SimpleMath">\(D_1\)</span> is equivalent to <span class="SimpleMath">\(D_2\)</span> if <span class="SimpleMath">\(D_1\)</span> can be mapped to <span class="SimpleMath">\(D_2\)</span> by translation and automorphism in the group <span class="SimpleMath">\(G\)</span>. We say <span class="SimpleMath">\(D_1, D_2\)</span> are translationally equivalent if they are equivalent solely by translation, meaning <span class="SimpleMath">\(D_1 = gD_2\)</span> for some <span class="SimpleMath">\(g \in G\)</span>.</p>
<p>In the package, difference sets are stored as lists of integers that represent the index of the elements in the difference set as found in the list of all elements in the group returned by the <strong class="pkg">GAP</strong> function <code class="code">Elements(G)</code>. For example, the difference set <code class="code">[1, 3, 6, 9, 11, 13]</code> in <code class="code">SmallGroup(16, 5)</code> really consists of the first, third, sixth, ninth, eleventh, and thirteenth elements of the list returned by <code class="code">Elements(SmallGroup(16, 5))</code>. When given as arguments, difference sets in the package are never assumed to be sorted, but many functions will return difference sets in sorted order since sorting is used internally.</p>
<p><a id="X7A3AC90D79A6AA3B" name="X7A3AC90D79A6AA3B"></a></p>
<h4>1.2 <span class="Heading">Difference Sums</span></h4>
<p>A <span class="SimpleMath">\(\langle v, k, \lambda \rangle\)</span>-difference sum in a group <span class="SimpleMath">\(G\)</span> modulo its normal subgroup <span class="SimpleMath">\(N\)</span> is an element <span class="SimpleMath">\(S\)</span> of the group ring <span class="SimpleMath">\(\mathbb{Z}[G/N]\)</span> such that <span class="SimpleMath">\(SS^{(-1)} = (k - \lambda) + \lambda |N|G/N\)</span> and the coefficients of <span class="SimpleMath">\(S\)</span> have values in <span class="SimpleMath">\(\{0, 1, \dots, |N|\}\)</span>. Note that the original <span class="SimpleMath">\(G\)</span> and <span class="SimpleMath">\(N\)</span> are included in the definition, so it makes no sense to talk about a difference sum in some arbitrary group <span class="SimpleMath">\(H\)</span>. The size of a difference sum is the sum of its coefficients, and by defining the complement of <span class="SimpleMath">\(S\)</span> to be <span class="SimpleMath">\(|N|G/N - S\)</span> we can see that, similar to difference sets, size one sums and complements of difference sums are always difference sums.</p>
<p>Two difference sums <span class="SimpleMath">\(S_1, S_2\)</span> are equivalent if both are in the same group <span class="SimpleMath">\(G\)</span> mod its normal subgroup <span class="SimpleMath">\(N\)</span> and <span class="SimpleMath">\(S_1 = gS_2^\phi\)</span> for some <span class="SimpleMath">\(g \in G/N\)</span> and <span class="SimpleMath">\(\phi\)</span> an automorphism of <span class="SimpleMath">\(G/N\)</span> induced by an automorphism of <span class="SimpleMath">\(G\)</span>. Note that not all automorphisms of <span class="SimpleMath">\(G/N\)</span> are induced by automorphisms of <span class="SimpleMath">\(G\)</span>, so our definition here is more restrictive than perhaps expected. As with difference sets, the sums <span class="SimpleMath">\(S_1, S_2\)</span> are translationally equivalent if <span class="SimpleMath">\(S_1 = gS_2\)</span> for some <span class="SimpleMath">\(g \in G/N\)</span>.</p>
<p>In the package, difference sums are stored as lists of integers that represent the values of the coefficients of the group ring elements, with position in the list given by the position of the coset in the list of elements returned by the <strong class="pkg">GAP</strong> function <code class="code">Elements(G/N)</code>. For example, the difference sum <code class="code">[2, 4]</code> in <code class="code">G := SmallGroup(16, 5)</code> mod its normal subgroup <code class="code">Subgroup(G, [G.2, G.3, G.4])</code> has coefficient 2 on the identity coset, and coefficient 4 on the nonidentity coset.</p>
<p>Difference sums can be thought of as a generalization of difference sets. More importantly, however, difference sums can be thought of as images of difference sets in quotients of the original group. In particular, if <span class="SimpleMath">\(\theta : G \to G/N\)</span> is the natural projection, then for any difference set <span class="SimpleMath">\(D\)</span> in <span class="SimpleMath">\(\mathbb{Z}[G]\)</span> we have a difference sum <span class="SimpleMath">\(D^\theta\)</span> in <span class="SimpleMath">\(G\)</span> modulo its normal subgroup <span class="SimpleMath">\(N\)</span>. Additionally, difference sums induce other difference sums in any further quotient. The fundamental idea of the algorithm in this package is that we can reverse this process. Starting with <span class="SimpleMath">\(G\)</span> mod <span class="SimpleMath">\(G\)</span>, where the only difference sum of size <span class="SimpleMath">\(k\)</span> is <code class="code">[k]</code>, we can successively refine this difference sum up a series of quotients of <span class="SimpleMath">\(G\)</span> until reaching <span class="SimpleMath">\(G\)</span> itself. In each step we enumerate all preimages of the difference sums and remove preimages that are not difference sums themselves. In the final step we refine to difference sets. Furthermore, since equivalent difference sums will have equivalent collections of difference sets as preimages, in each step we remove all but one representative of each equivalence class from our collection. This method dramatically decreases the search space for an exhaustive enumeration of all difference sets up to equivalence in <span class="SimpleMath">\(G\)</span>.</p>
<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"><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> </div>
<hr />
<p class="foot">generated by <a href="http://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>
¤ Dauer der Verarbeitung: 0.20 Sekunden
(vorverarbeitet)
¤
*© Formatika GbR, Deutschland
|
|
