  
  [1X2. Unions of Residue Classes with Fixed Representatives[0X
  
  [5XResClasses[0X  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.
  
  
  [1X2.1 Entering unions of residue classes with fixed representatives[0X
  
  [1X2.1-1 ResidueClassWithFixedRepresentative[0X
  
  [2X> ResidueClassWithFixedRepresentative( [0X[3XR, m, r[0X[2X ) ___________________[0Xfunction
  [2X> ResidueClassWithFixedRepresentative( [0X[3Xm, r[0X[2X ) ______________________[0Xfunction
  [6XReturns:[0X  The   residue   class  [3Xr[0X mod [3Xm[0X  of  the  ring [3XR[0X,  with  the  fixed
            representative [3Xr[0X.
  
  If  the argument [3XR[0X is omitted, it defaults to [10XIntegers[0X. Residue classes with
  fixed           representatives          have          the          property
  [10XIsResidueClassWithFixedRepresentative[0X.  The  fixed  representative [3Xr[0X  can be
  retrieved  by  the  operation [10XResidue[0X, and the modulus [3Xm[0X can be retrieved by
  the operation [10XModulus[0X.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4X[0X
    [4Xgap> ResidueClassWithFixedRepresentative(Integers,2,1);[0X
    [4X[1/2][0X
    [4X[0X
  [4X------------------------------------------------------------------[0X
  
  [1X2.1-2 UnionOfResidueClassesWithFixedReps[0X
  
  [2X> UnionOfResidueClassesWithFixedReps( [0X[3XR, classes[0X[2X ) _________________[0Xfunction
  [2X> UnionOfResidueClassesWithFixedReps( [0X[3Xclasses[0X[2X ) ____________________[0Xfunction
  [6XReturns:[0X  The  union  of the residue classes [3Xclasses[0X[i][2] mod [3Xclasses[0X[i][1]
            of the ring [3XR[0X, with fixed representatives [3Xclasses[0X[i][2].
  
  The  argument  [3Xclasses[0X  must  be  a list of pairs of elements of the ring [3XR[0X.
  Their  first  entries -- the moduli -- must be nonzero. If the argument [3XR[0X is
  omitted, it defaults to [10XIntegers[0X.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4X[0X
    [4Xgap> UnionOfResidueClassesWithFixedReps(Integers,[[2,4],[3,9]]);[0X
    [4X[4/2] U [9/3][0X
    [4X[0X
  [4X------------------------------------------------------------------[0X
  
  There  is  a  method  for the operation [10XModulus[0X which returns the lcm of the
  moduli  of  the  residue  classes  forming such a union. Further there is an
  operation  [10XClasses[0X  for retrieving the list of classes which has been passed
  as   an   argument   to  [10XUnionOfResidueClassesWithFixedReps[0X.  The  operation
  [10XAsListOfClasses[0X  does  the  same,  except  that  the  returned list contains
  residue  classes  instead  of pairs [10X[[3Xmodulus[0X,[3Xresidue[0X][0X. There are methods for
  [10XPrint[0X, [10XString[0X and [10XDisplay[0X available for unions of residue classes with fixed
  representatives.
  
  [1X2.1-3 AllResidueClassesWithFixedRepsModulo[0X
  
  [2X> AllResidueClassesWithFixedRepsModulo( [0X[3XR, m[0X[2X ) _____________________[0Xfunction
  [2X> AllResidueClassesWithFixedRepsModulo( [0X[3Xm[0X[2X ) ________________________[0Xfunction
  [6XReturns:[0X  A  sorted  list of all residue classes (mod [3Xm[0X) of the ring [3XR[0X, with
            fixed representatives.
  
  If  the  argument [3XR[0X is omitted it defaults to the default ring of [3Xm[0X, cf. the
  documentation   of   [10XDefaultRing[0X   in   the   [5XGAP[0X   reference   manual.  The
  representatives  are the same as those chosen by the operation [10Xmod[0X. See also
  [2XAllResidueClassesModulo[0X ([14X1.1-3[0X).
  
  [4X---------------------------  Example  ----------------------------[0X
    [4X[0X
    [4Xgap> AllResidueClassesWithFixedRepsModulo(4);[0X
    [4X[ [0/4], [1/4], [2/4], [3/4] ][0X
    [4X[0X
  [4X------------------------------------------------------------------[0X
  
  
  [1X2.2 Methods for unions of residue classes with fixed representatives[0X
  
  Throughout this chapter, the argument [3XR[0X denotes the underlying ring, and the
  arguments  [3XU[0X,  [3XU1[0X  and [3XU2[0X  denote  unions of residue classes of [3XR[0X with fixed
  representatives.
  
  Unions of residue classes with fixed representatives are multisets. Elements
  and residue classes can be contained with multiplicities:
  
  [1X2.2-1 Multiplicity[0X
  
  [2X> Multiplicity( [0X[3Xx, U[0X[2X ) _______________________________________________[0Xmethod
  [2X> Multiplicity( [0X[3Xcl, U[0X[2X ) ______________________________________________[0Xmethod
  [6XReturns:[0X  The  multiplicity  of  [3Xx[0X  in [3XU[0X  regarded  as  a  multiset  of ring
            elements,  resp.  the  multiplicity  of  the residue class [3Xcl[0X in [3XU[0X
            regarded as a multiset of residue classes.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4X[0X
    [4Xgap> U := UnionOfResidueClassesWithFixedReps(Integers,[[2,0],[3,0]]);[0X
    [4X[0/2] U [0/3][0X
    [4Xgap> List([0..20],n->Multiplicity(n,U));[0X
    [4X[ 2, 0, 1, 1, 1, 0, 2, 0, 1, 1, 1, 0, 2, 0, 1, 1, 1, 0, 2, 0, 1 ][0X
    [4Xgap> Multiplicity(ResidueClassWithFixedRep(2,0),U);[0X
    [4X1[0X
    [4X[0X
  [4X------------------------------------------------------------------[0X
  
  Let [10XU[0X be a union of residue classes with fixed representatives. The multiset
  [10XU[0X  can  have  an  attribute  [10XDensity[0X  which denotes its [13Xnatural density[0X as a
  multiset, i.e. elements with multiplicity k count k-fold. The multiset [10XU[0X has
  the  property  [10XIsOverlappingFree[0X if it consists of pairwise disjoint residue
  classes.  The  set-theoretic  union  of the residue classes forming [10XU[0X can be
  determined  by  the  operation  [10XAsOrdinaryUnionOfResidueClasses[0X.  The object
  returned by this operation is an "ordinary" residue class union as described
  in Chapter [14X1.[0X.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4X[0X
    [4Xgap> U := UnionOfResidueClassesWithFixedReps(Integers,[[2,0],[3,0]]);[0X
    [4X[0/2] U [0/3][0X
    [4Xgap> Density(U);[0X
    [4X5/6[0X
    [4Xgap> IsOverlappingFree(U);[0X
    [4Xfalse[0X
    [4Xgap> AsOrdinaryUnionOfResidueClasses(U);[0X
    [4XZ \ Union of the residue classes 1(6) and 5(6) of Z[0X
    [4Xgap> Density(last);[0X
    [4X2/3[0X
    [4X[0X
  [4X------------------------------------------------------------------[0X
  
  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".
  
  There are methods for [10X+[0X and [10X-[0X 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 [10X*[0X and [10X/[0X 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 [10XU[0X to be divisible by x. If the underlying ring is
  the  ring  of  integers,  scalar  multiplication  and  division  leave delta
  invariant (-> [2XDelta[0X ([14X2.3-1[0X)).
  
  [4X---------------------------  Example  ----------------------------[0X
    [4X[0X
    [4Xgap> U := UnionOfResidueClassesWithFixedReps(Integers,[[2,0],[3,0]]);[0X
    [4X[0/2] U [0/3][0X
    [4Xgap> U + 7;[0X
    [4X[7/2] U [7/3][0X
    [4Xgap> U - 7; 7 - U; -U;[0X
    [4X[-7/2] U [-7/3][0X
    [4X[7/-3] U [7/-2][0X
    [4X[0/-3] U [0/-2][0X
    [4Xgap> V := 2 * U;[0X
    [4X[0/4] U [0/6][0X
    [4Xgap> V/2;[0X
    [4X[0/2] U [0/3][0X
    [4X[0X
  [4X------------------------------------------------------------------[0X
  
  [1X2.2-2 Union[0X
  
  [2X> Union( [0X[3XU1, U2[0X[2X ) ____________________________________________________[0Xmethod
  [6XReturns:[0X  The union of [3XU1[0X and [3XU2[0X.
  
  The  multiplicity  of  any ring element or residue class in the union is the
  sum    of   its   multiplicities   in   the   arguments.   It   holds   that
  [10XDelta(Union([3XU1[0X,[3XU2[0X)) = Delta([3XU1[0X) + Delta([3XU2[0X)[0X. (-> [2XDelta[0X ([14X2.3-1[0X)).
  
  [4X---------------------------  Example  ----------------------------[0X
    [4X[0X
    [4Xgap> U := UnionOfResidueClassesWithFixedReps(Integers,[[2,0],[3,0]]);[0X
    [4X[0/2] U [0/3][0X
    [4Xgap> Union(U,U);                                      [0X
    [4X[0/2] U [0/2] U [0/3] U [0/3][0X
    [4X[0X
  [4X------------------------------------------------------------------[0X
  
  [1X2.2-3 Intersection[0X
  
  [2X> Intersection( [0X[3XU1, U2[0X[2X ) _____________________________________________[0Xmethod
  [6XReturns:[0X  The intersection of [3XU1[0X and [3XU2[0X.
  
  The  multiplicity of any residue class in the intersection is the minimum of
  its multiplicities in the arguments.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4X[0X
    [4Xgap> U := UnionOfResidueClassesWithFixedReps(Integers,[[2,0],[3,0]]);[0X
    [4X[0/2] U [0/3][0X
    [4Xgap> Intersection(U,ResidueClassWithFixedRep(2,0));[0X
    [4X[0/2][0X
    [4Xgap> Intersection(U,ResidueClassWithFixedRep(6,0));[0X
    [4XEmpty union of residue classes of Z with fixed representatives[0X
    [4X[0X
  [4X------------------------------------------------------------------[0X
  
  [1X2.2-4 Difference[0X
  
  [2X> Difference( [0X[3XU1, U2[0X[2X ) _______________________________________________[0Xmethod
  [6XReturns:[0X  The difference of [3XU1[0X and [3XU2[0X.
  
  The  multiplicity of any residue class in the difference is its multiplicity
  in [3XU1[0X  minus  its  multiplicity  in [3XU2[0X,  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
  [10XDelta(Difference([3XU1[0X,[3XU2[0X)) = Delta([3XU1[0X) - Delta([3XU2[0X)[0X. (-> [2XDelta[0X ([14X2.3-1[0X)).
  
  [4X---------------------------  Example  ----------------------------[0X
    [4X[0X
    [4Xgap> U := UnionOfResidueClassesWithFixedReps(Integers,[[2,0],[3,0]]);[0X
    [4X[0/2] U [0/3][0X
    [4Xgap> V := UnionOfResidueClassesWithFixedReps(Integers,[[3,0],[5,2]]);[0X
    [4X[0/3] U [2/5][0X
    [4Xgap> Difference(U,V);[0X
    [4X[0/2] U [3/5][0X
    [4X[0X
  [4X------------------------------------------------------------------[0X
  
  
  [1X2.3 The invariant Delta[0X
  
  [1X2.3-1 Delta[0X
  
  [2X> Delta( [0X[3XU[0X[2X ) ______________________________________________________[0Xattribute
  [6XReturns:[0X  The value of the invariant delta of the residue class union [3XU[0X.
  
  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 [10XRho[0X.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4X[0X
    [4Xgap> U := UnionOfResidueClassesWithFixedReps(Integers,[[2,3],[3,4]]);[0X
    [4X[3/2] U [4/3][0X
    [4Xgap> Delta(U) = (3/2-1/2) + (4/3-1/2);[0X
    [4Xtrue[0X
    [4Xgap> V := RepresentativeStabilizingRefinement(U,3);[0X
    [4X[3/6] U [5/6] U [7/6] U [4/9] U [7/9] U [10/9][0X
    [4Xgap> Delta(V) = Delta(U);[0X
    [4Xtrue[0X
    [4Xgap> Rho(V);[0X
    [4XE(12)^11[0X
    [4X[0X
  [4X------------------------------------------------------------------[0X
  
  [1X2.3-2 RepresentativeStabilizingRefinement[0X
  
  [2X> RepresentativeStabilizingRefinement( [0X[3XU, k[0X[2X ) ________________________[0Xmethod
  [6XReturns:[0X  The representative stabilizing refinement of [3XU[0X into [3Xk[0X parts.
  
  The [13Xrepresentative stabilizing refinement[0X 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.
  
  If  the  argument  [3Xk[0X  is  zero, the method performs a simplification of [3XU[0X by
  joining appropriate residue classes, if this is possible.
  
  In  any  case  the  value  of  [10XDelta([3XU[0X)[0X  is  invariant  under this operation
  (-> [2XDelta[0X ([14X2.3-1[0X)).
  
  [4X---------------------------  Example  ----------------------------[0X
    [4X[0X
    [4Xgap> U := UnionOfResidueClassesWithFixedReps(Integers,[[2,0],[3,0]]);[0X
    [4X[0/2] U [0/3][0X
    [4Xgap> RepresentativeStabilizingRefinement(U,4);   [0X
    [4X[0/8] U [2/8] U [4/8] U [6/8] U [0/12] U [3/12] U [6/12] U [9/12][0X
    [4Xgap> RepresentativeStabilizingRefinement(last,0);[0X
    [4X[0/2] U [0/3][0X
    [4X[0X
  [4X------------------------------------------------------------------[0X
  
  
  [1X2.4 The categories of unions of residue classes with fixed rep's[0X
  
  The  names  of  the  categories  of  unions  of  residue  classes with fixed
  representatives  are  [10XIsUnionOfResidueClasses[  OfZ  |  OfZ_pi | OfZorZ_pi |
  OfGFqx ]WithFixedRepresentatives[0X.
  
