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 Hecke Grossencharacters Number field structures Relative extensions bnfcertify bnfdecodemodule bnfinit bnfisintnorm bnfisnorm bnfisprincipal bnfissunit bnfisunit bnflog bnflogdegree bnflogef bnfnarrow bnfsignunit bnfsunit bnfunits bnrL1 bnrchar bnrclassfield bnrclassno bnrclassnolist bnrcompositum bnrconductor bnrconductorofchar bnrdisc bnrdisclist bnrgaloisapply bnrgaloismatrix bnrinit bnrisconductor bnrisgalois bnrisprincipal bnrmap bnrrootnumber bnrstark bnrstarkunit dirzetak factornf galoischardet galoischarpoly galoischartable galoisconjclasses galoisexport galoisfixedfield galoisgetgroup galoisgetname galoisgetpol galoisidentify galoisinit galoisisabelian galoisisnormal galoispermtopol galoissplittinginit galoissubcyclo galoissubfields galoissubgroups gcharalgebraic gcharconductor gcharduallog gchareval gcharidentify gcharinit gcharisalgebraic gcharlocal gcharlog gcharnewprec idealadd idealaddtoone idealappr idealchinese idealcoprime idealdiv idealdown idealfactor idealfactorback idealfrobenius idealhnf idealintersect idealinv idealismaximal idealispower ideallist ideallistarch ideallog idealmin idealmul idealnorm idealnumden idealpow idealprimedec idealprincipalunits idealramgroups idealred idealredmodpower idealstar idealtwoelt idealval matalgtobasis matbasistoalg modreverse newtonpoly nfalgtobasis nfbasis nfbasistoalg nfcertify nfcompositum nfdetint nfdisc nfdiscfactors nfeltadd nfeltdiv nfeltdiveuc nfeltdivmodpr nfeltdivrem nfeltembed nfeltispower nfeltissquare 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 nflist nfmodpr nfmodprinit nfmodprlift nfnewprec nfpolsturm nfresolvent nfroots nfrootsof1 nfsnf nfsolvemodpr nfsplitting nfsubfields nfsubfieldscm nfsubfieldsmax nfweilheight 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 subcyclohminus subcycloiwasawa subcyclopclgp 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
factorization 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 ∏_{i} 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 χ(∏_{j} g_{j}^{nj}) = exp(2π i∑_{j} 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. Basic definitions.
* rnf denotes a relative number field, i.e. a data structure
output by * A relative matrix is an m x n matrix whose entries are elements of K, in any form. Its m columns A_{j} represent elements in K^{n}. * An ideal list is a row vector of fractional ideals of the number field nf. * A pseudo-matrix is a 2-component row vector (A,I) where A is a relative m x n matrix and I an ideal list of length n. If I = {𝔞_{1},..., 𝔞_{n}} and the columns of A are (A_{1},..., A_{n}), this data defines the torsion-free (projective) ℤ_{K}-module 𝔞_{1} A_{1}⨁ 𝔞_{n} A_{n}. * An integral pseudo-matrix is a 3-component row vector (A,I,J) where A = (a_{i,j}) is an m x n relative matrix and I = (𝔟_{1},..., 𝔟_{m}), J = (𝔞_{1},..., 𝔞_{n}) are ideal lists, such that a_{i,j} ∈ 𝔟_{i} 𝔞_{j}^{-1} for all i,j. This data defines two abstract projective ℤ_{K}-modules N = 𝔞_{1}ω_{1}⨁ ...⨁ 𝔞_{n}ω_{n} in K^{n}, P = 𝔟_{1}η_{1}⨁ ...⨁ 𝔟_{m}η_{m} in K^{m}, and a ℤ_{K}-linear map f:N → P given by f(∑_{j} α_{j}ω_{j}) = ∑_{i} (a_{i,j}α_{j}) η_{i}. This data defines the ℤ_{K}-module M = P/f(N). * Any projective ℤ_{K}-moduleprojective module M of finite type in K^{m} can be given by a pseudo matrix (A,I). * An arbitrary ℤ_{K} module of finite type in K^{m}, with nontrivial torsion, is given by an integral pseudo-matrix (A,I,J) Algebraic numbers in relative extension.
We are given a number field K =
* a
* a
* a
* if an absolute
Special case: Pseudo-bases, determinant. * The pair (A,I) is a pseudo-basis of the module it generates if the 𝔞_{j} are nonzero, and the A_{j} are K-linearly independent. We call n the size of the pseudo-basis. If A is a relative matrix, the latter condition means it is square with nonzero determinant; we say that it is in Hermite Normal Form (HNF) if it is upper triangular and all the elements of the diagonal are equal to 1.
* For instance, the relative integer basis * The determinant of a pseudo-basis (A,I) is the ideal equal to the product of the determinant of A by all the ideals of I. The determinant of a pseudo-matrix is the determinant of any pseudo-basis of the module it generates.
| |
Class field theory | |
A modulus, in the sense of class field theory, is a divisor supported
on the real and finite 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 * character is a character χ of the ray class group modulo 𝔣, representing the subgroup Ker χ. 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:
The member functions
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 nonmonic 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 nonnegative 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.
| |
Hecke Grossencharacters | |
Hecke Grossencharacters are continuous characters of the id\`ele class group; they generalize classical Hecke characters on ray class groups obtained through the bnr structure. Let K be a number field, \A^{×} its group of id\`eles. Every Grossencharacter χ : \A^{×}/K^{×} → ℂ^{×} can be uniquely written χ = χ_{0} |.|^{s} for some s ∈ ℂ and some character χ_{0} of the compact group \A^{×}/(K^{×}.ℝ_{ > 0}), where |a |= ∏_{v} |a_{v}|_{v} is the id\`ele norm. Let 𝔪 be a modulus (an integral ideal and a finite set of real places). Let U(𝔪) be the subgroup of id\`eles congruent to 1 modulo 𝔪 (units outside 𝔪, positive at real places in 𝔪). The Hecke Grossencharacters defined modulo 𝔪 are the characters of the id\`ele class group C_{K}(𝔪) = \A^{×}/(K^{×}.U(𝔪)), that is, combinations of an archimedean character χ_{ oo } on the connected component K_{ oo }^{ x o } and a ray class group character χ_{f} satisfying a compatibility condition χ_{ oo }(a)χ_{f}(a) = 1 for all units a congruent to 1 modulo 𝔪. gchar * gc denotes a structure allowing to compute with Hecke Grossencharacters.
*
* gc
* A Hecke character of modulus 𝔪 is described as a
* Hecke Grossencharacters have L-functions and can be given to all
| |
bnfcertify(bnf, {flag = 0}) | |
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: precision too low in makeunits [use bnfinit(,1)]. ? 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
| |
bnfdecodemodule(nf, m) | |
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[2] %1 = [[[Vecsmall([8]), Vecsmall([1])], [[0, 0, 0]]], [[Vecsmall([9]), Vecsmall([1])], [[0, 0, 0]]]] ? bnfdecodemodule(K, s[1][1]) %2 = [2 0] [0 1] ? bnfdecodemodule(K,s[2][1]) %3 = [2 1] [0 1]
The library syntax is
| |
bnfinit(P, {flag = 0}, {tech = []}) | |
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. The meaning of flag is as follows:
* flag = 0 (default). This is the historical behavior, kept for
compatibility reasons and speed. It has severe drawbacks but is likely to be
a little faster than the alternative, twice faster say, so only use it if
speed is paramount, you obtain a useful speed gain for the fields
under consideration, and you are only interested in the field invariants
such as the classgroup structure or its regulator. The computations involve
exact algebraic numbers which are replaced by floating point embeddings for
the sake of speed. If the precision is insufficient,
When flag = 1, we keep an exact algebraic version of all floating point data
and this allows to guarantee that functions using the structure will always
succeed, as well as to compute the fundamental units exactly. The units are
computed in compact form, as a product of small S-units, possibly with
huge exponents. This flag also allows 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 are technical. 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] contains a dummy 0.
bnf[7] or
bnf[8] is a vector containing the classgroup
bnf[9] is a 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(bnf, x, {flag = 0}) | |
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.
If (optional) flag is set, allow returning solutions in factored form, which
helps a lot when the fundamental units are large (equivalently, when
? bnf = bnfinit(x^4-2, 1); ? bnfisintnorm(bnf,7) %2 = [-x^2 + x - 1, x^2 + x + 1] ? bnfisintnorm(bnf,-7) %3 = [-x^3 - 1, x^3 + 2*x^2 + 2*x + 1] ? bnf = bnfinit(x^2-2305843005992468481, 1); ? bnfisintnorm(b, 2305843008139952128) \\ stack overflow with 100GB parisize ? bnf.reg \\ fundamental unit is huge %6 = 14054016.227457155120413774802385952043 ? v = bnfisintnorm(b, 2305843008139952128, 1); #v %7 = 31 \\ succeeds instantly ? s = v[1]; [type(s), matsize(s)] %8 = ["t_MAT", [165, 2]] \\ solution 1 is a product of 165 factors ? exponent(s[,2]) %9 = 105 The exponents have 105 bits, so there is indeed little hope of writing down the solutions in expanded form.
See also
The library syntax is
| |
bnfisnorm(bnf, x, {flag = 1}) | |
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, you may set flag = 0 (in this case, x is a norm iff b = 1). If flag is nonzero 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 4log(disc(Bnf))^{2}, where Bnf is the Galois closure of bnf.
See also
The library syntax is
| |
bnfisprincipal(bnf, x, {flag = 1}) | |
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 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
* 4: Return t in factored form (compact representation),
as a small product of S-units for a small set of finite places S,
possibly with huge exponents. This kind of result can be cheaply mapped to
K^{*}/(K^{*})^{ℓ} or to ℂ or ℚ_{p} to bounded accuracy and this
is usually enough for applications. Explicitly expanding such a compact
representation is possible using
The library syntax is
| |
bnfissunit(bnf, sfu, x) | |
This function is obsolete, use
The library syntax is
| |
bnfisunit(bnf, x, {U}) | |
bnf being the number field data
output by Note that bnf need not contain the fundamental units explicitly: it may contain the placeholder 0 instead:
? setrand(1); bnf = bnfinit(x^2-x-100000); ? bnf.fu %2 = 0 ? u = [119836165644250789990462835950022871665178127611316131167, \ 379554884019013781006303254896369154068336082609238336]~; ? bnfisunit(bnf, u) %3 = [-1, 0]~
The given u is 1/u_{1}, where u_{1} is the fundamental
unit implicitly stored in bnf. In this case, u_{1} was not computed
and stored in algebraic form since the default accuracy was too low. Re-run
the This function allows x to be given in factored form, but it then assumes that x is an actual unit. (Because it is general too costly to check whether this is the case.)
? { v = [2, 85; 5, -71; 13, -162; 17, -76; 23, -37; 29, -104; [224, 1]~, -66; [-86, 1]~, 86; [-241, 1]~, -20; [44, 1]~, 30; [124, 1]~, 11; [125, -1]~, -11; [-214, 1]~, 33; [-213, -1]~, -33; [189, 1]~, 74; [190, -1]~, 104; [-168, 1]~, 2; [-167, -1]~, -8]; } ? bnfisunit(bnf,v) %5 = [1, 0]~
Note that v is the fundamental unit of
If the argument
? bnf = bnfinit(x^4 - x^3 + 4*x^2 + 3*x + 9, 1); ? bnf.sign %2 = [0, 2] ? S = idealprimedec(bnf,5); #S %3 = 2 ? US = bnfunits(bnf,S); ? g = US[1]; #g \\ #S = #g, four S-units generators, in factored form %5 = 4 ? g[1] %6 = [[6, -3, -2, -2]~ 1] ? g[2] %7 = [[-1, 1/2, -1/2, -1/2]~ 1] [ [4, -2, -1, -1]~ 1] ? [nffactorback(bnf, x) | x <- g] %8 = [[6, -3, -2, -2]~, [-5, 5, 0, 0]~, [-1, 1, -1, 0]~, [1, -1, 0, 0]~] ? u = [10,-40,24,11]~; ? a = bnfisunit(bnf, u, US) %9 = [2, 0, 1, 4]~ ? nffactorback(bnf, g, a) \\ prod_{i} g[i]^a[i] still in factored form %10 = [[6, -3, -2, -2]~ 2] [ [0, 0, -1, -1]~ 1] [ [2, -1, -1, 0]~ -2] [ [1, 1, 0, 0]~ 2] [ [-1, 1, 1, 1]~ -1] [ [1, -1, 0, 0]~ 4] ? nffactorback(bnf,%) \\ u = prod_{i} g[i]^a[i] %11 = [10, -40, 24, 11]~
The library syntax is
| |
bnflog(bnf, l) | |
Let bnf be a bnf structure attached to the 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(nf, A, l) | |
Let nf be a nf structure attached to a number field F, and let l be a prime number (hereafter denoted ℓ). The ℓ-adified group of id\`{e}les of F quotiented by the group of logarithmic units is identified to the ℓ-group of logarithmic divisors ⨁ ℤ_{ℓ} [𝔭], generated by the maximal ideals of F.
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(nf, pr) | |
Let nf be a nf structure attached to a number field F and let pr be a prid structure attached to a maximal ideal 𝔭 / p. Return [~{e}(F_{𝔭} / ℚ_{p}), ~{f}(F_{𝔭} / ℚ_{p})] the logarithmic ramification and residue degrees. Let ℚ_{p}^{c}/ℚ_{p} be the cyclotomic ℤ_{p}-extension, then ~{e} = [F_{𝔭} : F_{𝔭} ∩ ℚ_{p}^{c}] and ~{f} = [F_{𝔭} ∩ ℚ_{p}^{c} : ℚ_{p}]. Note that ~{e}~{f} = e(𝔭/p) f(𝔭/p), where e(𝔭/p) and f(𝔭/p) denote the usual ramification and residue degrees.
? 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) | |
bnf being as output by
The library syntax is
| |
bnfsignunit(bnf) | |
bnf being as output by
/* exponents of totally positive units generators on K.tu, K.fu */ tpuexpo(K)= { my(M, S = bnfsignunit(K), [m,n] = matsize(S)); \\ m = K.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) M = matkermod(S, 2); if (M, mathnfmodid(M, 2), 2*matid(n+1)) } /* totally positive fundamental units of bnf K */ tpu(K)= { my(ex = tpuexpo(K)[,^1]); \\ remove ex[,1], corresponds to 1 or -1 my(v = concat(K.tu[2], K.fu)); [ nffactorback(K, v, c) | c <- ex]; }
The library syntax is
| |
bnfsunit(bnf, S) | |
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 obsoleted component, now the empty vector. v[4] is the S-regulator (this is the product of the regulator, the S-class number and the natural logarithms of the norms of the ideals in S). v[5] gives the S-class group structure, in the usual abelian group format: a 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
| |
bnfunits(bnf, {S}) | |
Return the fundamental units of the number field bnf output by bnfinit; if S is present and is a list of prime ideals, compute fundamental S-units instead. The first component of the result contains independent integral S-units generators: first nonunits, then r_{1}+r_{2}-1 fundamental units, then the torsion unit. The result may be used as an optional argument to bnfisunit. The units are given in compact form: no expensive computation is attempted if the bnf does not already contain units.
? bnf = bnfinit(x^4 - x^3 + 4*x^2 + 3*x + 9, 1); ? bnf.sign \\ r1 + r2 - 1 = 1 %2 = [0, 2] ? U = bnfunits(bnf); u = U[1]; ? #u \\ r1 + r2 = 2 units %5 = 2; ? u[1] \\ fundamental unit as factorization matrix %6 = [[0, 0, -1, -1]~ 1] [[2, -1, -1, 0]~ -2] [ [1, 1, 0, 0]~ 2] [ [-1, 1, 1, 1]~ -1] ? u[2] \\ torsion unit as factorization matrix %7 = [[1, -1, 0, 0]~ 1] ? [nffactorback(bnf, z) | z <- u] \\ same units in expanded form %8 = [[-1, 1, -1, 0]~, [1, -1, 0, 0]~] Now an example involving S-units for a nontrivial S:
? S = idealprimedec(bnf,5); #S %9 = 2 ? US = bnfunits(bnf, S); uS = US[1]; ? g = [nffactorback(bnf, z) | z <- uS] \\ now 4 units %11 = [[6, -3, -2, -2]~, [-5, 5, 0, 0]~, [-1, 1, -1, 0]~, [1, -1, 0, 0]~] ? bnfisunit(bnf,[10,-40,24,11]~) %12 = []~ \\ not a unit ? e = bnfisunit(bnf, [10,-40,24,11]~, US) %13 = [2, 0, 1, 4]~ \\ ...but an S-unit ? nffactorback(bnf, g, e) %14 = [10, -40, 24, 11]~ ? nffactorback(bnf, uS, e) \\ in factored form %15 = [[6, -3, -2, -2]~ 2] [ [0, 0, -1, -1]~ 1] [ [2, -1, -1, 0]~ -2] [ [1, 1, 0, 0]~ 2] [ [-1, 1, 1, 1]~ -1] [ [1, -1, 0, 0]~ 4]
Note that in more complicated cases, any
The library syntax is
| |
bnrL1(bnr, {H}, {flag = 0}) | |
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 nonzero 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 nonzero 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(G, g, {v}) | |
Returns all characters χ on G such that χ(g_{i}) = e(v_{i}), where e(x) = exp(2iπ x). G is allowed to be a bnr struct (representing a ray class group) or a znstar (representing (ℤ/Nℤ)^{*}). If v is omitted, returns all characters that are trivial on the g_{i}. Else the vectors g and v must have the same length, the g_{i} must be elements of G, and each v_{i} is a rational number whose denominator must divide the order of g_{i} in G.
For convenience, the vector of the g_{i}
can be replaced by a matrix whose columns give their discrete logarithm
in G, for instance as given by
? G = bnrinit(bnfinit(x), [160,[1]], 1); /* (Z/160Z)^{*} */ ? G.cyc %2 = [8, 4, 2] ? g = G.gen; ? bnrchar(G, g, [1/2,0,0]) %4 = [[4, 0, 0]] \\ a unique character ? bnrchar(G, [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(G, [1,0,0;0,1,0;0,0,2]) %6 = [[0, 0, 1], [0, 0, 0]] \\ characters trivial on given subgroup ? G = znstar(75, 1); ? bnrchar(G, [2, 7], [11/20, 1/4]) %8 = [[1, 1]] \\ Dirichlet char: chi(2) = e(11/20), chi(7) = e(1/4)
The library syntax is
| |
bnrclassfield(bnr, {subgp}, {flag = 0}) | |
bnr being as output by If flag = 0, returns a vector of polynomials such that the compositum of the corresponding fields is the class field; if flag = 1 returns a single polynomial; if flag = 2 returns a single absolute polynomial.
? bnf = bnfinit(y^3+14*y-1); bnf.cyc %1 = [4, 2] ? pol = bnrclassfield(bnf,,1) \\ Hilbert class field %2 = x^8 - 2*x^7 + ... + Mod(11*y^2 - 82*y + 116, y^3 + 14*y - 1) ? rnfdisc(bnf,pol)[1] %3 = 1 ? bnr = bnrinit(bnf,3*5*7); bnr.cyc %4 = [24, 12, 12, 2] ? bnrclassfield(bnr,2) \\ maximal 2-elementary subextension %5 = [x^2 + (-21*y - 105), x^2 + (-5*y - 25), x^2 + (-y - 5), x^2 + (-y - 1)] \\ quadratic extensions of maximal conductor ? bnrclassfield(bnr, subgrouplist(bnr,[2])) %6 = [[x^2 - 105], [x^2 + (-105*y^2 - 1260)], [x^2 + (-105*y - 525)], [x^2 + (-105*y - 105)]] ? #bnrclassfield(bnr,subgrouplist(bnr,[2],1)) \\ all quadratic extensions %7 = 15
When the subgroup contains n Cl_{f}, where n is
fixed, it is advised to directly compute the
? bnf = bnfinit(y^2-5); p = 1594287814679644276013; ? bnr = bnrinit(bnf,p); \\ very slow time = 24,146 ms. ? bnrclassfield(bnr, 2) \\ ... even though the result is trivial %3 = [x^2 - 1594287814679644276013] ? bnr2 = bnrinit(bnf,p,,2); \\ now fast time = 1 ms. ? bnrclassfield(bnr2, 2) %5 = [x^2 - 1594287814679644276013] This will save a lot of time when the modulus contains a maximal ideal whose residue field is large.
The library syntax is
| |
bnrclassno(A, {B}, {C}) | |
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, list) | |
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
| |
bnrcompositum(A, B) | |
Given two abelian extensions A =
? Q = bnfinit(y); ? bnr1 = bnrinit(Q, [7, [1]]); bnr1.cyc %2 = [6] ? bnr2 = bnrinit(Q, [13, [1]]); bnr2.cyc %3 = [12] ? H1 = Mat(2); bnrclassfield(bnr1, H1) %4 = [x^2 + 7] ? H2 = Mat(2); bnrclassfield(bnr2, H2) %5 = [x^2 - 13] ? [bnr,H] = bnrcompositum([bnr1, H1], [bnr2,H2]); ? bnrclassfield(bnr,H) %7 = [x^2 - 13, x^2 + 7]
The library syntax is
| |
bnrconductor(A, {B}, {C}, {flag = 0}) | |
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}]. Note. Using this function with flag ! = 0 is usually a bad idea and kept for compatibility and convenience only: flag = 1 has always been useless, since it is no faster than flag = 2 and returns less information; flag = 2 is mostly OK with two subtle drawbacks:
* it returns the full bnr attached to the full ray class
group, whereas in applications we only need Cl_{f} modulo N-th powers,
where N is any multiple of the exponent of Cl_{f}/H. Computing directly the
conductor, then calling * computing the bnr needs only be done once for each conductor, which is not possible using this function.
For maximal efficiency, the recommended procedure is as follows. Starting
from data (character or congruence subgroups) attached to a modulus m,
we can first compute the conductors using this function with default flag =
0. Then for all data with a common conductor f | m, compute (once!) the
bnr attached to f using
The library syntax is
Also available are
| |
bnrconductorofchar(bnr, chi) | |
This function is obsolete, use bnrconductor.
The library syntax is
| |
bnrdisc(A, {B}, {C}, {flag = 0}) | |
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, bound, {arch}) | |
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^{r1} 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(bnr, mat, H) | |
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(bnr, aut) | |
Return the matrix of the action of the automorphism aut of the base
field
The generators
? K = bnfinit(a^4-3*a^2+253009); B = bnrinit(K,9); B.cyc %1 = [8400, 12, 6, 3] ? G = nfgaloisconj(K) %2 = [-a, a, -1/503*a^3 + 3/503*a, 1/503*a^3 - 3/503*a]~ ? bnrgaloismatrix(B, G[2]) \\ G[2] = Id ... %3 = [1 0 0 0] [0 1 0 0] [0 0 1 0] [0 0 0 1] ? bnrgaloismatrix(B, G[3]) \\ automorphism of order 2 %4 = [799 0 0 2800] [ 0 7 0 4] [ 4 0 5 2] [ 0 0 0 2] ? M = %^2; for (i=1, #B.cyc, M[i,] %= B.cyc[i]); M %5 = \\ acts on ray class group as automorphism of order 2 [1 0 0 0] [0 1 0 0] [0 0 1 0] [0 0 0 1]
See
The library syntax is
| |
bnrinit(bnf, f, {flag = 0}, {cycmod}) | |
bnf is as
output by
If the positive integer
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
explicitly computed, which saves time. Hence If flag = 1, as the default, except that generators are computed.
The library syntax is
| |
bnrisconductor(A, {B}, {C}) | |
Fast variant of
The library syntax is
| |
bnrisgalois(bnr, gal, H) | |
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); B = bnrinit(K,9); G = galoisinit(K); ? [H | H<-subgrouplist(B,3), bnrisgalois(B,G,H)]; time = 160 ms. ? M = bnrgaloismatrix(B,G); ? [H | H<-subgrouplist(B,3), bnrisgalois(B,M,H)] time = 1 ms.
The second computation is much faster since
The library syntax is
| |
bnrisprincipal(bnr, x, {flag = 1}) | |
Let bnr be the ray class group data output by
The binary digits of flag (default flag = 1) mean: * 1: If set returns a 2-component vector [e,α] where e is the vector of components of x on the ray class group generators, α is an element congruent to 1 mod^{*} f such that x = α ∏_{i} g_{i}^{ei}. If unset, returns only e. * 4: If set, returns [e,α] where α is given in factored form (compact representation). This is orders of magnitude faster.
? 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]; \\ the ramified prime ideal above 3 ? bnrisprincipal(bnr,P) \\ bnr.gen undefined ! %5 = [[3, 0, 0]~, 9] ? bnrisprincipal(bnr,P, 0) \\ omit principal part %5 = [3, 0, 0]~ ? bnr = bnrinit(bnr, bnr.bid, 1); \\ include explicit generators ? bnrisprincipal(bnr,P) \\ ... alpha is different ! %7 = [[3, 0, 0]~, 1/128625]
It may be surprising that the generator α is different
although the underlying bnf and bid are the same. This defines
unique generators for the ray class group as ideal classes, whether
we use
Beware that, when
? bnr2 = bnrinit(K, bnr.mod,, 2); \\ modulo squares ? bnr2.clgp %9 = [8, [2, 2, 2]] \\ bnr.clgp tensored by Z/2Z ? bnrisprincipal(bnr2,P, 0) %10 = [1, 0, 0]~
The library syntax is
bnrisprincipal(bnr, x, nf_GEN)
Also available is
| |
bnrmap(A, B) | |
This function has two different uses:
* if A and B are bnr structures for the same bnf attached
to moduli m_{A} and m_{B} with m_{B} | m_{A}, return the canonical surjection
from A to B, i.e. from the ray class group moodulo m_{A} to the ray
class group modulo m_{B}. The map is coded by a triple
[M,cyc_{A},cyc_{B}]:
M gives the image of the fixed ray class group generators of A in
terms of the ones in B, cyc_{A} and cyc_{B} are the cyclic
structures
If B is only known modulo N-th powers (from
* if A is a projection map as above and B is either a congruence
subgroup H, or a ray class character χ, or a discrete logarithm
(from
The library syntax is
| |
bnrrootnumber(bnr, chi, {flag = 0}) | |
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}^{a}g_{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, {subgroup}) | |
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
rnfpolredbest(bnf, pol) \\ compute a reduced relative polynomial rnfpolredbest(bnf, pol, 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. ? bnrclassfield(bnr) time = 20 ms. %2 = [x^2 + (-2/3*y^6 + 7*y^4 - 14*y^2 + 3)]
The library syntax is
| |
bnrstarkunit(bnr, {subgroup}) | |
bnr being as output by The ground field attached to bnr must be totally real and all but one infinite place must become complex in the class field, which must be a quadratic extension of its totally real subfield. Finally, the output is given as a polynomial in x, so the main variable of bnr must not be x. Here is an example:
? bnf = bnfinit(y^2 - 2); ? bnr = bnrinit(bnf, [15, [1,0]]); ? lift(bnrstarkunit(bnr)) %3 = x^8 + (-9000*y - 12728)*x^7 + (57877380*y + 81850978)*x^6 + ... + 1
The library syntax is
| |
dirzetak(nf, b) | |
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(x, t) | |
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 nonrational 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
| |
galoischardet(gal, chi, {o = 1}) | |
Let G be the group attached to the
Return the degree-1 character detρ as the list of det ρ(g),
where g runs through representatives of the conjugacy classes
in
? P = x^5 - x^4 - 5*x^3 + 4*x^2 + 3*x - 1; ? polgalois(P) %2 = [10, 1, 1, "D(5) = 5:2"] ? K = nfsplitting(P); ? gal = galoisinit(K); \\ dihedral of order 10 ? [T,o] = galoischartable(gal); ? chi = T[,1]; \\ trivial character ? galoischardet(gal, chi, o) %7 = [1, 1, 1, 1]~ ? [galoischardet(gal, T[,i], o) | i <- [1..#T]] \\ all characters %8 = [[1, 1, 1, 1]~, [1, 1, -1, 1]~, [1, 1, -1, 1]~, [1, 1, -1, 1]~]
The library syntax is
| |
galoischarpoly(gal, chi, {o = 1}) | |
Let G be the group attached to the
? T = x^5 - x^4 - 5*x^3 + 4*x^2 + 3*x - 1; ? polgalois(T) %2 = [10, 1, 1, "D(5) = 5:2"] ? K = nfsplitting(T); ? gal = galoisinit(K); \\ dihedral of order 10 ? [T,o] = galoischartable(gal); ? o %5 = 5 ? galoischarpoly(gal, T[,1], o) \\ T[,1] is the trivial character %6 = [-x + 1, -x + 1, -x + 1, -x + 1]~ ? galoischarpoly(gal, T[,3], o) %7 = [x^2 - 2*x + 1, x^2 + (y^3 + y^2 + 1)*x + 1, -x^2 + 1, x^2 + (-y^3 - y^2)*x + 1]~
The library syntax is
| |
galoischartable(gal) | |
Compute the character table of G, where G is the underlying group of
the * Each column corresponds to an irreducible character; the characters are ordered by increasing dimension and the first column is the trivial character (hence contains only 1's).
* Each row corresponds to a conjugacy class; the conjugacy classes are
ordered as specified by
The value M[i,j] of the character j at the conjugacy class i
is represented by a polynomial in
Mod(y, polcyclo(e,'y)) (Note that M is the transpose of the usual orientation for character tables.) The integer e divides the exponent of the group G and is chosen as small as posible; for instance e = 1 when the characters are all defined over ℚ, as is the case for S_{n}. Examples:
? K = nfsplitting(x^4+x+1); ? gal = galoisinit(K); ? [M,e] = galoischartable(gal); ? M~ \\ take the transpose to get the usual orientation %4 = [1 1 1 1 1] [1 -1 -1 1 1] [2 0 0 -1 2] [3 -1 1 0 -1] [3 1 -1 0 -1] ? e %5 = 1 ? {G = [Vecsmall([1, 2, 3, 4, 5]), Vecsmall([1, 5, 4, 3, 2]), Vecsmall([2, 1, 5, 4, 3]), Vecsmall([2, 3, 4, 5, 1]), Vecsmall([3, 2, 1, 5, 4]), Vecsmall([3, 4, 5, 1, 2]), Vecsmall([4, 3, 2, 1, 5]), Vecsmall([4, 5, 1, 2, 3]), Vecsmall([5, 1, 2, 3, 4]), Vecsmall([5, 4, 3, 2, 1])];} \\G = D10 ? [M,e] = galoischartable(G); ? M~ %8 = [1 1 1 1] [1 -1 1 1] [2 0 -y^3 - y^2 - 1 y^3 + y^2] [2 0 y^3 + y^2 -y^3 - y^2 - 1] ? e %9 = 5
The library syntax is
| |
galoisconjclasses(gal) | |
gal being output by
? G = galoisinit(x^6+108); ? galoisidentify(G) %2 = [6, 1] \\ S_{3} ? S = galoisconjclasses(G) %3 = [[Vecsmall([1,2,3,4,5,6])], [Vecsmall([3,1,2,6,4,5]),Vecsmall([2,3,1,5,6,4])], [Vecsmall([6,5,4,3,2,1]),Vecsmall([5,4,6,2,1,3]), Vecsmall([4,6,5,1,3,2])]] ? [[permorder(c[1]),#c] | c <- S ] %4 = [[1,1], [3,2], [2,3]]
This command also accepts subgroups returned by
? subs = galoissubgroups(G); H = subs[5]; ? galoisidentify(H) %2 = [2, 1] \\ Z/2 ? S = galoisconjclasses(subgroups_of_{G}[5]); ? [[permorder(c[1]),#c] | c <- S ] %4 = [[1,1], [2,1]]
The library syntax is
| |
galoisexport(gal, {flag}) | |
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, perm, {flag}, {v = y}) | |
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). In this case, P is also expressed in the variable v for compatibility with F. Example:
? G = galoisinit(x^4+1); ? galoisfixedfield(G,G.group[2],2) %2 = [y^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
| |
galoisgetgroup(a, {b}) | |
Query the
The current version of
The library syntax is
| |
galoisgetname(a, b) | |
Query the
? o = 12; N = galoisgetgroup(o); \\ # of abstract groups of order 12 ? for(i=1, N, print(i, ". ", galoisgetname(o,i))) 1. C3 : C4 2. C12 3. A4 4. D12 5. C6 x C2
The current version of
? o = 20; N = galoisgetgroup(o); ? for(i=1, N, print(i, ". ", galoisgetname(o,i))) 1. C5 : C4 2. C20 3. C5 : C4 4. D20 5. C10 x C2
The library syntax is
| |
galoisgetpol(a, {b}, {s}) | |
Query the
*
*
? [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) | |
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(pol, {den}) | |
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}, S_{4} or the group
(3 x 3):4 ( In practice, almost all small groups are WKSS, the exceptions having order 48(2), 56(1), 60(1), 72(3), 75(1), 80(1), 96(10), 112(1), 120(3) and ≥ 144.
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].
* if G/H_{n} ~ (3 x 3):4 ( * for 1 ≤ i ≤ g the subgroup of G generated by [s_{1},...,s_{i}] is normal, with the exception of i = g-2 in the A_{4} and (3 x 3):4 cases and of i = g-3 in the S_{4} 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}^{e1}g_{2}^{e2}...g_{n}^{en} If present den must be a suitable value for gal[5].
The library syntax is
| |
galoisisabelian(gal, {flag = 0}) | |
gal being as output by
This command also accepts subgroups returned by
The library syntax is
| |
galoisisnormal(gal, subgrp) | |
gal being as output by
This command also accepts subgroups returned by
The library syntax is
| |
galoispermtopol(gal, perm) | |
gal being a
Galois group as output by Note that
G = galoisinit(pol); galoispermtopol(G, G[6])~
is equivalent to
The library syntax is
| |
galoissplittinginit(P, {d}) | |
Compute the Galois group over Q of the splitting field of P, that is the smallest field over which P is totally split. P is assumed to be integral, monic and irreducible; it can also be given by a
The library syntax is
| |
galoissubcyclo(N, H, {flag = 0}, {v}) | |
Computes the subextension L 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). This function output is somewhat canonical, as it returns the minimal polynomial of a Gaussian period Tr_{ℚ(ζ_{n})/L}(ζ_{n}). 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 flag = 0, computes a polynomial (in the variable v) defining the subfield of ℚ(ζ_{n}) fixed by the subgroup H of (ℤ/nℤ)^{*}. If flag = 1, computes only the conductor of the abelian extension, as a module. If flag = 2, outputs [pol, N], where pol is the polynomial as output when flag = 0 and N the conductor as output when flag = 1.
If flag = 3; outputs
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(G, {flag = 0}, {v}) | |
Outputs all the subfields of the Galois group G, as a vector.
This works by applying
The library syntax is
| |
galoissubgroups(G) | |
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
| |
gcharalgebraic(gc, {type}) | |
gc being the structure returned by
If type is a
? bnf = bnfinit(x^4-2*x^3+23*x^2-22*x+6,1); ? gc = gcharinit(bnf,1); ? gc.cyc % = [6, 0, 0, 0, 0.E-57] ? gcharalgebraic(gc) % = [1 0 0 0] [0 1 0 0] [0 0 1 0] [0 0 0 0] [0 0 -1/2 -1] ? gcharalgebraic(gc,[[1,1],[0,1]]) % = [] \\ p_{τ}+q_{τ} must be constant for an algebraic character to exist ? chi = gcharalgebraic(gc,[[1,1],[0,2]])[1] % = [0, 1, 2, 0, -1]~ ? for(i=0,5,print(lfuneuler([gc,chi+[i,0,0,0,0]~],3))); \\ all characters with this infinity type: multiply by finite order characters
When the torsion subgroup is not cyclic, we can enumerate the characters of a
given type with
? bnf = bnfinit(x^4+15*x^2+45,1); ? gc = gcharinit(bnf,1); ? gc.cyc % = [2, 2, 0, 0, 0, 0.E-57] ? [chi] = gcharalgebraic(gc,[[2,0],[2,0]]); ? {forvec(v=vectorv(2,i,[0,gc.cyc[i]-1]), print(round(lfunan([gc,chi+concat(v,[0,0,0,0]~)],20))); )}; [1, 0, 0, 4, -5, 0, 0, 0, -9, 0, 16, 0, 0, 0, 0, 16, 0, 0, 16, -20] [1, 0, 0, -4, 5, 0, 0, 0, 9, 0, 16, 0, 0, 0, 0, 16, 0, 0, -16, -20] [1, 0, 0, 4, 5, 0, 0, 0, 9, 0, -16, 0, 0, 0, 0, 16, 0, 0, 16, 20] [1, 0, 0, -4, -5, 0, 0, 0, -9, 0, -16, 0, 0, 0, 0, 16, 0, 0, -16, 20] Some algebraic Hecke characters are related to CM Abelian varieties. We first show an example with an elliptic curve.
? E = ellinit([0, 0, 1, -270, -1708]); \\ elliptic curve with potential CM by ℚ(sqrt{-3}) ? bnf = bnfinit(x^2+3,1); ? p3 = idealprimedec(bnf,3)[1]; ? gc = gcharinit(bnf,Mat([p3,2])); ? gc.cyc % = [0, 0.E-57] ? [chi] = gcharalgebraic(gc,[[1,0]]) % = [[-1, -1/2]~] ? LE = lfuncreate(E); ? lfunan(LE,20) % = [1, 0, 0, -2, 0, 0, -1, 0, 0, 0, 0, 0, 5, 0, 0, 4, 0, 0, -7, 0] ? Lchi = lfuncreate([gc,chi]); ? round(lfunan(Lchi,20)) % = [1, 0, 0, -2, 0, 0, -1, 0, 0, 0, 0, 0, 5, 0, 0, 4, 0, 0, -7, 0] Here is an example with a CM Abelian surface.
? L = lfungenus2([-2*x^4 - 2*x^3 + 2*x^2 + 3*x - 2, x^3]); ? bnf = bnfinit(a^4 - a^3 + 2*a^2 + 4*a + 3, 1); ? pr = idealprimedec(bnf,13)[1]; ? gc = gcharinit(bnf,pr); ? gc.cyc % = [3, 0, 0, 0, 0.E-57] ? chitors = [1,0,0,0,0]~; ? typ = [[1,0],[1,0]]; ? [chi0] = gcharalgebraic(gc,typ); ? igood = oo; nbgood = 0; ? {for(i=0,gc.cyc[1]-1, chi = chi0 + i*chitors; Lchi = lfuncreate([gc,chi]); if(lfunparams(L) == lfunparams(Lchi) && exponent(lfunan(L,10) - lfunan(Lchi,10)) < -50, igood=i; nbgood++ ); )}; ? nbgood % = 1 ? chi = chi0 + igood*chitors; ? Lchi = lfuncreate([gc,chi]); ? lfunan(L,30) % = [1, 0, -3, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, -4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -6, 0, -3, 0] ? round(lfunan(Lchi,30)) % = [1, 0, -3, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, -4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -6, 0, -3, 0]
The library syntax is
| |
gcharconductor(gc, chi) | |
Returns the conductor of * for a real place v, v | 𝔪 iff χ_{v}(-1) = -1. * for a finite place 𝔭, the prime power 𝔭^{e} divides exactly 𝔪 if e ≥ 0 is the smallest integer such that χ_{𝔭} (U_{e}) = 1 where U_{0} = ℤ_{𝔭}^{×} and U_{i} = 1+𝔭^{i}ℤ_{𝔭} for i > 0.
? bnf = bnfinit(x^2-5,1); ? gc = gcharinit(bnf,[(13*19)^2,[1,1]]); ? gc.cyc % = [8892, 6, 2, 0, 0.E-57] ? chi = [0,0,1,1]~; ? gcharconductor(gc,chi) % = [[61009, 7267; 0, 169], [1, 0]] ? gcharconductor(gc,13*chi) % = [[4693, 559; 0, 13], [1, 0]] ? gcharconductor(gc,13*19*chi) % = [[247, 65; 0, 13], [1, 0]] ? gcharconductor(gc,13*19*168*chi) % = [[19, 5; 0, 1], [0, 0]]
The library syntax is
| |
gcharduallog(gc, chi) | |
Returns internal logarithm vector of character The components are organized as follows:
* the first
* the next
* the next r_{1}+r_{2} components are in ℝ and correspond to characters
of ℝ for each infinite place: ϕ encodes x
* the last r_{2} components are in ℤ and correspond to characters of
ℝ/ℤ for each complex place: k encodes z * the last component s is in ℂ and corresponds to a power |.|^{s} of the adélic norm.
See also
? bnf = bnfinit(x^3+4*x-1,1); ? gc = gcharinit(bnf,[1,[1]]); ? gc.cyc % = [2, 0, 0, 0.E-57] ? chi = [0,1,0]~; ? f = gcharduallog(gc,chi) % = [0.153497221319231, 1/2, 0.776369647248353, -0.388184823624176, 1, 0] ? pr = idealprimedec(bnf,2)[1]; ? v = gcharlog(gc,pr); ? exp(2*I*Pi*f*v) % = -0.569867696226731232993110144 - 0.821736459454756074068598760*I ? gchareval(gc,chi,pr) % = -0.569867696226731232993110144 - 0.821736459454756074068598760*I
The library syntax is
| |
gchareval(gc, chi, x, {flag = 1}) | |
gc being the structure returned by
? bnf = bnfinit(x^2-5); ? gc = gcharinit(bnf,1); ? chi = [1]~; ? pr = idealprimedec(bnf,11)[1]; ? a = gchareval(gc,chi,pr) % = -0.3804107379142448929315340886 - 0.9248176417432464199580504588*I ? b = gchareval(gc,chi,pr,0) % = -0.3121086861831031476247589216 ? a == exp(2*Pi*I*b) %7 = 1
The library syntax is
| |
gcharidentify(gc, Lv, Lchiv) | |
gc being a Grossencharacter group as output by
? bnf = bnfinit(x^2-5,1); ? gc = gcharinit(bnf,1); ? chi = gcharidentify(gc,[2],[[0,13.]]); ? gcharlocal(gc,chi,2) % = [0, 13.057005210545987626926134713745179631] ? pr = idealprimedec(bnf,11)[1]; ? chi = gcharidentify(gc,[pr],[0.3]); ? gchareval(gc,chi,pr,0) % = 0.30000006229129706787363344444425752636 If you know only few digits, it may be a good idea to reduce the current precision to obtain a meaningful result.
? bnf = bnfinit(x^2-5,1); ? gc = gcharinit(bnf,1); ? pr = idealprimedec(bnf,11)[1]; ? chi = gcharidentify(gc,[pr],[0.184760]) % = [-420226]~ \\ unlikely to be meaningful ? gchareval(gc,chi,pr,0) % = 0.18475998070331376194260927294721168954 ? \p 10 realprecision = 19 significant digits (10 digits displayed) ? chi = gcharidentify(gc,[pr],[0.184760]) % = [-7]~ \\ probably what we were looking for ? gchareval(gc,chi,pr,0) % = 0.1847608033 ? \p 38 realprecision = 38 significant digits ? gchareval(gc,chi,pr,0) % = 0.18476080328172203337331245154966763237 The output may be a quasi-character.
? bnf = bnfinit(x^2-2,1); ? gc = gcharinit(bnf,1); gc.cyc % = [0, 0.E-57] ? gcharidentify(gc,[1,2],[[0,3.5+1/3*I],[0,-3.5+1/3*I]]) % = [-1, 1/3]~
The library syntax is
| |
gcharinit(bnf, f) | |
bnf being a number field output by
The following member functions are available
on the result:
The internal representation uses a logarithm map on ideals
ℒ: I → ℝ^{n},
so that a Hecke Grossencharacter χ can be described by a n
components vector v via
χ: a ∈ I
See
? bnf = bnfinit(polcyclo(5),1); \\ initializes number field ℚ(ζ_{5}) ? pr = idealprimedec(bnf,5)[1]; \\ prime 𝔭 = (1-ζ_{5}) above 5 ? gc = gcharinit(bnf,idealpow(bnf,pr,2)); \\ characters of modulus dividing 𝔭^{2} ? gc.cyc \\ structure as an abelian group % = [0,0,0,0.E-57] ? chi = [1,1,-1,0]~; \\ a character ? gcharconductor(gc,chi)[1] % = [5 4 1 4] [0 1 0 0] [0 0 1 0] [0 0 0 1]
Currently, gc[1] is a matrix whose rows describe a system of generators of the characters as vectors of ℝ^{n}, under the above description.
gc[2] contains the underlying number field bnf
(
gc[3] contains the underlying number field nf
( gc[4] contains data for computing in (ℤ_{K}/f)^{×}. gc[5] is a vector S of prime ideals which generate the class group. gc[6] contains data to compute discrete logarithms with respect to S in the class group.
gc[7] is a vector
gc[8] is
gc[9] is a vector describing gc as a ℤ-module
via its SNF invariants (
gc[10] is a vector
Specifically, a character gc[11] = m is the matrix of ℒ(v) for all S-units v. gc[12] = u is an integral base change matrix such that gc[1] corresponds to (mu)^{-1}.
The library syntax is
| |
gcharisalgebraic(gc, chi, {&type}) | |
gc being the structure returned by
If type is given, it is set to the
? bnf = bnfinit(x^4+1,1); ? gc = gcharinit(bnf,1); ? gc.cyc % = [0, 0, 0, 0.E-57] ? chi1 = [0,0,1]~; ? gcharisalgebraic(gc,chi1) % = 0 ? gcharlocal(gc,chi1,1) % = [-3, -0.89110698909568455588720672648627467040] ? chi2 = [1,0,0,-3]~; ? gcharisalgebraic(gc,chi2,&typ) % = 1 ? typ % = [[6, 0], [2, 4]] ? gcharlocal(gc,chi2,1) % = [-6, 3*I]
The library syntax is
| |
gcharlocal(gc, chi, v, {&BID}) | |
* if v is a real place, χ_{v}(x) = {\rm sign}(x)^{k} |x|^{iϕ} is encoded as [k,ϕ]; * if v is a complex place, χ_{v}(z) = (z/|z|)^{k} |z|^{2iϕ} is encoded as [k,ϕ];
* if v = 𝔭 is a finite place not dividing gc
* if v = 𝔭 is a finite place dividing gc
? bnf = bnfinit(x^3-x-1); ? gc = gcharinit(bnf,1); ? gc.cyc % = [0, 0, 0.E-57] ? chi = [0,1,1/3]~; ? pr = idealprimedec(bnf,5)[1]; ? gcharlocal(gc,chi,1) % = [0, -4.8839310048284836274074581373242545693 - 1/3*I] ? gcharlocal(gc,chi,2) % = [6, 2.4419655024142418137037290686621272847 - 1/3*I] ? gcharlocal(gc,chi,pr) % = [0.115465135184293124024408915 + 0.0853833331211293579127218326*I] ? bnf = bnfinit(x^2+1,1); ? pr3 = idealprimedec(bnf,3)[1]; ? pr5 = idealprimedec(bnf,5)[1]; ? gc = gcharinit(bnf,[pr3,2;pr5,3]); ? gc.cyc % = [600, 3, 0, 0.E-57] ? chi = [1,1,1]~; ? gcharlocal(gc,chi,pr3,&bid) % = [1, 1, -21/50] ? bid.cyc % = [24, 3] ? gcharlocal(gc,chi,pr5,&bid) % = [98, -0.30120819117478336291229946188762973702] ? bid.cyc % = [100]
The library syntax is
| |
gcharlog(gc, x) | |
Returns the internal (logarithmic) representation of the ideal x suitable
for computations in gc, as a
Its n =
More precisely, let x = (α) ∏ 𝔭_{i}^{ai} a
principalization of x on a set S of primes generating
the class group (see ℒ(x) = [ (a_{i}), log_{f}(α), (log|x/α|_{τ})/(2π), (arg(x/α)_{τ})/(2π), (log N(x))/(2π).i ] where
* the exponent vector (a_{i}) has
* log_{f}(α) is a discrete logarithm of
α in the * log|x/α|_{τ} has r_{1}+r_{2} components, one for each real embedding and pair of complex embeddings τ: K → ℂ (and |z|_{τ} = |z|^{2} for complex τ). * arg{(x/α)_{τ}} has r_{2} components, one for each pair of complex embeddings τ: K → ℂ. * N(x) is the norm of the ideal x.
? bnf = bnfinit(x^3-x^2+5*x+1,1); ? gc = gcharinit(bnf,3); ? gc.cyc % = [3, 0, 0, 0.E-57] ? chi = [1,1,0,-1]~; ? f = gcharduallog(gc,chi); ? pr = idealprimedec(bnf,5)[1]; ? v = gcharlog(gc,pr) % = [2, -5, -1, 0.0188115475004995312411, -0.0188115475004995312411, -0.840176314833856764413, 0.256149999363388073738*I]~ ? exp(2*I*Pi*f*v) % = -4.5285995080704456583673312 + 2.1193835177957097598574507*I ? gchareval(gc,chi,pr) % = -4.5285995080704456583673312 + 2.1193835177957097598574507*I
The library syntax is
| |
gcharnewprec(gc) | |
gc being a Grossencharacter group output by It is advisable to increase the precision before computing several values at large ideals.
The library syntax is
| |
idealadd(nf, x, y) | |
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: nonsquare t_MAT in idealtyp. ? c = [2, 0; 2, 0]; idealadd(K, c, c) \\ nonsense %6 = [2 0] [0 2] ? d = [1, 0; 0, 2]; idealadd(K, d, d) \\ nonsense %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(nf, x, {y}) | |
x and y being two co-prime integral ideals (given in any form), this gives a two-component row vector [a,b] such that a ∈ x, b ∈ y and a+b = 1.
The alternative syntax
The library syntax is
| |
idealappr(nf, x, {flag}) | |
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 nonzero, 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(nf, x, {y}) | |
x being a prime ideal factorization (i.e. a 2-columns matrix whose first column contains prime ideals and the second column contains 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
? 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. In this case, the right hand side y is not allowed to have denominators, unless they are coprime to x.
? 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(nf, x, y) | |
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. In fact, β is also guaranteed to be integral outside primes dividing y.
The library syntax is
| |
idealdiv(nf, x, y, {flag = 0}) | |
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 nonzero, 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. More precisely, the algorithm cheaply removes all maximal ideals above rational primes such that v_{p}(Nx) = v_{p}(Ny).
The library syntax is
| |
idealdown(nf, x) | |
Let nf be a number field as output by
? nf = nfinit(y^2+1); ? idealdown(nf, -1/2) %2 = 1/2 ? idealdown(nf, (y+1)/3) %3 = 2/3 ? idealdown(nf, [2, 11]~) %4 = 125 ? x = idealprimedec(nf, 2)[1]; idealdown(nf, x) %5 = 2 ? idealdown(nf, [130, 94; 0, 2]) %6 = 130
The library syntax is
| |
idealfactor(nf, x, {lim}) | |
Factors into prime ideal powers the ideal x in the number field
nf. The output format is similar to the
? nf = nfinit(x^3-2); ? idealfactor(nf, x) \\ a prime ideal above 2 %2 = [[2, [0, 1, 0]~, 3, 1, ...] 1] ? A = idealhnf(nf, 6*x, 4+2*x+x^2) %3 = [6 0 4] [0 6 2] [0 0 1] ? idealfactor(nf, A) %4 = [[2, [0, 1, 0]~, 3, 1, ...] 2] [[3, [1, 1, 0]~, 3, 1, ...] 2] ? idealfactor(nf, A, 3) \\ restrict to primes above p < 3 %5 = [[2, [0, 1, 0]~, 3, 1, ...] 2]
The library syntax is
| |
idealfactorback(nf, f, {e}, {flag = 0}) | |
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 flag is nonzero, perform ideal reductions (
? 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(nf, gal, pr) | |
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(nf, u, {v}) | |
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 v 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(nf, A, B) | |
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(nf, x) | |
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
| |
idealismaximal(nf, x) | |
Given nf a number field as output by
? K = nfinit(y^2 + 1); ? idealismaximal(K, 3) \\ 3 is inert %2 = [3, [3, 0]~, 1, 2, 1] ? idealismaximal(K, 5) \\ 5 is not %3 = 0 ? pr = idealprimedec(K,5)[1] \\ already a prid %4 = [5, [-2, 1]~, 1, 1, [2, -1; 1, 2]] ? idealismaximal(K, pr) \\ trivial check %5 = [5, [-2, 1]~, 1, 1, [2, -1; 1, 2]] ? x = idealhnf(K, pr) %6 = [5 3] [0 1] ? idealismaximal(K, x) \\ converts from matrix form to prid %7 = [5, [-2, 1]~, 1, 1, [2, -1; 1, 2]]
This function is noticeably faster than
The library syntax is
| |
idealispower(nf, A, n, {&B}) | |
Let nf be a number field and n > 0 be a positive integer. Return 1 if the fractional ideal A = B^{n} is an n-th power and 0 otherwise. If the argument B is present, set it to the n-th root of A, in HNF.
? K = nfinit(x^3 - 2); ? A = [46875, 30966, 9573; 0, 3, 0; 0, 0, 3]; ? idealispower(K, A, 3, &B) %3 = 1 ? B %4 = [75 22 41] [ 0 1 0] [ 0 0 1] ? A = [9375, 2841, 198; 0, 3, 0; 0, 0, 3]; ? idealispower(K, A, 3) %5 = 0
The library syntax is
| |
ideallist(nf, bound, {flag = 4}) | |
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. The information is inferred from local data and Chinese remainders and less expensive than computing than a direct global computation. The binary digits of flag mean: * 1: if the ideals are given by a bid, include generators; otherwise don't.
* 2: if this bit is set, nf must be a bnf with units. Each
component is of the form [bid,U], where bid is attached to
an ideal f and U is a vector of discrete logarithms of the units in
(ℤ_{K}/f)^{*}. More precisely, U gives the * 4: give only the ideal (in HNF), else a bid. * 8: omit ideals which cannot be conductors, i.e. divisible exactly my a prime ideal of norm 2.
? 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 65 in ℤ[i] If one wants more information:
? L = ideallist(nf, 100, 0); ? l = L[25]; vector(#l, i, l[i].clgp) %6 = [[20, [20]], [16, [4, 4]], [20, [20]]] ? l[1].mod %7 = [[25, 18; 0, 1], []] ? l[2].mod %8 = [[5, 0; 0, 5], []] ? l[3].mod %9 = [[25, 7; 0, 1], []]
where we ask for the structures of the (ℤ[i]/f)^{*} 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
Finally, one can input a negative
The library syntax is
| |
ideallistarch(nf, list, arch) | |
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}, x, bid) | |
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(nf, ix, {vdir}) | |
This function is useless and kept for backward compatibility only,
use
The library syntax is
| |
idealmul(nf, x, y, {flag = 0}) | |
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 nonzero, reduce the result using
The library syntax is
See also
| |
idealnorm(nf, x) | |
Computes the norm of the ideal x in the number field nf.
The library syntax is
| |
idealnumden(nf, x) | |
Returns [A,B], where A,B are coprime integer ideals such that x = A/B, in the number field nf.
? nf = nfinit(x^2+1); ? idealnumden(nf, (x+1)/2) %2 = [[1, 0; 0, 1], [2, 1; 0, 1]]
The library syntax is
| |
idealpow(nf, x, k, {flag = 0}) | |
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 nonzero, reduce the result using
The library syntax is
See also
| |
idealprimedec(nf, p, {f = 0}) | |
Computes the prime ideal decomposition of the (positive) prime number p in the number field K represented by nf. If a nonprime p is given the result is undefined. If f is present and nonzero, 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(nf, pr, k) | |
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(nf, gal, pr) | |
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 nontrivial 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(nf, I, {v = 0}) | |
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 nontrivial result does not prove that
the ideal is nonprincipal. 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}^{r1+r2}
2^{vi}ϵ_{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
| |
idealredmodpower(nf, x, n, {B = factorlimit}) | |
Let nf be a number field, x an ideal in nf and n > 0 be a positive integer. Return a number field element b such that x b^{n} = v is small. If x is integral, then v is also integral.
More precisely, The bound B avoids a costly complete factorization of x; as soon as the n-core of x is B-smooth (i.e., as soon as I is n-power free), then J is as large as possible and so is the expected reduction.
? T = x^6+108; nf = nfinit(T); a = Mod(x,T); ? setrand(1); u = (2*a^2+a+3)*random(2^1000*x^6)^6; ? sizebyte(u) %3 = 4864 ? b = idealredmodpower(nf,u,2); ? v2 = nfeltmul(nf,u, nfeltpow(nf,b,2)) %5 = [34, 47, 15, 35, 9, 3]~ ? b = idealredmodpower(nf,u,6); ? v6 = nfeltmul(nf,u, nfeltpow(nf,b,6)) %7 = [3, 0, 2, 6, -7, 1]~
The last element
? idealnorm(nf,v2) %8 = 81309 ? idealnorm(nf,v6) %9 = 731781
The library syntax is
| |
idealstar({nf}, N, {flag = 1}, {cycmod}) | |
Outputs a
If the positive integer
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 faster. The alternative syntax
The library syntax is
| |
idealtwoelt(nf, x, {a}) | |
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
? K = nfinit(t^5-23); ? x = idealhnf(K, t^2*(t+1), t^3*(t+1)) %2 = \\ some random ideal of norm 552*23 [552 23 23 529 23] [ 0 23 0 0 0] [ 0 0 1 0 0] [ 0 0 0 1 0] [ 0 0 0 0 1] ? [a,alpha] = idealtwoelt(K, x) %3 = [552, [23, 0, 1, 0, 0]~] ? nfbasistoalg(K, alpha) %4 = Mod(t^2 + 23, t^5 - 23)
* When called as
? alpha2 = idealtwoelt(K, x, 552) %5 = [-161, -161, -183, -207, 0]~ ? idealhnf(K, 552, alpha2) == x %6 = 1
Note that, in both cases, the return value is not
recognized as an ideal by GP functions; one must use
The library syntax is
| |
idealval(nf, x, pr) | |
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(nf, x) | |
This function is deprecated, use
nf being a number field in
The library syntax is
| |
matbasistoalg(nf, x) | |
This function is deprecated, use
nf being a number field in
The library syntax is
| |
modreverse(z) | |
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(x, p) | |
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(nf, x) | |
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(T, {&dK}) | |
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. If present,
? nfbasis(x^2 + 4) \\ Z[X]/(T) has index 2 in Z_{K} %1 = [1, x/2] ? nfbasis(x^2 + 4, &D) %2 = [1, x/2] ? D %3 = -4 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 may actually be
a global integral basis, in particular if all the prime divisors of the
field discriminant are included, but this is not guaranteed!
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 following function computes the index i_{T} of ℤ[X]/(T) in the order generated by the ℤ-basis B:
nfbasisindex(T, B) = vecprod([denominator(pollead(Q)) | Q <- B]);
In particular, B is a basis of the maximal order
if and only if
? B = nfbasis([T, P], &D); ? dK = sign(D) * vecprod([p^valuation(D,p) | p<-P]); ? dK * nfbasisindex(T, B)^2 == poldisc(T)
The variable 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; ? listP = factor(poldisc(T), B); \\ primes <= B dividing D + cofactor ? basis = nfbasis([T, listP], &D)
If the computed discriminant D factors completely
over the primes less than B (together with the primes contained in the
F = factor(D, B); P = F[,1]; E = F[,2]; for (i = 1, #P, if (P[i] > B && !isprime(P[i]), warning("nf may be incorrect"))); This is a sufficient but not a necessary condition, hence the warning, instead of an error.
The function
? B = 10^5; ? nf = nfinit([T, B]); ? nfcertify(nf) %3 = [] \\ nf is unconditionally correct ? [basis, disc] = [nf.zk, nf.disc];
The library syntax is
| |
nfbasistoalg(nf, x) | |
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) | |
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(nf, P, Q, {flag = 0}) | |
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(nf, x) | |
Given a pseudo-matrix x, computes a
nonzero ideal contained in (i.e. multiple of) the determinant of x. This
is particularly useful in conjunction with
The library syntax is
| |
nfdisc(T) | |
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 following function computes the discriminant of the maximal order under the assumption that P is a vector of prime numbers containing (at least) all prime divisors of the field discriminant:
globaldisc(T, P) = { my (D = nfdisc([T, P])); sign(D) * vecprod([p^valuation(D,p) | p <-P]); } ? globaldisc(x^2 + 6, [2, 3, 5]) %1 = -24
The library syntax is
| |
nfdiscfactors(T) | |
Given a polynomial T with integer coefficients, return
[D, faD] where D is
? T = x^3 - 6021021*x^2 + 12072210077769*x - 8092423140177664432; ? [D,faD] = nfdiscfactors(T); print(faD); D [3, 3; 500009, 2] %2 = -6750243002187] ? T = x^3 + 9*x^2 + 27*x - 125014250689643346789780229390526092263790263725; ? [D,faD] = nfdiscfactors(T); print(faD); D [3, 3; 1000003, 2] %4 = -27000162000243 ? [D,faD] = nfdiscfactors([T, 10^3]); print(faD) [3, 3; 125007125141751093502187, 2] In the final example, we only get a partial factorization, which is only guaranteed correct at primes ≤ 10^{3}.
The function also accept number field structures, for instance as output by
? T = x^3 + 9*x^2 + 27*x - 125014250689643346789780229390526092263790263725; ? nf = nfinit(T); [D,faD] = nfdiscfactors(T); print(faD); D %2 = -27000162000243 ? nf.disc %3 = -27000162000243
The library syntax is
| |
nfeltadd(nf, x, y) | |
Given two elements x and y in nf, computes their sum x+y in the number field nf.
? nf = nfinit(1+x^2); ? nfeltadd(nf, 1, x) \\ 1 + I %2 = [1, 1]~
The library syntax is
| |
nfeltdiv(nf, x, y) | |
Given two elements x and y in nf, computes their quotient x/y in the number field nf.
The library syntax is
| |
nfeltdiveuc(nf, x, y) | |
Given two elements x and y in
nf, computes an algebraic integer q in the number field nf
such that the components of x-qy are reasonably small. In fact, this is
functionally identical to
The library syntax is
| |
nfeltdivmodpr(nf, x, y, pr) | |
This function is obsolete, use
Given two elements x
and y in nf and pr a prime ideal in
The library syntax is
| |
nfeltdivrem(nf, x, y) | |
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
| |
nfeltembed(nf, x, {pl}) | |
Given an element x in the number field nf, return
the (real or) complex embeddings of x specified by optional argument
pl, at the current * pl omitted: return the vector of embeddings at all r_{1}+r_{2} places;
* pl an integer between 1 and r_{1}+r_{2}: return the
i-th embedding of x, attached to the i-th root of
* pl a vector or
? nf = nfinit('y^3 - 2); ? nf.sign %2 = [1, 1] ? nfeltembed(nf, 'y) %3 = [1.25992[...], -0.62996[...] + 1.09112[...]*I]] ? nfeltembed(nf, 'y, 1) %4 = 1.25992[...] ? nfeltembed(nf, 'y, 3) \\ there are only 2 arch. places *** at top-level: nfeltembed(nf,'y,3) *** ^ — — — — — -- *** nfeltembed: domain error in nfeltembed: index > 2
The library syntax is
| |
nfeltispower(nf, x, n, {&y}) | |
Returns 1 if x is an n-th power in the number field
? nf = nfinit(1+x^2); ? nfeltispower(nf, -4, 4, &y) %2 = 1 ? y %3 = [-1, -1]~
The library syntax is
| |
nfeltissquare(nf, x, {&y}) | |
Returns 1 if x is a square in
? nf = nfinit(1+x^2); ? nfeltissquare(nf, -1, &y) %2 = 1 ? y %3 = [0, -1]~
The library syntax is
| |
nfeltmod(nf, x, y) | |
Given two elements x and y in
nf, computes an element r of nf of the form r = x-qy with
q and algebraic integer, and such that r is small. This is functionally
identical to
The library syntax is
| |
nfeltmul(nf, x, y) | |
Given two elements x and y in nf, computes their product x*y in the number field nf.
The library syntax is
| |
nfeltmulmodpr(nf, x, y, pr) | |
This function is obsolete, use
Given two elements x and
y in nf and pr a prime ideal in
The library syntax is
| |
nfeltnorm(nf, x) | |
Returns the absolute norm of x.
The library syntax is
| |
nfeltpow(nf, x, k) | |
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(nf, x, k, pr) | |
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(nf, a, id) | |
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(nf, x, pr) | |
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(nf, x, {pl}) | |
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/11)) ? 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(nf, x) | |
Returns the absolute trace of x.
The library syntax is
| |
nfeltval(nf, x, pr, {&y}) | |
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}^{ei} 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(nf, T) | |
Factorization of the univariate
polynomial (or rational function) 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(nf, f, {e}) | |
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(nf, Q, pr) | |
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(nf, aut, x) | |
Let nf be a
number field as output by
? nf = nfinit(x^2+1); ? L = nfgaloisconj(nf) %2 = [-x, x]~ ? aut = L[1]; /* the nontrivial 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, {flag = 0}, {d}) | |
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(nf, Lpr, Ld, pl, {v = 'x}) | |
Given nf a number field in nf or bnf format,
a * at the prime Lpr[i], the extension has local degree a multiple of Ld[i]; * 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, the function 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(nf, a, b, {pr}) | |
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(nf, x, {flag = 0}) | |
Given a pseudo-matrix (A,I), finds a pseudo-basis (B,J) in Hermite normal form of the module it generates. If flag is nonzero, also return the transformation matrix U such that AU = [0|B].
The library syntax is
| |
nfhnfmod(nf, x, detx) | |
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, {flag = 0}) | |
pol being a nonconstant irreducible polynomial in ℚ[X],
preferably monic and integral, initializes a
number field (or nf) structure attached to the field K defined
by pol. As such, it's a technical object passed as the first argument
to most
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 and a vector vP defined as follows: * 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.
* MDI is a two-element representation (for faster
ideal product) of d(K) times the codifferent ideal
(
* vP is the list of prime divisors of the field discriminant,
i.e, the ramified primes (
nf[6] is the vector containing the r1+r2 roots
(
nf[7] is a ℤ-basis for dℤ_{K}, where d = [ℤ_{K}:ℤ(θ)],
expressed on the powers of θ. The multiplication by
d ensures that all polynomials have integral coefficients
and nf[7] / d ( 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 or non integral 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 following special input formats are also accepted:
* [pol, B] where pol is a monic integral polynomial and
B is the lift of an integer basis, as would be computed by * [pol, B, P] where pol and B are as above (a monic integral polynomial and the lift of an integer basis), and P is the list of ramified primes in the extension.
* [pol,
? pol = polcompositum(x^5 - 101, polcyclo(7))[1]; ? nf = nfinit( [pol, 10^3] ); ? nfcertify(nf) %3 = []
A priori,
In order to explain the meaning of flag, let P =
* 1: return [nf,
* 2: return
Both flags are set automatically when pol is not monic or not
integral: first a linear change of variables is performed, to get a monic
integral polynomial, then
* 4: do not LLL-reduce
? T = polcyclo(307); ? K = nfinit(T); time = 19,390 ms. ? a = idealhnf(K,1-x); time = 477ms ? idealfactor(K, a) time = 294ms ? Kno = nfinit(T, 4); time = 11,256 ms. ? ano = idealhnf(Kno,1-x); \\ no slowdown, even sligthly faster time = 460ms ? idealfactor(Kno, ano) time = 264ms ? nfinit(T, 2); \\ polredbest is very slow in high degree time = 4min, 34,870 ms. ? norml2(%.pol) == norml2(T) \\ and gains nothing here %9 = 1
The library syntax is
*
*
*
| |
nfisideal(nf, x) | |
Returns 1 if x is an ideal in the number field nf, 0 otherwise.
The library syntax is
| |
nfisincl(f, g, {flag = 0}) | |
Let f and g define number fields, where f and g are irreducible
polynomials in ℚ[X] and nf structures as output by * flag = 0 (default): return a vector of polynomials [a_{1},...,a_{n}] with rational coefficients, representing all distinct embeddings: we have g | f o a_{i} for all i. * flag = 1: return a single polynomial a representing a single embedding; this can be n times faster than the default when the embeddings have huge coefficients. * flag = 2: return a vector of rational functions [r_{1},...,r_{n}] whose denominators are coprime to g and such that r_{i} % g is the polynomial a_{i} from flag = 0. This variant is always faster than flag = 0 but produces results which are harder to use. If the denominators are hard to invert in ℚ[X]/(g), this may be even faster than flag = 1.
? T = x^6 + 3*x^4 - 6*x^3 + 3*x^2 + 18*x + 10; ? U = x^3 + 3*x^2 + 3*x - 2 ? nfisincl(U, T) %3 = [24/179*x^5-27/179*x^4+80/179*x^3-234/179*x^2+380/179*x+94/179] ? a = nfisincl(U, T, 1) %4 = 24/179*x^5-27/179*x^4+80/179*x^3-234/179*x^2+380/179*x+94/179 ? subst(U, x, Mod(a,T)) %5 = Mod(0, x^6 + 3*x^4 - 6*x^3 + 3*x^2 + 18*x + 10) ? nfisincl(U, T, 2) \\ a as a t_RFRAC %6 = [(2*x^3 - 3*x^2 + 2*x + 4)/(3*x^2 - 1)] ? (a - %[1]) % T %7 = 0 ? #nfisincl(x^2+1, T) \\ two embeddings %8 = 2 \\ same result with nf structures ? L = nfinit(T); K = nfinit(U); v = [a]; ? nfisincl(U, L) == v %10 = 1 ? nfisincl(K, T) == v %11 = 1 ? nfisincl(K, L) == v %12 = 1 \\ comparative bench: an nf is a little faster, esp. for the subfield ? B = 2000; ? for (i=1, B, nfisincl(U,T)) time = 1,364 ms. ? for (i=1, B, nfisincl(K,T)) time = 988 ms. ? for (i=1, B, nfisincl(U,L)) time = 1,341 ms. ? for (i=1, B, nfisincl(K,L)) time = 880 ms.
Using an nf structure for the tentative subfield is
faster if the structure is already available. On the other hand, the gain in
? for (i=1, B, nfinit(U)) time = 590 ms. A final more complicated example
? f = x^8 - 72*x^6 + 1944*x^4 - 30228*x^2 - 62100*x - 34749; ? g = nfsplitting(f); poldegree(g) %2 = 96 ? #nfisincl(f, g) time = 559 ms. %3 = 8 ? nfisincl(f,g,1); time = 172 ms. ? v = nfisincl(f,g,2); time = 199 ms. ? apply(x->poldegree(denominator(x)), v) %6 = [81, 81, 81, 81, 81, 81, 80, 81] ? v % g; time = 407 ms.
This final example shows that mapping rational functions to
ℚ[X]/(g) can be more costly than that the rest of the algorithm. Note that
The library syntax is
| |
nfisisom(f, g) | |
As
? f = x^6 + 30*x^5 + 495*x^4 + 1870*x^3 + 16317*x^2 - 22560*x + 59648; ? g = x^6 + 42*x^5 + 999*x^4 + 8966*x^3 + 36117*x^2 + 21768*x + 159332; ? h = x^6 + 30*x^5 + 351*x^4 + 2240*x^3 + 10311*x^2 + 35466*x + 58321; ? #nfisisom(f,g) \\ two isomorphisms %3 = 2 ? nfisisom(f,h) \\ not isomorphic %4 = 0 \\ comparative bench ? K = nfinit(f); L = nfinit(g); B = 10^3; ? for (i=1, B, nfisisom(f,g)) time = 6,124 ms. ? for (i=1, B, nfisisom(K,g)) time = 3,356 ms. ? for (i=1, B, nfisisom(f,L)) time = 3,204 ms. ? for (i=1, B, nfisisom(K,L)) time = 3,173 ms. The function is usually very fast when the fields are nonisomorphic, whenever the fields can be distinguished via a simple invariant such as degree, signature or discriminant. It may be slower when the fields share all invariants, but still faster than computing actual isomorphisms:
\\ usually very fast when the answer is 'no': ? for (i=1, B, nfisisom(f,h)) time = 32 ms. \\ but not always ? u = x^6 + 12*x^5 + 6*x^4 - 377*x^3 - 714*x^2 + 5304*x + 15379 ? v = x^6 + 12*x^5 + 60*x^4 + 166*x^3 + 708*x^2 + 6600*x + 23353 ? nfisisom(u,v) %13 = 0 ? polsturm(u) == polsturm(v) %14 = 1 ? nfdisc(u) == nfdisc(v) %15 = 1 ? for(i=1,B, nfisisom(u,v)) time = 1,821 ms. ? K = nfinit(u); L = nfinit(v); ? for(i=1,B, nfisisom(K,v)) time = 232 ms.
The library syntax is
| |
nfislocalpower(nf, pr, a, n) | |
Let nf be a nf structure attached to a number field K, let a ∈ K and let pr be a prid structure attached to a 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(nf, x, pr) | |
This function is obsolete, use
Kernel of the matrix a in ℤ_{K}/pr, where pr is in
modpr format (see
The library syntax is
| |
nflist(G, {N}, {s = -1}, {F}) | |
Finds number fields (up to isomorphism) with Galois group of Galois closure isomorphic to G with s complex places. The number fields are given by polynomials. This function supports the following groups: * degree 2: C_{2} = 2T1; * degree 3: C_{3} = 3T1 and S_{3} = 3T2; * degree 4: C_{4} = 4T1, V_{4} = 4T2, D_{4} = 4T3, A_{4} = 4T4 and S_{4} = 4T5; * degree 5: C_{5} = 5T1, D_{5} = 5T2, F_{5} = M_{20} = 5T3 and A_{5} = 5T4; * degree 6: C_{6} = 6T1, S_{3}(6) = D_{6}(6) = 6T2, D_{6}(12) = 6T3, A_{4}(6) = 6T4, S_{3} x C_{3} = 6T5, A_{4}(6) x C_{2} = 6T6, S_{4}(6)^{+} = 6T7, S_{4}(6)^{−} = 6T8, S_{3}^{2} = 6T9, C_{3}^{2}:C_{4} = 6T10, S_{4}(6) x C_{2} = 6T11, A_{5}(6) = PSL_{2}(5) = 6T12 and C_{3}^{2}:D_{4} = 6T13; * degree 7: C_{7} = 7T1, D_{7} = 7T2, M_{21} = 7T3 and M_{42} = 7T4; * degree 9: C_{9} = 9T1, C_{3} x C_{3} = 9T2 and D_{9} = 9T3; * degree ℓ with ℓ prime: C_{ℓ} = ℓ T1 and D_{ℓ} = ℓ T2.
The groups A_{5} and A_{5}(6) require the optional package
In addition, if N is a polynomial, all transitive subgroups of S_{n} with n ≤ 15, as well as alternating groups A_{n} and the full symmetric group S_{n} for all n (see below for details and explanations).
The groups are coded as [n,k] using the
Alternatively, the groups C_{n}, D_{n}, A_{n}, S_{n},
V_{4}, F_{5} = M_{20}, M_{21} and M_{42} can be input as
character strings exactly as written, lifting subscripts; for instance
The number fields are computed on the fly (and not from a preexisting table)
using a variety of algorithms, with the exception of A_{5} and A_{5}(6)
which are obtained by table lookup.
The algorithms are recursive and use the following ingredients: build
distinguished subfields (or resolvent fields in Galois closures) of smaller
degrees, use class field theory to build abelian extensions over a known
base, select subfields using Galois theory. Because of our use of class
field theory, and ultimately
To avoid wasting time, the output polynomials defining the number fields are
usually not the simplest possible, use The non-negative integer s specifies the number of complex places, between 0 and n/2. Additional supported values are: * s = -1 (default) all signatures; * s = -2 all signatures, given by increasing number of complex places; in degree n, this means a vector with 1 + floor(n/2) components: the i-th entry corresponds to s = i - 1.
If the irreducible monic polynomial F ∈ ℤ[X] is specified, gives only
number fields having ℚ[X]/(F) as a subfield, or in the case of
S_{3}, D_{ℓ}, A_{4}, S_{4}, F_{5}, M_{21} and M_{42},
as a resolvent field (see also the function The parameter N can be the following: * a positive integer: finds all fields with absolute discriminant N (recall that the discriminant over ℚ is (-1)^{s} N). * a pair of non-negative real numbers [a,b] specifying a real interval: finds all fields with absolute value of discriminant between a and b. For most Galois groups, this is faster than iterating on individual N. * omitted (default): a few fields of small discriminant (not always those with smallest absolute discriminant) are output with given G and s; usually about 10, less if too difficult to find. The parameter F is ignored.
* a polynomial with main variable, say t, of priority lower than x.
The program outputs a regular polynomial in ℚ(t)[x] (in fact in
ℤ[x,t]) with the given Galois group. By Hilbert irreducibility, almost all
specializations of t will give suitable polynomials. The parameters s and
F are ignored. This is implemented for all transitive subgroups of
S_{n} with n ≤ 15 as well as for the alternating and symmetric groups
A_{n} and S_{n} for all n.
Polynomials for A_{n} were inspired by J.-F. Mestre, a few polynomials in
degree ≤ 8 come from G. W. Smith, "Some polynomials over ℚ(t) and
their Galois groups", Math. Comp., 69 (230), 1999, pp. 775–796
most others in degree ≤ 11 were provided by J. Klüners and G. Malle
(see G. Malle and B. H. Matzat, Inverse Galois Theory, Springer,
1999) and T. Dokchitser completed the list up to degree 15. But for
A_{n} and S_{n}, subgroups of S_{n} for n > 7 require the optional
Complexity. : For a positive integer N, the complexity is subexponential in log N (and involves factoring N). For an interval [a,b], the complexity is roughly as follows, ignoring terms which are subexponential in log b. It is usually linear in the output size. * C_{n}: O(b^{1/φ(n)}) for n = 2, 4, 6, 9 or any odd prime; * D_{n}: O(b^{2/φ(n)}) for n = 4 or any odd prime; * V_{4}, A_{4}: O(b^{1/2}), S_{4}: O(b); N.B. The subexponential terms are expensive for A_{4} and S_{4}. * M_{20}: O(b). * S_{4}(6)^{−}, S_{4}(6)^{+} A_{4}(6) x C_{2}, S_{3} x S_{3}, S_{4}(6) x C_{2} : O(b), D_{6}(12), A_{4}(6), S_{3}(6), S_{3} x C_{3}, C_{3}^{2}:C_{4}: O(b^{1/2}). * M_{21}, M_{42}: O(b). * C_{3} x C_{3}: O(b^{1/3}), D_{9}: O(b^{5/12}).
? #nflist("S3", [1, 10^5]) \\ S3 cubic fields %1 = 21794 ? #nflist("S3", [1, 10^5], 0) \\ real S3 cubic fields (0 complex place) %2 = 4753 ? #nflist("S3", [1, 10^5], 1) \\ complex cubic fields (1 complex place) %3 = 17041 ? v = nflist("S3", [1, 10^5], -2); apply(length,v) %4 = [4753, 17041] ? nflist("S4") \\ a few S4 fields %5 = [x^4 + 12*x^2 - 8*x + 16, x^4 - 2*x^2 - 8*x + 25, ...] ? nflist("S4",,0) \\ a few real S4 fields %6 = [x^4 - 52*x^2 - 56*x + 48, x^4 - 26*x^2 - 8*x + 1, ...] ? nflist("S4",,-2) \\ a few real S4 fields, by signature %7 = [[x^4 - 52*x^2 - 56*x + 48, ...], [x^4 - 8*x - 16, ... ], [x^4 + 138*x^2 - 8*x + 4541, ...]] ? nflist("S3",,,x^2+23) \\ a few cubic fields with resolvent Q(sqrt(-23)) %8 = [x^3 + x + 1, x^3 + 2*x + 1, ...] ? nflist("C3", 3969) \\ C3 fields of given discriminant %9 = [x^3 - 21*x + 28, x^3 - 21*x - 35] ? nflist([3,1], 3969) \\ C3 fields, using nTt label %10 = [x^3 - 21*x + 28, x^3 - 21*x - 35] ? P = nflist([8,12],t) \\ geometric 8T12 polynomial %11 = x^8 + (-t^2 - 803)*x^6 + (264*t^2 + 165528)*x^4 + (-2064*t^2 - 1724976)*x^2 + 4096*t^2 ? polgalois(subst(P, t, 11)) %12 = [24, 1, 12, "2A_{4}(8)=[2]A(4)=SL(2,3)"] ? nflist("S11") *** at top-level: nflist("S11") *** ^ — — — — - *** nflist: unsupported group (S11). Use one of "C1"=[1,1]; "C2"=[2,1]; "C3"=[3,1], "S3"=[3,2]; "C4"=[4,1], "V4"=[4,2], "D4"=[4,3], "A4"=[4,4], "S4"=[4,5]; "C5"=[5,1], "D5"=[5,2], "F5"="M20"=[5,3], "A5"=[5,4]; "C6"=[6,1], "D6"=[6,2], [6,3], ..., [6,13]; "C7"=[7,1], "D7"=[7,2], "M21"=[7,3], "M42"=[7,4]; "C9"=[9,1], [9,2], "D9"=[9,3]." Also supported are "Cp"=[p,1] and "Dp"=[p,2] for any odd prime p. ? nflist("S25", 't) %13 = x^25 + x*t + 1
The library syntax is
| |
nfmodpr(nf, x, pr) | |
Map x 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, 't); ? K.zk %4 = [1, 1/5*y, 1/25*y^2] ? apply(t->nfmodpr(K,t,modP), K.zk) %5 = [1, t, 2*t + 1] ? %[1].mod %6 = t^2 + 3*t + 4 ? K.index %7 = 125
For clarity, we represent elements in the residue
field 𝔽_{5}[t]/(T) as polynomials in the variable t. Whenever the
underlying rational prime does not divide
The library syntax is
| |
nfmodprinit(nf, pr, {v = variable(nf.pol)}) | |
Transforms the prime ideal pr into
? K = nfinit(y^3-250); ? P = idealprimedec(K, 5)[2]; ? modP = nfmodprinit(K, P, 't); ? K.zk %4 = [1, 1/5*y, 1/25*y^2] ? apply(t->nfmodpr(K,t,modP), K.zk) %5 = [1, t, 2*t + 1] ? %[1].mod %6 = t^2 + 3*t + 4 ? K.index %7 = 125
For clarity, we represent elements in the residue
field 𝔽_{5}[t]/(T) as polynomials in the variable t. Whenever the
underlying rational prime does not divide
The library syntax is
| |
nfmodprlift(nf, x, pr) | |
Lift the
The argument pr is either a maximal ideal in
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(nf) | |
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, a bnr
or a rnf (update structure to current precision). If the original
bnf structure was not computed by
The library syntax is
| |
nfpolsturm(nf, T, {pl}) | |
Given a polynomial T with coefficients in the number field nf, returns the number of real roots of the s(T) where s runs through the real embeddings of the field specified by optional argument pl: * pl omitted: all r_{1} real places;
* pl an integer between 1 and r_{1}: the embedding attached to
the i-th real root of
* pl a vector or
? nf = nfinit('y^2 - 2); ? nf.sign %2 = [2, 0] ? nf.roots %3 = [-1.414..., 1.414...] ? T = x^2 + 'y; ? nfpolsturm(nf, T, 1) \\ subst(T,y,sqrt(2)) has two real roots %5 = 2 ? nfpolsturm(nf, T, 2) \\ subst(T,y,-sqrt(2)) has no real root %6 = 0 ? nfpolsturm(nf, T) \\ all embeddings together %7 = [2, 0] ? nfpolsturm(nf, T, [2,1]) \\ second then first embedding %8 = [0, 2] ? nfpolsturm(nf, x^3) \\ number of distinct roots ! %9 = [1, 1] ? nfpolsturm(nf, x, 6) \\ there are only 2 real embeddings ! *** at top-level: nfpolsturm(nf,x,6) *** ^ — — — — — -- *** nfpolsturm: domain error in nfpolsturm: index > 2
The library syntax is
| |
nfresolvent(pol, {flag = 0}) | |
Let The binary digits of flag correspond to 1: returns a pair [R,f] where f is a "conductor" whose definition is specific to each group and given below; 2: returns all "canonical" subfields.
Let D be the discriminant of the resolvent field * In cases C_{ℓ}, D_{ℓ}, A_{4}, or S_{4}, disc(K) = (Df^{2})^{m} with m = (ℓ-1)/2 in the first two cases, and 1 in the last two. * In cases where K is abelian over the resolvent subfield, the conductor of the relative extension. * In case F_{5}, disc(K) = Df^{4} if f > 0 or 5^{2}Df^{4} if f < 0. * In cases M_{21} or M_{42}, disc(K) = D^{m}f^{6} if f > 0 or 7^{3}D^{m}f^{6} if f < 0, where m = 2 for M_{21} and m = 1 for M_{42}. * In cases A_{5} and A_{5}(6), flag is currently ignored.
? pol = x^6-3*x^5+7*x^4-9*x^3+7*x^2-3*x+1; \\ Galois closure D_{6} ? nfresolvent(pol) %2 = x^3 + x - 1 ? nfresolvent(pol,1) %3 = [x^3 + x - 1, [[31, 21, 3; 0, 1, 0; 0, 0, 1], [1]]]
The library syntax is
| |
nfroots({nf}, x) | |
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(nf) | |
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. It is possible to input a defining polynomial for nf instead.
? 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(nf, x, {flag = 0}) | |
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 nonzero 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_{1}e_{1}⨁ ...⨁ b_{n}e_{n}) / (a_{1}A_{1}⨁ ...⨁ a_{n}A_{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(nf, a, b, P) | |
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(P, {d}, {fl}) | |
Defining polynomial S over ℚ for the splitting field of
P ∈ ℚ[x], that is the smallest field over which P is totally
split. If irreducible, the polynomial P can also be given by a If flag is non-zero, we assume P to be monic, integral and irreducible and the return value depends on flag:
* flag = 1: return [S,C] where S is as before and C is an
embedding of ℚ[x]/(P) in its splitting field given by a polynomial
(implicitly modulo S, as in * flag = 2: return [S,C] where C is vector of rational functions whose image in ℚ[x]/(S) yields the embedding; this avoids inverting the denominator, which is costly. when the degree of the splitting field is huge.
* flag = 3: return [S, v, p] a data structure allowing to quickly
compute the Galois group of the splitting field, which is used by
? K = nfinit(x^3 - 2); ? nfsplitting(K) %2 = x^6 + 108 ? nfsplitting(x^8 - 2) %3 = x^16 + 272*x^8 + 64 ? S = nfsplitting(x^6 - 8) \\ reducible %4 = x^4 + 2*x^2 + 4 ? lift(nfroots(subst(S,x,a),x^6-8)) %5 = [-a, a, -1/2*a^3 - a, -1/2*a^3, 1/2*a^3, 1/2*a^3 + a] ? P = x^8-2; ? [S,C] = nfsplitting(P,,1) %7 = [x^16 + 272*x^8 + 64, -7/768*x^13 - 239/96*x^5 + 1/2*x] ? subst(P, x, Mod(C,S)) %8 = Mod(0, x^16 + 272*x^8 + 64) Specifying the degree d of the splitting field can make the computation faster; if d is not a multiple of the true degree, it will be ignored with a warning.
? 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.
Variant: Also available is
The library syntax is
| |
nfsubfields(pol, {d = 0}, {flag = 0}) | |
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] (default) or simply g (flag = 1), 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
* Allombert's * Klüners's or van Hoeij-Klüners-Novocin algorithm in the general case. The latter runs in polynomial time and is generally superior unless there exists a small unramified prime p such that pol has few irreducible factors modulo p.
An input of the form
? pol = x^4 - x^3 - x^2 + x + 1; ? nfsubfields(pol) %2 = [[x, 0], [x^2 - x + 1, x^3 - x^2 + 1], [x^4 - x^3 - x^2 + x + 1, x]] ? nfsubfields(pol,,1) %2 = [x, x^2 - x + 1, x^4 - x^3 - x^2 + x + 1] ? y=varhigher("y"); fa = nffactor(pol,subst(pol,x,y)); ? #nfsubfields([pol,fa]) %5 = 3
The library syntax is
| |
nfsubfieldscm(nf, {flag = 0}) | |
Computes the maximal CM subfield of nf. Returns 0 if nf does
not have a CM subfield, otherwise returns [g,h] (default) or g (flag = 1)
where g is an absolute equation and h expresses a root of g in terms of
the generator of nf.
Moreover, the CM involution is given by X mod g(X)
An input of the form
? nf = nfinit(x^8 + 20*x^6 + 10*x^4 - 4*x^2 + 9); ? nfsubfieldscm(nf) %2 = [x^4 + 4480*x^2 + 3612672, 3*x^5 + 58*x^3 + 5*x] ? pol = y^16-8*y^14+29*y^12-60*y^10+74*y^8-48*y^6+8*y^4+4*y^2+1; ? fa = nffactor(pol, subst(pol,y,x)); ? nfsubfieldscm([pol,fa]) %5 = [y^8 + ... , ...]
The library syntax is
| |
nfsubfieldsmax(nf, {flag = 0}) | |
Computes the list of maximal subfields of nf. The result is a vector
as in
An input of the form
The library syntax is
| |
nfweilheight(nf, v) | |
Let nf be attached to a number field K, let v be a vector of
elements of K, not all of them 0, seen as element of the projective
space of dimension
When the entries of v are rational, the height is
? v = [1, 2, -3, 101]; Q = nfinit(x); Qi = nfinit(x^2 + 1); ? exponent(nfweilheight(Q, v) - log(101)) %2 = -125 ? exponent(nfweilheight(Qi, v) - log(101)) %3 = -125
The library syntax is
| |
polcompositum(P, Q, {flag = 0}) | |
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(T) | |
Galois group of the nonconstant
polynomial T ∈ ℚ[X]. In the present version 2.16.2, 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(T, {flag = 0}) | |
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 + 1 x^2 - 2*x + 3] [-1/2*x^2 + 1 x^2 - 2*x + 3] [ 1/2*x^2 x^2 + 2] [ 1/4*x^3 x^4 + 2] ? minpoly(Mod(M[4,1], x^4+8)) %2 = x^2 + 2
The library syntax is
| |
polredabs(T, {flag = 0}) | |
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: (OBSOLETE) Possibly use a suborder of the maximal order, without
attempting to certify the result as in Warning 1. This makes
? 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 precise definition of the output of * Consider the finite list of characteristic polynomials of primitive elements of K that are in ℤ_{K} and minimal for the T_{2} norm; now remove from the list the polynomials whose discriminant do not have minimal absolute value. Note that this condition is restricted to the original list of polynomials with minimal T_{2} norm and does not imply that the defining polynomial for the field with smallest discriminant belongs to the list !
* To a polynomial P(x) = x^{n} +...+ a_{n} ∈ ℝ[x] we attach
the sequence S(P) given by |a_{1}|, a_{1},..., |a_{n}|, a_{n}.
Order the polynomials P by the lexicographic order on the coefficient
vectors S(P). Then the output of
The library syntax is
*
*
*
*
*
| |
polredbest(T, {flag = 0}) | |
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 an order in ℚ[X]/(T), then
examines small linear combinations of the basis vectors, computing their
characteristic polynomials. It returns the separable polynomial P 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(x) | |
This function is obsolete, use polredbest.
The library syntax is
| |
poltschirnhaus(x) | |
Applies a random Tschirnhausen
transformation to the polynomial x, which is assumed to be nonconstant
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(rnf, x) | |
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(bnf, M) | |
Let K the field represented by
bnf, as output by It is allowed to use a monic 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.
Huge discriminants, helping rnfdisc. The format [T,B] is
also accepted instead of T and computes an order which is maximal at all
maximal ideals specified by B, see
The library syntax is
| |
rnfbasistoalg(rnf, x) | |
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(nf, T, a, {var = 'x}) | |
Characteristic polynomial of a over nf, where a belongs to the algebra defined by T over nf, i.e. nf[X]/(T). Returns a polynomial in variable v (x by default).
? nf = nfinit(y^2+1); ? rnfcharpoly(nf, x^2+y*x+1, x+y) %2 = x^2 + Mod(-y, y^2 + 1)*x + 1
The library syntax is
| |
rnfconductor(bnf, T, {flag = 0}) | |
Given a bnf structure attached to a number field K, as produced
by
The result is a 3-component vector [f,bnr,H], where f is the
conductor of the extension given as a 2-component row vector
[f_{0},f_{ oo }],
bnr is the attached
* If flag is 1, return [f,bnrmod, H], where
* If flag is 2, only return [f,
Huge discriminants, helping rnfdisc. The format [T,B] is
also accepted instead of T and computes the conductor of the extension
provided it factors completely over the maximal ideals specified by B,
see
The library syntax is
| |
rnfdedekind(nf, pol, {pr}, {flag = 0}) | |
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 nonzero, 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 nonmonic
P = ∑_{i ≤ n} p_{i} X^{i} ∈ ℤ_{K}[X] if flag = 1;
in this case, we test maximality of Dedekind's order generated by
1, p_{n} α, p_{n}α^{2} + p_{n-1}α,...,
p_{n}α^{n-1} + p_{n-1}α^{n-2} +...+ p_{1}α.
The routine will fail if P vanishes on the projective line over the residue
field ℤ_{K}/
The library syntax is
| |
rnfdet(nf, M) | |
Given a pseudo-matrix M over the maximal order of nf, computes its determinant.
The library syntax is
| |
rnfdisc(nf, T) | |
Given an nf structure attached to a number field K, as output
by
Huge discriminants, helping rnfdisc. The format [T,B] is
also accepted instead of T and computes an order which is maximal at all
maximal ideals specified by B, see
The library syntax is
| |
rnfeltabstorel(rnf, x) | |
Let rnf be a relative number field extension L/K as output by
* as a polynomial modulo the absolute equation
* or in terms of the absolute ℤ-basis for ℤ_{L} if rnf
contains one (as in Computes x as an element of the relative extension L/K as a polmod with polmod coefficients. If x is actually rational, return it as a rational number:
? 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)) ? rnfeltabstorel(L, [1,0,0,0]~) %7 = 1
The library syntax is
| |
rnfeltdown(rnf, x, {flag = 0}) | |
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,0,1,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,0,1,0]~) \\ now OK %8 = Mod(y, y^2 + 1)
If we had started with
The library syntax is
| |
rnfeltnorm(rnf, x) | |
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
The library syntax is
| |
rnfeltreltoabs(rnf, x) | |
rnf being 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 ? 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)
If the input is actually rational, then
? rnfeltreltoabs(L, Mod(2, K.pol)) %6 = 2
The library syntax is
| |
rnfelttrace(rnf, x) | |
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
The library syntax is
| |
rnfeltup(rnf, x, {flag = 0}) | |
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]~ ? rnfeltup(L, [1,0]~) \\ rational %8 = 1
The library syntax is
| |
rnfequation(nf, pol, {flag = 0}) | |
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 nonzero, 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. It is guaranteed that k = 0 whenever ℚ(β) = L.
? 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(bnf, M) | |
Given a bnf attached to a number field K and a projective
ℤ_{K}-module M given by a pseudo-matrix, returns either a true HNF basis
of M if one exists, or zero otherwise. If M is a polynomial with
coefficients in K, replace it by the pseudo-matrix returned by
The library syntax is
| |
rnfidealabstorel(rnf, x) | |
Let rnf be a relative
number field extension L/K as output by
Let
? K = nfinit(y^2+1); rnf = rnfinit(K, x^2-y); Labs = nfinit(rnf); ? m = idealhnf(Labs, 17, x^3+2); \\ some ideal in HNF wrt. Labs.zk ? B = rnfidealabstorel(rnf, m) %3 = [[1, 8; 0, 1], [[17, 4; 0, 1], 1]] \\ pseudo-basis for m as Z_{K}-module ? A = rnfidealreltoabs(rnf, B) %4 = [17, x^2 + 4, x + 8, x^3 + 8*x^2] \\ Z-basis for m in Q[x]/(rnf.polabs) ? mathnf(matalgtobasis(Labs, A)) == m %5 = 1
If on the other hand, we do not have a
? K = nfinit(y^2+1); rnf = rnfinit(K, x^2-y); ? rnfidealabstorel(rnf, [17, x^2 + 4, x + 8, x^3 + 8*x^2]) %2 = [[1, 8; 0, 1], [[17, 4; 0, 1], 1]] ? rnfidealabstorel(rnf, Mod([17, y + 4, x + 8, y*x + 8*y], x^2-y)) %3 = [[1, 8; 0, 1], [[17, 4; 0, 1], 1]]
The library syntax is
| |
rnfidealdown(rnf, x) | |
Let rnf be a relative number
field extension L/K as output by
The library syntax is
| |
rnfidealfactor(rnf, x) | |
Factor 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, x) | |
rnf being a relative number
field extension L/K as output by
The library syntax is
| |
rnfidealmul(rnf, x, y) | |
rnf being a relative number
field extension L/K as output by
The library syntax is
| |
rnfidealnormabs(rnf, x) | |
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(rnf, x) | |
Let rnf be a relative
number field extension L/K as output by
The library syntax is
| |
rnfidealprimedec(rnf, pr) | |
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); ? pr = idealprimedec(K, 2)[1]; ? S = rnfidealprimedec(rnf, pr); ? #S %4 = 1
The relative ramification indices and residue degrees
can be obtained as
The argument pr is also allowed to be a prime number p, in which
case the function returns a pair of vectors
? [SK,SL] = rnfidealprimedec(rnf, 5); ? [#SK, vector(#SL,i,#SL[i])] %6 = [2, [2, 2]]
The library syntax is
| |
rnfidealreltoabs(rnf, x, {flag = 0}) | |
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, x) | |
rnf being a relative
number field extension L/K as output by
The library syntax is
| |
rnfidealup(rnf, x, {flag = 0}) | |
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, T, {flag = 0}) | |
Given an nf structure attached to a number field K, as output by
The result is a row vector, whose components are technical. 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](
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 T and α the generator of K given above, then P(β + kα) = 0. It is guaranteed that k = 0 if ℚ(β) = L. 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, T, 1); if (k, T = subst(T, x, x - k*Mod(y, K.pol))); L = rnfinit(K, T);
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
Huge discriminants, helping rnfdisc. When T has a
discriminant which is difficult to factor, it is hard to compute
ℤ_{L}. As in * an integer: the list of all maximal ideals above a rational prime p < B. * a vector of rational primes or prime ideals: the list of all maximal ideals dividing an element in the list. Instead of ℤ_{L}, this produces an order which is maximal at all such maximal ideals primes. The result may actually be a complete and correct rnf structure if the relative ideal discriminant factors completely over this list of maximal ideals but this is not guaranteed. In general, the order may not be maximal at primes 𝔭 not in the list such that 𝔭^{2} divides the relative ideal discriminant.
The library syntax is
| |
rnfisabelian(nf, T) | |
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(bnf, M) | |
Given a bnf attached to a number field K and
a projective ℤ_{K}-module M given by a pseudo-matrix, return true (1) if
M is free else return false (0). If M is a polynomial with coefficients
in K, replace it by the pseudo-matrix returned by
The library syntax is
| |
rnfislocalcyclo(rnf) | |
Let rnf be 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(T, a, {flag = 0}) | |
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 but you may want to add more primes to S to produce different elements, possibly smaller; 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 4log^{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(pol, polrel, {flag = 2}) | |
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, {subgp}) | |
This function is deprecated, use
The library syntax is
| |
rnflllgram(nf, pol, order) | |
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, pol) | |
bnr being a big ray
class field as output by
The library syntax is
| |
rnfpolred(nf, pol) | |
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(nf, pol, {flag = 0}) | |
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, 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. This polynomial is canonical and does not depend on the nf structure. Same as but faster than
polredabs(rnfequation(nf, pol))
3: returns [Pabs,a,b], where Pabs is an absolute polynomial
as above, a, b are
16: (OBSOLETE) possibly use a suborder of the maximal order. This makes
Warning. The complexity of
The library syntax is
| |
rnfpolredbest(nf, pol, {flag = 0}) | |
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(nf, T) | |
Given an nf structure attached to a number field K, as output by
? K = nfinit(y^2+1); ? [A,J,D,d] = rnfpseudobasis(K, x^2+y); ? A %3 = [1 0] [0 1] ? J %4 = [1, 1] ? D %5 = [0, -4]~ ? d %6 = [0, -1]~
Huge discriminants, helping rnfdisc. The format [T,B] is
also accepted instead of T and produce an order which is maximal at all
prime ideals specified by B, see
? p = 585403248812100232206609398101; ? q = 711171340236468512951957953369; ? T = x^2 + 3*(p*q)^2; ? [A,J,D,d] = V = rnfpseudobasis(K, T); D time = 22,178 ms. %10 = 3 ? [A,J,D,d] = W = rnfpseudobasis(K, [T,100]); D time = 5 ms. %11 = 3 ? V == W %12 = 1 ? [A,J,D,d] = W = rnfpseudobasis(K, [T, [3]]); D %13 = 3 ? V == W %14 = 1 In this example, the results are identical since D ∩ ℤ factors over primes less than 100 (and in fact, over 3). Had it not been the case, the order would have been guaranteed maximal at primes 𝔭 | p for p ≤ 100 only (resp. 𝔭 | 3). And might have been nonmaximal at any other prime ideal 𝔭 such that 𝔭^{2} divided D.
The library syntax is
| |
rnfsteinitz(nf, M) | |
Given a nf attached to a number field K and a projective
module M given by a pseudo-matrix, returns a pseudo-basis (A,I)
(not in HNF in general) such that all the ideals of I except perhaps the
last one are equal to the ring of integers of nf. If M is a
polynomial with coefficients in K, replace it by the pseudo-matrix
returned by
The library syntax is
| |
subcyclohminus(fH, {p = 0}) | |
Let F be the abelian number field contained in ℚ(ζ_{f})
corresponding to the subgroup H of (ℤ/fℤ)^{*}.
Computes the relative class number h^{−}(F) = h(F)/h(F^{+}) of F.
The argument
*
*
*
* * an irreducible integral polynomial defining a primitive element for F. The algorithm is based on an analytic class number formula: h^{−}(F) = Q(F)w(F)∏_{K ⊂ F}N_{ℚ(ζ_{d})/ℚ} l(-B_{1,χ}/2r) , where Q(F) is the unit index of F, w(F) is the number of roots of unity contained in F and K runs through all imaginary cyclic subfields of F. For each K, d is the degree [K:ℚ], χ is an arbitrary injective character of G(K/ℚ) to ℂ^{×} and the Bernoulli number is given by B_{1,χ} = (1/f_{χ})∑_{a = 1}^{fχ}aχ(a) = -(1/(2-χ(2)) ∑_{1 ≤ a ≤ f_{χ}/2}χ(a) , where f_{χ} is the conductor of χ, namely the conductor of K. The unit index Q ∈ {1,2} is difficult to determine in general. If it could be computed, the function returns [a, b] = [h^{−}, Q]; else it returns [2h^{−}/Q, 0]. More precisely, the second component is 0 unless we are in one of the following cases: * If f = p^{a} with a prime number p, then Q = 1. * If F = ℚ(ζ_{f}), then Q = 1 if and only if f = p^{a}. * If f = 4p^{a} or p^{a}q^{b} with odd prime numbers p,q, then Q = 1 if and only if [ℚ(ζ_{f}):F] is even.
Finally, the optional parameter p is an odd prime number.
If p is given, then
? [a,b] = subcyclohminus(22220); b %1 = 2 \\ = Q ? sizedigit(a) %2 = 4306 \\ huge... ? valuation(a, 101) %3 = 41 ? subcyclohminus(22220, 101) \\ directly compute the valuation %4 = 41 shows that 101^{41} divides h^{−}(ℚ(ζ_{22220})) exactly. Let k_{n} be the n-th layer of the cyclotomic ℤ_{3}-extension of k = ℚ(sqrt{-1501391}); the following computes e_{n} for 1 ≤ n ≤ 3, where 3^{en} is the 3-part of the relative class number h^{−}(k_{n}):
? d = 1501391; ? subcyclohminus([9*d, [28,10,8]], 3) %1 = 5 ? subcyclohminus([27*d, [28,188,53]], 3) %2 = 12 ? subcyclohminus([81*d, [161,80,242]], 3) %3 = 26 Note that h^{+}(k_{n}) is prime to 3 for all n ≥ 0. The following example computes the 3-part of h^{−}(F), where F is the subfield of the 7860079-th cyclotomic field with degree 2.3^{8}.
? p=7860079; a=znprimroot(p)^(2*3^8); ? valuation(subcyclohminus([p,a])[1], 3) time = 1min, 47,896 ms. %2 = 65 ? subcyclohminus([p,a], 3) time = 1,290 ms. %3 = 65
The library syntax is
| |
subcycloiwasawa(fH, p, {n = 0}) | |
Let F be the abelian number field contained in ℚ(ζ_{f}) corresponding to the subgroup H of (ℤ/fℤ)^{*}, let p > 2 be an odd prime not dividing [F:ℚ], let F_{ oo } be the cyclotomic ℤ_{p}-extension of F and let F_{n} by its n-th layer. Computes the minus part of Iwasawa polynomials and λ-invariants attached to F_{ oo }, using the Stickelberger elements ξ_{n}^{χ} belonging to F_{n}.
The function is only implemented when p, n and f are relatively small:
all of p^{4}, p^{n+1} and f must fit into an
*
*
*
* * an irreducible integral polynomial defining a primitive element for F. If F is quadratic, we also allow p = 2 and more data is output (see below).
For a number field K, we write K_{n} for the n-th layer of the
cyclotomic ℤ_{p}-extension of K. The algorithm considers all cyclic
subfields K of F and all injective odd characters
χ:Gal(K/ℚ) If n = 0, the function returns [λ_{p}^{−}(F)] (the vector may contain further useful components, see below); for positive n, it returns all non-constant G_{n}^{χ}(x) mod {p^{n+1-r}} as (K,χ) vary.
? subcycloiwasawa(22220, 41) \\ f = 22220, H = {1} %1 = [217] ? P = polcompositum(x^2 - 42853, polcyclo(5))[1]; ? subcycloiwasawa(P, 5) %3 = [3] ? subcycloiwasawa(P, 5, 4) \\ the sum of the degrees is indeed 3 %4 = [T + 585, T^2 + 405*T] The first example corresponds to F = ℚ(ζ_{22220}) and shows, that λ_{41}^{−}(F) = 217. The second one builds F = ℚ(sqrt{42853}, ζ_{5}) then lists the non-constant G_{4}^{χ}(x) mod {p^{4}} for p = 5. Note that in this case all degrees are ≤ 5 hence r ≤ 1 and n+1-r ≥ n; so the above also gives G_{χ} modulo p^{4}. We henceforth restrict to the quadratic case, where more information is available, and p = 2 is now allowed: we write F = ℚ(sqrt{d}) of discriminant d ( ! = 1) and character χ. Algorithm and output for n = 0, F = ℚ(sqrt{d}). Currently, only the case d < 0 (F quadratic imaginary, i.e. χ(-1) = -1) is implemented.
* If p > 2, the function returns
[λ, ν, [e_{0},...,e_{k}]], where λ = λ_{p}^{−}(F),
p^{en} denotes the p-part of the class number of F_{n} and e_{n} =
λ n + ν for all n > k. We use Gold's theorem
(Acta Arith. vol.26 (1974), pp. 21–32, vol.26 (1975), pp. 233–240).
Then as soon as e_{n} - e_{n-1} < ϕ(p^{n}) for some n ≥ 1, we have
λ_{p}(F) = e_{n}-e_{n-1};
if χ(p) = 1 we can weaken the hypothesis to e_{n}-e_{n-1} ≤
ϕ(p^{n}) for some n ≥ 1 and obtain the same conclusion.
To compute e_{n} - e_{n-1} we use Bernoulli numbers
( * For p = 2, we use Kida's formula (Tohoku Math. J. vol. 31 (1979), pp. 91–96) and only return [λ^{−}].
When d > 1,
? subcycloiwasawa(x^2+11111, 2) %1 = [5] /* λ_{2}(ℚ(sqrt{-11111})) = 5 */ ? subcycloiwasawa(x^2+11111, 3) %2 = [1, 0, []] ? subcycloiwasawa(x^2+11111, 11) %3 = [0, 0, []] This shows that for p = 3, we have λ = 1, ν = 0, and e_{n} = n for all n ≥ 0. And at p = 11, we have e_{n} = 0 for all n ≥ 0.
? subcycloiwasawa(x^2+1501391, 3) time = 23 ms. %4 = [14, -16, [2, 5]] computes e_{n} by Gold's algorithm for F = ℚ(sqrt{-1501391}). This shows that at p = 3, we have λ = 14, ν = -16, then e_{0} = 2, e_{1} = 5, and e_{n} = 14n-16 for n ≥ 2.
? subcycloiwasawa(x^2+956238, 3) time = 141 ms. %5 = [14, -19, [1, 3]] computes e_{n} using Bernoulli numbers for F = ℚ(sqrt{-956238}). This shows that e_{0} = 1, e_{1} = 3 and e_{n} = 14n-19 for n ≥ 2. Algorithm and output for n > 0; F = ℚ(sqrt{d}).
* When d < 0 and n ≥ 1,
Conjecturally, we have further 1. case q_{0} = p: ξ_{n} ∈ ℤ[Σ_{n}]. 2. case d = -1 and χ(p) = -1: ξ_{n} ∈ ℤ[Σ_{n}]. 3. case d = -3 and χ(p) = -1: (3/2)ξ_{n} ∈ ℤ[Σ_{n}]. 4. other cases: (1/2)ξ_{n} ∈ ℤ[Σ_{n}].
Finally,
? subcycloiwasawa(x^2+239, 3, 10) %6 = [x^6 + 18780*x^5 + 14526*x^4 + 18168*x^3 + 3951*x^2 + 1128*x] This is g(x) mod {3^{9}}. Indeed, n = 10, λ = 6 (the degree), hence r = 2 and n + 1 - r = 2.
* When d > 1 and n ≥ 1, ξ_{n}^{*} ∈ ℚ[Σ_{n}] is
constructed from
χ^{*} = χ^{-1}ω, where χ is the character of
F = ℚ(sqrt{d})
and ω is the Teichmüller character mod q. Next we construct
f_{n}^{*}(x) ∈ ℤ_{p}[x] from (1/2)ξ_{n}^{*} by the correspondence
s^{-1}
? subcycloiwasawa(x^2-13841, 2, 19) time = 1min, 17,238 ms. %7 = [x^3 + 30644*x^2 + 126772*x + 44128] This is g^{*}(x) mod {2^{17}} (r = 2), the distinguished polynomial treated in a paper of T. Fukuda, K. Komatsu, M. Ozaki and T. Tsuji (Funct. Approx. Comment. Math. vol.54.1, pp. 7–17, 2016).
The library syntax is
| |
subcyclopclgp(fH, p, {flag = 0}) | |
Let F be the abelian number field contained in ℚ(ζ_{f}) corresponding to the subgroup H of (ℤ/fℤ)^{*}, let p > 2 be an odd prime not dividing [F:ℚ]. Computes the p-Sylow subgroup A_{F} of the ideal class group using an unconditional algorithm of M. Aoki and T. Fukuda (LNCS. vol.4076, pp.56–71, 2006).
The argument
*
*
*
* * an irreducible integral polynomial defining a primitive element for F. The result is a 6-component vector v, and components 2 or 3 can be left empty or only partially computed to save time (see flag below): v[1] is p. v[2] contains [E, [e_{1},...,e_{k}]] with E = ∑_{i} e_{i}, meaning that the order of A_{F}^{+} is p^{E} and its cyclic structure is ℤ/p^{e1}ℤ x...ℤ/p^{ek}ℤ v[3] similarly describes the order and the structure of A_{F}^{−}. v[4] contains the structure of Gal(F/ℚ) as a product of cyclic groups (elementary divisors). v[5] is the number of cyclic subfields K of F except for ℚ.
v[6] is the number of ℚ_{p}-conjugacy classes of injective
characters χ:Gal(K/ℚ) A vector of primes p is also accepted and the result is then a vector of vectors as above, in the same order as the primes. The group A_{F} is the direct sum of A_{F}^{+} and A_{F}^{−}; each of A_{F}^{+} and A_{F}^{−} is decomposed into χ-parts A_{χ}. By default, the function computes only |A_{F}^{−}| and an upper bound for |A_{F}^{+}| (expected to be equal to |A_{F}^{+}|) separately with different algorithms. This is expected to be fast. The behavior is controled by the binary digits of flag: 1: if |A_{F}^{+}| or |A_{F}^{−}| is computed, also determines its group structure and guarantees informations about A_{F}^{+}. This last part is usually costly. 2: do not compute quantities related to A_{F}^{+} (the corresponding (e_{i}) in v[2] is replaced with a dummy empty vector). 4: do not compute quantities related to A_{F}^{−} (the corresponding (e_{i}) in v[3] is replaced with a dummy empty vector). 8: ignores proper subfields of F. This is motivated by the following kind of problems: let ℚ(p^{k}) be the k-th layer of the cyclotomic ℤ_{p}-extension of ℚ and define ℚ(n) = ℚ(p_{1}^{e1})...ℚ(p_{r}^{er}) when n factors as n = p_{1}^{e1}...p_{r}^{er}, which is a real cyclic field of degree n satisfying ℚ(n) ⊂ ℚ(m) when n | m. What are the prime factors of the class number h(n) of ℚ(n) ? The new prime factors of h(n), not occurring in a lower level, will all be present when using this flag. The other values are technical and only useful when bit 1 (certification and structure) is set; do not set them unless you run into difficulties with default parameters. 16: when this bit is set, the function tries to save memory, sacrificing speed; this typically uses half the memory for a slowdown of a factor 2. 32: likely to speed up the algorithm when the rank of A_{χ} is large and to create a minor slowdown otherwise. Though the effect is restricted, the 3-class group of ℚ(sqrt{15338}, ζ_{5}) is computed 4 times faster when this bit is set (see below). Examples. With default flag = 0, the function (quickly) determines the exact value of |A_{F}^{−}| and a rigorous upper bound of |A_{F}^{+}| which is expected to be equal to |A_{F}^{+}|; of course, when the upper bound is 0, we know for sure that A_{F}^{+} is trivial. With flag = 1 we obtain the group structure of A_{F} completely and guarantee the informations about A_{F}^{+} (slow).
? subcyclopclgp(22220, 101) time = 113 ms. %1 = [101, [0, []], [41, [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]], [100, 20, 2, 2], 479, 7999]
This computes the 101-part A_{F} of the ideal class group of
F = ℚ(ζ_{22220}).
The output says that A_{F}^{+} = 0, which is rigorous (since trivial),
and |A_{F}^{−} |= 101^{41}, more precisely A_{F}^{−} is isomorphic to
(ℤ/101ℤ)^{41} which is also rigorous
(since the description of A_{F}^{−} is always rigorous). The Galois group
Gal(F/ℚ) is ℤ/100ℤ⨁ ℤ/20ℤ⨁ ℤ/2ℤ⨁ ℤ/2ℤ.
The field F has 479 cyclic subfields different from ℚ and
there are 7999 ℚ_{101}-conjugacy classes of injective characters
χ:Gal(K/ℚ)
? subcyclopclgp(22220, 11) time = 83 ms. %2 = [11, [2, [1, 1]], [16, []], [100, 20, 2, 2], 479, 1799] This computes the 11-part A_{F} for the same F. The result says that |A_{F}^{+} |= 11^{2}, A_{F}^{+} is isomorphic to (ℤ/11ℤ)^{2} which is not rigorous and is only an upper bound, and |A_{F}^{−} |= 11^{16} which is rigorous. The group structure of A_{F}^{−} is unknown.
? subcyclopclgp(22220, 11, 1) time = 185 ms. %3 = [11, [2, [1, 1]], [16, [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]], [100, 20, 2, 2], 479, 1799] now guarantees that A_{F}^{+} is isomorphic to (ℤ/11ℤ)^{2} and determines that A_{F}^{−} is isomorphic to ℤ/11^{2}ℤ⨁ (ℤ/11ℤ)^{14}, at the expense of slightly increasing the running time. We now try a much harder example: F = ℚ(sqrt{36322},ζ_{5}), which we could define using f = 726440 and H = [41, 61, 111, 131] (prove it!). We will use a defining polynomial instead:
? T = polcompositum(x^2-36322, polcyclo(5), 2); ? subcyclopclgp(T, 5) \\ fast when non rigorous for A^+ time = 82 ms. %4 = [5, [1, [1]], [4, []], [4, 2], 5, 7] \\ try to certify; requires about 2GB of memory ? subcyclopclgp(T, 5, 1) *** subcyclopclgp: the PARI stack overflows ! current stack size: 1000003072 (1907.352 Mbytes) ? default(parisizemax,"2G"); ? subcyclopclgp(T, 5, 1) \\ with more memory, we get an answer time = 36,201 ms. %6 = [5, [1, [1]], [4, [3, 1]], [4, 2], 5, 7] \\ trying to reduce memory use does not work (still need 2GB); slower ? subcyclopclgp(T, 5, 1+16) time = 39,450 ms. This shows that A_{F}^{+} is isomorphic to ℤ/5ℤ and A_{F}^{−} is isomorphic to ℤ/5^{3}ℤ⨁ ℤ/5ℤ for p = 5. For this example, trying to reduce memory use with flag = 1+16 fails: the computation becomes slower and still needs 2GB; flag = 1+16+32 is a disaster: it requires about 8GB and 9 minutes of computation. Here's a situation where the technical flags make a difference: let F = ℚ(sqrt{15338}, ζ_{5}).
? T = polcompositum(x^2-15338, polcyclo(5), 2); ? subcyclopclgp(T, 3) time = 123 ms. %2 = [3, [1, [1]], [4, []], [4, 2], 5, 5] ? subcyclopclgp(T, 3, 1) \\ requires a stack of 8GB time = 4min, 47,822 ms. %3 = [3, [1, [1]], [4, [1, 1, 1, 1]], [4, 2], 5, 5] ? subcyclopclgp(T, 3, 1+16); time = 7min, 20,876 ms. \\ works with 5GB, but slower ? subcyclopclgp(T, 3, 1+32); time = 1min, 11,424 ms. \\ also works with 5GB, 4 times faster than original ? subcyclopclgp(T, 3, 1+16+32); time = 1min, 47,285 ms. \\ now works with 2.5GB Let F = ℚ(106) defined as above; namely, F is the composite field of ℚ(sqrt{2}) and the subfield of ℚ(ζ_{532}) with degree 53. This time we shall build the compositum using class field theory:
? Q = bnfinit(y); ? bnr1 = bnrinit(Q, 8); H1 = Mat(2); ? bnr2 = bnrinit(Q, [53^2, [1]]); H2 = Mat(53); ? [bnr,H] = bnrcompositum([bnr1, H1], [bnr2, H2]); ? subcyclopclgp([bnr,H], 107) time = 10 ms. %5 = [107, [1, [1]], [0, []], [106], 3, 105] ? subcyclopclgp([bnr,H], 107, 1) \\ requires 2.5GB time = 15min, 13,537 ms. %6 = [107, [1, [1]], [0, []], [106], 3, 105] Both results are identical (and they were expected to be), but only the second is rigorous. Flag bit 32 has a minor impact in this case (reduces timings by 20 s.)
The library syntax is
| |
subgrouplist(cyc, {bound}, {flag = 0}) | |
cyc being a vector of positive integers giving the cyclic
components for a finite Abelian group G (or any object which has a
If flag = 0 (default) and cyc is a bnr structure 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
Warning. This function requires factoring the exponent of G.
If you are only interested in subgroups of index n (or dividing n), you
may considerably speed up the function by computing the subgroups of
G/G^{n}, whose cyclic components are
The library syntax is
| |