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 ("fixed") representative. These unions of residue classes behave different than the "ordinary" residue class unions which were described in the previous chapter:
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 "delta-additivity" (-> Delta
(4.4-2)).
They can be viewed as multisets of ring elements -- the residue classes in such a union are not necessarily disjoint, and not even necessarily distinct.
Throughout this chapter, the argument R denotes the ring whose residue classes are considered, and the arguments U, U1 and U2 denote unions of residue classes of R with fixed representatives.
Some of the functionality described in this chapter makes only sense if R is the ring of integers -- in particular this holds for everything concerning the invariant delta.
> ResidueClassWithFixedRepresentative ( R, m, r ) | ( function ) |
> ResidueClassWithFixedRepresentative ( m, r ) | ( function ) |
Returns: The residue class r mod m of the ring R, with fixed representative r.
If the argument R is omitted, it defaults to Integers
.
gap> cl1 := ResidueClassWithFixedRepresentative(Integers,3,2); [2/3] gap> cl2 := ResidueClassWithFixedRepresentative(Integers,2,1); [1/2] |
In all names of functions described in this chapter, Representative
can be abbreviated by Rep
. When entering a union of residue classes with fixed representative, for any residue class in the union a representative has to be specified:
> ResidueClassUnionWithFixedRepresentatives ( R, classes ) | ( function ) |
> ResidueClassUnionWithFixedRepresentatives ( classes ) | ( function ) |
Returns: The union of the residue classes classes[i][2] mod classes[i][1] of the ring R, with fixed representatives classes[i][2].
The argument classes must be a list of pairs of elements of the ring R, those first elements (the moduli) have to be non-zero. If the argument R is omitted, it defaults to Integers
.
gap> U := ResidueClassUnionWithFixedRepresentatives(Integers,[[2,1],[7,4]]); [1/2] U [4/7] |
There is a method for the operation Modulus
, which returns the lcm of the moduli of the residue classes forming such a union, and there is an operation Classes
for extracting the list of classes which is passed as an argument to ResidueClassUnionWithFixedRepresentatives
.
> AllResidueClassesWithFixedRepresentativesModulo ( R, m ) | ( function ) |
> AllResidueClassesWithFixedRepresentativesModulo ( m ) | ( function ) |
Returns: A sorted list of all residue classes (mod m) of the ring R, with fixed representatives.
If the argument R is omitted it defaults to the default ring of m -- cp. the documentation of DefaultRing
in the GAP reference manual. The representatives are the same as those chosen by the operation mod
. See also AllResidueClassesModulo
(3.1-4).
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] ] |
There are methods for Print
, String
and Display
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:
> Multiplicity ( x, U ) | ( method ) |
Returns: The multiplicity of x in U regarded as a multiset of ring elements.
gap> List([1,2,11],n->Multiplicity(n,U)); [ 1, 0, 2 ] |
> IsOverlappingFree ( U ) | ( property ) |
Returns: true
if the residue classes in U are pairwisely disjoint and false
otherwise.
We call a residue class union U with fixed representatives overlapping free if and only if it consists of pairwisely disjoint residue classes.
gap> IsOverlappingFree(cl1); true gap> IsOverlappingFree(U); false |
> AsOrdinaryUnionOfResidueClasses ( U ) | ( method ) |
Returns: The set-theoretic union of the residue classes in U.
The returned object is an ordinary residue class union without fixed representatives as described in Chapter 3. which behaves like a subset of the underlying ring.
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 ] |
> \in ( cl, U ) | ( method ) |
Returns: true
if the residue class cl with a fixed representative is an element of U and false
otherwise.
gap> cl1 in U; false gap> cl2 in U; true |
> AsListOfClasses ( U ) | ( method ) |
Returns: The sorted list of the residue classes in U.
gap> AsListOfClasses(U); [ [1/2], [4/7] ] |
> IsSubset ( U1, U2 ) | ( method ) |
Returns: true
if U2 is a subset of U1 and false
otherwise.
We say that U2 is a subset of U1 if the multiplicity of any residue class [r/m] in U1 is greater than or equal to its multiplicity in U2.
gap> IsSubset(U,cl1); false gap> IsSubset(U,cl2); true |
> Density ( U ) | ( operation ) |
Returns: The natural density of U as a multiset (elements with multiplicity k count k-fold).
gap> Density(U); 9/14 gap> 1/2+1/7; 9/14 |
> Union ( U1, U2 ) | ( method ) |
Returns: The union of U1 and U2.
It holds Delta(Union(U1,U2)) = Delta(U1) + Delta(U2)
. (-> Delta
(4.4-2)).
gap> Union(U,cl1); [1/2] U [2/3] U [4/7] |
> Intersection ( U1, U2 ) | ( method ) |
Returns: The intersection of U1 and U2.
The multiplicity of any residue class in the intersection is the minimum of its multiplicities in the arguments.
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] |
> Difference ( U1, U2 ) | ( method ) |
Returns: The difference of U1 and U2.
It holds Delta(Difference(U1,U2)) = Delta(U1) - Delta(U2)
. (-> Delta
(4.4-2)). This is ensured by setting the difference of the empty residue class union with fixed representatives and some residue class [r/m] equal to [(m-r)/m].
gap> Difference(U,cl1); [1/2] U [1/3] U [4/7] gap> Difference(U,cl2); [4/7] |
Throughout the rest of this section, U is regarded as a multiset of ring elements. For sake of simplicity, the term "the multiset of ring elements endowed with the structure of a union of residue classes with fixed representatives" is abbreviated by "the multiset".
> \+ ( U, x ) | ( method ) |
> \+ ( x, U ) | ( method ) |
Returns: The multiset of sums u + x, u in U.
gap> cl1 + 1; [3/3] gap> U+23; [24/2] U [27/7] |
> \- ( U, x ) | ( method ) |
> \- ( x, U ) | ( method ) |
> \- ( U ) | ( method ) |
Returns: The multiset of differences u - x, u in U resp. the set of differences x - u, u in U resp. the set of the additive inverses of the elements of U.
gap> cl2 - 1; [0/2] gap> U - 17; [-16/2] U [-13/7] |
> \* ( U, x ) | ( method ) |
> \* ( x, U ) | ( method ) |
Returns: The multiset of products x * u, u in U.
Scalar multiplication leaves delta invariant (-> Delta
(4.4-2)).
gap> 3*cl1; [6/9] gap> 7*U; [7/14] U [28/49] |
> \/ ( U, x ) | ( method ) |
Returns: The multiset of quotients u/x, u in U.
Scalar division leaves delta invariant (-> Delta
(4.4-2)). If not all elements of all residue classes in U are divisible by x, the method gives up.
gap> (2*cl1+2)/3; [2/2] |
> RepresentativeStabilizingRefinement ( U, k ) | ( method ) |
Returns: The representative stabilizing refinement of U into k parts.
The representative stabilizing refinement 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 a natural way to unions of residue classes.
The method tries to perform a simplification of U by joining appropriate residue classes if the argument k is zero.
In any case the value of Delta(U)
is invariant under this operation (-> Delta
(4.4-2)).
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] |
> Delta ( U ) | ( attribute ) |
Returns: The value of the invariant delta of the residue class union U.
For a residue class [r/m] with fixed representative we set delta([r/m]) := r/m - 1/2 and extend this additively to unions of such residue classes. If no representatives are fixed, this definition is still unique (mod 1).
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 |
> Rho ( U ) | ( attribute ) |
Returns: The value of the invariant rho of the residue class union U.
For a union U subseteq Z of finitely many residue classes, we set rho(U) := e^pi i delta(U).
The names of the categories of unions of residue classes with fixed representatives can be derived from the names of those of the "ordinary" unions of residue classes given in Section 3.3 by appending WithFixedRepresentatives
.
generated by GAPDoc2HTML