Goto Chapter: | Top | 1 | 2 | 3 | 4 | 5 | Bib | Ind

### 3. Unions of Residue Classes

#### 3.1 Entering residue classes and unions thereof

##### 3.1-1 ResidueClass

`> ResidueClass`( R, m, r ) | ( function )

`> ResidueClass`( m, r ) | ( function )

`> ResidueClass`( r, m ) | ( function )

Returns: In the three-argument form the residue class r mod m of the ring R, and in the two-argument form the residue class r mod m of the integers.

In the two-argument case, r and m must not be negative, and r is assumed to lie in the range `[0..m-1]`. The latter is used to decide which of the two arguments is the modulus m, and which is the residue r.

    gap> A := ResidueClass(2,3);
    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> R := PolynomialRing(GF(7),1);; 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]

##### 3.1-2 IsResidueClass

`> IsResidueClass`( obj ) | ( property )

Returns: `true` if obj is a (single) residue class and `false` otherwise.

Rings are regarded as residue class 0 (mod 1).

    gap> IsResidueClass(A);
    true
    gap> IsResidueClass(Z_pi([2,5]));
    true

##### 3.1-3 ResidueClassUnion

`> ResidueClassUnion`( R, m, r ) | ( function )

`> ResidueClassUnion`( R, m, r, included, excluded ) | ( function )

Returns: The union of the residue classes r[i] mod m of the ring R, plus / minus finite sets included and excluded of ring elements.

If the arguments included and excluded are given, they must be sets of elements of R.

    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 )>

##### 3.1-4 AllResidueClassesModulo

`> AllResidueClassesModulo`( R, m ) | ( function )

`> AllResidueClassesModulo`( m ) | ( function )

Returns: A sorted list of all residue classes (mod m) of the ring R.

If the argument R is omitted it defaults to the default ring of m -- cp. the documentation of `DefaultRing` in the GAP reference manual.

    gap> AllResidueClassesModulo(3);
    [ The residue class 0(3) of Z, The residue class 1(3) of Z,
      The residue class 2(3) of Z ]
    gap> AllResidueClassesModulo(Z_pi(2),4);
    [ The residue class 0(4) of Z_( 2 ), The residue class 1(4) of Z_( 2 ),
      The residue class 2(4) of Z_( 2 ), The residue class 3(4) of Z_( 2 ) ]
    gap> AllResidueClassesModulo(R,x);
    [ The residue class 0*Z(7) ( mod x ) of GF(7)[x],
      The residue class Z(7)^0 ( mod x ) of GF(7)[x],
      The residue class Z(7) ( mod x ) of GF(7)[x],
      The residue class Z(7)^2 ( mod x ) of GF(7)[x],
      The residue class -Z(7)^0 ( mod x ) of GF(7)[x],
      The residue class Z(7)^4 ( mod x ) of GF(7)[x],
      The residue class Z(7)^5 ( mod x ) of GF(7)[x] ]

A transversal for the set of residue classes (mod m) can be obtained by the following function:

##### 3.1-5 AllResidues

`> AllResidues`( R, m ) | ( function )

Returns: A sorted list of all residues modulo m in the ring R.

    gap> AllResidues(Integers,6);
    [ 0 .. 5 ]
    gap> AllResidues(Z_pi([3,5,7]),700);
    [ 0 .. 174 ]
    gap> x := Indeterminate(GF(2),1);; SetName(x,"x");;
    gap> R := PolynomialRing(GF(2),1); e := One(R);; z := Zero(R);;
    GF(2)[x]
    gap> AllResidues(R,x^4+x^2);
    [ 0*Z(2), Z(2)^0, x, x+Z(2)^0, x^2, x^2+Z(2)^0, x^2+x, x^2+x+Z(2)^0, x^3,
      x^3+Z(2)^0, x^3+x, x^3+x+Z(2)^0, x^3+x^2, x^3+x^2+Z(2)^0, x^3+x^2+x,
      x^3+x^2+x+Z(2)^0 ]

For extracting the components of a residue class union as given as arguments in `ResidueClassUnion` (3.1-3), there are operations `Modulus`, `Residues`, `IncludedElements` and `ExcludedElements`.

#### 3.2 Methods for unions of residue classes

There are methods for `Print`, `String` and `Display` which are applicable to unions of residue classes. There is a method for `in` to test whether some ring element lies in a given union of residue classes.

    gap> 20 in A;
    true
    gap> 1/3 in B;
    true
    gap> x in G;
    false
    gap> Perform( [ C, F, H ], function( U ) Print(U,"\n"); end );
    ResidueClassUnion( GF(7)[x], x+Z(7)^0, [ Z(7) ] )
    ResidueClassUnion( Integers, 5, [ 1, 2 ], [ 3, 8 ], [ -4, 1 ] )
    ResidueClassUnion( Z_( 2, 3 ), 8, [ 3, 5 ] )

There is a method for `IsSubset` available for unions of residue classes. As described in detail in the sequel, there are methods for computing set-theoretic unions, intersections and differences of unions of residue classes:

##### 3.2-1 Union

`> Union`( U1, U2 ) | ( method )

`> Union`( U, S ) | ( method )

Returns: The union of two residue class unions U1 and U2 resp. of the residue class union U and the finite set S of elements of the ring U is defined over.

    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

##### 3.2-2 Intersection

`> Intersection`( U1, U2 ) | ( method )

`> Intersection`( U, S ) | ( method )

Returns: The intersection of two residue class unions U1 and U2 resp. of the residue class union U and the finite set S of elements of the ring U is defined over.

    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 ]

##### 3.2-3 Difference

`> Difference`( U1, U2 ) | ( method )

`> Difference`( U, S ) | ( method )

Returns: The difference of two residue class unions U1 and U2 resp. of the residue class union U and the finite set S of elements of the ring U is defined over.

    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 ]

If the underlying ring has a residue class ring of some cardinality t, then a residue class can be written as a disjoint union of t residue classes with equal moduli:

##### 3.2-4 SplittedClass

`> SplittedClass`( cl, t ) | ( operation )

Returns: A partition of the residue class cl into t residue classes with equal moduli, provided that such a partition exists. Otherwise `fail`.

    gap> SplittedClass(ResidueClass(2,3),5);
    [ The residue class 2(15) of Z, The residue class 5(15) of Z,
      The residue class 8(15) of Z, The residue class 11(15) of Z,
      The residue class 14(15) of Z ]
    gap> SplittedClass(ResidueClass(Z_pi([2,3]),3,2),2);
    [ The residue class 2(6) of Z_( 2, 3 ), The residue class 5(6) of Z_( 2, 3 ) ]
    gap> SplittedClass(ResidueClass(Z_pi([2,3]),3,2),5);
    fail

Sometimes one wants to know a partition of a given union of residue classes into "few" residue classes. Ensuring to get always a partition of minimal possible length seems to be algorithmically difficult. The following yields usually "reasonably short" partitions:

##### 3.2-5 AsUnionOfFewClasses

`> AsUnionOfFewClasses`( U ) | ( operation )

Returns: A set of disjoint residue classes whose union is U.

As the name of the operation suggests, it is taken care that the number of residue classes in the returned list is kept "reasonably small". It is not necessarily minimal. No care is taken of `IncludedElements` and `ExcludedElements`.

    gap> AsUnionOfFewClasses(K);
    [ The residue class 1(5) of Z, The residue class 2(5) of Z,
      The residue class 3(5) of Z, The residue class 4(5) of Z,
      The residue class 5(30) of Z, The residue class 25(30) of Z ]

One can add / subtract a constant to / from all elements of a union of residue classes, and one can multiply or divide the elements by a constant:

##### 3.2-6 \+

`> \+`( U, x ) | ( method )

`> \+`( x, U ) | ( method )

Returns: The set of sums u + x, u in U.

    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

##### 3.2-7 \-

`> \-`( U, x ) | ( method )

`> \-`( x, U ) | ( method )

`> \-`( U ) | ( method )

Returns: The set 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> 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]

##### 3.2-8 \*

`> \*`( U, x ) | ( method )

`> \*`( x, U ) | ( method )

Returns: The set of products x * u, u in U.

    gap> D*17;
    Union of the residue classes 34(102) and 68(102) of Z
    gap> 2*Difference(Integers,[1,2,3]);
    (The residue class 0(2) of Z) \ [ 2, 4, 6 ]

##### 3.2-9 \/

`> \/`( U, x ) | ( method )

Returns: The set of quotients u/x, u in U.

If the result would be not a subset of the underlying ring, the method gives up.

    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

The natural density of a residue class r(m) of a ring R is defined by 1/|R/mR|, and the natural density of a union U of finitely many residue classes is defined as the sum of the densities of the elements of a partition of U into finitely many residue classes:

##### 3.2-10 Density

`> Density`( U ) | ( operation )

Returns: The natural density of U as a subset of the underlying ring.

    gap> Density(G); G;
    3/7
    <union of 3 residue classes (mod x) of GF(7)[x]> U [ 0*Z(7) ] \ [ Z(7)^0 ]
    gap> ResidueClassUnion(Integers,12,[3,5,9]);
    Union of the residue classes 3(6) and 5(12) of Z
    gap> List([last,2*last],Density);
    [ 1/4, 1/8 ]

For looping over unions of residue classes of the integers, there are methods for the operations `Iterator` and `NextIterator`.

#### 3.3 The categories and families of unions of residue classes

##### 3.3-1 IsUnionOfResidueClasses

`> IsUnionOfResidueClasses`( U ) | ( filter )

`> IsUnionOfResidueClassesOfZ`( U ) | ( filter )

`> IsUnionOfResidueClassesOfZ_pi`( U ) | ( filter )

`> IsUnionOfResidueClassesOfGFqx`( U ) | ( filter )

Returns: `true` if U is a union of residue classes, resp. a union of residue classes of the ring of integers, resp. a union of residue classes of a semilocalization of the ring of integers, resp. a union of residue classes of a polynomial ring in one variable over a finite field, and `false` otherwise.

##### 3.3-2 ResidueClassUnionsFamily

`> ResidueClassUnionsFamily`( R ) | ( function )

`> ResidueClassUnionsFamily`( R, fixedreps ) | ( function )

Returns: The family of unions of residue classes resp. the family of unions of residue classes with fixed representatives of the ring R, depending on whether fixedreps is present and `true`.

The ring R can be accessed as `UnderlyingRing(ResidueClassUnionsFamily(R))`. Unions of residue classes with fixed representatives are described in the next chapter.

Top of Book | Previous Chapter | Next Chapter

Goto Chapter: | Top | 1 | 2 | 3 | 4 | 5 | Bib | Ind

generated by GAPDoc2HTML