-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy pathGaloisGroup_SinglyRamified.mag
163 lines (155 loc) · 5.98 KB
/
GaloisGroup_SinglyRamified.mag
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
import "Utils.mag": factorization, is_eisenstein, Z, Q;
declare type PGGAlg_GaloisGroup_SinglyRamified: PGGAlg_GaloisGroup;
intrinsic PGGAlg_GaloisGroup_SinglyRamified_Make() -> PGGAlg_GaloisGroup_SinglyRamified
{A direct algorithm for singly ramified extensions.}
alg := New(PGGAlg_GaloisGroup_SinglyRamified);
return alg;
end intrinsic;
intrinsic Print(alg :: PGGAlg_GaloisGroup_SinglyRamified)
{Print.}
printf "singly ramified";
end intrinsic;
// some example polynomials to try this on:
// Example 9.* from Greve, Pauli "On ramification polygons..."
// Example 3.24 from Milstead "Computing Galois groups..." (thesis)
intrinsic TryGaloisGroup(alg :: PGGAlg_GaloisGroup_SinglyRamified, f :: PGGPolStd) -> BoolElt, GrpPerm
{The Galois group of f.}
xf := Actual(f : FixPr);
// check f is irreducible and find the extension it defines
d := Degree(xf);
facs, certs := factorization(xf : Extensions);
if #facs ne 1 then
return false, "f must be irreducible";
end if;
K := BaseRing(xf);
cert := certs[1];
L := cert`Extension;
assert Degree(L, K) eq d;
assert cert`E * cert`F eq d;
// special case: unramified
if cert`E eq 1 then
return true, CyclicGroup(GrpPerm, cert`F);
elif cert`F ne 1 then
return false, "f must define a singly ramified extension";
end if;
// special case: totally tamely ramified
p := Prime(K);
Qp := PrimeField(K);
q := p^InertiaDegree(K, Qp);
if not IsDivisibleBy(d, p) then
// the inertia degree of the Galois closure, i.e. the degree of K(zeta_d)/K
F := Min([F : F in [1..d] | IsDivisibleBy(q^F-1, d)]);
S := SymmetricGroup(d);
gen1 := S![(i mod d)+1 : i in [1..d]];
gen2 := S![(((i-1)*q) mod d) + 1 : i in [1..d]];
return true, sub<S | gen1, gen2>;
end if;
// check we are totally wildly ramified
ok, m := IsPowerOf(d, p);
if not ok then
return false, "f must define a singly ramified extension";
end if;
// compute the ramification polynomial and polygon
phi := DefiningPolynomial(L);
assert BaseRing(phi) eq K;
assert is_eisenstein(phi);
x := PolynomialRing(L).1;
pi := L.1;
assert IsWeaklyZero(Evaluate(phi, pi));
r := Evaluate(phi, x+pi) div x;
assert Degree(r) eq d-1;
rp := NewtonPolygon([<i,Valuation(Coefficient(r, i))> : i in [0..d-1]] : Faces:="Lower");
vs := ChangeUniverse(Vertices(rp), car<Z,Z>);
assert vs[1][1] eq 0;
assert vs[#vs][1] eq d-1;
assert forall{v : v in vs | not IsWeaklyZero(Coefficient(r, v[1]))};
assert forall{v : v in vs | IsPowerOf(v[1]+1, p)};
if #vs ne 2 then
return false, "f must define a singly ramified extension";
end if;
// now compute the galois group
// this is an implementation of Algorithm 3.23 of Milstead's thesis.
// we try to keep the notation and step numbers of the description
// step 1
slope := (vs[2][2] - vs[1][2])/(vs[2][1] - vs[1][1]);
h := Numerator(-slope);
e := Denominator(-slope);
ok, d0 := IsDivisibleBy(d-1, e);
assert ok;
// step 2
Fq, LtoFq:=ResidueClassField(Integers(L));
assert #Fq eq q;
A := Polynomial([ShiftValuation(Coefficient(r, i*e), i*h - vs[1][2]) @ LtoFq : i in [0..d0]]);
assert Degree(A) eq d0;
assert Coefficient(A, 0) ne 0;
assert Coefficient(A, d0) ne 0;
// steps 3 and 4 and 6
FqF := SplittingField(A * (Parent(A).1^e - 1));
zeta := PrimitiveElement(FqF);
F := Degree(FqF, Fq);
assert #FqF eq q^F;
// step 5
g, a, a2 := XGCD(e, -p^m);
assert g eq 1;
g, b, b2 := XGCD(h, -e);
assert g eq 1;
// step 7
us := [x[1] : x in Roots(ChangeRing(A, FqF))];
assert #us eq d0;
// steps 8 and 9
r := Log(zeta, us[1]^b) mod e;
// steps 10 and 11 (V is the additive group of FqF)
V, FqFtoV := VectorSpace(FqF, GF(p));
generators := [V | FqFtoV(0)];
M := sub<V | generators>;
assert #M eq 1;
assert Dimension(M) eq 0;
for i in [1..d0] do
roots := [x[1] : x in Roots(PolynomialRing(FqF).1^e - us[i]/zeta^(r*h))];
assert #roots eq e;
generators cat:= [V | FqFtoV(a*x) : x in roots];
M := sub<V | generators>;
assert #M eq p^Dimension(M);
// if #M eq p^m then
// break;
// end if;
end for;
assert #M eq p^m;
assert Dimension(M) eq m;
// step 12
assert BaseField(M) eq GF(p);
B := Basis(M);
assert #B eq m;
assert Universe(B) eq M;
// step 13
ok, ell := IsDivisibleBy(q^F-1, e);
assert ok;
ok, k := IsDivisibleBy(r*(q-1), e);
assert ok;
// steps 14, 15, 16, 17
// the following line works around a bug in Magma: it refuses to compute AGL(GrpMat,1,GF(p))
AGLmp := m eq 1 select sub<G | [G| [[M[1,1], 0],[0,1]] : M in Generators(GL(1,GF(p)))] cat [G![[1,0],[1,1]]]> where G:=GL(2,GF(p)) else AGL(GrpMat, m, GF(p));
S := AGLmp ! ([Coordinates(M, b2) cat [0] where b2 := M ! ((zeta^j2) @ FqFtoV) where j2 := ell*h+j where j := Log(zeta, (V ! b) @@ FqFtoV) : b in B] cat [[i eq m+1 select 1 else 0 : i in [1..m+1]]]);
T := AGLmp ! ([Coordinates(M, b2) cat [0] where b2 := M ! ((zeta^j2) @ FqFtoV) where j2 := k*h+q*j where j := Log(zeta, (V ! b) @@ FqFtoV) : b in B] cat [[i eq m+1 select 1 else 0 : i in [1..m+1]]]);
// print S, T, GroupName(sub<AGLmp | [S, T]>);
// step 18
G := sub<AGLmp | [S, T] cat [AGLmp | [[i eq j select 1 else i eq m+1 and j eq a select 1 else 0 : j in [1..m+1]] : i in [1..m+1]] : a in [1..m]]>;
// convert G to a permutation group
Gperm := OrbitImage(G, {@ Vector([x : x in v]) : v in CartesianProduct([[x : x in GF(p)] : i in [1..m]] cat [[GF(p) ! 1]]) @});
return true, Gperm;
end intrinsic;
intrinsic TryGaloisGroup(alg :: PGGAlg_GaloisGroup_SinglyRamified, f :: PGGPolGrp) -> BoolElt, GrpPerm
{The Galois group of f.}
if not IsIrreducible(f) then
return false, "f must be irreducible";
end if;
F := BaseRing(f);
E := Extension(f);
R := RamificationTower(E, F);
assert #R ge 1;
if #R gt 2 then
return false, "f must define a singly ramified extension";
end if;
G := GaloisGroup(f);
return true, G;
end intrinsic;