<Section Label="sec:DefiningUnionsOfResidueClasses">
<Heading>Entering residue classes and set-theoretic unions thereof</Heading>
<ManSection>
<Func Name="ResidueClass"
Arg="R, m, r" Label="by ring, modulus and residue"/>
<Func Name="ResidueClass"
Arg="m, r" Label="by modulus and residue"/>
<Func Name="ResidueClass"
Arg="r, m" Label="by residue and modulus"/>
<Returns>
in the three-argument form the residue class
<A>r</A> mod <A>m</A> of the ring <A>R</A>,
and in the two-argument form the residue class
<A>r</A> mod <A>m</A> of the <Q>default ring</Q>
(<M>\rightarrow</M> <C>DefaultRing</C> in the &GAP; Reference Manual)
of the arguments.
</Returns>
<Description>
In the two-argument case, <A>m</A> is taken to be the larger and
<A>r</A> is taken to be the smaller of the arguments.
For convenience, it is permitted to enclose the argument list in
list brackets. <P/>
<Index Key="IsResidueClass"><C>IsResidueClass</C></Index>
<Index Key="Modulus" Subkey="of a residue class"><C>Modulus</C></Index>
<Index Key="Residue" Subkey="of a residue class"><C>Residue</C></Index>
Residue classes have the property <C>IsResidueClass</C>.
Rings are regarded as residue class 0 (mod 1),
and therefore have this property. There are operations <C>Modulus</C>
and <C>Residue</C> to retrieve the modulus <A>m</A> resp.
residue <A>r</A> of a residue class.
<Example>
<![CDATA[
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 ( mod x+1 ) of GF(2)[x]
]]>
</Example>
</Description>
</ManSection>
<ManSection>
<Func Name="ResidueClassUnion"
Arg="R, m, r"
Label="by ring, modulus and residues"/>
<Func Name="ResidueClassUnion"
Arg="R, m, r, included, excluded"
Label="by ring, modulus, residues and included / excluded elements"/>
<Func Name="ResidueClassUnion"
Arg="R, cls"
Label="by ring and list of classes"/>
<Func Name="ResidueClassUnion"
Arg="R, cls, included, excluded"
Label="by ring, list of classes and included / excluded elements"/>
<Returns>
in the first two cases, the union of the residue classes
<A>r</A>[<M>i</M>] mod <A>m</A>
of the ring <A>R</A>, plus / minus finite sets <A>included</A>
and <A>excluded</A> of elements of <A>R</A>.
In the last two cases, the union of the residue classes
<A>cls</A>[<M>i</M>][1] mod <A>cls</A>[<M>i</M>][2]
of the ring <A>R</A>=&ZZ;, plus / minus finite sets
<A>included</A> and <A>excluded</A> of integers.
</Returns>
<Description>
For unions of residue classes of the integers, two distinct
representations are implemented: in the first representation,
a union of residue classes is represented by its modulus <A>m</A>
and the list of residues <A>r</A>; this is called the <Q>standard</Q>
representation. In the second (<Q>sparse</Q>) representation,
a union of residue classes <M>r_1(m_1) \cup \dots \cup r_k(m_k)</M>
is represented by the list <A>cls</A> of the pairs <C>[r_i,m_i]</C>.
<Index Key="StandardRep" Subkey="for a residue class union">
<C>StandardRep</C>
</Index>
<Index Key="SparseRep" Subkey="for a residue class union">
<C>SparseRep</C>
</Index>
One can switch between the two representations by using the operations
<C>StandardRep</C> and <C>SparseRep</C>, respectively.
The sparse representation allows more efficient computation in terms
of time- and memory requirements when computing with unions of
<Q>relatively few</Q> residue classes where the lcm of the moduli
is <Q>large</Q>; otherwise the standard representation is
advantageous. For rings other than &ZZ;, presently only the standard
representation is available.
<Example>
<![CDATA[
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(Integers,[[1,2],[0,40],[2,1200]]);
Union of the residue classes 1(2), 0(40) and 2(1200) of Z
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]> \ [ 1 ]
]]>
</Example>
</Description>
</ManSection>
<Index Key="residue class union" Subkey="definition">
residue class union
</Index>
When talking about a <E>residue class union</E> in this chapter,
we always mean an object as it is returned by this function. <P/>
<Index Key="Modulus" Subkey="of a residue class union">
<C>Modulus</C>
</Index>
<Index Key="Residues" Subkey="of a residue class union">
<C>Residues</C>
</Index>
<Index Key="IncludedElements" Subkey="of a residue class union">
<C>IncludedElements</C>
</Index>
<Index Key="ExcludedElements" Subkey="of a residue class union">
<C>ExcludedElements</C>
</Index>
There are operations <C>Modulus</C>, <C>Residues</C>,
<C>IncludedElements</C> and <C>ExcludedElements</C> to retrieve the
components of a residue class union as they have originally been passed
as arguments to <Ref Func="ResidueClassUnion"
Label="by ring, modulus and residues"/>. <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:
<Example>
<![CDATA[
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
]]>
</Example>
<ManSection>
<Func Name="AllResidueClassesModulo"
Arg="R, m" Label="of a given ring, modulo a given modulus"/>
<Func Name="AllResidueClassesModulo"
Arg="m" Label="by modulus, of the default ring of that modulus"/>
<Returns>
a sorted list of all residue classes (mod <A>m</A>)
of the ring <A>R</A>.
</Returns>
<Description>
If the argument <A>R</A> is omitted it defaults to the default ring of
<A>m</A> -- cf. the documentation of <C>DefaultRing</C> in the &GAP;
reference manual.
<Index Key="AllResidues" Subkey="for ring and modulus">
<C>AllResidues</C>
</Index>
<Index Key="NumberOfResidues" Subkey="for ring and modulus">
<C>NumberOfResidues</C>
</Index>
<Index Key="NrResidues" Subkey="for ring and modulus">
<C>NrResidues</C>
</Index>
A transversal for the residue classes (mod <A>m</A>) can be
obtained by the operation <C>AllResidues(<A>R</A>,<A>m</A>)</C>,
and their number can be determined by the operation
<C>NumberOfResidues(<A>R</A>,<A>m</A>)</C>.
<Example>
<![CDATA[
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 ( mod x ) of GF(2)[x],
The residue class 1 ( mod x ) of GF(2)[x] ]
gap> AllResidues(R,x^3);
[ 0, 1, x, x+1, x^2, x^2+1, x^2+x, x^2+x+1 ]
gap> NumberOfResidues(Z_pi([2,3]),360);
72
]]>
</Example>
</Description>
</ManSection>
<Section Label="sec:MethodsForResidueClassUnions">
<Heading>Methods for residue class unions</Heading>
<Index Key="Print" Subkey="for a residue class union">
<C>Print</C>
</Index>
<Index Key="String" Subkey="for a residue class union">
<C>String</C>
</Index>
<Index Key="Display" Subkey="for a residue class union">
<C>Display</C>
</Index>
There are methods for <C>Print</C>, <C>String</C> and <C>Display</C>
which are applicable to residue class unions. There is a method
for <C>in</C> which tests whether some ring element lies in a given
residue class union.
<Index Key="Union" Subkey="for residue class unions">
<C>Union</C>
</Index>
<Index Key="Intersection" Subkey="for residue class unions">
<C>Intersection</C>
</Index>
<Index Key="Difference" Subkey="for residue class unions">
<C>Difference</C>
</Index>
<Index Key="IsSubset" Subkey="for residue class unions">
<C>IsSubset</C>
</Index>
There are methods for <C>Union</C>, <C>Intersection</C>, <C>Difference</C>
and <C>IsSubset</C> available for residue class unions.
They also accept finite subsets of the base ring as arguments.
<Example>
<![CDATA[
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
]]>
</Example>
If the underlying ring has a residue class ring of a given
cardinality <M>t</M>, then a residue class can be written as
a disjoint union of <M>t</M> residue classes with equal moduli:
<ManSection>
<Oper Name="SplittedClass"
Arg="cl, t" Label="for a residue class and a number of parts"/>
<Returns>
a partition of the residue class <A>cl</A> into <A>t</A> residue
classes with equal moduli, provided that such a partition exists.
Otherwise <C>fail</C>.
</Returns>
<Description>
<Example>
<![CDATA[
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
]]>
</Example>
</Description>
</ManSection>
Often one needs a partition of a given residue class union into
<Q>few</Q> residue classes. The following operation takes care of this:
<ManSection>
<Oper Name="AsUnionOfFewClasses"
Arg="U" Label="for a residue class union"/>
<Returns>
a set of disjoint residue classes whose union is equal to <A>U</A>,
up to the finite sets <C>IncludedElements(<A>U</A>)</C> and
<C>ExcludedElements(<A>U</A>)</C>.
</Returns>
<Description>
As the name of the operation suggests, it is taken care that
the number of residue classes in the returned list is kept
<Q>reasonably small</Q>. It is not guaranteed that it is minimal.
<Example>
<![CDATA[
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)
]]>
</Example>
</Description>
</ManSection>
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:
<ManSection>
<Oper Name="PartitionsIntoResidueClasses"
Arg="R, length" Label="of a given ring, of given length"/>
<Oper Name="PartitionsIntoResidueClasses"
Arg="R, length, primes"
Label="of a given ring, of given length, with moduli with given factors"/>
<Returns>
in the 2-argument version a sorted list of all partitions of the ring
<A>R</A> into <A>length</A> residue classes. In the 3-argument version
a sorted list of all partitions of the ring <A>R</A> into <A>length</A>
residue classes whose moduli have only prime factors in the list
<A>primes</A>.
</Returns>
<Description>
<Example>
<![CDATA[
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) ] ]
]]>
</Example>
</Description>
</ManSection>
<ManSection>
<Oper Name="RandomPartitionIntoResidueClasses"
Arg="R, length, primes"
Label="of a given ring, of given length"/>
<Returns>
a <Q>random</Q> partition of the ring <A>R</A> into <A>length</A>
residue classes whose moduli have only prime factors in <A>primes</A>,
respectively <C>fail</C> if no such partition exists.
</Returns>
<Description>
<Log>
<![CDATA[
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
]]>
</Log>
</Description>
</ManSection>
<ManSection>
<Meth Name="CoverByResidueClasses"
Arg="Integers, moduli"
Label="of the integers, by residue classes with given moduli"/>
<Meth Name="CoversByResidueClasses"
Arg="Integers, moduli"
Label="of the integers, by residue classes with given moduli"/>
<Returns>
in the first form a cover of the integers by residue classes with moduli
<A>moduli</A> if such cover exists, and <C>fail</C> otherwise;
in the second form a list of all covers of the integers by residue
classes with moduli <A>moduli</A>.
</Returns>
<Description>
Since there are often very many such covers, computing all of them
can take a lot of time and memory.
<Log>
<![CDATA[
gap> CoverByResidueClasses(Integers,[2,3,4,6,8,12]);
[ 0(2), 0(3), 1(4), 1(6), 3(8), 11(12) ]
gap> Union(last);
Integers
gap> CoversByResidueClasses(Integers,[2,3,3,6]);
[ [ 0(2), 0(3), 1(3), 5(6) ], [ 0(2), 0(3), 2(3), 1(6) ],
[ 0(2), 1(3), 2(3), 3(6) ], [ 1(2), 0(3), 1(3), 2(6) ],
[ 1(2), 0(3), 2(3), 4(6) ], [ 1(2), 1(3), 2(3), 0(6) ] ]
gap> List(last,Union);
[ Integers, Integers, Integers, Integers, Integers, Integers ]
]]>
</Log>
</Description>
</ManSection>
<ManSection>
<Oper Name="Density" Arg="U" Label="of a residue class union"/>
<Returns>
the natural density of <A>U</A> as a subset of the underlying ring.
</Returns>
<Description>
The <E>natural density</E> of a residue class <M>r(m)</M>
of a ring <M>R</M> is defined by <M>1/|R/mR|</M>, and
the <E>natural density</E> of a union <M>U</M> of finitely many
residue classes is defined by the sum of the densities of the elements
of a partition of <M>U</M> into finitely many residue classes.
<Example>
<![CDATA[
gap> Density(ResidueClass(0,2));
1/2
gap> Density(Difference(Integers,ResidueClass(0,5)));
4/5
]]>
</Example>
</Description>
</ManSection>
<Index Key="Iterator" Subkey="for a residue class union">
<C>Iterator</C>
</Index>
<Index Key="NextIterator" Subkey="for an iterator of a residue class union">
<C>NextIterator</C>
</Index>
For looping over residue class unions of the integers, there are
methods for the operations <C>Iterator</C> and <C>NextIterator</C>.
<Section Label="sec:ResidueClassUnionsOfZxZ">
<Heading>On residue class unions of <M>&ZZ;^2</M></Heading>
Residue class unions of <M>&ZZ;^2</M> are treated similar as those of any
other ring. Also there is roughly the same functionality available for them.
However there are some differences and a few additional features, which are
described in this section. <P/>
The elements of <M>&ZZ;^2</M> are represented as lists of length 2
with integer entries. The modulus of a residue class union of <M>&ZZ;^2</M>
is a lattice. This lattice is stored as a <M>2 \times 2</M> integer matrix
of full rank in Hermite normal form, whose rows are the spanning vectors.
Residue classes of <M>&ZZ;^2</M> modulo principal ideals are presently
not implemented. Residue class unions of <M>&ZZ;^2</M> can be
multiplied by matrices of full rank from the right. A snippet of a residue
class union of <M>&ZZ;^2</M> is shown in <Q>ASCII art</Q> when one
<C>Display</C>'s it with option AsGrid. We give some illustrative
examples:
Note that in &GAP; multiplying lists of integers means computing their
scalar product as vectors. The consequence is that technically the free
module <M>&ZZ;^2</M> is not a ring in &GAP;.
<Section Label="sec:CategoriesOfResidueClassUnions">
<Heading>The categories and families of residue class unions</Heading>
<ManSection>
<Filt Name="IsResidueClassUnion" Arg="U"/>
<Filt Name="IsResidueClassUnionOfZ" Arg="U"/>
<Filt Name="IsResidueClassUnionOfZxZ" Arg="U"/>
<Filt Name="IsResidueClassUnionOfZ_pi" Arg="U"/>
<Filt Name="IsResidueClassUnionOfGFqx" Arg="U"/>
<Returns>
<C>true</C> if <A>U</A> is a residue class union,
a residue class union of &ZZ;,
a residue class union of <M>&ZZ;^2</M>,
a residue class union of a semilocalization of &ZZ; or
a residue class union of a polynomial ring in one variable
over a finite field, respectively, and <C>false</C> otherwise.
</Returns>
<Description>
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 <C>IsResidueClassUnionOfZorZ&uscore;pi</C> which is the
union of <C>IsResidueClassUnionOfZ</C> and
<C>IsResidueClassUnionOfZ&uscore;pi</C>.
<Index Key="IsResidueClassUnionOfZ_pi">
<C>IsResidueClassUnionOfZ&uscore;pi</C>
</Index>
The internal representation of residue class unions is called
<C>IsResidueClassUnionResidueListRep</C>.
<Index Key="IsResidueClassUnionResidueListRep">
<C>IsResidueClassUnionResidueListRep</C>
</Index>
There are methods available for <C>ExtRepOfObj</C> and
<C>ObjByExtRep</C>.
<Index Key="ExtRepOfObj"><C>ExtRepOfObj</C></Index>
<Index Key="ObjByExtRep"><C>ObjByExtRep</C></Index>
</Description>
</ManSection>
<ManSection>
<Func Name="ResidueClassUnionsFamily"
Arg="R" Label="of a ring"/>
<Func Name="ResidueClassUnionsFamily"
Arg="R, fixedreps" Label="of a ring, with fixed representatives"/>
<Returns>
the family of residue class unions or the family of unions of
residue classes with fixed representatives of the ring <A>R</A>,
depending on whether <A>fixedreps</A> is present and <C>true</C> or not.
</Returns>
<Description>
The ring <A>R</A> can be retrieved as
<C>UnderlyingRing(ResidueClassUnionsFamily(<A>R</A>))</C>.
<Index Key="residue class union" Subkey="coercion">
residue class union
</Index>
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.
</Description>
</ManSection>
¤ 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.0.15Bemerkung:
(vorverarbeitet)
¤
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.
