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

\newcommand{\Q}{\mathcal{Q}}


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

\NAME

\CLASS{order} \dotfill orders in algebraic number fields.

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

\ABSTRACT

\code{order} is a class for representing orders of algebraic number fields and for computing
elementary invariants like the discriminant and for maximizing the order at a given prime.


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

\DESCRIPTION \label{order_description}

An \code{order}, exactly like a \code{number_field}, consists of its $\bbfZ$-basis.  This basis
is stored using the internal class \code{nf_base}.


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

\CONS

\begin{fcode}{ct}{order}{const nf_base * $\mathit{base}_1$ = nf_base::current_base}
  initializes with the base represented by $\mathit{base}_1$.  If no pointer to an
  \code{nf_base} is given, the current base is used, which is the base of the
  \code{number_field} or the \code{order} that was constructed or read the last before invoking
  this constructor.  If no \code{number_field} or \code{order} has been used so far, this
  defaults to a (mostly useless) dummy order.
\end{fcode}

\begin{fcode}{ct}{order}{const polynomial< bigint > & $p$,
    const base_matrix< bigint > & $T$ = bigint_matrix(), const bigint & $d$ = 1}%
  if the second and third argument are omitted, this constructor initializes an order with the
  equation order of the polynomial $p$.  If this polynomial is not irreducible or not monic,
  this results in undefined behaviour.  If $T$ and $d$ are given also, this constructs an order
  with basis $(1, x, \dots, x^{\deg(p)}) \cdot T \cdot 1 / d$.
\end{fcode}

\begin{fcode}{ct}{order}{const bigint_matrix & $A$}
  initializes with the given matrix $A$ as multiplication table.  $A$ must be in the format
  described in the section Input/Output of the documentation for class \code{number_field} (see
  page \pageref{order_io}) .
\end{fcode}

\begin{fcode}{ct}{order}{const bigint_matrix & $A$, const bigint & $d$,
    nf_base * $\mathit{base}$ = nf_base::current_base}%
  initializes with the order generated by the columns of $\frac{1}{d} \cdot B \cdot A$, where
  $B$ is the base pointed to by $\mathit{base}$.  Note that due to the automatic casts you may
  also use an \code{order} or a \code{number_field} as third argument.  If no third argument is
  given, the current base is used, which is the base of the \code{number_field} or the
  \code{order} that was constructed or read the last before invoking this constructor.  If no
  \code{number_field} or \code{order} has been used so far, this defaults to a (mostly useless)
  dummy field.
\end{fcode}

\begin{fcode}{ct}{order}{const number_field & $F$}
  initializes with the maximal \code{order} of the \code{number_field} $F$.
\end{fcode}

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

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


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

\ASGN

Let $\Or$ be of type \code{order}.  The operator \code{=} is overloaded.  For consistency, the
following function is also implemented:

\begin{fcode}{void}{$\Or$.assign}{const order & $\Q$}
  $\Or \assign \Q$.
\end{fcode}


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

\ACCS

Let $\Or$ be an order in $\bbfZ[X] / (p)$ for a polynomial $p$ and let
\begin{displaymath}
  (w_1, \dots, w_n) = \frac{1}{d}(1, x, \dots, x^{n-1}) \cdot T
\end{displaymath}
be the basis of $\Or$, where $d$ is a \code{bigint} and $T$ is a \code{bigint_matrix}.  Then
$MT$ with
\begin{displaymath}
  w_i \cdot w_j = \sum_{k=1}^{n} \mathit{MT}(i,j,k) w_k
\end{displaymath}
is the multiplication table of the order.

\begin{cfcode}{const bigint &}{$\Or$.MT}{long $i$, long $j$, long $k$}
  returns $\mathit{MT}(i,j,k)$.
\end{cfcode}

\begin{cfcode}{const bigint_matrix &}{$\Or$.base_numerator}{}
  returns the \code{bigint_matrix} $T$ described above, if $T$ has been computed.  Otherwise it
  returns a $1 \times 1$-matrix containing $0$.
\end{cfcode}

\begin{fcode}{const bigint_matrix &}{base_numerator}{const order & $\Or$}
  returns the \code{bigint_matrix} $T$ described above, if $T$ has been computed.  Otherwise it
  returns a $1 \times 1$-matrix containing $0$.
\end{fcode}

\begin{cfcode}{const bigint &}{$\Or$.base_denominator}{}
  returns the \code{bigint} $d$ described above, if $T$ has been computed.  Otherwise it returns
  $1$.
\end{cfcode}

\begin{fcode}{const bigint & }{base_denominator}{const order & $\Or$}
  returns the \code{bigint} $d$ described above, if $T$ has been computed.  Otherwise it returns
  $1$.
\end{fcode}

\begin{cfcode}{nf_base *}{$\Or$.which_base}{}
  returns the pointer to the \code{nf_base} used to describe $\Or$.
\end{cfcode}

\begin{fcode}{nf_base *}{which_base}{const order & $\Or$}
  returns the pointer to the \code{nf_base} used to describe $\Or$.
\end{fcode}

\begin{cfcode}{const polynomial< bigint > &}{$\Or$.which_polynomial}{}
  returns the polynomial $p$ described above.
\end{cfcode}

\begin{fcode}{const polynomial< bigint > &}{which_polynomial}{const order & $\Or$}
  returns the polynomial $p$ described above.
\end{fcode}


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

\COMP

The binary operators \code{==}, \code{!=}, \code{<=}, \code{<} (true subset), \code{>=}, and
\code{>} are overloaded and can be used in exactly the same way as in the programming language
C++ if the orders to be compared happen to be represented using the same polynomial.  If this is
not the case the \LEH will be invoked.


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

\BASIC

Let $\Or$ be an instance of type \code{order}.

\begin{cfcode}{long}{$\Or$.degree}{}
  returns the rank of $\Or$ as module over $\bbfZ$.
\end{cfcode}

\begin{fcode}{long}{degree}{const order & $\Or$}
  returns the rank of $\Or$ as module over $\bbfZ$.
\end{fcode}

\begin{cfcode}{lidia_size_t}{$\Or$.no_of_real_embeddings}{}
  returns the number of embeddings of $\Or$ into $\bbfR$.
\end{cfcode}

\begin{fcode}{lidia_size_t}{no_of_real_embeddings}{const order & $\Or$}
  returns the number of embeddings of $\Or$ into $\bbfR$.
\end{fcode}

\begin{fcode}{void}{swap}{order & $\Or$, order & $\Q$}
  swaps $\Or$ and $\Q$.
\end{fcode}

\begin{cfcode}{operator}{alg_ideal}{}
  cast operator, which implicitly converts an \code{order} to an \code{alg_ideal} over this
  \code{order}.
\end{cfcode}


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

\HIGH

Let $\Or$ be an instance of type \code{order}.

\begin{cfcode}{const bigfloat &}{$\Or$.get_conjugate}{lidia_size_t $i$, lidia_size_t $j$}
  or $0 \leq i < \code{$\Or$.degree()}$ and $0 < j \leq \code{$\Or$.degree()}$ this functions
  returns the $j$-th conjugate of the $i$-th element of the basis representing $\Or$.  If $i$ or
  $j$ are not within the indicated bounds, the \LEH will be invoked.  Note that the order of the
  conjugates is randomly determined, but once it is determined, it remains fixed.  The first
  \code{$\Or$.no_of_real_embeddings()} conjugates always correspond to the real embeddings of
  $\Or$.
\end{cfcode}

\begin{cfcode}{const math_matrix< bigfloat > &}{$\Or$.get_conjugates}{}
  returns a reference to the matrix that is used internally to store the conjugates.  The $i$-th
  column of the matrix contains the conjugates of the $i$-th element of the basis representing
  $\Or$.
\end{cfcode}

\begin{cfcode}{const math_vector< bigint > &}{$\Or$.get_one}{}
  returns the representation of the rational number $1$ in $\Or$.
\end{cfcode}

%\begin{cfcode}{bigint_matrix}{$\Or$.get_trace_matrix}{}%
%returns the matrix of the traces of $w_i \cdot w_j$,
%$1 \leq i,j \leq n$, i.e.~$(\rm Tr(w_i \cdot
%w_j))_i,j$.
%\end{cfcode}

\begin{fcode}{bigint}{disc}{const order & $\Or$}
  returns the discriminant of $\Or$.
\end{fcode}

\begin{cfcode}{module}{$\Or$.pseudo_radical}{const bigint & $p$}
  returns the $p$-radical, if $p$ is a prime number.  Otherwise, this routine returns the
  so-called pseudo-radical (see~\cite{Buchmann/LenstraHW}).
\end{cfcode}

\begin{cfcode}{int}{$\Or$.dedekind}{const bigint & $p$, polynomial< bigint > & $h$}
  returns $1$, if $p$ is an index divisor of the equation order of the polynomial used to
  describe the base of $\Or$.  In this case $h(x)$ and $p$ generate the $p$-radical, where $x$
  is a root of the generating polynomial of the field.  If $p$ is not a prime number the
  behaviour of this function is undefined.
\end{cfcode}

\begin{cfcode}{order}{$\Or$.maximize}{const bigint & $m$}
  returns an order which is maximized at all primes which divide $m$ but whose squares don't
  divide $m$.
\end{cfcode}

\begin{cfcode}{order}{$\Or$.maximize}{}
  returns the maximal order containing $\Or$.  Since this involves factoring the discriminant of
  the order, this might take a fairly long time.
\end{cfcode}
%which is maximized at all primes with less than 6
%digits and at all factors of the discriminant with at most $10$
%digits, that where found by ECM (see \code{rational_factorization}, page
%\pageref{class:rational_fact}).}


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

\IO

\code{istream} operator \code{>>} and \code{ostream} operator \code{<<} are overloaded.  Input
and output of an \code{order} support exactly the same formats as input and output of a
\code{number_field}, so see the description of \code{number_field} for the (lengthy) description
of these formats (page \pageref{order_io}).


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

\WARNINGS

Some of the functions and arguments described as \code{const} in this documentation are only
\code{const}, if your compiler supports the new ANSI C++ keyword ``\code{mutable}''.  Otherwise
you might get some warnings while compiling your own programs.  For more detailed information
which functions are concerned have a look at \path{LiDIA/alg_number.h} and look for the
\code{LIDIA_NO_MUTABLE} conditionals.


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

\SEEALSO

\SEE{bigint}, \SEE{base_vector}, \SEE{module},
\SEE{alg_number}, \SEE{polynomial< bigint >}


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

\EXAMPLES

\begin{quote}
\begin{verbatim}
#include <LiDIA/alg_number.h>

int main()
{
    order O;                            // a dummy order
    number_field F;                     // a dummy field
    cin >> O;                           // Now the base of O is current_base
    alg_number a = bigint(1);
    cout << O;
    O = O.maximize();                   // Now the current_base is the base
                                        // of the maximal order!
                                        
    for (long zaehl = 1; zaehl <= 2; zaehl++) {
        alg_number one = bigint(1);
        cout << "one = " << one << endl;
        cout << "one + 1 = " << (one + 1) << endl;

        alg_number two = bigint(2);
        cout << "two = " << two << endl;

        if (zaehl != 2){
            cin >> F;                   // now the base of F is the current_base
            O.assign(order(F));         // O is the maximal order of F;
           // The numbers used in the next iteration will be numbers in order(F)!!
        }
        else cout << endl;
    }

    return 0;
}
\end{verbatim}
\end{quote}


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

\AUTHOR

Stefan Neis
