Pari/GP Reference Documentation | Contents - Global index - GP keyboard shortcuts |
Algebraic numbers and ideals Class field theory Class group, units, and the GRH Finite abelian groups General use Number field structures Relative extensions bnfcertify bnfcompress bnfdecodemodule bnfinit bnfisintnorm bnfisnorm bnfisprincipal bnfissunit bnfisunit bnflog bnflogdegree bnflogef bnfnarrow bnfsignunit bnfsunit bnrL1 bnrchar bnrclassno bnrclassnolist bnrconductor bnrconductorofchar bnrdisc bnrdisclist bnrgaloisapply bnrgaloismatrix bnrinit bnrisconductor bnrisgalois bnrisprincipal bnrrootnumber bnrstark dirzetak factornf galoisexport galoisfixedfield galoisgetpol galoisidentify galoisinit galoisisabelian galoisisnormal galoispermtopol galoissubcyclo galoissubfields galoissubgroups idealadd idealaddtoone idealappr idealchinese idealcoprime idealdiv idealfactor idealfactorback idealfrobenius idealhnf idealintersect idealinv ideallist ideallistarch ideallog idealmin idealmul idealnorm idealnumden idealpow idealprimedec idealprincipalunits idealramgroups idealred idealstar idealtwoelt idealval matalgtobasis matbasistoalg modreverse newtonpoly nfalgtobasis nfbasis nfbasistoalg nfcertify nfcompositum nfdetint nfdisc nfeltadd nfeltdiv nfeltdiveuc nfeltdivmodpr nfeltdivrem nfeltmod nfeltmul nfeltmulmodpr nfeltnorm nfeltpow nfeltpowmodpr nfeltreduce nfeltreducemodpr nfeltsign nfelttrace nfeltval nffactor nffactorback nffactormod nfgaloisapply nfgaloisconj nfgrunwaldwang nfhilbert nfhnf nfhnfmod nfinit nfisideal nfisincl nfisisom nfislocalpower nfkermodpr nfmodpr nfmodprinit nfmodprlift nfnewprec nfroots nfrootsof1 nfsnf nfsolvemodpr nfsplitting nfsubfields polcompositum polgalois polred polredabs polredbest polredord poltschirnhaus rnfalgtobasis rnfbasis rnfbasistoalg rnfcharpoly rnfconductor rnfdedekind rnfdet rnfdisc rnfeltabstorel rnfeltdown rnfeltnorm rnfeltreltoabs rnfelttrace rnfeltup rnfequation rnfhnfbasis rnfidealabstorel rnfidealdown rnfidealfactor rnfidealhnf rnfidealmul rnfidealnormabs rnfidealnormrel rnfidealprimedec rnfidealreltoabs rnfidealtwoelt rnfidealup rnfinit rnfisabelian rnfisfree rnfislocalcyclo rnfisnorm rnfisnorminit rnfkummer rnflllgram rnfnormgroup rnfpolred rnfpolredabs rnfpolredbest rnfpseudobasis rnfsteinitz subgrouplist | |
In this section, we describe functions related to general number fields. Functions related to quadratic number fields are found in Section se:arithmetic (Arithmetic functions).
| |
Number field structures | |
Let K = ℚ[X] / (T) a number field, ℤ_K its ring of integers, T ∈ ℤ[X] is monic. Three basic number field structures can be attached to K in GP:
* nf denotes a number field, i.e. a data structure output by
* bnf denotes a "Buchmann's number field", i.e. a
data structure output by
* bnr denotes a "ray number field", i.e. a data structure
output by
| |
Algebraic numbers and ideals | |
An algebraic number belonging to K = ℚ[X]/(T) is given as
* a
* a
* a 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
* a
One may use
* 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
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
| |
Finite abelian groups | |
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 = ⨁ _{i ≤ n} (ℤ/d_iℤ) g_i, with d_n | ... | d_2 | d_1
and ∏ d_i = h. This information can also be retrieved as
G. * a character on the abelian group ⨁ (ℤ/d_jℤ) g_j is given by a row vector χ = [a_1,...,a_n] such that χ(∏ g_j^{n_j}) = exp(2π i∑ a_j n_j / d_j). * 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).
| |
Relative extensions | |
We now have a look at data structures attached to relative extensions of number fields L/K, and to projective ℤ_K-modules. When defining a relative extension L/K, the nf attached to the base field K must be defined by a variable having a lower priority (see Section 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.
| |
Class field theory | |
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 attached to the i-th real root of
A bid or "big ideal" is a structure output by 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], [bnr,character], [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 * mod is a modulus 𝔣, as described above.
* subgroup a subgroup of the ray class group modulo 𝔣 of
K. As described above, this is input as a square matrix expressing
generators of a subgroup of the ray class group The corresponding bnr is the subfield of the ray class field of K modulo 𝔣, 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 ? bnrconductor(bnr, [3,1]); \\ conductor of chi: g1->zeta_12^3, g2->zeta_3 We could have written directly
? bnrdisc(K, 13); ? bnrdisc(K, 13, [3,1;0,1]);
avoiding one
| |
General use | |
All the functions which are specific to relative extensions, number fields,
Buchmann's number fields, Buchmann's number rays, share the prefix
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 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: Deprecated. The following member functions are still available, but deprecated and should not be used in new scripts : w generates the torsion units. w generates the torsion units.
For instance, assume that bnf =
| |
Class group, units, and the GRH | |
Some of the functions starting with
P is the defining polynomial for the number field, which must be in
ℤ[X], irreducible and monic. In fact, if you supply a non-monic polynomial
at this point, 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
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 nrpid is the maximal number of small norm relations attached 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 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 Note also that you can use an nf instead of P, which avoids recomputing the integral basis and analogous quantities.
| |
bnfcertify | |
bnf being as output by
? 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
| |
bnfcompress | |
Computes a compressed version of bnf (from
An sbnf is a 12 component vector v, as follows. Let All the components are exact (integral or rational), except for the roots in v[5].
The library syntax is
| |
bnfdecodemodule | |
If m is a module as output in the
first component of an extension given by
? 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
| |
bnfinit | |
Initializes a
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, 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 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 (𝔭_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 𝔭_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
bnf[8] is a vector containing the classgroup
bnf[9] is a 3-element row vector used in
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
The library syntax is
Also available is
| |
bnfisintnorm | |
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
The library syntax is
| |
bnfisnorm | |
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
The library syntax is
| |
bnfisprincipal | |
bnf being the
number field data output by 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 the
The library syntax is
| |
bnfissunit | |
bnf being output by
The library syntax is
| |
bnfisunit | |
bnf being the number field data
output by 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 bnf. In this case, the fundamental unit was not computed and stored in algebraic form since the default accuracy was too low. (Re-run the command at \g1 or higher to see such diagnostics.)
The library syntax is
| |
bnflog | |
Let bnf be attached to a number field F and let l be a prime number (hereafter denoted ℓ for typographical reasons). Return the logarithmic ℓ-class group ~{Cl}_F of F. This is an abelian group, conjecturally finite (known to be finite if F/ℚ is abelian). The function returns if and only if the group is indeed finite (otherwise it would run into an infinite loop). Let S = { 𝔭_1,..., 𝔭_k} be the set of ℓ-adic places (maximal ideals containing ℓ). The function returns [D, G(ℓ), G'], where * D is the vector of elementary divisors for ~{Cl}_F; * G(ℓ) is the vector of elementary divisors for the (conjecturally finite) abelian group ~{Cl}(ℓ) = { 𝔞 = ∑_{i ≤ k} a_i 𝔭_i : deg_F 𝔞 = 0}, where the 𝔭_i are the ℓ-adic places of F; this is a subgroup of ~{Cl}. * G' is the vector of elementary divisors for the ℓ-Sylow Cl' of the S-class group of F; the group ~{Cl} maps to Cl' with a simple co-kernel.
The library syntax is
| |
bnflogdegree | |
Let nf be the number field data output by
The degree map deg_F is additive with values in ℤ_ℓ,
defined by deg_F 𝔭 = ~{f}_{𝔭} deg_ℓ p,
where the integer ~{f} is as in Let A = ∏ 𝔭^{n_{𝔭}} be an ideal and let ~{A} = ∑ n_𝔭 [𝔭] be the attached logarithmic divisor. Return the exponential of the ℓ-adic logarithmic degree deg_F A, which is a natural number.
The library syntax is
| |
bnflogef | |
Let F be a number field represented by the nf structure,
and let pr be a
? F = nfinit(y^6 - 3*y^5 + 5*y^3 - 3*y + 1); ? bnflogef(F, idealprimedec(F,2)[1]) %2 = [6, 1] ? bnflogef(F, idealprimedec(F,5)[1]) %3 = [1, 2]
The library syntax is
| |
bnfnarrow | |
bnf being as output by
The library syntax is
| |
bnfsignunit | |
bnf being as output by
/* exponents of totally positive units generators on bnf.tufu */ tpuexpo(bnf)= { my(K, S = bnfsignunit(bnf), [m,n] = matsize(S)); \\ m = bnf.r1, n = r1+r2-1 S = matrix(m,n, i,j, if (S[i,j] < 0, 1,0)); S = concat(vectorv(m,i,1), S); \\ add sign(-1) K = matker(S * Mod(1,2)); if (K, mathnfmodid(lift(K), 2), 2*matid(n+1)) } /* totally positive fundamental units */ tpu(bnf)= { my(ex = tpuexpo(bnf)[,2..-1]); \\ remove ex[,1], corresponds to 1 or -1 vector(#ex, i, nffactorback(bnf, bnf.tufu, ex[,i])); }
The library syntax is
| |
bnfsunit | |
Computes the fundamental S-units of the
number field bnf (output by 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 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
| |
bnrL1 | |
Let bnr be the number field data output by 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 attached to χ 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, χ), 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); bnrL1(bnr) returns the order and the first non-zero term of L(s, χ) at s = 0 where χ runs through the characters of the class group of K = ℚ(sqrt{229}). Then
bnr2 = bnrinit(K,2); bnrL1(bnr2,,2)
returns the order and the first non-zero terms of L_S(s, χ) at s = 0
where χ 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
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
| |
bnrchar | |
Returns all characters χ on
? bnr = bnrinit(bnfinit(x), [160,[1]], 1); /* (Z/160Z)^* */ ? bnr.cyc %2 = [8, 4, 2] ? g = bnr.gen; ? bnrchar(bnr, g, [1/2,0,0]) %4 = [[4, 0, 0]] \\ a unique character ? bnrchar(bnr, [g[1],g[3]]) \\ all characters trivial on g[1] and g[3] %5 = [[0, 1, 0], [0, 2, 0], [0, 3, 0], [0, 0, 0]] ? bnrchar(bnr, [1,0,0;0,1,0;0,0,2]) %6 = [[0, 0, 1], [0, 0, 0]] \\ characters trivial on given subgroup
The library syntax is
| |
bnrclassno | |
Let A, B, C define a class field L over a ground field K
(of type 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 attached 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
The library syntax is
| |
bnrclassnolist | |
bnf being as
output by
? 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
? bnrclassno(bnf, ids[2]) %6 = 3
The library syntax is
| |
bnrconductor | |
Conductor f of the subfield of a ray class field as defined by [A,B,C]
(of type 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
In place of a subgroup H, this function also accepts a character
If flag = 0, the conductor f of Ker χ. If flag = 1, [f, Cl_f, χ_f], where χ_f is χ expressed on the minimal ray class group, whose modulus is the conductor. If flag = 2, [f, bnr(f), χ_f].
The library syntax is
Also available is
| |
bnrconductorofchar | |
This function is obsolete, use bnrconductor.
The library syntax is
| |
bnrdisc | |
A, B, C defining a class field L over a ground field K
(of type * 1: if this bit is unset, output absolute data related to L/ℚ: N is the absolute degree [L:ℚ], r_1 the number of real places of L, and D the discriminant of L/ℚ. 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
| |
bnrdisclist | |
bnf being as output by
The alternative syntax The output v is a vector, where 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 attached 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:ℚ] 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,α,e,f,β] 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
m can be decoded using
Note that to compute such data for a single field, either
The library syntax is
| |
bnrgaloisapply | |
Apply the automorphism given by its matrix mat to the congruence
subgroup H given as a HNF matrix.
The matrix mat can be computed with
The library syntax is
| |
bnrgaloismatrix | |
Return the matrix of the action of the automorphism aut of the base
field
See
The library syntax is
| |
bnrinit | |
bnf is as
output by
The following member functions are available
on the result:
The last group of functions are different from the members of the underlying
bnf, which refer to the class group; use
They are also different from the members of the underlying bid, which
refer to (ℤ_K/f)^*; use
If flag = 0 (default), the generators of the ray class group are not computed,
which saves time. Hence If flag = 1, as the default, except that generators are computed.
The library syntax is
| |
bnrisconductor | |
Fast variant of
The library syntax is
| |
bnrisgalois | |
Check whether the class field attached to the subgroup H is Galois
over the subfield of In the following example, we lists the congruence subgroups of subextension of degree at most 3 of the ray class field of conductor 9 which are Galois over the rationals.
K=bnfinit(a^4-3*a^2+253009); G=galoisinit(K); B=bnrinit(K,9,1); L1=[H|H<-subgrouplist(B,3), bnrisgalois(B,G,H)] ## M=bnrgaloismatrix(B,G) L2=[H|H<-subgrouplist(B,3), bnrisgalois(B,M,H)] ##
The second computation is much faster since
The library syntax is
| |
bnrisprincipal | |
Let bnr be the ray class group data output by
If flag = 1, returns a 2-component vector v where v[1] is the vector of components of x on the ray class group generators, v[2] is an element α congruent to 1 mod^* f such that x = α ∏_i g_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
? K = bnfinit(x^2 - 30); bnr = bnrinit(K, [4, [1,1]]); ? bnr.clgp \\ ray class group is isomorphic to Z/4 x Z/2 x Z/2 %2 = [16, [4, 2, 2]] ? P = idealprimedec(K, 3)[1]; \\ a prime ideal above 3 ? bnrisprincipal(bnr,P) %4 = [[1, 0, 0]~, 1] ? bnrisprincipal(bnr,P, 0) \\ omit the principal part %4 = [1, 0, 0]~
The library syntax is
bnrisprincipal(bnr, x, nf_GEN)
| |
bnrrootnumber | |
If χ = chi is a character over bnr, not necessarily primitive, let L(s,χ) = ∑_{id} χ(id) N(id)^{-s} be the attached Artin L-function. Returns the so-called Artin root number, i.e. the complex number W(χ) of modulus 1 such that Λ(1-s,χ) = W(χ) Λ(s,χ) where Λ(s,χ) = A(χ)^{s/2}γ_χ(s) L(s,χ) is the enlarged L-function attached to L. 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]]); bnrrootnumber(bnr, [2,1])
returns the root number of the character χ of
Cl_{7 oo _1 oo _2}(ℚ(sqrt{229})) defined by χ(g_1^ag_2^b)
= ζ_1^{2a}ζ_2^b. Here g_1, g_2 are the generators of the
ray-class group given by
The library syntax is
| |
bnrstark | |
bnr being as output by
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 ℚ, the vastly
simpler
bnf = bnfinit(y^2 - 3); bnr = bnrinit(bnf, 5); bnrstark(bnr) returns the ray class field of ℚ(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
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
? bnr = bnrinit(bnfinit(y^8-12*y^6+36*y^4-36*y^2+9,1), 2); ? 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
| |
dirzetak | |
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
| |
factornf | |
This function is obsolete, use
factorization of the univariate polynomial x
over the number field defined by the (univariate) polynomial t. x may
have coefficients in ℚ or in the number field. The algorithm reduces to
factorization over ℚ (Trager's trick). The direct approach of
The main variable of t must be of lower priority than that of x (see Section 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
| |
galoisexport | |
gal being be a Galois group as output by
? 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
To import a GAP permutation into gp (for
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
| |
galoisfixedfield | |
gal being be a Galois group as output by
If no flags or flag = 0, output format is the same as for 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 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
| |
galoisgetpol | |
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] = 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
| |
galoisidentify | |
gal being be a Galois group as output by
This command also accepts subgroups returned by 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
The library syntax is
| |
galoisinit | |
Computes the Galois group
and all necessary information for computing the fixed fields of the
Galois extension K/ℚ where K is the number field defined by
pol (monic irreducible polynomial in ℤ[X] or
a number field as output by 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 ◃ H_1 ◃ ... ◃ H_{n-1} ◃ 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 ≥ 108.
This function is a prerequisite for most of the
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[2] is a three-components vector [p,e,q] where p is a
prime number (
gal[3] is a vector L containing the p-adic roots of
pol as integers implicitly modulo 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[7] is a generating subset S = [s_1,...,s_g] of G
expressed as a vector of permutations of L (
gal[8] contains the relative orders [o_1,...,o_g] of
the generators of S ( 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/ * for any x ∈ 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
| |
galoisisabelian | |
gal being as output by
This command also accepts subgroups returned by
The library syntax is
| |
galoisisnormal | |
gal being as output by
This command also accepts subgroups returned by
The library syntax is
| |
galoispermtopol | |
gal being a
Galois group as output by Note that
G = galoisinit(pol); galoispermtopol(G, G[6])~
is equivalent to
The library syntax is
| |
galoissubcyclo | |
Computes the subextension of ℚ(ζ_n) fixed by the subgroup H ⊂ (ℤ/nℤ)^*. 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
* N the output of 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 (ℤ/nℤ)^*, but of its quotient by {± 1}. If fl = 0, compute a polynomial (in the variable v) defining the subfield of ℚ(ζ_n) fixed by the subgroup H of (ℤ/nℤ)^*. 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
ℚ(ζ_n) (of exact degree
subcyclo(n, d = -1)= { my(bnr,L,IndexBound); IndexBound = if (d < 0, n, [d]); bnr = bnrinit(bnfinit(y), [n,[1]]); L = subgrouplist(bnr, IndexBound, 1); vector(#L,i, galoissubcyclo(bnr,L[i])); }
Setting
The library syntax is
| |
galoissubfields | |
Outputs all the subfields of the Galois group G, as a vector.
This works by applying
The library syntax is
| |
galoissubgroups | |
Outputs all the subgroups of the Galois group To get the subfield fixed by a subgroup sub of gal, use
galoisfixedfield(gal,sub[1])
The library syntax is
| |
idealadd | |
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 ℤ-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 ℤ-span of their
columns (as usual interpreted as coordinates with respect to the integer basis
The library syntax is
| |
idealaddtoone | |
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 ∈ x, b ∈ y and a+b = 1.
The alternative syntax
The library syntax is
| |
idealappr | |
If x is a fractional ideal (given in any form), gives an element α in nf such that for all prime ideals 𝔭 such that the valuation of x at 𝔭 is non-zero, we have v_{𝔭}(α) = v_{𝔭}(x), and v_{𝔭}(α) ≥ 0 for all other 𝔭.
The argument x may also be given as a prime ideal factorization, as
output by flag is deprecated (ignored), kept for backward compatibility
The library syntax is
| |
idealchinese | |
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_{𝔭}(b - y_{𝔭}) ≥ v_{𝔭}(x) for all prime ideals in x and v_{𝔭}(b) ≥ 0 for all other 𝔭.
? K = nfinit(t^2-2); ? x = idealfactor(K, 2^2*3) %2 = [[2, [0, 1]~, 2, 1, [0, 2; 1, 0]] 4] [ [3, [3, 0]~, 1, 2, 1] 1] ? y = [t,1]; ? idealchinese(K, x, y) %4 = [4, -3]~
The argument x may also be of the form [x, s] where the first component
is as above and s is a vector of signs, with r_1 components
s_i in {-1,0,1}:
if σ_i denotes the i-th real embedding of the number field,
the element b returned satisfies further
s_i
? idealchinese(K, [x, [1,1]], y) %5 = [16, -3]~ ? idealchinese(K, [x, [-1,-1]], y) %6 = [-20, -3]~ ? idealchinese(K, [x, [1,-1]], y) %7 = [4, -3]~ If y is omitted, return a data structure which can be used in place of x in later calls and allows to solve many chinese remainder problems for a given x more efficiently.
? C = idealchinese(K, [x, [1,1]]); ? idealchinese(K, C, y) \\ as above %9 = [16, -3]~ ? for(i=1,10^4, idealchinese(K,C,y)) \\ ... but faster ! time = 80 ms. ? for(i=1,10^4, idealchinese(K,[x,[1,1]],y)) time = 224 ms. Finally, this structure is itself allowed in place of x, the new s overriding the one already present in the structure. This allows to initialize for different sign conditions more efficiently when the underlying ideal factorization remains the same.
? D = idealchinese(K, [C, [1,-1]]); \\ replaces [1,1] ? idealchinese(K, D, y) %13 = [4, -3]~ ? for(i=1,10^4,idealchinese(K,[C,[1,-1]])) time = 40 ms. \\ faster than starting from scratch ? for(i=1,10^4,idealchinese(K,[x,[1,-1]])) time = 128 ms.
The library syntax is
| |
idealcoprime | |
Given two integral ideals x and y in the number field nf, returns a β in the field, such that β.x is an integral ideal coprime to y.
The library syntax is
| |
idealdiv | |
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
| |
idealfactor | |
Factors into prime ideal powers the
ideal x in the number field nf. The output format is similar to the
The library syntax is
| |
idealfactorback | |
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
? 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
? 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
The library syntax is
| |
idealfrobenius | |
Let K be the number field defined by nf and assume K/ℚ be a
Galois extension with Galois group given
? nf = nfinit(polcyclo(31)); ? gal = galoisinit(nf); ? pr = idealprimedec(nf,101)[1]; ? g = idealfrobenius(nf,gal,pr); ? galoispermtopol(gal,g) %5 = x^8 This is correct since 101 = 8 mod 31.
The library syntax is
| |
idealhnf | |
Gives the Hermite normal form of the ideal uℤ_K+vℤ_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
* if strictly less than N = [K:ℚ] generators are given, u is the ℤ_K-module they generate,
* if N or more are given, it is assumed that they form a
ℤ-basis of the ideal, in particular that the matrix has maximal rank N.
This acts as
? 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 =
? 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
| |
idealintersect | |
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 ℤ-modules, e.g. orders, since its arguments are replaced by the ideals they generate. The following script intersects ℤ-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
| |
idealinv | |
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
| |
ideallist | |
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 attached 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 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 in ℤ[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 (ℤ[i]/I)^* for all
three ideals of norm 25. In fact, for all moduli with finite part of norm
25 and trivial Archimedean part, as the last 3 commands show. See
The library syntax is
| |
ideallistarch | |
list is a vector of vectors of bid's, as output by
? 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 ℤ/2ℤ to (ℤ_K/f)^*. 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]; %4 = [2, 12, 2]
The library syntax is
| |
ideallog | |
nf is a number field,
bid is as output by
When nf is omitted, take it to be the rational number field. In that
case, x must be a
The library syntax is
| |
idealmin | |
This function is useless and kept for backward compatibility only,
use
The library syntax is
| |
idealmul | |
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 %3 = [[4, 2; 0, 2], x] ? idealmul(nf, [2, x], [x+1, x]) \\ two extended ideals %4 = [[4, 2; 0, 2], [-1, 0]~]
If flag is non-zero, reduce the result using
The library syntax is
See also
| |
idealnorm | |
Computes the norm of the ideal x in the number field nf.
The library syntax is
| |
idealnumden | |
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
| |
idealpow | |
Computes the k-th power of the ideal x in the number field nf; k ∈ ℤ. 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
The library syntax is
See also
| |
idealprimedec | |
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. If f is present and non-zero, restrict the result to primes of residue degree ≤ f.
The result is a vector of prid structures, each representing one of the
prime ideals above p in the number field nf. The representation
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
? K = nfinit(x^3-2); ? P = idealprimedec(K, 5); ? #P \\ 2 primes above 5 in Q(2^(1/3)) %3 = 2 ? [p1,p2] = P; ? [p1.e, p1.f] \\ the first is unramified of degree 1 %5 = [1, 1] ? [p2.e, p2.f] \\ the second is unramified of degree 2 %6 = [1, 2] ? p1.gen %7 = [5, [2, 1, 0]~] ? nfbasistoalg(K, %[2]) \\ a uniformizer for p1 %8 = Mod(x + 2, x^3 - 2) ? #idealprimedec(K, 5, 1) \\ restrict to f = 1 %9 = 1 \\ now only p1
The library syntax is
| |
idealprincipalunits | |
Given a prime ideal in
? K = nfinit(y^2+1); ? P = idealprimedec(K,2)[1]; ? G = idealprincipalunits(K, P, 20); ? G.cyc %4 = [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
| |
idealramgroups | |
Let K be the number field defined by nf and assume that K/ℚ is
Galois with Galois group G given by
*
* and for i ≥ 2,
* 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) %3 = [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] %5 = [[Vecsmall([2, 3, 1, 5, 6, 4])], Vecsmall([3])] ? nfdisc(galoisfixedfield(gal,iso,1)) %6 = -3 The field fixed by the inertia group of 2 is not ramified at 2.
The library syntax is
| |
idealred | |
LLL reduction of
the ideal I in the number field K attached to nf, along the
direction v. The v parameter is best left omitted, but if it is present,
it must be an This function finds an a ∈ K^* such that J = (a)I is "small" and integral (see the end for technical details). The result is the Hermite normal form of the "reduced" ideal J.
? 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 If the input is an extended ideal [I,s], the output is [J, sa]; in this way, one keeps 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
Technical note. The routine computes an LLL-reduced
basis for the lattice I^(-1) equipped with the quadratic
form
|| x ||_v^2 = ∑_{i = 1}^{r_1+r_2} 2^{v_i}ϵ_i|σ_i(x)|^2,
where as usual the σ_i are the (real and) complex embeddings and
ϵ_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 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^(-1) and that a I is "expected to be small".
The library syntax is
| |
idealstar | |
Outputs a
This bid is used in
If flag = 1 (default), the result is a If flag = 2, as flag = 1, but including generators. If flag = 0, only outputs (ℤ_K/N)^* 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.
If nf is omitted, we take it to be the rational number fields, N must
be an integer and we return the structure of (ℤ/Nℤ)^*. In other words
idealstar(nfinit(x), N, flag)
but much faster. The alternative syntax
The library syntax is
| |
idealtwoelt | |
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
* When called as
The library syntax is
| |
idealval | |
Gives the valuation of the ideal x at the prime ideal pr in the
number field nf, where pr is in
The library syntax is
| |
matalgtobasis | |
This function is deprecated, use
nf being a number field in
The library syntax is
| |
matbasistoalg | |
This function is deprecated, use
nf being a number field in
The library syntax is
| |
modreverse | |
Let z = 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 ℚ(u) = ℚ[x]/(x^3 - x - 1) = ℚ[x]/(x^3 - 5x^2 + 4x - 1) = ℚ(v), and that u → v^2 - 4v + 1 gives an explicit isomorphism. From this, it is easy to convert elements between the A(u) ∈ ℚ(u) and B(v) ∈ ℚ(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
| |
newtonpoly | |
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
The library syntax is
| |
nfalgtobasis | |
Given an algebraic number x in the number field nf,
transforms it to a column vector on the integral basis
? 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)) %5 = [0, 2]~
This is the inverse function of
The library syntax is
| |
nfbasis | |
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 ℤ-basis of its maximal order. The basis elements are given as elements in ℚ[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 it 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 distinct 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 ℤ-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
? K = nfinit([T, listP]); ? nfcertify(K) \\ we computed an actual maximal order %2 = [];
The first line initializes a number field structure
incorporating Of course, if listP contains a single prime number p, the function returns a local integral basis for ℤ_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
? 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
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.
The function
? B = 10^5; ? nf = nfinit([T, B]); ? nfcertify(nf) %3 = [] \\ nf is unconditionally correct ? basis = nf.zk; ? disc = nf.disc;
The library syntax is
| |
nfbasistoalg | |
Given an algebraic number x in the number field nf, transforms it
into
? 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)) %5 = Mod(y, y^2 + 4)
This is the inverse function of
The library syntax is
| |
nfcertify | |
nf being as output by
The function returns a vector of coprime composite integers. If this vector
is empty, then
The library syntax is
| |
nfcompositum | |
Let nf be a number field structure attached to the field K and let P and Q be squarefree polynomials in K[X] in the same variable. Outputs the simple factors of the étale K-algebra A = K[X, Y] / (P(X), Q(Y)). The factors are given by a list of polynomials R in K[X], attached to the number field K[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 linearly disjoint (their intersection is K). The binary digits of flag mean 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 K[X]/(R). Finally, k is a small integer such that b + ka = X modulo R. 2: assume that P and Q define number fields that are linearly disjoint: both polynomials are irreducible and the corresponding number fields have no common subfield besides K. This allows to save a costly factorization over K. In this case return the single simple factor instead of a vector with one element. 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 K(ζ_5, 5^{1/10}), K = ℚ(sqrt{5}):
? K = nfinit(y^2-5);
? L = nfcompositum(K, x^5 - y, polcyclo(5), 1); \\ list of [R,a,b,k]
? [R, a] = L[1]; \\ pick the single factor, extract R,a (ignore b,k)
? lift(R) \\ defines the compositum
%4 = x^10 + (-5/2*y + 5/2)*x^9 + (-5*y + 20)*x^8 + (-20*y + 30)*x^7 + \
(-45/2*y + 145/2)*x^6 + (-71/2*y + 121/2)*x^5 + (-20*y + 60)*x^4 + \
(-25*y + 5)*x^3 + 45*x^2 + (-5*y + 15)*x + (-2*y + 6)
? a^5 - y \\ a fifth root of y
%5 = 0
? [T, X] = rnfpolredbest(K, R, 1);
? lift(T) \\ simpler defining polynomial for K[x]/(R)
%7 = x^10 + (-11/2*y + 25/2)
? liftall(X) \\ root of R in K[x]/(T(x))
%8 = (3/4*y + 7/4)*x^7 + (-1/2*y - 1)*x^5 + 1/2*x^2 + (1/4*y - 1/4)
? a = subst(a.pol, 'x, X); \\
The main variables of P and Q must be the same and have higher priority
than that of nf (see
The library syntax is
| |
nfdetint | |
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
The library syntax is
| |
nfdisc | |
field discriminant of the number field defined by the integral, preferably monic, irreducible polynomial T(X). Returns the discriminant of the number field ℚ[X]/(T), using the Round 4 algorithm. Local discriminants, valuations at certain primes.
As in
In particular, if
? padicdisc(T,p) = p^valuation(nfdisc(T,[p]), p); ? nfdisc(x^2 + 6) %2 = -24 ? padicdisc(x^2 + 6, 2) %3 = 8 ? padicdisc(x^2 + 6, 3) %4 = 3
The library syntax is
| |
nfeltadd | |
Given two elements x and y in nf, computes their sum x+y in the number field nf.
The library syntax is
| |
nfeltdiv | |
Given two elements x and y in nf, computes their quotient x/y in the number field nf.
The library syntax is
| |
nfeltdiveuc | |
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
The library syntax is
| |
nfeltdivmodpr | |
This function is obsolete, use
Given two elements x
and y in nf and pr a prime ideal in
The library syntax is
| |
nfeltdivrem | |
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
| |
nfeltmod | |
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
The library syntax is
| |
nfeltmul | |
Given two elements x and y in nf, computes their product x*y in the number field nf.
The library syntax is
| |
nfeltmulmodpr | |
This function is obsolete, use
Given two elements x and
y in nf and pr a prime ideal in
The library syntax is
| |
nfeltnorm | |
Returns the absolute norm of x.
The library syntax is
| |
nfeltpow | |
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
| |
nfeltpowmodpr | |
This function is obsolete, use
Given an element x in nf, an integer k and a prime ideal
pr in
The library syntax is
| |
nfeltreduce | |
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
| |
nfeltreducemodpr | |
This function is obsolete, use
Given an element x of the number field nf and a prime ideal
pr in
The library syntax is
| |
nfeltsign | |
Given an element x in the number field nf, returns the signs of the real embeddings of x specified by optional argument pl: * pl omitted: return the vector of signs at all r_1 real places;
* pl an integer between 1 and r_1: return the sign of the
i-th embedding of x, attached to the i-th real root of
* pl a vector or
? nf = nfinit(polsubcyclo(11,5,'y)); \\ Q(cos(2 pi/5)) ? nf.sign %2 = [5, 0] ? x = Mod('y, nf.pol); ? nfeltsign(nf, x) %4 = [-1, -1, -1, 1, 1] ? nfeltsign(nf, x, 1) %5 = -1 ? nfeltsign(nf, x, [1..4]) %6 = [-1, -1, -1, 1] ? nfeltsign(nf, x, 6) \\ there are only 5 real embeddings *** at top-level: nfeltsign(nf,x,6) *** ^----------------- *** nfeltsign: domain error in nfeltsign: index > 5
The library syntax is
| |
nfelttrace | |
Returns the absolute trace of x.
The library syntax is
| |
nfeltval | |
Given an element x in
nf and a prime ideal pr in the format output by
? nf = nfinit(x^2 + 1); ? P = idealprimedec(nf, 2)[1]; ? nfeltval(nf, x+1, P) %3 = 1
This particular valuation can also be obtained using
If the y argument is present, sets y = x τ^v, where τ is a
fixed "anti-uniformizer" for pr: its valuation at pr is -1;
its valuation is 0 at other prime ideals dividing
? nfeltval(nf, x+1, P, &y); y %4 = [0, 1]~
For instance if x = ∏_i x_i^{e_i} is known to be coprime to pr,
where the x_i are algebraic integers and e_i ∈ ℤ then,
if v_i =
The library syntax is
| |
nffactor | |
Factorization of the univariate
polynomial T over the number field nf given by
The main variable of nf must be of lower
priority than that of T, see Section se:priority. However if
the polynomial defining the number field occurs explicitly in the
coefficients of T as modulus of a
? 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
Caveat.
The library syntax is
| |
nffactorback | |
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
| |
nffactormod | |
This routine is obsolete, use
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 se:priority). The prime ideal pr is either in
? 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) %5 = [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
| |
nfgaloisapply | |
Let nf be a
number field as output by
? 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] %6 = 0 \\ !!!! ? idealval(nf, nfgaloisapply(nf, aut, P[2]), P[1]) %7 = 1
The surprising failure of the equality test (
The automorphism can also be given as a column vector, representing the
image of
? nf = nfinit(x^3 - 37*x^2 + 74*x - 37); ? aut = nfgaloisconj(nf)[2]; \\ an automorphism in basistoalg form %2 = -31/11*x^2 + 1109/11*x - 925/11 ? AUT = nfalgtobasis(nf, aut); \\ 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 = 463 ms. ? for (i=1,10^5, nfgaloisapply(nf, AUT, v)) time = 343 ms. \\ but the latter is faster
The library syntax is
| |
nfgaloisconj | |
nf being a number field as output by 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
If flag = 4, use This routine can only compute ℚ-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,al,S, ala,k, vR); R *= Mod(1, nfK.pol); \\ convert coeffs to polmod elts of K vR = variable(R); al = Mod(variable(nfK.pol),nfK.pol); [polabs,ala,k] = rnfequation(nfK, R, 1); Rt = if(k==0,R,subst(R,vR,vR-al*k)); N = nfgaloisconj(polabs) % Rt; \\ Q-automorphisms of L S = select(s->subst(Rt, vR, Mod(s,Rt)) == 0, N); if (k==0, S, apply(s->subst(s,vR,vR+k*al)-k*al,S)); } 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
| |
nfgrunwaldwang | |
Given nf a number field in nf or bnf format,
a
* at the prime * at the i-th real place of nf, it is complex if pl[i] = -1 (no condition if pl[i] = 0).
The extension has degree the LCM of the local degrees. Currently, the degree
is restricted to be a prime power for the search, and to be prime for the
construction because of the
When nf is ℚ, prime integers are accepted instead of Warning. If the number field nf does not contain the n-th roots of unity where n is the degree of the extension to be computed, triggers the computation of the bnf of nf(ζ_n), which may be costly.
? nf = nfinit(y^2-5); ? pr = idealprimedec(nf,13)[1]; ? pol = nfgrunwaldwang(nf, [pr], [2], [0,-1], 'x) %3 = x^2 + Mod(3/2*y + 13/2, y^2 - 5)
The library syntax is
| |
nfhilbert | |
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
The library syntax is
Also available is
| |
nfhnf | |
Given a pseudo-matrix (A,I), finds a pseudo-basis (B,J) in Hermite normal form of the module it generates. If flag is non-zero, also return the transformation matrix U such that AU = [0|B].
The library syntax is
| |
nfhnfmod | |
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
The library syntax is
| |
nfinit | |
pol being a non-constant,
preferably monic, irreducible polynomial in ℤ[X], initializes a
number field structure (
nf[1] contains the polynomial pol (
nf[2] contains [r1,r2] (
nf[3] contains the discriminant d(K) (
nf[4] contains the index 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) = ∑ |σ(x)|^2, σ running over the embeddings of K into ℂ. * roundG is a rescaled copy of G, rounded to nearest integers. * T is the n x n matrix whose coefficients are Tr(ω_iω_j) where the ω_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 ( * 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
(
nf[6] is the vector containing the r1+r2 roots
(
nf[7] is an integral basis for ℤ_K ( 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,
? 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] \\ 𝔭_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
* an argument
? pol = polcompositum(x^5 - 101, polcyclo(7))[1]; ? nf = nfinit( [pol, 10^3] ); ? nfcertify(nf) %3 = []
A priori,
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
If flag = 3, apply
The library syntax is
*
*
*
*
| |
nfisideal | |
Returns 1 if x is an ideal in the number field nf, 0 otherwise.
The library syntax is
| |
nfisincl | |
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 ℚ[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
The library syntax is
| |
nfisisom | |
As
The library syntax is
| |
nfislocalpower | |
Let nf be a number field structure attached to K, let a ∈ K and let pr be a prid attched to the maximal ideal v. Return 1 if a is an n-th power in the completed local field K_v, and 0 otherwise.
? K = nfinit(y^2+1); ? P = idealprimedec(K,2)[1]; \\ the ramified prime above 2 ? nfislocalpower(K,P,-1, 2) \\ -1 is a square %3 = 1 ? nfislocalpower(K,P,-1, 4) \\ ... but not a 4-th power %4 = 0 ? nfislocalpower(K,P,2, 2) \\ 2 is not a square %5 = 0 ? Q = idealprimedec(K,5)[1]; \\ a prime above 5 ? nfislocalpower(K,Q, [0, 32]~, 30) \\ 32*I is locally a 30-th power %7 = 1
The library syntax is
| |
nfkermodpr | |
This function is obsolete, use
Kernel of the matrix a in ℤ_K/pr, where pr is in
modpr format (see
The library syntax is
| |
nfmodpr | |
Map x to the residue field modulo pr, to a
Note that the function applies to number field elements and not to
vector / matrices / polynomials of such. Use
? K = nfinit(y^3-250); ? P = idealprimedec(K, 5)[2] ? modP = nfmodprinit(K,P); ? K.zk %4 = [1, 1/5*y, 1/25*y^2] ? apply(t->nfmodpr(K,t,modP), K.zk) %5 = [1, y, 2*y + 1]
The library syntax is
| |
nfmodprinit | |
Transforms the prime ideal pr into
The library syntax is
| |
nfmodprlift | |
Lift the
The argument
The function
? K = nfinit(y^3-250); ? P = idealprimedec(K, 5)[2] ? modP = nfmodprinit(K,P); ? K.zk %4 = [1, 1/5*y, 1/25*y^2] ? apply(t->nfmodpr(K,t,modP), K.zk) %5 = [1, y, 2*y + 1] ? nfmodprlift(K, %, modP) %6 = [1, 1/5*y, 2/5*y + 1] ? nfeltval(K, %[3] - K.zk[3], P) %7 = 1
The library syntax is
| |
nfnewprec | |
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 or a bnr (update structure to current precision) but may be quite slow: many generators of principal ideals have to be computed; note that in this latter case, the bnf must contain fundamental units.
The library syntax is
| |
nfroots | |
Roots of the polynomial x in the
number field nf given by
It is possible to input a defining polynomial for nf
instead, but this is in general less efficient since parts of an
Caveat.
The library syntax is
| |
nfrootsof1 | |
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
| |
nfsnf | |
Given a torsion ℤ_K-module x attached to the square integral invertible pseudo-matrix (A,I,J), returns an ideal list D = [d_1,...,d_n] which is the Smith normal form of x. In other words, x is isomorphic to ℤ_K/d_1⨁ ...⨁ ℤ_K/d_n and d_i divides d_{i-1} for i ≥ 2. If flag is non-zero return [D,U,V], where UAV is the identity. See Section 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 ℤ_K module x given by (b_1e_1⨁ ...⨁ b_ne_n) / (a_1A_1⨁ ...⨁ a_nA_n) , The integrality condition is a_{i,j} ∈ 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
| |
nfsolvemodpr | |
This function is obsolete, use
Let P be a prime ideal in modpr format (see
? 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
| |
nfsplitting | |
Defining polynomial over ℚ for the splitting field of nf;
if d is given, it must be a multiple of the splitting field degree.
Instead of
? K = nfinit(x^3-2); ? nfsplitting(K) %2 = x^6 + 108 ? nfsplitting(x^8-2) %3 = x^16 + 272*x^8 + 64 Specifying the degree of the splitting field can make the computation faster.
? nfsplitting(x^17-123); time = 3,607 ms. ? poldegree(%) %2 = 272 ? nfsplitting(x^17-123,272); time = 150 ms. ? nfsplitting(x^17-123,273); *** nfsplitting: Warning: ignoring incorrect degree bound 273 time = 3,611 ms. The complexity of the algorithm is polynomial in the degree d of the
splitting field and the bitsize of T; if d is large the result will
likely be unusable, e.g.
? nfsplitting(x^6-x-1) [... degree 720 polynomial deleted ...] time = 11,020 ms.
The library syntax is
| |
nfsubfields | |
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
The library syntax is
| |
polcompositum | |
P and Q being squarefree polynomials in ℤ[X] in the same variable, outputs the simple factors of the étale ℚ-algebra A = ℚ(X, Y) / (P(X), Q(Y)). The factors are given by a list of polynomials R in ℤ[X], attached to the number field ℚ(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 linearly disjoint (their intersection is ℚ). 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 The binary digits of flag mean 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 ℚ(X)/(R). Finally, k is a small integer such that b + ka = X modulo R. 2: assume that P and Q define number fields which are linearly disjoint: both polynomials are irreducible and the corresponding number fields have no common subfield besides ℚ. This allows to save a costly factorization over ℚ. In this case return the single simple factor instead of a vector with one element. 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 ℚ(ζ_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 for ℚ[x]/(R)
%6 = x^20 + 25*x^10 + 5
? X \\ root of R in ℚ[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) \\ In the above example, x^5-5 and the 5-th cyclotomic polynomial are irreducible over ℚ; they have coprime degrees so define linearly disjoint extensions and we could have started by
? [R,a] = polcompositum(x^5 - 5, polcyclo(5), 3); \\ [R,a,b,k]
The library syntax is
| |
polgalois | |
Galois group of the non-constant
polynomial T ∈ ℚ[X]. In the present version 2.10.0, T must be irreducible
and the degree d of T must be less than or equal to 7. If the
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
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
| |
polred | |
This function is deprecated, use
All T accepted by 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
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
| |
polredabs | |
Returns a canonical defining polynomial P for the number field
ℚ[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
? polredabs(x^2 + 16) %1 = x^2 + 1 ? K = bnfinit(x^2 + 16); polredabs(K) %2 = x^2 + 1
Warning 1. Using a
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 The binary digits of flag mean
1: outputs a two-component row vector [P,a], where P is the default
output and 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
*
*
*
*
*
| |
polredbest | |
Finds a polynomial with reasonably
small coefficients defining the same number field as T.
All T accepted by
This routine computes an LLL-reduced basis for the ring of integers of
ℚ[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 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 E44
In this example, the initial polynomial P is the one
returned by
If flag = 1: outputs a two-component row vector [P,a], where P is the
default output and
? [P,a] = polredbest(x^4 + 8, 1) %1 = [x^4 + 2, Mod(x^3, x^4 + 2)] ? charpoly(a) %2 = x^4 + 8
In particular, the map ℚ[x]/(T) → ℚ[x]/(P),
x
subst(lift(Q), 'x, a)
if Q is a
The library syntax is
| |
polredord | |
This function is obsolete, use polredbest.
The library syntax is
| |
poltschirnhaus | |
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
The library syntax is
| |
rnfalgtobasis | |
Expresses x on the relative
integral basis. Here, rnf is a relative number field extension L/K
as output by
The library syntax is
| |
rnfbasis | |
Let K the field represented by
bnf, as output by 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 ℤ_K-module.
The library syntax is
| |
rnfbasistoalg | |
Computes the representation of x
as a polmod with polmods coefficients. Here, rnf is a relative number
field extension L/K as output by
The library syntax is
| |
rnfcharpoly | |
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
| |
rnfconductor | |
Given bnf
as output by
The library syntax is
| |
rnfdedekind | |
Given a number field K coded by nf and a monic polynomial P ∈ ℤ_K[X], irreducible over K and thus defining a relative extension L of K, applies Dedekind's criterion to the order ℤ_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
* basis is a pseudo-basis of an enlarged order O produced by Dedekind's criterion, containing the original order ℤ_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 ℤ_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) %3 = [1, [[1, 0, 0; 0, 1, 0; 0, 0, 1], [1, 1, 1]], 8] ? rnfdedekind(nf, P, pr3, 1) %4 = 1
In this example,
? pr2 = idealprimedec(nf,2)[1]; ? rnfdedekind(nf, P, pr2, 1) %6 = 0 ? rnfdedekind(nf, P, pr2) %7 = [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
? B = rnfpseudobasis(nf, P) %8 = [[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) %9 = 2
It is possible to use this routine with non-monic
P = ∑_{i ≤ n} a_i X^i ∈ ℤ_K[X] if flag = 1;
in this case, we test maximality of Dedekind's order generated by
1, a_n α, a_nα^2 + a_{n-1}α,...,
a_nα^{n-1} + a_{n-1}α^{n-2} +...+ a_1α.
The routine will fail if P is 0 on the projective line over the residue
field ℤ_K/
The library syntax is
| |
rnfdet | |
Given a pseudo-matrix M over the maximal order of nf, computes its determinant.
The library syntax is
| |
rnfdisc | |
Given a number field nf as
output by
The library syntax is
| |
rnfeltabstorel | |
Let rnf be a relative
number field extension L/K as output by
? K = nfinit(y^2+1); L = rnfinit(K, x^2-y); ? L.polabs %2 = x^4 + 1 ? rnfeltabstorel(L, Mod(x, L.polabs)) %3 = Mod(x, x^2 + Mod(-y, y^2 + 1)) ? rnfeltabstorel(L, 1/3) %4 = 1/3 ? rnfeltabstorel(L, Mod(x, x^2-y)) %5 = Mod(x, x^2 + Mod(-y, y^2 + 1)) ? rnfeltabstorel(L, [0,0,0,1]~) \\ Z_L not initialized yet *** at top-level: rnfeltabstorel(L,[0, *** ^-------------------- *** rnfeltabstorel: incorrect type in rnfeltabstorel, apply nfinit(rnf). ? nfinit(L); \\ initialize now ? rnfeltabstorel(L, [0,0,0,1]~) %6 = Mod(Mod(y, y^2 + 1)*x, x^2 + Mod(-y, y^2 + 1))
The library syntax is
| |
rnfeltdown | |
rnf being a relative number
field extension L/K as output by
? 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(x^2, L.pol), 1) %4 = [0, 1]~ ? rnfeltdown(L, Mod(y, x^2-y)) %5 = Mod(y, y^2 + 1) ? rnfeltdown(L, Mod(y,K.pol)) %6 = 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 ? rnfeltdown(L, Mod(y, x^2-y), 1) \\ as a t_COL %7 = [0, 1]~ ? rnfeltdown(L, [0,1,0,0]~) \\ not allowed without absolute nf struct *** rnfeltdown: incorrect type in rnfeltdown (t_COL). ? nfinit(L); \\ add absolute nf structure to L ? rnfeltdown(L, [0,1,0,0]~) \\ now OK %8 = Mod(y, y^2 + 1)
If we had started with
The library syntax is
| |
rnfeltnorm | |
rnf being a relative number field extension L/K as output by
? 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
| |
rnfeltreltoabs | |
rnf being a relative
number field extension L/K as output by
? 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
| |
rnfelttrace | |
rnf being a relative number field extension L/K as output by
? 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
| |
rnfeltup | |
rnf being a relative number field extension L/K as output by
? K = nfinit(y^2+1); L = rnfinit(K, x^2-y); ? L.pol %2 = x^4 + 1 ? rnfeltup(L, Mod(y, K.pol)) %3 = Mod(x^2, x^4 + 1) ? rnfeltup(L, y) %4 = Mod(x^2, x^4 + 1) ? rnfeltup(L, [1,2]~) \\ in terms of K.zk %5 = Mod(2*x^2 + 1, x^4 + 1) ? rnfeltup(L, y, 1) \\ in terms of nfinit(L).zk %6 = [0, 1, 0, 0]~ ? rnfeltup(L, [1,2]~, 1) %7 = [1, 2, 0, 0]~
The library syntax is
| |
rnfequation | |
Given a number field
nf as output by
The main variable of nf must be of lower priority than that
of pol (see Section 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
? 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 ℚ, as in the default behavior,
* a expresses as a * k is a small integer such that θ = β+kα is a root of z, where β is a root of pol.
? T = y^3-2; pol = x^2 +x*y + y^2; ? [z,a,k] = rnfequation(T, pol, 1); ? z %3 = x^6 + 108 ? subst(T, y, a) %4 = 0 ? alpha= Mod(y, T); ? beta = Mod(x*Mod(1,T), pol); ? subst(z, x, beta + k*alpha) %7 = 0
The library syntax is
| |
rnfhnfbasis | |
Given bnf as output by
The library syntax is
| |
rnfidealabstorel | |
Let rnf be a relative
number field extension L/K as output by
The reason why the input does not use the customary HNF in terms of a fixed
ℤ-basis for ℤ_L is precisely that no such basis has been explicitly
specified. On the other hand, if you already computed an (absolute)
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); ? 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
| |
rnfidealdown | |
Let rnf be a relative number
field extension L/K as output by
The library syntax is
| |
rnfidealfactor | |
Factors into prime ideal powers the
ideal x in the attached absolute number field L =
? rnf = rnfinit(nfinit(y^2+1), x^2-y+1); ? rnfidealfactor(rnf, y+1) \\ P_2^2 %2 = [[2, [0,0,1,0]~, 4, 1, [0,0,0,2;0,0,-2,0;-1,-1,0,0;1,-1,0,0]] 2] ? rnfidealfactor(rnf, x) \\ P_2 %3 = [[2, [0,0,1,0]~, 4, 1, [0,0,0,2;0,0,-2,0;-1,-1,0,0;1,-1,0,0]] 1] ? L = nfinit(rnf); ? id = idealhnf(L, idealhnf(L, 25, (x+1)^2)); ? idealfactor(L, id) == rnfidealfactor(rnf, id) %6 = 1
Note that ideals of the base field K must be explicitly
lifted to L via
The library syntax is
| |
rnfidealhnf | |
rnf being a relative number
field extension L/K as output by
The library syntax is
| |
rnfidealmul | |
rnf being a relative number
field extension L/K as output by
The library syntax is
| |
rnfidealnormabs | |
Let rnf be a relative
number field extension L/K as output by
idealnorm(rnf, rnfidealnormrel(rnf,x)) but faster.
The library syntax is
| |
rnfidealnormrel | |
Let rnf be a relative
number field extension L/K as output by
The library syntax is
| |
rnfidealprimedec | |
Let rnf be a relative number
field extension L/K as output by
? K = nfinit(y^2+1); rnf = rnfinit(K, x^3+y+1); ? P = idealprimedec(K, 2)[1]; ? S = rnfidealprimedec(rnf, P); ? #S %4 = 1
The argument
? [SK,SL] = rnfidealprimedec(rnf, 5); ? [#SK, vector(#SL,i,#SL[i])] %6 = [2, [2, 2]]
The library syntax is
| |
rnfidealreltoabs | |
Let rnf be a relative
number field extension L/K as output by
? K = nfinit(y^2+1); rnf = rnfinit(K, x^2-y); ? P = idealprimedec(K,2)[1]; ? P = rnfidealup(rnf, P) %3 = [2, x^2 + 1, 2*x, x^3 + x] ? Prel = rnfidealhnf(rnf, P) %4 = [[1, 0; 0, 1], [[2, 1; 0, 1], [2, 1; 0, 1]]] ? rnfidealreltoabs(rnf,Prel) %5 = [2, x^2 + 1, 2*x, x^3 + x] ? rnfidealreltoabs(rnf,Prel,1) %6 = [2 1 0 0] [0 1 0 0] [0 0 2 1] [0 0 0 1] The reason why we do not return by default (flag = 0) the customary HNF in terms of a fixed ℤ-basis for ℤ_L is precisely because a rnf does not contain such a basis by default. Completing the structure so that it contains a nf structure for L is polynomial time but costly when the absolute degree is large, thus it is not done by default. Note that setting flag = 1 will complete the rnf.
The library syntax is
| |
rnfidealtwoelt | |
rnf being a relative
number field extension L/K as output by
The library syntax is
| |
rnfidealup | |
Let rnf be a relative number
field extension L/K as output by
? K = nfinit(y^2+1); rnf = rnfinit(K, x^2-y); ? P = idealprimedec(K,2)[1]; ? rnfidealup(rnf, P) %3 = [2, x^2 + 1, 2*x, x^3 + x] ? rnfidealup(rnf, P,1) %4 = [2 1 0 0] [0 1 0 0] [0 0 2 1] [0 0 0 1] The reason why we do not return by default (flag = 0) the customary HNF in terms of a fixed ℤ-basis for ℤ_L is precisely because a rnf does not contain such a basis by default. Completing the structure so that it contains a nf structure for L is polynomial time but costly when the absolute degree is large, thus it is not done by default. Note that setting flag = 1 will complete the rnf.
The library syntax is
| |
rnfinit | |
nf being a number field in 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 extension attached to the rnf. Furthermore, we let m = [K:ℚ] 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. Access to this information via member functions is preferred since the specific data organization specified below will change in the future.
If flag = 1, add an nf structure attached to L to rnf.
This is likely to be very expensive if the absolute degree mn is large,
but fixes an integer basis for ℤ_L as a ℤ-module and allows to input
and output elements of L in absolute form: as
rnf[1]( rnf[2] contains the integer basis [A,d] of K, as (integral) elements of L/ℚ. 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[4]( rnf[5] is currently unused. rnf[6] is currently unused.
rnf[7] ( rnf[8] is the inverse matrix of the integral basis matrix, with coefficients polmods in nf. rnf[9] is currently unused.
rnf[10] (
rnf[11] is an extension of k is a small integer such that, if β is an abstract root of pol and α the generator of K given above, then P(β + kα) = 0. Caveat. Be careful if k != 0 when dealing simultaneously with absolute and relative quantities since L = ℚ(β + kα) = K(α), 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 β + k α. 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
The library syntax is
| |
rnfisabelian | |
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
| |
rnfisfree | |
Given bnf as output by
The library syntax is
| |
rnfislocalcyclo | |
Let rnf a a relative number field extension L/K as output
by
? K = nfinit(y^2 + y + 1); ? L = rnfinit(K, x^3 - y); /* = K(zeta_9), globally cyclotomic */ ? rnfislocalcyclo(L) %3 = 1 \\ we expect 3-adic continuity by Krasner's lemma ? vector(5, i, rnfislocalcyclo(rnfinit(K, x^3 - y + 3^i))) %5 = [0, 1, 1, 1, 1]
The library syntax is
| |
rnfisnorm | |
Similar to
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
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 ℚ(β) / ℚ(α), where α^3 + α^2 - 2α - 1 = 0 and β^2 + α^2 + 2α + 1 = 0 (it is).
The library syntax is
| |
rnfisnorminit | |
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 ℚ),
polrel is also allowed to be an nf, etc. Computes technical data needed
by 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
If flag = 2, let the routine determine whether L/K is Galois.
The library syntax is
| |
rnfkummer | |
bnr
being as output by
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
The library syntax is
| |
rnflllgram | |
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
The library syntax is
| |
rnfnormgroup | |
bnr being a big ray
class field as output by
The library syntax is
| |
rnfpolred | |
This function is obsolete: use
Remark. this function is based on an incomplete reduction
theory of lattices over number fields, implemented by
The library syntax is
| |
rnfpolredabs | |
This function is obsolete: use 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 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 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 se:polredabs.
Warning. In the present implementation,
The library syntax is
| |
rnfpolredbest | |
Relative version of 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 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
? 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
| |
rnfpseudobasis | |
Given a number field
nf as output by
The library syntax is
| |
rnfsteinitz | |
Given a number field nf as
output by
The library syntax is
| |
subgrouplist | |
bnr being as output by
If flag = 0 (default) and bnr is as output by 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 ℚ(ζ_{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
The library syntax is
| |