<!-- #################################################################### -->
<!-- ## ## -->
<!-- ## fixedrep.xml ResClasses documentation Stefan Kohl ## -->
<!-- ## ## -->
<!-- ## $Id: fixedrep.xml,v 1.32 2007/09/26 14:44:22 stefan Exp $ ## -->
<!-- ## ## -->
<!-- #################################################################### -->
<Chapter Label="ch:UnionsOfResidueClassesWithFixedReps">
<Heading>Unions of Residue Classes with Fixed Representatives</Heading>
<Ignore Remark="set screen width to 75, for the example tester">
<Example>
<![CDATA[
gap> SizeScreen([75,24]);;
]]>
</Example>
</Ignore>
&ResClasses; supports computations with unions of residue classes which
are endowed with distinguished (<Q>fixed</Q>) 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.
<!-- #################################################################### -->
<Section Label="sec:DefiningUnionsOfResidueClassesWithFixedReps">
<Heading>
Entering unions of residue classes with fixed representatives
</Heading>
<ManSection>
<Func Name="ResidueClassWithFixedRepresentative"
Arg="R, m, r" Label="by ring, modulus and residue"/>
<Func Name="ResidueClassWithFixedRepresentative"
Arg="m, r" Label="of Z, by modulus and residue"/>
<Returns>
The residue class <A>r</A> mod <A>m</A> of the
ring <A>R</A>, with the fixed representative <A>r</A>.
</Returns>
<Description>
If the argument <A>R</A> is omitted, it defaults to <C>Integers</C>.
<Index Key="IsResidueClassWithFixedRep">
<C>IsResidueClassWithFixedRep</C>
</Index>
Residue classes with fixed representatives have the property
<C>IsResidueClassWithFixedRepresentative</C>.
The fixed representative <A>r</A> can be retrieved by the operation
<C>Residue</C>, and the modulus <A>m</A> can be retrieved by the
operation <C>Modulus</C>.
<Example>
<![CDATA[
gap> ResidueClassWithFixedRepresentative(Integers,2,1);
[1/2]
]]>
</Example>
</Description>
</ManSection>
<ManSection>
<Func Name="UnionOfResidueClassesWithFixedReps" Arg="R, classes"
Label="by ring and list of classes"/>
<Func Name="UnionOfResidueClassesWithFixedReps" Arg="classes"
Label="of Z, by list of 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>. Their first entries -- the moduli -- must be nonzero.
If the argument <A>R</A> is omitted, it defaults to <C>Integers</C>.
<Alt Only="LaTeX">\pagebreak[4]</Alt>
<Example>
<![CDATA[
gap> UnionOfResidueClassesWithFixedReps(Integers,[[2,4],[3,9]]);
[4/2] U [9/3]
]]>
</Example>
</Description>
</ManSection>
<Index Key="Modulus"
Subkey="of a union of residue classes with fixed rep's">
<C>Modulus</C>
</Index>
<Index Key="Classes"
Subkey="of a union of residue classes with fixed rep's">
<C>Classes</C>
</Index>
<Index Key="AsListOfClasses"
Subkey="for a union of residue classes with fixed rep's">
<C>AsListOfClasses</C>
</Index>
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. Further there is an
operation <C>Classes</C> for retrieving the list of classes which has been
passed as an argument to <C>UnionOfResidueClassesWithFixedReps</C>.
The operation <C>AsListOfClasses</C> does the same, except that the returned
list contains residue classes instead of pairs
<C>[<A>modulus</A>,<A>residue</A>]</C>. There are methods for <C>Print</C>,
<C>String</C> and <C>Display</C> available for unions of residue classes
with fixed representatives.
<ManSection>
<Func Name="AllResidueClassesWithFixedRepsModulo"
Arg="R, m" Label="by ring and modulus"/>
<Func Name="AllResidueClassesWithFixedRepsModulo"
Arg="m" Label="by modulus, of the default ring of that modulus"/>
<Returns>
A sorted list of all residue classes (mod <A>m</A>)
of the ring <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>, cf. 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="of a given ring, modulo a given modulus"/>.
<Example>
<![CDATA[
gap> AllResidueClassesWithFixedRepsModulo(4);
[ [0/4], [1/4], [2/4], [3/4] ]
]]>
</Example>
</Description>
</ManSection>
</Section>
<!-- #################################################################### -->
<Section Label="sec:MethodsForUnionOfResidueClassesWithFixedReps">
<Heading>
Methods for unions of residue classes with fixed representatives
</Heading>
Throughout this chapter, the argument <A>R</A> denotes the underlying ring,
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/>
Unions of residue classes with fixed representatives are multisets.
Elements and residue classes can be contained with multiplicities:
<ManSection>
<Meth Name="Multiplicity" Arg="x, U"
Label="of an element in a union of residue classes with fixed rep's"/>
<Meth Name="Multiplicity" Arg="cl, U"
Label="of a residue class in a union of residue classes with fixed rep's"/>
<Returns>
The multiplicity of <A>x</A> in <A>U</A> regarded as a multiset
of ring elements, resp. the multiplicity of the residue class <A>cl</A>
in <A>U</A> regarded as a multiset of residue classes.
</Returns>
<Description>
<Example>
<![CDATA[
gap> U := UnionOfResidueClassesWithFixedReps(Integers,[[2,0],[3,0]]);
[0/2] U [0/3]
gap> List([0..20],n->Multiplicity(n,U));
[ 2, 0, 1, 1, 1, 0, 2, 0, 1, 1, 1, 0, 2, 0, 1, 1, 1, 0, 2, 0, 1 ]
gap> Multiplicity(ResidueClassWithFixedRep(2,0),U);
1
]]>
</Example>
</Description>
</ManSection>
<Index Key="Density"
Subkey="of a union of residue classes with fixed rep's">
<C>Density</C>
</Index>
<Index Key="IsOverlappingFree"
Subkey="for a union of residue classes with fixed rep's">
<C>IsOverlappingFree</C>
</Index>
<Index Key="AsOrdinaryUnionOfResidueClasses"
Subkey="for a union of residue classes with fixed rep's">
<C>AsOrdinaryUnionOfResidueClasses</C>
</Index>
Let <C>U</C> be a union of residue classes with fixed representatives.
The multiset <C>U</C> can have an attribute <C>Density</C> which denotes
its <E>natural density</E> as a multiset, i.e. elements with
multiplicity <M>k</M> count <M>k</M>-fold.
The multiset <C>U</C> has the property <C>IsOverlappingFree</C> if it
consists of pairwise disjoint residue classes. The set-theoretic union of
the residue classes forming <C>U</C> can be determined by the
operation <C>AsOrdinaryUnionOfResidueClasses</C>. The object returned
by this operation is an <Q>ordinary</Q> residue class union as described
in Chapter <Ref Label="ch:UnionsOfResidueClasses"/>.
<Example>
<![CDATA[
gap> U := UnionOfResidueClassesWithFixedReps(Integers,[[2,0],[3,0]]);
[0/2] U [0/3]
gap> Density(U);
5/6
gap> IsOverlappingFree(U);
false
gap> AsOrdinaryUnionOfResidueClasses(U);
Z \ Union of the residue classes 1(6) and 5(6) of Z
gap> Density(last);
2/3
]]>
</Example>
In the sequel we abbreviate the term <Q>the multiset of ring elements
endowed with the structure of a union of residue classes with fixed
representatives</Q> by <Q>the multiset</Q>. <P/>
There are methods for <C>+</C> and <C>-</C> available for computing the
multiset of sums <M>u + x</M>, <M>u \in U</M>, the multiset of differences
<M>u - x</M> resp. <M>x - u</M>, <M>u \in U</M> and the multiset of the
additive inverses of the elements of <M>U</M>.
Further there are methods for <C>*</C> and <C>/</C> available for
computing the multiset of products <M>x \cdot u</M>, <M>u \in U</M>
and the multiset of quotients <M>u/x</M>, <M>u \in U</M>.
The division method requires all elements of <C>U</C> to be divisible
by <M>x</M>. If the underlying ring is the ring of integers, scalar
multiplication and division leave <M>\delta</M> invariant
(<M>\rightarrow</M> <Ref Attr="Delta"
Label="for a union of residue classes with fixed representatives"/>).
<Example>
<![CDATA[
gap> U := UnionOfResidueClassesWithFixedReps(Integers,[[2,0],[3,0]]);
[0/2] U [0/3]
gap> U + 7;
[7/2] U [7/3]
gap> U - 7; 7 - U; -U;
[-7/2] U [-7/3]
[7/-3] U [7/-2]
[0/-3] U [0/-2]
gap> V := 2 * U;
[0/4] U [0/6]
gap> V/2;
[0/2] U [0/3]
]]>
</Example>
<Alt Only="LaTeX">\pagebreak[4]</Alt>
<ManSection>
<Meth Name="Union" Arg="U1, U2"
Label="for unions of residue classes with fixed representatives"/>
<Returns>
The union of <A>U1</A> and <A>U2</A>.
</Returns>
<Description>
The multiplicity of any ring element or residue class in
the union is the sum of its multiplicities in the arguments.
It holds that <C>Delta(Union(<A>U1</A>,<A>U2</A>))
= Delta(<A>U1</A>) + Delta(<A>U2</A>)</C>.
(<M>\rightarrow</M> <Ref Attr="Delta"
Label="for a union of residue classes with fixed representatives"/>).
<Example>
<![CDATA[
gap> U := UnionOfResidueClassesWithFixedReps(Integers,[[2,0],[3,0]]);
[0/2] U [0/3]
gap> Union(U,U);
[0/2] U [0/2] U [0/3] U [0/3]
]]>
</Example>
</Description>
</ManSection>
<ManSection>
<Meth Name="Intersection" Arg="U1, U2"
Label="for unions of residue classes with fixed representatives"/>
<Returns>
The intersection of <A>U1</A> and <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> U := UnionOfResidueClassesWithFixedReps(Integers,[[2,0],[3,0]]);
[0/2] U [0/3]
gap> Intersection(U,ResidueClassWithFixedRep(2,0));
[0/2]
gap> Intersection(U,ResidueClassWithFixedRep(6,0));
Empty union of residue classes of Z with fixed representatives
]]>
</Example>
</Description>
</ManSection>
<ManSection>
<Meth Name="Difference" Arg="U1, U2"
Label="for unions of residue classes with fixed representatives"/>
<Returns>
The difference of <A>U1</A> and <A>U2</A>.
</Returns>
<Description>
The multiplicity of any residue class in the difference is its
multiplicity in <A>U1</A> minus its multiplicity in <A>U2</A>,
if this value is nonnegative. The difference of the empty residue class
union with fixed representatives and some residue class <M>[r/m]</M>
is set equal to <M>[(m-r)/m]</M>.
It holds that <C>Delta(Difference(<A>U1</A>,<A>U2</A>))
= Delta(<A>U1</A>) - Delta(<A>U2</A>)</C>.
(<M>\rightarrow</M> <Ref Attr="Delta"
Label="for a union of residue classes with fixed representatives"/>).
<Example>
<![CDATA[
gap> U := UnionOfResidueClassesWithFixedReps(Integers,[[2,0],[3,0]]);
[0/2] U [0/3]
gap> V := UnionOfResidueClassesWithFixedReps(Integers,[[3,0],[5,2]]);
[0/3] U [2/5]
gap> Difference(U,V);
[0/2] U [3/5]
]]>
</Example>
</Description>
</ManSection>
</Section>
<!-- #################################################################### -->
<Section Label="sec:DeltaAndRho">
<Heading>
The invariant Delta
</Heading>
<ManSection>
<Attr Name="Delta" Arg="U"
Label="for a union of residue classes with fixed representatives"/>
<Returns>
The value of the invariant <M>\delta</M> of the
residue class union <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 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 <M>\rho</M> which is defined by
<M>e^{\delta(U) \pi i}</M>. The corresponding attribute is called
<C>Rho</C>.
<Index Key="Rho"
Subkey="for a union of residue classes with fixed rep's">
<C>Rho</C>
</Index>
<Example>
<![CDATA[
gap> U := UnionOfResidueClassesWithFixedReps(Integers,[[2,3],[3,4]]);
[3/2] U [4/3]
gap> Delta(U) = (3/2-1/2) + (4/3-1/2);
true
gap> V := RepresentativeStabilizingRefinement(U,3);
[3/6] U [5/6] U [7/6] U [4/9] U [7/9] U [10/9]
gap> Delta(V) = Delta(U);
true
gap> Rho(V);
E(12)^11
]]>
</Example>
</Description>
</ManSection>
<ManSection>
<Meth Name="RepresentativeStabilizingRefinement" Arg="U, k"
Label="of a union of res.-classes with fixed rep's"/>
<Returns>
The representative stabilizing refinement of <A>U</A>
into <A>k</A> parts.
</Returns>
<Description>
The <E>representative stabilizing refinement</E> of a residue class
<M>[r/m]</M> of <M>\mathbb{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 the obvious way to unions of residue
classes. <P/>
If the argument <A>k</A> is zero, the method performs a simplification
of <A>U</A> by joining appropriate residue classes, if this is possible.
<P/>
In any case the value of <C>Delta(<A>U</A>)</C> is invariant under
this operation (<M>\rightarrow</M> <Ref Attr="Delta"
Label="for a union of residue classes with fixed representatives"/>).
<Example>
<![CDATA[
gap> U := UnionOfResidueClassesWithFixedReps(Integers,[[2,0],[3,0]]);
[0/2] U [0/3]
gap> RepresentativeStabilizingRefinement(U,4);
[0/8] U [2/8] U [4/8] U [6/8] U [0/12] U [3/12] U [6/12] U [9/12]
gap> RepresentativeStabilizingRefinement(last,0);
[0/2] U [0/3]
]]>
</Example>
</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 are <C>IsUnionOfResidueClasses[ OfZ | OfZ&uscore;pi |
OfZorZ&uscore;pi | OfGFqx ]WithFixedRepresentatives</C>.
</Section>
<!-- #################################################################### -->
</Chapter>
<!-- #################################################################### -->
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
91213ddcfbe7f54821d42c2d9e091326
>
files
>
2592
