Function: nfinit
Section: number_fields
C-Name: nfinit0
Prototype: GD0,L,p
Help: nfinit(pol,{flag=0}): pol being a nonconstant irreducible polynomial,
 gives the vector: [pol,[r1,r2],discf,index,[M,MC,T2,T,different] (see
 manual),r1+r2 first roots, integral basis, matrix of power basis in terms of
 integral basis, multiplication table of basis]. flag is optional and can be
 set to 0: default; 1: do not compute different; 2: first use polred to find
 a simpler polynomial; 3: outputs a two-element vector [nf,Mod(a,P)], where
 nf is as in 2 and Mod(a,P) is a polmod equal to Mod(x,pol) and P=nf.pol.
Description:
 (gen, ?0):nf:prec       nfinit0($1, 0, prec)
 (gen, 1):nf:prec        nfinit0($1, 1, prec)
 (gen, 2):nf:prec        nfinit0($1, 2, prec)
 (gen, 3):gen:prec       nfinit0($1, 3, prec)
 (gen, 4):nf:prec        nfinit0($1, 4, prec)
 (gen, 5):gen:prec       nfinit0($1, 5, prec)
 (gen, #small):void      $"incorrect flag in nfinit"
 (gen, small):gen:prec   nfinit0($1, $2, prec)
Doc: \var{pol} being a non-constant,
 preferably monic, irreducible polynomial in $\Z[X]$, initializes a
 \emph{number field} structure (\kbd{nf}) associated to the field $K$ defined
 by \var{pol}. As such, it's a technical object passed as the first argument
 to most \kbd{nf}\var{xxx} functions, but it contains some information which
 may be directly useful. Access to this information via \emph{member
 functions} is preferred since the specific data organization specified below
 may change in the future. Currently, \kbd{nf} is a row vector with 9
 components:

 $\var{nf}[1]$ contains the polynomial \var{pol} (\kbd{\var{nf}.pol}).

 $\var{nf}[2]$ contains $[r1,r2]$ (\kbd{\var{nf}.sign}, \kbd{\var{nf}.r1},
 \kbd{\var{nf}.r2}), the number of real and complex places of $K$.

 $\var{nf}[3]$ contains the discriminant $d(K)$ (\kbd{\var{nf}.disc}) of $K$.

 $\var{nf}[4]$ contains the index of $\var{nf}[1]$ (\kbd{\var{nf}.index}),
 i.e.~$[\Z_K : \Z[\theta]]$, where $\theta$ is any root of $\var{nf}[1]$.

 $\var{nf}[5]$ is a vector containing 7 matrices $M$, $G$, \var{roundG}, $T$,
 $MD$, $TI$, $MDI$ useful for certain computations in the number field $K$.

 \quad\item $M$ is the $(r1+r2)\times n$ matrix whose columns represent
 the numerical values of the conjugates of the elements of the integral
 basis.

 \quad\item $G$ is an $n\times n$ matrix such that $T2 = {}^t G G$,
 where $T2$ is the quadratic form $T_2(x) = \sum |\sigma(x)|^2$, $\sigma$
 running over the embeddings of $K$ into $\C$.

 \quad\item \var{roundG} is a rescaled copy of $G$, rounded to nearest
 integers.

 \quad\item $T$ is the $n\times n$ matrix whose coefficients are
 $\text{Tr}(\omega_i\omega_j)$ where the $\omega_i$ are the elements of the
 integral basis. Note also that $\det(T)$ is equal to the discriminant of the
 field $K$. Also, when understood as an ideal, the matrix $T^{-1}$
 generates the codifferent ideal.

 \quad\item The columns of $MD$ (\kbd{\var{nf}.diff}) express a $\Z$-basis
 of the different of $K$ on the integral basis.

 \quad\item $TI$ is equal to the primitive part of $T^{-1}$, which has integral
 coefficients.

 \quad\item Finally, $MDI$ is a two-element representation (for faster
 ideal product) of $d(K)$ times the codifferent ideal
 (\kbd{\var{nf}.disc$*$\var{nf}.codiff}, which is an integral ideal). $MDI$
 is only used in \tet{idealinv}.

 $\var{nf}[6]$ is the vector containing the $r1+r2$ roots
 (\kbd{\var{nf}.roots}) of $\var{nf}[1]$ corresponding to the $r1+r2$
 embeddings of the number field into $\C$ (the first $r1$ components are real,
 the next $r2$ have positive imaginary part).

 $\var{nf}[7]$ is an integral basis for $\Z_K$ (\kbd{\var{nf}.zk}) expressed
 on the powers of~$\theta$. Its first element is guaranteed to be $1$. This
 basis is LLL-reduced with respect to $T_2$ (strictly speaking, it is a
 permutation of such a basis, due to the condition that the first element be
 $1$).

 $\var{nf}[8]$ is the $n\times n$ integral matrix expressing the power
 basis in terms of the integral basis, and finally

 $\var{nf}[9]$ is the $n\times n^2$ matrix giving the multiplication table
 of the integral basis.

 If a non monic polynomial is input, \kbd{nfinit} will transform it into a
 monic one, then reduce it (see $\fl=3$). It is allowed, though not very
 useful given the existence of \tet{nfnewprec}, to input a \var{nf} or a
 \var{bnf} instead of a polynomial. It is also allowed to
 input a \var{rnf}, in which case an \var{nf} structure associated to the
 absolute defining polynomial \kbd{polabs} is returned (\fl is then ignored).

 \bprog
 ? nf = nfinit(x^3 - 12); \\ initialize number field Q[X] / (X^3 - 12)
 ? nf.pol   \\ defining polynomial
 %2 = x^3 - 12
 ? nf.disc  \\ field discriminant
 %3 = -972
 ? nf.index \\ index of power basis order in maximal order
 %4 = 2
 ? nf.zk    \\ integer basis, lifted to Q[X]
 %5 = [1, x, 1/2*x^2]
 ? nf.sign  \\ signature
 %6 = [1, 1]
 ? factor(abs(nf.disc ))  \\ determines ramified primes
 %7 =
 [2 2]

 [3 5]
 ? idealfactor(nf, 2)
 %8 =
 [[2, [0, 0, -1]~, 3, 1, [0, 1, 0]~] 3]  \\ @com $\goth{p}_2^3$
 @eprog

 \misctitle{Huge discriminants, helping nfdisc}

 In case \var{pol} has a huge discriminant which is difficult to factor,
 it is hard to compute from scratch the maximal order. The special input
 format $[\var{pol}, B]$ is also accepted where \var{pol} is a polynomial as
 above and $B$ has one of the following forms

 \item an integer basis, as would be computed by \tet{nfbasis}: a vector of
 polynomials with first element $1$. This is useful if the maximal order is
 known in advance.

 \item an argument \kbd{listP} which specifies a list of primes (see
 \tet{nfbasis}). Instead of the maximal order, \kbd{nfinit} then computes an
 order which is maximal at these particular primes as well as the primes
 contained in the private prime table (see \tet{addprimes}). The result is
 unconditionaly correct when the discriminant \kbd{nf.disc} factors
 completely over this set of primes. The function \tet{nfcertify} automates
 this:
 \bprog
 ? pol = polcompositum(x^5 - 101, polcyclo(7))[1];
 ? nf = nfinit( [pol, 10^3] );
 ? nfcertify(nf)
 %3 = []
 @eprog\noindent A priori, \kbd{nf.zk} defines an order which is only known
 to be maximal at all primes $\leq 10^3$ (no prime $\leq 10^3$ divides
 \kbd{nf.index}). The certification step proves the correctness of the
 computation.
 \medskip

 If $\fl=2$: \var{pol} is changed into another polynomial $P$ defining the same
 number field, which is as simple as can easily be found using the
 \tet{polredbest} algorithm, and all the subsequent computations are done
 using this new polynomial. In particular, the first component of the result
 is the modified polynomial.

 If $\fl=3$, apply \kbd{polredbest} as in case 2, but outputs
 $[\var{nf},\kbd{Mod}(a,P)]$, where $\var{nf}$ is as before and
 $\kbd{Mod}(a,P)=\kbd{Mod}(x,\var{pol})$ gives the change of
 variables. This is implicit when \var{pol} is not monic: first a linear change
 of variables is performed, to get a monic polynomial, then \kbd{polredbest}.
Variant: Also available are
 \fun{GEN}{nfinit}{GEN x, long prec} ($\fl = 0$),
 \fun{GEN}{nfinitred}{GEN x, long prec} ($\fl = 2$),
 \fun{GEN}{nfinitred2}{GEN x, long prec} ($\fl = 3$).
 Instead of the above hardcoded numerical flags in \kbd{nfinit0}, one should
 rather use

 \fun{GEN}{nfinitall}{GEN x, long flag, long prec}, where \fl\ is an
 or-ed combination of

 \item \tet{nf_RED}: find a simpler defining polynomial,

 \item \tet{nf_ORIG}: if \tet{nf_RED} set, also return the change of variable,

 \item \tet{nf_ROUND2}: \emph{Deprecated}. Slow down the routine by using an
 obsolete normalization algorithm (do not use this one!),

 \item \tet{nf_PARTIALFACT}: \emph{Deprecated}. Lazy factorization of the
 polynomial discriminant. Result is conditional unless \kbd{nfcertify}
 can certify it.