<!-- #################################################################### -->
<!-- ##                                                                ## -->
<!-- ##  resclass.xml      ResClasses documentation       Stefan Kohl  ## -->
<!-- ##                                                                ## -->
<!-- ##  $Id: resclass.xml,v 1.26 2006/01/12 13:12:39 stefan Exp $     ## -->
<!-- ##                                                                ## -->
<!-- #################################################################### -->

<Chapter Label="ch:UnionsOfResidueClasses">
<Heading>Unions of Residue Classes</Heading>

<!-- #################################################################### -->

<Section Label="sec:DefiningUnionsOfResidueClasses">
<Heading>Entering residue classes and unions thereof</Heading>

<ManSection>
  <Func Name="ResidueClass" Arg="R, m, r" Label="R, m, r"/>
  <Func Name="ResidueClass" Arg="m, r" Label="m, r"/>
  <Func Name="ResidueClass" Arg="r, m" Label="r, m"/>
  <Returns>
    In the three-argument form the residue class
    <A>r</A>&nbsp;mod&nbsp;<A>m</A> of the ring&nbsp;<A>R</A>, and
    in the two-argument form the residue class
    <A>r</A>&nbsp;mod&nbsp;<A>m</A> of the integers.
  </Returns>
  <Description>
    In the two-argument case, <A>r</A> and <A>m</A> must not be negative,
    and <A>r</A> is assumed to lie in the range <C>[0..<A>m</A>-1]</C>.
    The latter is used to decide which of the two arguments is the modulus
    <A>m</A>, and which is the residue&nbsp;<A>r</A>.
<Example>
<![CDATA[
gap> A := ResidueClass(2,3);
The residue class 2(3) of Z
gap> B := ResidueClass(Z_pi([2,5]),2,1);
The residue class 1(2) of Z_( 2, 5 )
gap> R := PolynomialRing(GF(7),1);; x := Indeterminate(GF(7),1);; SetName(x,"x");
gap> C := ResidueClass(R,x+One(R),3*One(R));
The residue class Z(7) ( mod x+Z(7)^0 ) of GF(7)[x]
]]>
</Example>
  </Description>
</ManSection>

<ManSection>
  <Prop Name="IsResidueClass" Arg="obj" Label="obj"/>
  <Returns>
    <C>true</C> if <A>obj</A> is a (single) residue class and <C>false</C>
    otherwise.
  </Returns>
  <Description>
    Rings are regarded as residue class 0&nbsp;(mod&nbsp;1).
<Example>
<![CDATA[
gap> IsResidueClass(A);
true
gap> IsResidueClass(Z_pi([2,5]));
true
]]>
</Example>
  </Description>
</ManSection>

<ManSection>
  <Func Name="ResidueClassUnion"
        Arg="R, m, r" Label="R, m, r"/>
  <Func Name="ResidueClassUnion"
        Arg="R, m, r, included, excluded"
        Label="R, m, r, included, excluded"/>
  <Returns>
    The union of the residue classes
    <A>r</A>[<M>i</M>]&nbsp;mod&nbsp;<A>m</A>
    of the ring&nbsp;<A>R</A>, plus / minus finite sets <A>included</A>
    and <A>excluded</A> of ring elements.
  </Returns>
  <Description>
    If the arguments <A>included</A> and <A>excluded</A> are given, they
    must be sets of elements of&nbsp;<A>R</A>.
<Example>
<![CDATA[
gap> D := ResidueClassUnion(Integers,6,[2,4]);
Union of the residue classes 2(6) and 4(6) of Z
gap> F := 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> G := ResidueClassUnion(R,x,[One(R),5*One(R),6*One(R)],[Zero(R)],[One(R)]);
<union of 3 residue classes (mod x) of GF(7)[x]> U [ 0*Z(7) ] \ [ Z(7)^0 ]
gap> H := ResidueClassUnion(Z_pi([2,3]),8,[3,5]);
<union of 2 residue classes (mod 8) of Z_( 2, 3 )>
]]>
</Example>
  </Description>
</ManSection>

<ManSection>
  <Func Name="AllResidueClassesModulo" Arg="R, m" Label="R, m"/>
  <Func Name="AllResidueClassesModulo" Arg="m" Label="m"/>
  <Returns>
    A sorted list of all residue classes (mod&nbsp;<A>m</A>)
    of the ring&nbsp;<A>R</A>.
  </Returns>
  <Description>
    If the argument <A>R</A> is omitted it defaults to the default ring of
    <A>m</A> -- cp. the documentation of <C>DefaultRing</C> in the &GAP;
    reference manual.
<Example>
<![CDATA[
gap> AllResidueClassesModulo(3);
[ The residue class 0(3) of Z, The residue class 1(3) of Z, 
  The residue class 2(3) of Z ]
gap> AllResidueClassesModulo(Z_pi(2),4);
[ The residue class 0(4) of Z_( 2 ), The residue class 1(4) of Z_( 2 ), 
  The residue class 2(4) of Z_( 2 ), The residue class 3(4) of Z_( 2 ) ]
gap> AllResidueClassesModulo(R,x);
[ The residue class 0*Z(7) ( mod x ) of GF(7)[x], 
  The residue class Z(7)^0 ( mod x ) of GF(7)[x], 
  The residue class Z(7) ( mod x ) of GF(7)[x], 
  The residue class Z(7)^2 ( mod x ) of GF(7)[x], 
  The residue class -Z(7)^0 ( mod x ) of GF(7)[x], 
  The residue class Z(7)^4 ( mod x ) of GF(7)[x], 
  The residue class Z(7)^5 ( mod x ) of GF(7)[x] ]
]]>
</Example>
  </Description>
</ManSection>

<Alt Only="LaTeX">\pagebreak[4]</Alt>

A transversal for the set of residue classes (mod&nbsp;<M>m</M>)
can be obtained by the following function:

<ManSection>
  <Func Name="AllResidues" Arg="R, m" Label="R, m"/>
  <Returns>
    A sorted list of all residues modulo&nbsp;<A>m</A>
    in the ring&nbsp;<A>R</A>.
  </Returns>
  <Description>
<Example>
<![CDATA[
gap> AllResidues(Integers,6);
[ 0 .. 5 ]
gap> AllResidues(Z_pi([3,5,7]),700);
[ 0 .. 174 ]
gap> x := Indeterminate(GF(2),1);; SetName(x,"x");;
gap> R := PolynomialRing(GF(2),1); e := One(R);; z := Zero(R);;
GF(2)[x]
gap> AllResidues(R,x^4+x^2);
[ 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, x^3, 
  x^3+Z(2)^0, x^3+x, x^3+x+Z(2)^0, x^3+x^2, x^3+x^2+Z(2)^0, x^3+x^2+x, 
  x^3+x^2+x+Z(2)^0 ]
]]>
</Example>
  </Description>
</ManSection>

For extracting the components of a residue class union as given as
arguments in <Ref Func="ResidueClassUnion" Label="R, m, r"/>, there are
operations <C>Modulus</C>, <C>Residues</C>, <C>IncludedElements</C> and
<C>ExcludedElements</C>.

</Section>

<!-- #################################################################### -->

<Section Label="sec:MethodsForResidueClassUnions">
<Heading>Methods for unions of residue classes</Heading>

There are methods for <C>Print</C>, <C>String</C> and <C>Display</C>
which are applicable to unions of residue classes. There is a method
for <C>in</C> to test whether some ring element lies in a given union
of residue classes.

<Example>
<![CDATA[
gap> 20 in A;
true
gap> 1/3 in B;
true
gap> x in G;
false
gap> Perform( [ C, F, H ], function( U ) Print(U,"\n"); end );
ResidueClassUnion( GF(7)[x], x+Z(7)^0, [ Z(7) ] )
ResidueClassUnion( Integers, 5, [ 1, 2 ], [ 3, 8 ], [ -4, 1 ] )
ResidueClassUnion( Z_( 2, 3 ), 8, [ 3, 5 ] )
]]>
</Example>

There is a method for <C>IsSubset</C> available for unions of residue
classes. As described in detail in the sequel, there are methods for
computing set-theoretic unions, intersections and differences of unions
of residue classes:

<ManSection>
  <Meth Name="Union" Arg="U1, U2" Label="U1, U2"/>
  <Meth Name="Union" Arg="U, S" Label="U, S"/>
  <Returns>
    The union of two residue class unions <A>U1</A> and&nbsp;<A>U2</A>
    resp. of the residue class union&nbsp;<A>U</A> and the finite
    set&nbsp;<A>S</A> of elements of the ring <A>U</A>&nbsp;is defined
    over.
  </Returns>
  <Description>
<Example>
<![CDATA[
gap> I := ResidueClassUnion(Integers,6,[1,5]);
Union of the residue classes 1(6) and 5(6) of Z
gap> J := ResidueClassUnion(Integers,5,[1,2,3,4]);
Union of the residue classes 1(5), 2(5), 3(5) and 4(5) of Z
gap> K := Union(I,J);
<union of 26 residue classes (mod 30) of Z>
gap> Residues(K);
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 21, 22, 23, 24, 
  25, 26, 27, 28, 29 ]
gap> Union(K,[0]);
<union of 26 residue classes (mod 30) of Z> U [ 0 ]
gap> Union(D,I);
Union of the residue classes 1(3) and 2(3) of Z
]]>
</Example>
  </Description>
</ManSection>

<ManSection>
  <Meth Name="Intersection" Arg="U1, U2" Label="U1, U2"/>
  <Meth Name="Intersection" Arg="U, S" Label="U, S"/>
  <Returns>
    The intersection of two residue class unions <A>U1</A>
    and&nbsp;<A>U2</A> resp. of the residue class union&nbsp;<A>U</A>
    and the finite set&nbsp;<A>S</A> of elements of the ring
    <A>U</A>&nbsp;is defined over.
  </Returns>
  <Description>
<Example>
<![CDATA[
gap> L := Intersection(I,J);
<union of 8 residue classes (mod 30) of Z>
gap> Display(L);

The union of the residue classes r ( mod 30 ) of Z for r =

  1  7 11 13 17 19 23 29

gap> cl := List([1..25],i->ResidueClass(Integers,Primes[i],i));;
gap> cl_int := Intersection(cl);
The residue class 941584379775558526136539054851975983(
2305567963945518424753102147331756070) of Z
gap> List(Primes{[1..25]},p->Representative(cl_int) mod p);
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 
  22, 23, 24, 25 ]
]]>
</Example>
  </Description>
</ManSection>

<ManSection>
  <Meth Name="Difference" Arg="U1, U2" Label="U1, U2"/>
  <Meth Name="Difference" Arg="U, S" Label="U, S"/>
  <Returns>
    The difference of two residue class unions <A>U1</A> and&nbsp;<A>U2</A>
    resp. of the residue class union <A>U</A> and the finite
    set&nbsp;<A>S</A> of elements of the ring <A>U</A>&nbsp;is defined
    over.
  </Returns>
  <Description>
<Example>
<![CDATA[
gap> M := Difference(I,J);
Union of the residue classes 5(30) and 25(30) of Z
gap> N := Difference(J,I);
<union of 16 residue classes (mod 30) of Z>
gap> Display(N);

The union of the residue classes r ( mod 30 ) of Z for r =

  2  3  4  6  8  9 12 14 16 18 21 22 24 26 27 28

gap> Difference(Integers,[1,2,3]);
Z \ [ 1, 2, 3 ]
gap> Difference(Z_pi([2,3,7]),[1/5,1/55]);
Z_( 2, 3, 7 ) \ [ 1/55, 1/5 ]
]]>
</Example>
  </Description>
</ManSection>

If the underlying ring has a residue class ring of some 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="cl, t"/>
  <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(2,3),5);
[ The residue class 2(15) of Z, The residue class 5(15) of Z, 
  The residue class 8(15) of Z, The residue class 11(15) of Z, 
  The residue class 14(15) of Z ]
gap> SplittedClass(ResidueClass(Z_pi([2,3]),3,2),2);
[ The residue class 2(6) of Z_( 2, 3 ), The residue class 5(6) of Z_( 2, 3 ) ]
gap> SplittedClass(ResidueClass(Z_pi([2,3]),3,2),5);
fail
]]>
</Example>
  </Description>
</ManSection>

Sometimes one wants to know a partition of a given union of residue
classes into <Q>few</Q> residue classes. Ensuring to get always a
partition of minimal possible length seems to be algorithmically
difficult. The following yields usually <Q>reasonably short</Q>
partitions:

<ManSection>
  <Oper Name="AsUnionOfFewClasses" Arg="U" Label="U"/>
  <Returns>
    A set of disjoint residue classes whose union is <A>U</A>.
  </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 necessarily minimal.
    No care is taken of <C>IncludedElements</C> and
    <C>ExcludedElements</C>.
<Example>
<![CDATA[
gap> AsUnionOfFewClasses(K);
[ The residue class 1(5) of Z, The residue class 2(5) of Z, 
  The residue class 3(5) of Z, The residue class 4(5) of Z, 
  The residue class 5(30) of Z, The residue class 25(30) of Z ]
]]>
</Example>
  </Description>
</ManSection>

One can add / subtract a constant to / from all elements of a union of
residue classes, and one can multiply or divide the elements by a constant:

<ManSection>
  <Meth Name="\+" Arg="U, x" Label="U, x"/>
  <Meth Name="\+" Arg="x, U" Label="x, U"/>
  <Returns>
    The set of sums <M>u + x</M>, <M>u \in U</M>.
  </Returns>
  <Description>
<Example>
<![CDATA[
gap> Display(L+1);

The union of the residue classes r ( mod 30 ) of Z for r =

  0  2  8 12 14 18 20 24

gap> L+30 = L;
true
]]>
</Example>
  </Description>
</ManSection>

<ManSection>
  <Meth Name="\-" Arg="U, x" Label="U, x"/>
  <Meth Name="\-" Arg="x, U" Label="x, U"/>
  <Meth Name="\-" Arg="U" Label="U"/>
  <Returns>
    The set of differences <M>u - x</M>, <M>u \in U</M> resp. the set of
    differences <M>x - u</M>, <M>u \in U</M> resp. the set of the additive
    inverses of the elements of&nbsp;<M>U</M>.
  </Returns>
  <Description>
<Example>
<![CDATA[
gap> F-7;
(Union of the residue classes 0(5) and 4(5) of Z) U [ -4, 1 ] \ [ -11, -6 ]
gap> -L = L;
true
gap> -C;
The residue class Z(7)^4 ( mod x+Z(7)^0 ) of GF(7)[x]
]]>
</Example>
  </Description>
</ManSection>

<ManSection>
  <Meth Name="\*" Arg="U, x" Label="U, x"/>
  <Meth Name="\*" Arg="x, U" Label="x, U"/>
  <Returns>
    The set of products <M>x \cdot u</M>, <M>u \in U</M>.
  </Returns>
  <Description>
<Example>
<![CDATA[
gap> D*17;
Union of the residue classes 34(102) and 68(102) of Z
gap> 2*Difference(Integers,[1,2,3]);
(The residue class 0(2) of Z) \ [ 2, 4, 6 ]
]]>
</Example>
  </Description>
</ManSection>

<ManSection>
  <Meth Name="\/" Arg="U, x" Label="U, x"/>
  <Returns>
    The set of quotients <M>u/x</M>, <M>u \in U</M>.
  </Returns>
  <Description>
    If the result would be not a subset of the underlying ring,
    the method gives up.
<Example>
<![CDATA[
gap> D/2;
Union of the residue classes 1(3) and 2(3) of Z
gap> M/5;
Union of the residue classes 1(6) and 5(6) of Z
]]>
</Example>
  </Description>
</ManSection>

The natural density of a residue class <M>r(m)</M> of a ring
<M>R</M> is defined by <M>1/|R/mR|</M>, and the natural density of
a union <M>U</M> of finitely many residue classes is defined as the
sum of the densities of the elements of a partition of <M>U</M>
into finitely many residue classes:

<ManSection>
  <Oper Name="Density" Arg="U" Label="U"/>
  <Returns>
    The natural density of&nbsp;<A>U</A> as a subset of the underlying ring.
  </Returns>
  <Description>
<Example>
<![CDATA[
gap> Density(G); G;
3/7
<union of 3 residue classes (mod x) of GF(7)[x]> U [ 0*Z(7) ] \ [ Z(7)^0 ]
gap> ResidueClassUnion(Integers,12,[3,5,9]);
Union of the residue classes 3(6) and 5(12) of Z
gap> List([last,2*last],Density);
[ 1/4, 1/8 ]
]]>
</Example>
  </Description>
</ManSection>

For looping over unions of residue classes of the integers, there are
methods for the operations <C>Iterator</C> and <C>NextIterator</C>.

</Section>

<!-- #################################################################### -->

<Section Label="sec:CategoriesOfUnionsOfResidueClasses">
<Heading>The categories and families of unions of residue classes</Heading>

<ManSection>
  <Filt Name="IsUnionOfResidueClasses" Arg="U" Label="U"/>
  <Filt Name="IsUnionOfResidueClassesOfZ" Arg="U" Label="U"/>
  <Filt Name="IsUnionOfResidueClassesOfZ_pi" Arg="U" Label="U"/>
  <Filt Name="IsUnionOfResidueClassesOfGFqx" Arg="U" Label="U"/>
  <Returns>
    <C>true</C> if <A>U</A> is a union of residue classes, resp.
    a union of residue classes of the ring of integers, resp.
    a union of residue classes of a semilocalization of the ring of integers,
    resp. a union of residue classes of a polynomial ring in one variable
    over a finite field, and <C>false</C> otherwise.
  </Returns>
</ManSection>

<ManSection>
  <Func Name="ResidueClassUnionsFamily"
        Arg="R" Label="R"/>
  <Func Name="ResidueClassUnionsFamily"
        Arg="R, fixedreps" Label="R, fixedreps"/>
  <Returns>
    The family of unions of residue classes resp. 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>.
  </Returns>
  <Description>
    The ring <A>R</A> can be accessed as
    <C>UnderlyingRing(ResidueClassUnionsFamily(<A>R</A>))</C>.
    Unions of residue classes with fixed representatives are described
    in the next chapter.
  </Description>
</ManSection>

</Section>

<!-- #################################################################### -->

</Chapter>

<!-- #################################################################### -->
