We first introduce generic Galois theory over ℚ then specialize to abelian extensions of number fields.
Functions related to generic Galois theory over ℚ share the prefix
galois. The galoisinit(T) function computes the Galois group
of K = ℚ[X]/(T) over ℚ and its output allows to compute subgroupgs
(galoissubgroups), identify Galois groups and subgroups
galoisidentify, compute fixed fields K^H, compute character tables
(galoischartable) or just check properties (galoisisnormal,
galoisisabelian). If K is not Galois, galoisinit simply
returns 0.
If the galpol package is installed, then additional functions
galoisgetgroup, galoisgetname and galoisgetpol
become available and support all groups of order ≤ 143. The last one
provides defining polynomials T solving the inverse Galois problem for
all small groups.
The function nflist returns all polynomials of given Galois closure
and discriminant less than the given bound (see the function help for the
list of supported groups). The package nflistdata allows to support
the A5 group as well as to obtain regular polynmials in ℚ(t)[x] with
given Galois group over ℚ(t) (for all transitive subgroups of Sn,
n ≤ 15).
A finite abelian group G is given by its Smith
Normal Form as a pair [h,d] or triple [h,d,g].
Here h is the cardinality of G, (di) is the vector of elementary
divisors, and (gi) is a vector of generators. In short,
G = ⨁ i ≤ n (ℤ/diℤ) gi, with
dn | ... | d2 | d1
and ∏i di = h. This information can also be retrieved as
G.no, G.cyc and G.gen.
* a character on the abelian group ⨁ (ℤ/djℤ) gj is given by a row vector χ = [a1,...,an] such that χ(∏j gjnj) = exp(2π i∑j aj nj / dj).
* 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 gi. Note that the determinant of that matrix is equal to the index (G:H).
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 r1 {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
K.roots. (That ordering is not canonical, but well defined once a
defining polynomial for K is chosen.) For instance, [1, [1,1]] is a
modulus for a real quadratic field, allowing ramification at any of the two
places at infinity, and nowhere else.
A bid or "big ideal" is a structure output by idealstar
needed to compute in (ℤK/I)*, where I is a modulus in the above sense.
It is a finite abelian group as described above, supplemented by
technical data needed to solve discrete log problems.
Finally we explain how to input ray number fields (or bnr), using class field theory. These are defined by a triple A, B, C, where the defining set [A,B,C] can have any of the following forms: [bnr], [bnr,subgroup], [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 bnfinit, where units are mandatory
unless the modulus is trivial; bnr is as output by bnrinit. This
is the ground field K.
* mod is a modulus 𝔣, 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 bnr.clgp on the
given generators. We also allow a t_INT n for n.Clf.
* 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->zeta3
We could have written directly
? bnrdisc(K, 13);
? bnrdisc(K, 13, [3,1;0,1]);
avoiding one bnrinit, but this would actually be slower since the
bnrinit is called internally anyway. And now twice!
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, 𝔸× its group of id\`eles. Every Grossencharacter
χ : 𝔸×/K× → ℂ×
can be uniquely written χ = χ0 |.|s for some s ∈ ℂ and some character χ0 of the compact group 𝔸×/(K×.ℝ > 0), where |a |= ∏v |av|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
CK(𝔪) = 𝔸×/(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.
* gcharinit(bnf,mod) initializes the structure gc.
The underlying number field and modulus can be accessed using
gc.bnf and gc.mod.
* gc.cyc describes the finite abelian group structure of
gc, the torsion part corresponding to finite order ray class
characters, the exact zeros corresponding to a lattice of infinite order
Grossencharacters, and the approximate zero being a placeholder for the
complex powers of the id\`ele norm.
* A Hecke character of modulus 𝔪 is described as a t_COL of
coordinates corresponding to gc.cyc: all the coordinates are
integers except the last one, which can be an arbitrary complex number, or
omitted instead of 0.
* Hecke Grossencharacters have L-functions and can be given to all
lfun functions as a 2 components vector [gc,chi], see
also Section se:lfungchar.
Let bnr be the number field data output by bnrinit and
H be a square matrix defining a congruence subgroup of the
ray class group corresponding to bnr (the trivial congruence subgroup
if omitted). This function returns, for each character χ of the ray
class group which is trivial on H, the value at s = 1 (or s = 0) of the
abelian L-function attached to χ. For the value at s = 0, the
function returns in fact for each χ a vector [rχ, cχ] where
L(s, χ) = c.sr + O(sr + 1)
near 0.
The argument flag is optional, its binary digits mean 1: compute at s = 0 if unset or s = 1 if set, 2: compute the primitive L-function attached to χ if unset or the L-function with Euler factors at prime ideals dividing the modulus of bnr removed if set (that is LS(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 LS(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
bnrL1(bnr2,0) returns the same answer as bnrL1(bnr,0).
This function will fail with the message
*** bnrL1: overflow in zeta_get_N0 [need too many primes].
if the approximate functional equation requires us to sum too many terms (if the discriminant of K is too large).
The library syntax is GEN bnrL1(GEN bnr, GEN H = NULL, long flag, long prec).
Returns all characters χ on G such that χ(gi) = e(vi), 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 gi. Else the vectors g and v must have the same length, the gi must be elements of G, and each vi is a rational number whose denominator must divide the order of gi in G.
For convenience, the vector of the gi
can be replaced by a matrix whose columns give their discrete logarithm
in G, for instance as given by bnrisprincipal if G is a bnr;
in this particular case, G can be any finite abelian group
given by a vector of elementary divisors.
? 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 GEN bnrchar(GEN G, GEN g, GEN v = NULL).
bnr being as output by bnrinit, returns a relative equation
for the class field corresponding to the congruence group defined by
(bnr,subgp) (the full ray class field if subgp is
omitted). The subgroup can also be a t_INT n,
meaning n.Clf. The function also handles a vector of
subgroup, e.g, from subgrouplist and returns the vector of individual
results in this case.
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 Clf, where n is
fixed, it is advised to directly compute the bnr modulo n to avoid
expensive discrete logarithms:
? 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 GEN bnrclassfield(GEN bnr, GEN subgp = NULL, long flag, long prec).
Let A, B, C define a class field L over a ground field K
(of type [bnr],
[bnr, subgroup],
or [bnf, modulus],
or [bnf, modulus,subgroup],
Section se:CFT); this function returns the relative degree [L:K].
In particular if A is a bnf (with units), and B a modulus, this function returns the corresponding ray class number modulo B. One can input the 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 bnrinit and should be used if only the
ray class number is desired. See bnrclassnolist if you need ray class
numbers for all moduli less than some bound.
The library syntax is GEN bnrclassno0(GEN A, GEN B = NULL, GEN C = NULL).
Also available is
GEN bnrclassno(GEN bnf,GEN f) to compute the ray class number
modulo f.
bnf being as
output by bnfinit, and list being a list of moduli (with units) as
output by ideallist or ideallistarch, outputs the list of the
class numbers of the corresponding ray class groups. To compute a single
class number, bnrclassno is more efficient.
? bnf = bnfinit(x^2 - 2); ? L = ideallist(bnf, 100, 2); ? H = bnrclassnolist(bnf, L); ? H[98] %4 = [1, 3, 1] ? l = L[1][98]; ids = vector(#l, i, l[i].mod[1]) %5 = [[98, 88; 0, 1], [14, 0; 0, 7], [98, 10; 0, 1]]
The weird l[i].mod[1], is the first component of l[i].mod, i.e.
the finite part of the conductor. (This is cosmetic: since by construction
the Archimedean part is trivial, I do not want to see it). This tells us that
the ray class groups modulo the ideals of norm 98 (printed as %5) have
respectively order 1, 3 and 1. Indeed, we may check directly:
? bnrclassno(bnf, ids[2]) %6 = 3
The library syntax is GEN bnrclassnolist(GEN bnf, GEN list).
Given two abelian extensions A = [bnr1, H1] and
B = [bnr2, H2], where bnr1 and bnr2 are two bnr
structures attached to the same base field, return their compositum
as [bnr, H]. The modulus attached to bnr need not be the
conductor of the compositum.
? 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 GEN bnrcompositum(GEN A, GEN B).
Conductor f of the subfield of a ray class field as defined by [A,B,C]
(of type [bnr],
[bnr, subgroup],
[bnf, modulus] or
[bnf, modulus, subgroup],
Section se:CFT)
If flag = 0, returns f.
If flag = 1, returns [f, Clf, H], where Clf is the ray class group modulo f, as a finite abelian group; finally H is the subgroup of Clf defining the extension.
If flag = 2, returns [f, bnr(f), H], as above except Clf is
replaced by a bnr structure, as output by bnrinit(,f), without
generators unless the input contained a bnr with generators.
In place of a subgroup H, this function also accepts a character
chi = (aj), expressed as usual in terms of the generators
bnr.gen: χ(gj) = exp(2iπ aj / dj), where gj has
order dj = bnr.cyc[j]. In which case, the function returns
respectively
If flag = 0, the conductor f of Ker χ.
If flag = 1, [f, Clf, χ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 Clf modulo N-th powers,
where N is any multiple of the exponent of Clf/H. Computing directly the
conductor, then calling bnrinit with optional argument N avoids this
problem.
* 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 bnrinit (modulo N-th powers for
a suitable N!) and finally map original data to the new bnr using
bnrmap.
The library syntax is GEN bnrconductor0(GEN A, GEN B = NULL, GEN C = NULL, long flag).
Also available is GEN bnrconductor(GEN bnr, GEN H, long flag).
This function is obsolete, use bnrconductor.
The library syntax is GEN bnrconductorofchar(GEN bnr, GEN chi).
A, B, C defining a class field L over a ground field K
(of type [bnr],
[bnr, subgroup],
[bnr, character],
[bnf, modulus] or
[bnf, modulus, subgroup],
Section se:CFT), outputs data [N,r1,D] giving the discriminant and
signature of L, depending on the binary digits of flag:
* 1: if this bit is unset, output absolute data related to L/ℚ: N is the absolute degree [L:ℚ], r1 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], r1 is the number of real places of K unramified in L (so that the number of real places of L is equal to r1 times N), and D is the relative discriminant ideal of L/K.
* 2: if this bit is set and if the modulus is not the conductor of L, only return 0.
The library syntax is GEN bnrdisc0(GEN A, GEN B = NULL, GEN C = NULL, long flag).
bnf being as output by bnfinit (with units), computes a
list of discriminants of Abelian extensions of the number field by increasing
modulus norm up to bound bound. The ramified Archimedean places are
given by arch; all possible values are taken if arch is omitted.
The alternative syntax bnrdisclist(bnf,list) is
supported, where list is as output by ideallist or
ideallistarch (with units), in which case arch is disregarded.
The output v is a vector, 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 = 2r1 possible values are taken and a component of w has the form [m, [[d1,r1,D1],..., [dt,rt,Dt]]], where m is the finite part of the conductor as above, and [di,ri,Di] are the invariants of the ray class field of conductor [m,vi], where vi is the i-th Archimedean component, ordered by inverse lexicographic order; so v1 = [0,...,0], v2 = [1,0...,0], etc. Again, we set di = ri = Di = 0 if [m,vi] is not a conductor.
Finally, each prime ideal pr = [p,α,e,f,β] in the prime factorization m is coded as the integer p.n2+(f-1).n+(j-1), where n is the degree of the base field and j is such that
pr = idealprimedec(nf,p)[j].
m can be decoded using bnfdecodemodule.
Note that to compute such data for a single field, either bnrclassno
or bnrdisc are (much) more efficient.
The library syntax is GEN bnrdisclist0(GEN bnf, GEN bound, GEN arch = NULL).
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 bnrgaloismatrix.
The library syntax is GEN bnrgaloisapply(GEN bnr, GEN mat, GEN H).
Return the matrix of the action of the automorphism aut of the base
field bnf.nf on the generators of the ray class field bnr.gen.
The automorphism
aut can be given as a polynomial, an algebraic number, or a vector of
automorphisms and must stabilize the modulus bnr.mod. We also
allow a Galois group as output by galoisinit, in which case a
vector of matrices is returned corresponding to the generators
aut.gen.
Note: This function only makes sense when the ray class field attached to
bnr is Galois, which is not checked.
The generators bnr.gen need not be explicitly computed in the input
bnr, which saves time: the result is well defined in this case also.
? 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 bnrisgalois for further examples.
The library syntax is GEN bnrgaloismatrix(GEN bnr, GEN aut).
When aut is a polynomial or an algebraic number,
GEN bnrautmatrix(GEN bnr, GEN aut) is available.
bnf is as
output by bnfinit (including fundamental units), f is a modulus,
initializes data linked to the ray class group structure corresponding to
this module, a so-called bnr structure. One can input the attached
bid with generators for f instead of the module itself, saving some
time. (As in idealstar, the finite part of the conductor may be given
by a factorization into prime ideals, as produced by idealfactor.)
If the positive integer cycmod is present, only compute the ray class
group modulo cycmod, which may save a lot of time when some maximal
ideals in f have a huge residue field. In applications, we are given
a congruence subgroup H and study the class field attached to
Clf/H. If that finite Abelian group has an exponent which divides
cycmod, then we have changed nothing theoretically, while trivializing
expensive discrete logs in residue fields (since computations can be
made modulo cycmod-th powers). This is useful in bnrclassfield,
for instance when computing p-elementary extensions.
The following member functions are available
on the result: .bnf is the underlying bnf,
.mod the modulus, .bid the bid structure attached to the
modulus; finally, .clgp, .no, .cyc, .gen refer to the
ray class group (as a finite abelian group), its cardinality, its elementary
divisors, its generators (only computed if flag = 1).
The last group of functions are different from the members of the underlying
bnf, which refer to the class group; use bnr.bnf.xxx
to access these, e.g. bnr.bnf.cyc to get the cyclic decomposition
of the class group.
They are also different from the members of the underlying bid, which
refer to (ℤK/f)*; use bnr.bid.xxx to access these,
e.g. bnr.bid.no to get φ(f).
If flag = 0 (default), the generators of the ray class group are not
explicitly computed, which saves time. Hence bnr.gen would
produce an error. Note that implicit generators are still fixed and stored
in the bnr (and guaranteed to be the same for fixed bnf and
bid inputs), in terms of bnr.bnf.gen and bnr.bid.gen.
The computation which is not performed is the expansion of such products
in the ray class group so as to fix eplicit ideal representatives.
If flag = 1, as the default, except that generators are computed.
The library syntax is GEN bnrinitmod(GEN bnf, GEN f, long flag, GEN cycmod = NULL).
Instead of the above hardcoded numerical flags, one should rather use
GEN Buchraymod(GEN bnf, GEN module, long flag, GEN cycmod)
where an omitted cycmod is coded as NULL and flag is an or-ed
combination of nf_GEN (include generators) and nf_INIT (if
omitted, return just the cardinality of the ray class group and its structure),
possibly 0. Or simply
GEN Buchray(GEN bnf, GEN module, long flag)
when cycmod is NULL.
Fast variant of bnrconductor(A,B,C); A, B, C represent
an extension of the base field, given by class field theory
(see Section se:CFT). Outputs 1 if this modulus is the conductor, and 0
otherwise. This is slightly faster than bnrconductor when the
character or subgroup is not primitive.
The library syntax is long bnrisconductor0(GEN A, GEN B = NULL, GEN C = NULL).
Check whether the class field attached to the subgroup H is Galois
over the subfield of bnr.nf fixed by the group gal, which can be
given as output by galoisinit, or as a matrix or a vector of matrices as
output by bnrgaloismatrix, the second option being preferable, since it
saves the recomputation of the matrices. Note: The function assumes that the
ray class field attached to bnr is Galois, which is not checked.
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 bnrgaloismatrix(B,G) is
computed only once.
The library syntax is long bnrisgalois(GEN bnr, GEN gal, GEN H).
Let bnr be the ray class group data output by
bnrinit(,,1) and let x be an ideal in any form, coprime
to the modulus f = bnr.mod. Solves the discrete logarithm problem
in the ray class group, with respect to the generators bnr.gen,
in a way similar to bnfisprincipal. If x is not coprime to the
modulus of bnr the result is undefined. Note that bnr need not
contain the ray class group generators, i.e. it may be created with
bnrinit(,,0); in that case, although bnr.gen is undefined, we
can still fix natural generators for the ray class group (in terms of the
generators in bnr.bnf.gen and bnr.bid.gen) and compute with
respect to them.
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 giei. 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 bnrinit(,0) or bnrinit(,1). But the actual ideal
representatives (implicit if flag = 0, computed and stored in the
bnr if flag = 1) are in general different and this is what
happens here. Indeed, the implicit generators are naturally expressed
in terms of bnr.bnf.gen and bnr.bid.gen and then
expanded and simplified (in the same ideal class) so that we obtain ideal
representatives for bnr.gen which are as simple as possible.
And indeed the quotient of the two α found is 1 modulo the
conductor (and positive at the infinite places it contains), and this is the
only guaranteed property.
Beware that, when bnr is generated using bnrinit(, cycmod), the
results are given in Clf modulo cycmod-th powers:
? 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 GEN bnrisprincipal(GEN bnr, GEN x, long flag).
Instead of hardcoded numerical flags, one should rather use
GEN isprincipalray(GEN bnr, GEN x) for flag = 0, and if you
want generators:
bnrisprincipal(bnr, x, nf_GEN)
Also available is
GEN bnrisprincipalmod(GEN bnr, GEN x, GEN mod, long flag)
that returns the discrete logarithm of x modulo the t_INT
mod; the value mod = NULL is treated as 0 (full discrete
logarithm), and flag = 1 is not allowed if mod is set.
This function has two different uses:
* if A and B are bnr structures for the same bnf attached
to moduli mA and mB with mB | mA, return the canonical surjection
from A to B, i.e. from the ray class group moodulo mA to the ray
class group modulo mB. The map is coded by a triple
[M,cycA,cycB]:
M gives the image of the fixed ray class group generators of A in
terms of the ones in B, cycA and cycB are the cyclic
structures A.cyc and B.cyc respectively. Note that this function
does not need A or B to contain explicit generators for the ray
class groups: they may be created using bnrinit(,0).
If B is only known modulo N-th powers (from bnrinit(,N)), the result
is correct provided N is a multiple of the exponent of A.
* 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 bnrisprincipal) modulo mA whose conductor
divides mB, return the image of the subgroup (resp. the character, the
discrete logarighm) as defined modulo mB. The main use of this variant is
to compute the primitive subgroup or character attached to a bnr modulo
their conductor. This is more efficient than bnrconductor in two
respects: the bnr attached to the conductor need only be computed once
and, most importantly, the ray class group can be computed modulo N-th
powers, where N is a multiple of the exponent of Clm_{A} / H
(resp.
of the order of χ). Whereas bnrconductor is specified to return a
bnr attached to the full ray class group, which may lead to untractable
discrete logarithms in the full ray class group instead of a tiny quotient.
The library syntax is GEN bnrmap(GEN A, GEN B).
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
Cl7 oo _{1 oo 2}(ℚ(sqrt{229})) defined by
χ(g1ag2b)
= ζ12aζ2b. Here g1, g2 are the generators of the
ray-class group given by bnr.gen and ζ1 = e2iπ/N1,
ζ2 = e2iπ/N2 where N1, N2 are the orders of g1
and g2 respectively (N1 = 6 and N2 = 3 as bnr.cyc readily
tells us).
The library syntax is GEN bnrrootnumber(GEN bnr, GEN chi, long flag, long prec).
bnr being as output by bnrinit, finds a relative equation
for the class field corresponding to the modulus in bnr and the given
congruence subgroup (as usual, omit subgroup if you want the whole ray
class group).
The main variable of bnr must not be x, and the ground field and the
class field must be totally real. When the base field is ℚ, the vastly
simpler galoissubcyclo is used instead. Here is an example:
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 bnrstark is allowed to return a vector of
polynomials defining independent relative extensions, whose compositum
is the requested class field. We decided that it was useful to keep the
extra information thus made available, hence the user has to take the
compositum herself, see nfcompositum.
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 bnrclassfield:
? 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 GEN bnrstark(GEN bnr, GEN subgroup = NULL, long prec).
bnr being as output by bnrinit, returns the characteristic
polynomial of the (conjectural) Stark unit corresponding to the modulus in
bnr and the given congruence subgroup (as usual, omit subgroup
if you want the whole ray class group).
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 GEN bnrstarkunit(GEN bnr, GEN subgroup = NULL).
Let G be the group attached to the galoisinit
structure gal, and
let χ be the character of some representation ρ of the group G,
where a polynomial variable is to be interpreted as an o-th root of 1.
For instance, if [T,o] = galoischartable(gal) the characters
χ are input as the columns of T.
Return the degree-1 character detρ as the list of det ρ(g),
where g runs through representatives of the conjugacy classes
in galoisconjclasses(gal), with the same ordering.
? 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 GEN galoischardet(GEN gal, GEN chi, long o).
Let G be the group attached to the galoisinit
structure gal, and
let χ be the character of some representation ρ of the group
G, where a polynomial variable is to be interpreted as an o-th root of
1, e.g., if [T,o] = galoischartable(gal) and χ is a column of
T.
Return the list of characteristic polynomials det(1 - ρ(g)T),
where g runs through representatives of the conjugacy classes
in galoisconjclasses(gal), with the same ordering.
? 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 GEN galoischarpoly(GEN gal, GEN chi, long o).
Compute the character table of G, where G is the underlying group of
the galoisinit structure gal. The input gal is also allowed
to be a t_VEC of permutations that is closed under products.
Let N be the number of conjugacy classes of G.
Return a t_VEC [M,e] where e ≥ 1 is an integer
and M is a square t_MAT of size N giving the character table
of G.
* 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 galoisconjclasses(gal), in particular the
first row corresponds to the identity and gives the dimension χ(1)
of the irreducible representation attached to the successive characters
χ.
The value M[i,j] of the character j at the conjugacy class i
is represented by a polynomial in y whose variable should be
interpreted as an e-th root of unity, i.e. as the lift of
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 Sn. 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 GEN galoischartable(GEN gal).
gal being output by galoisinit,
return the list of conjugacy classes of the underlying group.
The ordering of the classes is consistent with galoischartable
and the trivial class comes first.
? G = galoisinit(x^6+108);
? galoisidentify(G)
%2 = [6, 1] \\ S3
? 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 galoissubgroups:
? subs = galoissubgroups(G); H = subs[5]; ? galoisidentify(H) %2 = [2, 1] \\ Z/2 ? S = galoisconjclasses(subgroups_ofG[5]); ? [[permorder(c[1]),#c] | c <- S ] %4 = [[1,1], [2,1]]
The library syntax is GEN galoisconjclasses(GEN gal).
gal being be a Galois group as output by galoisinit,
export the underlying permutation group as a string suitable
for (no flags or flag = 0) GAP or (flag = 1) Magma. The following example
compute the index of the underlying abstract group in the GAP library:
? G = galoisinit(x^6+108);
? s = galoisexport(G)
%2 = "Group((1, 2, 3)(4, 5, 6), (1, 4)(2, 6)(3, 5))"
? extern("echo \"IdGroup("s");\" | gap -q")
%3 = [6, 1]
? galoisidentify(G)
%4 = [6, 1]
This command also accepts subgroups returned by galoissubgroups.
To import a GAP permutation into gp (for galoissubfields for
instance), the following GAP function may be useful:
PermToGP := function(p, n)
return Permuted([1..n],p);
end;
gap> p:= (1,26)(2,5)(3,17)(4,32)(6,9)(7,11)(8,24)(10,13)(12,15)(14,27)
(16,22)(18,28)(19,20)(21,29)(23,31)(25,30)
gap> PermToGP(p,32);
[ 26, 5, 17, 32, 2, 9, 11, 24, 6, 13, 7, 15, 10, 27, 12, 22, 3, 28, 20, 19,
29, 16, 31, 8, 30, 1, 14, 18, 21, 25, 23, 4 ]
The library syntax is GEN galoisexport(GEN gal, long flag).
gal being be a Galois group as output by galoisinit and
perm an element of gal.group, a vector of such elements
or a subgroup of gal as returned by galoissubgroups,
computes the fixed field of gal by the automorphism defined by the
permutations perm of the roots gal.roots. P is guaranteed to
be squarefree modulo gal.p.
If no flags or flag = 0, output format is the same as for nfsubfield,
returning [P,x] such that P is a polynomial defining the fixed field, and
x is a root of P expressed as a polmod in gal.pol.
If flag = 1 return only the polynomial P.
If flag = 2 return [P,x,F] where P and x are as above and F is the factorization of gal.pol over the field defined by P, where variable v (y by default) stands for a root of P. The priority of v must be less than the priority of the variable of gal.pol (see Section 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 x4+1 = (x2-sqrt{2}x+1)(x2+sqrt{2}x+1)
The library syntax is GEN galoisfixedfield(GEN gal, GEN perm, long flag, long v = -1) where v is a variable number.
Query the galpol package for a group of order a with index b
in the GAP4 Small Group library, by Hans Ulrich Besche, Bettina Eick and
Eamonn O'Brien.
The current version of galpol supports groups of order a ≤ 143.
If b is omitted, return the number of isomorphism classes of
groups of order a.
The library syntax is GEN galoisgetgroup(long a, long b).
Also available is GEN galoisnbpol(long a) when b
is omitted.
Query the galpol package for a string describing the group of order
a with index b in the GAP4 Small Group library, by Hans Ulrich Besche,
Bettina Eick and Eamonn O'Brien.
The strings were generated using the GAP4 function StructureDescription.
The command below outputs the names of all abstract groups of order 12:
? 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 galpol supports groups of order a ≤ 143.
For a ≥ 16, it is possible for different groups to have the same name:
? 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 GEN galoisgetname(long a, long b).
Query the galpol package for a polynomial with Galois group
isomorphic to
GAP4(a,b), totally real if s = 1 (default) and totally complex if s = 2.
The current version of galpol supports groups of order a ≤ 143.
The output is a vector [pol, den] where
* pol is the polynomial of degree a
* den is the denominator of nfgaloisconj(pol).
Pass it as an optional argument to galoisinit or nfgaloisconj to
speed them up:
? [pol,den] = galoisgetpol(64,4,1); ? G = galoisinit(pol); time = 352ms ? galoisinit(pol, den); \\ passing 'den' speeds up the computation time = 264ms ? % == %` %4 = 1 \\ same answer
If b and s are omitted, return the number of isomorphism classes of groups of order a.
The library syntax is GEN galoisgetpol(long a, long b, long s).
Also available is GEN galoisnbpol(long a) when b and s
are omitted.
gal being be a Galois group as output by galoisinit,
output the isomorphism class of the underlying abstract group as a
two-components vector [o,i], where o is the group order, and i is the
group index in the GAP4 Small Group library, by Hans Ulrich Besche, Bettina
Eick and Eamonn O'Brien.
This command also accepts subgroups returned by galoissubgroups.
The current implementation is limited to degree less or equal to 127. Some larger "easy" orders are also supported.
The output is similar to the output of the function IdGroup in GAP4.
Note that GAP4 IdGroup handles all groups of order less than 2000
except 1024, so you can use galoisexport and GAP4 to identify large
Galois groups.
The library syntax is GEN galoisidentify(GEN gal).
Computes the Galois group
and all necessary information for computing the fixed fields of the
Galois extension K/ℚ where K is the number field defined by
pol (monic irreducible polynomial in ℤ[X] or
a number field as output by nfinit). The extension K/ℚ must be
Galois returns 0 otherwise.
The function use either nfisisom or 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 (WSS) if there exists a normal series
{1} = H0 ◃ H1 ◃ ... ◃ Hn-1 ◃ Hn
such that each Hi is normal in G and for i < n, each quotient group
Hi+1/Hi is cyclic, and either Hn = G (then G is super-solvable) or
G/Hn is isomorphic to either A4, S4 or the group
(3 x 3):4 (GAP4(36,9)).
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 galoisxxx routines.
For instance:
P = x^6 + 108; G = galoisinit(P); L = galoissubgroups(G); vector(#L, i, galoisisabelian(L[i],1)) vector(#L, i, galoisidentify(L[i]))
The output is an 8-component vector gal.
gal[1] contains the polynomial pol
(gal.pol).
gal[2] is a three-components vector [p,e,q] where p is a
prime number (gal.p) such that pol totally split
modulo p , e is an integer and q = pe (gal.mod) is the
modulus of the roots in gal.roots.
gal[3] is a vector L containing the p-adic roots of
pol as integers implicitly modulo gal.mod.
(gal.roots).
gal[4] is the inverse of the Vandermonde matrix of the p-adic roots of pol, multiplied by gal[5].
gal[5] is a multiple of the least common denominator of the automorphisms expressed as polynomial in a root of pol.
gal[6] is the Galois group G expressed as a vector of
permutations of L (gal.group).
Assuming the group is weakly super-solvable, the following are available (otherwise both are empty).
gal[7] is a generating subset S = [s1,...,sg] of G
expressed as a vector of permutations of L (gal.gen).
gal[8] contains the relative orders [o1,...,og] of
the generators of S (gal.orders).
Let Hn be as above, we have the following properties:
* if G/Hn ~ A4 then [o1,...,og] ends by [2,2,3].
* if G/Hn ~ S4 then [o1,...,og] ends by [2,2,3,2].
* if G/Hn ~ (3 x 3):4 (GAP4(36,9)) then
[o1,...,og] ends by [3,3,4].
* for 1 ≤ i ≤ g the subgroup of G generated by [s1,...,si] is normal, with the exception of i = g-2 in the A4 and (3 x 3):4 cases and of i = g-3 in the S4 case.
* the relative order oi of si is its order in the
quotient group G/<s1,...,si-1>, with the same
exceptions.
* for any x ∈ G there exists a unique family [e1,...,eg] such that (no exceptions):
-- for 1 ≤ i ≤ g we have 0 ≤ ei < oi
-- x = g1e1g2e2...gnen
If present den must be a suitable value for gal[5].
The library syntax is GEN galoisinit(GEN pol, GEN den = NULL).
gal being as output by galoisinit, return 0 if
gal is not an abelian group, and the HNF matrix of gal over
gal.gen if flag = 0, 1 if flag = 1, and the SNF matrix of gal
if flag = 2.
This command also accepts subgroups returned by galoissubgroups.
The library syntax is GEN galoisisabelian(GEN gal, long flag).
gal being as output by galoisinit, and subgrp a subgroup
of gal as output by galoissubgroups,return 1 if subgrp is a
normal subgroup of gal, else return 0.
This command also accepts subgroups returned by galoissubgroups.
The library syntax is long galoisisnormal(GEN gal, GEN subgrp).
gal being a
Galois group as output by galoisinit and perm a element of
gal.group, return the polynomial defining the Galois
automorphism, as output by nfgaloisconj, attached to the
permutation perm of the roots gal.roots. perm can
also be a vector or matrix, in this case, galoispermtopol is
applied to all components recursively.
Note that
G = galoisinit(pol); galoispermtopol(G, G[6])~
is equivalent to nfgaloisconj(pol), if degree of pol is greater
or equal to 2.
The library syntax is GEN galoispermtopol(GEN gal, GEN perm).
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 nf structure. If d is given, it must be a multiple of
the splitting field degree. The output is compatible with functions expecting
a galoisinit structure.
The library syntax is GEN galoissplittinginit(GEN P, GEN d = NULL).
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ℚ(ζ_{f)/L}(ζf), where f is the smallest integer so that ζn ∈ ℚ(ζf).
The pair (n, H) is deduced from the parameters (N, H) as follows
* N an integer: then n = N; H is a generator, i.e. an integer or an integer modulo n; or a vector of generators.
* N the output of znstar(n) or znstar(n,1).
H as in the first case above, or a matrix, taken to be a HNF left divisor
of the SNF for (ℤ/nℤ)*
(N.cyc), giving the generators of H in terms of N.gen.
* N the output of bnrinit(bnfinit(y), m) where m is a
module. H as in the first case, or a matrix taken to be a HNF left
divisor of the SNF for the ray class group modulo m
(of type N.cyc), giving the generators of H in terms of
N.bid.gen ( = N.gen if N includes generators).
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 galoisinit(pol).
The following function can be used to compute all subfields of
ℚ(ζn) (of exact degree d, if d is set):
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 L = subgrouplist(bnr, IndexBound) would produce subfields of
exact conductor n oo .
The library syntax is GEN galoissubcyclo(GEN N, GEN H = NULL, long flag, long v = -1) where v is a variable number.
Outputs all the subfields of the Galois group G, as a vector.
This works by applying galoisfixedfield to all subgroups. The meaning of
flag is the same as for galoisfixedfield.
The library syntax is GEN galoissubfields(GEN G, long flag, long v = -1) where v is a variable number.
Outputs all the subgroups of the Galois group gal. A subgroup is a
vector [gen, orders], with the same meaning
as for gal.gen and gal.orders. Hence gen is a vector of
permutations generating the subgroup, and orders is the relatives
orders of the generators. The cardinality of a subgroup is the product of the
relative orders. Such subgroup can be used instead of a Galois group in the
following command: galoisisabelian, galoissubgroups,
galoisexport and galoisidentify.
To get the subfield fixed by a subgroup sub of gal, use
galoisfixedfield(gal,sub[1])
The library syntax is GEN galoissubgroups(GEN G).
gc being the structure returned by gcharinit, returns a t_MAT
whose columns form a basis of the subgroup of algebraic Grossencharacters in
gc (Weil type A0). The last component is interpreted as a power of the
norm.
If typ is a t_VEC of length gc.r1+gc.r2,
containing a pair of integers [pτ,qτ] for each complex
embedding τ, returns a t_VEC containing a character whose infinity type
at τ is
z ⟼ z-pτz-qτ
if such a character exists, or empty otherwise.
The full set of characters of that infinity type is obtained by multiplying by
the group of finite order characters.
? 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 forvec.
? 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 GEN gcharalgebraic(GEN gc, GEN typ = NULL).
Returns the conductor of chi, as a modulus over gc.bnf. This is
the minimum modulus 𝔪 such that
U(𝔪) ⊂ ker(chi)
indicating the exact ramification of chi.
* 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 χ𝔭 (Ue) = 1 where U0 = ℤ𝔭× and Ui = 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 GEN gchar_conductor(GEN gc, GEN chi).
Returns internal logarithm vector of character chi
as a t_VEC in ℝn, so that for all x,
gchareval(gc,chi,x,0) is equal to
gcharduallog(gc,chi) * gcharlog(gc,x) in
ℝ/ ℤ.
The components are organized as follows:
* the first ns components are in ℝ and describe the character on
the class group generators: θ encodes 𝔭 ⟼
exp(2iπθ),
* the next nc components are in ℝ and describe the idealstar
group character via its image on generators: θ encodes the
image exp(2iπθ),
* the next r1+r2 components are in ℝ and correspond to characters
of ℝ for each infinite place: ϕ encodes x ⟼ |x|iϕ in
the real case and z ⟼ |z|2iϕ in the complex case,
* the last r2 components are in ℤ and correspond to characters of
ℝ/ℤ for each complex place: k encodes z ⟼ (z/|z|)k.
* the last component s is in ℂ and corresponds to a power |.|s of the adélic norm.
See also gcharlog.
? 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 GEN gcharduallog(GEN gc, GEN chi).
gc being the structure returned by gcharinit, chi a
character in gc, and x an ideal of the base field, returns the
value χ(x). If flag = 1 (default), returns a value in ℂ×;
if flag = 0, returns a value in ℂ/ℤ, normalized so that the real part is
between -1/2 and 1/2.
? 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 GEN gchareval(GEN gc, GEN chi, GEN x, long flag).
gc being a Grossencharacter group as output by gcharinit, Lv
being t_VEC of places v encoded by a t_INT (infinite place) or a prime
ideal structure representing a prime not dividing the modulus of gc (finite
place), and Lchiv being a t_VEC of local characters χv encoded
by [k,ϕ] with k a t_INT and ϕ a t_REAL or
t_COMPLEX representing x ⟼ sign(x)k|x|iϕ (real
place) or z ⟼ (z/|z|)k|z|2iϕ(complex place) or by a t_REAL
or t_COMPLEX θ representing 𝔭 ⟼ exp(2iπ θ)
(finite place), returns a Grossencharacter ψ belonging to g such
that ψv ~ χv for all v.
At finite places, in place of a scalar one can provide a t_VEC whose
last component is θ, as output by gcharlocal.
To ensure proper identification, it is recommended to provide all infinite
places together with a set of primes that generate the ray class group of
modulus gc.mod.
? 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 GEN gchar_identify(GEN gc, GEN Lv, GEN Lchiv, long prec).
bnf being a number field output by bnfinit (including
fundamental units), f a modulus, initializes a structure (gc)
describing the group of Hecke Grossencharacters of modulus f.
(As in idealstar, the finite part of the conductor may be given
by a factorization into prime ideals, as produced by idealfactor.)
The following member functions are available
on the result: .bnf is the underlying bnf,
.mod the modulus, .cyc its elementary divisors.
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 ⟼ exp(2iπ v.{ℒ(a)}).
See gcharlog for more details on the map ℒ.
? 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 is a row vector with 11 components:
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.bnf).
gc[3] contains the underlying number field nf
(gc.nf), possibly stored at higher precision than bnf.
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 [Sunits,m], where Sunits describes
the S-units of bnf and m is a relation matrix for internal usage.
gc[8] is
[Vecsmall([evalprec,prec,nfprec]), Vecsmall([ntors,nfree,nalg])]
caching precisions and various dimensions.
gc[9] is a vector describing gc as a ℤ-module
via its SNF invariants (gc.cyc), the last component
representing the norm character.
gc[10] is a vector [R,U,Ui] allowing to convert characters
from SNF basis to internal combination of generators.
Specifically, a character chi in SNF basis has coordinates
chi*Ui in internal basis (the rows of gc[1]).
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 GEN gcharinit(GEN bnf, GEN f, long prec).
gc being the structure returned by gcharinit and chi
a character on gc, returns 1 if and only if chi is an algebraic
(Weil type A0) character, so that its infinity type at every complex
embedding τ can be written
z ⟼ z-pτz-qτ
for some pair of integers (pτ,qτ).
If typ is given, it is set to the t_VEC of exponents
[pτ,qτ].
? 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 int gcharisalgebraic(GEN gc, GEN chi, GEN *typ = NULL).
gc being a gchar structure initialised by gcharinit, returns
the local component χv, where v is either an integer between 1
and r1+r2 encoding an infinite place, or a prime ideal structure
encoding a finite place.
* if v is a real place, χv(x) = 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.mod,
χv(πv) = exp(2iπ θ) is encoded as [θ];
* if v = 𝔭 is a finite place dividing gc.mod,
we can define a bid structure attached to the multiplicative group
G = (ℤK/𝔭k)*, where 𝔭k divides exactly
gc.mod (see idealstar).
Then χv is encoded as [c1,...,cn,θ]
where [c1,...,cn] defines a character on G
(see gchareval) and χv(πv) = exp(2iπ θ).
This bid structure only depends on gc and v
(and not on the character χ);
it can be recovered through the optional argument BID.
? 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 GEN gcharlocal(GEN gc, GEN chi, GEN v, long prec, GEN *BID = NULL).
Returns the internal (logarithmic) representation of the ideal x suitable
for computations in gc, as a t_COL in ℝn.
Its n = ns+nc+(r1+r2)+r2+1 components correspond to a
logarithm map on the group of fractional ideals ℒ: I → ℝn, see
gcharinit.
More precisely, let x = (α) ∏ 𝔭iai a
principalization of x on a set S of primes generating
the class group (see bnfisprincipal),
then the logarithm of x is the t_COL
ℒ(x) = [ (ai), logf(α), (log|x/α|τ)/(2π), (arg(x/α)τ)/(2π), (log N(x))/(2π).i ]
where
* the exponent vector (ai) has ns components, where
ns = #S is the number of prime ideals used to generate the class group,
* logf(α) is a discrete logarithm of
α in the idealstar group (ℤK/f)×,
with nc components,
* log|x/α|τ has r1+r2 components, one for each real embedding and pair of complex embeddings τ: K → ℂ (and |z|τ = |z|2 for complex τ).
* arg{(x/α)τ} has r2 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 GEN gcharlog(GEN gc, GEN x, long prec).
gc being a Grossencharacter group output by gcharinit,
recomputes its archimedean components ensuring accurate computations to
current precision.
It is advisable to increase the precision before computing several values at large ideals.
The library syntax is GEN gcharnewprec(GEN gc, long prec).
'x})
Given nf a number field in nf or bnf format,
a t_VEC Lpr of primes of nf and a t_VEC Ld of
positive integers of the same length, a t_VECSMALL pl of length
r1 the number of real places of nf, computes a polynomial with
coefficients in nf defining a cyclic extension of nf of
minimal degree satisfying certain local conditions:
* 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 rnfkummer restrictions.
When nf is ℚ, prime integers are accepted instead of prid
structures. However, their primality is not checked and the behavior is
undefined if you provide a composite number.
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 GEN nfgrunwaldwang(GEN nf, GEN Lpr, GEN Ld, GEN pl, long v = -1) where v is a variable number.
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: C2 = 2T1;
* degree 3: C3 = 3T1 and S3 = 3T2;
* degree 4: C4 = 4T1, V4 = 4T2, D4 = 4T3, A4 = 4T4 and S4 = 4T5;
* degree 5: C5 = 5T1, D5 = 5T2, F5 = M20 = 5T3 and A5 = 5T4;
* degree 6: C6 = 6T1, S3(6) = D6(6) = 6T2, D6(12) = 6T3, A4(6) = 6T4, S3 x C3 = 6T5, A4(6) x C2 = 6T6, S4(6)+ = 6T7, S4(6)− = 6T8, S32 = 6T9, C32:C4 = 6T10, S4(6) x C2 = 6T11, A5(6) = PSL2(5) = 6T12 and C32:D4 = 6T13;
* degree 7: C7 = 7T1, D7 = 7T2, M21 = 7T3 and M42 = 7T4;
* degree 9: C9 = 9T1, C3 x C3 = 9T2 and D9 = 9T3;
* degree ℓ with ℓ prime: Cℓ = ℓ T1 and Dℓ = ℓ T2.
* degree n = pq with p and q distinct primes: Cn = nT1.
The groups A5 and A5(6) require the optional package
nflistdata.
In addition, if N is a polynomial, all transitive subgroups of Sn with n ≤ 15, as well as alternating groups An and the full symmetric group Sn for all n (see below for details and explanations).
The groups are coded as [n,k] using the nTk format where n is the
degree and k is the T-number, the index in the classification of
transitive subgroups of Sn.
Alternatively, the groups Cn, Dn, An, Sn,
V4, F5 = M20, M21 and M42 can be input as
character strings exactly as written, lifting subscripts; for instance
"S4" or "M21". If the group is not recognized or is
unsupported the function raises an exception.
The number fields are computed on the fly (and not from a preexisting table)
using a variety of algorithms, with the exception of A5 and A5(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 bnfinit, all results depend on the GRH in
degree n > 3.
To avoid wasting time, the output polynomials defining the number fields are
usually not the simplest possible, use polredbest or polredabs
to reduce them.
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
S3, Dℓ, A4, S4, F5, M21 and M42,
as a resolvent field (see also the function nfresolvent for these cases).
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
Sn with n ≤ 15 as well as for the alternating and symmetric groups
An and Sn for all n.
Polynomials for An 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
An and Sn, subgroups of Sn for n > 7 require the optional
nflistdata package.
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.
* Cn: O(b1/φ(n)) for n = 2, 4, 6, 9 or any odd prime, and for n = pq with p, q distinct primes;
* Dn: O(b2/φ(n)) for n = 4 or any odd prime;
* V4, A4: O(b1/2), S4: O(b); N.B. The subexponential terms are expensive for A4 and S4.
* M20: O(b).
* S4(6)−, S4(6)+ A4(6) x C2, S3 x S3, S4(6) x C2 : O(b), D6(12), A4(6), S3(6), S3 x C3, C32:C4: O(b1/2).
* M21, M42: O(b).
* C3 x C3: O(b1/3), D9: O(b5/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, "2A4(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,
and "Cn"=[n,1] when n is a product of two distinct primes.
? nflist("S25", 't)
%13 = x^25 + x*t + 1
The library syntax is GEN nflist(GEN G, GEN N = NULL, long s, GEN F = NULL).
Let pol be an irreducible integral polynomial defining a number
field K with Galois closure ~{K}. This function is limited to the
Galois groups supported by nflist; in the following ℓ denotes an
odd prime. If Gal(~{K}/ℚ) is Dℓ, A4, S4,
F5 (M20), A5, M21 or M42,
returns a polynomial R defining the corresponding resolvent field (quadratic
for Dℓ, cyclic cubic for A4 and M21, noncyclic cubic for
S4, cyclic quartic for F5, A5(6) sextic for A5, and cyclic
sextic for M42). In the A5(6) case, returns the A5 field of
which it is the resolvent. Otherwise, gives a "canonical" subfield, or 0
if the Galois group is not supported.
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 nfdisc(R):
* In cases Cℓ, Dℓ, A4, or S4, disc(K) = (Df2)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 the case Cpq with p and q primes with p < q, the conductor of the degree q subfield.
* In case F5, disc(K) = Df4 if f > 0 or 52Df4 if f < 0.
* In cases M21 or M42, disc(K) = Dmf6 if f > 0 or 73Dmf6 if f < 0, where m = 2 for M21 and m = 1 for M42.
* In cases A5 and A5(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 D6 ? 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 GEN nfresolvent(GEN pol, long flag).
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 fH encodes F and the data [f,H] as follows:
* fH = [f, H], where H is given by a vector of
integral generators,
* fH = [bnr, H], where bnr is attached to
Clf(ℚ) and H is a congruence subgroup,
* fH = [G, H], where G is idealstar(f,1), and H is
a subgroup of (ℤ/fℤ)×,
* fH = f, where we assume that H = {1}, i.e., F =
ℚ(ζf),
* 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 ⊂ FNℚ(ζ_{d)/ℚ} l(-B1,χ/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 B1,χ = (1/fχ)∑a = 1fχ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 = pa with a prime number p, then Q = 1.
* If F = ℚ(ζf), then Q = 1 if and only if f = pa.
* If f = 4pa or paqb 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 subcyclohminus outputs the valuation at p of
h−(F), in other words the maximal integer e such that
pe|h−(F) by evaluating p-adic valuations of Bernoulli numbers.
Since p is odd and Q ∈ {1,2}, the latter can be disregarded and
the result is the same as valuation(subcyclohminus(f,H)[1], p), but
adding this argument p can be much faster when p does not divide [F:ℚ]
or if a high power of p divides [F:ℚ].
? [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 10141 divides h−(ℚ(ζ22220)) exactly. Let kn be the n-th layer of the cyclotomic ℤ3-extension of k = ℚ(sqrt{-1501391}); the following computes en for 1 ≤ n ≤ 3, where 3en is the 3-part of the relative class number h−(kn):
? 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+(kn) 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.38.
? 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 GEN subcyclohminus(GEN fH, GEN p = NULL).
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 Fn 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 Fn.
The function is only implemented when p, n and f are relatively small:
all of p4, pn+1 and f must fit into an unsigned long integer.
The argument fH encodes the data [f,H] as follows:
* fH = [f, H], where H is given by a vector of
integral generators,
* fH = [bnr, H], where bnr is attached to
Clf(ℚ) and H is a congruence subgroup,
* fH = [G, H], where G is idealstar(f,1), and H is
a subgroup of (ℤ/fℤ)×,
* fH = f, where we assume that H = {1}, i.e., F =
ℚ(ζf),
* 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 Kn 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/ℚ) ⟶ ℚp×. Let
Σn =
Gal(Kn/K), which is cyclic generated by the Frobenius automorphism
σ; we write Kχ = ℚp(χ),
𝒪χ = ℤp[χ] with maximal ideal 𝔭.
The Stickelberger element
ξnχ belongs to 𝒪χ[Σn];
the polynomial fnχ(x) ∈ 𝒪χ[x]
is constructed from ξnχ by the correspondence
σ ⟼ 1+x. If n is sufficiently large, then
𝔭 does not divide fnχ(x) and the distinguished polynomial
gnχ(x) ∈ 𝒪χ[x] is uniquely determined by the relation
fnχ(x) = u(x)gnχ(x),u(x) ∈ 𝒪χ[x]×.
Owing to Iwasawa Main Conjecture proved by Mazur-Wiles, we can define
the Iwasawa polynomial
gχ(x) = limn ⟶ oo gnχ(x) ∈ 𝒪χ[x].
If r is the smallest integer satisfying
deg gnχ ≤ pr, then we have
gχ(x) = gnχ(x) (mod 𝔭n+1-r) .
Applying the norm from Kχ down to ℚp, we obtain polynomials
Gχ(x), Gnχ(x) ∈ ℤp[x] satisfying the congruence
Gχ(x) = Gnχ(x) (mod pn+1-r) .
Note that λp−(F) = ∑K,χ deg Gχ(x) is the Iwasawa
λ−-invariant of F, while the μ-invariant μp(F) is
known to be zero by the theorem of Ferrero-Washington.
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 Gnχ(x) mod {pn+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 G4χ(x) mod {p4} 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 p4.
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
[λ, ν, [e0,...,ek]], where λ = λp−(F),
pen denotes the p-part of the class number of Fn and en =
λ 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 en - en-1 < ϕ(pn) for some n ≥ 1, we have
λp(F) = en-en-1;
if χ(p) = 1 we can weaken the hypothesis to en-en-1 ≤
ϕ(pn) for some n ≥ 1 and obtain the same conclusion.
To compute en - en-1 we use Bernoulli numbers
(subcyclohminus) if
χ(p) = 0 and a much faster algorithm of Gold
(Pacific J. Math. vol.40 (1972), pp.83–88) otherwise.
* For p = 2, we use Kida's formula (Tohoku Math. J. vol. 31 (1979), pp. 91–96) and only return [λ−].
When d > 1, subcycloiwasawa should calculate
λp(F) = λp+(F), which is conjectured to be zero.
But this is not yet implemented.
? 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 en = n for all n ≥ 0. And at p = 11, we have en = 0 for all n ≥ 0.
? subcycloiwasawa(x^2+1501391, 3) time = 23 ms. %4 = [14, -16, [2, 5]]
computes en by Gold's algorithm for F = ℚ(sqrt{-1501391}). This shows that at p = 3, we have λ = 14, ν = -16, then e0 = 2, e1 = 5, and en = 14n-16 for n ≥ 2.
? subcycloiwasawa(x^2+956238, 3) time = 141 ms. %5 = [14, -19, [1, 3]]
computes en using Bernoulli numbers for F = ℚ(sqrt{-956238}). This shows that e0 = 1, e1 = 3 and en = 14n-19 for n ≥ 2.
Algorithm and output for n > 0; F = ℚ(sqrt{d}).
* When d < 0 and n ≥ 1,
subcycloiwasawa computes the Stickelberger element
ξn = ξnχ ∈ ℤp[Σn] and the Iwasawa polynomial
g(x) = gχ(x) ∈ ℤp[x]
from the n-th layer Fn of the cyclotomic ℤp-extension of F.
Let q be p (p odd) or 4 (p = 2) and let
q0 be the lcm of q and the discriminant d of F, and let
qn = q0pn.
Then Σn = Gal(ℚn/ℚ) = Gal(Fn/F)
= ⟨s>,
where s is the Frobenius automorphism (ℚn/ℚ,1+q0) and
ξn = qn-1∑a = 1, (a,q_{n) = 1}qn
aχ(a)-1(ℚn/ℚ,a)-1
is an element of ℚ[Σn].
For (p,d) = (2,-1),(2,-2),(2,-3), (2,-6),(3,-3),
we know that λp(F) = 0 and there is nothing to do.
For the other cases, it is proved that (1/2)ξn ∈ ℤp[Σn].
The polynomial fn(x) ∈ ℤp[x] is constructed from (1/2)ξn
by the
correspondence s ⟼ 1+x. If n is sufficiently large, then
p does not divide fn(x) and the distinguished polynomial
gn(x) ∈ ℤp[x] is uniquely determined by the relation
fn(x) = u(x)gn(x), u(x) ∈ ℤp[[x]]×. The Iwasawa polynomial
g(x) is defined by g(x) = limn ⟶ oo gn(x); if r is the
smallest integer satisfying deg g = λp(F) ≤ pr, then we have
g(x) = gn(x) (mod pn+1-r) when p > 2 and modulo 2n-r
otherwise.
Conjecturally, we have further
1. case q0 = 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 outputs [g] where
g is gn(x) mod {pn+1-r} (p odd) or mod {2n-r} (p = 2).
? 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 {39}. 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
fn*(x) ∈ ℤp[x] from (1/2)ξn* by the correspondence
s-1 ⟼ (1+x)(1+q0)-1 and define the distinguished
polynomial gn*(x) ∈ ℤp[x] using fn*(x).
Then g*(x) = limn ⟶ oo gn*(x) is the Iwasawa
polynomial, which has a connection with Greenberg conjecture for F.
Let r be the smallest integer satisfying deg g* ≤ pr,
then we have g*(x) = gn*(x) (mod pn+1-r)
when p > 2 and g*(x) = gn*(x) (mod 2n-r) when p = 2.
Finally, subcycloiwasawa outputs [g*] where
g* is gn*(x) mod {pn+1-r} (p odd) or mod {2n-r} (p = 2).
? 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 {217} (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 GEN subcycloiwasawa(GEN fH, GEN p, long n).
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 AF of the ideal class group using an unconditional algorithm of M. Aoki and T. Fukuda (LNCS. vol.4076, pp.56–71, 2006).
The argument fH encodes the data [f,H] as follows:
* fH = [f, H], where H is given by a vector of
integral generators,
* fH = [bnr, H], where bnr is attached to
Clf(ℚ) and H is a congruence subgroup,
* fH = [G, H], where G is idealstar(f,1), and H is
a subgroup of (ℤ/fℤ)×,
* fH = f, where we assume that H = {1}, i.e., F =
ℚ(ζf),
* 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, [e1,...,ek]] with E = ∑i ei, meaning that the order of AF+ is pE and its cyclic structure is ℤ/pe1ℤ x...ℤ/pekℤ
v[3] similarly describes the order and the structure of AF−.
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/ℚ) ⟶ ℚp×.
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 AF is the direct sum of AF+ and AF−; each of AF+ and AF− is decomposed into χ-parts Aχ. By default, the function computes only |AF−| and an upper bound for |AF+| (expected to be equal to |AF+|) separately with different algorithms. This is expected to be fast. The behavior is controled by the binary digits of flag:
1: if |AF+| or |AF−| is computed, also determines its group structure and guarantees informations about AF+. This last part is usually costly.
2: do not compute quantities related to AF+ (the corresponding (ei) in v[2] is replaced with a dummy empty vector).
4: do not compute quantities related to AF− (the corresponding (ei) 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 ℚ(pk) be the k-th layer of the cyclotomic ℤp-extension of ℚ and define ℚ(n) = ℚ(p1e1)...ℚ(prer) when n factors as n = p1e1...prer, 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 |AF−| and a rigorous upper bound of |AF+| which is expected to be equal to |AF+|; of course, when the upper bound is 0, we know for sure that AF+ is trivial. With flag = 1 we obtain the group structure of AF completely and guarantee the informations about AF+ (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 AF of the ideal class group of
F = ℚ(ζ22220).
The output says that AF+ = 0, which is rigorous (since trivial),
and |AF− |= 10141, more precisely AF− is isomorphic to
(ℤ/101ℤ)41 which is also rigorous
(since the description of AF− 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/ℚ) ⟶ ℚ101×.
? subcyclopclgp(22220, 11) time = 83 ms. %2 = [11, [2, [1, 1]], [16, []], [100, 20, 2, 2], 479, 1799]
This computes the 11-part AF for the same F. The result says that |AF+ |= 112, AF+ is isomorphic to (ℤ/11ℤ)2 which is not rigorous and is only an upper bound, and |AF− |= 1116 which is rigorous. The group structure of AF− 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 AF+ is isomorphic to (ℤ/11ℤ)2 and determines that AF− is isomorphic to ℤ/112ℤ⨁ (ℤ/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 AF+ is isomorphic to ℤ/5ℤ and AF− is isomorphic to ℤ/53ℤ⨁ ℤ/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 GEN subcyclopclgp(GEN fH, GEN p, long flag).