Quelle  main.tex   Sprache: Latech

% generated by GAPDoc2LaTeX from XML source (Frank Luebeck)
\documentclass[a4paper,11pt]{report}

\usepackage[top=37mm,bottom=37mm,left=27mm,right=27mm]{geometry}
\sloppy
\pagestyle{myheadings}
\usepackage{amssymb}
\usepackage[utf8]{inputenc}
\usepackage{makeidx}
\makeindex
\usepackage{color}
\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{linkColor}{rgb}{0.0,0.0,0.554}
\definecolor{citeColor}{rgb}{0.0,0.0,0.554}
\definecolor{fileColor}{rgb}{0.0,0.0,0.554}
\definecolor{urlColor}{rgb}{0.0,0.0,0.554}
\definecolor{promptColor}{rgb}{0.0,0.0,0.589}
\definecolor{brkpromptColor}{rgb}{0.589,0.0,0.0}
\definecolor{gapinputColor}{rgb}{0.589,0.0,0.0}
\definecolor{gapoutputColor}{rgb}{0.0,0.0,0.0}

%%  for a long time these were red and blue by default,
%%  now black, but keep variables to overwrite
\definecolor{FuncColor}{rgb}{0.0,0.0,0.0}
%% strange name because of pdflatex bug:
\definecolor{Chapter }{rgb}{0.0,0.0,0.0}
\definecolor{DarkOlive}{rgb}{0.1047,0.2412,0.0064}


\usepackage{fancyvrb}

\usepackage{mathptmx,helvet}
\usepackage[T1]{fontenc}
\usepackage{textcomp}


\usepackage[
            pdftex=true,
            bookmarks=true,        
            a4paper=true,
            pdftitle={Written with GAPDoc},
            pdfcreator={LaTeX with hyperref package / GAPDoc},
            colorlinks=true,
            backref=page,
            breaklinks=true,
            linkcolor=linkColor,
            citecolor=citeColor,
            filecolor=fileColor,
            urlcolor=urlColor,
            pdfpagemode={UseNone}, 
           ]{hyperref}

\newcommand{\maintitlesize}{\fontsize{50}{55}\selectfont}

% 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,}}
%% were never documented, give conflicts with some additional packages

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

%% nicer description environments, allows long labels
\usepackage{enumitem}
\setdescription{style=nextline}

%% depth of toc
\setcounter{tocdepth}{1}




\usepackage{amsfonts}
\usepackage{amsxtra}

\tolerance 2500
\hbadness 2500
\emergencystretch 1.5em
\hfuzz 0.3pt
\widowpenalty=10000
\clubpenalty=10000
\vfuzz \hfuzz
\raggedbottom


%% command for ColorPrompt style examples
\newcommand{\gapprompt}[1]{\color{promptColor}{\bfseries #1}}
\newcommand{\gapbrkprompt}[1]{\color{brkpromptColor}{\bfseries #1}}
\newcommand{\gapinput}[1]{\color{gapinputColor}{#1}}


\begin{document}

\logpage{[ 0, 0, 0 ]}
\begin{titlepage}
\mbox{}\vfill

\begin{center}{\maintitlesize \textbf{ RCWA \mbox{}}}\\
\vfill

\hypersetup{pdftitle= RCWA }
\markright{\scriptsize \mbox{}\hfill  RCWA  \hfill\mbox{}}
{\Huge \textbf{ Residue\texttt{\symbol{45}}Class\texttt{\symbol{45}}Wise Affine Groups \mbox{}}}\\
\vfill

{\Huge  4.8.0 \mbox{}}\\[1cm]
{ 22 September 2025 \mbox{}}\\[1cm]
\mbox{}\\[2cm]
{\Large \textbf{ Stefan Kohl\\
   \mbox{}}}\\
\hypersetup{pdfauthor= Stefan Kohl\\
   }
\end{center}\vfill

\mbox{}\\
{\mbox{}\\
\small \noindent \textbf{ Stefan Kohl\\
   }  Email: \href{mailto://sk239@st-andrews.ac.uk} {\texttt{sk239@st\texttt{\symbol{45}}andrews.ac.uk}}\\
  Homepage: \href{https://stefan-kohl.github.io/} {\texttt{https://stefan\texttt{\symbol{45}}kohl.github.io/}}}\\
\end{titlepage}

\newpage\setcounter{page}{2}
{\small 
\section*{Abstract}
\logpage{[ 0, 0, 1 ]}
      \textsf{RCWA} is a package for \textsf{GAP}{\nobreakspace}4. It provides implementations of algorithms and methods for
computing in certain infinite permutation groups acting on the set of
integers. This package can be used to investigate the following types of
groups and many more: 
\begin{itemize}
\item  Finite groups, and certain divisible torsion groups which they embed into. 
\item  Free groups of finite rank. 
\item  Free products of finitely many finite groups. 
\item  Direct products of the above groups. 
\item  Wreath products of the above groups with finite groups and
with{\nobreakspace}({\ensuremath{\mathbb Z}},+). 
\item  Subgroups of any such groups. 
\end{itemize}
 With the help of this package, the author has found a countable simple group
which is generated by involutions interchanging disjoint residue classes of
{\ensuremath{\mathbb Z}} and which all the above groups embed into
\texttt{\symbol{45}}\texttt{\symbol{45}} see{\nobreakspace}\cite{Kohl09}. 

  \mbox{}}\\[1cm]
{\small 
\section*{Copyright}
\logpage{[ 0, 0, 2 ]}
 {\copyright} 2003 \texttt{\symbol{45}} 2018 by Stefan Kohl. 

 \textsf{RCWA} is free software: you can redistribute it and/or modify it under the terms of
the GNU General Public License as published by the Free Software Foundation,
either version 2 of the License, or (at your option) any later version. 

 \textsf{RCWA} is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
PARTICULAR PURPOSE. See the GNU General Public License for more details. 

 For a copy of the GNU General Public License, see the file \texttt{GPL} in the \texttt{etc} directory of the \textsf{GAP} distribution or see \href{https://www.gnu.org/licenses/gpl.html} {\texttt{https://www.gnu.org/licenses/gpl.html}}. \vspace{-1cm} \mbox{}}\\[1cm]
{\small 
\section*{Acknowledgements}
\logpage{[ 0, 0, 3 ]}
 I am grateful to John P. McDermott for the discovery that the group discussed
in Section{\nobreakspace}\ref{sec:ThompsonsGroupV} is isomorphic to Thompson's Group V in July 2008, and to Laurent Bartholdi for
his hint on how to construct wreath products of
residue\texttt{\symbol{45}}class\texttt{\symbol{45}}wise affine groups
with{\nobreakspace}({\ensuremath{\mathbb Z}},+) in April 2006. Further, I
thank Bettina{\nobreakspace}Eick for communicating this package and for her
valuable suggestions on its manual in the time before its first public release
in April 2005. Last but not least I thank the two anonymous referees for their
constructive criticism and their helpful suggestions. \mbox{}}\\[1cm]
\newpage

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

\tableofcontents
\newpage

      
\chapter{\textcolor{Chapter }{About the RCWA Package}}\label{ch:AboutRCWA}
\logpage{[ 1, 0, 0 ]}
\hyperdef{L}{X83A8C2927FAE2C23}{}
{
 \index{Collatz conjecture@Collatz conjecture} \index{Collatz conjecture@Collatz mapping} This package permits to compute in monoids, in particular groups, whose
elements are \emph{residue\texttt{\symbol{45}}class\texttt{\symbol{45}}wise affine} mappings. Probably the widest\texttt{\symbol{45}}known occurrence of such a
mapping is in the statement of the $3n+1$ conjecture, which asserts that iterated application of the \emph{Collatz mapping} 
  
\[
  T: \ \ \mathbb{Z} \longrightarrow \mathbb{Z}, \ \ \ java.lang.NullPointerException
           n \ \longmapsto java.lang.NullPointerException
          \begin{cases}
          \frac{n}{2}    & \text{if} \ \ n \ \ \text{is even}, \\
          \frac{3n+1}{2} & \text{if} \ \ n \ \ \text{is odd}
          \end{cases}
  \]

   to any given positive integer eventually yields{\nobreakspace}1
(cf.{\nobreakspace}\cite{Lagarias06}). For definitions, see Section{\nobreakspace}\ref{sec:basicdefinitions}. 

 Presently, most research in computational group theory focuses on finite
permutation groups, matrix groups, finitely presented groups, polycyclically
presented groups and automata groups. For details, we refer to{\nobreakspace}\cite{HoltEickOBrien05}. The purpose of this package is twofold: 
\begin{itemize}
\item  On the one hand, it provides the means to deal with another large class of
groups which are accessible to computational methods, and it therefore extends
the range of groups which can be dealt with by means of computation. 
\item  On the other \texttt{\symbol{45}}\texttt{\symbol{45}} and perhaps more
importantly \texttt{\symbol{45}}\texttt{\symbol{45}}
residue\texttt{\symbol{45}}class\texttt{\symbol{45}}wise affine groups appear
to be interesting mathematical objects in their own right, and this package is
intended to serve as a tool to obtain a better understanding of their rich and
often complicated group theoretical and combinatorial structure. 
\end{itemize}
 In principle this package permits to construct and investigate all groups
which have faithful representations as
residue\texttt{\symbol{45}}class\texttt{\symbol{45}}wise affine groups. Among
many others, the following groups and their subgroups belong to this class: 
\begin{itemize}
\item  Finite groups, and certain divisible torsion groups which they embed into. 
\item  Free groups of finite rank. 
\item  Free products of finitely many finite groups. 
\item  Direct products of the above groups. 
\item  Wreath products of the above groups with finite groups and
with{\nobreakspace}({\ensuremath{\mathbb Z}},+). 
\end{itemize}
 This list permits already to conclude that there are finitely generated
residue\texttt{\symbol{45}}class\texttt{\symbol{45}}wise affine groups which
do not have finite presentations, and such with algorithmically unsolvable
membership problem. However the list is certainly by far not exhaustive, and
using this package it is easy to construct groups of types which are not
mentioned there. 

 The group CT({\ensuremath{\mathbb Z}}) which is generated by all \emph{class transpositions} of{\nobreakspace}{\ensuremath{\mathbb Z}}
\texttt{\symbol{45}}\texttt{\symbol{45}} these are involutions which
interchange two disjoint residue classes, see \texttt{ClassTransposition} (\ref{ClassTransposition:r1, m1, r2, m2}) \texttt{\symbol{45}}\texttt{\symbol{45}} is a simple group which has subgroups
of all types listed above. It is countable, but it has an uncountable series
of simple subgroups which is parametrized by the sets of odd primes. 

 Proofs of most of the results mentioned so far can be found in{\nobreakspace}\cite{Kohl09}. Descriptions of a part of the algorithms and methods which are implemented
in this package can be found in{\nobreakspace}\cite{Kohl08b}. 

 The reader might want to know what type of results one can obtain with \textsf{RCWA}. However, the answer to this is that the package can be applied in various
ways to various different problems, and it is simply not possible to say in
general what can be found out with its help. So one really cannot give a
better answer here than for the same question about \textsf{GAP} itself. The best way to get familiar with the package and its capabilities is
likely to experiment with the examples discussed in this manual and the groups
generated by 3 class transpositions from the corresponding data library. 

 Of course, sometimes this package does not provide an
out\texttt{\symbol{45}}of\texttt{\symbol{45}}the\texttt{\symbol{45}}box
solution for a given problem. But quite often it is still possible to find an
answer by an interactive trial\texttt{\symbol{45}}and\texttt{\symbol{45}}error
approach. With substantial help of this package, the author has found the
results mentioned above. Interactive sessions with this package have also led
to the development of most of the algorithms which are now implemented in it.
Just to mention one example, developing the factorization method for
residue\texttt{\symbol{45}}class\texttt{\symbol{45}}wise affine permutations
(see{\nobreakspace}\texttt{FactorizationIntoCSCRCT} (\ref{FactorizationIntoCSCRCT:for an rcwa permutation of Z})) solely by means of theory would likely have been very hard.  }

       
\chapter{\textcolor{Chapter }{Residue\texttt{\symbol{45}}Class\texttt{\symbol{45}}Wise Affine Mappings}}\label{ch:RcwaMappings}
\logpage{[ 2, 0, 0 ]}
\hyperdef{L}{X7FD73FCB8510050E}{}
{
   This chapter contains the basic definitions, and it describes how to enter
residue\texttt{\symbol{45}}class\texttt{\symbol{45}}wise affine mappings and
how to compute with them. 

 How to compute with residue\texttt{\symbol{45}}class\texttt{\symbol{45}}wise
affine groups is described in detail in the next chapter. The reader is
encouraged to look there already after having read the first few pages of this
chapter, and to look up definitions as he needs to.  
\section{\textcolor{Chapter }{Basic definitions}}\label{sec:basicdefinitions}
\logpage{[ 2, 1, 0 ]}
\hyperdef{L}{X78ED07E37FC2BD46}{}
{
  \index{rcwa mapping@rcwa mapping!definition} \index{rcwa group@rcwa group!definition} Residue\texttt{\symbol{45}}class\texttt{\symbol{45}}wise affine groups, or \emph{rcwa} groups for short, are permutation groups whose elements are bijective
residue\texttt{\symbol{45}}class\texttt{\symbol{45}}wise affine mappings. 

 A mapping $f: {\ensuremath{\mathbb Z}} \rightarrow {\ensuremath{\mathbb Z}}$ is called \emph{residue\texttt{\symbol{45}}class\texttt{\symbol{45}}wise affine}, or for short an \emph{rcwa} mapping, if there is a positive integer{\nobreakspace}$m$ such that the restrictions of{\nobreakspace}$f$ to the residue classes $r(m) \in {\ensuremath{\mathbb Z}}/m{\ensuremath{\mathbb Z}}$ are all affine, i.e. given{\nobreakspace}by 
  
\[
    f|_{r(m)}: \ r(m) \rightarrow \mathbb{Z}, \ \ java.lang.NullPointerException
    n \ \mapsto \ \frac{a_{r(m)} \cdot n + b_{r(m)}}{c_{r(m)}}
  \]

   for certain coefficients $a_{r(m)}, b_{r(m)}, c_{r(m)} \in {\ensuremath{\mathbb Z}}$ depending on{\nobreakspace}$r(m)$. \index{modulus@modulus!definition} \index{rcwa mapping@rcwa mapping!modulus} \index{multiplier@multiplier!definition} \index{rcwa mapping@rcwa mapping!multiplier} \index{divisor@divisor!definition} \index{rcwa mapping@rcwa mapping!divisor} The smallest possible $m$ is called the \emph{modulus} of{\nobreakspace}$f$. It is understood that all fractions are reduced, i.e. that $\gcd( a_{r(m)}, b_{r(m)}, c_{r(m)} ) = 1$, and that $c_{r(m)} > 0$. The lcm of the coefficients $a_{r(m)}$ is called the \emph{multiplier} of{\nobreakspace}$f$, and the lcm of the coefficients $c_{r(m)}$ is called the \emph{divisor} of{\nobreakspace}$f$. 

 It is easy to see that the
residue\texttt{\symbol{45}}class\texttt{\symbol{45}}wise affine mappings
of{\nobreakspace}{\ensuremath{\mathbb Z}} form a monoid under composition, and
that the residue\texttt{\symbol{45}}class\texttt{\symbol{45}}wise affine
permutations of{\nobreakspace}{\ensuremath{\mathbb Z}} form a countable
subgroup of Sym({\ensuremath{\mathbb Z}}). We denote the former by
Rcwa({\ensuremath{\mathbb Z}}), and the latter by RCWA({\ensuremath{\mathbb
Z}}). 

 \index{tame@tame!rcwa mapping} \index{tame@tame!rcwa group} \index{wild@wild!rcwa mapping} \index{wild@wild!rcwa group} \index{rcwa mapping@rcwa mapping!tame} \index{rcwa group@rcwa group!tame} \index{rcwa mapping@rcwa mapping!wild} \index{rcwa group@rcwa group!wild} An rcwa mapping is called \emph{tame} if the set of moduli of its powers is bounded, or equivalently if it permutes
a partition of{\nobreakspace}{\ensuremath{\mathbb Z}} into finitely many
residue classes on all of which it is affine. An rcwa group is called \emph{tame} if there is a common such partition for all of its elements, or equivalently
if the set of moduli of its elements is bounded. Rcwa mappings and
\texttt{\symbol{45}}groups which are not tame are called \emph{wild}. Tame rcwa mappings and \texttt{\symbol{45}}groups are something which one
could call the ``trivial cases'' or ``basic building blocks'', while wild rcwa groups are the objects of primary interest. 

 The definitions of residue\texttt{\symbol{45}}class\texttt{\symbol{45}}wise
affine mappings and \texttt{\symbol{45}}groups can be generalized in the
obvious way to suitable rings other than{\nobreakspace}{\ensuremath{\mathbb
Z}}. In fact, this package provides also some support for
residue\texttt{\symbol{45}}class\texttt{\symbol{45}}wise affine groups over ${\ensuremath{\mathbb Z}}^2$, over semilocalizations of{\nobreakspace}{\ensuremath{\mathbb Z}} and over
univariate polynomial rings over finite fields. The ring ${\ensuremath{\mathbb Z}}^2$ has been chosen as an example of a suitable ring which is not a principal
ideal domain, the semilocalizations of{\nobreakspace}{\ensuremath{\mathbb Z}}
have been chosen as examples of rings with only finitely many prime elements,
and the univariate polynomial rings over finite fields have been chosen as
examples of rings with nonzero characteristic. }

  
\section{\textcolor{Chapter }{Entering residue\texttt{\symbol{45}}class\texttt{\symbol{45}}wise affine
mappings}}\label{sec:EnteringRcwaMappings}
\logpage{[ 2, 2, 0 ]}
\hyperdef{L}{X86BC55648302D643}{}
{
  Entering an rcwa mapping of{\nobreakspace}{\ensuremath{\mathbb Z}} requires
giving the modulus{\nobreakspace}$m$ and the coefficients $a_{r(m)}$, $b_{r(m)}$ and{\nobreakspace}$c_{r(m)}$ for $r(m)$ running over the residue classes (mod{\nobreakspace}$m$). 

 This can be done easiest by \texttt{RcwaMapping( \mbox{\texttt{\mdseries\slshape coeffs}} )}, where \mbox{\texttt{\mdseries\slshape coeffs}} is a list of $m$ coefficient triples \texttt{coeffs[}$r+1$\texttt{]{\nobreakspace}= [}$a_{r(m)}$, $b_{r(m)}$, $c_{r(m)}$\texttt{]}, with $r$ running from 0 to{\nobreakspace}$m-1$. 

 If some coefficient $c_{r(m)}$ is zero or if images of some integers under the mapping to be defined would
not be integers, an error message is printed and a break loop is entered. For
example, the coefficient triple \texttt{[1,4,3]} is not allowed at the first position. The reason for this is that not all
integers congruent to $1 \cdot 0 + 4 = 4${\nobreakspace}mod{\nobreakspace}$m$ are divisible by{\nobreakspace}3. 

 For the general constructor for rcwa mappings, see \texttt{RcwaMapping} (\ref{RcwaMapping:by ring, modulus and list of coefficients}). 
\begin{Verbatim}[commandchars=!@A,fontsize=\small,frame=single,label=Example]
  
  !gapprompt@gap>A !gapinput@T := RcwaMapping([[1,0,2],[3,1,2]]); # The Collatz mapping.A
  <rcwa mapping of Z with modulus 2>
  !gapprompt@gap>A !gapinput@[ IsSurjective(T), IsInjective(T) ];A
  [ true, false ]
  !gapprompt@gap>A !gapinput@Display(T);A
  
  Surjective rcwa mapping of Z with modulus 2
  
          /
          | n/2      if n in 0(2)
   n |-> <  (3n+1)/2 if n in 1(2)
          |
          java.lang.NullPointerException
  
  !gapprompt@gap>A !gapinput@a := RcwaMapping([[2,0,3],[4,-1,3],[4,1,3]]);A
  <rcwa mapping of Z with modulus 3>
  !gapprompt@gap>A !gapinput@IsBijective(a);A
  true
  !gapprompt@gap>A !gapinput@Display(a); # This is Collatz' permutation:A
  
  Rcwa permutation of Z with modulus 3
  
          /
          | 2n/3     if n in 0(3)
   n |-> <  (4n-1)/3 if n in 1(3)
          | (4n+1)/3 if n in 2(3)
          java.lang.NullPointerException
  
  !gapprompt@gap>A !gapinput@Support(a);A
  Z \ [ -1, 0, 1 ]
  !gapprompt@gap>A !gapinput@Cycle(a,44);A
  [ 44, 59, 79, 105, 70, 93, 62, 83, 111, 74, 99, 66 ]
  
\end{Verbatim}
 \noindent There is computational evidence for the conjecture that any
residue\texttt{\symbol{45}}class\texttt{\symbol{45}}wise affine permutation
of{\nobreakspace}{\ensuremath{\mathbb Z}} can be factored into members of the
following three series of permutations of particularly simple structure (cf. \texttt{FactorizationIntoCSCRCT} (\ref{FactorizationIntoCSCRCT:for an rcwa permutation of Z})): 

\subsection{\textcolor{Chapter }{ClassShift (r, m)}}
\logpage{[ 2, 2, 1 ]}\nobreak
\hyperdef{L}{X86B611BD7EED62A1}{}
{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{ClassShift({\mdseries\slshape r, m})\index{ClassShift@\texttt{ClassShift}!r, m}
\label{ClassShift:r, m}
}\hfill{\scriptsize (function)}}\\
\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{ClassShift({\mdseries\slshape cl})\index{ClassShift@\texttt{ClassShift}!cl}
\label{ClassShift:cl}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 the class shift $\nu_{r(m)}$. 



 The \emph{class shift} $\nu_{r(m)}$ is the rcwa mapping of{\nobreakspace}{\ensuremath{\mathbb Z}} which maps $n \in r(m)$ to $n + m$ and which fixes ${\ensuremath{\mathbb Z}} \setminus r(m)$ pointwise. 

 In the one\texttt{\symbol{45}}argument form, the argument{\nobreakspace}\mbox{\texttt{\mdseries\slshape cl}} stands for the residue class{\nobreakspace}$r(m)$. Enclosing the argument list in list brackets is permitted. 
\begin{Verbatim}[commandchars=!@A,fontsize=\small,frame=single,label=Example]
  
  !gapprompt@gap>A !gapinput@Display(ClassShift(5,12));A
  
  Tame rcwa permutation of Z with modulus 12, of order infinity
  
          /
          | n+12 if n in 5(12)
   n |-> <  n    if n in Z \ 5(12)
          |
          java.lang.NullPointerException
  
\end{Verbatim}
 }

 

\subsection{\textcolor{Chapter }{ClassReflection (r, m)}}
\logpage{[ 2, 2, 2 ]}\nobreak
\hyperdef{L}{X7896C5417E3692B4}{}
{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{ClassReflection({\mdseries\slshape r, m})\index{ClassReflection@\texttt{ClassReflection}!r, m}
\label{ClassReflection:r, m}
}\hfill{\scriptsize (function)}}\\
\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{ClassReflection({\mdseries\slshape cl})\index{ClassReflection@\texttt{ClassReflection}!cl}
\label{ClassReflection:cl}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 the class reflection $\varsigma_{r(m)}$. 



 The \emph{class reflection} $\varsigma_{r(m)}$ is the rcwa mapping of{\nobreakspace}{\ensuremath{\mathbb Z}} which maps $n \in r(m)$ to $-n + 2r$ and which fixes ${\ensuremath{\mathbb Z}} \setminus r(m)$ pointwise, where it is understood that $0 \leq r < m$. 

 In the one\texttt{\symbol{45}}argument form, the argument{\nobreakspace}\mbox{\texttt{\mdseries\slshape cl}} stands for the residue class{\nobreakspace}$r(m)$. Enclosing the argument list in list brackets is permitted. 
\begin{Verbatim}[commandchars=!@A,fontsize=\small,frame=single,label=Example]
  
  !gapprompt@gap>A !gapinput@Display(ClassReflection(5,9));A
  
  Rcwa permutation of Z with modulus 9, of order 2
  
          /
          | -n+10 if n in 5(9)
   n |-> <  n     if n in Z \ 5(9)
          |
          java.lang.NullPointerException
  
\end{Verbatim}
 }

 \pagebreak[4] 

\subsection{\textcolor{Chapter }{ClassTransposition (r1, m1, r2, m2)}}
\logpage{[ 2, 2, 3 ]}\nobreak
\hyperdef{L}{X8716A75F7DD1C46B}{}
{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{ClassTransposition({\mdseries\slshape r1, m1, r2, m2})\index{ClassTransposition@\texttt{ClassTransposition}!r1, m1, r2, m2}
\label{ClassTransposition:r1, m1, r2, m2}
}\hfill{\scriptsize (function)}}\\
\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{ClassTransposition({\mdseries\slshape cl1, cl2})\index{ClassTransposition@\texttt{ClassTransposition}!cl1, cl2}
\label{ClassTransposition:cl1, cl2}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 the class transposition $\tau_{r_1(m_1),r_2(m_2)}$. 



 Given two disjoint residue classes $r_1(m_1)$ and $r_2(m_2)$ of the integers, the \emph{class transposition} $\tau_{r_1(m_1),r_2(m_2)}$ $\in$ RCWA({\ensuremath{\mathbb Z}}) is defined as the involution which interchanges $r_1+km_1$ and $r_2+km_2$ for any integer{\nobreakspace}$k$ and which fixes all other points. It is understood that $m_1$ and{\nobreakspace}$m_2$ are positive, that $0 \leq r_1 < m_1$ and that $0 \leq r_2 < m_2$. For a \emph{generalized class transposition}, the latter assumptions are not made. 

 The class transposition $\tau_{r_1(m_1),r_2(m_2)}$ interchanges the residue classes $r_1(m_1)$ and $r_2(m_2)$ and fixes the complement of their union pointwise. 

 \index{TransposedClasses@\texttt{TransposedClasses}!of a class transposition} In the four\texttt{\symbol{45}}argument form, the arguments \mbox{\texttt{\mdseries\slshape r1}}, \mbox{\texttt{\mdseries\slshape m1}}, \mbox{\texttt{\mdseries\slshape r2}} and{\nobreakspace}\mbox{\texttt{\mdseries\slshape m2}} stand for $r_1$, $m_1$, $r_2$ and{\nobreakspace}$m_2$, respectively. In the two\texttt{\symbol{45}}argument form, the arguments \mbox{\texttt{\mdseries\slshape cl1}} and{\nobreakspace}\mbox{\texttt{\mdseries\slshape cl2}} stand for the residue classes $r_1(m_1)$ and{\nobreakspace}$r_2(m_2)$, respectively. Enclosing the argument list in list brackets is permitted. The
residue classes $r_1(m_1)$ and $r_2(m_2)$ are stored as an attribute \texttt{TransposedClasses}. 

 \index{ClassPairs@\texttt{ClassPairs}!m} A list of all class transpositions interchanging residue classes with moduli
less than or equal to a given bound \mbox{\texttt{\mdseries\slshape m}} can be obtained by \texttt{List(ClassPairs([\mbox{\texttt{\mdseries\slshape P}}],\mbox{\texttt{\mdseries\slshape m}}),ClassTransposition)}, where the function \texttt{ClassPairs} returns a list of all 4\texttt{\symbol{45}}tuples $(r_1,m_1,r_2,m_2)$ of integers corresponding to the unordered pairs of disjoint residue classes $r_1(m_1)$ and $r_2(m_2)$ with $m_1$ and $m_2$ less than or equal to the specified bound. If a list of primes is given as
optional argument \mbox{\texttt{\mdseries\slshape P}}, then the returned list contains only those 4\texttt{\symbol{45}}tuples where
all prime factors of $m_1$ and $m_2$ lie in \mbox{\texttt{\mdseries\slshape P}}. If the option \texttt{divisors} is set, the returned list contains only the 4\texttt{\symbol{45}}tuples where $m_1$ and $m_2$ divide \mbox{\texttt{\mdseries\slshape m}}. 

 \index{NrClassPairs@\texttt{NrClassPairs}!m} \index{ExtRepOfObj@\texttt{ExtRepOfObj}!for a class transposition} The function \texttt{NrClassPairs(\mbox{\texttt{\mdseries\slshape m}})} returns the length of the list \texttt{ClassPairs(\mbox{\texttt{\mdseries\slshape m}})}, where the result is computed much faster and without actually generating the
list of tuples. Given a class transposition \mbox{\texttt{\mdseries\slshape ct}}, the corresponding 4\texttt{\symbol{45}}tuple can be obtained by \texttt{ExtRepOfObj(\mbox{\texttt{\mdseries\slshape ct}})} 

 \index{SplittedClassTransposition@\texttt{SplittedClassTransposition}!for a class transposition and a number of factors} A class transposition can be written as a product of any given number $k$ of class transpositions. Such a decomposition can be obtained by \texttt{SplittedClassTransposition(\mbox{\texttt{\mdseries\slshape ct}},\mbox{\texttt{\mdseries\slshape k}})}. 

 
\begin{Verbatim}[commandchars=!@A,fontsize=\small,frame=single,label=Example]
  
  !gapprompt@gap>A !gapinput@Display(ClassTransposition(1,2,8,10):CycleNotation:=false);A
  
  Rcwa permutation of Z with modulus 10, of order 2
  
          /
          | 5n+3    if n in 1(2)
   n |-> <  (n-3)/5 if n in 8(10)
          | n       if n in 0(2) \ 8(10)
          java.lang.NullPointerException
  
  !gapprompt@gap>A !gapinput@List(ClassPairs(4),ClassTransposition);A
  [ ( 0(2), 1(2) ), ( 0(2), 1(4) ), ( 0(2), 3(4) ), ( 0(3), 1(3) ), 
    ( 0(3), 2(3) ), ( 0(4), 1(4) ), ( 0(4), 2(4) ), ( 0(4), 3(4) ), 
    ( 1(2), 0(4) ), ( 1(2), 2(4) ), ( 1(3), 2(3) ), ( 1(4), 2(4) ), 
    ( 1(4), 3(4) ), ( 2(4), 3(4) ) ]
  !gapprompt@gap>A !gapinput@NrClassPairs(100);A
  3528138
  !gapprompt@gap>A !gapinput@SplittedClassTransposition(ClassTransposition(0,2,1,4),3);A
  [ ( 0(6), 1(12) ), ( 2(6), 5(12) ), ( 4(6), 9(12) ) ]
\end{Verbatim}
 }

 \noindent The set of all class transpositions of the ring of integers generates the
simple group CT({\ensuremath{\mathbb Z}}) mentioned in Chapter{\nobreakspace}\ref{ch:AboutRCWA}. This group has a representation as a \textsf{GAP} object \texttt{\symbol{45}}\texttt{\symbol{45}} see{\nobreakspace}\texttt{CT} (\ref{CT:the group generated by all class transpositions of a ring}). The set of all generalized class transpositions
of{\nobreakspace}{\ensuremath{\mathbb Z}} generates a simple group as well,
cf.{\nobreakspace}\cite{Kohl09}. 

 Class shifts, class reflections and class transpositions of rings $R$ other than{\nobreakspace}{\ensuremath{\mathbb Z}} are defined in an entirely
analogous way \texttt{\symbol{45}}\texttt{\symbol{45}} all one needs to do is
to replace {\ensuremath{\mathbb Z}} by{\nobreakspace}$R$ and to read $<$ and $\leq$ in the sense of the ordering used by{\nobreakspace}\textsf{GAP}. They can also be entered basically as described above
\texttt{\symbol{45}}\texttt{\symbol{45}} just prepend the desired
ring{\nobreakspace}$R$ to the argument list. Often also a sensible ``default ring'' ($\rightarrow$ \texttt{DefaultRing} in the \textsf{GAP} Reference Manual) is chosen if that optional first argument is omitted. 

 On rings which have more than two units, there is another basic series of rcwa
permutations which generalizes class reflections: 

\subsection{\textcolor{Chapter }{ClassRotation (r, m, u)}}
\logpage{[ 2, 2, 4 ]}\nobreak
\hyperdef{L}{X87EB8C1C87F78A17}{}
{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{ClassRotation({\mdseries\slshape r, m, u})\index{ClassRotation@\texttt{ClassRotation}!r, m, u}
\label{ClassRotation:r, m, u}
}\hfill{\scriptsize (function)}}\\
\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{ClassRotation({\mdseries\slshape cl, u})\index{ClassRotation@\texttt{ClassRotation}!cl, u}
\label{ClassRotation:cl, u}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 the class rotation $\rho_{r(m),u}$. 



 Given a residue class $r(m)$ and a unit{\nobreakspace}$u$ of a suitable ring{\nobreakspace}$R$, the \emph{class rotation} $\rho_{r(m),u}$ is the rcwa mapping which maps $n \in r(m)$ to $un + (1-u)r$ and which fixes $R \setminus r(m)$ pointwise. Class rotations generalize class reflections, as we have $\rho_{r(m),-1} = \varsigma_{r(m)}$. 

 \index{RotationFactor@\texttt{RotationFactor}!of a class rotation} In the two\texttt{\symbol{45}}argument form, the argument{\nobreakspace}\mbox{\texttt{\mdseries\slshape cl}} stands for the residue class{\nobreakspace}$r(m)$. Enclosing the argument list in list brackets is permitted. The argument \mbox{\texttt{\mdseries\slshape u}} is stored as an attribute \texttt{RotationFactor}. 
\begin{Verbatim}[commandchars=!@A,fontsize=\small,frame=single,label=Example]
  
  !gapprompt@gap>A !gapinput@Display(ClassRotation(ResidueClass(Z_pi(2),2,1),1/3));A
  
  Tame rcwa permutation of Z_( 2 ) with modulus 2, of order infinity
  
          /
          | 1/3 n + 2/3 if n in 1(2)
   n |-> <  n           if n in 0(2)
          |
          java.lang.NullPointerException
  
  !gapprompt@gap>A !gapinput@x := Indeterminate(GF(8),1);; SetName(x,"x");A
  !gapprompt@gap>A !gapinput@R := PolynomialRing(GF(8),1);;A
  !gapprompt@gap>A !gapinput@cr := ClassRotation(1,x,Z(8)*One(R)); Support(cr);A
  ClassRotation( 1(x), Z(2^3) )
  1(x) \ [ 1 ]
  !gapprompt@gap>A !gapinput@Display(cr);A
  
  Rcwa permutation of GF(2^3)[x] with modulus x, of order 7
  
          /
          | Z(2^3)*P + Z(2^3)^3 if P in 1(x)
   P |-> <  P                   otherwise
          |
          java.lang.NullPointerException
  
\end{Verbatim}
 }

 \index{IsClassShift@\texttt{IsClassShift}!for an rcwa mapping} \index{IsClassReflection@\texttt{IsClassReflection}!for an rcwa mapping} \index{IsClassRotation@\texttt{IsClassRotation}!for an rcwa mapping} \index{IsClassTransposition@\texttt{IsClassTransposition}!for an rcwa mapping} \index{IsGeneralizedClassTransposition@\texttt{IsGeneralizedClassTransposition}!for an rcwa mapping} \texttt{IsClassShift}, \texttt{IsClassReflection}, \texttt{IsClassRotation}, \texttt{IsClassTransposition} and \texttt{IsGeneralizedClassTransposition} are properties which indicate whether a given rcwa mapping belongs to the
corresponding series. 

 In the sequel we describe the general\texttt{\symbol{45}}purpose constructor
for rcwa mappings. The constructor may look a bit technical on a first glance,
but knowing all possible ways of entering an rcwa mapping is by no means
necessary for understanding this manual or for using this package. 
\subsection{\textcolor{Chapter }{ RcwaMapping (the general constructor) }}\logpage{[ 2, 2, 5 ]}
\hyperdef{L}{X8799551B83644B37}{}
{
\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{RcwaMapping({\mdseries\slshape R, m, coeffs})\index{RcwaMapping@\texttt{RcwaMapping}!by ring, modulus and list of coefficients}
\label{RcwaMapping:by ring, modulus and list of coefficients}
}\hfill{\scriptsize (method)}}\\
\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{RcwaMapping({\mdseries\slshape R, coeffs})\index{RcwaMapping@\texttt{RcwaMapping}!by ring and list of coefficients}
\label{RcwaMapping:by ring and list of coefficients}
}\hfill{\scriptsize (method)}}\\
\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{RcwaMapping({\mdseries\slshape coeffs})\index{RcwaMapping@\texttt{RcwaMapping}!by list of coefficients}
\label{RcwaMapping:by list of coefficients}
}\hfill{\scriptsize (method)}}\\
\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{RcwaMapping({\mdseries\slshape perm, range})\index{RcwaMapping@\texttt{RcwaMapping}!by permutation and range}
\label{RcwaMapping:by permutation and range}
}\hfill{\scriptsize (method)}}\\
\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{RcwaMapping({\mdseries\slshape m, values})\index{RcwaMapping@\texttt{RcwaMapping}!by modulus and list of values}
\label{RcwaMapping:by modulus and list of values}
}\hfill{\scriptsize (method)}}\\
\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{RcwaMapping({\mdseries\slshape pi, coeffs})\index{RcwaMapping@\texttt{RcwaMapping}!by set of non-invertible primes and list of coefficients}
\label{RcwaMapping:by set of non-invertible primes and list of coefficients}
}\hfill{\scriptsize (method)}}\\
\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{RcwaMapping({\mdseries\slshape q, m, coeffs})\index{RcwaMapping@\texttt{RcwaMapping}!by finite field size, modulus and list of coefficients}
\label{RcwaMapping:by finite field size, modulus and list of coefficients}
}\hfill{\scriptsize (method)}}\\
\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{RcwaMapping({\mdseries\slshape P1, P2})\index{RcwaMapping@\texttt{RcwaMapping}!by two partitions of a ring into residue classes}
\label{RcwaMapping:by two partitions of a ring into residue classes}
}\hfill{\scriptsize (method)}}\\
\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{RcwaMapping({\mdseries\slshape cycles})\index{RcwaMapping@\texttt{RcwaMapping}!by residue class cycles}
\label{RcwaMapping:by residue class cycles}
}\hfill{\scriptsize (method)}}\\
\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{RcwaMapping({\mdseries\slshape expression})\index{RcwaMapping@\texttt{RcwaMapping}!by arithmetical expression}
\label{RcwaMapping:by arithmetical expression}
}\hfill{\scriptsize (method)}}\\
\textbf{\indent Returns:\ }
 an rcwa mapping. 



 In all cases the argument{\nobreakspace}\mbox{\texttt{\mdseries\slshape R}} is the underlying ring, \mbox{\texttt{\mdseries\slshape m}} is the modulus and \mbox{\texttt{\mdseries\slshape coeffs}} is the coefficient list. A \emph{coefficient list} for an rcwa mapping with modulus $m$ consists of $|R/mR|$ coefficient triples \texttt{[}$a_{r(m)}$, $b_{r(m)}$, $c_{r(m)}$\texttt{]}. Their ordering is determined by the ordering of the representatives of the
residue classes (mod{\nobreakspace}$m$) in the sorted list returned by \texttt{AllResidues(\mbox{\texttt{\mdseries\slshape R}}, \mbox{\texttt{\mdseries\slshape m}})}. In case $R = {\ensuremath{\mathbb Z}}$ this means that the coefficient triple for the residue class $0(m)$ comes first and is followed by the one for $1(m)$, the one for $2(m)$ and so on. 

 If one or several of the arguments \mbox{\texttt{\mdseries\slshape R}}, \mbox{\texttt{\mdseries\slshape m}} and \mbox{\texttt{\mdseries\slshape coeffs}} are omitted or replaced by other arguments, the former are either derived from
the latter or default values are chosen. The meaning of the other arguments is
defined in the detailed description of the particular methods given in the
sequel. The above methods return the rcwa mapping 
\begin{description}
\item[{(a)}]  of \mbox{\texttt{\mdseries\slshape R}} with modulus \mbox{\texttt{\mdseries\slshape m}} and coefficients \mbox{\texttt{\mdseries\slshape coeffs}}, 
\item[{(b)}]  of \mbox{\texttt{\mdseries\slshape R}} = {\ensuremath{\mathbb Z}} or \mbox{\texttt{\mdseries\slshape R}} = ${\ensuremath{\mathbb Z}}_{(\pi)}$ with modulus \texttt{Length(\mbox{\texttt{\mdseries\slshape coeffs}})} and coefficients \mbox{\texttt{\mdseries\slshape coeffs}}, 
\item[{(c)}]  of \mbox{\texttt{\mdseries\slshape R}} = {\ensuremath{\mathbb Z}} with modulus \texttt{Length(\mbox{\texttt{\mdseries\slshape coeffs}})} and coefficients \mbox{\texttt{\mdseries\slshape coeffs}}, 
\item[{(d)}]  of \mbox{\texttt{\mdseries\slshape R}} = {\ensuremath{\mathbb Z}}, permuting any set \texttt{\mbox{\texttt{\mdseries\slshape range}}+k*Length(\mbox{\texttt{\mdseries\slshape range}})} like \mbox{\texttt{\mdseries\slshape perm}} permutes \mbox{\texttt{\mdseries\slshape range}}, 
\item[{(e)}]  of \mbox{\texttt{\mdseries\slshape R}} = {\ensuremath{\mathbb Z}} with modulus \mbox{\texttt{\mdseries\slshape m}} and values given by a list \mbox{\texttt{\mdseries\slshape val}} of 2 pairs \texttt{[}preimage\texttt{, }image\texttt{]} per residue class (mod \mbox{\texttt{\mdseries\slshape m}}), 
\item[{(f)}]  of \mbox{\texttt{\mdseries\slshape R}} = ${\ensuremath{\mathbb Z}}_{(\pi)}$ with modulus \texttt{Length(\mbox{\texttt{\mdseries\slshape coeffs}})} and coefficients \mbox{\texttt{\mdseries\slshape coeffs}} (the set of primes $\pi$ which denotes the underlying ring is passed as argument{\nobreakspace}\mbox{\texttt{\mdseries\slshape pi}}), 
\item[{(g)}]  of \mbox{\texttt{\mdseries\slshape R}} = GF(\mbox{\texttt{\mdseries\slshape q}})[\mbox{\texttt{\mdseries\slshape x}}] with modulus{\nobreakspace}\mbox{\texttt{\mdseries\slshape m}} and coefficients \mbox{\texttt{\mdseries\slshape coeffs}}, 
\item[{(h)}]  an rcwa permutation which induces a bijection between the partitions \mbox{\texttt{\mdseries\slshape P1}} and \mbox{\texttt{\mdseries\slshape P2}} of{\nobreakspace}\mbox{\texttt{\mdseries\slshape R}} into residue classes and which is affine on the elements of \mbox{\texttt{\mdseries\slshape P1}}, 
\item[{(i)}]  an rcwa permutation with ``residue class cycles'' given by a list \mbox{\texttt{\mdseries\slshape cycles}} of lists of pairwise disjoint residue classes, each of which it permutes
cyclically, or 
\item[{(j)}]  the rcwa permutation of{\nobreakspace}{\ensuremath{\mathbb Z}} given by the
arithmetical expression \mbox{\texttt{\mdseries\slshape expression}} \texttt{\symbol{45}}\texttt{\symbol{45}} a string consisting of class
transpositions (e.g. \texttt{"(0(2),1(4))"}) or cycles permuting residue classes (e.g. \texttt{"(0(2),1(8),3(4),5(8))"}), class shifts (e.g. \texttt{"cs(4(6))"}, class reflections (e.g. \texttt{"cr(3(4))"}), arithmetical operators (\texttt{"*"}, \texttt{"/"} and \texttt{"\texttt{\symbol{94}}"}) and brackets (\texttt{"("}, \texttt{")"}), 
\end{description}
 respectively. The methods for the operation \texttt{RcwaMapping} perform a number of argument checks, which can be skipped by using \texttt{RcwaMappingNC} instead. 
\begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
  
  !gapprompt@gap>| !gapinput@R := PolynomialRing(GF(2),1);; x := X(GF(2),1);; SetName(x,"x");|
  !gapprompt@gap>| !gapinput@RcwaMapping(R,x+1,[[1,0,x+One(R)],[x+One(R),0,1]]*One(R));     # (a)|
  <rcwa mapping of GF(2)[x] with modulus x+1>
  !gapprompt@gap>| !gapinput@RcwaMapping(Z_pi(2),[[1/3,0,1]]);                              # (b)|
  Rcwa mapping of Z_( 2 ): n -> 1/3 n
  !gapprompt@gap>| !gapinput@a := RcwaMapping([[2,0,3],[4,-1,3],[4,1,3]]);                  # (c)|
  <rcwa mapping of Z with modulus 3>
  !gapprompt@gap>| !gapinput@RcwaMapping((1,2,3),[1..4]);                                   # (d)|
  ( 1(4), 2(4), 3(4) )
  !gapprompt@gap>| !gapinput@T = RcwaMapping(2,[[1,2],[2,1],[3,5],[4,2]]);                  # (e)|
  true
  !gapprompt@gap>| !gapinput@RcwaMapping([2],[[1/3,0,1]]);                                  # (f)|
  Rcwa mapping of Z_( 2 ): n -> 1/3 n
  !gapprompt@gap>| !gapinput@RcwaMapping(2,x+1,[[1,0,x+One(R)],[x+One(R),0,1]]*One(R));     # (g)|
  <rcwa mapping of GF(2)[x] with modulus x+1>
  !gapprompt@gap>| !gapinput@a = RcwaMapping(List([[0,3],[1,3],[2,3]],ResidueClass),|
  !gapprompt@>| !gapinput@                   List([[0,2],[1,4],[3,4]],ResidueClass));       # (h)|
  true
  !gapprompt@gap>| !gapinput@RcwaMapping([List([[0,2],[1,4],[3,8],[7,16]],ResidueClass)]);  # (i)|
  ( 0(2), 1(4), 3(8), 7(16) )
  !gapprompt@gap>| !gapinput@Cycle(last,ResidueClass(0,2));|
  [ 0(2), 1(4), 3(8), 7(16) ]
  !gapprompt@gap>| !gapinput@g := RcwaMapping("((0(4),1(6))*cr(0(6)))^2/cs(2(8))");         # (j)|
  <rcwa permutation of Z with modulus 72>
  !gapprompt@gap>| !gapinput@g = (ClassTransposition(0,4,1,6) * ClassReflection(0,6))^2/|
  !gapprompt@>| !gapinput@        ClassShift(2,8);|
  true
  
\end{Verbatim}
 }

 Rcwa mappings of {\ensuremath{\mathbb Z}} can be ``translated'' to rcwa mappings of some semilocalization ${\ensuremath{\mathbb Z}}_{(\pi)}$ of{\nobreakspace}{\ensuremath{\mathbb Z}}: 

\subsection{\textcolor{Chapter }{LocalizedRcwaMapping (for an rcwa mapping of Z and a prime)}}
\logpage{[ 2, 2, 6 ]}\nobreak
\hyperdef{L}{X7F1A559387D0226E}{}
{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{LocalizedRcwaMapping({\mdseries\slshape f, p})\index{LocalizedRcwaMapping@\texttt{LocalizedRcwaMapping}!for an rcwa mapping of Z and a prime}
\label{LocalizedRcwaMapping:for an rcwa mapping of Z and a prime}
}\hfill{\scriptsize (function)}}\\
\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{SemilocalizedRcwaMapping({\mdseries\slshape f, pi})\index{SemilocalizedRcwaMapping@\texttt{SemilocalizedRcwaMapping}!for an rcwa mapping of Z and a set of primes}
\label{SemilocalizedRcwaMapping:for an rcwa mapping of Z and a set of primes}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 the rcwa mapping of ${\ensuremath{\mathbb Z}}_{(p)}$ respectively ${\ensuremath{\mathbb Z}}_{(\pi)}$ with the same coefficients as the rcwa mapping \mbox{\texttt{\mdseries\slshape f}} of{\nobreakspace}{\ensuremath{\mathbb Z}}. 



 The argument \mbox{\texttt{\mdseries\slshape p}} or \mbox{\texttt{\mdseries\slshape pi}} must be a prime or a set of primes, respectively. The argument{\nobreakspace}\mbox{\texttt{\mdseries\slshape f}} must be an rcwa mapping of{\nobreakspace}{\ensuremath{\mathbb Z}} whose
modulus is a power of{\nobreakspace}\mbox{\texttt{\mdseries\slshape p}}, or whose modulus has only prime divisors which lie in{\nobreakspace}\mbox{\texttt{\mdseries\slshape pi}}, respectively. 
\begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
  
  !gapprompt@gap>| !gapinput@T := RcwaMapping([[1,0,2],[3,1,2]]);; # The Collatz mapping.|
  !gapprompt@gap>| !gapinput@Cycle(LocalizedRcwaMapping(T,2),131/13);|
  [ 131/13, 203/13, 311/13, 473/13, 716/13, 358/13, 179/13, 275/13, 
    419/13, 635/13, 959/13, 1445/13, 2174/13, 1087/13, 1637/13, 2462/13, 
    1231/13, 1853/13, 2786/13, 1393/13, 2096/13, 1048/13, 524/13, 262/13 ]
  
\end{Verbatim}
 }

 \index{View@\texttt{View}!for an rcwa mapping} \index{Display@\texttt{Display}!for an rcwa mapping} \index{Print@\texttt{Print}!for an rcwa mapping} \index{String@\texttt{String}!for an rcwa mapping} \noindent Rcwa mappings can be \texttt{View}ed, \texttt{Display}ed, \texttt{Print}ed and written to a \texttt{String}. The output of the \texttt{View} method is kept reasonably short. In most cases it does not describe an rcwa
mapping completely. In these cases the output is enclosed in brackets. There
are options \texttt{CycleNotation}, \texttt{AsClassMapping}, \texttt{PrintNotation} and \texttt{AbridgedNotation} to take influence on how certain rcwa mappings are shown. These options can
either be not set, set to \texttt{true} or set to \texttt{false}. If the option \texttt{CycleNotation} is set, it is tried harder to write down an rcwa permutation of
{\ensuremath{\mathbb Z}} of finite order as a product of disjoint residue
class cycles, if this is possible. If the option \texttt{AsClassMapping} is set, \texttt{Display} shows which residue classes are mapped to which by the affine partial
mappings, and marks any loops. The option \texttt{PrintNotation} influences the output in favour of \textsf{GAP} \texttt{\symbol{45}} readability, and the option \texttt{AbridgedNotation} can be used to abridge longer names like \texttt{ClassShift}, \texttt{ClassReflection} etc.. By default, the output of the methods for \texttt{Display} and \texttt{Print} describes an rcwa mapping in full. The \texttt{Print}ed representation of an rcwa mapping is \textsf{GAP} \texttt{\symbol{45}} readable if and only if the \texttt{Print}ed representation of the elements of the underlying ring is so. 

 \index{LaTeXStringRcwaMapping@\texttt{LaTeXStringRcwaMapping}!for an rcwa mapping} There is also an operation \texttt{LaTeXStringRcwaMapping}, which takes as argument an rcwa mapping and returns a corresponding {\LaTeX} string. The output makes use of the {\LaTeX} macro package \textsf{amsmath}. If the option \mbox{\texttt{\mdseries\slshape Factorization}} is set and the argument is bijective, a factorization into class shifts, class
reflections, class transpositions and prime switches is printed (cf. \texttt{FactorizationIntoCSCRCT} (\ref{FactorizationIntoCSCRCT:for an rcwa permutation of Z})). For rcwa mappings with modulus greater than{\nobreakspace}1, an indentation
by \mbox{\texttt{\mdseries\slshape Indentation}} characters can be obtained by setting this option value accordingly. 
\begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
  
  !gapprompt@gap>| !gapinput@Print(LaTeXStringRcwaMapping(T));|
  n \ \mapsto java.lang.NullPointerException
  \begin{cases}
    n/2      & \text{if} \ n \in 0(2), \\
    (3n+1)/2 & \text{if} \ n \in 1(2).
  \end{cases}
  
\end{Verbatim}
 \index{LaTeXAndXDVI@\texttt{LaTeXAndXDVI}!for an rcwa mapping} There is an operation \texttt{LaTeXAndXDVI} which displays an rcwa mapping in an \textsf{xdvi} window. This works as follows: The string returned by \texttt{LaTeXStringRcwaMapping} is inserted into a {\LaTeX} template file. This file is {\LaTeX}'ed, and the result is shown with \textsf{xdvi}. Calling \texttt{Display} with option \mbox{\texttt{\mdseries\slshape xdvi}} has the same effect. The operation \texttt{LaTeXAndXDVI} is only available on UNIX systems, and requires suitable installations of {\LaTeX} and \textsf{xdvi}. }

  
\section{\textcolor{Chapter }{Basic arithmetic for residue\texttt{\symbol{45}}class\texttt{\symbol{45}}wise
affine mappings}}\label{sec:BasicArithmeticForRcwaMappings}
\logpage{[ 2, 3, 0 ]}
\hyperdef{L}{X78E796B8824C4FC8}{}
{
  \index{rcwa mapping@rcwa mapping!arithmetic operations} \index{Order@\texttt{Order}!of an rcwa permutation} \index{IsTame@\texttt{IsTame}!for an rcwa mapping} 

 Testing rcwa mappings for equality requires only comparing their coefficient
lists, hence is cheap. Rcwa mappings can be multiplied, thus there is a method
for \texttt{*}. Rcwa permutations can also be inverted, thus there is a method for \texttt{Inverse}. The latter method is usually accessed by raising a mapping to a power with
negative exponent. Multiplying, inverting and computing powers of tame rcwa
mappings is cheap. Computing powers of wild mappings is usually expensive
\texttt{\symbol{45}}\texttt{\symbol{45}} run time and memory requirements
normally grow approximately exponentially with the exponent. How expensive
multiplying a couple of wild mappings is, varies very much. In any case, the
amount of memory required for storing an rcwa mapping is proportional to its
modulus. Whether a given mapping is tame or wild can be determined by the
operation \texttt{IsTame}. There is a method for \texttt{Order}, which can not only compute a finite order, but which can also detect
infinite order. 
\begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
  
  !gapprompt@gap>| !gapinput@T := RcwaMapping([[1,0,2],[3,1,2]]);;          # The Collatz mapping.|
  !gapprompt@gap>| !gapinput@a := RcwaMapping([[2,0,3],[4,-1,3],[4,1,3]]);; # Collatz' permutation.|
  !gapprompt@gap>| !gapinput@List([-4..4],k->Modulus(a^k));|
  [ 256, 64, 16, 4, 1, 3, 9, 27, 81 ]
  !gapprompt@gap>| !gapinput@IsTame(T) or IsTame(a);|
  false
  !gapprompt@gap>| !gapinput@IsTame(ClassShift(0,1)) and IsTame(ClassTransposition(0,2,1,2));|
  true
  !gapprompt@gap>| !gapinput@T^2*a*T*a^-3;|
  <rcwa mapping of Z with modulus 768>
  !gapprompt@gap>| !gapinput@(ClassShift(1,3)*ClassReflection(2,7))^1000000;|
  <rcwa permutation of Z with modulus 21>
  
\end{Verbatim}
 \index{IsInjective@\texttt{IsInjective}!for an rcwa mapping} \index{IsSurjective@\texttt{IsSurjective}!for an rcwa mapping} \index{IsBijective@\texttt{IsBijective}!for an rcwa mapping} \index{Image@\texttt{Image}!of an rcwa mapping} There are methods installed for \texttt{IsInjective}, \texttt{IsSurjective}, \texttt{IsBijective} and \texttt{Image}. 
\begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
  
  !gapprompt@gap>| !gapinput@[ IsInjective(T), IsSurjective(T), IsBijective(a) ];|
  [ false, true, true ]
  !gapprompt@gap>| !gapinput@Image(RcwaMapping([[2,0,1]]));|
  0(2)
  
\end{Verbatim}
 \index{rcwa mapping@rcwa mapping!images under} Images of elements, of finite sets of elements and of unions of finitely many
residue classes of the source of an rcwa mapping can be computed with \texttt{\texttt{\symbol{94}}}, the same symbol as used for exponentiation and conjugation. The same works
for partitions of the source into a finite number of residue classes. 
\begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
  
  !gapprompt@gap>| !gapinput@15^T;|
  23
  !gapprompt@gap>| !gapinput@ResidueClass(1,2)^T;|
  2(3)
  !gapprompt@gap>| !gapinput@List([[0,3],[1,3],[2,3]],ResidueClass)^a;|
  [ 0(2), 1(4), 3(4) ]
  
\end{Verbatim}
 \index{PreImageElm@\texttt{PreImageElm}!of a ring element under an rcwa mapping} \index{PreImagesElm@\texttt{PreImagesElm}!of a ring element under an rcwa mapping} \index{PreImage@\texttt{PreImage}!of a set of ring elements under an rcwa mapping} \index{PreImage@\texttt{PreImage}!of a residue class union under an rcwa mapping} For computing preimages of elements under rcwa mappings, there are methods for \texttt{PreImageElm} and \texttt{PreImagesElm}. The preimage of a finite set of ring elements or of a union of finitely many
residue classes under an rcwa mapping can be computed by \texttt{PreImage}. 
\begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
  
  !gapprompt@gap>| !gapinput@PreImagesElm(T,8);|
  [ 5, 16 ]
  !gapprompt@gap>| !gapinput@PreImage(T,ResidueClass(Integers,3,2));|
  Z \ 0(6) U 2(6)
  !gapprompt@gap>| !gapinput@M := [1];; l := [1];;|
  !gapprompt@gap>| !gapinput@while Length(M) < 5000 do M := PreImage(T,M); Add(l,Length(M)); od; l;|
  [ 1, 1, 2, 2, 4, 5, 8, 10, 14, 18, 26, 36, 50, 67, 89, 117, 157, 208, 
    277, 367, 488, 649, 869, 1154, 1534, 2039, 2721, 3629, 4843, 6458 ]
  
\end{Verbatim}
 \index{Support@\texttt{Support}!of an rcwa mapping} \index{MovedPoints@\texttt{MovedPoints}!of an rcwa mapping} \index{RestrictedPerm@\texttt{RestrictedPerm}!for an rcwa permutation and a residue class union} \index{DensityOfSupport@\texttt{DensityOfSupport}!of an rcwa mapping} \index{DensityOfSetOfFixedPoints@\texttt{DensityOfSetOfFixedPoints}!of an rcwa mapping} There is a method for the operation \texttt{Support} for computing the support of an rcwa mapping. A synonym for \texttt{Support} is \texttt{MovedPoints}. The natural density of the support of an rcwa mapping of
{\ensuremath{\mathbb Z}} can be computed efficiently with the operation \texttt{DensityOfSupport}. Likewise, the natural density of the set of fixed points of an rcwa mapping
of {\ensuremath{\mathbb Z}} can be computed efficiently with the operation \texttt{DensityOfSetOfFixedPoints}. There is also a method for \texttt{RestrictedPerm} for computing the restriction of an rcwa permutation to a union of residue
classes which it fixes setwise. 
\begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
  
  !gapprompt@gap>| !gapinput@List([a,a^2],Support);|
  [ Z \ [ -1, 0, 1 ], Z \ [ -3, -2, -1, 0, 1, 2, 3 ] ]
  !gapprompt@gap>| !gapinput@RestrictedPerm(ClassShift(0,2)*ClassReflection(1,2),|
  !gapprompt@>| !gapinput@                  ResidueClass(0,2));|
  <rcwa mapping of Z with modulus 2>
  !gapprompt@gap>| !gapinput@last = ClassShift(0,2);|
  true
  
\end{Verbatim}
 Rcwa mappings can be added and subtracted pointwise. However, please note that
the set of rcwa mappings of a ring does not form a ring under \texttt{+} and \texttt{*}. 

 
\begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
  
  !gapprompt@gap>| !gapinput@b := ClassShift(0,3) * a;;|
  !gapprompt@gap>| !gapinput@[ Image((a + b)), Image((a - b)) ];|
  [ 2(4), [ -2, 0 ] ]
  
\end{Verbatim}
 \index{Modulus@\texttt{Modulus}!of an rcwa mapping} \index{Mod@\texttt{Mod}!for an rcwa mapping} \index{Coefficients@\texttt{Coefficients}!of an rcwa mapping} \index{rcwa mapping@rcwa mapping!coercion} \index{rcwa group@rcwa group!coercion} There are operations \texttt{Modulus} (abbreviated \texttt{Mod}) and \texttt{Coefficients} for retrieving the modulus and the coefficient list of an rcwa mapping. The
meaning of the return values is as described in Section{\nobreakspace}\ref{sec:EnteringRcwaMappings}. 

 General documentation for most operations mentioned in this section can be
found in the \textsf{GAP} reference manual. For rcwa mappings of rings other
than{\nobreakspace}{\ensuremath{\mathbb Z}}, not for all operations applicable
methods are available. 

 As in general a subring relation $R_1<R_2$ does \emph{not} give rise to a natural embedding of RCWA($R_1$) into RCWA($R_2$), there is no coercion between rcwa mappings or rcwa groups over different
rings. }

  
\section{\textcolor{Chapter }{ Attributes and properties of
residue\texttt{\symbol{45}}class\texttt{\symbol{45}}wise affine mappings }}\label{sec:AttributesAndPropertiesOfRcwaMappings}
\logpage{[ 2, 4, 0 ]}
\hyperdef{L}{X7C16D22C7BD40FDC}{}
{
  \index{class-wise translating@class\texttt{\symbol{45}}wise translating!definition} \index{integral@integral!definition} \index{balanced@balanced!definition} \index{sign-preserving@sign\texttt{\symbol{45}}preserving!definition} \index{maximal shift@maximal shift!definition} \index{rcwa mapping@rcwa mapping!prime set} \index{rcwa mapping@rcwa mapping!maximal shift} \index{rcwa mapping@rcwa mapping!class-wise translating} \index{rcwa mapping@rcwa mapping!integral} \index{rcwa mapping@rcwa mapping!balanced} \index{rcwa mapping@rcwa mapping!class-wise order-preserving} \index{rcwa mapping@rcwa mapping!sign-preserving} \index{Multiplier@\texttt{Multiplier}!of an rcwa mapping} \index{Mult@\texttt{Mult}!for an rcwa mapping} \index{Divisor@\texttt{Divisor}!of an rcwa mapping} \index{Div@\texttt{Div}!for an rcwa mapping} \index{PrimeSet@\texttt{PrimeSet}!of an rcwa mapping} \index{MaximalShift@\texttt{MaximalShift}!of an rcwa mapping of Z} \index{IsClassWiseTranslating@\texttt{IsClassWiseTranslating}!for an rcwa mapping} \index{IsIntegral@\texttt{IsIntegral}!for an rcwa mapping} \index{IsBalanced@\texttt{IsBalanced}!for an rcwa mapping} \index{IsClassWiseOrderPreserving@\texttt{IsClassWiseOrderPreserving}!for an rcwa mapping} \index{IsSignPreserving@\texttt{IsSignPreserving}!for an rcwa mapping} A number of basic attributes and properties of an rcwa mapping are derived
immediately from the coefficients of its affine partial mappings. This holds
for example for the multiplier and the divisor. These two values are stored as
attributes \texttt{Multiplier} and \texttt{Divisor}, or for short \texttt{Mult} and \texttt{Div}. The \emph{prime set} of an rcwa mapping is the set of prime divisors of the product of its modulus
and its multiplier. It is stored as an attribute \texttt{PrimeSet}. The \emph{maximal shift} of an rcwa mapping of {\ensuremath{\mathbb Z}} is the maximum of the absolute
values of its coefficients $b_{r(m)}$ in the notation introduced in Section{\nobreakspace}\ref{sec:basicdefinitions}. It is stored as an attribute \texttt{MaximalShift}. An rcwa mapping is called \emph{class\texttt{\symbol{45}}wise translating} if all of its affine partial mappings are translations, it is called \emph{integral} if its divisor equals{\nobreakspace}1, and it is called \emph{balanced} if its multiplier and its divisor have the same prime divisors. A
class\texttt{\symbol{45}}wise translating mapping has the property \texttt{IsClassWiseTranslating}, an integral mapping has the property \texttt{IsIntegral} and a balanced mapping has the property \texttt{IsBalanced}. An rcwa mapping of the ring of integers or of one of its semilocalizations
is called \emph{class\texttt{\symbol{45}}wise order\texttt{\symbol{45}}preserving} if and only if all coefficients $a_{r(m)}$ (cf.{\nobreakspace}Section{\nobreakspace}\ref{sec:basicdefinitions}) in the numerators of the affine partial mappings are positive. The
corresponding property is \texttt{IsClassWiseOrderPreserving}. An rcwa mapping of{\nobreakspace}{\ensuremath{\mathbb Z}} is called \emph{sign\texttt{\symbol{45}}preserving} if it does not map nonnegative integers to negative integers or vice versa.
The corresponding property is \texttt{IsSignPreserving}. All elements of the simple group CT({\ensuremath{\mathbb Z}}) generated by
the set of all class transpositions are sign\texttt{\symbol{45}}preserving. 
\begin{Verbatim}[commandchars=!@A,fontsize=\small,frame=single,label=Example]
  
  !gapprompt@gap>A !gapinput@u := RcwaMapping([[3,0,5],[9,1,5],[3,-1,5],[9,-2,5],[9,4,5]]);;A
  !gapprompt@gap>A !gapinput@IsBijective(u);; Display(u);A
  
  Rcwa permutation of Z with modulus 5
  
          /
          | 3n/5     if n in 0(5)
          | (9n+1)/5 if n in 1(5)
   n |-> <  (3n-1)/5 if n in 2(5)
          | (9n-2)/5 if n in 3(5)
          | (9n+4)/5 if n in 4(5)
          java.lang.NullPointerException
  
  !gapprompt@gap>A !gapinput@Multiplier(u);A
  9
  !gapprompt@gap>A !gapinput@Divisor(u);A
  5
  !gapprompt@gap>A !gapinput@PrimeSet(u);A
  [ 3, 5 ]
  !gapprompt@gap>A !gapinput@IsIntegral(u) or IsBalanced(u);A
  false
  !gapprompt@gap>A !gapinput@IsClassWiseOrderPreserving(u) and IsSignPreserving(u);A
  true
  
\end{Verbatim}
 There are a couple of further attributes and operations related to the affine
partial mappings of an rcwa mapping: 

\subsection{\textcolor{Chapter }{LargestSourcesOfAffineMappings (for an rcwa mapping)}}
\logpage{[ 2, 4, 1 ]}\nobreak
\hyperdef{L}{X7C21406085B69C30}{}
{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{LargestSourcesOfAffineMappings({\mdseries\slshape f})\index{LargestSourcesOfAffineMappings@\texttt{LargestSourcesOfAffineMappings}!for an rcwa mapping}
\label{LargestSourcesOfAffineMappings:for an rcwa mapping}
}\hfill{\scriptsize (attribute)}}\\
\textbf{\indent Returns:\ }
 the coarsest partition of \texttt{Source(\mbox{\texttt{\mdseries\slshape f}})} on whose elements the rcwa mapping{\nobreakspace}\mbox{\texttt{\mdseries\slshape f}} is affine. 



 
\begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
  
  !gapprompt@gap>| !gapinput@LargestSourcesOfAffineMappings(ClassShift(3,7));|
  [ Z \ 3(7), 3(7) ]
  !gapprompt@gap>| !gapinput@LargestSourcesOfAffineMappings(ClassReflection(0,1));|
  [ Integers ]
  !gapprompt@gap>| !gapinput@u := RcwaMapping([[3,0,5],[9,1,5],[3,-1,5],[9,-2,5],[9,4,5]]);;|
  !gapprompt@gap>| !gapinput@List( [ u, u^-1 ], LargestSourcesOfAffineMappings );|
  [ [ 0(5), 1(5), 2(5), 3(5), 4(5) ], [ 0(3), 1(3), 2(9), 5(9), 8(9) ] ]
  !gapprompt@gap>| !gapinput@kappa := ClassTransposition(2,4,3,4) * ClassTransposition(4,6,8,12)|
  !gapprompt@>| !gapinput@          * ClassTransposition(3,4,4,6);|
  <rcwa permutation of Z with modulus 12>
  !gapprompt@gap>| !gapinput@LargestSourcesOfAffineMappings(kappa);|
  [ 2(4), 1(4) U 0(12), 3(12) U 7(12), 4(12), 8(12), 11(12) ]
  
\end{Verbatim}
 }

 

\subsection{\textcolor{Chapter }{FixedPointsOfAffinePartialMappings (for an rcwa mapping)}}
\logpage{[ 2, 4, 2 ]}\nobreak
\hyperdef{L}{X7D6D0F2783AD02F4}{}
{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{FixedPointsOfAffinePartialMappings({\mdseries\slshape f})\index{FixedPointsOfAffinePartialMappings@\texttt{FixedPointsOfAffinePartialMappings}!for an rcwa mapping}
\label{FixedPointsOfAffinePartialMappings:for an rcwa mapping}
}\hfill{\scriptsize (attribute)}}\\
\textbf{\indent Returns:\ }
 a list of the sets of fixed points of the affine partial mappings of the rcwa
mapping{\nobreakspace}\mbox{\texttt{\mdseries\slshape f}} in the quotient field of its source. 



 The returned list contains entries for the restrictions of{\nobreakspace}\mbox{\texttt{\mdseries\slshape f}} to all residue classes modulo \texttt{Mod(\mbox{\texttt{\mdseries\slshape f}})}. A list entry can either be an empty set, the source of{\nobreakspace}\mbox{\texttt{\mdseries\slshape f}} or a set of cardinality{\nobreakspace}1. The ordering of the entries
corresponds to the ordering of the residues in \texttt{AllResidues(Source(\mbox{\texttt{\mdseries\slshape f}}),\mbox{\texttt{\mdseries\slshape m}})}. 
\begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
  
  !gapprompt@gap>| !gapinput@FixedPointsOfAffinePartialMappings(ClassShift(0,2));|
  [ [  ], Rationals ]
  !gapprompt@gap>| !gapinput@List([1..3],k->FixedPointsOfAffinePartialMappings(T^k));|
  [ [ [ 0 ], [ -1 ] ], [ [ 0 ], [ 1 ], [ 2 ], [ -1 ] ], 
    [ [ 0 ], [ -7 ], [ 2/5 ], [ -5 ], [ 4/5 ], [ 1/5 ], [ -10 ], [ -1 ] ] ]
  
\end{Verbatim}
 }

 

\subsection{\textcolor{Chapter }{Multpk (for an rcwa mapping, a prime and an exponent)}}
\logpage{[ 2, 4, 3 ]}\nobreak
\hyperdef{L}{X7A2E308C860B46E3}{}
{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{Multpk({\mdseries\slshape f, p, k})\index{Multpk@\texttt{Multpk}!for an rcwa mapping, a prime and an exponent}
\label{Multpk:for an rcwa mapping, a prime and an exponent}
}\hfill{\scriptsize (operation)}}\\
\textbf{\indent Returns:\ }
 the union of the residue classes $r(m)$ such that $p^k||a_{r(m)}$ if $k \geq 0$, and the union of the residue classes $r(m)$ such that $p^k||c_{r(m)}$ if $k \leq 0$. In this context, $m$ denotes the modulus of{\nobreakspace}\mbox{\texttt{\mdseries\slshape f}}, and $a_{r(m)}$ and $c_{r(m)}$ denote the coefficients of{\nobreakspace}\mbox{\texttt{\mdseries\slshape f}} as introduced in Section{\nobreakspace}\ref{sec:basicdefinitions}. 



 
\begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
  
  !gapprompt@gap>| !gapinput@T := RcwaMapping([[1,0,2],[3,1,2]]);; # The Collatz mapping.|
  !gapprompt@gap>| !gapinput@[ Multpk(T,2,-1), Multpk(T,3,1) ];|
  [ Integers, 1(2) ]
  !gapprompt@gap>| !gapinput@u := RcwaMapping([[3,0,5],[9,1,5],[3,-1,5],[9,-2,5],[9,4,5]]);;|
  !gapprompt@gap>| !gapinput@[ Multpk(u,3,0), Multpk(u,3,1), Multpk(u,3,2), Multpk(u,5,-1) ];|
  [ [  ], 0(5) U 2(5), Z \ 0(5) U 2(5), Integers ]
  
\end{Verbatim}
 }

 \index{ClassWiseOrderPreservingOn@\texttt{ClassWiseOrderPreservingOn}} \index{ClassWiseConstantOn@\texttt{ClassWiseConstantOn}} \index{ClassWiseOrderReversingOn@\texttt{ClassWiseOrderReversingOn}} There are attributes \texttt{ClassWiseOrderPreservingOn}, \texttt{ClassWiseConstantOn} and \texttt{ClassWiseOrderReversingOn} which store the union of the residue classes (mod{\nobreakspace}\texttt{Mod(\mbox{\texttt{\mdseries\slshape f}})}) on which an rcwa mapping{\nobreakspace}\mbox{\texttt{\mdseries\slshape f}} of{\nobreakspace}{\ensuremath{\mathbb Z}} or of a semilocalization thereof is
class\texttt{\symbol{45}}wise order\texttt{\symbol{45}}preserving,
class\texttt{\symbol{45}}wise constant or class\texttt{\symbol{45}}wise
order\texttt{\symbol{45}}reversing, respectively. 
\begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
  
  !gapprompt@gap>| !gapinput@List([ClassTransposition(1,2,0,4),ClassShift(2,3),|
  !gapprompt@>| !gapinput@         ClassReflection(2,5)],ClassWiseOrderPreservingOn);|
  [ Integers, Integers, Z \ 2(5) ]
  
\end{Verbatim}
 \index{ShiftsUpOn@\texttt{ShiftsUpOn}} \index{ShiftsDownOn@\texttt{ShiftsDownOn}} Also there are attributes \texttt{ShiftsUpOn} and \texttt{ShiftsDownOn} which store the union of the residue classes (mod{\nobreakspace}\texttt{Mod(\mbox{\texttt{\mdseries\slshape f}})}) on which an rcwa mapping{\nobreakspace}\mbox{\texttt{\mdseries\slshape f}} of{\nobreakspace}{\ensuremath{\mathbb Z}} induces affine mappings $n \mapsto n + c$ for $c > 0$, respectively, $c < 0$. 

 Finally, there are epimorphisms from the subgroup of RCWA({\ensuremath{\mathbb
Z}}) formed by all class\texttt{\symbol{45}}wise
order\texttt{\symbol{45}}preserving elements to ({\ensuremath{\mathbb Z}},+)
and from RCWA({\ensuremath{\mathbb Z}}) itself to the cyclic group of
order{\nobreakspace}2, respectively: 

\subsection{\textcolor{Chapter }{Determinant (of an rcwa mapping of Z)}}
\logpage{[ 2, 4, 4 ]}\nobreak
\hyperdef{L}{X7B1E53127D9AE52F}{}
{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{Determinant({\mdseries\slshape f})\index{Determinant@\texttt{Determinant}!of an rcwa mapping of Z}
\label{Determinant:of an rcwa mapping of Z}
}\hfill{\scriptsize (method)}}\\
\textbf{\indent Returns:\ }
 the determinant of the rcwa mapping{\nobreakspace}\mbox{\texttt{\mdseries\slshape f}} of{\nobreakspace}{\ensuremath{\mathbb Z}}. 



--> --------------------

--> maximum size reached

--> --------------------