<!-- #################################################################### -->
<!-- ##                                                                ## -->
<!-- ##  resclass.xml      ResClasses documentation       Stefan Kohl  ## -->
<!-- ##                                                                ## -->
<!-- ##  $Id: resclass.xml,v 1.14 2004/02/02 13:24:36 stefan Exp $     ## -->
<!-- ##                                                                ## -->
<!-- #################################################################### -->

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

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

<Section Label="sec:DefiningUnionsOfResidueClasses">
<Heading>Defining unions of residue classes</Heading>

  <ManSection>
    <Func Name="ResidueClass" Arg="R, m, r"/>
    <Description>
      The residue class <A>r</A> mod <A>m</A> of the ring <A>R</A>.
<Example>
<![CDATA[
gap> A := ResidueClass(Integers,3,2);
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> B = ResidueClass(Integers,2,1);
false
gap> R := PolynomialRing(GF(7),1);;
gap> 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>
    <Func Name="ResidueClassUnion" Arg="R, m, r"/>
    <Func Name="ResidueClassUnion" Arg="R, m, r, included, excluded"/>
    <Description>
      The union of the residue classes <A>r</A>[ <M>i</M> ] mod <A>m</A>
      of the ring <A>R</A>.
      If the arguments <A>included</A> and <A>excluded</A> are given, they
      denote lists of elements to be added to resp. to be taken away from
      the union.
<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>

  The components of a residue class union as given as arguments
  in <Ref Func="ResidueClassUnion"/>
  can be extracted as follows.

  <ManSection>
    <Meth Name="Modulus" Arg="U"/>
    <Returns>the modulus <A>m</A> of <A>U</A>.</Returns>
  </ManSection>

  <ManSection>
    <Oper Name="Residues" Arg="U"/>
    <Returns>the set of residues <A>r</A> of <A>U</A>.</Returns>
    <Description>
      If an element <A>el</A> of the underlying ring of <A>U</A> is
      congruent to one of the residues of <A>U</A> modulo the modulus of
      <A>U</A>, it is contained in <A>U</A>, provided that it is not excluded
      explicitly ( see <Ref Oper="ExcludedElements"/> ).
    </Description>
  </ManSection>

  <ManSection>
    <Oper Name="IncludedElements" Arg="U"/>
    <Returns>
      the set <A>included</A> of single elements of <A>U</A>.
    </Returns>
  </ManSection>

  <ManSection>
    <Oper Name="ExcludedElements" Arg="U"/>
    <Returns>
      the set <A>excluded</A> of single elements explicitly not contained in
      <A>U</A>.
    </Returns>
  </ManSection>

</Section>

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

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

  <ManSection>
    <Meth Name="String" Arg="U"/>
    <Meth Name="String" Arg="U, lng"/>
    <Returns>
      a string representation of the residue class union <A>U</A>.
    </Returns>
    <Description>
      If the argument <A>lng</A> is given its absolute value denotes the
      length of the returned string; if <A>lng</A> is negative, the result
      is flushed left, otherwise it is flushed right.
<Example>
<![CDATA[
gap> String(C);
"ResidueClassUnion( GF(7)[x], x+Z(7)^0, [ Z(7) ] )"
gap> String(F);
"ResidueClassUnion( Integers, 5, [ 1, 2 ], [ 3, 8 ], [ -4, 1 ] )"
gap> String(H);
"ResidueClassUnion( Z_( 2, 3 ), 8, [ 3, 5 ] )"
]]>
</Example>
    </Description>
  </ManSection>

  <ManSection>
    <Meth Name="Print" Arg="U"/>
    <Description>
      Prints the residue class union <A>U</A> in a way similar to what
      a user has to write in order to create this object.
<Example>
<![CDATA[
gap> Print(C,"\n");
ResidueClassUnion( GF(7)[x], x+Z(7)^0, [ Z(7) ] )
gap> Print(F,"\n");
ResidueClassUnion( Integers, 5, [ 1, 2 ], [ 3, 8 ], [ -4, 1 ] )
gap> Print(H,"\n");
ResidueClassUnion( Z_( 2, 3 ), 8, [ 3, 5 ] )
]]>
</Example>
    </Description>
  </ManSection>

  <ManSection>
    <Meth Name="Display" Arg="U"/>
    <Description>
      Displays the residue class union <A>U</A> in a nice,
      human-readable form.
<Example>
<![CDATA[
gap> Display(F);

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

 1 2

and the elements

 3 8

without the elements

 -4  1

gap> Display(G);

The union of the residue classes r ( mod x ) of GF(7)[x] for r =

Z(7)^0  -Z(7)^0 Z(7)^5  

and the element

0*Z(7) 

without the element

Z(7)^0 

gap> Display(H);

The union of the residue classes r ( mod 8 ) of Z_( 2, 3 ) for r =

 3 5

]]>
</Example>
    </Description>
  </ManSection>

  <ManSection>
    <Meth Name="\in" Arg="el, U"/>
    <Description>
      Tests whether <A>el</A> is an element of the
      residue class union <A>U</A>. 
<Example>
<![CDATA[
gap> 20 in A;
true
gap> -20 in A;
false
gap> 1/3 in B;
true
gap> 1/5 in B;
false
gap> x in G;
false
gap> Zero(R) in G;
true
]]>
</Example>
    </Description>
  </ManSection>

  <ManSection>
    <Meth Name="IsSubset" Arg="U1, U2"/>
    <Description>
      Checks whether the residue class union <A>U2</A> is a subset of
      the residue class union <A>U1</A>.
<Example>
<![CDATA[
gap> IsSubset(A,D);
false
gap> IsSubset(H,ResidueClass(Z_pi([2,3]),16,11));
true
]]>
</Example>
    </Description>
  </ManSection>

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

  <ManSection>
    <Meth Name="Union" Arg="U1, U2"/>
    <Meth Name="Union" Arg="U, S"/>
    <Returns>
      the union of two residue class unions <A>U1</A> and <A>U2</A>
      resp. of the residue class union <A>U</A> and the finite set <A>S</A>
      of elements of the ring <A>U</A> 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"/>
    <Meth Name="Intersection" Arg="U, S"/>
    <Returns>
      the intersection of two residue class unions <A>U1</A> and <A>U2</A>
      resp. of the residue class union <A>U</A> and the finite set <A>S</A>
      of elements of the ring <A>U</A> 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"/>
    <Meth Name="Difference"   Arg="U, S"/>
    <Returns>
      the difference of two residue class unions <A>U1</A> and <A>U2</A>
      resp. of the residue class union <A>U</A> and the finite set <A>S</A>
      of elements of the ring <A>U</A> 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>

  <ManSection>
    <Meth Name="Iterator" Arg="U"/>
    <Returns> an iterator of the residue class union <A>U</A>. </Returns>
    <Description>
      Currently, iterators are only implemented for residue class unions of
      the integers.
<Example>
<![CDATA[
gap> it := Iterator(F);
<iterator of a residue class union of Z>
]]>
</Example>
    </Description>
  </ManSection>

  <ManSection>
    <Meth Name="NextIterator" Arg="iter"/>
    <Returns>
      the next element delivered by the iterator <A>iter</A> of
      some residue class union.
    </Returns>
    <Description>
      Currently, iterators are only implemented for residue class unions of
      the integers.
<Example>
<![CDATA[
gap> l := List([1..16],i->NextIterator(it));
[ 3, 8, 2, -3, 6, -9, 7, -8, 11, -14, 12, -13, 16, -19, 17, -18 ]
gap> Difference(l,Intersection(F,[-20..20]));
[  ]
]]>
</Example>
    </Description>
  </ManSection>

  <ManSection>
    <Meth Name="\+" Arg="U, x"/>
    <Meth Name="\+" Arg="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"/>
    <Meth Name="\-" Arg="x, U"/>
    <Meth Name="\-" Arg="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 <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"/>
    <Meth Name="\*" Arg="x, U"/>
    <Returns>
      the set of products <M>x \cdot u</M>, <M>u \in U</M>.
    </Returns>
    <Description>
<Example>
<![CDATA[
gap> 2*A;
The residue class 4(6) of Z
gap> D*17;
Union of the residue classes 34(102) and 68(102) of Z
gap> x^3*C;
The residue class Z(7)*x^3 ( mod x^4+x^3 ) of GF(7)[x]
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"/>
    <Returns>
      the set of quotients <M>u/x</M>, <M>u \in U</M>.
    </Returns>
    <Description>
      If the result is 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>

</Section>

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

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

  <ManSection>
    <Filt Name="IsUnionOfResidueClasses" Arg="U"/>
    <Description>
      The category of all unions of residue classes.
    </Description>
  </ManSection>

  <ManSection>
    <Filt Name="IsUnionOfResidueClassesOfZ" Arg="U"/>
    <Description>
      The category of all unions of residue classes of <M>\Z</M>.
    </Description>
  </ManSection>

  <ManSection>
    <Filt Name="IsUnionOfResidueClassesOfZ_pi" Arg="U"/>
    <Description>
      The category of all unions of residue classes of some semilocalization
      <M>\Z_{(\pi)}</M> of the integers.
    </Description>
  </ManSection>

  <ManSection>
    <Filt Name="IsUnionOfResidueClassesOfZorZ_pi" Arg="U"/>
    <Description>
      The category of all unions of residue classes of <M>\Z</M> or
      <M>\Z_{(\pi)}</M>.
    </Description>
  </ManSection>

  <ManSection>
    <Filt Name="IsUnionOfResidueClassesOfGFqx" Arg="U"/>
    <Description>
      The category of all unions of residue classes of some polynomial ring
      GF( <M>q</M> )[ <M>x</M> ].
    </Description>
  </ManSection>

  <ManSection>
    <Func Name="ResidueClassUnionsFamily" Arg="R"/>
    <Description>
      The family of unions of residue classes of the ring <A>R</A>. <P/>
      The ring <A>R</A> can be accessed as
      <C>UnderlyingRing( ResidueClassUnionsFamily( <A>R</A> ) )</C>.
    </Description>
  </ManSection>

</Section>

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

</Chapter>

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