Let K = **Q**[X] / (T) a number field, **Z**_K its ring of integers, T belongs to **Z**[X]
is monic. Three basic number field structures can be associated to K in
GP:

***** *nf* denotes a number field, i.e. a data structure output by
`nfinit`

. This contains the basic arithmetic data associated to the
number field: signature, maximal order (given by a basis `nf.zk`

),
discriminant, defining polynomial T, etc.

***** *bnf* denotes a "Buchmann's number field", i.e. a
data structure output by `bnfinit`

. This contains
*nf* and the deeper invariants of the field: units U(K), class group
Cl(K), as well as technical data required to solve the two associated
discrete logarithm problems.

***** *bnr* denotes a "ray number field", i.e. a data structure
output by `bnrinit`

, corresponding to the ray class group structure of
the field, for some modulus f. It contains a *bnf*, the modulus
f, the ray class group Cl_f(K) and data associated to
the discrete logarithm problem therein.

An *algebraic number* belonging to K = **Q**[X]/(T) is given as

***** a `t_INT`

, `t_FRAC`

or `t_POL`

(implicitly modulo T), or

***** a `t_POLMOD`

(modulo T), or

***** a `t_COL`

`v`

of dimension N = [K:**Q**], representing
the element in terms of the computed integral basis, as
`sum(i = 1, N, v[i] * nf.zk[i])`

. Note that a `t_VEC`

will not be recognized.

An *ideal* is given in any of the following ways:

***** an algebraic number in one of the above forms, defining a principal ideal.

***** a prime ideal, i.e. a 5-component vector in the format output by
`idealprimedec`

or `idealfactor`

.

***** a `t_MAT`

, square and in Hermite Normal Form (or at least
upper triangular with non-negative coefficients), whose columns represent a
**Z**-basis of the ideal.

One may use `idealhnf`

to convert any ideal to the last (preferred) format.

***** an *extended ideal* is a 2-component
vector [I, t], where I is an ideal as above and t is an algebraic
number, representing the ideal (t)I. This is useful whenever `idealred`

is involved, implicitly working in the ideal class group, while keeping track
of principal ideals. Ideal operations suitably update the principal part
when it makes sense (in a multiplicative context), e.g. using `idealmul`

on [I,t], [J,u], we obtain [IJ, tu]. When it does not make sense, the
extended part is silently discarded, e.g. using `idealadd`

with the above
input produces I+J.

The "principal part" t in an extended ideal may be
represented in any of the above forms, and *also* as a factorization
matrix (in terms of number field elements, not ideals!), possibly the empty
matrix `[;]`

representing 1. In the latter case, elements stay in
factored form, or *famat* for *fa*ctorization *mat*rix, which
is a convenient way to avoid coefficient explosion. To recover the
conventional expanded form, try `nffactorback`

; but many functions
already accept *famat*s as input, for instance `ideallog`

, so
expanding huge elements should never be necessary.

A finite abelian group G in user-readable format is given by its Smith
Normal Form as a pair [h,d] or triple [h,d,g].
Here h is the cardinality of G, (d_i) is the vector of elementary
divisors, and (g_i) is a vector of generators. In short,
G = oplus_{i `<=`

n} (**Z**/d_i**Z**) g_i, with d_n | ... | d_2 | d_1
and prod d_i = h. This information can also be retrieved as
G.`no`

, G.`cyc`

and G.`gen`

.

***** a *character* on the abelian group
oplus (**Z**/d_i**Z**) g_i
is given by a row vector chi = [a_1,...,a_n] such that
chi(prod g_i^{n_i}) = exp(2iPisum a_i n_i / d_i).

***** given such a structure, a *subgroup* H is input as a square
matrix in HNF, whose columns express generators of H on the given generators
g_i. Note that the determinant of that matrix is equal to the index (G:H).

We now have a look at data structures associated to relative extensions
of number fields L/K, and to projective **Z**_K-modules. When defining a
relative extension L/K, the *nf* associated to the base field K
must be defined by a variable having a lower priority (see
Section [**Label: se:priority**]) than the variable defining the extension. For example,
you may use the variable name y to define the base field K, and x to
define the relative extension L/K.

A *modulus*, in the sense of class field theory, is a divisor supported
on the non-complex places of K. In PARI terms, this means either an
ordinary ideal I as above (no Archimedean component), or a pair [I,a],
where a is a vector with r_1 {0,1}-components, corresponding to the
infinite part of the divisor. More precisely, the i-th component of a
corresponds to the real embedding associated to the i-th real root of
`K.roots`

. (That ordering is not canonical, but well defined once a
defining polynomial for K is chosen.) For instance, `[1, [1,1]]`

is a
modulus for a real quadratic field, allowing ramification at any of the two
places at infinity, and nowhere else.

A *bid* or "big ideal" is a structure output by `idealstar`

needed to compute in (**Z**_K/I)^*, where I is a modulus in the above sense.
It is a finite abelian group as described above, supplemented by
technical data needed to solve discrete log problems.

Finally we explain how to input ray number fields (or *bnr*), using class
field theory. These are defined by a triple A, B, C, where the
defining set [A,B,C] can have any of the following forms: [*bnr*],
[*bnr*,*subgroup*], [*bnf*,*mod*],
[*bnf*,*mod*,*subgroup*]. The last two forms are kept for
backward compatibility, but no longer serve any real purpose (see example
below); no newly written function will accept them.

***** *bnf* is as output by `bnfinit`

, where units are mandatory
unless the modulus is trivial; *bnr* is as output by `bnrinit`

. This
is the ground field K.

***** *mod* is a modulus **f**, as described above.

***** *subgroup* a subgroup of the ray class group modulo **f** of
K. As described above, this is input as a square matrix expressing
generators of a subgroup of the ray class group

on the
given generators.*bnr*.clgp

The corresponding *bnr* is the subfield of the ray class field of K
modulo **f**, fixed by the given subgroup.

? K = bnfinit(y^2+1); ? bnr = bnrinit(K, 13) ? %.clgp %3 = [36, [12, 3]] ? bnrdisc(bnr); \\ discriminant of the full ray class field ? bnrdisc(bnr, [3,1;0,1]); \\ discriminant of cyclic cubic extension of K

We could have written directly

? bnrdisc(K, 13); ? bnrdisc(K, 13, [3,1;0,1]);

avoiding one `bnrinit`

, but this would actually be slower since the
`bnrinit`

is called internally anyway. And now twice!

All the functions which are specific to relative extensions, number fields,
Buchmann's number fields, Buchmann's number rays, share the prefix `rnf`

,
`nf`

, `bnf`

, `bnr`

respectively. They take as first argument a
number field of that precise type, respectively output by `rnfinit`

,
`nfinit`

, `bnfinit`

, and `bnrinit`

.

However, and even though it may not be specified in the descriptions of the
functions below, it is permissible, if the function expects a *nf*, to
use a *bnf* instead, which contains much more information. On the other
hand, if the function requires a `bnf`

, it will *not* launch
`bnfinit`

for you, which is a costly operation. Instead, it will give you
a specific error message. In short, the types
`nf`

`<=`

`bnf`

`<=`

`bnr`

are ordered, each function requires a minimal type to work properly, but you
may always substitute a larger type.

The data types corresponding to the structures described above are rather complicated. Thus, as we already have seen it with elliptic curves, GP provides "member functions" to retrieve data from these structures (once they have been initialized of course). The relevant types of number fields are indicated between parentheses:

`bid`

(*bnr* ) : bid ideal structure.

`bnf`

(*bnr*, *bnf* ) : Buchmann's number field.

`clgp`

(*bnr*, *bnf* ) : classgroup. This one admits the
following three subclasses:

`cyc`

: cyclic decomposition
(SNF).

`gen`

:
generators.

`no`

: number of elements.

`diff`

(*bnr*, *bnf*, *nf* ) : the different ideal.

`codiff`

(*bnr*, *bnf*, *nf* ) : the codifferent
(inverse of the different in the ideal group).

`disc`

(*bnr*, *bnf*, *nf* ) : discriminant.

`fu`

(*bnr*, *bnf* ) : fundamental units.

`index`

(*bnr*, *bnf*, *nf* ) :
index of the power order in the ring of integers.

`mod`

(*bnr* ) : modulus.

`nf`

(*bnr*, *bnf*, *nf* ) : number field.

`pol`

(*bnr*, *bnf*, *nf* ) : defining polynomial.

`r1`

(*bnr*, *bnf*, *nf* ) : the number
of real embeddings.

`r2`

(*bnr*, *bnf*, *nf* ) : the number
of pairs of complex embeddings.

`reg`

(*bnr*, *bnf* ) : regulator.

`roots`

(*bnr*, *bnf*, *nf* ) : roots of the
polynomial generating the field.

`sign`

(*bnr*, *bnf*, *nf* ) : signature [r1,r2].

`t2`

(*bnr*, *bnf*, *nf* ) : the T_2 matrix (see
`nfinit`

).

`tu`

(*bnr*, *bnf* ) : a generator for the torsion
units.

`zk`

(*bnr*, *bnf*, *nf* ) : integral basis, i.e. a
**Z**-basis of the maximal order.

`zkst`

(*bnr* ) : structure of (**Z**_K/m)^*.

**Deprecated.** The following member functions are still available, but deprecated and should not be used in new scripts :

`futu`

(*bnr*, *bnf*, ) :
[u_1,...,u_r,w], (u_i) is a vector of fundamental units,

w generates the torsion units.

`tufu`

(*bnr*, *bnf*, ) :
[w,u_1,...,u_r], (u_i) is a vector of fundamental units,

w generates the torsion units.

For instance, assume that *bnf* = `bnfinit`

(*pol*), for some
polynomial. Then

retrieves the class group, and
*bnf*.clgp

the class number. If we had set *bnf*.clgp.no*bnf* =
`nfinit`

(*pol*), both would have output an error message. All these
functions are completely recursive, thus for instance

will yield the maximal order of *bnr*.bnf.nf.zk*bnr*, which
you could get directly with a simple

.*bnr*.zk

Some of the functions starting with `bnf`

are implementations of the
sub-exponential algorithms for finding class and unit groups under GRH,
due to Hafner-McCurley, Buchmann and Cohen-Diaz-Olivier. The general
call to the functions concerning class groups of general number fields
(i.e. excluding `quadclassunit`

) involves a polynomial P and a
technical vector
*tech* = [c_1, c_2, *nrpid* ],
where the parameters are to be understood as follows:

P is the defining polynomial for the number field, which must be in
**Z**[X], irreducible and monic. In fact, if you supply a non-monic polynomial
at this point, `gp`

issues a warning, then *transforms your
polynomial* so that it becomes monic. The `nfinit`

routine
will return a different result in this case: instead of `res`

, you get a
vector `[res,Mod(a,Q)]`

, where `Mod(a,Q) = Mod(X,P)`

gives the change
of variables. In all other routines, the variable change is simply lost.

The *tech* interface is obsolete and you should not tamper with
these parameters. Indeed, from version 2.4.0 on,

***** the results are always rigorous under GRH (before that version,
they relied on a heuristic strengthening, hence the need for overrides).

***** the influence of these parameters on execution time and stack size is
marginal. They *can* be useful to fine-tune and experiment with the
`bnfinit`

code, but you will be better off modifying all tuning
parameters in the C code (there are many more than just those three).
We nevertheless describe it for completeness.

The numbers c_1 `<=`

c_2 are non-negative real numbers. By default they are
chosen so that the result is correct under GRH. For i = 1,2, let
B_i = c_i(log |d_K|)^2, and denote by S(B) the set of maximal ideals of
K whose norm is less than B. We want S(B_1) to generate Cl(K) and hope
that S(B_2) can be *proven* to generate Cl(K).

More precisely, S(B_1) is a factorbase used to compute a tentative
Cl(K) by generators and relations. We then check explicitly, using
essentially `bnfisprincipal`

, that the elements of S(B_2) belong to the
span of S(B_1). Under the assumption that S(B_2) generates Cl(K), we
are done. User-supplied c_i are only used to compute initial guesses for
the bounds B_i, and the algorithm increases them until one can *prove*
under GRH that S(B_2) generates Cl(K). A uniform result of Bach says
that c_2 = 12 is always suitable, but this bound is very pessimistic and a
direct algorithm due to Belabas-Diaz-Friedman is used to check the condition,
assuming GRH. The default values are c_1 = c_2 = 0. When c_1 is equal to
0 the algorithm takes it equal to c_2.

*nrpid* is the maximal number of small norm relations associated to each
ideal in the factor base. Set it to 0 to disable the search for small norm
relations. Otherwise, reasonable values are between 4 and 20. The default is
4.

**Warning.** Make sure you understand the above! By default, most of
the `bnf`

routines depend on the correctness of the GRH. In particular,
any of the class number, class group structure, class group generators,
regulator and fundamental units may be wrong, independently of each other.
Any result computed from such a `bnf`

may be wrong. The only guarantee is
that the units given generate a subgroup of finite index in the full unit
group. You must use `bnfcertify`

to certify the computations
unconditionally.

**Remarks.**

You do not need to supply the technical parameters (under the library you
still need to send at least an empty vector, coded as `NULL`

). However,
should you choose to set some of them, they *must* be given in the
requested order. For example, if you want to specify a given value of
*nrpid*, you must give some values as well for c_1 and c_2, and provide
a vector [c_1,c_2,*nrpid*].

Note also that you can use an *nf* instead of P, which avoids
recomputing the integral basis and analogous quantities.

*bnf* being as output by
`bnfinit`

, checks whether the result is correct, i.e. whether it is
possible to remove the assumption of the Generalized Riemann
Hypothesis. It is correct if and only if the answer is 1. If it is
incorrect, the program may output some error message, or loop indefinitely.
You can check its progress by increasing the debug level. The *bnf*
structure must contain the fundamental units:

? K = bnfinit(x^3+2^2^3+1); bnfcertify(K) *** at top-level: K=bnfinit(x^3+2^2^3+1);bnfcertify(K) *** ^------------- *** bnfcertify: missing units in bnf. ? K = bnfinit(x^3+2^2^3+1, 1); \\ include units ? bnfcertify(K) %3 = 1

If flag is present, only certify that the class group is a quotient of the one computed in bnf (much simpler in general); likewise, the computed units may form a subgroup of the full unit group. In this variant, the units are no longer needed:

? K = bnfinit(x^3+2^2^3+1); bnfcertify(K, 1) %4 = 1

The library syntax is `long `

.
Also available is **bnfcertify0**(GEN bnf, long flag )`GEN `

(**bnfcertify**(GEN bnf)*flag* = 0).

Computes a compressed version of *bnf* (from `bnfinit`

), a
"small Buchmann's number field" (or *sbnf* for short) which contains
enough information to recover a full *bnf* vector very rapidly, but
which is much smaller and hence easy to store and print. Calling
`bnfinit`

on the result recovers a true `bnf`

, in general different
from the original. Note that an *snbf* is useless for almost all
purposes besides storage, and must be converted back to *bnf* form
before use; for instance, no `nf*`

, `bnf*`

or member function
accepts them.

An *sbnf* is a 12 component vector v, as follows. Let `bnf`

be
the result of a full `bnfinit`

, complete with units. Then v[1] is
`bnf.pol`

, v[2] is the number of real embeddings `bnf.sign[1]`

,
v[3] is `bnf.disc`

, v[4] is `bnf.zk`

, v[5] is the list of roots
`bnf.roots`

, v[7] is the matrix `W`

= `bnf[1]`

,
v[8] is the matrix `matalpha`

= `bnf[2]`

,
v[9] is the prime ideal factor base `bnf[5]`

coded in a compact way,
and ordered according to the permutation `bnf[6]`

, v[10] is the
2-component vector giving the number of roots of unity and a generator,
expressed on the integral basis, v[11] is the list of fundamental units,
expressed on the integral basis, v[12] is a vector containing the algebraic
numbers alpha corresponding to the columns of the matrix `matalpha`

,
expressed on the integral basis.

All the components are exact (integral or rational), except for the roots in v[5].

The library syntax is `GEN `

.**bnfcompress**(GEN bnf)

If m is a module as output in the
first component of an extension given by `bnrdisclist`

, outputs the
true module.

? K = bnfinit(x^2+23); L = bnrdisclist(K, 10); s = L[1][2] %1 = [[Mat([8, 1]), [[0, 0, 0]]], [Mat([9, 1]), [[0, 0, 0]]]] ? bnfdecodemodule(K, s[1][1]) %2 = [2 0] [0 1]

The library syntax is `GEN `

.**decodemodule**(GEN nf, GEN m)

Initializes a
*bnf* structure. Used in programs such as `bnfisprincipal`

,
`bnfisunit`

or `bnfnarrow`

. By default, the results are conditional
on the GRH, see [**Label: se:GRHbnf**]. The result is a
10-component vector *bnf*.

This implements Buchmann's sub-exponential algorithm for computing the class group, the regulator and a system of fundamental units of the general algebraic number field K defined by the irreducible polynomial P with integer coefficients.

If the precision becomes insufficient, `gp`

does not strive to compute
the units by default (*flag* = 0).

When *flag* = 1, we insist on finding the fundamental units exactly. Be
warned that this can take a very long time when the coefficients of the
fundamental units on the integral basis are very large. If the fundamental
units are simply too large to be represented in this form, an error message
is issued. They could be obtained using the so-called compact representation
of algebraic numbers as a formal product of algebraic integers. The latter is
implemented internally but not publicly accessible yet.

*tech* is a technical vector (empty by default, see [**Label: se:GRHbnf**]).
Careful use of this parameter may speed up your computations,
but it is mostly obsolete and you should leave it alone.

The components of a *bnf* or *sbnf* are technical and never used by
the casual user. In fact: *never access a component directly, always use
a proper member function.* However, for the sake of completeness and internal
documentation, their description is as follows. We use the notations
explained in the book by H. Cohen, *A Course in Computational Algebraic
Number Theory*, Graduate Texts in Maths **138**, Springer-Verlag, 1993,
Section 6.5, and subsection 6.5.5 in particular.

*bnf*[1] contains the matrix W, i.e. the matrix in Hermite normal
form giving relations for the class group on prime ideal generators
(**p**_i)_{1 `<=`

i `<=`

r}.

*bnf*[2] contains the matrix B, i.e. the matrix containing the
expressions of the prime ideal factorbase in terms of the **p**_i.
It is an r x c matrix.

*bnf*[3] contains the complex logarithmic embeddings of the system of
fundamental units which has been found. It is an (r_1+r_2) x (r_1+r_2-1)
matrix.

*bnf*[4] contains the matrix M"_C of Archimedean components of the
relations of the matrix (W|B).

*bnf*[5] contains the prime factor base, i.e. the list of prime
ideals used in finding the relations.

*bnf*[6] used to contain a permutation of the prime factor base, but
has been obsoleted. It contains a dummy 0.

*bnf*[7] or

is equal to the number field data
*bnf*.nf*nf* as would be given by `nfinit`

.

*bnf*[8] is a vector containing the classgroup

as a finite abelian group, the regulator *bnf*.clgp

, a 1 (used to
contain an obsolete "check number"), the number of roots of unity and a
generator *bnf*.reg

, the fundamental units *bnf*.tu

.*bnf*.fu

*bnf*[9] is a 3-element row vector used in `bnfisprincipal`

only
and obtained as follows. Let D = U W V obtained by applying the
Smith normal form algorithm to the matrix W ( = *bnf*[1]) and
let U_r be the reduction of U modulo D. The first elements of the
factorbase are given (in terms of `bnf.gen`

) by the columns of U_r,
with Archimedean component g_a; let also GD_a be the Archimedean
components of the generators of the (principal) ideals defined by the
`bnf.gen[i]^bnf.cyc[i]`

. Then *bnf*[9] = [U_r, g_a, GD_a].

*bnf*[10] is by default unused and set equal to 0. This field is used
to store further information about the field as it becomes available, which
is rarely needed, hence would be too expensive to compute during the initial
`bnfinit`

call. For instance, the generators of the principal ideals
`bnf.gen[i]^bnf.cyc[i]`

(during a call to `bnrisprincipal`

), or
those corresponding to the relations in W and B (when the `bnf`

internal precision needs to be increased).

The library syntax is `GEN `

.**bnfinit0**(GEN P, long flag, GEN tech = NULL, long prec)

Also available is `GEN `

,
corresponding to **Buchall**(GEN P, long flag, long prec)`tech = NULL`

, where
`flag`

is either 0 (default) or `nf_FORCE`

(insist on finding
fundamental units). The function
`GEN `

gives direct access to the technical parameters.**Buchall_param**(GEN P, double c1, double c2, long nrpid, long flag, long prec)

Computes a complete system of
solutions (modulo units of positive norm) of the absolute norm equation
Norm(a) = x,
where a is an integer in *bnf*. If *bnf* has not been certified,
the correctness of the result depends on the validity of GRH.

See also `bnfisnorm`

.

The library syntax is `GEN `

.
The function **bnfisintnorm**(GEN bnf, GEN x)`GEN `

returns a complete system of solutions modulo units of the absolute norm
equation |Norm(x) |= |a|. As fast as **bnfisintnormabs**(GEN bnf, GEN a)`bnfisintnorm`

, but solves
the two equations Norm(x) = ± a simultaneously.

Tries to tell whether the
rational number x is the norm of some element y in *bnf*. Returns a
vector [a,b] where x = Norm(a)*b. Looks for a solution which is an S-unit,
with S a certain set of prime ideals containing (among others) all primes
dividing x. If *bnf* is known to be Galois, set *flag* = 0 (in
this case, x is a norm iff b = 1). If *flag* is non zero the program adds to
S the following prime ideals, depending on the sign of *flag*. If *flag* > 0,
the ideals of norm less than *flag*. And if *flag* < 0 the ideals dividing *flag*.

Assuming GRH, the answer is guaranteed (i.e. x is a norm iff b = 1),
if S contains all primes less than 12log(disc(*Bnf*))^2, where
*Bnf* is the Galois closure of *bnf*.

See also `bnfisintnorm`

.

The library syntax is `GEN `

.**bnfisnorm**(GEN bnf, GEN x, long flag)

*bnf* being the
number field data output by `bnfinit`

, and x being an ideal, this
function tests whether the ideal is principal or not. The result is more
complete than a simple true/false answer and solves general discrete
logarithm problem. Assume the class group is oplus (**Z**/d_i**Z**)g_i
(where the generators g_i and their orders d_i are respectively given by
`bnf.gen`

and `bnf.cyc`

). The routine returns a row vector [e,t],
where e is a vector of exponents 0 `<=`

e_i < d_i, and t is a number
field element such that
x = (t) prod_i g_i^{e_i}.
For *given* g_i (i.e. for a given `bnf`

), the e_i are unique,
and t is unique modulo units.

In particular, x is principal if and only if e is the zero vector. Note that the empty vector, which is returned when the class number is 1, is considered to be a zero vector (of dimension 0).

? K = bnfinit(y^2+23); ? K.cyc %2 = [3] ? K.gen %3 = [[2, 0; 0, 1]] \\ a prime ideal above 2 ? P = idealprimedec(K,3)[1]; \\ a prime ideal above 3 ? v = bnfisprincipal(K, P) %5 = [[2]~, [3/4, 1/4]~] ? idealmul(K, v[2], idealfactorback(K, K.gen, v[1])) %6 = [3 0] [0 1] ? % == idealhnf(K, P) %7 = 1

The binary digits of *flag* mean:

***** 1: If set, outputs [e,t] as explained above, otherwise returns
only e, which is much easier to compute. The following idiom only tests
whether an ideal is principal:

is_principal(bnf, x) = !bnfisprincipal(bnf,x,0);

***** 2: It may not be possible to recover t, given the initial accuracy
to which `bnf`

was computed. In that case, a warning is printed and t is
set equal to the empty vector `[]~`

. If this bit is set,
increase the precision and recompute needed quantities until t can be
computed. Warning: setting this may induce *very* lengthy computations.

The library syntax is `GEN `

.
Instead of the above hardcoded numerical flags, one should
rather use an or-ed combination of the symbolic flags **bnfisprincipal0**(GEN bnf, GEN x, long flag)`nf_GEN`

(include
generators, possibly a place holder if too difficult) and `nf_FORCE`

(insist on finding the generators).

*bnf* being output by
`bnfinit`

, *sfu* by `bnfsunit`

, gives the column vector of
exponents of x on the fundamental S-units and the roots of unity.
If x is not a unit, outputs an empty vector.

The library syntax is `GEN `

.**bnfissunit**(GEN bnf, GEN sfu, GEN x)

*bnf* being the number field data
output by `bnfinit`

and x being an algebraic number (type integer,
rational or polmod), this outputs the decomposition of x on the fundamental
units and the roots of unity if x is a unit, the empty vector otherwise.
More precisely, if u_1,...,u_r are the fundamental units, and zeta
is the generator of the group of roots of unity (`bnf.tu`

), the output is
a vector [x_1,...,x_r,x_{r+1}] such that x = u_1^{x_1}...
u_r^{x_r}.zeta^{x_{r+1}}. The x_i are integers for i `<=`

r and is an
integer modulo the order of zeta for i = r+1.

Note that *bnf* need not contain the fundamental unit explicitly:

? setrand(1); bnf = bnfinit(x^2-x-100000); ? bnf.fu *** at top-level: bnf.fu *** ^-- *** _.fu: missing units in .fu. ? u = [119836165644250789990462835950022871665178127611316131167, \ 379554884019013781006303254896369154068336082609238336]~; ? bnfisunit(bnf, u) %3 = [-1, Mod(0, 2)]~The given u is the inverse of the fundamental unit implicitly stored in

The library syntax is `GEN `

.**bnfisunit**(GEN bnf, GEN x)

*bnf* being as output by
`bnfinit`

, computes the narrow class group of *bnf*. The output is
a 3-component row vector v analogous to the corresponding class group
component

(*bnf*.clgp

): the first component
is the narrow class number *bnf*[8][1]`v.no`

, the second component is a vector
containing the SNF cyclic components `v.cyc`

of
the narrow class group, and the third is a vector giving the generators of
the corresponding `v.gen`

cyclic groups. Note that this function is a
special case of `bnrinit`

.

The library syntax is `GEN `

.**buchnarrow**(GEN bnf)

*bnf* being as output by
`bnfinit`

, this computes an r_1 x (r_1+r_2-1) matrix having ±1
components, giving the signs of the real embeddings of the fundamental units.
The following functions compute generators for the totally positive units:

/* exponents of totally positive units generators on bnf.tufu */ tpuexpo(bnf)= { my(S,d,K); S = bnfsignunit(bnf); d = matsize(S); S = matrix(d[1],d[2], i,j, if (S[i,j] < 0, 1,0)); S = concat(vectorv(d[1],i,1), S); \\ add sign(-1) K = lift(matker(S * Mod(1,2))); if (K, mathnfmodid(K, 2), 2*matid(d[1])) } /* totally positive units */ tpu(bnf)= { my(vu = bnf.tufu, ex = tpuexpo(bnf)); vector(#ex-1, i, factorback(vu, ex[,i+1])) \\ ex[,1] is 1 }

The library syntax is `GEN `

.**signunits**(GEN bnf)

Computes the fundamental S-units of the
number field *bnf* (output by `bnfinit`

), where S is a list of
prime ideals (output by `idealprimedec`

). The output is a vector v with
6 components.

v[1] gives a minimal system of (integral) generators of the S-unit group modulo the unit group.

v[2] contains technical data needed by `bnfissunit`

.

v[3] is an empty vector (used to give the logarithmic embeddings of the generators in v[1] in version 2.0.16).

v[4] is the S-regulator (this is the product of the regulator, the determinant of v[2] and the natural logarithms of the norms of the ideals in S).

v[5] gives the S-class group structure, in the usual format (a row vector whose three components give in order the S-class number, the cyclic components and the generators).

v[6] is a copy of S.

The library syntax is `GEN `

.**bnfsunit**(GEN bnf, GEN S, long prec)

Let *bnr* be the number field data output by `bnrinit(,,1)`

and
*H* be a square matrix defining a congruence subgroup of the
ray class group corresponding to *bnr* (the trivial congruence subgroup
if omitted). This function returns, for each character chi of the ray
class group which is trivial on H, the value at s = 1 (or s = 0) of the
abelian L-function associated to chi. For the value at s = 0, the
function returns in fact for each chi a vector [r_chi, c_chi] where
L(s, chi) = c.s^r + O(s^{r + 1})
near 0.

The argument *flag* is optional, its binary digits
mean 1: compute at s = 0 if unset or s = 1 if set, 2: compute the
primitive L-function associated to chi if unset or the L-function
with Euler factors at prime ideals dividing the modulus of *bnr* removed
if set (that is L_S(s, chi), where S is the
set of infinite places of the number field together with the finite prime
ideals dividing the modulus of *bnr*), 3: return also the character if
set.

K = bnfinit(x^2-229); bnr = bnrinit(K,1,1); bnrL1(bnr)

returns the order and the first non-zero term of L(s, chi) at s = 0
where chi runs through the characters of the class group of
K = **Q**(sqrt{229}). Then

bnr2 = bnrinit(K,2,1); bnrL1(bnr2,,2)

returns the order and the first non-zero terms of L_S(s, chi) at s = 0
where chi runs through the characters of the class group of K and S is
the set of infinite places of K together with the finite prime 2. Note
that the ray class group modulo 2 is in fact the class group, so
`bnrL1(bnr2,0)`

returns the same answer as `bnrL1(bnr,0)`

.

This function will fail with the message

*** bnrL1: overflow in zeta_get_N0 [need too many primes].if the approximate functional equation requires us to sum too many terms (if the discriminant of K is too large).

The library syntax is `GEN `

.**bnrL1**(GEN bnr, GEN H = NULL, long flag, long prec)

Let A, B, C define a class field L over a ground field K
(of type `[`

,
*bnr*]`[`

,
or *bnr*, *subgroup*]`[`

,
or *bnf*, *modulus*]`[`

,
Section [*bnf*, *modulus*,*subgroup*]**Label: se:CFT**]); this function returns the relative degree [L:K].

In particular if A is a *bnf* (with units), and B a modulus,
this function returns the corresponding ray class number modulo B.
One can input the associated *bid* (with generators if the subgroup
C is non trivial) for B instead of the module itself, saving some time.

This function is faster than `bnrinit`

and should be used if only the
ray class number is desired. See `bnrclassnolist`

if you need ray class
numbers for all moduli less than some bound.

The library syntax is `GEN `

.
Also available is
**bnrclassno0**(GEN A, GEN B = NULL, GEN C = NULL)`GEN `

to compute the ray class number
modulo f.**bnrclassno**(GEN bnf,GEN f)

*bnf* being as
output by `bnfinit`

, and *list* being a list of moduli (with units) as
output by `ideallist`

or `ideallistarch`

, outputs the list of the
class numbers of the corresponding ray class groups. To compute a single
class number, `bnrclassno`

is more efficient.

? bnf = bnfinit(x^2 - 2); ? L = ideallist(bnf, 100, 2); ? H = bnrclassnolist(bnf, L); ? H[98] %4 = [1, 3, 1] ? l = L[1][98]; ids = vector(#l, i, l[i].mod[1]) %5 = [[98, 88; 0, 1], [14, 0; 0, 7], [98, 10; 0, 1]]

The weird `l[i].mod[1]`

, is the first component of `l[i].mod`

, i.e.
the finite part of the conductor. (This is cosmetic: since by construction
the Archimedean part is trivial, I do not want to see it). This tells us that
the ray class groups modulo the ideals of norm 98 (printed as `%5`

) have
respectively order 1, 3 and 1. Indeed, we may check directly:

? bnrclassno(bnf, ids[2]) %6 = 3

The library syntax is `GEN `

.**bnrclassnolist**(GEN bnf, GEN list)

Conductor f of the subfield of a ray class field as defined by [A,B,C]
(of type `[`

,
*bnr*]`[`

,
*bnr*, *subgroup*]`[`

or
*bnf*, *modulus*]`[`

,
Section [*bnf*, *modulus*, *subgroup*]**Label: se:CFT**])

If *flag* = 0, returns f.

If *flag* = 1, returns [f, Cl_f, H], where Cl_f is the ray class group
modulo f, as a finite abelian group; finally H is the subgroup of Cl_f
defining the extension.

If *flag* = 2, returns [f, *bnr*(f), H], as above except Cl_f is
replaced by a `bnr`

structure, as output by `bnrinit`

(,f,1).

The library syntax is `GEN `

.**bnrconductor0**(GEN A, GEN B = NULL, GEN C = NULL, long flag)

Also available is `GEN `

**bnrconductor**(GEN bnr, GEN H, long flag)

*bnr* being a big
ray number field as output by `bnrinit`

, and *chi* being a row vector
representing a character as expressed on the generators of the ray
class group, gives the conductor of this character as a modulus.

The library syntax is `GEN `

.**bnrconductorofchar**(GEN bnr, GEN chi)

A, B, C defining a class field L over a ground field K
(of type `[`

,
*bnr*]`[`

,
*bnr*, *subgroup*]`[`

or
*bnf*, *modulus*]`[`

,
Section [*bnf*, *modulus*, *subgroup*]**Label: se:CFT**]), outputs data [N,r_1,D] giving the discriminant and
signature of L, depending on the binary digits of *flag*:

***** 1: if this bit is unset, output absolute data related to L/**Q**:
N is the absolute degree [L:**Q**], r_1 the number of real places of L,
and D the discriminant of L/**Q**. Otherwise, output relative data for L/K:
N is the relative degree [L:K], r_1 is the number of real places of K
unramified in L (so that the number of real places of L is equal to r_1
times N), and D is the relative discriminant ideal of L/K.

***** 2: if this bit is set and if the modulus is not the conductor of L,
only return 0.

The library syntax is `GEN `

.**bnrdisc0**(GEN A, GEN B = NULL, GEN C = NULL, long flag)

*bnf* being as output by `bnfinit`

(with units), computes a
list of discriminants of Abelian extensions of the number field by increasing
modulus norm up to bound *bound*. The ramified Archimedean places are
given by *arch*; all possible values are taken if *arch* is omitted.

The alternative syntax `bnrdisclist`

(*bnf*,*list*) is
supported, where *list* is as output by `ideallist`

or
`ideallistarch`

(with units), in which case *arch* is disregarded.

The output v is a vector of vectors, where v[i][j] is understood to be in fact V[2^{15}(i-1)+j] of a unique big vector V. (This awkward scheme allows for larger vectors than could be otherwise represented.)

V[k] is itself a vector W, whose length is the number of ideals of norm
k. We consider first the case where *arch* was specified. Each
component of W corresponds to an ideal m of norm k, and
gives invariants associated to the ray class field L of *bnf* of
conductor [m, *arch*]. Namely, each contains a vector [m,d,r,D] with
the following meaning: m is the prime ideal factorization of the modulus,
d = [L:**Q**] is the absolute degree of L, r is the number of real places
of L, and D is the factorization of its absolute discriminant. We set d
= r = D = 0 if m is not the finite part of a conductor.

If *arch* was omitted, all t = 2^{r_1} possible values are taken and a
component of W has the form [m, [[d_1,r_1,D_1],..., [d_t,r_t,D_t]]],
where m is the finite part of the conductor as above, and
[d_i,r_i,D_i] are the invariants of the ray class field of conductor
[m,v_i], where v_i is the i-th Archimedean component, ordered by
inverse lexicographic order; so v_1 = [0,...,0], v_2 = [1,0...,0],
etc. Again, we set d_i = r_i = D_i = 0 if [m,v_i] is not a conductor.

Finally, each prime ideal pr = [p,alpha,e,f,beta] in the prime factorization m is coded as the integer p.n^2+(f-1).n+(j-1), where n is the degree of the base field and j is such that

`pr = idealprimedec(`

.*nf*,p)[j]

m can be decoded using `bnfdecodemodule`

.

Note that to compute such data for a single field, either `bnrclassno`

or `bnrdisc`

is more efficient.

The library syntax is `GEN `

.**bnrdisclist0**(GEN bnf, GEN bound, GEN arch = NULL)

*bnf* is as
output by `bnfinit`

, f is a modulus, initializes data linked to
the ray class group structure corresponding to this module, a so-called
*bnr* structure. One can input the associated *bid* with generators
for f instead of the module itself, saving some time.
(As in `idealstar`

, the finite part of the conductor may be given
by a factorization into prime ideals, as produced by `idealfactor`

.)

The following member functions are available
on the result: `.bnf`

is the underlying *bnf*,
`.mod`

the modulus, `.bid`

the *bid* structure associated to the
modulus; finally, `.clgp`

, `.no`

, `.cyc`

, `.gen`

refer to the
ray class group (as a finite abelian group), its cardinality, its elementary
divisors, its generators (only computed if *flag* = 1).

The last group of functions are different from the members of the underlying
*bnf*, which refer to the class group; use

to access these, e.g. *bnr*.bnf.*xxx*

to get the cyclic decomposition
of the class group.*bnr*.bnf.cyc

They are also different from the members of the underlying *bid*, which
refer to (**Z**_K/f)^*; use

to access these,
e.g. *bnr*.bid.*xxx*

to get phi(f).*bnr*.bid.no

If *flag* = 0 (default), the generators of the ray class group are not computed,
which saves time. Hence

would produce an error.*bnr*.gen

If *flag* = 1, as the default, except that generators are computed.

The library syntax is `GEN `

.
Instead the above hardcoded numerical flags, one should rather use
**bnrinit0**(GEN bnf, GEN f, long flag)`GEN `

where flag is an or-ed combination of **Buchray**(GEN bnf, GEN module, long flag)`nf_GEN`

(include generators)
and `nf_INIT`

(if omitted, return just the cardinal of the ray class group
and its structure), possibly 0.

A, B, C represent
an extension of the base field, given by class field theory
(see Section [**Label: se:CFT**]). Outputs 1 if this modulus is the conductor, and 0
otherwise. This is slightly faster than `bnrconductor`

.

The library syntax is `long `

.**bnrisconductor0**(GEN A, GEN B = NULL, GEN C = NULL)

*bnr* being the
number field data which is output by `bnrinit`

(,,1) and x being an
ideal in any form, outputs the components of x on the ray class group
generators in a way similar to `bnfisprincipal`

. That is a 2-component
vector v where v[1] is the vector of components of x on the ray class
group generators, v[2] gives on the integral basis an element alpha such
that x = alphaprod_ig_i^{x_i}.

If *flag* = 0, outputs only v_1. In that case, *bnr* need not contain the
ray class group generators, i.e. it may be created with `bnrinit`

(,,0)
If x is not coprime to the modulus of *bnr* the result is undefined.

The library syntax is `GEN `

.
Instead of hardcoded numerical flags, one should rather
use
**bnrisprincipal**(GEN bnr, GEN x, long flag)`GEN `

for **isprincipalray**(GEN bnr, GEN x)`flag`

= 0, and if you
want generators:

bnrisprincipal(bnr, x, nf_GEN)

If chi = *chi* is a
character over *bnr*, not necessarily primitive, let
L(s,chi) = sum_{id} chi(id) N(id)^{-s} be the associated
Artin L-function. Returns the so-called Artin root number, i.e. the
complex number W(chi) of modulus 1 such that

Lambda(1-s,chi) = W(chi) Lambda(s,\overline{chi})

where Lambda(s,chi) = A(chi)^{s/2}gamma_chi(s) L(s,chi) is the enlarged L-function associated to L.

The generators of the ray class group are needed, and you can set *flag* = 1 if
the character is known to be primitive. Example:

bnf = bnfinit(x^2 - x - 57); bnr = bnrinit(bnf, [7,[1,1]], 1); bnrrootnumber(bnr, [2,1])

returns the root number of the character chi of
Cl_{7 oo _1 oo _2}(**Q**(sqrt{229})) defined by chi(g_1^ag_2^b)
= zeta_1^{2a}zeta_2^b. Here g_1, g_2 are the generators of the
ray-class group given by `bnr.gen`

and zeta_1 = e^{2iPi/N_1},
zeta_2 = e^{2iPi/N_2} where N_1, N_2 are the orders of g_1 and
g_2 respectively (N_1 = 6 and N_2 = 3 as `bnr.cyc`

readily tells us).

The library syntax is `GEN `

.**bnrrootnumber**(GEN bnr, GEN chi, long flag, long prec)

*bnr* being as output by `bnrinit(,,1)`

, finds a relative equation
for the class field corresponding to the modulus in *bnr* and the given
congruence subgroup (as usual, omit *subgroup* if you want the whole ray
class group).

The main variable of *bnr* must not be x, and the ground field and the
class field must be totally real. When the base field is **Q**, the vastly
simpler `galoissubcyclo`

is used instead. Here is an example:

bnf = bnfinit(y^2 - 3); bnr = bnrinit(bnf, 5, 1); bnrstark(bnr)

returns the ray class field of **Q**(sqrt{3}) modulo 5. Usually, one wants
to apply to the result one of

rnfpolredabs(bnf, pol, 16) \\ compute a reduced relative polynomial rnfpolredabs(bnf, pol, 16 + 2) \\ compute a reduced absolute polynomial

The routine uses Stark units and needs to find a suitable auxiliary
conductor, which may not exist when the class field is not cyclic over the
base. In this case `bnrstark`

is allowed to return a vector of
polynomials defining *independent* relative extensions, whose compositum
is the requested class field. It was decided that it was more useful
to keep the extra information thus made available, hence the user has to take
the compositum herself.

Even if it exists, the auxiliary conductor may be so large that later
computations become unfeasible. (And of course, Stark's conjecture may simply
be wrong.) In case of difficulties, try `rnfkummer`

:

? bnr = bnrinit(bnfinit(y^8-12*y^6+36*y^4-36*y^2+9,1), 2, 1); ? bnrstark(bnr) *** at top-level: bnrstark(bnr) *** ^------------- *** bnrstark: need 3919350809720744 coefficients in initzeta. *** Computation impossible. ? lift( rnfkummer(bnr) ) time = 24 ms. %2 = x^2 + (1/3*y^6 - 11/3*y^4 + 8*y^2 - 5)

The library syntax is `GEN `

.**bnrstark**(GEN bnr, GEN subgroup = NULL, long prec)

Gives as a vector the first b
coefficients of the Dedekind zeta function of the number field *nf*
considered as a Dirichlet series.

The library syntax is `GEN `

.**dirzetak**(GEN nf, GEN b)

Factorization of the univariate polynomial x
over the number field defined by the (univariate) polynomial t. x may
have coefficients in **Q** or in the number field. The algorithm reduces to
factorization over **Q** (Trager's trick). The direct approach of
`nffactor`

, which uses van Hoeij's method in a relative setting, is
in general faster.

The main variable of t must be of *lower* priority than that of x
(see Section [**Label: se:priority**]). However if non-rational number field elements
occur (as polmods or polynomials) as coefficients of x, the variable of
these polmods *must* be the same as the main variable of t. For
example

? factornf(x^2 + Mod(y, y^2+1), y^2+1); ? factornf(x^2 + y, y^2+1); \\ these two are OK ? factornf(x^2 + Mod(z,z^2+1), y^2+1) *** at top-level: factornf(x^2+Mod(z,z *** ^-------------------- *** factornf: inconsistent data in rnf function. ? factornf(x^2 + z, y^2+1) *** at top-level: factornf(x^2+z,y^2+1 *** ^-------------------- *** factornf: incorrect variable in rnf function.

The library syntax is `GEN `

.**polfnf**(GEN x, GEN t)

*gal* being be a Galois group as output by `galoisinit`

,
export the underlying permutation group as a string suitable
for (no flags or *flag* = 0) GAP or (*flag* = 1) Magma. The following example
compute the index of the underlying abstract group in the GAP library:

? G = galoisinit(x^6+108); ? s = galoisexport(G) %2 = "Group((1, 2, 3)(4, 5, 6), (1, 4)(2, 6)(3, 5))" ? extern("echo \"IdGroup("s");\" | gap -q") %3 = [6, 1] ? galoisidentify(G) %4 = [6, 1]

This command also accepts subgroups returned by `galoissubgroups`

.

To *import* a GAP permutation into gp (for `galoissubfields`

for
instance), the following GAP function may be useful:

PermToGP := function(p, n) return Permuted([1..n],p); end; gap> p:= (1,26)(2,5)(3,17)(4,32)(6,9)(7,11)(8,24)(10,13)(12,15)(14,27) (16,22)(18,28)(19,20)(21,29)(23,31)(25,30) gap> PermToGP(p,32); [ 26, 5, 17, 32, 2, 9, 11, 24, 6, 13, 7, 15, 10, 27, 12, 22, 3, 28, 20, 19, 29, 16, 31, 8, 30, 1, 14, 18, 21, 25, 23, 4 ]

The library syntax is `GEN `

.**galoisexport**(GEN gal, long flag)

*gal* being be a Galois group as output by `galoisinit`

and
*perm* an element of *gal*.group, a vector of such elements
or a subgroup of *gal* as returned by galoissubgroups,
computes the fixed field of *gal* by the automorphism defined by the
permutations *perm* of the roots *gal*.roots. P is guaranteed to
be squarefree modulo *gal*.p.

If no flags or *flag* = 0, output format is the same as for `nfsubfield`

,
returning [P,x] such that P is a polynomial defining the fixed field, and
x is a root of P expressed as a polmod in *gal*.pol.

If *flag* = 1 return only the polynomial P.

If *flag* = 2 return [P,x,F] where P and x are as above and F is the
factorization of *gal*.pol over the field defined by P, where
variable v (y by default) stands for a root of P. The priority of v
must be less than the priority of the variable of *gal*.pol (see
Section [**Label: se:priority**]). Example:

? G = galoisinit(x^4+1); ? galoisfixedfield(G,G.group[2],2) %2 = [x^2 + 2, Mod(x^3 + x, x^4 + 1), [x^2 - y*x - 1, x^2 + y*x - 1]]

computes the factorization x^4+1 = (x^2-sqrt{-2}x-1)(x^2+sqrt{-2}x-1)

The library syntax is `GEN `

, where **galoisfixedfield**(GEN gal, GEN perm, long flag, long v = -1)`v`

is a variable number.

Query the galpol package for a polynomial with Galois group isomorphic to
GAP4(a,b), totally real if s = 1 (default) and totally complex if s = 2. The
output is a vector [`pol`

, `den`

] where

***** `pol`

is the polynomial of degree a

***** `den`

is the denominator of `nfgaloisconj(pol)`

.
Pass it as an optional argument to `galoisinit`

or `nfgaloisconj`

to
speed them up:

? [pol,den] = galoisgetpol(64,4,1); ? G = galoisinit(pol); time = 352ms ? galoisinit(pol, den); \\ passing 'den' speeds up the computation time = 264ms ? % == %` %4 = 1 \\ same answer

If b and s are omitted, return the number of isomorphism classes of groups of order a.

The library syntax is `GEN `

.
Also available is **galoisgetpol**(long a, long b, long s)`GEN `

when b and s
are omitted.**galoisnbpol**(long a)

*gal* being be a Galois group as output by `galoisinit`

,
output the isomorphism class of the underlying abstract group as a
two-components vector [o,i], where o is the group order, and i is the
group index in the GAP4 Small Group library, by Hans Ulrich Besche, Bettina
Eick and Eamonn O'Brien.

This command also accepts subgroups returned by `galoissubgroups`

.

The current implementation is limited to degree less or equal to 127. Some larger "easy" orders are also supported.

The output is similar to the output of the function `IdGroup`

in GAP4.
Note that GAP4 `IdGroup`

handles all groups of order less than 2000
except 1024, so you can use `galoisexport`

and GAP4 to identify large
Galois groups.

The library syntax is `GEN `

.**galoisidentify**(GEN gal)

Computes the Galois group
and all necessary information for computing the fixed fields of the
Galois extension K/**Q** where K is the number field defined by
*pol* (monic irreducible polynomial in **Z**[X] or
a number field as output by `nfinit`

). The extension K/**Q** must be
Galois with Galois group "weakly" super-solvable, see below;
returns 0 otherwise. Hence this permits to quickly check whether a polynomial
of order strictly less than 36 is Galois or not.

The algorithm used is an improved version of the paper "An efficient algorithm for the computation of Galois automorphisms", Bill Allombert, Math. Comp, vol. 73, 245, 2001, pp. 359--375.

A group G is said to be "weakly" super-solvable if there exists a normal series

{1} = H_0 \triangleleft H_1 \triangleleft...\triangleleft H_{n-1} \triangleleft H_n

such that each H_i is normal in G and for i < n, each quotient group H_{i+1}/H_i is cyclic, and either H_n = G (then G is super-solvable) or G/H_n is isomorphic to either A_4 or S_4.

In practice, almost all small groups are WKSS, the exceptions having order 36(1 exception), 48(2), 56(1), 60(1), 72(5), 75(1), 80(1), 96(10) and \geq 108.

This function is a prerequisite for most of the `galois`

xxx routines.
For instance:

P = x^6 + 108; G = galoisinit(P); L = galoissubgroups(G); vector(#L, i, galoisisabelian(L[i],1)) vector(#L, i, galoisidentify(L[i]))

The output is an 8-component vector *gal*.

*gal*[1] contains the polynomial *pol*
(

).*gal*.pol

*gal*[2] is a three-components vector [p,e,q] where p is a
prime number (

) such that *gal*.p*pol* totally split
modulo p , e is an integer and q = p^e (

) is the
modulus of the roots in *gal*.mod

.*gal*.roots

*gal*[3] is a vector L containing the p-adic roots of
*pol* as integers implicitly modulo

.
(*gal*.mod

).*gal*.roots

*gal*[4] is the inverse of the Vandermonde matrix of the
p-adic roots of *pol*, multiplied by *gal*[5].

*gal*[5] is a multiple of the least common denominator of the
automorphisms expressed as polynomial in a root of *pol*.

*gal*[6] is the Galois group G expressed as a vector of
permutations of L (

).*gal*.group

*gal*[7] is a generating subset S = [s_1,...,s_g] of G
expressed as a vector of permutations of L (

).*gal*.gen

*gal*[8] contains the relative orders [o_1,...,o_g] of
the generators of S (

).*gal*.orders

Let H_n be as above, we have the following properties:

***** if G/H_n ~ A_4 then [o_1,...,o_g] ends by
[2,2,3].

***** if G/H_n ~ S_4 then [o_1,...,o_g] ends by
[2,2,3,2].

***** for 1 `<=`

i `<=`

g the subgroup of G generated by
[s_1,...,s_g] is normal, with the exception of i = g-2 in the
A_4 case and of i = g-3 in the S_A case.

***** the relative order o_i of s_i is its order in the
quotient group G/`<`

s_1,...,s_{i-1}`>`

, with the same
exceptions.

***** for any x belongs to G there exists a unique family
[e_1,...,e_g] such that (no exceptions):

-- for 1 `<=`

i `<=`

g we have 0 `<=`

e_i < o_i

-- x = g_1^{e_1}g_2^{e_2}...g_n^{e_n}

If present den must be a suitable value for *gal*[5].

The library syntax is `GEN `

.**galoisinit**(GEN pol, GEN den = NULL)

*gal* being as output by `galoisinit`

, return 0 if
*gal* is not an abelian group, and the HNF matrix of *gal* over
`gal.gen`

if fl = 0, 1 if fl = 1.

This command also accepts subgroups returned by `galoissubgroups`

.

The library syntax is `GEN `

.**galoisisabelian**(GEN gal, long flag)

*gal* being as output by `galoisinit`

, and *subgrp* a subgroup
of *gal* as output by `galoissubgroups`

,return 1 if *subgrp* is a
normal subgroup of *gal*, else return 0.

This command also accepts subgroups returned by `galoissubgroups`

.

The library syntax is `long `

.**galoisisnormal**(GEN gal, GEN subgrp)

*gal* being a
Galois group as output by `galoisinit`

and *perm* a element of
*gal*.group, return the polynomial defining the Galois
automorphism, as output by `nfgaloisconj`

, associated with the
permutation *perm* of the roots *gal*.roots. *perm* can
also be a vector or matrix, in this case, `galoispermtopol`

is
applied to all components recursively.

Note that

G = galoisinit(pol); galoispermtopol(G, G[6])~

is equivalent to `nfgaloisconj(pol)`

, if degree of *pol* is greater
or equal to 2.

The library syntax is `GEN `

.**galoispermtopol**(GEN gal, GEN perm)

Computes the subextension
of **Q**(zeta_n) fixed by the subgroup H \subset (**Z**/n**Z**)^*. By the
Kronecker-Weber theorem, all abelian number fields can be generated in this
way (uniquely if n is taken to be minimal).

The pair (n, H) is deduced from the parameters (N, H) as follows

***** N an integer: then n = N; H is a generator, i.e. an
integer or an integer modulo n; or a vector of generators.

***** N the output of `znstar(n)`

. H as in the first case
above, or a matrix, taken to be a HNF left divisor of the SNF for (**Z**/n**Z**)^*
(of type `N.cyc`

), giving the generators of H in terms of `N.gen`

.

***** N the output of `bnrinit(bnfinit(y), m, 1)`

where m is a
module. H as in the first case, or a matrix taken to be a HNF left
divisor of the SNF for the ray class group modulo m
(of type `N.cyc`

), giving the generators of H in terms of `N.gen`

.

In this last case, beware that H is understood relatively to N; in
particular, if the infinite place does not divide the module, e.g if m is
an integer, then it is not a subgroup of (**Z**/n**Z**)^*, but of its quotient by
{± 1}.

If fl = 0, compute a polynomial (in the variable *v*) defining the
the subfield of **Q**(zeta_n) fixed by the subgroup *H* of (**Z**/n**Z**)^*.

If fl = 1, compute only the conductor of the abelian extension, as a module.

If fl = 2, output [pol, N], where pol is the polynomial as output when fl = 0 and N the conductor as output when fl = 1.

The following function can be used to compute all subfields of
**Q**(zeta_n) (of exact degree `d`

, if `d`

is set):

polsubcyclo(n, d = -1)= { my(bnr,L,IndexBound); IndexBound = if (d < 0, n, [d]); bnr = bnrinit(bnfinit(y), [n,[1]], 1); L = subgrouplist(bnr, IndexBound, 1); vector(#L,i, galoissubcyclo(bnr,L[i])); }

Setting `L = subgrouplist(bnr, IndexBound)`

would produce subfields of exact
conductor n oo .

The library syntax is `GEN `

, where **galoissubcyclo**(GEN N, GEN H = NULL, long fl, long v = -1)`v`

is a variable number.

Outputs all the subfields of the Galois group *G*, as a vector.
This works by applying `galoisfixedfield`

to all subgroups. The meaning of
the flag *fl* is the same as for `galoisfixedfield`

.

The library syntax is `GEN `

, where **galoissubfields**(GEN G, long flags, long v = -1)`v`

is a variable number.

Outputs all the subgroups of the Galois group `gal`

. A subgroup is a
vector [*gen*, *orders*], with the same meaning
as for *gal*.gen and *gal*.orders. Hence *gen* is a vector of
permutations generating the subgroup, and *orders* is the relatives
orders of the generators. The cardinal of a subgroup is the product of the
relative orders. Such subgroup can be used instead of a Galois group in the
following command: `galoisisabelian`

, `galoissubgroups`

,
`galoisexport`

and `galoisidentify`

.

To get the subfield fixed by a subgroup *sub* of *gal*, use

galoisfixedfield(gal,sub[1])

The library syntax is `GEN `

.**galoissubgroups**(GEN G)

Sum of the two ideals x and y in the number field *nf*. The
result is given in HNF.

? K = nfinit(x^2 + 1); ? a = idealadd(K, 2, x + 1) \\ ideal generated by 2 and 1+I %2 = [2 1] [0 1] ? pr = idealprimedec(K, 5)[1]; \\ a prime ideal above 5 ? idealadd(K, a, pr) \\ coprime, as expected %4 = [1 0] [0 1]

This function cannot be used to add arbitrary **Z**-modules, since it assumes
that its arguments are ideals:

? b = Mat([1,0]~); ? idealadd(K, b, b) \\ only square t_MATs represent ideals *** idealadd: non-square t_MAT in idealtyp. ? c = [2, 0; 2, 0]; idealadd(K, c, c) \\ non-sense %6 = [2 0] [0 2] ? d = [1, 0; 0, 2]; idealadd(K, d, d) \\ non-sense %7 = [1 0] [0 1]In the last two examples, we get wrong results since the matrices c and d do not correspond to an ideal: the

`K.zk`

) is not an O_K-module. To add arbitrary `mathnf(concat(A,B))`

.
The library syntax is `GEN `

.**idealadd**(GEN nf, GEN x, GEN y)

x and y being two co-prime integral ideals (given in any form), this gives a two-component row vector [a,b] such that a belongs to x, b belongs to y and a+b = 1.

The alternative syntax `idealaddtoone`

(*nf*,v), is supported, where
v is a k-component vector of ideals (given in any form) which sum to
**Z**_K. This outputs a k-component vector e such that e[i] belongs to x[i] for
1 `<=`

i `<=`

k and sum_{1 `<=`

i `<=`

k}e[i] = 1.

The library syntax is `GEN `

.**idealaddtoone0**(GEN nf, GEN x, GEN y = NULL)

If x is a fractional ideal
(given in any form), gives an element alpha in *nf* such that for
all prime ideals **p** such that the valuation of x at **p** is
non-zero, we have v_{**p**}(alpha) = v_{**p**}(x), and
v_{**p**}(alpha) `>=`

0 for all other **p**.

If *flag* is non-zero, x must be given as a prime ideal factorization, as
output by `idealfactor`

, but possibly with zero or negative exponents.
This yields an element alpha such that for all prime ideals **p**
occurring in x, v_{**p**}(alpha) is equal to the exponent of
**p** in x, and for all other prime ideals,
v_{**p**}(alpha) `>=`

0. This generalizes `idealappr`

(*nf*,x,0)
since zero exponents are allowed. Note that the algorithm used is slightly
different, so that

idealappr(nf, idealfactor(nf,x))

may not be the same as `idealappr(nf,x,1)`

.

The library syntax is `GEN `

.**idealappr0**(GEN nf, GEN x, long flag)

x being a prime ideal factorization
(i.e. a 2 by 2 matrix whose first column contains prime ideals, and the second
column integral exponents), y a vector of elements in *nf* indexed by
the ideals in x, computes an element b such that

v_{**p**}(b - y_{**p**}) `>=`

v_{**p**}(x) for all prime ideals
in x and v_{**p**}(b) `>=`

0 for all other **p**.

The library syntax is `GEN `

.**idealchinese**(GEN nf, GEN x, GEN y)

Given two integral ideals x and y
in the number field *nf*, returns a beta in the field,
such that beta.x is an integral ideal coprime to y.

The library syntax is `GEN `

.**idealcoprime**(GEN nf, GEN x, GEN y)

Quotient x.y^{-1} of the two ideals x and y in the number
field *nf*. The result is given in HNF.

If *flag* is non-zero, the quotient x.y^{-1} is assumed to be an
integral ideal. This can be much faster when the norm of the quotient is
small even though the norms of x and y are large.

The library syntax is `GEN `

.
Also available are **idealdiv0**(GEN nf, GEN x, GEN y, long flag)`GEN `

(**idealdiv**(GEN nf, GEN x, GEN y)*flag* = 0) and `GEN `

(**idealdivexact**(GEN nf, GEN x, GEN y)*flag* = 1).

Factors into prime ideal powers the
ideal x in the number field *nf*. The output format is similar to the
`factor`

function, and the prime ideals are represented in the form
output by the `idealprimedec`

function, i.e. as 5-element vectors.

The library syntax is `GEN `

.**idealfactor**(GEN nf, GEN x)

Gives back the ideal corresponding to a factorization. The integer 1 corresponds to the empty factorization. If e is present, e and f must be vectors of the same length (e being integral), and the corresponding factorization is the product of the f[i]^{e[i]}.

If not, and f is vector, it is understood as in the preceding case with e
a vector of 1s: we return the product of the f[i]. Finally, f can be a
regular factorization, as produced by `idealfactor`

.

? nf = nfinit(y^2+1); idealfactor(nf, 4 + 2*y) %1 = [[2, [1, 1]~, 2, 1, [1, 1]~] 2] [[5, [2, 1]~, 1, 1, [-2, 1]~] 1] ? idealfactorback(nf, %) %2 = [10 4] [0 2] ? f = %1[,1]; e = %1[,2]; idealfactorback(nf, f, e) %3 = [10 4] [0 2] ? % == idealhnf(nf, 4 + 2*y) %4 = 1

If `flag`

is non-zero, perform ideal reductions (`idealred`

) along the
way. This is most useful if the ideals involved are all *extended*
ideals (for instance with trivial principal part), so that the principal parts
extracted by `idealred`

are not lost. Here is an example:

? f = vector(#f, i, [f[i], [;]]); \\ transform to extended ideals ? idealfactorback(nf, f, e, 1) %6 = [[1, 0; 0, 1], [2, 1; [2, 1]~, 1]] ? nffactorback(nf, %[2]) %7 = [4, 2]~

The extended ideal returned in `%6`

is the trivial ideal 1, extended
with a principal generator given in factored form. We use `nffactorback`

to recover it in standard form.

The library syntax is `GEN `

.**idealfactorback**(GEN nf, GEN f, GEN e = NULL, long flag )

Let K be the number field defined by nf and assume K/**Q** be a
Galois extension with Galois group given `gal = galoisinit(nf)`

,
and that pr is the prime ideal **P** in prid format, and that
**P** is unramified.
This function returns a permutation of `gal.group`

which defines the
automorphism sigma = (**P**\over K/**Q** ), i.e the Frobenius
element associated to **P**. If p is the unique prime number
in **P**, then sigma(x) = x^p mod \P for all x belongs to **Z**_K.

? nf = nfinit(polcyclo(31)); ? gal = galoisinit(nf); ? pr = idealprimedec(nf,101)[1]; ? g = idealfrobenius(nf,gal,pr); ? galoispermtopol(gal,g) %5 = x^8This is correct since 101 = 8 mod 31.

The library syntax is `GEN `

.**idealfrobenius**(GEN nf, GEN gal, GEN pr)

Gives the Hermite normal form of the ideal u**Z**_K+v**Z**_K, where u
and v are elements of the number field K defined by `nf`

.

? nf = nfinit(y^3 - 2); ? idealhnf(nf, 2, y+1) %2 = [1 0 0] [0 1 0] [0 0 1] ? idealhnf(nf, y/2, [0,0,1/3]~) %3 = [1/3 0 0] [0 1/6 0] [0 0 1/6]

If b is omitted, returns the HNF of the ideal defined by u: u may be an
algebraic number (defining a principal ideal), a maximal ideal (as given by
`idealprimedec`

or `idealfactor`

), or a matrix whose columns give
generators for the ideal. This last format is a little complicated, but
useful to reduce general modules to the canonical form once in a while:

***** if strictly less than N = [K:**Q**] generators are given, u
is the **Z**_K-module they generate,

***** if N or more are given, it is *assumed* that they form a
**Z**-basis of the ideal, in particular that the matrix has maximal rank N.
This acts as `mathnf`

since the **Z**_K-module structure is (taken for
granted hence) not taken into account in this case.

? idealhnf(nf, idealprimedec(nf,2)[1]) %4 = [2 0 0] [0 1 0] [0 0 1] ? idealhnf(nf, [1,2;2,3;3,4]) %5 = [1 0 0] [0 1 0] [0 0 1]Finally, when K is quadratic with discriminant D_K, we allow u =

`Qfb(a,b,c)`

, provided b^2 - 4ac = D_K. As usual,
this represents the ideal a

? K = nfinit(x^2 - 60); K.disc %1 = 60 ? idealhnf(K, qfbprimeform(60,2)) %2 = [2 1] [0 1] ? idealhnf(K, Qfb(1,2,3)) *** at top-level: idealhnf(K,Qfb(1,2,3 *** ^-------------------- *** idealhnf: Qfb(1, 2, 3) has discriminant != 60 in idealhnf.

The library syntax is `GEN `

.
Also available is **idealhnf0**(GEN nf, GEN u, GEN v = NULL)`GEN `

.**idealhnf**(GEN nf, GEN a)

Intersection of the two ideals
A and B in the number field *nf*. The result is given in HNF.

? nf = nfinit(x^2+1); ? idealintersect(nf, 2, x+1) %2 = [2 0] [0 2]

This function does not apply to general **Z**-modules, e.g. orders, since its
arguments are replaced by the ideals they generate. The following script
intersects **Z**-modules A and B given by matrices of compatible
dimensions with integer coefficients:

ZM_intersect(A,B) = { my(Ker = matkerint(concat(A,B))); mathnf( A * Ker[1..#A,] ) }

The library syntax is `GEN `

.**idealintersect**(GEN nf, GEN A, GEN B)

Inverse of the ideal x in the
number field *nf*, given in HNF. If x is an extended
ideal, its principal part is suitably
updated: i.e. inverting [I,t], yields [I^{-1}, 1/t].

The library syntax is `GEN `

.**idealinv**(GEN nf, GEN x)

Computes the list
of all ideals of norm less or equal to *bound* in the number field
*nf*. The result is a row vector with exactly *bound* components.
Each component is itself a row vector containing the information about
ideals of a given norm, in no specific order, depending on the value of
*flag*:

The possible values of *flag* are:

0: give the *bid* associated to the ideals, without generators.

1: as 0, but include the generators in the *bid*.

2: in this case, *nf* must be a *bnf* with units. Each
component is of the form [*bid*,U], where *bid* is as case 0
and U is a vector of discrete logarithms of the units. More precisely, it
gives the `ideallog`

s with respect to *bid* of `bnf.tufu`

.
This structure is technical, and only meant to be used in conjunction with
`bnrclassnolist`

or `bnrdisclist`

.

3: as 2, but include the generators in the *bid*.

4: give only the HNF of the ideal.

? nf = nfinit(x^2+1); ? L = ideallist(nf, 100); ? L[1] %3 = [[1, 0; 0, 1]] \\ A single ideal of norm 1 ? #L[65] %4 = 4 \\ There are 4 ideals of norm 4 inZ[i]

If one wants more information, one could do instead:

? nf = nfinit(x^2+1); ? L = ideallist(nf, 100, 0); ? l = L[25]; vector(#l, i, l[i].clgp) %3 = [[20, [20]], [16, [4, 4]], [20, [20]]] ? l[1].mod %4 = [[25, 18; 0, 1], []] ? l[2].mod %5 = [[5, 0; 0, 5], []] ? l[3].mod %6 = [[25, 7; 0, 1], []]where we ask for the structures of the (

`ideallistarch`

to treat general moduli.
The library syntax is `GEN `

.**ideallist0**(GEN nf, long bound, long flag)

*list* is a vector of vectors of bid's, as output by `ideallist`

with
flag 0 to 3. Return a vector of vectors with the same number of
components as the original *list*. The leaves give information about
moduli whose finite part is as in original list, in the same order, and
Archimedean part is now *arch* (it was originally trivial). The
information contained is of the same kind as was present in the input; see
`ideallist`

, in particular the meaning of *flag*.

? bnf = bnfinit(x^2-2); ? bnf.sign %2 = [2, 0] \\ two places at infinity ? L = ideallist(bnf, 100, 0); ? l = L[98]; vector(#l, i, l[i].clgp) %4 = [[42, [42]], [36, [6, 6]], [42, [42]]] ? La = ideallistarch(bnf, L, [1,1]); \\ add them to the modulus ? l = La[98]; vector(#l, i, l[i].clgp) %6 = [[168, [42, 2, 2]], [144, [6, 6, 2, 2]], [168, [42, 2, 2]]]

Of course, the results above are obvious: adding t places at infinity will
add t copies of **Z**/2**Z** to the ray class group. The following application
is more typical:

? L = ideallist(bnf, 100, 2); \\ units are required now ? La = ideallistarch(bnf, L, [1,1]); ? H = bnrclassnolist(bnf, La); ? H[98]; %6 = [2, 12, 2]

The library syntax is `GEN `

.**ideallistarch**(GEN nf, GEN list, GEN arch)

*nf* is a number field,
*bid* is as output by `idealstar(nf, D,...)`

and x a
non-necessarily integral element of *nf* which must have valuation
equal to 0 at all prime ideals in the support of `D`

. This function
computes the discrete logarithm of x on the generators given in

. In other words, if g_i are these generators, of orders
d_i respectively, the result is a column vector of integers (x_i) such
that 0 *bid*.gen`<=`

x_i < d_i and
x = prod_i g_i^{x_i} (mod ^*D) .
Note that when the support of `D`

contains places at infinity, this
congruence implies also sign conditions on the associated real embeddings.
See `znlog`

for the limitations of the underlying discrete log algorithms.

The library syntax is `GEN `

.**ideallog**(GEN nf, GEN x, GEN bid)

*This function is useless and kept for backward compatibility only,
use idealred*. Computes a pseudo-minimum of the ideal x in the
direction

The library syntax is `GEN `

.**idealmin**(GEN nf, GEN ix, GEN vdir = NULL)

Ideal multiplication of the ideals x and y in the number field
*nf*; the result is the ideal product in HNF. If either x or y
are extended ideals, their principal part is suitably
updated: i.e. multiplying [I,t], [J,u] yields [IJ, tu]; multiplying
I and [J, u] yields [IJ, u].

? nf = nfinit(x^2 + 1); ? idealmul(nf, 2, x+1) %2 = [4 2] [0 2] ? idealmul(nf, [2, x], x+1) \\ extended ideal * ideal %4 = [[4, 2; 0, 2], x] ? idealmul(nf, [2, x], [x+1, x]) \\ two extended ideals %5 = [[4, 2; 0, 2], [-1, 0]~]

If *flag* is non-zero, reduce the result using `idealred`

.

The library syntax is `GEN `

.**idealmul0**(GEN nf, GEN x, GEN y, long flag)

See also
`GEN `

(**idealmul**(GEN nf, GEN x, GEN y)*flag* = 0) and
`GEN `

(**idealmulred**(GEN nf, GEN x, GEN y)*flag* != 0).

Computes the norm of the ideal x in the number field *nf*.

The library syntax is `GEN `

.**idealnorm**(GEN nf, GEN x)

Returns [A,B], where A,B are coprime integer ideals
such that x = A/B, in the number field *nf*.

? nf = nfinit(x^2+1); ? idealnumden(nf, (x+1)/2) %2 = [[1, 0; 0, 1], [2, 1; 0, 1]]

The library syntax is `GEN `

.**idealnumden**(GEN nf, GEN x)

Computes the k-th power of
the ideal x in the number field *nf*; k belongs to **Z**.
If x is an extended
ideal, its principal part is suitably
updated: i.e. raising [I,t] to the k-th power, yields [I^k, t^k].

If *flag* is non-zero, reduce the result using `idealred`

, *throughout
the (binary) powering process*; in particular, this is *not* the same as
as `idealpow`

(*nf*,x,k) followed by reduction.

The library syntax is `GEN `

.**idealpow0**(GEN nf, GEN x, GEN k, long flag)

See also
`GEN `

and
**idealpow**(GEN nf, GEN x, GEN k)`GEN `

(**idealpows**(GEN nf, GEN x, long k)*flag* = 0).
Corresponding to *flag* = 1 is `GEN `

.**idealpowred**(GEN nf, GEN vp, GEN k)

Computes the prime ideal
decomposition of the (positive) prime number p in the number field K
represented by *nf*. If a non-prime p is given the result is undefined.

The result is a vector of *prid* structures, each representing one of the
prime ideals above p in the number field *nf*. The representation
`pr`

= [p,a,e,f,*mb*] of a prime ideal means the following: a and
is an algebraic integer in the maximal order **Z**_K and the prime ideal is
equal to **p** = p**Z**_K + a**Z**_K;
e is the ramification index; f is the residual index;
finally, *mb* is the multiplication table associated to the algebraic
integer b is such that **p**^{-1} = **Z**_K+ b/ p**Z**_K, which is used
internally to compute valuations. In other words if p is inert,
then *mb* is the integer 1, and otherwise it's a square `t_MAT`

whose j-th column is b.`nf.zk[j]`

.

The algebraic number a is guaranteed to have a valuation equal to 1 at the prime ideal (this is automatic if e > 1).

The components of `pr`

should be accessed by member functions: `pr.p`

,
`pr.e`

, `pr.f`

, and `pr.gen`

(returns the vector [p,a]):

? K = nfinit(x^3-2); ? L = idealprimedec(K, 5); ? #L \\ 2 primes above 5 in Q(2^(1/3)) %3 = 2 ? p1 = L[1]; p2 = L[2]; ? [p1.e, p1.f] \\ the first is unramified of degree 1 %4 = [1, 1] ? [p2.e, p2.f] \\ the second is unramified of degree 2 %5 = [1, 2] ? p1.gen %6 = [5, [2, 1, 0]~] ? nfbasistoalg(K, %[2]) \\ a uniformizer for p1 %7 = Mod(x + 2, x^3 - 2)

The library syntax is `GEN `

.**idealprimedec**(GEN nf, GEN p)

Given a prime ideal in `idealprimedec`

format,
returns the multiplicative group (1 + *pr*) / (1 + *pr*^k) as an
abelian group. This function is much faster than `idealstar`

when the
norm of *pr* is large, since it avoids (useless) work in the
multiplicative group of the residue field.

? K = nfinit(y^2+1); ? P = idealprimedec(K,2)[1]; ? G = idealprincipalunits(K, P, 20); ? G.cyc [512, 256, 4] \\ Z/512 x Z/256 x Z/4 ? G.gen %5 = [[-1, -2]~, 1021, [0, -1]~] \\ minimal generators of given order

The library syntax is `GEN `

.**idealprincipalunits**(GEN nf, GEN pr, long k)

Let K be the number field defined by *nf* and assume that K/**Q** is
Galois with Galois group G given by `gal = galoisinit(nf)`

.
Let *pr* be the prime ideal **P** in prid format.
This function returns a vector g of subgroups of `gal`

as follow:

***** `g[1]`

is the decomposition group of **P**,

***** `g[2]`

is G_0(**P**), the inertia group of **P**,

and for i `>=`

2,

***** `g[i]`

is G_{i-2}(**P**), the i-2-th \idx{ramification
group} of **P**.

The length of g is the number of non-trivial groups in the sequence, thus is 0 if e = 1 and f = 1, and 1 if f > 1 and e = 1. The following function computes the cardinality of a subgroup of G, as given by the components of g:

card(H) =my(o=H[2]); prod(i=1,#o,o[i]);

? nf=nfinit(x^6+3); gal=galoisinit(nf); pr=idealprimedec(nf,3)[1]; ? g = idealramgroups(nf, gal, pr); ? apply(card,g) %4 = [6, 6, 3, 3, 3] \\ cardinalities of the G_i

? nf=nfinit(x^6+108); gal=galoisinit(nf); pr=idealprimedec(nf,2)[1]; ? iso=idealramgroups(nf,gal,pr)[2] %4 = [[Vecsmall([2, 3, 1, 5, 6, 4])], Vecsmall([3])] ? nfdisc(galoisfixedfield(gal,iso,1)) %5 = -3The field fixed by the inertia group of 2 is not ramified at 2.

The library syntax is `GEN `

.**idealramgroups**(GEN nf, GEN gal, GEN pr)

LLL reduction of
the ideal I in the number field *nf*, along the direction v.
The v parameter is best left omitted, but if it is present, it must
be an `nf.r1`

+ `nf.r2`

-component vector of *non-negative*
integers. (What counts is the relative magnitude of the entries: if all
entries are equal, the effect is the same as if the vector had been omitted.)

This function finds a "small" a in I (see the end for technical details). The result is the Hermite normal form of the "reduced" ideal J = r I/a, where r is the unique rational number such that J is integral and primitive. (This is usually not a reduced ideal in the sense of Buchmann.)

? K = nfinit(y^2+1); ? P = idealprimedec(K,5)[1]; ? idealred(K, P) %3 = [1 0] [0 1]More often than not, a principal ideal yields the unit ideal as above. This is a quick and dirty way to check if ideals are principal, but it is not a necessary condition: a non-trivial result does not prove that the ideal is non-principal. For guaranteed results, see

`bnfisprincipal`

,
which requires the computation of a full `bnf`

structure.
If the input is an extended ideal [I,s], the output is [J,sa/r]; this way, one can keep track of the principal ideal part:

? idealred(K, [P, 1]) %5 = [[1, 0; 0, 1], [-2, 1]~]

meaning that P is generated by [-2, 1] . The number field element in the
extended part is an algebraic number in any form *or* a factorization
matrix (in terms of number field elements, not ideals!). In the latter case,
elements stay in factored form, which is a convenient way to avoid
coefficient explosion; see also `idealpow`

.

**Technical note.** The routine computes an LLL-reduced
basis for the lattice I equipped with the quadratic form
|| x ||_v^2 = sum_{i = 1}^{r_1+r_2} 2^{v_i}varepsilon_i|sigma_i(x)|^2,
where as usual the sigma_i are the (real and) complex embeddings and
varepsilon_i = 1, resp. 2, for a real, resp. complex place. The element
a is simply the first vector in the LLL basis. The only reason you may want
to try to change some directions and set some v_i != 0 is to randomize
the elements found for a fixed ideal, which is heuristically useful in index
calculus algorithms like `bnfinit`

and `bnfisprincipal`

.

**Even more technical note.** In fact, the above is a white lie.
We do not use ||.||_v exactly but a rescaled rounded variant which
gets us faster and simpler LLLs. There's no harm since we are not using any
theoretical property of a after all, except that it belongs to I and is
"expected to be small".

The library syntax is `GEN `

.**idealred0**(GEN nf, GEN I, GEN v = NULL)

Outputs a *bid* structure,
necessary for computing in the finite abelian group G = (**Z**_K/I)^*. Here,
*nf* is a number field and I is a *modulus*: either an ideal in any
form, or a row vector whose first component is an ideal and whose second
component is a row vector of r_1 0 or 1. Ideals can also be given
by a factorization into prime ideals, as produced by `idealfactor`

.

This *bid* is used in `ideallog`

to compute discrete logarithms. It
also contains useful information which can be conveniently retrieved as

(the modulus),
*bid*.mod

(G as a finite abelian group),
*bid*.clgp

(the cardinality of G),
*bid*.no

(elementary divisors) and
*bid*.cyc

(generators).*bid*.gen

If *flag* = 1 (default), the result is a *bid* structure without
generators.

If *flag* = 2, as *flag* = 1, but including generators, which wastes some time.

If *flag* = 0, only outputs (**Z**_K/I)^* as an abelian group,
i.e as a 3-component vector [h,d,g]: h is the order, d is the vector of
SNF cyclic components and g the corresponding
generators.

The library syntax is `GEN `

.
Instead the above hardcoded numerical flags, one should rather use
**idealstar0**(GEN nf, GEN I, long flag)`GEN `

, where **Idealstar**(GEN nf, GEN ideal, long flag)`flag`

is
an or-ed combination of `nf_GEN`

(include generators) and `nf_INIT`

(return a full `bid`

, not a group), possibly 0. This offers
one more combination: gen, but no init.

Computes a two-element
representation of the ideal x in the number field *nf*, combining a
random search and an approximation theorem; x is an ideal
in any form (possibly an extended ideal, whose principal part is ignored)

***** When called as `idealtwoelt(nf,x)`

, the result is a row vector
[a,alpha] with two components such that x = a**Z**_K+alpha**Z**_K and a is
chosen to be the positive generator of xcap**Z**, unless x was given as a
principal ideal (in which case we may choose a = 0). The algorithm
uses a fast lazy factorization of xcap **Z** and runs in randomized
polynomial time.

***** When called as `idealtwoelt(nf,x,a)`

with an explicit non-zero a
supplied as third argument, the function assumes that a belongs to x and returns
alpha belongs to x such that x = a**Z**_K + alpha**Z**_K. Note that we must factor
a in this case, and the algorithm is generally much slower than the
default variant.

The library syntax is `GEN `

.
Also available are
**idealtwoelt0**(GEN nf, GEN x, GEN a = NULL)`GEN `

and
**idealtwoelt**(GEN nf, GEN x)`GEN `

.**idealtwoelt2**(GEN nf, GEN x, GEN a)

Gives the valuation of the ideal x at the prime ideal *pr* in the
number field *nf*, where *pr* is in `idealprimedec`

format.

The library syntax is `long `

.**idealval**(GEN nf, GEN x, GEN pr)

*nf* being a number field in `nfinit`

format, and x a
(row or column) vector or matrix, apply `nfalgtobasis`

to each entry
of x.

The library syntax is `GEN `

.**matalgtobasis**(GEN nf, GEN x)

*nf* being a number field in `nfinit`

format, and x a
(row or column) vector or matrix, apply `nfbasistoalg`

to each entry
of x.

The library syntax is `GEN `

.**matbasistoalg**(GEN nf, GEN x)

Let z = `Mod(A, T)`

be a polmod, and Q be its minimal
polynomial, which must satisfy {deg}(Q) = {deg}(T).
Returns a "reverse polmod" `Mod(B, Q)`

, which is a root of T.

This is quite useful when one changes the generating element in algebraic extensions:

? u = Mod(x, x^3 - x -1); v = u^5; ? w = modreverse(v) %2 = Mod(x^2 - 4*x + 1, x^3 - 5*x^2 + 4*x - 1)

which means that x^3 - 5x^2 + 4x -1 is another defining polynomial for the
cubic field
**Q**(u) = **Q**[x]/(x^3 - x - 1) = **Q**[x]/(x^3 - 5x^2 + 4x - 1) = **Q**(v),
and that u \to v^2 - 4v + 1 gives an explicit isomorphism. From this, it is
easy to convert elements between the A(u) belongs to **Q**(u) and B(v) belongs to **Q**(v)
representations:

? A = u^2 + 2*u + 3; subst(lift(A), 'x, w) %3 = Mod(x^2 - 3*x + 3, x^3 - 5*x^2 + 4*x - 1) ? B = v^2 + v + 1; subst(lift(B), 'x, v) %4 = Mod(26*x^2 + 31*x + 26, x^3 - x - 1)

If the minimal polynomial of z has lower degree than expected, the routine fails

? u = Mod(-x^3 + 9*x, x^4 - 10*x^2 + 1) ? modreverse(u) *** modreverse: domain error in modreverse: deg(minpoly(z)) < 4 *** Break loop: type 'break' to go back to GP prompt break> Vec( dbg_err() ) \\ ask for more info ["e_DOMAIN", "modreverse", "deg(minpoly(z))", "<", 4, Mod(-x^3 + 9*x, x^4 - 10*x^2 + 1)] break> minpoly(u) x^2 - 8

The library syntax is `GEN `

.**modreverse**(GEN z)

Gives the vector of the slopes of the Newton
polygon of the polynomial x with respect to the prime number p. The n
components of the vector are in decreasing order, where n is equal to the
degree of x. Vertical slopes occur iff the constant coefficient of x is
zero and are denoted by `LONG_MAX`

, the biggest single precision
integer representable on the machine (2^{31}-1 (resp. 2^{63}-1) on 32-bit
(resp. 64-bit) machines), see Section [**Label: se:valuation**].

The library syntax is `GEN `

.**newtonpoly**(GEN x, GEN p)

Given an algebraic number x in the number field *nf*,
transforms it to a column vector on the integral basis

.*nf*.zk

? nf = nfinit(y^2 + 4); ? nf.zk %2 = [1, 1/2*y] ? nfalgtobasis(nf, [1,1]~) %3 = [1, 1]~ ? nfalgtobasis(nf, y) %4 = [0, 2]~ ? nfalgtobasis(nf, Mod(y, y^2+4)) %4 = [0, 2]~

This is the inverse function of `nfbasistoalg`

.

The library syntax is `GEN `

.**algtobasis**(GEN nf, GEN x)

Let T(X) be an irreducible polynomial with integral coefficients. This
function returns an integral basis of the number field defined by T,
that is a **Z**-basis of its maximal order. The basis elements are given as
elements in **Q**[X]/(T):

? nfbasis(x^2 + 1) %1 = [1, x]

This function uses a modified version of the round 4 algorithm, due to David Ford, Sebastian Pauli and Xavier Roblot.

**Local basis, orders maximal at certain primes.**

Obtaining the maximal order is hard: it requires factoring the discriminant
D of T. Obtaining an order which is maximal at a finite explicit set of
primes is easy, but if may then be a strict suborder of the maximal order. To
specify that we are interested in a given set of places only, we can replace
the argument T by an argument [T,*listP*], where *listP* encodes
the primes we are interested in: it must be a factorization matrix, a vector
of integers or a single integer.

***** Vector: we assume that it contains distinct *prime* numbers.

***** Matrix: we assume that it is a two-column matrix of a
(partial) factorization of D; namely the first column contains
*primes* and the second one the valuation of D at each of these
primes.

***** Integer B: this is replaced by the vector of primes up to B. Note
that the function will use at least O(B) time: a small value, about
10^5, should be enough for most applications. Values larger than 2^{32}
are not supported.

In all these cases, the primes may or may not divide the discriminant D
of T. The function then returns a **Z**-basis of an order whose index is
not divisible by any of these prime numbers. The result is actually a global
integral basis if all prime divisors of the *field* discriminant are
included! Note that `nfinit`

has built-in support for such
a check:

? K = nfinit([T, listP]); ? nfcertify(K) \\ we computed an actual maximal order %2 = [];The first line initializes a number field structure incorporating

`nfbasis([T, listP]`

in place of a proven integral basis.
The second line certifies that the resulting structure is correct. This
allows to create an `nf`

structure associated to the number field K =
Of course, if *listP* contains a single prime number p,
the function returns a local integral basis for **Z**_p[X]/(T):

? nfbasis(x^2+x-1001) %1 = [1, 1/3*x - 1/3] ? nfbasis( [x^2+x-1001, [2]] ) %2 = [1, x]

**The Buchmann-Lenstra algorithm.**

We now complicate the picture: it is in fact allowed to include
*composite* numbers instead of primes
in `listP`

(Vector or Matrix case), provided they are pairwise coprime.
The result will still be a correct integral basis *if*
the field discriminant factors completely over the actual primes in the list.
Adding a composite C such that C^2 *divides* D may help because
when we consider C as a prime and run the algorithm, two good things can
happen: either we
succed in proving that no prime dividing C can divide the index
(without actually needing to find those primes), or the computation
exhibits a non-trivial zero divisor, thereby factoring C and
we go on with the refined factorization. (Note that including a C
such that C^2 does not divide D is useless.) If neither happen, then the
computed basis need not generate the maximal order. Here is an example:

? B = 10^5; ? P = factor(poldisc(T), B)[,1]; \\ primes <= B dividing D + cofactor ? basis = nfbasis([T, listP]) ? disc = nfdisc([T, listP])We obtain the maximal order and its discriminant if the field discriminant factors completely over the primes less than B (together with the primes contained in the

`addprimes`

table). This can be tested as follows:

check = factor(disc, B); lastp = check[-1..-1,1]; if (lastp > B && !setsearch(addprimes(), lastp), warning("nf may be incorrect!"))

This is a sufficient but not a necessary condition, hence the warning,
instead of an error. N.B. `lastp`

is the last entry
in the first column of the `check`

matrix, i.e. the largest prime
dividing `nf.disc`

if `<=`

B or if it belongs to the prime table.

The function `nfcertify`

speeds up and automates the above process:

? B = 10^5; ? nf = nfinit([T, B]); ? nfcertify(nf) %3 = [] \\ nf is unconditionally correct ? basis = nf.zk; ? disc = nf.disc;

The library syntax is

, which returns the order
basis, and where **nfbasis**(GEN T, GEN *d, GEN listP = NULL)`*d`

receives the order discriminant.

Given an algebraic number x in the number field `nf`

, transforms it
into `t_POLMOD`

form.

? nf = nfinit(y^2 + 4); ? nf.zk %2 = [1, 1/2*y] ? nfbasistoalg(nf, [1,1]~) %3 = Mod(1/2*y + 1, y^2 + 4) ? nfbasistoalg(nf, y) %4 = Mod(y, y^2 + 4) ? nfbasistoalg(nf, Mod(y, y^2+4)) %4 = Mod(y, y^2 + 4)

This is the inverse function of `nfalgtobasis`

.

The library syntax is `GEN `

.**basistoalg**(GEN nf, GEN x)

*nf* being as output by
`nfinit`

, checks whether the integer basis is known unconditionally.
This is in particular useful when the argument to `nfinit`

was of the
form [T, `listP`

], specifying a finite list of primes when
p-maximality had to be proven.

The function returns a vector of composite integers. If this vector is
empty, then `nf.zk`

and `nf.disc`

are correct. Otherwise, the
result is dubious. In order to obtain a certified result, one must
completely factor each of the given integers, then `addprime`

each of
them, then check whether `nfdisc(nf.pol)`

is equal to `nf.disc`

.

The library syntax is `GEN `

.**nfcertify**(GEN nf)

Given a pseudo-matrix x, computes a
non-zero ideal contained in (i.e. multiple of) the determinant of x. This
is particularly useful in conjunction with `nfhnfmod`

.

The library syntax is `GEN `

.**nfdetint**(GEN nf, GEN x)

field discriminant of the number field defined by the integral,
preferably monic, irreducible polynomial T(X). Returns the discriminant of
the number field **Q**[X]/(T), using the Round 4 algorithm.

**Local discriminants, valuations at certain primes.**

As in `nfbasis`

, the argument T can be replaced by [T,*listP*],
where `listP`

is as in `nfbasis`

: a vector of
pairwise coprime integers (usually distinct primes), a factorization matrix,
or a single integer. In that case, the function returns the discriminant of
an order whose basis is given by `nfbasis(T,listP)`

, which need not be
the maximal order, and whose valuation at a prime entry in `listP`

is the
same as the valuation of the field discriminant.

In particular, if `listP`

is [p] for a prime p, we can
return the p-adic discriminant of the maximal order of **Z**_p[X]/(T),
as a power of p, as follows:

? padicdisc(T,p) = p^valuation(nfdisc(T,[p]), p); ? nfdisc(x^2 + 6) %1 = -24 ? padicdisc(x^2 + 6, 2) %2 = 8 ? padicdisc(x^2 + 6, 3) %3 = 3

The library syntax is

(**nfdisc**(GEN T)`listP = NULL`

). Also available is
`GEN `

, which returns the order
basis, and where **nfbasis**(GEN T, GEN *d, GEN listP = NULL)`*d`

receives the order discriminant.

Given two elements x and y in
*nf*, computes their sum x+y in the number field *nf*.

The library syntax is `GEN `

.**nfadd**(GEN nf, GEN x, GEN y)

Given two elements x and y in
*nf*, computes their quotient x/y in the number field *nf*.

The library syntax is `GEN `

.**nfdiv**(GEN nf, GEN x, GEN y)

Given two elements x and y in
*nf*, computes an algebraic integer q in the number field *nf*
such that the components of x-qy are reasonably small. In fact, this is
functionally identical to `round(nfdiv(`

.*nf*,x,y))

The library syntax is `GEN `

.**nfdiveuc**(GEN nf, GEN x, GEN y)

Given two elements x
and y in *nf* and *pr* a prime ideal in `modpr`

format (see
`nfmodprinit`

), computes their quotient x / y modulo the prime ideal
*pr*.

The library syntax is `GEN `

.
This function is normally useless in library mode. Project your
inputs to the residue field using **nfdivmodpr**(GEN nf, GEN x, GEN y, GEN pr)`nf_to_Fq`

, then work there.

Given two elements x and y in
*nf*, gives a two-element row vector [q,r] such that x = qy+r, q is
an algebraic integer in *nf*, and the components of r are
reasonably small.

The library syntax is `GEN `

.**nfdivrem**(GEN nf, GEN x, GEN y)

Given two elements x and y in
*nf*, computes an element r of *nf* of the form r = x-qy with
q and algebraic integer, and such that r is small. This is functionally
identical to
`x - nfmul(`

.*nf*,round(nfdiv(*nf*,x,y)),y)

The library syntax is `GEN `

.**nfmod**(GEN nf, GEN x, GEN y)

Given two elements x and y in
*nf*, computes their product x*y in the number field *nf*.

The library syntax is `GEN `

.**nfmul**(GEN nf, GEN x, GEN y)

Given two elements x and
y in *nf* and *pr* a prime ideal in `modpr`

format (see
`nfmodprinit`

), computes their product x*y modulo the prime ideal
*pr*.

The library syntax is `GEN `

.
This function is normally useless in library mode. Project your
inputs to the residue field using **nfmulmodpr**(GEN nf, GEN x, GEN y, GEN pr)`nf_to_Fq`

, then work there.

Returns the absolute norm of x.

The library syntax is `GEN `

.**nfnorm**(GEN nf, GEN x)

Given an element x in *nf*, and a positive or negative integer k,
computes x^k in the number field *nf*.

The library syntax is `GEN `

.
**nfpow**(GEN nf, GEN x, GEN k)`GEN `

correspond to k = -1, and
**nfinv**(GEN nf, GEN x)`GEN `

to k = 2.**nfsqr**(GEN nf,GEN x)

Given an element x in *nf*, an integer k and a prime ideal
*pr* in `modpr`

format
(see `nfmodprinit`

), computes x^k modulo the prime ideal *pr*.

The library syntax is `GEN `

.
This function is normally useless in library mode. Project your
inputs to the residue field using **nfpowmodpr**(GEN nf, GEN x, GEN k, GEN pr)`nf_to_Fq`

, then work there.

Given an ideal *id* in
Hermite normal form and an element a of the number field *nf*,
finds an element r in *nf* such that a-r belongs to the ideal
and r is small.

The library syntax is `GEN `

.**nfreduce**(GEN nf, GEN a, GEN id)

Given an element x of the number field *nf* and a prime ideal
*pr* in `modpr`

format compute a canonical representative for the
class of x modulo *pr*.

The library syntax is `GEN `

.
This function is normally useless in library mode. Project your
inputs to the residue field using **nfreducemodpr**(GEN nf, GEN x, GEN pr)`nf_to_Fq`

, then work there.

Returns the absolute trace of x.

The library syntax is `GEN `

.**nftrace**(GEN nf, GEN x)

Given an element x in
*nf* and a prime ideal *pr* in the format output by
`idealprimedec`

, computes their the valuation at *pr* of the
element x. The same result could be obtained using
`idealval(`

(since x would then be converted to a
principal ideal), but it would be less efficient.*nf*,x,*pr*)

The library syntax is `long `

.**nfval**(GEN nf, GEN x, GEN pr)

Factorization of the univariate
polynomial T over the number field *nf* given by `nfinit`

; T
has coefficients in *nf* (i.e. either scalar, polmod, polynomial or
column vector). The factors are sorted by increasing degree.

The main variable of *nf* must be of *lower*
priority than that of T, see Section [**Label: se:priority**]. However if
the polynomial defining the number field occurs explicitly in the
coefficients of T as modulus of a `t_POLMOD`

or as a `t_POL`

coefficient, its main variable must be *the same* as the main variable
of T. For example,

? nf = nfinit(y^2 + 1); ? nffactor(nf, x^2 + y); \\ OK ? nffactor(nf, x^2 + Mod(y, y^2+1)); \\ OK ? nffactor(nf, x^2 + Mod(z, z^2+1)); \\ WRONG

It is possible to input a defining polynomial for *nf*
instead, but this is in general less efficient since parts of an `nf`

structure will then be computed internally. This is useful in two
situations: when you do not need the `nf`

elsewhere, or when you cannot
compute the field discriminant due to integer factorization difficulties. In
the latter case, if you must use a partial discriminant factorization (as
allowed by both `nfdisc`

or `nfbasis`

) to build a partially correct
*nf* structure, always input `nf.pol`

to `nffactor`

, and not your
makeshift *nf*: otherwise factors could be missed.

The library syntax is `GEN `

.**nffactor**(GEN nf, GEN T)

Gives back the `nf`

element corresponding to a factorization.
The integer 1 corresponds to the empty factorization.

If e is present, e and f must be vectors of the same length (e being integral), and the corresponding factorization is the product of the f[i]^{e[i]}.

If not, and f is vector, it is understood as in the preceding case with e a vector of 1s: we return the product of the f[i]. Finally, f can be a regular factorization matrix.

? nf = nfinit(y^2+1); ? nffactorback(nf, [3, y+1, [1,2]~], [1, 2, 3]) %2 = [12, -66]~ ? 3 * (I+1)^2 * (1+2*I)^3 %3 = 12 - 66*I

The library syntax is `GEN `

.**nffactorback**(GEN nf, GEN f, GEN e = NULL)

Factors the univariate polynomial Q modulo the prime ideal *pr* in
the number field *nf*. The coefficients of Q belong to the number
field (scalar, polmod, polynomial, even column vector) and the main variable
of *nf* must be of lower priority than that of Q (see
Section [**Label: se:priority**]). The prime ideal *pr* is either in
`idealprimedec`

or (preferred) `modprinit`

format. The coefficients
of the polynomial factors are lifted to elements of *nf*:

? K = nfinit(y^2+1); ? P = idealprimedec(K, 3)[1]; ? nffactormod(K, x^2 + y*x + 18*y+1, P) %3 = [x + (2*y + 1) 1] [x + (2*y + 2) 1] ? P = nfmodprinit(K, P); \\ convert to nfmodprinit format ? nffactormod(K, x^2 + y*x + 18*y+1) [x + (2*y + 1) 1] [x + (2*y + 2) 1]Same result, of course, here about 10% faster due to the precomputation.

The library syntax is `GEN `

.**nffactormod**(GEN nf, GEN Q, GEN pr)

Let *nf* be a
number field as output by `nfinit`

, and let *aut* be a Galois
automorphism of *nf* expressed by its image on the field generator
(such automorphisms can be found using `nfgaloisconj`

). The function
computes the action of the automorphism *aut* on the object x in the
number field; x can be a number field element, or an ideal (possibly
extended). Because of possible confusion with elements and ideals, other
vector or matrix arguments are forbidden.

? nf = nfinit(x^2+1); ? L = nfgaloisconj(nf) %2 = [-x, x]~ ? aut = L[1]; /* the non-trivial automorphism */ ? nfgaloisapply(nf, aut, x) %4 = Mod(-x, x^2 + 1) ? P = idealprimedec(nf,5); /* prime ideals above 5 */ ? nfgaloisapply(nf, aut, P[2]) == P[1] %7 = 0 \\ !!!! ? idealval(nf, nfgaloisapply(nf, aut, P[2]), P[1]) %8 = 1The surprising failure of the equality test (

`%7`

) is
due to the fact that although the corresponding prime ideals are equal, their
representations are not. (A prime ideal is specificed by a uniformizer, and
there is no guarantee that applying automorphisms yields the same elements
as a direct `idealprimedec`

call.)
The automorphism can also be given as a column vector, representing the
image of `Mod(x, nf.pol)`

as an algebraic number. This last
representation is more efficient and should be preferred if a given
automorphism must be used in many such calls.

? nf = nfinit(x^3 - 37*x^2 + 74*x - 37); ? l = nfgaloisconj(nf); aut = l[2] \\ automorphisms in basistoalg form %2 = -31/11*x^2 + 1109/11*x - 925/11 ? L = matalgtobasis(nf, l); AUT = L[2] \\ same in algtobasis form %3 = [16, -6, 5]~ ? v = [1, 2, 3]~; nfgaloisapply(nf, aut, v) == nfgaloisapply(nf, AUT, v) %4 = 1 \\ same result... ? for (i=1,10^5, nfgaloisapply(nf, aut, v)) time = 1,451 ms. ? for (i=1,10^5, nfgaloisapply(nf, AUT, v)) time = 1,045 ms. \\ but the latter is faster

The library syntax is `GEN `

.**galoisapply**(GEN nf, GEN aut, GEN x)

*nf* being a number field as output by `nfinit`

, computes the
conjugates of a root r of the non-constant polynomial x = *nf*[1]
expressed as polynomials in r. This also makes sense when the number field
is not Galois since some conjugates may lie in the field.
*nf* can simply be a polynomial.

If no flags or *flag* = 0, use a combination of flag 4 and 1 and the result
is always complete. There is no point whatsoever in using the other flags.

If *flag* = 1, use `nfroots`

: a little slow, but guaranteed to work in
polynomial time.

If *flag* = 2 (OBSOLETE), use complex approximations to the roots and an integral
LLL. The result is not guaranteed to be complete: some
conjugates may be missing (a warning is issued if the result is not proved
complete), especially so if the corresponding polynomial has a huge index,
and increasing the default precision may help. This variant is slow and
unreliable: don't use it.

If *flag* = 4, use `galoisinit`

: very fast, but only applies to (most) Galois
fields. If the field is Galois with weakly
super-solvable Galois group (see `galoisinit`

), return the complete list
of automorphisms, else only the identity element. If present, d is assumed to
be a multiple of the least common denominator of the conjugates expressed as
polynomial in a root of *pol*.

This routine can only compute **Q**-automorphisms, but it may be used to get
K-automorphism for any base field K as follows:

rnfgaloisconj(nfK, R) = \\ K-automorphisms of L = K[X] / (R) { my(polabs, N); R *= Mod(1, nfK.pol); \\ convert coeffs to polmod elts of K polabs = rnfequation(nfK, R); N = nfgaloisconj(polabs) % R; \\ Q-automorphisms of L \\ select the ones that fix K select(s->subst(R, variable(R), Mod(s,R)) == 0, N); } K = nfinit(y^2 + 7); rnfgaloisconj(K, x^4 - y*x^3 - 3*x^2 + y*x + 1) \\ K-automorphisms of L

The library syntax is `GEN `

.
Use directly
**galoisconj0**(GEN nf, long flag, GEN d = NULL, long prec)`GEN `

, corresponding to **galoisconj**(GEN nf, GEN d)*flag* = 0, the others
only have historical interest.

If *pr* is omitted,
compute the global quadratic Hilbert symbol (a,b) in *nf*, that
is 1 if x^2 - a y^2 - b z^2 has a non trivial solution (x,y,z) in
*nf*, and -1 otherwise. Otherwise compute the local symbol modulo
the prime ideal *pr*, as output by `idealprimedec`

.

The library syntax is `long `

.**nfhilbert0**(GEN nf, GEN a, GEN b, GEN pr = NULL)

Also available is `long `

(global
quadratic Hilbert symbol).**nfhilbert**(GEN bnf,GEN a,GEN b)

Given a pseudo-matrix (A,I), finds a pseudo-basis in Hermite normal form of the module it generates.

The library syntax is `GEN `

.
Also available:**nfhnf**(GEN nf, GEN x)

`GEN `

simplifies the pseudo-basis
given by x = (A,I). The ideals in the list I are integral, primitive and
either trivial (equal to the full ring of integer) or non-principal.**rnfsimplifybasis**(GEN bnf, GEN x)

Given a pseudo-matrix (A,I)
and an ideal *detx* which is contained in (read integral multiple of) the
determinant of (A,I), finds a pseudo-basis in Hermite normal form
of the module generated by (A,I). This avoids coefficient explosion.
*detx* can be computed using the function `nfdetint`

.

The library syntax is `GEN `

.**nfhnfmod**(GEN nf, GEN x, GEN detx)

*pol* being a non-constant,
preferably monic, irreducible polynomial in **Z**[X], initializes a
*number field* structure (`nf`

) associated to the field K defined
by *pol*. As such, it's a technical object passed as the first argument
to most `nf`

*xxx* functions, but it contains some information which
may be directly useful. Access to this information via *member
functions* is preferred since the specific data organization specified below
may change in the future. Currently, `nf`

is a row vector with 9
components:

*nf*[1] contains the polynomial *pol* (

).*nf*.pol

*nf*[2] contains [r1,r2] (

, *nf*.sign

,
*nf*.r1

), the number of real and complex places of K.*nf*.r2

*nf*[3] contains the discriminant d(K) (

) of K.*nf*.disc

*nf*[4] contains the index of *nf*[1] (

),
i.e. [*nf*.index**Z**_K : **Z**[theta]], where theta is any root of *nf*[1].

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

***** M is the (r1+r2) x n matrix whose columns represent
the numerical values of the conjugates of the elements of the integral
basis.

***** G is an n x 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**.

***** *roundG* is a rescaled copy of G, rounded to nearest
integers.

***** T is the n x n matrix whose coefficients are
{Tr}(omega_iomega_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.

***** The columns of MD (

) express a *nf*.diff**Z**-basis
of the different of K on the integral basis.

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

***** Finally, MDI is a two-element representation (for faster
ideal product) of d(K) times the codifferent ideal
(

, which is an integral ideal). MDI
is only used in *nf*.disc**nf*.codiff`idealinv`

.

*nf*[6] is the vector containing the r1+r2 roots
(

) of *nf*.roots*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).

*nf*[7] is an integral basis for **Z**_K (

) 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).*nf*.zk

*nf*[8] is the n x n integral matrix expressing the power
basis in terms of the integral basis, and finally

*nf*[9] is the n x n^2 matrix giving the multiplication table
of the integral basis.

If a non monic polynomial is input, `nfinit`

will transform it into a
monic one, then reduce it (see *flag* = 3). It is allowed, though not very
useful given the existence of `nfnewprec`

, to input a `nf`

or a
`bnf`

instead of a polynomial.

? 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] \\p_2^3

**Huge discriminants, helping nfdisc.**

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

***** an integer basis, as would be computed by `nfbasis`

: a vector of
polynomials with first element 1. This is useful if the maximal order is
known in advance.

***** an argument `listP`

which specifies a list of primes (see
`nfbasis`

). Instead of the maximal order, `nfinit`

then computes an
order which is maximal at these particular primes as well as the primes
contained in the private prime table (see `addprimes`

). The result is
unconditionnaly correct when the discriminant `nf.disc`

factors
completely over this set of primes. The function `nfcertify`

automates
this:

? pol = polcompositum(x^5 - 101, polcyclo(7))[1]; ? nf = nfinit( [pol, 10^3] ); ? nfcertify(nf) %3 = []A priori,

`nf.zk`

defines an order which is only known
to be maximal at all primes `<=`

10^3 (no prime `<=`

10^3 divides
`nf.index`

). The certification step proves the correctness of the
computation.
If *flag* = 2: *pol* is changed into another polynomial P defining the same
number field, which is as simple as can easily be found using the
`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 *flag* = 3, apply `polredbest`

as in case 2, but outputs
[*nf*,`Mod`

(a,P)], where *nf* is as before and
`Mod`

(a,P) = `Mod`

(x,*pol*) gives the change of
variables. This is implicit when *pol* is not monic: first a linear change
of variables is performed, to get a monic polynomial, then `polredbest`

.

The library syntax is `GEN `

.
Also available are
**nfinit0**(GEN pol, long flag, long prec)`GEN `

(**nfinit**(GEN x, long prec)*flag* = 0),
`GEN `

(**nfinitred**(GEN x, long prec)*flag* = 2),
`GEN `

(**nfinitred2**(GEN x, long prec)*flag* = 3).
Instead of the above hardcoded numerical flags in `nfinit0`

, one should
rather use

`GEN `

, where **nfinitall**(GEN x, long flag, long prec)*flag* is an
or-ed combination of

***** `nf_RED`

: find a simpler defining polynomial,

***** `nf_ORIG`

: if `nf_RED`

set, also return the change of variable,

***** `nf_ROUND2`

: *Deprecated*. Slow down the routine by using an
obsolete normalization algorithm (do not use this one!),

***** `nf_PARTIALFACT`

: *Deprecated*. Lazy factorization of the
polynomial discriminant. Result is conditional unless `nfcertify`

can certify it.

Returns 1 if x is an ideal in the number field *nf*, 0 otherwise.

The library syntax is `long `

.**isideal**(GEN nf, GEN x)

Tests whether the number field K defined
by the polynomial x is conjugate to a subfield of the field L defined
by y (where x and y must be in **Q**[X]). If they are not, the output
is the number 0. If they are, the output is a vector of polynomials, each
polynomial a representing an embedding of K into L, i.e. being such
that y | x o a.

If y is a number field (*nf*), a much faster algorithm is used
(factoring x over y using `nffactor`

). Before version 2.0.14, this
wasn't guaranteed to return all the embeddings, hence was triggered by a
special flag. This is no more the case.

The library syntax is `GEN `

.**nfisincl**(GEN x, GEN y)

As `nfisincl`

, but tests for isomorphism. If either x or y is a
number field, a much faster algorithm will be used.

The library syntax is `GEN `

.**nfisisom**(GEN x, GEN y)

Kernel of the matrix a in **Z**_K/*pr*, where *pr* is in
**modpr** format (see `nfmodprinit`

).

The library syntax is `GEN `

.
This function is normally useless in library mode. Project your
inputs to the residue field using **nfkermodpr**(GEN nf, GEN x, GEN pr)`nfM_to_FqM`

, then work there.

Transforms the prime ideal *pr* into `modpr`

format necessary
for all operations modulo *pr* in the number field *nf*.

The library syntax is `GEN `

.**nfmodprinit**(GEN nf, GEN pr)

Transforms the number field *nf*
into the corresponding data using current (usually larger) precision. This
function works as expected if *nf* is in fact a *bnf* (update
*bnf* to current precision) but may be quite slow (many generators of
principal ideals have to be computed).

The library syntax is `GEN `

.
See also **nfnewprec**(GEN nf, long prec)`GEN `

and **bnfnewprec**(GEN bnf, long prec)`GEN `

.**bnrnewprec**(GEN bnr, long prec)

Roots of the polynomial x in the
number field *nf* given by `nfinit`

without multiplicity (in **Q**
if *nf* is omitted). x has coefficients in the number field (scalar,
polmod, polynomial, column vector). The main variable of *nf* must be
of lower priority than that of x (see Section [**Label: se:priority**]). However if the
coefficients of the number field occur explicitly (as polmods) as
coefficients of x, the variable of these polmods *must* be the same as
the main variable of t (see `nffactor`

).

It is possible to input a defining polynomial for *nf*
instead, but this is in general less efficient since parts of an `nf`

structure will be computed internally. This is useful in two situations: when
you don't need the `nf`

, or when you can't compute its discriminant due
to integer factorization difficulties. In the latter case, `addprimes`

is
a possibility but a dangerous one: roots will probably be missed if the
(true) field discriminant and an `addprimes`

entry are strictly divisible
by some prime. If you have such an unsafe *nf*, it is safer to input
`nf.pol`

.

The library syntax is `GEN `

.
See also **nfroots**(GEN nf = NULL, GEN x)`GEN `

,
corresponding to **nfrootsQ**(GEN x)`nf`

= `NULL`

.

Returns a two-component vector [w,z] where w is the number of roots of
unity in the number field *nf*, and z is a primitive w-th root
of unity.

? K = nfinit(polcyclo(11)); ? nfrootsof1(K) %2 = [22, [0, 0, 0, 0, 0, -1, 0, 0, 0, 0]~] ? z = nfbasistoalg(K, %[2]) \\ in algebraic form %3 = Mod(-x^5, x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1) ? [lift(z^11), lift(z^2)] \\ proves that the order of z is 22 %4 = [-1, -x^9 - x^8 - x^7 - x^6 - x^5 - x^4 - x^3 - x^2 - x - 1]

This function guesses the number w as the gcd of the #k(v)^* for
unramified v above odd primes, then computes the roots in *nf*
of the w-th cyclotomic polynomial: the algorithm is polynomial time with
respect to the field degree and the bitsize of the multiplication table in
*nf* (both of them polynomially bounded in terms of the size of the
discriminant). Fields of degree up to 100 or so should require less than
one minute.

The library syntax is `GEN `

.
Also available is **rootsof1**(GEN nf)`GEN `

, that computes
all algebraic integers of T_2 norm equal to the field degree
(all roots of 1, by Kronecker's theorem). This is in general a little
faster than the default when there **rootsof1_kannan**(GEN nf)*are* roots of 1 in the field
(say twice faster), but can be much slower (say, *days* slower), since
the algorithm is a priori exponential in the field degree.

Given a **Z**_K-module x associated to the integral pseudo-matrix
(A,I,J), returns an ideal list d_1,...,d_n which is the \idx{Smith
normal form} of x. In other words, x is isomorphic to
**Z**_K/d_1oplus...oplus**Z**_K/d_n and d_i divides d_{i-1} for i `>=`

2.

See Section [**Label: se:ZKmodules**] for the definition of integral pseudo-matrix;
briefly, it is input as a 3-component row vector [A,I,J] where
I = [b_1,...,b_n] and J = [a_1,...,a_n] are two ideal lists,
and A is a square n x n matrix with columns (A_1,...,A_n),
seen as elements in K^n (with canonical basis (e_1,...,e_n)).
This data defines the **Z**_K module x given by
(b_1e_1oplus...oplus b_ne_n) / (a_1A_1oplus...oplus a_nA_n)
,
The integrality condition is a_{i,j} belongs to b_i a_j^{-1} for all i,j. If it
is not satisfied, then the d_i will not be integral. Note that every
finitely generated torsion module is isomorphic to a module of this form and
even with b_i = Z_K for all i.

The library syntax is `GEN `

.**nfsnf**(GEN nf, GEN x)

Let P be a prime ideal in **modpr** format (see `nfmodprinit`

),
let a be a matrix, invertible over the residue field, and let b be
a column vector or matrix. This function returns a solution of a.x =
b; the coefficients of x are lifted to *nf* elements.

? K = nfinit(y^2+1); ? P = idealprimedec(K, 3)[1]; ? P = nfmodprinit(K, P); ? a = [y+1, y; y, 0]; b = [1, y]~ ? nfsolvemodpr(K, a,b, P) %5 = [1, 2]~

The library syntax is `GEN `

.
This function is normally useless in library mode. Project your
inputs to the residue field using **nfsolvemodpr**(GEN nf, GEN a, GEN b, GEN P)`nfM_to_FqM`

, then work there.

Finds all subfields of degree
d of the number field defined by the (monic, integral) polynomial
*pol* (all subfields if d is null or omitted). The result is a vector
of subfields, each being given by [g,h], where g is an absolute equation
and h expresses one of the roots of g in terms of the root x of the
polynomial defining *nf*. This routine uses J. Klüners's algorithm
in the general case, and B. Allombert's `galoissubfields`

when *nf*
is Galois (with weakly supersolvable Galois group).

The library syntax is `GEN `

.**nfsubfields**(GEN pol, long d)

P and Q
being squarefree polynomials in **Z**[X] in the same variable, outputs
the simple factors of the étale **Q**-algebra A = **Q**(X, Y) / (P(X), Q(Y)).
The factors are given by a list of polynomials R in **Z**[X], associated to
the number field **Q**(X)/ (R), and sorted by increasing degree (with respect
to lexicographic ordering for factors of equal degrees). Returns an error if
one of the polynomials is not squarefree.

Note that it is more efficient to reduce to the case where P and Q are irreducible first. The routine will not perform this for you, since it may be expensive, and the inputs are irreducible in most applications anyway. In this case, there will be a single factor R if and only if the number fields defined by P and Q are disjoint.

Assuming P is irreducible (of smaller degree than Q for efficiency), it is in general much faster to proceed as follows

nf = nfinit(P); L = nffactor(nf, Q)[,1]; vector(#L, i, rnfequation(nf, L[i]))

to obtain the same result. If you are only interested in the degrees of the
simple factors, the `rnfequation`

instruction can be replaced by a
trivial `poldegree(P) * poldegree(L[i])`

.

If *flag* = 1, outputs a vector of 4-component vectors [R,a,b,k], where R
ranges through the list of all possible compositums as above, and a
(resp. b) expresses the root of P (resp. Q) as an element of
**Q**(X)/(R). Finally, k is a small integer such that b + ka = X modulo
R.

A compositum is often defined by a complicated polynomial, which it is
advisable to reduce before further work. Here is an example involving
the field **Q**(zeta_5, 5^{1/5}):

? L = polcompositum(x^5 - 5, polcyclo(5), 1); \\ list of [R,a,b,k] ? [R, a] = L[1]; \\ pick the single factor, extract R,a (ignore b,k) ? R \\ defines the compositum %3 = x^20 + 5*x^19 + 15*x^18 + 35*x^17 + 70*x^16 + 141*x^15 + 260*x^14\ + 355*x^13 + 95*x^12 - 1460*x^11 - 3279*x^10 - 3660*x^9 - 2005*x^8 \ + 705*x^7 + 9210*x^6 + 13506*x^5 + 7145*x^4 - 2740*x^3 + 1040*x^2 \ - 320*x + 256 ? a^5 - 5 \\ a fifth root of 5 %4 = 0 ? [T, X] = polredbest(R, 1); ? T \\ simpler defining polynomial forQ[x]/(R) %6 = x^20 + 25*x^10 + 5 ? X \\ root of R inQ[y]/(T(y)) %7 = Mod(-1/11*x^15 - 1/11*x^14 + 1/22*x^10 - 47/22*x^5 - 29/11*x^4 + 7/22,\ x^20 + 25*x^10 + 5) ? a = subst(a.pol, 'x, X) \\`a`

in the new coordinates %8 = Mod(1/11*x^14 + 29/11*x^4, x^20 + 25*x^10 + 5) ? a^5 - 5 %9 = 0

The library syntax is `GEN `

.
Also available are
**polcompositum0**(GEN P, GEN Q, long flag)`GEN `

(**compositum**(GEN P, GEN Q)*flag* = 0) and
`GEN `

(**compositum2**(GEN P, GEN Q)*flag* = 1).

Galois group of the non-constant
polynomial T belongs to **Q**[X]. In the present version **2.7.0**, T must be irreducible
and the degree d of T must be less than or equal to 7. If the
`galdata`

package has been installed, degrees 8, 9, 10 and 11 are also
implemented. By definition, if K = **Q**[x]/(T), this computes the action of
the Galois group of the Galois closure of K on the d distinct roots of
T, up to conjugacy (corresponding to different root orderings).

The output is a 4-component vector [n,s,k,name] with the following meaning: n is the cardinality of the group, s is its signature (s = 1 if the group is a subgroup of the alternating group A_d, s = -1 otherwise) and name is a character string containing name of the transitive group according to the GAP 4 transitive groups library by Alexander Hulpke.

k is more arbitrary and the choice made up to version 2.2.3 of PARI is rather
unfortunate: for d > 7, k is the numbering of the group among all
transitive subgroups of S_d, as given in "The transitive groups of degree up
to eleven", G. Butler and J. McKay, *Communications in Algebra*, vol. 11,
1983,
pp. 863--911 (group k is denoted T_k there). And for d `<=`

7, it was ad
hoc, so as to ensure that a given triple would denote a unique group.
Specifically, for polynomials of degree d `<=`

7, the groups are coded as
follows, using standard notations

In degree 1: S_1 = [1,1,1].

In degree 2: S_2 = [2,-1,1].

In degree 3: A_3 = C_3 = [3,1,1], S_3 = [6,-1,1].

In degree 4: C_4 = [4,-1,1], V_4 = [4,1,1], D_4 = [8,-1,1], A_4 = [12,1,1], S_4 = [24,-1,1].

In degree 5: C_5 = [5,1,1], D_5 = [10,1,1], M_{20} = [20,-1,1], A_5 = [60,1,1], S_5 = [120,-1,1].

In degree 6: C_6 = [6,-1,1], S_3 = [6,-1,2], D_6 = [12,-1,1], A_4 = [12,1,1], G_{18} = [18,-1,1], S_4^ -= [24,-1,1], A_4 x C_2 = [24,-1,2], S_4^ += [24,1,1], G_{36}^ -= [36,-1,1], G_{36}^ += [36,1,1], S_4 x C_2 = [48,-1,1], A_5 = PSL_2(5) = [60,1,1], G_{72} = [72,-1,1], S_5 = PGL_2(5) = [120,-1,1], A_6 = [360,1,1], S_6 = [720,-1,1].

In degree 7: C_7 = [7,1,1], D_7 = [14,-1,1], M_{21} = [21,1,1], M_{42} = [42,-1,1], PSL_2(7) = PSL_3(2) = [168,1,1], A_7 = [2520,1,1], S_7 = [5040,-1,1].

This is deprecated and obsolete, but for reasons of backward compatibility,
we cannot change this behavior yet. So you can use the default
`new_galois_format`

to switch to a consistent naming scheme, namely k is
always the standard numbering of the group among all transitive subgroups of
S_n. If this default is in effect, the above groups will be coded as:

In degree 1: S_1 = [1,1,1].

In degree 2: S_2 = [2,-1,1].

In degree 3: A_3 = C_3 = [3,1,1], S_3 = [6,-1,2].

In degree 4: C_4 = [4,-1,1], V_4 = [4,1,2], D_4 = [8,-1,3], A_4 = [12,1,4], S_4 = [24,-1,5].

In degree 5: C_5 = [5,1,1], D_5 = [10,1,2], M_{20} = [20,-1,3], A_5 = [60,1,4], S_5 = [120,-1,5].

In degree 6: C_6 = [6,-1,1], S_3 = [6,-1,2], D_6 = [12,-1,3], A_4 = [12,1,4], G_{18} = [18,-1,5], A_4 x C_2 = [24,-1,6], S_4^ += [24,1,7], S_4^ -= [24,-1,8], G_{36}^ -= [36,-1,9], G_{36}^ += [36,1,10], S_4 x C_2 = [48,-1,11], A_5 = PSL_2(5) = [60,1,12], G_{72} = [72,-1,13], S_5 = PGL_2(5) = [120,-1,14], A_6 = [360,1,15], S_6 = [720,-1,16].

In degree 7: C_7 = [7,1,1], D_7 = [14,-1,2], M_{21} = [21,1,3], M_{42} = [42,-1,4], PSL_2(7) = PSL_3(2) = [168,1,5], A_7 = [2520,1,6], S_7 = [5040,-1,7].

**Warning.** The method used is that of resolvent polynomials and is
sensitive to the current precision. The precision is updated internally but,
in very rare cases, a wrong result may be returned if the initial precision
was not sufficient.

The library syntax is `GEN `

.
To enable the new format in library mode,
set the global variable **polgalois**(GEN T, long prec)`new_galois_format`

to 1.

This function is *deprecated*, use `polredbest`

instead.
Finds polynomials with reasonably small coefficients defining subfields of
the number field defined by T. One of the polynomials always defines **Q**
(hence is equal to x-1), and another always defines the same number field
as T if T is irreducible.

All T accepted by `nfinit`

are also allowed here;
in particular, the format `[T, listP]`

is recommended, e.g. with
`listP`

= 10^5 or a vector containing all ramified primes. Otherwise,
the maximal order of **Q**[x]/(T) must be computed.

The following binary digits of *flag* are significant:

1: Possibly use a suborder of the maximal order. The
primes dividing the index of the order chosen are larger than
`primelimit`

or divide integers stored in the `addprimes`

table.
This flag is *deprecated*, the `[T, listP]`

format is more
flexible.

2: gives also elements. The result is a two-column matrix, the first column giving primitive elements defining these subfields, the second giving the corresponding minimal polynomials.

? M = polred(x^4 + 8, 2) %1 = [1 x - 1] [1/2*x^2 x^2 + 2] [1/4*x^3 x^4 + 2] [x x^4 + 8] ? minpoly(Mod(M[2,1], x^4+8)) %2 = x^2 + 2

The library syntax is

(**polred**(GEN T)*flag* = 0). Also available is
`GEN `

(**polred2**(GEN T)*flag* = 2). The function `polred0`

is
deprecated, provided for backward compatibility.

Returns a canonical defining polynomial P for the number field
**Q**[X]/(T) defined by T, such that the sum of the squares of the modulus
of the roots (i.e. the T_2-norm) is minimal. Different T defining
isomorphic number fields will yield the same P. All T accepted by
`nfinit`

are also allowed here, e.g. non-monic polynomials, or pairs
`[T, listP]`

specifying that a non-maximal order may be used.

**Warning 1.** Using a `t_POL`

T requires fully factoring the
discriminant of T, which may be very hard. The format `[T, listP]`

computes only a suborder of the maximal order and replaces this part of the
algorithm by a polynomial time computation. In that case the polynomial P
is a priori no longer canonical, and it may happen that it does not have
minimal T_2 norm. The routine attempts to certify the result independently
of this order computation (as per `nfcertify`

: we try to prove that the
order is maximal); if it fails, the routine returns 0 instead of P.
In order to force an output in that case as well, you may either use
`polredbest`

, or `polredabs(,16)`

, or

polredabs([T, nfbasis([T, listP])])(In all three cases, the result is no longer canonical.)

**Warning 2.** Apart from the factorization of the discriminant of
T, this routine runs in polynomial time for a *fixed* degree.
But the complexity is exponential in the degree: this routine
may be exceedingly slow when the number field has many subfields, hence a
lot of elements of small T_2-norm. If you do not need a canonical
polynomial, the function `polredbest`

is in general much faster (it runs
in polynomial time), and tends to return polynomials with smaller
discriminants.

The binary digits of *flag* mean

1: outputs a two-component row vector [P,a], where P is the default
output and `Mod(a, P)`

is a root of the original T.

4: gives *all* polynomials of minimal T_2 norm; of the two polynomials
P(x) and ± P(-x), only one is given.

16: Possibly use a suborder of the maximal order, *without* attempting to
certify the result as in Warning 1: we always return a polynomial and never
0. The result is a priori not canonical.

? T = x^16 - 136*x^14 + 6476*x^12 - 141912*x^10 + 1513334*x^8 \ - 7453176*x^6 + 13950764*x^4 - 5596840*x^2 + 46225 ? T1 = polredabs(T); T2 = polredbest(T); ? [ norml2(polroots(T1)), norml2(polroots(T2)) ] %3 = [88.0000000, 120.000000] ? [ sizedigit(poldisc(T1)), sizedigit(poldisc(T2)) ] %4 = [75, 67]

The library syntax is `GEN `

.
Instead of the above hardcoded numerical flags, one should use an
or-ed combination of**polredabs0**(GEN T, long flag)

***** `nf_PARTIALFACT`

: possibly use a suborder of the maximal order,
*without* attempting to certify the result.

***** `nf_ORIG`

: return [P, a], where `Mod(a, P)`

is a root of T.

***** `nf_RAW`

: return [P, b], where `Mod(b, T)`

is a root of P.
The algebraic integer b is the raw result produced by the small vectors
enumeration in the maximal order; P was computed as the characteristic
polynomial of `Mod(b, T)`

. `Mod(a, P)`

as in `nf_ORIG`

is obtained with `modreverse`

.

***** `nf_ADDZK`

: if r is the result produced with some of the above
flags (of the form P or [P,c]), return `[r,zk]`

, where `zk`

is a
**Z**-basis for the maximal order of **Q**[X]/(P).

***** `nf_ALL`

: return a vector of results of the above form, for all
polynomials of minimal T_2-norm.

Finds a polynomial with reasonably
small coefficients defining the same number field as T.
All T accepted by `nfinit`

are also allowed here (e.g. non-monic
polynomials, `nf`

, `bnf`

, `[T,Z_K_basis]`

). Contrary to
`polredabs`

, this routine runs in polynomial time, but it offers no
guarantee as to the minimality of its result.

This routine computes an LLL-reduced basis for the ring of integers of
**Q**[X]/(T), then examines small linear combinations of the basis vectors,
computing their characteristic polynomials. It returns the *separable*
P polynomial of smallest discriminant (the one with lexicographically
smallest `abs(Vec(P))`

in case of ties). This is a good candidate
for subsequent number field computations, since it guarantees that
the denominators of algebraic integers, when expressed in the power basis,
are reasonably small. With no claim of minimality, though.

It can happen that iterating this functions yields better and better polynomials, until it stabilizes:

? \p5 ? P = X^12+8*X^8-50*X^6+16*X^4-3069*X^2+625; ? poldisc(P)*1. %2 = 1.2622 E55 ? P = polredbest(P); ? poldisc(P)*1. %4 = 2.9012 E51 ? P = polredbest(P); ? poldisc(P)*1. %6 = 8.8704 E44In this example, the initial polynomial P is the one returned by

`polredabs`

, and the last one is stable.
If *flag* = 1: outputs a two-component row vector [P,a], where P is the
default output and `Mod(a, P)`

is a root of the original T.

? [P,a] = polredbest(x^4 + 8, 1) %1 = [x^4 + 2, Mod(x^3, x^4 + 2)] ? charpoly(a) %2 = x^4 + 8In particular, the map

`|--->`

`Mod(a,P)`

defines an isomorphism of number fields, which can
be computed as

subst(lift(Q), 'x, a)if Q is a

`t_POLMOD`

modulo T; `b = modreverse(a)`

returns a `t_POLMOD`

giving the inverse of the above map (which should be
useless since
The library syntax is `GEN `

.**polredbest**(GEN T, long flag)

Finds polynomials with reasonably small
coefficients and of the same degree as that of x defining suborders of the
order defined by x. One of the polynomials always defines **Q** (hence
is equal to (x-1)^n, where n is the degree), and another always defines
the same order as x if x is irreducible. Useless function: try
`polredbest`

.

The library syntax is `GEN `

.**polredord**(GEN x)

Applies a random Tschirnhausen
transformation to the polynomial x, which is assumed to be non-constant
and separable, so as to obtain a new equation for the étale algebra
defined by x. This is for instance useful when computing resolvents,
hence is used by the `polgalois`

function.

The library syntax is `GEN `

.**tschirnhaus**(GEN x)

Expresses x on the relative
integral basis. Here, *rnf* is a relative number field extension L/K
as output by `rnfinit`

, and x an element of L in absolute form, i.e.
expressed as a polynomial or polmod with polmod coefficients, *not* on
the relative integral basis.

The library syntax is `GEN `

.**rnfalgtobasis**(GEN rnf, GEN x)

Let K the field represented by
*bnf*, as output by `bnfinit`

. M is a projective **Z**_K-module
of rank n (M\otimes K is an n-dimensional K-vector space), given by a
pseudo-basis of size n. The routine returns either a true **Z**_K-basis of
M (of size n) if it exists, or an n+1-element generating set of M if
not.

It is allowed to use an irreducible polynomial P in K[X] instead of M,
in which case, M is defined as the ring of integers of K[X]/(P), viewed
as a **Z**_K-module.

The library syntax is `GEN `

.**rnfbasis**(GEN bnf, GEN M)

Computes the representation of x
as a polmod with polmods coefficients. Here, *rnf* is a relative number
field extension L/K as output by `rnfinit`

, and x an element of
L expressed on the relative integral basis.

The library syntax is `GEN `

.**rnfbasistoalg**(GEN rnf, GEN x)

Characteristic polynomial of
a over *nf*, where a belongs to the algebra defined by T over
*nf*, i.e. *nf*[X]/(T). Returns a polynomial in variable v
(x by default).

? nf = nfinit(y^2+1); ? rnfcharpoly(nf, x^2+y*x+1, x+y) %2 = x^2 + Mod(-y, y^2 + 1)*x + 1

The library syntax is `GEN `

, where **rnfcharpoly**(GEN nf, GEN T, GEN a, long var = -1)`var`

is a variable number.

Given *bnf*
as output by `bnfinit`

, and *pol* a relative polynomial defining an
Abelian extension, computes the class field theory conductor of this
Abelian extension. The result is a 3-component vector
[*conductor*,*rayclgp*,*subgroup*], where *conductor* is
the conductor of the extension given as a 2-component row vector
[f_0,f_ oo ], *rayclgp* is the full ray class group corresponding to
the conductor given as a 3-component vector [h,cyc,gen] as usual for a group,
and *subgroup* is a matrix in HNF defining the subgroup of the ray class
group on the given generators gen.

The library syntax is `GEN `

.**rnfconductor**(GEN bnf, GEN pol)

Given a number field K coded by *nf* and a monic
polynomial P belongs to **Z**_K[X], irreducible over K and thus defining a relative
extension L of K, applies Dedekind's criterion to the order
**Z**_K[X]/(P), at the prime ideal *pr*. It is possible to set *pr*
to a vector of prime ideals (test maximality at all primes in the vector),
or to omit altogether, in which case maximality at *all* primes is tested;
in this situation *flag* is automatically set to 1.

The default historic behavior (*flag* is 0 or omitted and *pr* is a
single prime ideal) is not so useful since
`rnfpseudobasis`

gives more information and is generally not that
much slower. It returns a 3-component vector [*max*, *basis*, v]:

***** *basis* is a pseudo-basis of an enlarged order O produced by
Dedekind's criterion, containing the original order **Z**_K[X]/(P)
with index a power of *pr*. Possibly equal to the original order.

***** *max* is a flag equal to 1 if the enlarged order O
could be proven to be *pr*-maximal and to 0 otherwise; it may still be
maximal in the latter case if *pr* is ramified in L,

***** v is the valuation at *pr* of the order discriminant.

If *flag* is non-zero, on the other hand, we just return 1 if the order
**Z**_K[X]/(P) is *pr*-maximal (resp. maximal at all relevant primes, as
described above), and 0 if not. This is much faster than the default,
since the enlarged order is not computed.

? nf = nfinit(y^2-3); P = x^3 - 2*y; ? pr3 = idealprimedec(nf,3)[1]; ? rnfdedekind(nf, P, pr3) %2 = [1, [[1, 0, 0; 0, 1, 0; 0, 0, 1], [1, 1, 1]], 8] ? rnfdedekind(nf, P, pr3, 1) %3 = 1In this example,

`pr3`

is the ramified ideal above 3,
and the order generated by the cube roots of y is already
`pr3`

-maximal. The order-discriminant has valuation 8. On the other
hand, the order is not maximal at the prime above 2:

? pr2 = idealprimedec(nf,2)[1]; ? rnfdedekind(nf, P, pr2, 1) %5 = 0 ? rnfdedekind(nf, P, pr2) %6 = [0, [[2, 0, 0; 0, 1, 0; 0, 0, 1], [[1, 0; 0, 1], [1, 0; 0, 1], [1, 1/2; 0, 1/2]]], 2]

The enlarged order is not proven to be `pr2`

-maximal yet. In fact, it
is; it is in fact the maximal order:

? B = rnfpseudobasis(nf, P) %7 = [[1, 0, 0; 0, 1, 0; 0, 0, 1], [1, 1, [1, 1/2; 0, 1/2]], [162, 0; 0, 162], -1] ? idealval(nf,B[3], pr2) %4 = 2

It is possible to use this routine with non-monic
P = sum_{i `<=`

n} a_i X^i belongs to **Z**_K[X] if *flag* = 1;
in this case, we test maximality of Dedekind's order generated by
1, a_n alpha, a_nalpha^2 + a_{n-1}alpha,...,
a_nalpha^{n-1} + a_{n-1}alpha^{n-2} +...+ a_1alpha.
The routine will fail if P is 0 on the projective line over the residue
field **Z**_K/`pr`

(FIXME).

The library syntax is `GEN `

.**rnfdedekind**(GEN nf, GEN pol, GEN pr = NULL, long flag)

Given a pseudo-matrix M over the maximal
order of *nf*, computes its determinant.

The library syntax is `GEN `

.**rnfdet**(GEN nf, GEN M)

Given a number field *nf* as
output by `nfinit`

and a polynomial *pol* with coefficients in
*nf* defining a relative extension L of *nf*, computes the
relative discriminant of L. This is a two-element row vector [D,d], where
D is the relative ideal discriminant and d is the relative discriminant
considered as an element of *nf*^*/{*nf*^*}^2. The main variable of
*nf* *must* be of lower priority than that of *pol*, see
Section [**Label: se:priority**].

The library syntax is `GEN `

.**rnfdiscf**(GEN nf, GEN pol)

*rnf* being a relative
number field extension L/K as output by `rnfinit`

and x being an
element of L expressed as a polynomial modulo the absolute equation

, computes x as an element of the relative extension
L/K as a polmod with polmod coefficients.*rnf*.pol

? K = nfinit(y^2+1); L = rnfinit(K, x^2-y); ? L.pol %2 = x^4 + 1 ? rnfeltabstorel(L, Mod(x, L.pol)) %3 = Mod(x, x^2 + Mod(-y, y^2 + 1)) ? rnfeltabstorel(L, Mod(2, L.pol)) %4 = 2 ? rnfeltabstorel(L, Mod(x, x^2-y)) *** at top-level: rnfeltabstorel(L,Mod *** ^-------------------- *** rnfeltabstorel: inconsistent moduli in rnfeltabstorel: x^2-y != x^4+1

The library syntax is `GEN `

.**rnfeltabstorel**(GEN rnf, GEN x)

*rnf* being a relative number
field extension L/K as output by `rnfinit`

and x being an element of
L expressed as a polynomial or polmod with polmod coefficients, computes
x as an element of K as a polmod, assuming x is in K (otherwise a
domain error occurs).

? K = nfinit(y^2+1); L = rnfinit(K, x^2-y); ? L.pol %2 = x^4 + 1 ? rnfeltdown(L, Mod(x^2, L.pol)) %3 = Mod(y, y^2 + 1) ? rnfeltdown(L, Mod(y, x^2-y)) %4 = Mod(y, y^2 + 1) ? rnfeltdown(L, Mod(y,K.pol)) %5 = Mod(y, y^2 + 1) ? rnfeltdown(L, Mod(x, L.pol)) *** at top-level: rnfeltdown(L,Mod(x,x *** ^-------------------- *** rnfeltdown: domain error in rnfeltdown: element not in the base field

The library syntax is `GEN `

.**rnfeltdown**(GEN rnf, GEN x)

*rnf* being a relative number field extension L/K as output by
`rnfinit`

and x being an element of L, returns the relative norm
N_{L/K}(x) as an element of K.

? K = nfinit(y^2+1); L = rnfinit(K, x^2-y); ? rnfeltnorm(L, Mod(x, L.pol)) %2 = Mod(x, x^2 + Mod(-y, y^2 + 1)) ? rnfeltnorm(L, 2) %3 = 4 ? rnfeltnorm(L, Mod(x, x^2-y))

The library syntax is `GEN `

.**rnfeltnorm**(GEN rnf, GEN x)

*rnf* being a relative
number field extension L/K as output by `rnfinit`

and x being an
element of L expressed as a polynomial or polmod with polmod
coefficients, computes x as an element of the absolute extension L/**Q** as
a polynomial modulo the absolute equation

.*rnf*.pol

? K = nfinit(y^2+1); L = rnfinit(K, x^2-y); ? L.pol %2 = x^4 + 1 ? rnfeltreltoabs(L, Mod(x, L.pol)) %3 = Mod(x, x^4 + 1) ? rnfeltreltoabs(L, Mod(y, x^2-y)) %4 = Mod(x^2, x^4 + 1) ? rnfeltreltoabs(L, Mod(y,K.pol)) %5 = Mod(x^2, x^4 + 1)

The library syntax is `GEN `

.**rnfeltreltoabs**(GEN rnf, GEN x)

*rnf* being a relative number field extension L/K as output by
`rnfinit`

and x being an element of L, returns the relative trace
N_{L/K}(x) as an element of K.

? K = nfinit(y^2+1); L = rnfinit(K, x^2-y); ? rnfelttrace(L, Mod(x, L.pol)) %2 = 0 ? rnfelttrace(L, 2) %3 = 4 ? rnfelttrace(L, Mod(x, x^2-y))

The library syntax is `GEN `

.**rnfelttrace**(GEN rnf, GEN x)

*rnf* being a relative number field extension L/K as output by
`rnfinit`

and x being an element of K, computes x as an element of
the absolute extension L/**Q** as a polynomial modulo the absolute equation

.*rnf*.pol

? K = nfinit(y^2+1); L = rnfinit(K, x^2-y); ? L.pol %2 = x^4 + 1 ? rnfeltup(L, Mod(y, K.pol)) %4 = Mod(x^2, x^4 + 1) ? rnfeltup(L, y) %5 = Mod(x^2, x^4 + 1) ? rnfeltup(L, [1,2]~) \\ in terms of K.zk %6 = Mod(2*x^2 + 1, x^4 + 1)

The library syntax is `GEN `

.**rnfeltup**(GEN rnf, GEN x)

Given a number field
*nf* as output by `nfinit`

(or simply a polynomial) and a
polynomial *pol* with coefficients in *nf* defining a relative
extension L of *nf*, computes an absolute equation of L over
**Q**.

The main variable of *nf* *must* be of lower priority than that
of *pol* (see Section [**Label: se:priority**]). Note that for efficiency, this does
not check whether the relative equation is irreducible over *nf*, but
only if it is squarefree. If it is reducible but squarefree, the result will
be the absolute equation of the étale algebra defined by *pol*. If
*pol* is not squarefree, raise an `e_DOMAIN`

exception.

? rnfequation(y^2+1, x^2 - y) %1 = x^4 + 1 ? T = y^3-2; rnfequation(nfinit(T), (x^3-2)/(x-Mod(y,T))) %2 = x^6 + 108 \\ Galois closure of Q(2^(1/3))

If *flag* is non-zero, outputs a 3-component row vector [z,a,k], where

***** z is the absolute equation of L over **Q**, as in the default
behavior,

***** a expresses as a `t_POLMOD`

modulo z a root alpha of the
polynomial defining the base field *nf*,

***** k is a small integer such that theta = beta+kalpha
is a root of z, where beta is a root of *pol*.

? T = y^3-2; pol = x^2 +x*y + y^2; ? [z,a,k] = rnfequation(T, pol, 1); ? z %4 = x^6 + 108 ? subst(T, y, a) %5 = 0 ? alpha= Mod(y, T); ? beta = Mod(x*Mod(1,T), pol); ? subst(z, x, beta + k*alpha) %8 = 0

The library syntax is `GEN `

.
Also available are
**rnfequation0**(GEN nf, GEN pol, long flag)`GEN `

(**rnfequation**(GEN nf, GEN pol)*flag* = 0) and
`GEN `

(**rnfequation2**(GEN nf, GEN pol)*flag* = 1).

Given *bnf* as output by
`bnfinit`

, and either a polynomial x with coefficients in *bnf*
defining a relative extension L of *bnf*, or a pseudo-basis x of
such an extension, gives either a true *bnf*-basis of L in upper
triangular Hermite normal form, if it exists, and returns 0 otherwise.

The library syntax is `GEN `

.**rnfhnfbasis**(GEN bnf, GEN x)

Let *rnf* be a relative
number field extension L/K as output by `rnfinit`

and x be an ideal of
the absolute extension L/**Q** given by a **Z**-basis of elements of L.
Returns the relative pseudo-matrix in HNF giving the ideal x considered as
an ideal of the relative extension L/K, i.e. as a **Z**_K-module.

The reason why the input does not use the customary HNF in terms of a fixed
**Z**-basis for **Z**_L is precisely that no such basis has been explicitly
specified. On the other hand, if you already computed an (absolute) *nf*
structure `Labs`

associated to L, and m is in HNF, defining
an (absolute) ideal with respect to the **Z**-basis `Labs.zk`

, then
`Labs.zk * m`

is a suitable **Z**-basis for the ideal, and

rnfidealabstorel(rnf, Labs.zk * m)converts m to a relative ideal.

? K = nfinit(y^2+1); L = rnfinit(K, x^2-y); Labs = nfinit(L.pol); ? m = idealhnf(Labs, 17, x^3+2); ? B = rnfidealabstorel(L, Labs.zk * m) %3 = [[1, 8; 0, 1], [[17, 4; 0, 1], 1]] \\ pseudo-basis for m as Z_K-module ? A = rnfidealreltoabs(L, B) %4 = [17, x^2 + 4, x + 8, x^3 + 8*x^2] \\ Z-basis for m in Q[x]/(L.pol) ? mathnf(matalgtobasis(Labs, A)) %5 = [17 8 4 2] [ 0 1 0 0] [ 0 0 1 0] [ 0 0 0 1] ? % == m %6 = 1

The library syntax is `GEN `

.**rnfidealabstorel**(GEN rnf, GEN x)

Let *rnf* be a relative number
field extension L/K as output by `rnfinit`

, and x an ideal of
L, given either in relative form or by a **Z**-basis of elements of L
(see Section [**Label: se:rnfidealabstorel**]). This function returns the ideal of K
below x, i.e. the intersection of x with K.

The library syntax is `GEN `

.**rnfidealdown**(GEN rnf, GEN x)

*rnf* being a relative number
field extension L/K as output by `rnfinit`

and x being a relative
ideal (which can be, as in the absolute case, of many different types,
including of course elements), computes the HNF pseudo-matrix associated to
x, viewed as a **Z**_K-module.

The library syntax is `GEN `

.**rnfidealhnf**(GEN rnf, GEN x)

*rnf* being a relative number
field extension L/K as output by `rnfinit`

and x and y being ideals
of the relative extension L/K given by pseudo-matrices, outputs the ideal
product, again as a relative ideal.

The library syntax is `GEN `

.**rnfidealmul**(GEN rnf, GEN x, GEN y)

Let *rnf* be a relative
number field extension L/K as output by `rnfinit`

and let x be a
relative ideal (which can be, as in the absolute case, of many different
types, including of course elements). This function computes the norm of the
x considered as an ideal of the absolute extension L/**Q**. This is
identical to

idealnorm(rnf, rnfidealnormrel(rnf,x))but faster.

The library syntax is `GEN `

.**rnfidealnormabs**(GEN rnf, GEN x)

Let *rnf* be a relative
number field extension L/K as output by `rnfinit`

and let x be a
relative ideal (which can be, as in the absolute case, of many different
types, including of course elements). This function computes the relative
norm of x as an ideal of K in HNF.

The library syntax is `GEN `

.**rnfidealnormrel**(GEN rnf, GEN x)

Let *rnf* be a relative
number field extension L/K as output by `rnfinit`

and let x be a
relative ideal, given as a **Z**_K-module by a pseudo matrix [A,I].
This function returns the ideal x as an absolute ideal of L/**Q** in
the form of a **Z**-basis, given by a vector of polynomials (modulo
`rnf.pol`

).

The reason why we do not return the customary HNF in terms of a fixed
**Z**-basis for **Z**_L is precisely that no such basis has been explicitly
specified. On the other hand, if you already computed an (absolute) *nf*
structure `Labs`

associated to L, then

xabs = rnfidealreltoabs(L, x); xLabs = mathnf(matalgtobasis(Labs, xabs));computes a traditional HNF

`xLabs`

for x in terms of
the fixed `Labs.zk`

.
The library syntax is `GEN `

.**rnfidealreltoabs**(GEN rnf, GEN x)

*rnf* being a relative
number field extension L/K as output by `rnfinit`

and x being an
ideal of the relative extension L/K given by a pseudo-matrix, gives a
vector of two generators of x over **Z**_L expressed as polmods with polmod
coefficients.

The library syntax is `GEN `

.**rnfidealtwoelement**(GEN rnf, GEN x)

Let *rnf* be a relative number
field extension L/K as output by `rnfinit`

and let x be an ideal of
K. This function returns the ideal x**Z**_L as an absolute ideal of L/**Q**,
in the form of a **Z**-basis, given by a vector of polynomials (modulo
`rnf.pol`

).

The reason why we do not return the customary HNF in terms of a fixed
**Z**-basis for **Z**_L is precisely that no such basis has been explicitly
specified. On the other hand, if you already computed an (absolute) *nf*
structure `Labs`

associated to L, then

xabs = rnfidealup(L, x); xLabs = mathnf(matalgtobasis(Labs, xabs));computes a traditional HNF

`xLabs`

for x in terms of
the fixed `Labs.zk`

.
The library syntax is `GEN `

.**rnfidealup**(GEN rnf, GEN x)

*nf* being a number field in `nfinit`

format considered as base field, and *pol* a polynomial defining a relative
extension over *nf*, this computes data to work in the
relative extension. The main variable of *pol* must be of higher priority
(see Section [**Label: se:priority**]) than that of *nf*, and the coefficients of
*pol* must be in *nf*.

The result is a row vector, whose components are technical. In the following
description, we let K be the base field defined by *nf* and L/K
the large field associated to the *rnf*. Furthermore, we let
m = [K:**Q**] the degree of the base field, n = [L:K] the relative degree,
r_1 and r_2 the number of real and complex places of K. Acces to this
information via *member functions* is preferred since the specific
data organization specified below will change in the future.

*rnf*[1](`rnf.pol`

) contains the relative polynomial *pol*.

*rnf*[2] contains the integer basis [A,d] of K, as
(integral) elements of L/**Q**. More precisely, A is a vector of
polynomial with integer coefficients, d is a denominator, and the integer
basis is given by A/d.

*rnf*[3] (`rnf.disc`

) is a two-component row vector
[**d**(L/K),s] where **d**(L/K) is the relative ideal discriminant
of L/K and s is the discriminant of L/K viewed as an element of
K^*/(K^*)^2, in other words it is the output of `rnfdisc`

.

*rnf*[4](`rnf.index`

) is the ideal index **f**, i.e. such
that d(pol)**Z**_K = **f**^2**d**(L/K).

*rnf*[5] is currently unused.

*rnf*[6] is currently unused.

*rnf*[7] (`rnf.zk`

) is the pseudo-basis (A,I) for the maximal
order **Z**_L as a **Z**_K-module: A is the relative integral pseudo basis
expressed as polynomials (in the variable of pol) with polmod coefficients
in *nf*, and the second component I is the ideal list of the
pseudobasis in HNF.

*rnf*[8] is the inverse matrix of the integral basis matrix, with
coefficients polmods in *nf*.

*rnf*[9] is currently unused.

*rnf*[10] (`rnf.nf`

) is *nf*.

*rnf*[11] is the output of `rnfequation(K, pol, 1)`

. Namely, a
vector [P, a, k] describing the *absolute* extension
L/**Q**: P is an absolute equation, more conveniently obtained
as `rnf.polabs`

; a expresses the generator alpha = y mod `K.pol`

of the number field K as an element of L, i.e. a polynomial modulo the
absolute equation P;

k is a small integer such that, if beta is an abstract root of *pol*
and alpha the generator of K given above, then P(beta + kalpha) = 0.

**Caveat..** Be careful if k != 0 when dealing simultaneously with
absolute and relative quantities since L = **Q**(beta + kalpha) =
K(alpha), and the generator chosen for the absolute extension is not the
same as for the relative one. If this happens, one can of course go on
working, but we advise to change the relative polynomial so that its root
becomes beta + k alpha. Typical GP instructions would be

[P,a,k] = rnfequation(K, pol, 1); if (k, pol = subst(pol, x, x - k*Mod(y, K.pol))); L = rnfinit(K, pol);

*rnf*[12] is by default unused and set equal to 0. This field is used
to store further information about the field as it becomes available (which
is rarely needed, hence would be too expensive to compute during the initial
`rnfinit`

call).

The library syntax is `GEN `

.**rnfinit**(GEN nf, GEN pol)

T being a relative polynomial with coefficients
in *nf*, return 1 if it defines an abelian extension, and 0 otherwise.

? K = nfinit(y^2 + 23); ? rnfisabelian(K, x^3 - 3*x - y) %2 = 1

The library syntax is `long `

.**rnfisabelian**(GEN nf, GEN T)

Given *bnf* as output by
`bnfinit`

, and either a polynomial x with coefficients in *bnf*
defining a relative extension L of *bnf*, or a pseudo-basis x of
such an extension, returns true (1) if L/*bnf* is free, false (0) if
not.

The library syntax is `long `

.**rnfisfree**(GEN bnf, GEN x)

Similar to
`bnfisnorm`

but in the relative case. T is as output by
`rnfisnorminit`

applied to the extension L/K. This tries to decide
whether the element a in K is the norm of some x in the extension
L/K.

The output is a vector [x,q], where a = Norm(x)*q. The
algorithm looks for a solution x which is an S-integer, with S a list
of places of K containing at least the ramified primes, the generators of
the class group of L, as well as those primes dividing a. If L/K is
Galois, then this is enough; otherwise, *flag* is used to add more primes to
S: all the places above the primes p `<=`

*flag* (resp. p|*flag*) if *flag* > 0
(resp. *flag* < 0).

The answer is guaranteed (i.e. a is a norm iff q = 1) if the field is Galois, or, under GRH, if S contains all primes less than 12log^2|disc(M)|, where M is the normal closure of L/K.

If `rnfisnorminit`

has determined (or was told) that L/K is
Galois, and *flag* != 0, a Warning is issued (so that you can set
*flag* = 1 to check whether L/K is known to be Galois, according to T).
Example:

bnf = bnfinit(y^3 + y^2 - 2*y - 1); p = x^2 + Mod(y^2 + 2*y + 1, bnf.pol); T = rnfisnorminit(bnf, p); rnfisnorm(T, 17)

checks whether 17 is a norm in the Galois extension **Q**(beta) /
**Q**(alpha), where alpha^3 + alpha^2 - 2alpha - 1 = 0 and beta^2 +
alpha^2 + 2alpha + 1 = 0 (it is).

The library syntax is `GEN `

.**rnfisnorm**(GEN T, GEN a, long flag)

Let K be defined by a root of *pol*, and L/K the extension defined
by the polynomial *polrel*. As usual, *pol* can in fact be an *nf*,
or *bnf*, etc; if *pol* has degree 1 (the base field is **Q**),
polrel is also allowed to be an *nf*, etc. Computes technical data needed
by `rnfisnorm`

to solve norm equations Nx = a, for x in L, and a
in K.

If *flag* = 0, do not care whether L/K is Galois or not.

If *flag* = 1, L/K is assumed to be Galois (unchecked), which speeds up
`rnfisnorm`

.

If *flag* = 2, let the routine determine whether L/K is Galois.

The library syntax is `GEN `

.**rnfisnorminit**(GEN pol, GEN polrel, long flag)

*bnr*
being as output by `bnrinit`

, finds a relative equation for the
class field corresponding to the module in *bnr* and the given
congruence subgroup (the full ray class field if *subgp* is omitted).
If d is positive, outputs the list of all relative equations of
degree d contained in the ray class field defined by *bnr*, with
the *same* conductor as (*bnr*, *subgp*).

**Warning.** This routine only works for subgroups of prime index. It
uses Kummer theory, adjoining necessary roots of unity (it needs to compute a
tough `bnfinit`

here), and finds a generator via Hecke's characterization
of ramification in Kummer extensions of prime degree. If your extension does
not have prime degree, for the time being, you have to split it by hand as a
tower / compositum of such extensions.

The library syntax is `GEN `

.**rnfkummer**(GEN bnr, GEN subgp = NULL, long d, long prec)

Given a polynomial
*pol* with coefficients in *nf* defining a relative extension L and
a suborder *order* of L (of maximal rank), as output by
`rnfpseudobasis`

(*nf*,*pol*) or similar, gives
[[*neworder*],U], where *neworder* is a reduced order and U is
the unimodular transformation matrix.

The library syntax is `GEN `

.**rnflllgram**(GEN nf, GEN pol, GEN order, long prec)

*bnr* being a big ray
class field as output by `bnrinit`

and *pol* a relative polynomial
defining an Abelian extension, computes the norm group (alias Artin
or Takagi group) corresponding to the Abelian extension of
*bnf* = `bnr.bnf`

defined by *pol*, where the module corresponding to *bnr* is assumed
to be a multiple of the conductor (i.e. *pol* defines a subextension of
bnr). The result is the HNF defining the norm group on the given generators
of `bnr.gen`

. Note that neither the fact that *pol* defines an
Abelian extension nor the fact that the module is a multiple of the conductor
is checked. The result is undefined if the assumption is not correct.

The library syntax is `GEN `

.**rnfnormgroup**(GEN bnr, GEN pol)

THIS FUNCTION IS OBSOLETE: use `rnfpolredbest`

instead.
Relative version of `polred`

. Given a monic polynomial *pol* with
coefficients in *nf*, finds a list of relative polynomials defining some
subfields, hopefully simpler and containing the original field. In the present
version **2.7.0**, this is slower and less efficient than `rnfpolredbest`

.

**Remark.** this function is based on an incomplete reduction
theory of lattices over number fields, implemented by `rnflllgram`

, which
deserves to be improved.

The library syntax is `GEN `

.**rnfpolred**(GEN nf, GEN pol, long prec)

THIS FUNCTION IS OBSOLETE: use `rnfpolredbest`

instead.
Relative version of `polredabs`

. Given a monic polynomial *pol*
with coefficients in *nf*, finds a simpler relative polynomial defining
the same field. The binary digits of *flag* mean

The binary digits of *flag* correspond to 1: add information to convert
elements to the new representation, 2: absolute polynomial, instead of
relative, 16: possibly use a suborder of the maximal order. More precisely:

0: default, return P

1: returns [P,a] where P is the default output and a,
a `t_POLMOD`

modulo P, is a root of *pol*.

2: returns *Pabs*, an absolute, instead of a relative, polynomial.
Same as but faster than

rnfequation(nf, rnfpolredabs(nf,pol))

3: returns [*Pabs*,a,b], where *Pabs* is an absolute polynomial
as above, a, b are `t_POLMOD`

modulo *Pabs*, roots of `nf.pol`

and *pol* respectively.

16: possibly use a suborder of the maximal order. This is slower than the
default when the relative discriminant is smooth, and much faster otherwise.
See Section [**Label: se:polredabs**].

**Warning.** In the present implementation, `rnfpolredabs`

produces smaller polynomials than `rnfpolred`

and is usually
faster, but its complexity is still exponential in the absolute degree.
The function `rnfpolredbest`

runs in polynomial time, and tends to
return polynomials with smaller discriminants.

The library syntax is `GEN `

.**rnfpolredabs**(GEN nf, GEN pol, long flag)

Relative version of `polredbest`

. Given a monic polynomial *pol*
with coefficients in *nf*, finds a simpler relative polynomial P
defining the same field. As opposed to `rnfpolredabs`

this function does
not return a *smallest* (canonical) polynomial with respect to some
measure, but it does run in polynomial time.

The binary digits of *flag* correspond to 1: add information to convert
elements to the new representation, 2: absolute polynomial, instead of
relative. More precisely:

0: default, return P

1: returns [P,a] where P is the default output and a,
a `t_POLMOD`

modulo P, is a root of *pol*.

2: returns *Pabs*, an absolute, instead of a relative, polynomial.
Same as but faster than

rnfequation(nf, rnfpolredbest(nf,pol))

3: returns [*Pabs*,a,b], where *Pabs* is an absolute polynomial
as above, a, b are `t_POLMOD`

modulo *Pabs*, roots of `nf.pol`

and *pol* respectively.

? K = nfinit(y^3-2); pol = x^2 +x*y + y^2; ? [P, a] = rnfpolredbest(K,pol,1); ? P %3 = x^2 - x + Mod(y - 1, y^3 - 2) ? a %4 = Mod(Mod(2*y^2+3*y+4,y^3-2)*x + Mod(-y^2-2*y-2,y^3-2), x^2 - x + Mod(y-1,y^3-2)) ? subst(K.pol,y,a) %5 = 0 ? [Pabs, a, b] = rnfpolredbest(K,pol,3); ? Pabs %7 = x^6 - 3*x^5 + 5*x^3 - 3*x + 1 ? a %8 = Mod(-x^2+x+1, x^6-3*x^5+5*x^3-3*x+1) ? b %9 = Mod(2*x^5-5*x^4-3*x^3+10*x^2+5*x-5, x^6-3*x^5+5*x^3-3*x+1) ? subst(K.pol,y,a) %10 = 0 ? substvec(pol,[x,y],[a,b]) %11 = 0

The library syntax is `GEN `

.**rnfpolredbest**(GEN nf, GEN pol, long flag)

Given a number field
*nf* as output by `nfinit`

and a polynomial *pol* with
coefficients in *nf* defining a relative extension L of *nf*,
computes a pseudo-basis (A,I) for the maximal order **Z**_L viewed as a
**Z**_K-module, and the relative discriminant of L. This is output as a
four-element row vector [A,I,D,d], where D is the relative ideal
discriminant and d is the relative discriminant considered as an element of
*nf*^*/{*nf*^*}^2.

The library syntax is `GEN `

.**rnfpseudobasis**(GEN nf, GEN pol)

Given a number field *nf* as
output by `nfinit`

and either a polynomial x with coefficients in
*nf* defining a relative extension L of *nf*, or a pseudo-basis
x of such an extension as output for example by `rnfpseudobasis`

,
computes another pseudo-basis (A,I) (not in HNF in general) such that all
the ideals of I except perhaps the last one are equal to the ring of
integers of *nf*, and outputs the four-component row vector [A,I,D,d]
as in `rnfpseudobasis`

. The name of this function comes from the fact
that the ideal class of the last ideal of I, which is well defined, is the
Steinitz class of the **Z**_K-module **Z**_L (its image in SK_0(**Z**_K)).

The library syntax is `GEN `

.**rnfsteinitz**(GEN nf, GEN x)

*bnr* being as output by `bnrinit`

or a list of cyclic components
of a finite Abelian group G, outputs the list of subgroups of G. Subgroups
are given as HNF left divisors of the SNF matrix corresponding to G.

If *flag* = 0 (default) and *bnr* is as output by `bnrinit`

, gives
only the subgroups whose modulus is the conductor. Otherwise, the modulus is
not taken into account.

If *bound* is present, and is a positive integer, restrict the output to
subgroups of index less than *bound*. If *bound* is a vector
containing a single positive integer B, then only subgroups of index
exactly equal to B are computed. For instance

? subgrouplist([6,2]) %1 = [[6, 0; 0, 2], [2, 0; 0, 2], [6, 3; 0, 1], [2, 1; 0, 1], [3, 0; 0, 2], [1, 0; 0, 2], [6, 0; 0, 1], [2, 0; 0, 1], [3, 0; 0, 1], [1, 0; 0, 1]] ? subgrouplist([6,2],3) \\ index less than 3 %2 = [[2, 1; 0, 1], [1, 0; 0, 2], [2, 0; 0, 1], [3, 0; 0, 1], [1, 0; 0, 1]] ? subgrouplist([6,2],[3]) \\ index 3 %3 = [[3, 0; 0, 1]] ? bnr = bnrinit(bnfinit(x), [120,[1]], 1); ? L = subgrouplist(bnr, [8]);

In the last example, L corresponds to the 24 subfields of
**Q**(zeta_{120}), of degree 8 and conductor 120 oo (by setting *flag*,
we see there are a total of 43 subgroups of degree 8).

? vector(#L, i, galoissubcyclo(bnr, L[i]))

will produce their equations. (For a general base field, you would
have to rely on `bnrstark`

, or `rnfkummer`

.)

The library syntax is `GEN `

.**subgrouplist0**(GEN bnr, GEN bound = NULL, long flag)

*znf* being a number
field initialized by `zetakinit`

(*not* by `nfinit`

),
computes the value of the Dedekind zeta function of the number
field at the complex number x. If *flag* = 1 computes Dedekind Lambda
function instead (i.e. the product of the Dedekind zeta function by its gamma
and exponential factors).

**CAVEAT.** This implementation is not satisfactory and must be
rewritten. In particular

***** The accuracy of the result depends in an essential way on the
accuracy of both the `zetakinit`

program and the current accuracy.
Be wary in particular that x of large imaginary part or, on the
contrary, very close to an ordinary integer will suffer from precision
loss, yielding fewer significant digits than expected. Computing with 28
digits of relative accuracy, we have

? zeta(3) %1 = 1.202056903159594285399738161 ? zeta(3-1e-20) %2 = 1.202056903159594285401719424 ? zetak(zetakinit(x), 3-1e-20) %3 = 1.2020569031595952919 \\ 5 digits are wrong ? zetak(zetakinit(x), 3-1e-28) %4 = -25.33411749 \\ junk

***** As the precision increases, results become unexpectedly
completely wrong:

? \p100 ? zetak(zetakinit(x^2-5), -1) - 1/30 %1 = 7.26691813 E-108 \\ perfect ? \p150 ? zetak(zetakinit(x^2-5), -1) - 1/30 %2 = -2.486113578 E-156 \\ perfect ? \p200 ? zetak(zetakinit(x^2-5), -1) - 1/30 %3 = 4.47... E-75 \\ more than half of the digits are wrong ? \p250 ? zetak(zetakinit(x^2-5), -1) - 1/30 %4 = 1.6 E43 \\ junk

The library syntax is `GEN `

.
See also **gzetakall**(GEN nfz, GEN x, long flag, long prec)`GEN `

or
**glambdak**(GEN znf, GEN x, long prec)`GEN `

.**gzetak**(GEN znf, GEN x, long prec)

Computes a number of initialization data
concerning the number field associated to `bnf`

so as to be able
to compute the Dedekind zeta and lambda functions, respectively
`zetak`

(x) and `zetak`

(x,1), at the current real precision. If
you do not need the `bnfinit`

data somewhere else, you may call it
with an irreducible polynomial instead of a *bnf*: it will call
`bnfinit`

itself.

The result is a 9-component vector v whose components are very technical
and cannot really be used except through the `zetak`

function.

This function is very inefficient and should be rewritten. It needs to
computes millions of coefficients of the corresponding Dirichlet series if
the precision is big. Unless the discriminant is small it will not be able
to handle more than 9 digits of relative precision. For instance,
`zetakinit(x^8 - 2)`

needs 440MB of memory at default precision.

This function will fail with the message

*** bnrL1: overflow in zeta_get_N0 [need too many primes].if the approximate functional equation requires us to sum too many terms (if the discriminant of the number field is too large).

The library syntax is `GEN `

.**initzeta**(GEN bnf, long prec)