% generated by GAPDoc2LaTeX from XML source (Frank Luebeck)
\documentclass[11pt]{report}
\usepackage{a4wide}
\sloppy
\pagestyle{myheadings}
\usepackage{amssymb}
\usepackage[latin1]{inputenc}
\usepackage{makeidx}
\makeindex
\usepackage{color}
\definecolor{DarkOlive}{rgb}{0.1047,0.2412,0.0064}
\definecolor{FireBrick}{rgb}{0.5812,0.0074,0.0083}
\definecolor{RoyalBlue}{rgb}{0.0236,0.0894,0.6179}
\definecolor{RoyalGreen}{rgb}{0.0236,0.6179,0.0894}
\definecolor{RoyalRed}{rgb}{0.6179,0.0236,0.0894}
\definecolor{LightBlue}{rgb}{0.8544,0.9511,1.0000}
\definecolor{Black}{rgb}{0.0,0.0,0.0}
\definecolor{FuncColor}{rgb}{1.0,0.0,0.0}
%% strange name because of pdflatex bug:
\definecolor{Chapter }{rgb}{0.0,0.0,1.0}

\usepackage{fancyvrb}

\usepackage{pslatex}

\usepackage[
        a4paper=true,bookmarks=false,pdftitle={Written with GAPDoc},
        pdfcreator={LaTeX with hyperref package / GAPDoc},
        colorlinks=true,backref=page,breaklinks=true,linkcolor=RoyalBlue,
        citecolor=RoyalGreen,filecolor=RoyalRed,
        urlcolor=RoyalRed,pagecolor=RoyalBlue]{hyperref}

% write page numbers to a .pnr log file for online help
\newwrite\pagenrlog
\immediate\openout\pagenrlog =\jobname.pnr
\immediate\write\pagenrlog{PAGENRS := [}
\newcommand{\logpage}[1]{\protect\write\pagenrlog{#1, \thepage,}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\F}{\mathbb{F}}

\newcommand{\GAP}{\textsf{GAP}}

\newsavebox{\backslashbox}
\sbox{\backslashbox}{\texttt{\symbol{92}}}
\newcommand{\bs}{\usebox{\backslashbox}}

\begin{document}

\logpage{[ 0, 0, 0 ]}
\begin{titlepage}
\begin{center}{\Huge \textbf{ResClasses}}\\[1cm]
\hypersetup{pdftitle=ResClasses}
\markright{\scriptsize \mbox{}\hfill ResClasses \hfill\mbox{}}
{\Large \textbf{ Computations with Residue Classes and their Set-Theoretic Unions }}\\[1cm]
{ ( Version 2.1.2 ) }\\[1cm]
{January 12, 2006}\\[1cm]
\mbox{}\\[2cm]
{\large \textbf{ Stefan Kohl    }}\\
\hypersetup{pdfauthor= Stefan Kohl    }
\end{center}\vfill

\mbox{}\\
{\mbox{}\\
\small \noindent \textbf{ Stefan Kohl    } --- Email: \href{mailto://kohl@mathematik.uni-stuttgart.de}{\texttt{kohl@mathematik.uni-stuttgart.de}}\\
 --- Homepage: \href{http://www.cip.mathematik.uni-stuttgart.de/~kohlsn}{\texttt{http://www.cip.mathematik.uni-stuttgart.de/\~{}kohlsn}}\\
 --- Address: \begin{minipage}[t]{8cm}\noindent
 Institut für Geometrie und Topologie \\
 Universität Stuttgart \\
 70550 Stuttgart \\
 Germany \end{minipage}
}\\
\end{titlepage}

\newpage\setcounter{page}{2}
{\small 
\section*{Abstract}
\logpage{[ 0, 0, 2 ]}
 This package for \textsf{GAP} 4 (at least version 4.4) implements set-theoretic unions of residue classes of
the ring $\mathbb{Z}$ of the integers, of its semilocalisations $\Z_{(\pi)}$ at some finite set of primes $\pi$ and of the polynomial rings GF($q$)[$x$] for some prime power $q$ as \textsf{GAP} domains. 

 It provides basic functionality for computing with these sets, like forming
intersections, unions and differences. Any of this is also supported in the
case that one of the operands is a finite set of elements. The package also
implements the mentioned rings $\Z_{(\pi)}$ as \textsf{GAP} domains. }\\[1cm]
{\small 
\section*{Copyright}
\logpage{[ 0, 0, 1 ]}
 {\copyright} 2003 - 2006 by Stefan Kohl 

 This package is distributed under the same conditions as the \textsf{GAP} system. }\\[1cm]
\newpage

\def\contentsname{Contents\logpage{[ 0, 0, 3 ]}}

\tableofcontents
\newpage

        
\chapter{\textcolor{Chapter }{Preface}}\label{ch:preface}
\logpage{[ 1, 0, 0 ]}
{
  Although most functionality provided by this package is mathematically
trivial, the author thinks that having available a nice and easy-to-use
implementation of residue classes as sets which permits to form unions,
intersections and differences and which interacts smoothly with finite sets of
elements w.r.t. these operations is often useful. The functionality of this
package is used in a group theoretical context by the \textsf{RCWA} package written by the same author. 

 The introduction of unions of residue classes with fixed representatives which
are implemented in this package since version~2.0 follows a suggestion by Wolfgang~Rump. 

 I would be grateful for any bug reports, comments or suggestions.    \vfill \hfill Stefan Kohl   }

         
\chapter{\textcolor{Chapter }{Semilocalizations of the Integers}}\label{ch:Z_pi}
\logpage{[ 2, 0, 0 ]}
{
  In the following the semilocalizations $\Z_{(\pi)}$ of the ring of integers are needed as base rings for unions of residue
classes. Since these rings are not already implemented as domains in the \textsf{GAP} library, they had to be implemented in this package.  
\section{\textcolor{Chapter }{Entering semilocalizations of the integers}}\label{sec:DefiningZ_pi}
\logpage{[ 2, 1, 0 ]}
{
  

\subsection{\textcolor{Chapter }{Z{\_}pi (pi)}}
\logpage{[ 2, 1, 1 ]}\nobreak
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Z{\_}pi( pi )\index{Zpi@\texttt{Z{\_}pi}!pi}
\label{Zpi:pi}
}\hfill{\scriptsize (function)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Z{\_}pi( p )\index{Zpi@\texttt{Z{\_}pi}!pi}
\label{Zpi:pi}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 The ring $\Z_{(\pi)}$. 



 The function also accepts a single prime \mbox{\texttt{p}} instead of the one-element list \texttt{\mbox{\texttt{pi}} = [ \mbox{\texttt{p}} ]} as argument. 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  gap> R := Z_pi(2);
  Z_( 2 )
  gap> S := Z_pi([2,5,7]);
  Z_( 2, 5, 7 )
  gap> T := Z_pi([3,11]);
  Z_( 3, 11 )
  
\end{Verbatim}
 }

 

\subsection{\textcolor{Chapter }{IsZ{\_}pi (R)}}
\logpage{[ 2, 1, 2 ]}\nobreak
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsZ{\_}pi( R )\index{IsZpi@\texttt{IsZ{\_}pi}!R}
\label{IsZpi:R}
}\hfill{\scriptsize (property)}}\\
\textbf{\indent Returns:\ }
 \texttt{true} if \mbox{\texttt{R}} is a ring $\Z_{(\pi)}$ for some set of primes~$\pi$ and \texttt{false} otherwise. 

}

 

\subsection{\textcolor{Chapter }{NoninvertiblePrimes (R)}}
\logpage{[ 2, 1, 3 ]}\nobreak
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{NoninvertiblePrimes( R )\index{NoninvertiblePrimes@\texttt{NoninvertiblePrimes}!R}
\label{NoninvertiblePrimes:R}
}\hfill{\scriptsize (attribute)}}\\
\textbf{\indent Returns:\ }
 The set of noninvertible primes~\mbox{\texttt{pi}} in the semilocalization~\mbox{\texttt{R}} of the integers. 

}

 }

  
\section{\textcolor{Chapter }{Methods for semilocalizations of the integers}}\label{sec:MethodsForZ_pi}
\logpage{[ 2, 2, 0 ]}
{
  There are methods for the operations \texttt{in}, \texttt{Intersection}, \texttt{IsSubset}, \texttt{StandardAssociate}, \texttt{Gcd}, \texttt{Lcm}, \texttt{Factors} and \texttt{IsUnit} available for semilocalizations of the integers. For the documentation of
these operations, see the \textsf{GAP} reference manual. The standard associate of an element of a ring $\Z_{(\pi)}$ is defined by the product of the non-invertible prime factors of its
numerator. 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  gap> 4/7 in R;
  true
  gap> 3/2 in R;
  false
  gap> U := Intersection(R,S,T);
  Z_( 2, 3, 5, 7, 11 )
  gap> IsSubset(R,U);
  true
  gap> StandardAssociate(R,-6/7);
  2
  gap> Gcd(S,90/3,60/17,120/33);
  10
  gap> Lcm(S,90/3,60/17,120/33);
  40
  gap> Factors(R,840);
  [ 105, 2, 2, 2 ]
  gap> Factors(R,-2/3);
  [ -1/3, 2 ]
  gap> IsUnit(S,3/11);
  true
  
\end{Verbatim}
  }

  }

         
\chapter{\textcolor{Chapter }{Unions of Residue Classes}}\label{ch:UnionsOfResidueClasses}
\logpage{[ 3, 0, 0 ]}
{
   
\section{\textcolor{Chapter }{Entering residue classes and unions thereof}}\label{sec:DefiningUnionsOfResidueClasses}
\logpage{[ 3, 1, 0 ]}
{
  

\subsection{\textcolor{Chapter }{ResidueClass (R, m, r)}}
\logpage{[ 3, 1, 1 ]}\nobreak
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ResidueClass( R, m, r )\index{ResidueClass@\texttt{ResidueClass}!R, m, r}
\label{ResidueClass:R, m, r}
}\hfill{\scriptsize (function)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ResidueClass( m, r )\index{ResidueClass@\texttt{ResidueClass}!m, r}
\label{ResidueClass:m, r}
}\hfill{\scriptsize (function)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ResidueClass( r, m )\index{ResidueClass@\texttt{ResidueClass}!r, m}
\label{ResidueClass:r, m}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 In the three-argument form the residue class \mbox{\texttt{r}}~mod~\mbox{\texttt{m}} of the ring~\mbox{\texttt{R}}, and in the two-argument form the residue class \mbox{\texttt{r}}~mod~\mbox{\texttt{m}} of the integers. 



 In the two-argument case, \mbox{\texttt{r}} and \mbox{\texttt{m}} must not be negative, and \mbox{\texttt{r}} is assumed to lie in the range \texttt{[0..\mbox{\texttt{m}}-1]}. The latter is used to decide which of the two arguments is the modulus \mbox{\texttt{m}}, and which is the residue~\mbox{\texttt{r}}. 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  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]
  
\end{Verbatim}
 }

 

\subsection{\textcolor{Chapter }{IsResidueClass (obj)}}
\logpage{[ 3, 1, 2 ]}\nobreak
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsResidueClass( obj )\index{IsResidueClass@\texttt{IsResidueClass}!obj}
\label{IsResidueClass:obj}
}\hfill{\scriptsize (property)}}\\
\textbf{\indent Returns:\ }
 \texttt{true} if \mbox{\texttt{obj}} is a (single) residue class and \texttt{false} otherwise. 



 Rings are regarded as residue class 0~(mod~1). 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  gap> IsResidueClass(A);
  true
  gap> IsResidueClass(Z_pi([2,5]));
  true
  
\end{Verbatim}
 }

 

\subsection{\textcolor{Chapter }{ResidueClassUnion (R, m, r)}}
\logpage{[ 3, 1, 3 ]}\nobreak
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ResidueClassUnion( R, m, r )\index{ResidueClassUnion@\texttt{ResidueClassUnion}!R, m, r}
\label{ResidueClassUnion:R, m, r}
}\hfill{\scriptsize (function)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ResidueClassUnion( R, m, r, included, excluded )\index{ResidueClassUnion@\texttt{ResidueClassUnion}!R, m, r, included, excluded}
\label{ResidueClassUnion:R, m, r, included, excluded}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 The union of the residue classes \mbox{\texttt{r}}[$i$]~mod~\mbox{\texttt{m}} of the ring~\mbox{\texttt{R}}, plus / minus finite sets \mbox{\texttt{included}} and \mbox{\texttt{excluded}} of ring elements. 



 If the arguments \mbox{\texttt{included}} and \mbox{\texttt{excluded}} are given, they must be sets of elements of~\mbox{\texttt{R}}. 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  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 )>
  
\end{Verbatim}
 }

 

\subsection{\textcolor{Chapter }{AllResidueClassesModulo (R, m)}}
\logpage{[ 3, 1, 4 ]}\nobreak
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{AllResidueClassesModulo( R, m )\index{AllResidueClassesModulo@\texttt{AllResidueClassesModulo}!R, m}
\label{AllResidueClassesModulo:R, m}
}\hfill{\scriptsize (function)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{AllResidueClassesModulo( m )\index{AllResidueClassesModulo@\texttt{AllResidueClassesModulo}!m}
\label{AllResidueClassesModulo:m}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 A sorted list of all residue classes (mod~\mbox{\texttt{m}}) of the ring~\mbox{\texttt{R}}. 



 If the argument \mbox{\texttt{R}} is omitted it defaults to the default ring of \mbox{\texttt{m}} -- cp. the documentation of \texttt{DefaultRing} in the \textsf{GAP} reference manual. 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  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] ]
  
\end{Verbatim}
 }

 \pagebreak[4] A transversal for the set of residue classes (mod~$m$) can be obtained by the following function: 

\subsection{\textcolor{Chapter }{AllResidues (R, m)}}
\logpage{[ 3, 1, 5 ]}\nobreak
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{AllResidues( R, m )\index{AllResidues@\texttt{AllResidues}!R, m}
\label{AllResidues:R, m}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 A sorted list of all residues modulo~\mbox{\texttt{m}} in the ring~\mbox{\texttt{R}}. 



 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  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 ]
  
\end{Verbatim}
 }

 For extracting the components of a residue class union as given as arguments
in \texttt{ResidueClassUnion} (\ref{ResidueClassUnion:R, m, r}), there are operations \texttt{Modulus}, \texttt{Residues}, \texttt{IncludedElements} and \texttt{ExcludedElements}. }

  
\section{\textcolor{Chapter }{Methods for unions of residue classes}}\label{sec:MethodsForResidueClassUnions}
\logpage{[ 3, 2, 0 ]}
{
  There are methods for \texttt{Print}, \texttt{String} and \texttt{Display} which are applicable to unions of residue classes. There is a method for \texttt{in} to test whether some ring element lies in a given union of residue classes. 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  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 ] )
  
\end{Verbatim}
 There is a method for \texttt{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: 

\subsection{\textcolor{Chapter }{Union (U1, U2)}}
\logpage{[ 3, 2, 1 ]}\nobreak
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Union( U1, U2 )\index{Union@\texttt{Union}!U1, U2}
\label{Union:U1, U2}
}\hfill{\scriptsize (method)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Union( U, S )\index{Union@\texttt{Union}!U, S}
\label{Union:U, S}
}\hfill{\scriptsize (method)}}\\
\textbf{\indent Returns:\ }
 The union of two residue class unions \mbox{\texttt{U1}} and~\mbox{\texttt{U2}} resp. of the residue class union~\mbox{\texttt{U}} and the finite set~\mbox{\texttt{S}} of elements of the ring \mbox{\texttt{U}}~is defined over. 



 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  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
  
\end{Verbatim}
 }

 

\subsection{\textcolor{Chapter }{Intersection (U1, U2)}}
\logpage{[ 3, 2, 2 ]}\nobreak
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Intersection( U1, U2 )\index{Intersection@\texttt{Intersection}!U1, U2}
\label{Intersection:U1, U2}
}\hfill{\scriptsize (method)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Intersection( U, S )\index{Intersection@\texttt{Intersection}!U, S}
\label{Intersection:U, S}
}\hfill{\scriptsize (method)}}\\
\textbf{\indent Returns:\ }
 The intersection of two residue class unions \mbox{\texttt{U1}} and~\mbox{\texttt{U2}} resp. of the residue class union~\mbox{\texttt{U}} and the finite set~\mbox{\texttt{S}} of elements of the ring \mbox{\texttt{U}}~is defined over. 



 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  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 ]
  
\end{Verbatim}
 }

 

\subsection{\textcolor{Chapter }{Difference (U1, U2)}}
\logpage{[ 3, 2, 3 ]}\nobreak
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Difference( U1, U2 )\index{Difference@\texttt{Difference}!U1, U2}
\label{Difference:U1, U2}
}\hfill{\scriptsize (method)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Difference( U, S )\index{Difference@\texttt{Difference}!U, S}
\label{Difference:U, S}
}\hfill{\scriptsize (method)}}\\
\textbf{\indent Returns:\ }
 The difference of two residue class unions \mbox{\texttt{U1}} and~\mbox{\texttt{U2}} resp. of the residue class union \mbox{\texttt{U}} and the finite set~\mbox{\texttt{S}} of elements of the ring \mbox{\texttt{U}}~is defined over. 



 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  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 ]
  
\end{Verbatim}
 }

 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: 

\subsection{\textcolor{Chapter }{SplittedClass (cl, t)}}
\logpage{[ 3, 2, 4 ]}\nobreak
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{SplittedClass( cl, t )\index{SplittedClass@\texttt{SplittedClass}!cl, t}
\label{SplittedClass:cl, t}
}\hfill{\scriptsize (operation)}}\\
\textbf{\indent Returns:\ }
 A partition of the residue class \mbox{\texttt{cl}} into \mbox{\texttt{t}} residue classes with equal moduli, provided that such a partition exists.
Otherwise \texttt{fail}. 



 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  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
  
\end{Verbatim}
 }

 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: 

\subsection{\textcolor{Chapter }{AsUnionOfFewClasses (U)}}
\logpage{[ 3, 2, 5 ]}\nobreak
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{AsUnionOfFewClasses( U )\index{AsUnionOfFewClasses@\texttt{AsUnionOfFewClasses}!U}
\label{AsUnionOfFewClasses:U}
}\hfill{\scriptsize (operation)}}\\
\textbf{\indent Returns:\ }
 A set of disjoint residue classes whose union is \mbox{\texttt{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 \texttt{IncludedElements} and \texttt{ExcludedElements}. 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  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 ]
  
\end{Verbatim}
 }

 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: 

\subsection{\textcolor{Chapter }{\texttt{\symbol{92}}+ (U, x)}}
\logpage{[ 3, 2, 6 ]}\nobreak
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{\texttt{\symbol{92}}+( U, x )\index{+@\texttt{\texttt{\symbol{92}}+}!U, x}
\label{+:U, x}
}\hfill{\scriptsize (method)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{\texttt{\symbol{92}}+( x, U )\index{+@\texttt{\texttt{\symbol{92}}+}!x, U}
\label{+:x, U}
}\hfill{\scriptsize (method)}}\\
\textbf{\indent Returns:\ }
 The set of sums $u + x$, $u \in U$. 



 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  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
  
\end{Verbatim}
 }

 

\subsection{\textcolor{Chapter }{\texttt{\symbol{92}}- (U, x)}}
\logpage{[ 3, 2, 7 ]}\nobreak
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{\texttt{\symbol{92}}-( U, x )\index{-@\texttt{\texttt{\symbol{92}}-}!U, x}
\label{-:U, x}
}\hfill{\scriptsize (method)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{\texttt{\symbol{92}}-( x, U )\index{-@\texttt{\texttt{\symbol{92}}-}!x, U}
\label{-:x, U}
}\hfill{\scriptsize (method)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{\texttt{\symbol{92}}-( U )\index{-@\texttt{\texttt{\symbol{92}}-}!U}
\label{-:U}
}\hfill{\scriptsize (method)}}\\
\textbf{\indent 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$. 



 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  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]
  
\end{Verbatim}
 }

 

\subsection{\textcolor{Chapter }{\texttt{\symbol{92}}* (U, x)}}
\logpage{[ 3, 2, 8 ]}\nobreak
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{\texttt{\symbol{92}}*( U, x )\index{*@\texttt{\texttt{\symbol{92}}*}!U, x}
\label{*:U, x}
}\hfill{\scriptsize (method)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{\texttt{\symbol{92}}*( x, U )\index{*@\texttt{\texttt{\symbol{92}}*}!x, U}
\label{*:x, U}
}\hfill{\scriptsize (method)}}\\
\textbf{\indent Returns:\ }
 The set of products $x \cdot u$, $u \in U$. 



 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  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 ]
  
\end{Verbatim}
 }

 

\subsection{\textcolor{Chapter }{\texttt{\symbol{92}}/ (U, x)}}
\logpage{[ 3, 2, 9 ]}\nobreak
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{\texttt{\symbol{92}}/( U, x )\index{/@\texttt{\texttt{\symbol{92}}/}!U, x}
\label{/:U, x}
}\hfill{\scriptsize (method)}}\\
\textbf{\indent 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. 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  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
  
\end{Verbatim}
 }

 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: 

\subsection{\textcolor{Chapter }{Density (U)}}
\logpage{[ 3, 2, 10 ]}\nobreak
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Density( U )\index{Density@\texttt{Density}!U}
\label{Density:U}
}\hfill{\scriptsize (operation)}}\\
\textbf{\indent Returns:\ }
 The natural density of~\mbox{\texttt{U}} as a subset of the underlying ring. 



 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  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 ]
  
\end{Verbatim}
 }

 For looping over unions of residue classes of the integers, there are methods
for the operations \texttt{Iterator} and \texttt{NextIterator}. }

  
\section{\textcolor{Chapter }{The categories and families of unions of residue classes}}\label{sec:CategoriesOfUnionsOfResidueClasses}
\logpage{[ 3, 3, 0 ]}
{
  

\subsection{\textcolor{Chapter }{IsUnionOfResidueClasses (U)}}
\logpage{[ 3, 3, 1 ]}\nobreak
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsUnionOfResidueClasses( U )\index{IsUnionOfResidueClasses@\texttt{IsUnionOfResidueClasses}!U}
\label{IsUnionOfResidueClasses:U}
}\hfill{\scriptsize (filter)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsUnionOfResidueClassesOfZ( U )\index{IsUnionOfResidueClassesOfZ@\texttt{IsUnionOfResidueClassesOfZ}!U}
\label{IsUnionOfResidueClassesOfZ:U}
}\hfill{\scriptsize (filter)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsUnionOfResidueClassesOfZ{\_}pi( U )\index{IsUnionOfResidueClassesOfZpi@\texttt{IsUnionOfResidueClassesOfZ{\_}pi}!U}
\label{IsUnionOfResidueClassesOfZpi:U}
}\hfill{\scriptsize (filter)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsUnionOfResidueClassesOfGFqx( U )\index{IsUnionOfResidueClassesOfGFqx@\texttt{IsUnionOfResidueClassesOfGFqx}!U}
\label{IsUnionOfResidueClassesOfGFqx:U}
}\hfill{\scriptsize (filter)}}\\
\textbf{\indent Returns:\ }
 \texttt{true} if \mbox{\texttt{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 \texttt{false} otherwise. 

}

 

\subsection{\textcolor{Chapter }{ResidueClassUnionsFamily (R)}}
\logpage{[ 3, 3, 2 ]}\nobreak
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ResidueClassUnionsFamily( R )\index{ResidueClassUnionsFamily@\texttt{ResidueClassUnionsFamily}!R}
\label{ResidueClassUnionsFamily:R}
}\hfill{\scriptsize (function)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ResidueClassUnionsFamily( R, fixedreps )\index{ResidueClassUnionsFamily@\texttt{ResidueClassUnionsFamily}!R, fixedreps}
\label{ResidueClassUnionsFamily:R, fixedreps}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 The family of unions of residue classes resp. the family of unions of residue
classes with fixed representatives of the ring \mbox{\texttt{R}}, depending on whether \mbox{\texttt{fixedreps}} is present and \texttt{true}. 



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

 }

  }

         
\chapter{\textcolor{Chapter }{Unions of Residue Classes with Fixed Representatives}}\label{ch:UnionsOfResidueClassesWithFixedReps}
\logpage{[ 4, 0, 0 ]}
{
   
\section{\textcolor{Chapter }{ About unions of residue classes with fixed representatives }}\label{sec:AboutUnionsOfResidueClassesWithFixedReps}
\logpage{[ 4, 1, 0 ]}
{
  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: 
\begin{description}
\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 ``$\delta$-additivity'' ($\rightarrow$~\texttt{Delta} (\ref{Delta:U})). 
\item[{-}]  They can be viewed as \emph{multisets} of ring elements -- the residue classes in such a union are not necessarily
disjoint, and not even necessarily distinct. 
\end{description}
 Throughout this chapter, the argument \mbox{\texttt{R}} denotes the ring whose residue classes are considered, and the arguments \mbox{\texttt{U}}, \mbox{\texttt{U1}} and \mbox{\texttt{U2}} denote unions of residue classes of \mbox{\texttt{R}} with fixed representatives. 

 Some of the functionality described in this chapter makes only sense if \mbox{\texttt{R}} is the ring of integers -- in particular this holds for everything concerning
the invariant $\delta$. }

  
\section{\textcolor{Chapter }{ Entering unions of residue classes with fixed representatives }}\label{sec:DefiningUnionsOfResidueClassesWithFixedReps}
\logpage{[ 4, 2, 0 ]}
{
  

\subsection{\textcolor{Chapter }{ResidueClassWithFixedRepresentative (R, m, r)}}
\logpage{[ 4, 2, 1 ]}\nobreak
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ResidueClassWithFixedRepresentative( R, m, r )\index{ResidueClassWithFixedRepresentative@\texttt{ResidueClassWithFixedRepresentative}!R, m, r}
\label{ResidueClassWithFixedRepresentative:R, m, r}
}\hfill{\scriptsize (function)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ResidueClassWithFixedRepresentative( m, r )\index{ResidueClassWithFixedRepresentative@\texttt{ResidueClassWithFixedRepresentative}!m, r}
\label{ResidueClassWithFixedRepresentative:m, r}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 The residue class \mbox{\texttt{r}}~mod~\mbox{\texttt{m}} of the ring~\mbox{\texttt{R}}, with fixed representative~\mbox{\texttt{r}}. 



 If the argument \mbox{\texttt{R}} is omitted, it defaults to \texttt{Integers}. 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  gap> cl1 := ResidueClassWithFixedRepresentative(Integers,3,2);
  [2/3]
  gap> cl2 := ResidueClassWithFixedRepresentative(Integers,2,1);
  [1/2]
  
\end{Verbatim}
 }

 In all names of functions described in this chapter, \texttt{Representative} can be abbreviated by \texttt{Rep}. When entering a union of residue classes with fixed representative, for \emph{any} residue class in the union a representative has to be specified: 

\subsection{\textcolor{Chapter }{ResidueClassUnionWithFixedRepresentatives (R, classes)}}
\logpage{[ 4, 2, 2 ]}\nobreak
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ResidueClassUnionWithFixedRepresentatives( R, classes )\index{ResidueClassUnionWithFixedRepresentatives@\texttt{ResidueClassUnionWithFixedRepresentatives}!R, classes}
\label{ResidueClassUnionWithFixedRepresentatives:R, classes}
}\hfill{\scriptsize (function)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ResidueClassUnionWithFixedRepresentatives( classes )\index{ResidueClassUnionWithFixedRepresentatives@\texttt{ResidueClassUnionWithFixedRepresentatives}!classes}
\label{ResidueClassUnionWithFixedRepresentatives:classes}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 The union of the residue classes \mbox{\texttt{classes}}[$i$][2] mod \mbox{\texttt{classes}}[$i$][1] of the ring \mbox{\texttt{R}}, with fixed representatives \mbox{\texttt{classes}}[$i$][2]. 



 The argument \mbox{\texttt{classes}} must be a list of pairs of elements of the ring \mbox{\texttt{R}}, those first elements (the moduli) have to be non-zero. If the argument \mbox{\texttt{R}} is omitted, it defaults to \texttt{Integers}. 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  gap> U := ResidueClassUnionWithFixedRepresentatives(Integers,[[2,1],[7,4]]);
  [1/2] U [4/7]
  
\end{Verbatim}
 }

 There is a method for the operation \texttt{Modulus}, which returns the lcm of the moduli of the residue classes forming such a
union, and there is an operation \texttt{Classes} for extracting the list of classes which is passed as an argument to \texttt{ResidueClassUnionWithFixedRepresentatives}. 

\subsection{\textcolor{Chapter }{AllResidueClassesWithFixedRepresentativesModulo (R, m)}}
\logpage{[ 4, 2, 3 ]}\nobreak
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{AllResidueClassesWithFixedRepresentativesModulo( R, m )\index{AllResidueClassesWithFixedRepresentativesModulo@\texttt{AllResidueClassesWithFixedRepresentativesModulo}!R, m}
\label{AllResidueClassesWithFixedRepresentativesModulo:R, m}
}\hfill{\scriptsize (function)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{AllResidueClassesWithFixedRepresentativesModulo( m )\index{AllResidueClassesWithFixedRepresentativesModulo@\texttt{AllResidueClassesWithFixedRepresentativesModulo}!m}
\label{AllResidueClassesWithFixedRepresentativesModulo:m}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 A sorted list of all residue classes (mod~\mbox{\texttt{m}}) of the ring~\mbox{\texttt{R}}, with fixed representatives. 



 If the argument \mbox{\texttt{R}} is omitted it defaults to the default ring of \mbox{\texttt{m}} -- cp. the documentation of \texttt{DefaultRing} in the \textsf{GAP} reference manual. The representatives are the same as those chosen by the
operation \texttt{mod}. See also \texttt{AllResidueClassesModulo} (\ref{AllResidueClassesModulo:R, m}). 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  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] ]
  
\end{Verbatim}
 }

 }

  
\section{\textcolor{Chapter }{ Methods for unions of residue classes with fixed representatives }}\label{sec:MethodsForResidueClassUnions}
\logpage{[ 4, 3, 0 ]}
{
  There are methods for \texttt{Print}, \texttt{String} and \texttt{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: 

\subsection{\textcolor{Chapter }{Multiplicity (x, U)}}
\logpage{[ 4, 3, 1 ]}\nobreak
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Multiplicity( x, U )\index{Multiplicity@\texttt{Multiplicity}!x, U}
\label{Multiplicity:x, U}
}\hfill{\scriptsize (method)}}\\
\textbf{\indent Returns:\ }
 The multiplicity of \mbox{\texttt{x}} in~\mbox{\texttt{U}} regarded as a multiset of ring elements. 



 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  gap> List([1,2,11],n->Multiplicity(n,U));
  [ 1, 0, 2 ]
  
\end{Verbatim}
 }

 

\subsection{\textcolor{Chapter }{IsOverlappingFree (U)}}
\logpage{[ 4, 3, 2 ]}\nobreak
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsOverlappingFree( U )\index{IsOverlappingFree@\texttt{IsOverlappingFree}!U}
\label{IsOverlappingFree:U}
}\hfill{\scriptsize (property)}}\\
\textbf{\indent Returns:\ }
 \texttt{true} if the residue classes in~\mbox{\texttt{U}} are pairwisely disjoint and \texttt{false} otherwise. 



 We call a residue class union~\mbox{\texttt{U}} with fixed representatives \emph{overlapping free} if and only if it consists of pairwisely disjoint residue classes. 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  gap> IsOverlappingFree(cl1);
  true
  gap> IsOverlappingFree(U);
  false
  
\end{Verbatim}
 }

 

\subsection{\textcolor{Chapter }{AsOrdinaryUnionOfResidueClasses (U)}}
\logpage{[ 4, 3, 3 ]}\nobreak
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{AsOrdinaryUnionOfResidueClasses( U )\index{AsOrdinaryUnionOfResidueClasses@\texttt{AsOrdinaryUnionOfResidueClasses}!U}
\label{AsOrdinaryUnionOfResidueClasses:U}
}\hfill{\scriptsize (method)}}\\
\textbf{\indent Returns:\ }
 The set-theoretic union of the residue classes in~\mbox{\texttt{U}}. 



 The returned object is an ordinary residue class union without fixed
representatives as described in Chapter~\ref{ch:UnionsOfResidueClasses} which behaves like a subset of the underlying ring. 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  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 ]
  
\end{Verbatim}
 }

 

\subsection{\textcolor{Chapter }{\texttt{\symbol{92}}in (cl, U)}}
\logpage{[ 4, 3, 4 ]}\nobreak
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{\texttt{\symbol{92}}in( cl, U )\index{in@\texttt{\texttt{\symbol{92}}in}!cl, U}
\label{in:cl, U}
}\hfill{\scriptsize (method)}}\\
\textbf{\indent Returns:\ }
 \texttt{true} if the residue class \mbox{\texttt{cl}} with a fixed representative is an element of~\mbox{\texttt{U}} and \texttt{false} otherwise. 



 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  gap> cl1 in U;
  false
  gap> cl2 in U;
  true
  
\end{Verbatim}
 }

 

\subsection{\textcolor{Chapter }{AsListOfClasses (U)}}
\logpage{[ 4, 3, 5 ]}\nobreak
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{AsListOfClasses( U )\index{AsListOfClasses@\texttt{AsListOfClasses}!U}
\label{AsListOfClasses:U}
}\hfill{\scriptsize (method)}}\\
\textbf{\indent Returns:\ }
 The sorted list of the residue classes in~\mbox{\texttt{U}}. 



 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  gap> AsListOfClasses(U);
  [ [1/2], [4/7] ]
  
\end{Verbatim}
 }

 

\subsection{\textcolor{Chapter }{IsSubset (U1, U2)}}
\logpage{[ 4, 3, 6 ]}\nobreak
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsSubset( U1, U2 )\index{IsSubset@\texttt{IsSubset}!U1, U2}
\label{IsSubset:U1, U2}
}\hfill{\scriptsize (method)}}\\
\textbf{\indent Returns:\ }
 \texttt{true} if \mbox{\texttt{U2}} is a subset of \mbox{\texttt{U1}} and \texttt{false} otherwise. 



 We say that \mbox{\texttt{U2}} is a subset of \mbox{\texttt{U1}} if the multiplicity of any residue class~$[r/m]$ in \mbox{\texttt{U1}} is greater than or equal to its multiplicity in~\mbox{\texttt{U2}}. 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  gap> IsSubset(U,cl1);
  false
  gap> IsSubset(U,cl2);
  true
  
\end{Verbatim}
 }

 

\subsection{\textcolor{Chapter }{Density (U)}}
\logpage{[ 4, 3, 7 ]}\nobreak
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Density( U )\index{Density@\texttt{Density}!U}
\label{Density:U}
}\hfill{\scriptsize (operation)}}\\
\textbf{\indent Returns:\ }
 The natural density of \mbox{\texttt{U}} as a multiset (elements with multiplicity~$k$ count $k$-fold). 



 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  gap> Density(U);
  9/14
  gap> 1/2+1/7;
  9/14
  
\end{Verbatim}
 }

 

\subsection{\textcolor{Chapter }{Union (U1, U2)}}
\logpage{[ 4, 3, 8 ]}\nobreak
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Union( U1, U2 )\index{Union@\texttt{Union}!U1, U2}
\label{Union:U1, U2}
}\hfill{\scriptsize (method)}}\\
\textbf{\indent Returns:\ }
 The union of \mbox{\texttt{U1}} and~\mbox{\texttt{U2}}. 



 It holds \texttt{Delta(Union(\mbox{\texttt{U1}},\mbox{\texttt{U2}})) = Delta(\mbox{\texttt{U1}}) + Delta(\mbox{\texttt{U2}})}. ($\rightarrow$~\texttt{Delta} (\ref{Delta:U})). 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  gap> Union(U,cl1);
  [1/2] U [2/3] U [4/7]
  
\end{Verbatim}
 }

 

\subsection{\textcolor{Chapter }{Intersection (U1, U2)}}
\logpage{[ 4, 3, 9 ]}\nobreak
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Intersection( U1, U2 )\index{Intersection@\texttt{Intersection}!U1, U2}
\label{Intersection:U1, U2}
}\hfill{\scriptsize (method)}}\\
\textbf{\indent Returns:\ }
 The intersection of \mbox{\texttt{U1}} and~\mbox{\texttt{U2}}. 



 The multiplicity of any residue class in the intersection is the minimum of
its multiplicities in the arguments. 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  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]
  
\end{Verbatim}
 }

 

\subsection{\textcolor{Chapter }{Difference (U1, U2)}}
\logpage{[ 4, 3, 10 ]}\nobreak
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Difference( U1, U2 )\index{Difference@\texttt{Difference}!U1, U2}
\label{Difference:U1, U2}
}\hfill{\scriptsize (method)}}\\
\textbf{\indent Returns:\ }
 The difference of \mbox{\texttt{U1}} and~\mbox{\texttt{U2}}. 



 It holds \texttt{Delta(Difference(\mbox{\texttt{U1}},\mbox{\texttt{U2}})) = Delta(\mbox{\texttt{U1}}) - Delta(\mbox{\texttt{U2}})}. ($\rightarrow$~\texttt{Delta} (\ref{Delta:U})). 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]$. 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  gap> Difference(U,cl1);
  [1/2] U [1/3] U [4/7]
  gap> Difference(U,cl2);
  [4/7]
  
\end{Verbatim}
 }

 Throughout the rest of this section, \mbox{\texttt{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''. 

\subsection{\textcolor{Chapter }{\texttt{\symbol{92}}+ (U, x)}}
\logpage{[ 4, 3, 11 ]}\nobreak
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{\texttt{\symbol{92}}+( U, x )\index{+@\texttt{\texttt{\symbol{92}}+}!U, x}
\label{+:U, x}
}\hfill{\scriptsize (method)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{\texttt{\symbol{92}}+( x, U )\index{+@\texttt{\texttt{\symbol{92}}+}!x, U}
\label{+:x, U}
}\hfill{\scriptsize (method)}}\\
\textbf{\indent Returns:\ }
 The multiset of sums $u + x$, $u \in U$. 



 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  gap> cl1 + 1;
  [3/3]
  gap> U+23;
  [24/2] U [27/7]
  
\end{Verbatim}
 }

 

\subsection{\textcolor{Chapter }{\texttt{\symbol{92}}- (U, x)}}
\logpage{[ 4, 3, 12 ]}\nobreak
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{\texttt{\symbol{92}}-( U, x )\index{-@\texttt{\texttt{\symbol{92}}-}!U, x}
\label{-:U, x}
}\hfill{\scriptsize (method)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{\texttt{\symbol{92}}-( x, U )\index{-@\texttt{\texttt{\symbol{92}}-}!x, U}
\label{-:x, U}
}\hfill{\scriptsize (method)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{\texttt{\symbol{92}}-( U )\index{-@\texttt{\texttt{\symbol{92}}-}!U}
\label{-:U}
}\hfill{\scriptsize (method)}}\\
\textbf{\indent 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$. 



 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  gap> cl2 - 1;
  [0/2]
  gap> U - 17;
  [-16/2] U [-13/7]
  
\end{Verbatim}
 }

 

\subsection{\textcolor{Chapter }{\texttt{\symbol{92}}* (U, x)}}
\logpage{[ 4, 3, 13 ]}\nobreak
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{\texttt{\symbol{92}}*( U, x )\index{*@\texttt{\texttt{\symbol{92}}*}!U, x}
\label{*:U, x}
}\hfill{\scriptsize (method)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{\texttt{\symbol{92}}*( x, U )\index{*@\texttt{\texttt{\symbol{92}}*}!x, U}
\label{*:x, U}
}\hfill{\scriptsize (method)}}\\
\textbf{\indent Returns:\ }
 The multiset of products $x \cdot u$, $u \in U$. 



 Scalar multiplication leaves $\delta$ invariant ($\rightarrow$~\texttt{Delta} (\ref{Delta:U})). 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  gap> 3*cl1;
  [6/9]
  gap> 7*U;
  [7/14] U [28/49]
  
\end{Verbatim}
 }

 

\subsection{\textcolor{Chapter }{\texttt{\symbol{92}}/ (U, x)}}
\logpage{[ 4, 3, 14 ]}\nobreak
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{\texttt{\symbol{92}}/( U, x )\index{/@\texttt{\texttt{\symbol{92}}/}!U, x}
\label{/:U, x}
}\hfill{\scriptsize (method)}}\\
\textbf{\indent Returns:\ }
 The multiset of quotients $u/x$, $u \in U$. 



 Scalar division leaves $\delta$ invariant ($\rightarrow$~\texttt{Delta} (\ref{Delta:U})). If not all elements of all residue classes in \mbox{\texttt{U}} are divisible by~\mbox{\texttt{x}}, the method gives up. 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  gap> (2*cl1+2)/3;
  [2/2]
  
\end{Verbatim}
 }

 }

 \pagebreak[4]  
\section{\textcolor{Chapter }{ The invariant Delta }}\label{sec:WhereRepsComeIntoPlay}
\logpage{[ 4, 4, 0 ]}
{
  

\subsection{\textcolor{Chapter }{RepresentativeStabilizingRefinement (U, k)}}
\logpage{[ 4, 4, 1 ]}\nobreak
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{RepresentativeStabilizingRefinement( U, k )\index{RepresentativeStabilizingRefinement@\texttt{RepresentativeStabilizingRefinement}!U, k}
\label{RepresentativeStabilizingRefinement:U, k}
}\hfill{\scriptsize (method)}}\\
\textbf{\indent Returns:\ }
 The representative stabilizing refinement of \mbox{\texttt{U}} into $k$~parts. 



 The \emph{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 \mbox{\texttt{U}} by joining appropriate residue classes if the argument \mbox{\texttt{k}} is zero. 

 In any case the value of \texttt{Delta(\mbox{\texttt{U}})} is invariant under this operation ($\rightarrow$~\texttt{Delta} (\ref{Delta:U})). 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  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]
  
\end{Verbatim}
 }

 

\subsection{\textcolor{Chapter }{Delta (U)}}
\logpage{[ 4, 4, 2 ]}\nobreak
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Delta( U )\index{Delta@\texttt{Delta}!U}
\label{Delta:U}
}\hfill{\scriptsize (attribute)}}\\
\textbf{\indent Returns:\ }
 The value of the invariant $\delta$ of the residue class union~\mbox{\texttt{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). 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  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
  
\end{Verbatim}
 }

 

\subsection{\textcolor{Chapter }{Rho (U)}}
\logpage{[ 4, 4, 3 ]}\nobreak
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Rho( U )\index{Rho@\texttt{Rho}!U}
\label{Rho:U}
}\hfill{\scriptsize (attribute)}}\\
\textbf{\indent Returns:\ }
 The value of the invariant $\rho$ of the residue class union~\mbox{\texttt{U}}. 



 For a union $U \subseteq \Z$ of finitely many residue classes, we set $\rho(U) := e^{\pi i \delta(U)}$. }

 }

  
\section{\textcolor{Chapter }{ The categories of unions of residue classes with fixed rep's }}\label{sec:CategoriesOfUnionsOfResidueClassesWithFixedReps}
\logpage{[ 4, 5, 0 ]}
{
  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~\ref{sec:CategoriesOfUnionsOfResidueClasses} by appending \texttt{WithFixedRepresentatives}. }

  }

         
\chapter{\textcolor{Chapter }{Installation and auxiliary functions}}\label{ch:InstallationAndAuxiliaryFunctions}
\logpage{[ 5, 0, 0 ]}
{
   
\section{\textcolor{Chapter }{Installation}}\label{sec:Installation}
\logpage{[ 5, 1, 0 ]}
{
  Like any other \textsf{GAP} package, \textsf{ResClasses} must be installed in the \texttt{pkg} subdirectory of the \textsf{GAP} distribution. This is done by extracting the distribution file in this
directory. By default, the package \textsf{ResClasses} is autoloaded, otherwise you can load it via \texttt{LoadPackage( "resclasses" );}. The \textsf{ResClasses} Package needs at least version 4.4 of \textsf{GAP}, is completely written in the \textsf{GAP} language and does neither contain nor require external binaries. For the
documentation the package \textsf{GAPDoc} \cite{GAPDoc} is needed. }

  
\section{\textcolor{Chapter }{Building the manual}}\label{sec:BuildingTheManual}
\logpage{[ 5, 2, 0 ]}
{
  

\subsection{\textcolor{Chapter }{ResClassesBuildManual}}
\logpage{[ 5, 2, 1 ]}\nobreak
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ResClassesBuildManual(  )\index{ResClassesBuildManual@\texttt{ResClassesBuildManual}}
\label{ResClassesBuildManual}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 Nothing. 



 This function builds the manual of the \textsf{ResClasses} package in the file formats {\LaTeX}, DVI, Postscript, PDF, HTML and ASCII text. This is done using the \textsf{GAPDoc} package by Frank Lübeck and Max Neunhöffer. }

 }

  
\section{\textcolor{Chapter }{The testing routine}}\label{sec:TheTestingRoutine}
\logpage{[ 5, 3, 0 ]}
{
  

\subsection{\textcolor{Chapter }{ResClassesTest}}
\logpage{[ 5, 3, 1 ]}\nobreak
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ResClassesTest(  )\index{ResClassesTest@\texttt{ResClassesTest}}
\label{ResClassesTest}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 Nothing. 



 Performs tests of the \textsf{ResClasses} package. This function makes use of an adaptation of the test file \texttt{tst/testall.g} of the \textsf{GAP} library to this package. }

 }

  
\section{\textcolor{Chapter }{Changing the viewing format for residue class unions}}\label{sec:ChangingTheClassUnionViewingFormat}
\logpage{[ 5, 4, 0 ]}
{
  

\subsection{\textcolor{Chapter }{ResidueClassUnionViewingFormat (format)}}
\logpage{[ 5, 4, 1 ]}\nobreak
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ResidueClassUnionViewingFormat( format )\index{ResidueClassUnionViewingFormat@\texttt{ResidueClassUnionViewingFormat}!format}
\label{ResidueClassUnionViewingFormat:format}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 Nothing. 



 Switches between a longer and more descriptive (\mbox{\texttt{format}} = \texttt{"long"}) and a shorter and less bulky (\mbox{\texttt{format}} = \texttt{"short"}) viewing format for unions of residue classes. 

 The former is the default and should be used when not many residue classes
have to be displayed or residue classes of different rings are used, but the
latter is usually preferable if it is always clear which the base ring is and
if the printed representation of many residue classes should fit on one
screen. 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  gap> ResidueClassUnionViewingFormat("short");
  gap> ResidueClassUnion(Integers,12,[1,4,5,7,10,11]);
  1(3) U 5(6)
  gap> ResidueClassUnionViewingFormat("long");
  gap> ResidueClassUnion(Integers,12,[1,4,5,7,10,11]);
  Union of the residue classes 1(3) and 5(6) of Z
  
\end{Verbatim}
 }

  }

  }

  \def\bibname{References\logpage{[ "Bib", 0, 0 ]}}

\bibliographystyle{alpha}
\bibliography{resclasses.bib}

\def\indexname{Index\logpage{[ "Ind", 0, 0 ]}}


\printindex

\newpage
\immediate\write\pagenrlog{["End"], \arabic{page}];}
\immediate\closeout\pagenrlog
\end{document}
