<?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 1: Set-Theoretic Unions of Residue Classes</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="chap0.html">Previous Chapter</a> <a href="chap2.html">Next Chapter</a> </div>
<p><a id="X815A3DDE7C0BC44A" name="X815A3DDE7C0BC44A"></a></p>
<div class="ChapSects"><a href="chap1.html#X815A3DDE7C0BC44A">1. <span class="Heading">Set-Theoretic Unions of Residue Classes</span></a>
<div class="ContSect"><span class="nocss"> </span><a href="chap1.html#X7E16A64485A7AB79">1.1 <span class="Heading">Entering residue classes and set-theoretic unions thereof</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap1.html#X8753CC098447BE0D">1.1-1 ResidueClass</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap1.html#X85327C777F32DA8F">1.1-2 ResidueClassUnion</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap1.html#X8326D6F285081E0F">1.1-3 AllResidueClassesModulo</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap1.html#X7A3FA13187CEADED">1.2 <span class="Heading">Methods for residue class unions</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap1.html#X854315A2877B69A7">1.2-1 SplittedClass</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap1.html#X87C166FE7FA17325">1.2-2 AsUnionOfFewClasses</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap1.html#X8079E174813646DA">1.2-3 PartitionsIntoResidueClasses</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap1.html#X8653860F7ADA4D38">1.2-4 RandomPartitionIntoResidueClasses</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap1.html#X791C16E77BE97FE3">1.2-5 Density</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap1.html#X7B26BB1C7C8495A5">1.3 <span class="Heading">The categories and families of residue class unions</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap1.html#X7EA29BBD82552352">1.3-1 IsResidueClassUnion</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap1.html#X7F9BCB1A797F8F48">1.3-2 ResidueClassUnionsFamily</a></span>
</div>
</div>
<h3>1. <span class="Heading">Set-Theoretic Unions of Residue Classes</span></h3>
<p><a id="X7E16A64485A7AB79" name="X7E16A64485A7AB79"></a></p>
<h4>1.1 <span class="Heading">Entering residue classes and set-theoretic unions thereof</span></h4>
<p><a id="X8753CC098447BE0D" name="X8753CC098447BE0D"></a></p>
<h5>1.1-1 ResidueClass</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> ResidueClass</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">> ResidueClass</code>( <var class="Arg">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">> ResidueClass</code>( <var class="Arg">r, m</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><b>Returns: </b>In the three-argument form the residue class <var class="Arg">r</var> mod <var class="Arg">m</var> of the ring <var class="Arg">R</var>, and in the two-argument form the residue class <var class="Arg">r</var> mod <var class="Arg">m</var> of the "default ring" (-> <code class="code">DefaultRing</code> in the <strong class="pkg">GAP</strong> Reference Manual) of the arguments.</p>
<p>In the two-argument case, <var class="Arg">m</var> is taken to be the larger and <var class="Arg">r</var> is taken to be the smaller of the arguments. For convenience, it is permitted to enclose the argument list in list brackets.</p>
<p>Residue classes have the property <code class="code">IsResidueClass</code>. Rings are regarded as residue class 0 (mod 1), and therefore have this property. There are operations <code class="code">Modulus</code> and <code class="code">Residue</code> to retrieve the modulus <var class="Arg">m</var> resp. residue <var class="Arg">r</var> of a residue class.</p>
<table class="example">
<tr><td><pre>
gap> ResidueClass(2,3);
The residue class 2(3) of Z
gap> ResidueClass(Z_pi([2,5]),2,1);
The residue class 1(2) of Z_( 2, 5 )
gap> R := PolynomialRing(GF(2),1);;
gap> x := Indeterminate(GF(2),1);; SetName(x,"x");
gap> ResidueClass(R,x+One(R),Zero(R));
The residue class 0*Z(2) ( mod x+Z(2)^0 ) of GF(2)[x]
</pre></td></tr></table>
<p><a id="X85327C777F32DA8F" name="X85327C777F32DA8F"></a></p>
<h5>1.1-2 ResidueClassUnion</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> ResidueClassUnion</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">> ResidueClassUnion</code>( <var class="Arg">R, m, r, included, excluded</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><b>Returns: </b>The union of the residue classes <var class="Arg">r</var>[i] mod <var class="Arg">m</var> of the ring <var class="Arg">R</var>, plus / minus finite sets <var class="Arg">included</var> and <var class="Arg">excluded</var> of elements of <var class="Arg">R</var>.</p>
<table class="example">
<tr><td><pre>
gap> ResidueClassUnion(Integers,5,[1,2],[3,8],[-4,1]);
(Union of the residue classes 1(5) and 2(5) of Z) U [ 3, 8 ] \ [ -4, 1 ]
gap> ResidueClassUnion(Z_pi([2,3]),8,[3,5]);
Union of the residue classes 3(8) and 5(8) of Z_( 2, 3 )
gap> ResidueClassUnion(R,x^2,[One(R),x],[],[One(R)]);
<union of 2 residue classes (mod x^2) of GF(2)[x]> \ [ Z(2)^0 ]
</pre></td></tr></table>
<p>When talking about a <em>residue class union</em> in this chapter, we always mean an object as it is returned by this function.</p>
<p>There are operations <code class="code">Modulus</code>, <code class="code">Residues</code>, <code class="code">IncludedElements</code> and <code class="code">ExcludedElements</code> to retrieve the components of a residue class union as they have originally been passed as arguments to <code class="func">ResidueClassUnion</code>.</p>
<p>The user has the choice between a longer and more descriptive and a shorter and less bulky output format for residue classes and unions thereof:</p>
<table class="example">
<tr><td><pre>
gap> ResidueClassUnionViewingFormat("short");
gap> ResidueClassUnion(Integers,12,[0,1,4,7,8]);
0(4) U 1(6)
gap> ResidueClassUnionViewingFormat("long");
gap> ResidueClassUnion(Integers,12,[0,1,4,7,8]);
Union of the residue classes 0(4) and 1(6) of Z
</pre></td></tr></table>
<p><a id="X8326D6F285081E0F" name="X8326D6F285081E0F"></a></p>
<h5>1.1-3 AllResidueClassesModulo</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AllResidueClassesModulo</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">> AllResidueClassesModulo</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>.</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. A transversal for the residue classes (mod <var class="Arg">m</var>) can be obtained by the operation <code class="code">AllResidues(<var class="Arg">R</var>,<var class="Arg">m</var>)</code>, and their number can be determined by the operation <code class="code">NumberOfResidues(<var class="Arg">R</var>,<var class="Arg">m</var>)</code>.</p>
<table class="example">
<tr><td><pre>
gap> AllResidueClassesModulo(Integers,2);
[ The residue class 0(2) of Z, The residue class 1(2) of Z ]
gap> AllResidueClassesModulo(Z_pi(2),2);
[ The residue class 0(2) of Z_( 2 ), The residue class 1(2) of Z_( 2 ) ]
gap> AllResidueClassesModulo(R,x);
[ The residue class 0*Z(2) ( mod x ) of GF(2)[x],
The residue class Z(2)^0 ( mod x ) of GF(2)[x] ]
gap> AllResidues(R,x^3);
[ 0*Z(2), Z(2)^0, x, x+Z(2)^0, x^2, x^2+Z(2)^0, x^2+x, x^2+x+Z(2)^0 ]
gap> NumberOfResidues(Z_pi([2,3]),360);
72
</pre></td></tr></table>
<p><a id="X7A3FA13187CEADED" name="X7A3FA13187CEADED"></a></p>
<h4>1.2 <span class="Heading">Methods for residue class unions</span></h4>
<p>There are methods for <code class="code">Print</code>, <code class="code">String</code> and <code class="code">Display</code> which are applicable to residue class unions. There is a method for <code class="code">in</code> which tests whether some ring element lies in a given residue class union.</p>
<table class="example">
<tr><td><pre>
gap> Print(ResidueClass(1,2),"\n");
ResidueClassUnion( Integers, 2, [ 1 ] )
gap> 1 in ResidueClass(1,2);
true
</pre></td></tr></table>
<p>There are methods for <code class="code">Union</code>, <code class="code">Intersection</code>, <code class="code">Difference</code> and <code class="code">IsSubset</code> available for residue class unions. They also accept finite subsets of the base ring as arguments.</p>
<table class="example">
<tr><td><pre>
gap> S := Union(ResidueClass(0,2),ResidueClass(0,3));
Z \ Union of the residue classes 1(6) and 5(6) of Z
gap> Intersection(S,ResidueClass(0,7));
Union of the residue classes 0(14) and 21(42) of Z
gap> Difference(S,ResidueClass(2,4));
Union of the residue classes 0(4) and 3(6) of Z
gap> IsSubset(ResidueClass(0,2),ResidueClass(4,8));
true
gap> Union(S,[1..10]);
(Union of the residue classes 0(2) and 3(6) of Z) U [ 1, 5, 7 ]
gap> Intersection(S,[1..6]);
[ 2, 3, 4, 6 ]
gap> Difference(S,[1..6]);
(Union of the residue classes 0(2) and 3(6) of Z) \ [ 2, 3, 4, 6 ]
gap> Difference(Integers,[1..10]);
Z \ <set of cardinality 10>
gap> IsSubset(S,[1..10]);
false
</pre></td></tr></table>
<p>If the underlying ring has a residue class ring of a given cardinality t, then a residue class can be written as a disjoint union of t residue classes with equal moduli:</p>
<p><a id="X854315A2877B69A7" name="X854315A2877B69A7"></a></p>
<h5>1.2-1 SplittedClass</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> SplittedClass</code>( <var class="Arg">cl, t</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>A partition of the residue class <var class="Arg">cl</var> into <var class="Arg">t</var> residue classes with equal moduli, provided that such a partition exists. Otherwise <code class="code">fail</code>.</p>
<table class="example">
<tr><td><pre>
gap> SplittedClass(ResidueClass(1,2),2);
[ The residue class 1(4) of Z, The residue class 3(4) of Z ]
gap> SplittedClass(ResidueClass(Z_pi(3),3,0),2);
fail
</pre></td></tr></table>
<p>Often one needs a partition of a given residue class union into "few" residue classes. The following operation takes care of this:</p>
<p><a id="X87C166FE7FA17325" name="X87C166FE7FA17325"></a></p>
<h5>1.2-2 AsUnionOfFewClasses</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AsUnionOfFewClasses</code>( <var class="Arg">U</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>A set of disjoint residue classes whose union is equal to <var class="Arg">U</var>, up to the finite sets <code class="code">IncludedElements(<var class="Arg">U</var>)</code> and <code class="code">ExcludedElements(<var class="Arg">U</var>)</code>.</p>
<p>As the name of the operation suggests, it is taken care that the number of residue classes in the returned list is kept "reasonably small". It is not guaranteed that it is minimal.</p>
<table class="example">
<tr><td><pre>
gap> ResidueClassUnionViewingFormat("short");
gap> AsUnionOfFewClasses(Difference(Integers,ResidueClass(0,30)));
[ 1(2), 2(6), 4(6), 6(30), 12(30), 18(30), 24(30) ]
gap> Union(last);
Z \ 0(30)
</pre></td></tr></table>
<p>One can compute the sets of sums, differences, products and quotients of the elements of a residue class union and an element of the base ring:</p>
<table class="example">
<tr><td><pre>
gap> ResidueClass(0,2) + 1;
1(2)
gap> ResidueClass(0,2) - 2 = ResidueClass(0,2);
true
gap> 3 * ResidueClass(0,2);
0(6)
gap> ResidueClass(0,2)/2;
Integers
</pre></td></tr></table>
<p><a id="X8079E174813646DA" name="X8079E174813646DA"></a></p>
<h5>1.2-3 PartitionsIntoResidueClasses</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> PartitionsIntoResidueClasses</code>( <var class="Arg">R, length</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>A sorted list of all partitions of the ring <var class="Arg">R</var> into <var class="Arg">length</var> residue classes.</p>
<table class="example">
<tr><td><pre>
gap> PartitionsIntoResidueClasses(Integers,4);
[ [ 0(2), 1(4), 3(8), 7(8) ], [ 0(2), 3(4), 1(8), 5(8) ],
[ 0(2), 1(6), 3(6), 5(6) ], [ 1(2), 0(4), 2(8), 6(8) ],
[ 1(2), 2(4), 0(8), 4(8) ], [ 1(2), 0(6), 2(6), 4(6) ],
[ 0(3), 1(3), 2(6), 5(6) ], [ 0(3), 2(3), 1(6), 4(6) ],
[ 1(3), 2(3), 0(6), 3(6) ], [ 0(4), 1(4), 2(4), 3(4) ] ]
</pre></td></tr></table>
<p><a id="X8653860F7ADA4D38" name="X8653860F7ADA4D38"></a></p>
<h5>1.2-4 RandomPartitionIntoResidueClasses</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> RandomPartitionIntoResidueClasses</code>( <var class="Arg">R, length, primes</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>A "random" partition of the ring <var class="Arg">R</var> into <var class="Arg">length</var> residue classes whose moduli have only prime factors in <var class="Arg">primes</var>, respectively <code class="code">fail</code> if no such partition exists.</p>
<table class="example">
<tr><td><pre>
gap> RandomPartitionIntoResidueClasses(Integers,30,[2,3,5,7]);
[ 0(7), 2(7), 5(7), 3(14), 10(14), 1(21), 8(21), 15(21), 18(21), 20(21),
6(63), 13(63), 25(63), 27(63), 32(63), 34(63), 46(63), 48(63), 53(63),
55(63), 4(126), 67(126), 137(189), 74(567), 200(567), 263(567),
389(567), 452(567), 11(1134), 578(1134) ]
gap> Union(last);
Integers
gap> Sum(List(last2,Density));
1
</pre></td></tr></table>
<p><a id="X791C16E77BE97FE3" name="X791C16E77BE97FE3"></a></p>
<h5>1.2-5 Density</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Density</code>( <var class="Arg">U</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>The natural density of <var class="Arg">U</var> as a subset of the underlying ring.</p>
<p>The <em>natural density</em> of a residue class r(m) of a ring R is defined by 1/|R/mR|, and the <em>natural density</em> of a union U of finitely many residue classes is defined by the sum of the densities of the elements of a partition of U into finitely many residue classes.</p>
<table class="example">
<tr><td><pre>
gap> Density(ResidueClass(0,2));
1/2
gap> Density(Difference(Integers,ResidueClass(0,5)));
4/5
</pre></td></tr></table>
<p>For looping over residue class unions of the integers, there are methods for the operations <code class="code">Iterator</code> and <code class="code">NextIterator</code>.</p>
<p><a id="X7B26BB1C7C8495A5" name="X7B26BB1C7C8495A5"></a></p>
<h4>1.3 <span class="Heading">The categories and families of residue class unions</span></h4>
<p><a id="X7EA29BBD82552352" name="X7EA29BBD82552352"></a></p>
<h5>1.3-1 IsResidueClassUnion</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsResidueClassUnion</code>( <var class="Arg">U</var> )</td><td class="tdright">( filter )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsResidueClassUnionOfZ</code>( <var class="Arg">U</var> )</td><td class="tdright">( filter )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsResidueClassUnionOfZ_pi</code>( <var class="Arg">U</var> )</td><td class="tdright">( filter )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsResidueClassUnionOfGFqx</code>( <var class="Arg">U</var> )</td><td class="tdright">( filter )</td></tr></table></div>
<p><b>Returns: </b><code class="code">true</code> if <var class="Arg">U</var> is a residue class union, a residue class union of the ring of integers, a residue class union of a semilocalization of the ring of integers or a residue class union of a polynomial ring in one variable over a finite field, respectively, and <code class="code">false</code> otherwise.</p>
<p>Often the same methods can be used for residue class unions of the ring of integers and of its semilocalizations. For this reason, there is a category <code class="code">IsResidueClassUnionOfZorZ_pi</code> which is the union of <code class="code">IsResidueClassUnionOfZ</code> and <code class="code">IsResidueClassUnionOfZ_pi</code>. The internal representation of residue class unions is called <code class="code">IsResidueClassUnionResidueListRep</code>. There are methods available for <code class="code">ExtRepOfObj</code> and <code class="code">ObjByExtRep</code>.</p>
<p><a id="X7F9BCB1A797F8F48" name="X7F9BCB1A797F8F48"></a></p>
<h5>1.3-2 ResidueClassUnionsFamily</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> ResidueClassUnionsFamily</code>( <var class="Arg">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">> ResidueClassUnionsFamily</code>( <var class="Arg">R, fixedreps</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><b>Returns: </b>The family of residue class unions or the family of unions of residue classes with fixed representatives of the ring <var class="Arg">R</var>, depending on whether <var class="Arg">fixedreps</var> is present and <code class="code">true</code> or not.</p>
<p>The ring <var class="Arg">R</var> can be retrieved as <code class="code">UnderlyingRing(ResidueClassUnionsFamily(<var class="Arg">R</var>))</code>. There is no coercion between residue class unions or unions of residue classes with fixed representatives which belong to different families. Unions of residue classes with fixed representatives are described in the next chapter.</p>
<div class="chlinkprevnextbot"> <a href="chap0.html">Top of Book</a> <a href="chap0.html">Previous Chapter</a> <a href="chap2.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
>
5e1854624d3bc613bdd0dd13d1ef9ac7
>
files
>
2983
