<!-- #################################################################### -->
<!-- ##                                                                ## -->
<!-- ##  fixedrep.xml      ResClasses documentation       Stefan Kohl  ## -->
<!-- ##                                                                ## -->
<!-- ##  $Id: fixedrep.xml,v 1.16 2005/05/24 08:24:36 stefan Exp $     ## -->
<!-- ##                                                                ## -->
<!-- #################################################################### -->

<Chapter Label="ch:UnionsOfResidueClassesWithFixedReps">
<Heading>Unions of Residue Classes with Fixed Representatives</Heading>

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

<Section Label="sec:AboutUnionsOfResidueClassesWithFixedReps">
<Heading>
  About unions of residue classes with fixed representatives
</Heading>

In this chapter, a different kind of unions of residue classes is
introduced -- namely the one of residue classes which are endowed with
a distinguished (<Q>fixed</Q>) representative.

These unions of residue classes behave different than the <Q>ordinary</Q>
residue class unions which were described in the previous chapter:

<List>

  <Mark>-</Mark>
  <Item>
    In most situations they behave like lists of single residue classes
    with fixed representatives rather than like sets of ring elements.
    There are exceptions from this behaviour, e.g. w.r.t. forming
    differences, in order to ensure <Q><M>\delta</M>-additivity</Q>
    (<M>\rightarrow</M>&nbsp;<Ref Attr="Delta" Label="U"/>).
  </Item>

  <Mark>-</Mark>
  <Item>
    They can be viewed as <E>multisets</E> of ring elements --
    the residue classes in such a union are not necessarily disjoint,
    and not even necessarily distinct.
  </Item>

</List>

Throughout this chapter, the argument <A>R</A> denotes the ring whose
residue classes are considered, and the arguments <A>U</A>, <A>U1</A>
and <A>U2</A> denote unions of residue classes of <A>R</A> with fixed
representatives. <P/>

Some of the functionality described in this chapter makes only sense
if <A>R</A> is the ring of integers -- in particular this holds for
everything concerning the invariant <M>\delta</M>.

</Section>

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

<Section Label="sec:DefiningUnionsOfResidueClassesWithFixedReps">
<Heading>
  Entering unions of residue classes with fixed representatives
</Heading>

<ManSection>
  <Func Name="ResidueClassWithFixedRepresentative"
        Arg="R, m, r" Label="R, m, r"/>
  <Func Name="ResidueClassWithFixedRepresentative"
        Arg="m, r" Label="m, r"/>
  <Returns>
    The residue class <A>r</A>&nbsp;mod&nbsp;<A>m</A> of the
    ring&nbsp;<A>R</A>, with fixed representative&nbsp;<A>r</A>.
  </Returns>
  <Description>
    If the argument <A>R</A> is omitted, it defaults to <C>Integers</C>.
<Example>
<![CDATA[
gap> cl1 := ResidueClassWithFixedRepresentative(Integers,3,2);
[2/3]
gap> cl2 := ResidueClassWithFixedRepresentative(Integers,2,1);
[1/2]
]]>
</Example>
  </Description>
</ManSection>

In all names of functions described in this chapter, <C>Representative</C>
can be abbreviated by <C>Rep</C>. When entering a union of residue classes
with fixed representative, for <E>any</E> residue class in the union
a representative has to be specified:

<ManSection>
  <Func Name="ResidueClassUnionWithFixedRepresentatives"
        Arg="R, classes" Label="R, classes"/>
  <Func Name="ResidueClassUnionWithFixedRepresentatives"
        Arg="classes" Label="classes"/>
  <Returns>
    The union of the residue classes <A>classes</A>[<M>i</M>][2] mod
    <A>classes</A>[<M>i</M>][1] of the ring <A>R</A>, with fixed
    representatives <A>classes</A>[<M>i</M>][2].
  </Returns>
  <Description>
    The argument <A>classes</A> must be a list of pairs of elements of
    the ring <A>R</A>, those first elements (the moduli) have to be
    non-zero. If the argument <A>R</A> is omitted, it defaults to
    <C>Integers</C>.
<Example>
<![CDATA[
gap> U := ResidueClassUnionWithFixedRepresentatives(Integers,[[2,1],[7,4]]);
[1/2] U [4/7]
]]>
</Example>
  </Description>
</ManSection>

There is a method for the operation <C>Modulus</C>, which returns the
lcm of the moduli of the residue classes forming such a union, and there
is an operation <C>Classes</C> for extracting the list of classes which
is passed as an argument to <C>ResidueClassUnionWithFixedRepresentatives</C>.

<ManSection>
  <Func Name="AllResidueClassesWithFixedRepresentativesModulo"
        Arg="R, m" Label="R, m"/>
  <Func Name="AllResidueClassesWithFixedRepresentativesModulo"
        Arg="m" Label="m"/>
  <Returns>
    A sorted list of all residue classes (mod&nbsp;<A>m</A>)
    of the ring&nbsp;<A>R</A>, with fixed representatives.
  </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. The representatives are the same as those chosen
    by the operation <C>mod</C>.
    See also <Ref Func="AllResidueClassesModulo" Label="R, m"/>.
<Example>
<![CDATA[
gap> AllResidueClassesWithFixedRepresentativesModulo(Z_pi(2),4);
[ [0/4], [1/4], [2/4], [3/4] ]
gap> AllResidueClassesWithFixedRepsModulo(9);
[ [0/9], [1/9], [2/9], [3/9], [4/9], [5/9], [6/9], [7/9], [8/9] ]
]]>
</Example>
  </Description>
</ManSection>

</Section>

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

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

There are methods for <C>Print</C>, <C>String</C> and <C>Display</C>
which are applicable to unions of residue classes with fixed representatives.
Unions of residue classes are multisets, thus elements can be contained with
different multiplicities:

<ManSection>
  <Meth Name="Multiplicity" Arg="x, U" Label="x, U"/>
  <Returns>
    The multiplicity of <A>x</A> in&nbsp;<A>U</A> regarded as a multiset
    of ring elements.
  </Returns>
  <Description>
<Example>
<![CDATA[
gap> List([1,2,11],n->Multiplicity(n,U));
[ 1, 0, 2 ]
]]>
</Example>
  </Description>
</ManSection>

<ManSection>
  <Prop Name="IsOverlappingFree" Arg="U" Label="U"/>
  <Returns>
    <C>true</C> if the residue classes in&nbsp;<A>U</A> are pairwisely
    disjoint and <C>false</C> otherwise.
  </Returns>
  <Description>
    We call a residue class union&nbsp;<A>U</A> with fixed representatives
    <E>overlapping free</E> if and only if it consists of pairwisely
    disjoint residue classes.
<Example>
<![CDATA[
gap> IsOverlappingFree(cl1);
true
gap> IsOverlappingFree(U);
false
]]>
</Example>
  </Description>
</ManSection>

<ManSection>
  <Meth Name="AsOrdinaryUnionOfResidueClasses" Arg="U" Label="U"/>
  <Returns>
    The set-theoretic union of the residue classes in&nbsp;<A>U</A>.
  </Returns>
  <Description>
    The returned object is an ordinary residue class union
    without fixed representatives as described in
    Chapter&nbsp;<Ref Label="ch:UnionsOfResidueClasses" />
    which behaves like a subset of the underlying ring.
<Example>
<![CDATA[
gap> List([cl1,cl2,U],AsOrdinaryUnionOfResidueClasses);
[ The residue class 2(3) of Z, The residue class 1(2) of Z, 
  Union of the residue classes 1(2) and 4(14) of Z ]
]]>
</Example>
  </Description>
</ManSection>

<ManSection>
  <Meth Name="\in" Arg="cl, U" Label="cl, U"/>
  <Returns>
    <C>true</C> if the residue class <A>cl</A> with a fixed representative
    is an element of&nbsp;<A>U</A> and <C>false</C> otherwise.
  </Returns>
  <Description>
<Example>
<![CDATA[
gap> cl1 in U;
false
gap> cl2 in U;
true
]]>
</Example>
  </Description>
</ManSection>

<ManSection>
  <Meth Name="AsListOfClasses" Arg="U" Label="U"/>
  <Returns>
    The sorted list of the residue classes in&nbsp;<A>U</A>.
  </Returns>
  <Description>
<Example>
<![CDATA[
gap> AsListOfClasses(U);
[ [1/2], [4/7] ]
]]>
</Example>
  </Description>
</ManSection>

<ManSection>
  <Meth Name="IsSubset" Arg="U1, U2" Label="U1, U2"/>
  <Returns>
    <C>true</C> if <A>U2</A> is a subset of <A>U1</A>
    and <C>false</C> otherwise.
  </Returns>
  <Description>
    We say that <A>U2</A> is a subset of <A>U1</A> if the multiplicity
    of any residue class&nbsp;<M>[r/m]</M> in <A>U1</A> is greater than
    or equal to its multiplicity in&nbsp;<A>U2</A>.
<Example>
<![CDATA[
gap> IsSubset(U,cl1);
false
gap> IsSubset(U,cl2);
true
]]>
</Example>
  </Description>
</ManSection>

<ManSection>
  <Oper Name="Density" Arg="U" Label="U"/>
  <Returns>
    The natural density of <A>U</A> as a multiset (elements with
    multiplicity&nbsp;<M>k</M> count <M>k</M>-fold).
  </Returns>
  <Description>
<Example>
<![CDATA[
gap> Density(U);
9/14
gap> 1/2+1/7;
9/14
]]>
</Example>
  </Description>
</ManSection>

<ManSection>
  <Meth Name="Union" Arg="U1, U2" Label="U1, U2"/>
  <Returns>
    The union of <A>U1</A> and&nbsp;<A>U2</A>.
  </Returns>
  <Description>
    It holds <C>Delta(Union(<A>U1</A>,<A>U2</A>))
    = Delta(<A>U1</A>) + Delta(<A>U2</A>)</C>.
    (<M>\rightarrow</M>&nbsp;<Ref Attr="Delta" Label="U"/>).
<Example>
<![CDATA[
gap> Union(U,cl1);
[1/2] U [2/3] U [4/7]
]]>
</Example>
  </Description>
</ManSection>

<ManSection>
  <Meth Name="Intersection" Arg="U1, U2" Label="U1, U2"/>
  <Returns>
    The intersection of <A>U1</A> and&nbsp;<A>U2</A>.
  </Returns>
  <Description>
    The multiplicity of any residue class in the intersection
    is the minimum of its multiplicities in the arguments. 
<Example>
<![CDATA[
gap> Intersection(cl1,cl2);
Empty union of residue classes of Z with fixed representatives
gap> Intersection(List([cl1,cl2],AsOrdinaryUnionOfResidueClasses));
The residue class 5(6) of Z
gap> Intersection(cl2,U);
[1/2]
]]>
</Example>
  </Description>
</ManSection>

<ManSection>
  <Meth Name="Difference" Arg="U1, U2" Label="U1, U2"/>
  <Returns>
    The difference of <A>U1</A> and&nbsp;<A>U2</A>.
  </Returns>
  <Description>
    It holds <C>Delta(Difference(<A>U1</A>,<A>U2</A>))
    = Delta(<A>U1</A>) - Delta(<A>U2</A>)</C>.
    (<M>\rightarrow</M>&nbsp;<Ref Attr="Delta" Label="U"/>).
    This is ensured by setting the difference of the empty residue class
    union with fixed representatives and some residue class <M>[r/m]</M>
    equal to <M>[(m-r)/m]</M>.
<Example>
<![CDATA[
gap> Difference(U,cl1);
[1/2] U [1/3] U [4/7]
gap> Difference(U,cl2);
[4/7]
]]>
</Example>
  </Description>
</ManSection>

Throughout the rest of this section, <A>U</A> is regarded as
a multiset of ring elements. For sake of simplicity, the term
<Q>the multiset of ring elements endowed with the structure of
a union of residue classes with fixed representatives</Q> is
abbreviated by <Q>the multiset</Q>.

<ManSection>
  <Meth Name="\+" Arg="U, x" Label="U, x"/>
  <Meth Name="\+" Arg="x, U" Label="x, U"/>
  <Returns>
    The multiset of sums <M>u + x</M>, <M>u \in U</M>.
  </Returns>
  <Description>
<Example>
<![CDATA[
gap> cl1 + 1;
[3/3]
gap> U+23;
[24/2] U [27/7]
]]>
</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 multiset 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> cl2 - 1;
[0/2]
gap> U - 17;
[-16/2] U [-13/7]
]]>
</Example>
  </Description>
</ManSection>

<ManSection>
  <Meth Name="\*" Arg="U, x" Label="U, x"/>
  <Meth Name="\*" Arg="x, U" Label="x, U"/>
  <Returns>
    The multiset of products <M>x \cdot u</M>, <M>u \in U</M>.
  </Returns>
  <Description>
    Scalar multiplication leaves <M>\delta</M> invariant
    (<M>\rightarrow</M>&nbsp;<Ref Attr="Delta" Label="U"/>).
<Example>
<![CDATA[
gap> 3*cl1;
[6/9]
gap> 7*U;
[7/14] U [28/49]
]]>
</Example>
  </Description>
</ManSection>

<ManSection>
  <Meth Name="\/" Arg="U, x" Label="U, x"/>
  <Returns>
    The multiset of quotients <M>u/x</M>, <M>u \in U</M>.
  </Returns>
  <Description>
    Scalar division leaves <M>\delta</M> invariant
    (<M>\rightarrow</M>&nbsp;<Ref Attr="Delta" Label="U"/>).
    If not all elements of all residue classes in <A>U</A> are divisible
    by&nbsp;<A>x</A>, the method gives up.
<Example>
<![CDATA[
gap> (2*cl1+2)/3;
[2/2]
]]>
</Example>
  </Description>
</ManSection>

</Section>

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

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

<Section Label="sec:WhereRepsComeIntoPlay">
<Heading>
  The invariant Delta
</Heading>

<ManSection>
  <Meth Name="RepresentativeStabilizingRefinement" Arg="U, k" Label="U, k"/>
  <Returns>
    The representative stabilizing refinement of <A>U</A>
    into <M>k</M>&nbsp;parts.
  </Returns>
  <Description>
    The <E>representative stabilizing refinement</E> of a residue class
    <M>[r/m]</M> of <M>\Z</M> into <M>k</M> parts is defined by
    <M>[r/km] \cup [(r+m)/km] \cup \dots \cup [(r+(k-1)m)/km]</M>.
    This definition is extended in a natural way to unions of residue
    classes. <P/>

    The method tries to perform a simplification of <A>U</A> by joining
    appropriate residue classes if the argument <A>k</A> is zero. <P/>

    In any case the value of <C>Delta(<A>U</A>)</C> is invariant under
    this operation (<M>\rightarrow</M>&nbsp;<Ref Attr="Delta" Label="U"/>).
<Example>
<![CDATA[
gap> cl := ResidueClassUnionWithFixedReps(Integers,[[2,1]]);
[1/2]
gap> S := RepresentativeStabilizingRefinement(cl,3);
[1/6] U [3/6] U [5/6]
gap> cls := AsListOfClasses(S);
[ [1/6], [3/6], [5/6] ]
gap> cls := List([1..3],i->RepresentativeStabilizingRefinement(cls[i],i+1));
[ [1/12] U [7/12], [3/18] U [9/18] U [15/18], 
  [5/24] U [11/24] U [17/24] U [23/24] ]
gap> S := Union(cls);
<union of 9 residue classes of Z with fixed representatives>
gap> RepresentativeStabilizingRefinement(S,0);
[1/2]
]]>
</Example>
  </Description>
</ManSection>

<ManSection>
  <Attr Name="Delta" Arg="U" Label="U"/>
  <Returns>
    The value of the invariant <M>\delta</M> of the
    residue class union&nbsp;<A>U</A>.
  </Returns>
  <Description>
    For a residue class <M>[r/m]</M> with fixed representative we set
    <M>\delta([r/m]) := r/m - 1/2</M> and extend this additively to unions of
    such residue classes. If no representatives are fixed, this definition
    is still unique (mod&nbsp;1).
<Example>
<![CDATA[
gap> [ Delta(U), (1/2-1/2)+(4/7-1/2) ];
[ 1/14, 1/14 ]
gap> V := RepresentativeStabilizingRefinement(U,3);
[1/6] U [3/6] U [5/6] U [4/21] U [11/21] U [18/21]
gap> Delta(V) = (1/6-1/2)+(3/6-1/2)+(5/6-1/2)+(4/21-1/2)+(11/21-1/2)+(18/21-1/2);
true
]]>
</Example>
  </Description>
</ManSection>

<ManSection>
  <Attr Name="Rho" Arg="U" Label="U"/>
  <Returns>
    The value of the invariant <M>\rho</M> of the
    residue class union&nbsp;<A>U</A>.
  </Returns>
  <Description>
    For a union <M>U \subseteq \Z</M> of finitely many residue classes,
    we set <M>\rho(U) := e^{\pi i \delta(U)}</M>.
  </Description>
</ManSection>

</Section>

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

<Section Label="sec:CategoriesOfUnionsOfResidueClassesWithFixedReps">
<Heading>
  The categories of unions of residue classes with fixed rep's
</Heading>

The names of the categories of unions of residue classes with fixed
representatives can be derived from the names of those of the
<Q>ordinary</Q> unions of residue classes given in
Section&nbsp;<Ref Label="sec:CategoriesOfUnionsOfResidueClasses" />
by appending <C>WithFixedRepresentatives</C>.

</Section>

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

</Chapter>

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