1. Set-Theoretic Unions of Residue Classes
  
  
  1.1 Entering residue classes and set-theoretic unions thereof
  
  1.1-1 ResidueClass
  
  > ResidueClass( R, m, r ) __________________________________________function
  > ResidueClass( m, r ) _____________________________________________function
  > ResidueClass( r, m ) _____________________________________________function
  Returns:  In  the  three-argument  form  the  residue  class  r mod m of the
            ring R,  and in the two-argument form the residue class r mod m of
            the "default ring" (-> DefaultRing in the GAP Reference Manual) of
            the arguments.
  
  In  the  two-argument case, m is taken to be the larger and r is taken to be
  the  smaller  of  the arguments. For convenience, it is permitted to enclose
  the argument list in list brackets.
  
  Residue  classes  have  the  property  IsResidueClass. Rings are regarded as
  residue  class  0 (mod 1),  and  therefore  have  this  property.  There are
  operations  Modulus and Residue to retrieve the modulus m resp. residue r of
  a residue class.
  
  ---------------------------  Example  ----------------------------
    
    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]
    
  ------------------------------------------------------------------
  
  1.1-2 ResidueClassUnion
  
  > ResidueClassUnion( R, m, r ) _____________________________________function
  > ResidueClassUnion( R, m, r, included, excluded ) _________________function
  Returns:  The  union of the residue classes r[i] mod m of the ring R, plus /
            minus finite sets included and excluded of elements of R.
  
  ---------------------------  Example  ----------------------------
    
    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 ]
    
  ------------------------------------------------------------------
  
  When  talking about a residue class union in this chapter, we always mean an
  object as it is returned by this function.
  
  There    are    operations    Modulus,    Residues,   IncludedElements   and
  ExcludedElements to retrieve the components of a residue class union as they
  have originally been passed as arguments to ResidueClassUnion.
  
  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  ----------------------------
    
    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
    
  ------------------------------------------------------------------
  
  1.1-3 AllResidueClassesModulo
  
  > AllResidueClassesModulo( R, m ) __________________________________function
  > AllResidueClassesModulo( m ) _____________________________________function
  Returns:  A sorted list of all residue classes (mod m) of the ring R.
  
  If the argument R is omitted it defaults to the default ring of m -- cf. the
  documentation  of DefaultRing in the GAP reference manual. A transversal for
  the   residue   classes   (mod m)   can   be   obtained   by  the  operation
  AllResidues(R,m),  and  their  number  can  be  determined  by the operation
  NumberOfResidues(R,m).
  
  ---------------------------  Example  ----------------------------
    
    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
    
  ------------------------------------------------------------------
  
  
  1.2 Methods for residue class unions
  
  There  are  methods  for  Print,  String and Display which are applicable to
  residue class unions. There is a method for in which tests whether some ring
  element lies in a given residue class union.
  
  ---------------------------  Example  ----------------------------
    
    gap> Print(ResidueClass(1,2),"\n");
    ResidueClassUnion( Integers, 2, [ 1 ] )
    gap> 1 in ResidueClass(1,2);
    true
    
  ------------------------------------------------------------------
  
  There are methods for Union, Intersection, Difference and IsSubset available
  for  residue  class unions. They also accept finite subsets of the base ring
  as arguments.
  
  ---------------------------  Example  ----------------------------
    
    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
    
  ------------------------------------------------------------------
  
  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:
  
  1.2-1 SplittedClass
  
  > SplittedClass( cl, t ) __________________________________________operation
  Returns:  A  partition  of  the residue class cl into t residue classes with
            equal  moduli,  provided  that  such a partition exists. Otherwise
            fail.
  
  ---------------------------  Example  ----------------------------
    
    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
    
  ------------------------------------------------------------------
  
  Often  one  needs  a  partition  of  a  given residue class union into "few"
  residue classes. The following operation takes care of this:
  
  1.2-2 AsUnionOfFewClasses
  
  > AsUnionOfFewClasses( U ) ________________________________________operation
  Returns:  A set of disjoint residue classes whose union is equal to U, up to
            the finite sets IncludedElements(U) and ExcludedElements(U).
  
  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.
  
  ---------------------------  Example  ----------------------------
    
    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)
    
  ------------------------------------------------------------------
  
  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:
  
  ---------------------------  Example  ----------------------------
    
    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
    
  ------------------------------------------------------------------
  
  1.2-3 PartitionsIntoResidueClasses
  
  > PartitionsIntoResidueClasses( R, length ) _______________________operation
  Returns:  A  sorted list of all partitions of the ring R into length residue
            classes.
  
  ---------------------------  Example  ----------------------------
    
    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) ] ]
    
  ------------------------------------------------------------------
  
  1.2-4 RandomPartitionIntoResidueClasses
  
  > RandomPartitionIntoResidueClasses( R, length, primes ) __________operation
  Returns:  A  "random"  partition  of  the ring R into length residue classes
            whose  moduli have only prime factors in primes, respectively fail
            if no such partition exists.
  
  -----------------------------  Log  ------------------------------
    
    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
    
  ------------------------------------------------------------------
  
  1.2-5 Density
  
  > Density( U ) ____________________________________________________operation
  Returns:  The natural density of U as a subset of the underlying ring.
  
  The  natural  density  of  a  residue  class  r(m) of a ring R is defined by
  1/|R/mR|,  and  the  natural  density  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.
  
  ---------------------------  Example  ----------------------------
    
    gap> Density(ResidueClass(0,2));
    1/2
    gap> Density(Difference(Integers,ResidueClass(0,5)));
    4/5
    
  ------------------------------------------------------------------
  
  For looping over residue class unions of the integers, there are methods for
  the operations Iterator and NextIterator.
  
  
  1.3 The categories and families of residue class unions
  
  1.3-1 IsResidueClassUnion
  
  > IsResidueClassUnion( U ) ___________________________________________filter
  > IsResidueClassUnionOfZ( U ) ________________________________________filter
  > IsResidueClassUnionOfZ_pi( U ) _____________________________________filter
  > IsResidueClassUnionOfGFqx( U ) _____________________________________filter
  Returns:  true  if  U 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 false
            otherwise.
  
  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
  IsResidueClassUnionOfZorZ_pi  which  is  the union of IsResidueClassUnionOfZ
  and  IsResidueClassUnionOfZ_pi. The internal representation of residue class
  unions   is  called  IsResidueClassUnionResidueListRep.  There  are  methods
  available for ExtRepOfObj and ObjByExtRep.
  
  1.3-2 ResidueClassUnionsFamily
  
  > ResidueClassUnionsFamily( R ) ____________________________________function
  > ResidueClassUnionsFamily( R, fixedreps ) _________________________function
  Returns:  The  family  of  residue  class  unions or the family of unions of
            residue   classes   with  fixed  representatives  of  the  ring R,
            depending on whether fixedreps is present and true or not.
  
  The  ring R can be retrieved as UnderlyingRing(ResidueClassUnionsFamily(R)).
  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.