<?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 (ResClasses) - Chapter 2: Unions of Residue Classes with Fixed Representatives</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" />
</head>
<body>
<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><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="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<div class="chlinkprevnexttop"> <a href="chap0.html">Top of Book</a> <a href="chap1.html">Previous Chapter</a> <a href="chap3.html">Next Chapter</a> </div>
<p><a id="X87871B5A86254179" name="X87871B5A86254179"></a></p>
<div class="ChapSects"><a href="chap2.html#X87871B5A86254179">2. <span class="Heading">Unions of Residue Classes with Fixed Representatives</span></a>
<div class="ContSect"><span class="nocss"> </span><a href="chap2.html#X78BE0FA38691B1B6">2.1 <span class="Heading">
Entering unions of residue classes with fixed representatives
</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X831C976D876FDAD3">2.1-1 ResidueClassWithFixedRepresentative</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X871ED1D17AE52A95">2.1-2 UnionOfResidueClassesWithFixedReps</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X8198386A809A6B17">2.1-3 AllResidueClassesWithFixedRepsModulo</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap2.html#X7C26C7E682C2FD2E">2.2 <span class="Heading">
Methods for unions of residue classes with fixed representatives
</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X808442EC7F3F5748">2.2-1 Multiplicity</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X8296A97779FE8B72">2.2-2 Union</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X7FC166A57F1F5601">2.2-3 Intersection</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X82A4EE727E67AB98">2.2-4 Difference</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap2.html#X7A1CBA1B7E6B93D0">2.3 <span class="Heading">
The invariant Delta
</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X78DCAB2C7C4E37E8">2.3-1 Delta</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X7E109A6E81A0465C">2.3-2 RepresentativeStabilizingRefinement</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap2.html#X7BA9DE337DF742E9">2.4 <span class="Heading">
The categories of unions of residue classes with fixed rep's
</span></a>
</div>
</div>
<h3>2. <span class="Heading">Unions of Residue Classes with Fixed Representatives</span></h3>
<p><strong class="pkg">ResClasses</strong> supports computations with unions of residue classes which are endowed with distinguished ("fixed") representatives. These unions of residue classes can be viewed as multisets of ring elements. The residue classes forming such a union do not need to be disjoint or even only distinct.</p>
<p><a id="X78BE0FA38691B1B6" name="X78BE0FA38691B1B6"></a></p>
<h4>2.1 <span class="Heading">
Entering unions of residue classes with fixed representatives
</span></h4>
<p><a id="X831C976D876FDAD3" name="X831C976D876FDAD3"></a></p>
<h5>2.1-1 ResidueClassWithFixedRepresentative</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> ResidueClassWithFixedRepresentative</code>( <var class="Arg">R, m, r</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> ResidueClassWithFixedRepresentative</code>( <var class="Arg">m, r</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><b>Returns: </b>The residue class <var class="Arg">r</var> mod <var class="Arg">m</var> of the ring <var class="Arg">R</var>, with the fixed representative <var class="Arg">r</var>.</p>
<p>If the argument <var class="Arg">R</var> is omitted, it defaults to <code class="code">Integers</code>. Residue classes with fixed representatives have the property <code class="code">IsResidueClassWithFixedRepresentative</code>. The fixed representative <var class="Arg">r</var> can be retrieved by the operation <code class="code">Residue</code>, and the modulus <var class="Arg">m</var> can be retrieved by the operation <code class="code">Modulus</code>.</p>
<table class="example">
<tr><td><pre>
gap> ResidueClassWithFixedRepresentative(Integers,2,1);
[1/2]
</pre></td></tr></table>
<p><a id="X871ED1D17AE52A95" name="X871ED1D17AE52A95"></a></p>
<h5>2.1-2 UnionOfResidueClassesWithFixedReps</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> UnionOfResidueClassesWithFixedReps</code>( <var class="Arg">R, classes</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> UnionOfResidueClassesWithFixedReps</code>( <var class="Arg">classes</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><b>Returns: </b>The union of the residue classes <var class="Arg">classes</var>[i][2] mod <var class="Arg">classes</var>[i][1] of the ring <var class="Arg">R</var>, with fixed representatives <var class="Arg">classes</var>[i][2].</p>
<p>The argument <var class="Arg">classes</var> must be a list of pairs of elements of the ring <var class="Arg">R</var>. Their first entries -- the moduli -- must be nonzero. If the argument <var class="Arg">R</var> is omitted, it defaults to <code class="code">Integers</code>.</p>
<table class="example">
<tr><td><pre>
gap> UnionOfResidueClassesWithFixedReps(Integers,[[2,4],[3,9]]);
[4/2] U [9/3]
</pre></td></tr></table>
<p>There is a method for the operation <code class="code">Modulus</code> which returns the lcm of the moduli of the residue classes forming such a union. Further there is an operation <code class="code">Classes</code> for retrieving the list of classes which has been passed as an argument to <code class="code">UnionOfResidueClassesWithFixedReps</code>. The operation <code class="code">AsListOfClasses</code> does the same, except that the returned list contains residue classes instead of pairs <code class="code">[<var class="Arg">modulus</var>,<var class="Arg">residue</var>]</code>. There are methods for <code class="code">Print</code>, <code class="code">String</code> and <code class="code">Display</code> available for unions of residue classes with fixed representatives.</p>
<p><a id="X8198386A809A6B17" name="X8198386A809A6B17"></a></p>
<h5>2.1-3 AllResidueClassesWithFixedRepsModulo</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AllResidueClassesWithFixedRepsModulo</code>( <var class="Arg">R, m</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AllResidueClassesWithFixedRepsModulo</code>( <var class="Arg">m</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><b>Returns: </b>A sorted list of all residue classes (mod <var class="Arg">m</var>) of the ring <var class="Arg">R</var>, with fixed representatives.</p>
<p>If the argument <var class="Arg">R</var> is omitted it defaults to the default ring of <var class="Arg">m</var>, cf. the documentation of <code class="code">DefaultRing</code> in the <strong class="pkg">GAP</strong> reference manual. The representatives are the same as those chosen by the operation <code class="code">mod</code>. See also <code class="func">AllResidueClassesModulo</code> (<a href="chap1.html#X8326D6F285081E0F"><b>1.1-3</b></a>).</p>
<table class="example">
<tr><td><pre>
gap> AllResidueClassesWithFixedRepsModulo(4);
[ [0/4], [1/4], [2/4], [3/4] ]
</pre></td></tr></table>
<p><a id="X7C26C7E682C2FD2E" name="X7C26C7E682C2FD2E"></a></p>
<h4>2.2 <span class="Heading">
Methods for unions of residue classes with fixed representatives
</span></h4>
<p>Throughout this chapter, the argument <var class="Arg">R</var> denotes the underlying ring, and the arguments <var class="Arg">U</var>, <var class="Arg">U1</var> and <var class="Arg">U2</var> denote unions of residue classes of <var class="Arg">R</var> with fixed representatives.</p>
<p>Unions of residue classes with fixed representatives are multisets. Elements and residue classes can be contained with multiplicities:</p>
<p><a id="X808442EC7F3F5748" name="X808442EC7F3F5748"></a></p>
<h5>2.2-1 Multiplicity</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Multiplicity</code>( <var class="Arg">x, U</var> )</td><td class="tdright">( method )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Multiplicity</code>( <var class="Arg">cl, U</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p><b>Returns: </b>The multiplicity of <var class="Arg">x</var> in <var class="Arg">U</var> regarded as a multiset of ring elements, resp. the multiplicity of the residue class <var class="Arg">cl</var> in <var class="Arg">U</var> regarded as a multiset of residue classes.</p>
<table class="example">
<tr><td><pre>
gap> U := UnionOfResidueClassesWithFixedReps(Integers,[[2,0],[3,0]]);
[0/2] U [0/3]
gap> List([0..20],n->Multiplicity(n,U));
[ 2, 0, 1, 1, 1, 0, 2, 0, 1, 1, 1, 0, 2, 0, 1, 1, 1, 0, 2, 0, 1 ]
gap> Multiplicity(ResidueClassWithFixedRep(2,0),U);
1
</pre></td></tr></table>
<p>Let <code class="code">U</code> be a union of residue classes with fixed representatives. The multiset <code class="code">U</code> can have an attribute <code class="code">Density</code> which denotes its <em>natural density</em> as a multiset, i.e. elements with multiplicity k count k-fold. The multiset <code class="code">U</code> has the property <code class="code">IsOverlappingFree</code> if it consists of pairwise disjoint residue classes. The set-theoretic union of the residue classes forming <code class="code">U</code> can be determined by the operation <code class="code">AsOrdinaryUnionOfResidueClasses</code>. The object returned by this operation is an "ordinary" residue class union as described in Chapter <a href="chap1.html#X815A3DDE7C0BC44A"><b>1.</b></a>.</p>
<table class="example">
<tr><td><pre>
gap> U := UnionOfResidueClassesWithFixedReps(Integers,[[2,0],[3,0]]);
[0/2] U [0/3]
gap> Density(U);
5/6
gap> IsOverlappingFree(U);
false
gap> AsOrdinaryUnionOfResidueClasses(U);
Z \ Union of the residue classes 1(6) and 5(6) of Z
gap> Density(last);
2/3
</pre></td></tr></table>
<p>In the sequel we abbreviate the term "the multiset of ring elements endowed with the structure of a union of residue classes with fixed representatives" by "the multiset".</p>
<p>There are methods for <code class="code">+</code> and <code class="code">-</code> available for computing the multiset of sums u + x, u in U, the multiset of differences u - x resp. x - u, u in U and the multiset of the additive inverses of the elements of U. Further there are methods for <code class="code">*</code> and <code class="code">/</code> available for computing the multiset of products x * u, u in U and the multiset of quotients u/x, u in U. The division method requires all elements of <code class="code">U</code> to be divisible by x. If the underlying ring is the ring of integers, scalar multiplication and division leave delta invariant (-> <code class="func">Delta</code> (<a href="chap2.html#X78DCAB2C7C4E37E8"><b>2.3-1</b></a>)).</p>
<table class="example">
<tr><td><pre>
gap> U := UnionOfResidueClassesWithFixedReps(Integers,[[2,0],[3,0]]);
[0/2] U [0/3]
gap> U + 7;
[7/2] U [7/3]
gap> U - 7; 7 - U; -U;
[-7/2] U [-7/3]
[7/-3] U [7/-2]
[0/-3] U [0/-2]
gap> V := 2 * U;
[0/4] U [0/6]
gap> V/2;
[0/2] U [0/3]
</pre></td></tr></table>
<p><a id="X8296A97779FE8B72" name="X8296A97779FE8B72"></a></p>
<h5>2.2-2 Union</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Union</code>( <var class="Arg">U1, U2</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p><b>Returns: </b>The union of <var class="Arg">U1</var> and <var class="Arg">U2</var>.</p>
<p>The multiplicity of any ring element or residue class in the union is the sum of its multiplicities in the arguments. It holds that <code class="code">Delta(Union(<var class="Arg">U1</var>,<var class="Arg">U2</var>)) = Delta(<var class="Arg">U1</var>) + Delta(<var class="Arg">U2</var>)</code>. (-> <code class="func">Delta</code> (<a href="chap2.html#X78DCAB2C7C4E37E8"><b>2.3-1</b></a>)).</p>
<table class="example">
<tr><td><pre>
gap> U := UnionOfResidueClassesWithFixedReps(Integers,[[2,0],[3,0]]);
[0/2] U [0/3]
gap> Union(U,U);
[0/2] U [0/2] U [0/3] U [0/3]
</pre></td></tr></table>
<p><a id="X7FC166A57F1F5601" name="X7FC166A57F1F5601"></a></p>
<h5>2.2-3 Intersection</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Intersection</code>( <var class="Arg">U1, U2</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p><b>Returns: </b>The intersection of <var class="Arg">U1</var> and <var class="Arg">U2</var>.</p>
<p>The multiplicity of any residue class in the intersection is the minimum of its multiplicities in the arguments.</p>
<table class="example">
<tr><td><pre>
gap> U := UnionOfResidueClassesWithFixedReps(Integers,[[2,0],[3,0]]);
[0/2] U [0/3]
gap> Intersection(U,ResidueClassWithFixedRep(2,0));
[0/2]
gap> Intersection(U,ResidueClassWithFixedRep(6,0));
Empty union of residue classes of Z with fixed representatives
</pre></td></tr></table>
<p><a id="X82A4EE727E67AB98" name="X82A4EE727E67AB98"></a></p>
<h5>2.2-4 Difference</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Difference</code>( <var class="Arg">U1, U2</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p><b>Returns: </b>The difference of <var class="Arg">U1</var> and <var class="Arg">U2</var>.</p>
<p>The multiplicity of any residue class in the difference is its multiplicity in <var class="Arg">U1</var> minus its multiplicity in <var class="Arg">U2</var>, if this value is nonnegative. The difference of the empty residue class union with fixed representatives and some residue class [r/m] is set equal to [(m-r)/m]. It holds that <code class="code">Delta(Difference(<var class="Arg">U1</var>,<var class="Arg">U2</var>)) = Delta(<var class="Arg">U1</var>) - Delta(<var class="Arg">U2</var>)</code>. (-> <code class="func">Delta</code> (<a href="chap2.html#X78DCAB2C7C4E37E8"><b>2.3-1</b></a>)).</p>
<table class="example">
<tr><td><pre>
gap> U := UnionOfResidueClassesWithFixedReps(Integers,[[2,0],[3,0]]);
[0/2] U [0/3]
gap> V := UnionOfResidueClassesWithFixedReps(Integers,[[3,0],[5,2]]);
[0/3] U [2/5]
gap> Difference(U,V);
[0/2] U [3/5]
</pre></td></tr></table>
<p><a id="X7A1CBA1B7E6B93D0" name="X7A1CBA1B7E6B93D0"></a></p>
<h4>2.3 <span class="Heading">
The invariant Delta
</span></h4>
<p><a id="X78DCAB2C7C4E37E8" name="X78DCAB2C7C4E37E8"></a></p>
<h5>2.3-1 Delta</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Delta</code>( <var class="Arg">U</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><b>Returns: </b>The value of the invariant delta of the residue class union <var class="Arg">U</var>.</p>
<p>For a residue class [r/m] with fixed representative we set delta([r/m]) := r/m - 1/2, and extend this definition additively to unions of such residue classes. If no representatives are fixed, this definition is still unique (mod 1). There is a related invariant rho which is defined by e^delta(U) pi i. The corresponding attribute is called <code class="code">Rho</code>.</p>
<table class="example">
<tr><td><pre>
gap> U := UnionOfResidueClassesWithFixedReps(Integers,[[2,3],[3,4]]);
[3/2] U [4/3]
gap> Delta(U) = (3/2-1/2) + (4/3-1/2);
true
gap> V := RepresentativeStabilizingRefinement(U,3);
[3/6] U [5/6] U [7/6] U [4/9] U [7/9] U [10/9]
gap> Delta(V) = Delta(U);
true
gap> Rho(V);
E(12)^11
</pre></td></tr></table>
<p><a id="X7E109A6E81A0465C" name="X7E109A6E81A0465C"></a></p>
<h5>2.3-2 RepresentativeStabilizingRefinement</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> RepresentativeStabilizingRefinement</code>( <var class="Arg">U, k</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p><b>Returns: </b>The representative stabilizing refinement of <var class="Arg">U</var> into <var class="Arg">k</var> parts.</p>
<p>The <em>representative stabilizing refinement</em> of a residue class [r/m] of Z into k parts is defined by [r/km] cup [(r+m)/km] cup dots cup [(r+(k-1)m)/km]. This definition is extended in the obvious way to unions of residue classes.</p>
<p>If the argument <var class="Arg">k</var> is zero, the method performs a simplification of <var class="Arg">U</var> by joining appropriate residue classes, if this is possible.</p>
<p>In any case the value of <code class="code">Delta(<var class="Arg">U</var>)</code> is invariant under this operation (-> <code class="func">Delta</code> (<a href="chap2.html#X78DCAB2C7C4E37E8"><b>2.3-1</b></a>)).</p>
<table class="example">
<tr><td><pre>
gap> U := UnionOfResidueClassesWithFixedReps(Integers,[[2,0],[3,0]]);
[0/2] U [0/3]
gap> RepresentativeStabilizingRefinement(U,4);
[0/8] U [2/8] U [4/8] U [6/8] U [0/12] U [3/12] U [6/12] U [9/12]
gap> RepresentativeStabilizingRefinement(last,0);
[0/2] U [0/3]
</pre></td></tr></table>
<p><a id="X7BA9DE337DF742E9" name="X7BA9DE337DF742E9"></a></p>
<h4>2.4 <span class="Heading">
The categories of unions of residue classes with fixed rep's
</span></h4>
<p>The names of the categories of unions of residue classes with fixed representatives are <code class="code">IsUnionOfResidueClasses[ OfZ | OfZ_pi | OfZorZ_pi | OfGFqx ]WithFixedRepresentatives</code>.</p>
<div class="chlinkprevnextbot"> <a href="chap0.html">Top of Book</a> <a href="chap1.html">Previous Chapter</a> <a href="chap3.html">Next Chapter</a> </div>
<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><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="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<hr />
<p class="foot">generated by <a href="http://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
91213ddcfbe7f54821d42c2d9e091326
>
files
>
2580
