%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%%  module.tex      LiDIA documentation
%%
%%  This file contains the documentation of the class module
%%
%%  Copyright (c) 1995 by the LiDIA Group
%%
%%  Authors: Stefan Neis
%%

\newcommand{\num}{\mathit{num}}
\newcommand{\den}{\mathit{den}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\NAME

\CLASS{module/}\CLASS{alg_ideal} \dotfill free $\bbfZ$-modules and ideals in
algebraic number fields


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\ABSTRACT

\code{module} is a class for doing module arithmetic in number fields or more precisely in
orders.  \code{alg_ideal} is a class for doing ideal arithmetic.  They support for example
arithmetic operations (including pseudo-division), comparisons, and the computation of the ring
of multipliers of a module.

Both classes are essentially the same, however for ideals multiplication and divsion can use
faster algorithms than for modules.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\DESCRIPTION

A \code{module} as well as an \code{alg_ideal} consists of a triple $(\num, \den, \Or)$, where
the numerator $\num = (\underline{\num}_0, \dots, \underline{\num}_{m-1})$ is a
\code{bigmod_matrix} of size $n \times m$ (n is the degree of the number field) with
coefficients from $\bbfZ / M \bbfZ$ for some $M$, the denominator $\den$ is a \code{bigint}, and
$\Or$ is a pointer to the \code{nf_base}, that is used to represent the module.  The
\code{module}(\code{alg_ideal}) $(\num, \den, \Or)$ represents the module (ideal)
\begin{displaymath}
  \sum_{j=0}^{m-1} \frac{1}{\den} \left(\sum_{i=0}^{n-1} \num_{i,j} w_i\right) \cdot \bbfZ+M \Or
  \enspace,
\end{displaymath}
where $w_i$ are the base elements of the \code{nf_base} pointed to by $\Or$.  The components of
the numerator $\num$ and the denominator $\den$ of a \code{module} are always coprime, the
denominator $\den$ is positive.

Note that since each ideal is a module as well, \code{alg_ideal} inherits from \code{module}, so
that you can use all functions described for modules for \code{alg_ideals} as well.  Note
however, that a couple of extra functions are available for \code{alg_ideals}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\CONS

\begin{fcode}{ct}{module}{nf_base * $\Or_1$ = nf_base::current_base}
  initializes with the zero ideal.
\end{fcode}

\begin{fcode}{ct}{module}{const alg_number & $a$, const alg_number & $b$ = 0}
  initializes with the ideal generated by the algebraic numbers $a$ and $b$.  This constructor
  will be removed in the next release.
\end{fcode}

\begin{fcode}{ct}{module}{const base_matrix< bigint > & $A$, const bigint & d = 1,
    nf_base * $\Or_1$ = nf_base::current_base}%
  initializes the module with the ideal(!)  generated by the columns of $A$ divided by $d$.  If
  the number of rows of $A$ does not match the degree of the number field with the base $\Or_1$
  is pointing to, the \LEH will be invoked.  The behaviour of this constructor will change in
  the next release.  Please use the class \code{alg_ideal} for representing ideals.
\end{fcode}

\begin{fcode}{ct}{module}{const bigmod_matrix & $A$, const bigint & $d$ = 1,
    nf_base * $\Or_1$ = nf_base::current_base}%
  initializes with the $\bbfZ$-module generated by the columns of $A$ and the columns of $m\cdot
  I$ divided by $d$.  Here $m$ denotes the modulus of the \code{bigmod_matrix} and $I$ denotes
  an identity matrix with as many rows as $A$.  If the number of rows of $A$ does not match the
  degree of the number field with the base $\Or_1$ is pointing to, the \LEH will be invoked.
\end{fcode}

\begin{fcode}{ct}{module}{const module & $M$}
  initializes with a copy of the module $M$.
\end{fcode}

\begin{fcode}{dt}{{~module}}{}
\end{fcode}

\begin{fcode}{ct}{alg_ideal}{nf_base * $\Or_1$ = nf_base::current_base}
  initializes with the zero ideal.
\end{fcode}

\begin{fcode}{ct}{alg_ideal}{const bigint & $a$, const alg_number & $b$ = 0}
  initializes with the ideal generated by the integer $a$ and the algebraic number $b$.  Note
  that this will generate an ideal over the order, in which $b$ is contained.  Especially, if
  $b$ is omitted, it will be an ideal with respect to the base pointed to by
  \code{nf_base::current_base}.
\end{fcode}

\begin{fcode}{ct}{alg_ideal}{const alg_number & $a$, const alg_number & $b$ = 0}
  initializes with the ideal generated by the algebraic numbers $a$ and $b$.
\end{fcode}

\begin{fcode}{ct}{alg_ideal}{const base_matrix< bigint > & $A$, const bigint & d = 1,
    nf_base * $\Or_1$ = nf_base::current_base}%
  initializes with the ideal generated by the columns of $A$ (interpreted as algebraic numbers)
  divided by $d$.  If the number of rows of $A$ does not match the degree of the number field
  with the base $\Or_1$ is pointing to, the \LEH will be invoked.
\end{fcode}

\begin{fcode}{ct}{alg_ideal}{const bigmod_matrix & $A$, const bigint & $d$ = 1,
    nf_base * $\Or_1$ = nf_base::current_base}%
  initializes with the $\bbfZ$-module generated by the columns of $A$ and the columns of $m\cdot
  I$ divided by $d$.  Here $m$ denotes the modulus of the \code{bigmod_matrix} and $I$ denotes
  an identity matrix with as many rows as $A$.  If the number of rows of $A$ does not match the
  degree of the number field with the base $\Or_1$ is pointing to, the \LEH will be invoked.  If
  the resulting module does not have full rank, we use the ideal generated by the numbers of the
  module, otherwise we assume that the matrix really describes an ideal.  If this is not true,
  operations using this ideal may lead to wrong results!
\end{fcode}

\begin{fcode}{ct}{alg_ideal}{const alg_ideal & $M$}
  initializes with a copy of the ideal $M$.
\end{fcode}

\begin{fcode}{dt}{{~alg_ideal}}{}
\end{fcode}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\ASGN

Let $M$ be of type \code{module} or \code{alg_ideal}.  The operator \code{=} is overloaded.  For
efficiency reasons, the following functions are also implemented:

\begin{fcode}{void}{$M$.assign_zero}{}
  $M \assign (0)$, i.e.~$M$ is set to the zero ideal.
\end{fcode}

\begin{fcode}{void}{$M$.assign_one}{}
  $M \assign (1)$, i.e.~$M$ is set to the whole order generated by the base elements of the
  \code{nf_base}.
\end{fcode}

\begin{fcode}{void}{$M$.assign_whole_order}{}
  $M \assign (1)$.
\end{fcode}

\begin{fcode}{void}{$M$.assign}{const bigint & $b$}
  $M \assign (b)$, i.e.~$M$ is set to the principal ideal generated by $b$.
\end{fcode}

\begin{fcode}{void}{$M$.assign}{const alg_number & $b$}
  $M \assign (b)$.
\end{fcode}

\begin{fcode}{void}{$M$.assign}{const module & $N$}
  if $M$ is of type \code{alg_ideal}, then $M$ is set to the ideal generated by the elements of
  $N$, otherwise $M$ is set to $N$.
\end{fcode}

\begin{fcode}{void}{$M$.assign}{const alg_ideal & $N$}
  $M \assign N$.
\end{fcode}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\ACCS

Let $M$ be of type \code{module} or \code{alg_ideal} with $M = (\num, \den, \Or)$.

\begin{cfcode}{const bigmod_matrix &}{$M$.coeff_matrix}{}
  returns the numerator $\num$ of the description of $M$.
\end{cfcode}

\begin{fcode}{const bigmod_matrix &}{coeff_matrix}{const module/alg_ideal & $M$}
  returns the numerator $\num$ of the description of $M$.
\end{fcode}

\begin{cfcode}{module/alg_ideal}{$M$.numerator}{}
  Depending on the type of $M$, this returns either the \code{module} or the \code{alg_ideal}
  $(\num, 1, \Or)$.
\end{cfcode}

\begin{fcode}{module/alg_ideal}{numerator}{const module/alg_ideal & $M$}
  Depending on the type of $M$, this returns either the \code{module} or the \code{alg_ideal}
  $(\num, 1, \Or)$.
\end{fcode}

\begin{cfcode}{const bigint &}{$M$.denominator}{}
  returns the denominator $\den$ of the description of $M$.
\end{cfcode}

\begin{fcode}{const bigint &}{denominator}{const module/alg_ideal & $M$}
  returns the denominator $\den$ of the description of $M$.
\end{fcode}

\begin{cfcode}{nf_base *}{$M$.which_base}{}
  returns the pointer $\Or$ of the description of $M$.
\end{cfcode}

\begin{fcode}{nf_base *}{which_base}{const module/alg_ideal & $M$}
  returns the pointer $\Or$ of the description of $M$.
\end{fcode}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\ARTH

The following operators are overloaded and can be used in exactly the same way as in the
programming language C++.  If you use these operators on two modules/ideals $a$ and $b$, this is
only successful if $\code{$a$.which_base()} = \code{$b$.which_base()}$, otherwise the \LEH will
be invoked.

\begin{center}
  \code{(binary) +, &, *, / }\\
  \code{(bin.~with assignment) +=, &=, *=, /= }
\end{center}
\textbf{Note:} By \code{$M$ & $N$} we denote the intersection of the modules $M$
and $N$.

To avoid copying all operators also exist as functions:

\begin{fcode}{void}{add}{module & $c$, const module & $a$, const module & $b$}
  $c \assign a + b$, if $a$ and $b$ are over the same order.  Otherwise the \LEH will be
  invoked.
\end{fcode}

\begin{fcode}{void}{intersect}{module & $c$, const module & $a$, const module & $b$}
  $c \assign a \cap b$, if $a$ and $b$ are over the same order.  Otherwise the \LEH will be
  invoked.
\end{fcode}

\begin{fcode}{void}{multiply}{module & $c$, const module & $a$, const module & $b$}
  $c \assign a \cdot b$, if $a$ and $b$ are over the same order.  Otherwise the \LEH will be
  invoked.
\end{fcode}

\begin{fcode}{void}{multiply}{module & $c$, const module & $a$, const bigint & $i$}
  $c \assign a \cdot i$.
\end{fcode}

\begin{fcode}{void}{multiply}{module & $c$, const bigint & $i$, const module & $b$}
  $c \assign i \cdot b$.
\end{fcode}

\begin{fcode}{void}{multiply}{alg_ideal & $c$, const alg_ideal & $a$, const alg_ideal & $b$}
  $c \assign a \cdot b$, if $a$ and $b$ are over the same order.  Otherwise the \LEH will be
  invoked.  Note that the result will be the same if the multiply function for modules is used,
  however this special case should be faster.
\end{fcode}

\begin{fcode}{void}{multiply}{alg_ideal & $c$, const alg_ideal & $a$, const alg_number & $b$}
  $c \assign a \cdot b$, if $a$ and $b$ are over the same order.  Otherwise the \LEH will be
  invoked.
\end{fcode}

\begin{fcode}{void}{multiply}{alg_ideal & $c$, const alg_number & $b$, const alg_ideal & $a$}
  $c \assign a \cdot b$, if $a$ and $b$ are over the same order.  Otherwise the \LEH will be
  invoked.
\end{fcode}

\begin{fcode}{void}{divide}{module & $c$, const module & $a$, const module & $b$}
  $c \assign a / b$, if $b \neq 0$ and if $a$ and $b$ are over the same order $\Or$.  Otherwise
  the \LEH will be invoked.  If $b$ is not invertible, we compute the maximal module $c$ with
  $b\cdot c\subset a$.  Note that although this may seem a bit strange, it is a natural way to
  extend the notion of ideal division.
\end{fcode}

\begin{fcode}{void}{divide}{module & $c$, const module & $a$, const bigint & $i$}
  $c \assign a / i$, if $i \neq 0$.  Otherwise the \LEH will be invoked.
\end{fcode}

\begin{fcode}{void}{divide}{alg_ideal & $c$, const alg_ideal & $a$, const alg_ideal & $b$}
  $c \assign a / b$, if $b \neq 0$ and if $a$ and $b$ are over the same order $\Or$.  Otherwise
  the \LEH will be invoked.  If $b$ is not invertible, we compute the maximal module $c$ with
  $b\cdot c\subset a$.  Note that although this may seem a bit strange, it is a natural way to
  extend the notion of ideal division.
\end{fcode}

\begin{fcode}{void}{divide}{alg_ideal & $c$, const alg_ideal & $a$, const alg_number & $b$}
  $c \assign a / b$, if $b \neq 0$.  Otherwise the \LEH will be invoked.
\end{fcode}

\begin{fcode}{void}{a.invert}{}
  $a \assign 1 / a$, if $a$ is an invertible ideal.  Otherwise we set $a$ to the module $a':=\{
  x \in \bbfK : x \cdot a \subseteq \Or \}$.
\end{fcode}

\begin{fcode}{void}{invert}{module & $a$, const module & $b$}
  $a \assign 1 / b$, if $b$ is an invertible ideal.  Otherwise $a$ is set to $b':=\{ x \in \bbfK
  : x \cdot b \subseteq \Or \}$.
\end{fcode}

\begin{fcode}{module}{inverse}{const module & $a$}
  returns $1 / a$, if $a$ is an invertible ideal.  Otherwise we return the module $a':=\{ x \in
  \bbfK : x \cdot a \subseteq \Or \}$.
\end{fcode}

\begin{fcode}{alg_ideal}{inverse}{const alg_ideal & $a$}
  returns $1 / a$, if $a$ is an invertible ideal.  Otherwise we return the ideal $a':=\{ x \in
  \bbfK : x \cdot a \subseteq \Or \}$.
\end{fcode}

\begin{fcode}{void}{square}{module & $c$, const module & $a$}
  $c \assign a^2$.
\end{fcode}

\begin{fcode}{void}{power}{module & $c$, const module & $a$, const bigint & $i$}
  $c \assign a^i$.
\end{fcode}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\COMP

The binary operators \code{==}, \code{!=}, \code{<=}, \code{<} (true subset), \code{>=},
\code{>}, and the unary operator \code{!} (comparison with zero) are overloaded and can be used
in exactly the same way as in the programming language C++ if the modules/ideals to be compared
are given relative to the same basis.  Otherwise the \LEH will be invoked.  The operators may
also be used to compare modules with ideals.

Let $M$ be an instance of type \code{module} or \code{alg_ideal}.

\begin{cfcode}{bool}{$M$.is_zero}{}
  returns \TRUE if $M = (0)$, \FALSE otherwise.
\end{cfcode}

\begin{cfcode}{bool}{$M$.is_one}{}
  returns \TRUE if $M = (1)$, \FALSE otherwise.
\end{cfcode}

\begin{cfcode}{bool}{$M$.is_whole_order}{}
  returns \TRUE if $M = (1)$, \FALSE otherwise.
\end{cfcode}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\BASIC

Let $M = (\num, \den, \Or)$ be an instance of type \code{module} or \code{alg_ideal}.

\begin{cfcode}{bigint_matrix}{$M$.z_basis}{}
  returns a $\bbfZ$-basis of the module or ideal $M$.
\end{cfcode}

\begin{cfcode}{bigint_matrix}{z_basis}{const module/alg_ideal & $M$}
  returns a $\bbfZ$-basis of the module or ideal $M$.
\end{cfcode}

\begin{cfcode}{long}{$M$.degree}{}
  returns the rank of the order pointed to by $\Or$ as module over $\bbfZ$.
\end{cfcode}

\begin{fcode}{long}{degree}{const module/alg_ideal & $M$}
  returns the rank of the order pointed to by $\Or$ as module over $\bbfZ$.
\end{fcode}

\begin{fcode}{void}{$M$.normalize}{}
  normalizes the \code{module} or \code{alg_ideal} $M$ such that the $\gcd$ of the elements
  representing the numerator and the denominator is $1$ and that the denominator is positive.
\end{fcode}

\begin{fcode}{void}{swap}{module/alg_ideal & $M$, module/alg_ideal & $N$}
  exchanges the values of $M$ and $N$.  Note that using swap on parameters of different type
  will lead to unpredictable results, i.e.~the compiler does not (yet) complain.
\end{fcode}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\HIGH

Let $M$ be an instance of type \code{module} or \code{alg_ideal}.

\begin{fcode}{bigrational}{norm}{const module/alg_ideal & $M$}
  returns the norm of $M$.
\end{fcode}

\begin{fcode}{bigrational}{exp}{const module/alg_ideal & $M$}
  returns the exponent of $M$, i.e.~if $M = (\num, \den, \Or)$ it computes the smallest integer
  $e$, such that $e\cdot (*\Or) \subseteq \den \cdot M$ and then it returns $\frac{e}{\den}$.
\end{fcode}

\begin{cfcode}{order}{$M$.ring_of_multipliers}{const bigint & $p$}
  returns the ring of multipliers of the module $M$ modulo $p$.  Note that it is not necessary,
  that $p$ is prime.
\end{cfcode}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\IO

\code{istream} operator \code{>>} and \code{ostream} operator \code{<<} are overloaded.  Input
and output of a \code{module} or an \code{alg_ideal} have the following format:
$[\code{bigint_matrix}] / \den$, where [\code{bigint_matrix}] denotes a matrix given in any
format understood by the class \code{bigint_matrix}.  If the denominator is $1$, we omit it,
i.e.~in this case the formats are the same as for the class \code{bigint_matrix}.

Note that you have to manage by yourself that a \code{module} or an \code{alg_ideal} may have to
be separated by blanks from other input or output.

Since we didn't want to read the $\Or$-component of each module/ideal, we always assume, that we
are reading a representation with coefficients relative to the base pointed to by
\code{nf_base::current_base}.  By default, \code{nf_base::current_base} points to the basis of
the last number field or order that was read or constructed, but you may set it to previously
defined bases e.g.~by calling a constructor of the class \code{order} with suitable arguments.
If \code{nf_base::current_base} was not set before, the module will use some useless dummy base,
which will produce unpredictable results, if you use such a module in a computation before
assigning a meaningful value to it.  (Note: Exactly the same mechanism using the same variables
is used for reading and writing algebraic numbers).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\WARNINGS

For backward compatibility some of the constructors do not yet behave as one would expect, for
example \code{module(a,b)} with to \code{alg_numbers} $a$ and $b$ should construct the module
$a\bbfZ + b\bbfZ$, but in fact it does construct the ideal generated by $a$ and $b$, i.e.~the
module $a \Or + b \Or$.  However we do recommend to use the new class \code{alg_ideal} for this
purpose, which will support this constructor also in the future (\code{module} will not !!).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\SEEALSO

\SEE{bigint}, \SEE{bigmod_matrix},
\SEE{alg_number}, \SEE{order}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\EXAMPLES

For further references please refer \path{LiDIA/src/packages/alg_number/module_appl.cc}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\AUTHOR

Stefan Neis
