ResClasses 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.
‣ ResidueClassWithFixedRepresentative( R, m, r ) | ( function ) |
‣ ResidueClassWithFixedRepresentative( m, r ) | ( function ) |
Returns: the residue class r mod m of the ring R, with the fixed representative r.
If the argument R is omitted, it defaults to Integers. Residue classes with fixed representatives have the property IsResidueClassWithFixedRepresentative. The fixed representative r can be retrieved by the operation Residue, and the modulus m can be retrieved by the operation Modulus.
gap> ResidueClassWithFixedRepresentative(Integers,2,1); [1/2]
‣ UnionOfResidueClassesWithFixedReps( R, classes ) | ( function ) |
‣ UnionOfResidueClassesWithFixedReps( 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. Their first entries -- the moduli -- must be nonzero. If the argument R is omitted, it defaults to Integers.
gap> UnionOfResidueClassesWithFixedReps(Integers,[[2,4],[3,9]]); [4/2] U [9/3]
There is a method for the operation Modulus which returns the lcm of the moduli of the residue classes forming such a union. Further there is an operation Classes for retrieving the list of classes which has been passed as an argument to UnionOfResidueClassesWithFixedReps. The operation AsListOfClasses does the same, except that the returned list contains residue classes instead of pairs [modulus,residue]. There are methods for Print, String and Display available for unions of residue classes with fixed representatives.
‣ AllResidueClassesWithFixedRepsModulo( R, m ) | ( function ) |
‣ AllResidueClassesWithFixedRepsModulo( 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, cf. the documentation of DefaultRing in the GAP reference manual. The representatives are the same as those chosen by the operation mod. See also AllResidueClassesModulo (1.1-3).
gap> AllResidueClassesWithFixedRepsModulo(4); [ [0/4], [1/4], [2/4], [3/4] ]
Throughout this chapter, the argument R denotes the underlying ring, and the arguments U, U1 and U2 denote unions of residue classes of R with fixed representatives.
Unions of residue classes with fixed representatives are multisets. Elements and residue classes can be contained with multiplicities:
‣ Multiplicity( x, U ) | ( method ) |
‣ Multiplicity( cl, U ) | ( method ) |
Returns: the multiplicity of x in U regarded as a multiset of ring elements, resp. the multiplicity of the residue class cl in U regarded as a multiset of residue classes.
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
Let U be a union of residue classes with fixed representatives. The multiset U can have an attribute Density which denotes its natural density as a multiset, i.e. elements with multiplicity k count k-fold. The multiset U has the property IsOverlappingFree if it consists of pairwise disjoint residue classes. The set-theoretic union of the residue classes forming U can be determined by the operation AsOrdinaryUnionOfResidueClasses. The object returned by this operation is an "ordinary" residue class union as described in Chapter 1.
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 \ 1(6) U 5(6) gap> Density(last); 2/3
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 + and - available for computing the multiset of sums u + x, u ∈ U, the multiset of differences u - x resp. x - u, u ∈ U and the multiset of the additive inverses of the elements of U. Further there are methods for * and / available for computing the multiset of products x ⋅ u, u ∈ U and the multiset of quotients u/x, u ∈ U. The division method requires all elements of U to be divisible by x. If the underlying ring is the ring of integers, scalar multiplication and division leave δ invariant (→ Delta (2.3-1)).
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]
‣ Union( U1, U2 ) | ( method ) |
Returns: the union of U1 and U2.
The multiplicity of any ring element or residue class in the union is the sum of its multiplicities in the arguments. It holds that Delta(Union(U1,U2)) = Delta(U1) + Delta(U2). (→ Delta (2.3-1)).
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]
‣ 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> 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)); []
‣ Difference( U1, U2 ) | ( method ) |
Returns: the difference of U1 and U2.
The multiplicity of any residue class in the difference is its multiplicity in U1 minus its multiplicity in U2, 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 Delta(Difference(U1,U2)) = Delta(U1) - Delta(U2). (→ Delta (2.3-1)).
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]
‣ Delta( U ) | ( attribute ) |
Returns: the value of the invariant δ of the residue class union U.
For a residue class [r/m] with fixed representative we set δ([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 ρ which is defined by e^δ(U) π i. The corresponding attribute is called Rho.
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
‣ 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 ℤ into k parts is defined by [r/km] ∪ [(r+m)/km] ∪ dots ∪ [(r+(k-1)m)/km]. This definition is extended in the obvious way to unions of residue classes.
If the argument k is zero, the method performs a simplification of U by joining appropriate residue classes, if this is possible.
In any case the value of Delta(U) is invariant under this operation (→ Delta (2.3-1)).
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]
The names of the categories of unions of residue classes with fixed representatives are IsUnionOfResidueClassesOf[Z|Z_pi|ZorZ_pi|GFqx]WithFixedRepresentatives.
generated by GAPDoc2HTML