<!-- #################################################################### -->
<!-- ##                                                                ## -->
<!-- ##  preface.xml         RCWA documentation           Stefan Kohl  ## -->
<!-- ##                                                                ## -->
<!-- ##  $Id: preface.xml,v 1.34 2005/11/11 13:53:45 stefan Exp $      ## -->
<!-- ##                                                                ## -->
<!-- #################################################################### -->

<Chapter Label="ch:preface"><Heading>Preface</Heading>

<!-- #################################################################### -->

<Section Label="sec:motivation">
<Heading>Motivation</Heading>

<Index Key="Collatz conjecture">Collatz conjecture</Index>
<Index Key="Collatz conjecture">Collatz mapping</Index>
The development of this package has been motivated by the famous
<M>3n+1</M> - Conjecture, which states that iterated application of the
Collatz mapping <P/>
<Alt Only="Text"> 
  <![CDATA[

       T: Z -> Z, n |-> n/2 if n even, and n |-> (3n+1)/2 if n odd

  ]]>
</Alt>
<Alt Only="HTML">
  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
  T:&nbsp;&nbsp;&nbsp;&nbsp;Z&nbsp;->&nbsp;Z,&nbsp;&nbsp;&nbsp;&nbsp;
  n&nbsp;|->&nbsp;n/2&nbsp;&nbsp;if&nbsp;n&nbsp;even,&nbsp;&nbsp;and
  &nbsp;&nbsp;n&nbsp;|->&nbsp;(3n+1)/2&nbsp;&nbsp;if&nbsp;n&nbsp;odd
</Alt>
<Alt Only="LaTeX">
  <Display>
  <![CDATA[
    T: \ \mathbb{Z} \longrightarrow \mathbb{Z}, \ \ \ \
    n \ \longmapsto \
    \begin{cases}
      \frac{n}{2}    & \text{if} \ n \ \text{even}, \\
      \frac{3n+1}{2} & \text{if} \ n \ \text{odd}
    \end{cases}
  ]]>
  </Display>
</Alt>
to any given positive integer eventually yields&nbsp;1. <P/>

This has been conjectured by Lothar Collatz in the 1930s, and is still
an unsolved problem today.
Replacing the Collatz mapping <M>T</M> by its conjugate under some
permutation <M>\sigma</M> of <M>\mathbb{Z}</M> fixing&nbsp;1 and setwisely
fixing the positive integers turns the <M>3n+1</M> - Conjecture into the
following equivalent conjecture: <M>\forall n \in \mathbb{N} \ \exists
k \in \mathbb{N}_0: \ n^{(T^\sigma)^k} = 1</M>.
The <M>3n+1</M> - Conjecture is true if and only if there is such a
permutation <M>\sigma</M> such that <M>T^\sigma</M> maps all integers
<M>n > 1</M> to smaller ones. Hence the problem is to find a suitable normal
form for the Collatz mapping&nbsp;<M>T</M>. <P/>

Investigating arbitrary permutations of finite sets is both theoretically
and computationally a hard problem. It is straightforward to restrict the
considerations to permutations which are <Q>similar</Q> to the Collatz
mapping itself. Probably the most natural class of such mappings is the
class of residue class-wise affine permutations. <P/>

Jeffrey C. Lagarias has written and maintains a commented bibliography
<Cite Key="Lagarias04"/>, which currently lists 193&nbsp;references
to publications related to the <M>3n+1</M> - Conjecture.
None of the articles which are referenced there tries to attack the
problem by means of group theory, or investigates the structure of
groups generated by bijective residue class-wise affine mappings.
In fact, the subject <E>residue class-wise affine groups</E> apparently
has not been treated anywhere in the literature before. <P/>

The author feels that this is a gap which is worth to be filled, and in
particular that the group of all residue class-wise affine bijections of
the integers is an object of natural interest in its own.

</Section>

<Alt Only="LaTeX">\pagebreak[4]</Alt>

<!-- #################################################################### -->

<Section Label="sec:purpose">
<Heading>Purpose of this package</Heading>

The purpose of this package is to serve as a tool for computational
investigations of residue class-wise affine mappings and -groups
mainly over the ring of the integers. <P/>

Perhaps the only sensible reason for using this package is being fascinated
by the mathematical beauty of the objects it helps to investigate. <P/>

This manual is pure software documentation, and as such it does not contain
any theorems or proofs. In a few places, where this is absolutely necessary
for understanding what some function is good for, corresponding mathematical
assertions are made. Proofs for all of them as well as a detailed development
of the theoretical background for the subject can be found in the
author's PhD thesis&nbsp;<Cite Key="Kohl05"/>.

</Section>

<!-- #################################################################### -->

<Section Label="sec:noteaboutcontents">
<Heading>Scope of this package</Heading>

There are relatively elaborate methods for dealing with residue class-wise
affine groups whose elements have a bounded number of different affine
partial mappings. These groups have a relatively easy structure. Hence they
are called <E>tame</E>. Understanding tame residue class-wise affine groups
is a necessary prerequisite for being able to investigate those which are
not tame. <P/>

The groups which are not tame are much more difficult to examine.
Hence these groups are called <E>wild</E>. 
Nevertheless, some computations can be done also in them --
there is e.g. an algorithm for factoring elements into generators,
which usually works reasonably well if the resulting word is not
<Q>too long</Q>. Often it is also possible to get useful information
about a wild group by considering its action on finite orbits --
of course provided that such orbits exist. <P/>

It cannot be said in a few sentences what can be found out with this package
about which mappings or groups. The best way to get an idea about this is to
experiment yourself with the examples discussed in this manual and included
in the file <File>pkg/rcwa/examples/examples.g</File>. Another useful source
of examples is the <Ref Meth="Random" Label="RCWA( Integers )"/> - function.
Often the package does not provide an out-of-the-box solution.
At the beginning you will perhaps be bored by extremely long runtimes for
seemingly trivial things. But with some experience you will learn to estimate
in advance how long something will take and to see why raising some
harmlessly-looking mapping to the 20th power would take terabytes of memory,
while one can easily find out non-trivial things about some group which looks
much more complicate. Provided that you have &LaTeX; and
<Package>xdvi</Package> installed, you can nicely display examples of rcwa
mappings by repeatedly issueing <C>Display(Random(RCWA(Integers)):xdvi);</C>.
Quite often it is possible to find an answer for a given question by using an
interactive trial-and-error approach. <P/>

The author for example has found with substancial help of this package
a non-trivial normal subgroup of the group of all residue class-wise affine
bijections of the integers.

</Section>

<!-- #################################################################### -->

<Section Label="sec:acknowledgements">
<Heading>Acknowledgements</Heading>

I would like to thank Bettina&nbsp;Eick for her kind help in
trying to make this package and in particular its documentation more
useful and more interesting for a larger number of people.
Furthermore I would like to thank the two anonymous referees for their
constructive criticism and helpful suggestions. <P/>

If you use &RCWA; in some work leading to a publication, I ask you to cite
it just as you would cite a journal article. I would be grateful for any
bug reports, comments or suggestions and of course for reports of results
found with the help of this package.

<Alt Only="Text"> </Alt>
<Alt Only="HTML">
<![CDATA[
  <P align = right> Stefan Kohl </P>
]]>
</Alt>
<Alt Only="LaTeX">
<![CDATA[
  \vfill \noindent Stuttgart, \today \hfill Stefan Kohl
]]>
</Alt>

</Section>

<!-- #################################################################### -->

</Chapter>

<!-- #################################################################### -->
