aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorSebastiano Tronto <sebastiano.tronto@gmail.com>2019-09-17 10:26:45 +0200
committerSebastiano Tronto <sebastiano.tronto@gmail.com>2019-09-17 10:26:45 +0200
commit31f855d9a13e237e81c46d1c363a9c74e443af43 (patch)
tree7109aef94eb795e144c3163f7e20f3c16af00868
parentcc3732bc883f7c64685b8b474d143e402b8d8ce0 (diff)
downloadkummer-degrees-31f855d9a13e237e81c46d1c363a9c74e443af43.tar.gz
kummer-degrees-31f855d9a13e237e81c46d1c363a9c74e443af43.zip
Removed some commented code, changed README.md
-rw-r--r--README.md34
-rw-r--r--kummer_degree.sage236
2 files changed, 108 insertions, 162 deletions
diff --git a/README.md b/README.md
index 94ad39d..5fbdb34 100644
--- a/README.md
+++ b/README.md
@@ -9,39 +9,29 @@ Outputs the description of the failure of maximality for all possible values of
9Example: 9Example:
10 10
11``` 11```
12
12sage: TotalKummerFailure([-36,12,-1]) 13sage: TotalKummerFailure([-36,12,-1])
13M_0 = 24 14M_0 = 24
14N_0 = 8 15N_0 = 8
15 16
16The following table shows the total failure of Kummer degrees in 17The following table shows the total failure of Kummer degrees in case the quotient M/N is EVEN.
17 case the quotient M/N is EVEN. 18The degree of the Kummer extension (M,N) is e / f, where e = phi(M)*N^rank(G) if N is odd and e = 2*phi(M)*N^rank(G) if N is even and f is the entry of the table below at the row labelled with gcd(N,N0) and the column labelled with gcd(M,M0).
18Columns correspond to values of M, rows to values of N
19
20The degree of the Kummer extension (M,N) can be extracted by taking
21the value f (failure) of the entry at (gcd(N,N0),gcd(M,M0)) and
22simply computing ed(M,N) / f, where ed(M,N) is the expected degree
23of the Kummer extension.
24In this case (-1 is in G), we have ed(M,N) = 2^e*phi(M)*N^r,
25where e=1 if N is even and e=0 if N is odd.
26where r is the rank of G.
27 19
28 | 1 2 3 4 6 8 12 24 20 | 1 2 3 4 6 8 12 24
29 - - - - - - - - - - 21 - - - - - - - - - -
30 1 | 1 1 1 1 1 1 1 1 22 1 | 1 1 1 1 1 1 1 1
31 2 | 4 4 4 4 4 4 8 8 23 2 | 4 4 4 4 4 4 8 8
32 4 | 4 4 4 4 4 8 8 16 24 4 | 4 4 4 4 4 8 8 16
33 8 | 8 8 8 8 8 16 16 32 25 8 | 8 8 8 8 8 8 8 16
34 26
35The following table shows the total failure of Kummer degrees in 27The following table shows the total failure of Kummer degrees if the quotient M/N is ODD and is read as the previous one.
36case the quotient M/N is ODD.
37This table can be read exactly as the first one.
38 28
39 | 1 2 3 4 6 8 12 24 29 | 1 2 3 4 6 8 12 24
40 - - - - - - - - - - 30 - - - - - - - - - -
41 1 | 1 1 1 1 1 1 1 1 31 1 | 1 1 1 1 1 1 1 1
42 2 | 2 2 2 2 4 2 4 4 32 2 | 2 2 2 2 4 2 4 4
43 4 | 2 2 2 4 4 4 8 8 33 4 | 2 2 2 4 4 4 8 8
44 8 | 4 4 4 8 8 8 16 16 34 8 | 4 4 4 4 4 4 8 8
45 35
46``` 36```
47 37
@@ -52,5 +42,5 @@ Returns the degree of the Kummer extension Q_{M,N}. Again, G is given simply as
52Example: 42Example:
53``` 43```
54sage: KummerDegree([-36,12,-1],120,24) 44sage: KummerDegree([-36,12,-1],120,24)
552304 454608
56``` 46```
diff --git a/kummer_degree.sage b/kummer_degree.sage
index 29e6852..2b03716 100644
--- a/kummer_degree.sage
+++ b/kummer_degree.sage
@@ -1,13 +1,13 @@
1############################################################################### 1#############################################################################
2# This program allows one to compute the degree of certain field extensions # 2# This program allows one to compute the degree of certain field extensions #
3# of the rational numbers. In particular, it can compute the degree over Q of # 3# of the rational numbers. In particular, it can compute the degree over Q #
4# extensions of the form Q( sqrt[N](G), \zeta_M ), where: # 4# of extensions of the form Q( sqrt[N](G), \zeta_M ), where: #
5# - N and M are integers with N dividing M; # 5# - N and M are integers with N dividing M; #
6# - G is a finitely generated subgroup of the multiplicative group of Q # 6# - G is a finitely generated subgroup of the multiplicative group of Q #
7# - \zeta_M is a primitive M-th root of unity # 7# - \zeta_M is a primitive M-th root of unity #
8# The group G does not have to be given in a particular format. A finite set # 8# The group G does not have to be given in a particular format. A finite #
9# of generators is sufficient. # 9# set of generators is sufficient. #
10############################################################################### 10#############################################################################
11 11
12# Computes the "adelic Kummer failure", i.e. the degrees of the intersection 12# Computes the "adelic Kummer failure", i.e. the degrees of the intersection
13# of the the Kummer extension Q(\sqrt{2^n}{G}) with the M-th cyclotomic field 13# of the the Kummer extension Q(\sqrt{2^n}{G}) with the M-th cyclotomic field
@@ -16,12 +16,12 @@
16# Input: a good basis B for the torsion-free group G, organized as a list of 16# Input: a good basis B for the torsion-free group G, organized as a list of
17# lists, and a non negative integer d. They have to satisfy the following: 17# lists, and a non negative integer d. They have to satisfy the following:
18# 1. Each list B[i] contains all basis elements of 2-divisibility i. 18# 1. Each list B[i] contains all basis elements of 2-divisibility i.
19# 2. The basis given by B is 2-maximal, that is to say it satisfies Theorem 14 19# 2. The basis given by B is 2-maximal, that is to say it satisfies Theorem
20# of Debry-Perucca; i.e. each element of B[i] is, up to plus or minus 1, the 20# 14 of Debry-Perucca; i.e. each element of B[i] is, up to plus or minus
21# 2^i-th power of a strongly 2-indivisible rational. 21# 1, the 2^i-th power of a strongly 2-indivisible rational.
22# 3. For i != d every element of B[i] is positive, and B[d][0] is the only 22# 3. For i != d every element of B[i] is positive, and B[d][0] is the only
23# negative element of B[d] (if d=-1, then there is no negative element). 23# negative element of B[d] (if d=-1, then there is no negative element).
24# 3'. Notice that the existence on negative elements in B[0] does not influence 24# 3'. Notice that the existence on negative elements in B[0] does not change
25# the correctness of the algorithm; in fact, the function adjust_sign 25# the correctness of the algorithm; in fact, the function adjust_sign
26# produces a basis that may have negative elements of divisibility 0, and 26# produces a basis that may have negative elements of divisibility 0, and
27# this basis is given as input for adelic_failure_gb. 27# this basis is given as input for adelic_failure_gb.
@@ -30,9 +30,9 @@
30# integer such that the intersection of Q(\sqrt{2^n}{G}) with Q_\infty is 30# integer such that the intersection of Q(\sqrt{2^n}{G}) with Q_\infty is
31# contained in Q_M0. 31# contained in Q_M0.
32# The table ad_fail has N rows, where N is defined below. 32# The table ad_fail has N rows, where N is defined below.
33# Each row R=ad_fail[i] contains a variable number of pairs (d,r), where d is a 33# Each row R=ad_fail[i] contains a variable number of pairs (d,r), where d
34# divisor of M0 and r is the degree of Q(\sqrt{2^{i+1}}{G}) \cap Q_d over 34# is a divisor of M0 and r is the degree of Q(\sqrt{2^{i+1}}{G}) \cap Q_d
35# Q_{2^n}. 35# over Q_{2^n}.
36# Each divisor of M appears at most once on each row, and the last element of 36# Each divisor of M appears at most once on each row, and the last element of
37# the last row is of the form (M0,r0). 37# the last row is of the form (M0,r0).
38def adelic_failure_gb( B, d ): 38def adelic_failure_gb( B, d ):
@@ -40,48 +40,48 @@ def adelic_failure_gb( B, d ):
40 # The table to be returned (or printed at the end), as described above. 40 # The table to be returned (or printed at the end), as described above.
41 ad_fail = [] 41 ad_fail = []
42 42
43 # N is such that for every n > N the adelic failure of Q(\sqrt{2^n}{G}) is 43 # N is such that for every n > N the adelic failure of Q(\sqrt{2^n}{G})
44 # the same as that of Q(\sqrt{2^N}{G}). 44 # is the same as that of Q(\sqrt{2^N}{G}).
45 # We always have to include n=3, because of problem with sqrt(2) in Q_8 (in 45 # We always have to include n=3, because of problem with sqrt(2) in Q_8
46 # theory, this is not necessary in some cases, e.g. if 2 does not divide 46 # (in theory, this is not necessary in some cases, e.g. if 2 does not
47 # any element of G). 47 # divide any element of G).
48 # If the negative generator is on the last level, we need to increase N by 48 # If the negative generator is on the last level, we need to increase N
49 # 1, because it would contribute to the shortlist in the next level (by 49 # by 1, because it would contribute to the shortlist in the next level
50 # taking the root of an even power). 50 # (by taking the root of an even power).
51 if d == len(B)-1: 51 if d == len(B)-1:
52 N = max(3,len(B)+1) 52 N = max(3,len(B)+1)
53 else: 53 else:
54 N = max(3,len(B)) 54 N = max(3,len(B))
55 55
56 # The intersection is given by adding the square roots of the elements of 56 # The intersection is given by adding the square roots of the elements of
57 # this shortlist (and a "special element", not always of the form sqrt(d), 57 # this shortlist (and a "special element", not always of the form sqrt d,
58 # coming from taking a suitable root of a negative generator; this special 58 # coming from taking a suitable root of a negative generator; this
59 # element is dealt with later). The shortlist grows at each step, so we 59 # special element is dealt with later). The shortlist grows at each step,
60 # declare it before starting to loop over n and we build it incrementally. 60 # so we declare it before starting to loop over n and we build it
61 # The "special element" is of the form \zeta_{2^n}\sqrt{b}, which we encode 61 # incrementally. The "special element" is of the form \zeta_{2^n}\sqrt b,
62 # as (n,b). We use the value (1,1) (special element -1) to say that there 62 # which we encode as (n,b). We use the value (1,1) (special element -1)
63 # isno special element at this level. 63 # to say that there is no special element at this level.
64 shortlist = [] 64 shortlist = []
65 special_element = (1,1) 65 special_element = (1,1)
66 66
67 # The integers M, giving the smallest cyclotomic field in which lies the 67 # The integers M, giving the smallest cyclotomic field in which lies the
68 # whole intersection with Q_\infty, also grows with n. As with the 68 # whole intersection with Q_\infty, grows with n. As with the shortlist,
69 # shortlist, we declare it here and increase it appropriately at each step. 69 # we declare it here and increase it appropriately at each step.
70 M = 1 70 M = 1
71 71
72 for n in range( 1, N+1 ): 72 for n in range( 1, N+1 ):
73 73
74 # We add the new elements to the shortlist, modifying M if needed. 74 # We add the new elements to the shortlist, modifying M if needed.
75 # This is not done in case we are in the extra "fake" level (this case 75 # This is not done in case we are in the extra "fake" level (this
76 # dealt with immediately below). 76 # case dealt with immediately below).
77 if n-1 < len(B): 77 if n-1 < len(B):
78 for g in B[n-1]: 78 for g in B[n-1]:
79 # Case of negative g 79 # Case of negative g
80 if g < 0 and n > 1: 80 if g < 0 and n > 1:
81 # Special element of the form \zeta_{2^{n+1}}\sqrt(b). 81 # Special element of the form \zeta_{2^{n+1}}\sqrt(b).
82 # It is contained in Q_{lcm(2^{n+1},cyc_emb(b))}, except in 82 # It is contained in Q_{lcm(2^{n+1},cyc_emb(b))}, except
83 # case n=2 and b=2, in which case it is contained in Q_4. 83 # in case n=2 and b=2, in which case it is contained in
84 # We store it as as pair ( n+1, b ). 84 # Q_4. We store it as as pair ( n+1, b ).
85 special_element = ( n+1, abs(g)^(1/(2^(n-1))) ) 85 special_element = ( n+1, abs(g)^(1/(2^(n-1))) )
86 M = lcm( M, special_embed( special_element ) ) 86 M = lcm( M, special_embed( special_element ) )
87 else: 87 else:
@@ -89,8 +89,8 @@ def adelic_failure_gb( B, d ):
89 shortlist.append( b ) 89 shortlist.append( b )
90 M = lcm( M, cyc_embed(b) ) 90 M = lcm( M, cyc_embed(b) )
91 91
92 # We add a root of an even power of the negative generator, as soon as 92 # We add a root of an even power of the negative generator, as soon
93 # we are beyond its level. 93 # as we are beyond its level.
94 if d != -1 and n == d+2: 94 if d != -1 and n == d+2:
95 b = abs(B[d][0])^(1/2^d) 95 b = abs(B[d][0])^(1/2^d)
96 shortlist.append( b ) 96 shortlist.append( b )
@@ -112,19 +112,20 @@ def adelic_failure_gb( B, d ):
112 112
113 # For each divisor dM of M, compute the degree of the intersection of 113 # For each divisor dM of M, compute the degree of the intersection of
114 # Q(\sqrt{2^n}{G}) with Q_dM over Q_{2^n}. We need to compute the 114 # Q(\sqrt{2^n}{G}) with Q_dM over Q_{2^n}. We need to compute the
115 # number r of elements in the subgroup of G generated by the shortlist 115 # number r of elements in the subgroup of G generated by the
116 # that lie in Q_dM. This is going to be a power of 2. The sought degree 116 # shortlist that lie in Q_dM. This is going to be a power of 2. The
117 # will be r, up to considering some special cases (described below). 117 # sought degree will be r, up to considering some special cases
118 # (described below).
118 # 119 #
119 # This algorithm could be inefficient for groups of big rank. It can be 120 # This algorithm could be inefficient for groups of big rank. It can
120 # improved by precomputing subgroups of G/G^2 and the cyclotomic fields 121 # be improved by precomputing subgroups of G/G^2 and the cyclotomic
121 # containing them. 122 # fields containing them.
122 123
123 aux = [] # Next line of ad_fail table 124 aux = [] # Next line of ad_fail table
124 125
125 for dM in divisors( M ): 126 for dM in divisors( M ):
126 # We only care of the intersection with Q_dM if it contains the 2^n 127 # We only care of the intersection with Q_dM if it contains the
127 # roots of unity. 128 # 2^n roots of unity.
128 if dM % (2^n) != 0: 129 if dM % (2^n) != 0:
129 continue 130 continue
130 131
@@ -141,7 +142,7 @@ def adelic_failure_gb( B, d ):
141 if n <= d and dM % (2^(n+1)) == 0 and n > 1: 142 if n <= d and dM % (2^(n+1)) == 0 and n > 1:
142 r *= 2 143 r *= 2
143 144
144 # We loose a factor of 2 if we have sqrt(2) in Q_8 or \zeta_8 2 in 145 # We loose a factor of 2 if we have sqrt(2) in Q_8 or \zeta_8 in
145 # Q_4. 146 # Q_4.
146 if 8 in H and dM % 8 == 0 and (n >= 3 or (n == 2 and n <= d)): 147 if 8 in H and dM % 8 == 0 and (n >= 3 or (n == 2 and n <= d)):
147 r = r/2 148 r = r/2
@@ -150,11 +151,11 @@ def adelic_failure_gb( B, d ):
150 # We have to consider all possible special elements arising from 151 # We have to consider all possible special elements arising from
151 # multiplying the given element with the other elements of the 152 # multiplying the given element with the other elements of the
152 # shortlist. 153 # shortlist.
153 # If any of them is of the form \zeta_8 2q for q a square, there is 154 # If any of them is of the form \zeta_8 2q for q a square, there
154 # nothing to do: in fact \zeta_8 2 embeds in Q_4, which coincides 155 # is nothing to do: in fact \zeta_8 2 embeds in Q_4, which
155 # with Q_{2^n} (n must be 2); so we would double the degree because 156 # coincides with Q_{2^n} (n must be 2); so we would double the
156 # of the existence of the special element, butthen we would loose 157 # degree because of the existence of the special element, but
157 # another factor of 2 because of this. 158 # then we would loose another factor of 2 because of this.
158 if special_element != (1,1) and special_element[0] == n+1: 159 if special_element != (1,1) and special_element[0] == n+1:
159 nothing_to_do = False 160 nothing_to_do = False
160 intersecting_QdM = False 161 intersecting_QdM = False
@@ -223,15 +224,16 @@ def bad_primes( B ):
223 224
224 return sorted(bad_primes) # Ensures 2 is always first 225 return sorted(bad_primes) # Ensures 2 is always first
225 226
226# Computes the l-adic failure for a specific l. Returns a "table" as described 227# Computes the l-adic failure for a specific l. Returns a "table" as
227# above "total_l_adic_failure". 228# described above "total_l_adic_failure".
228# B is any basis for G. 229# B is any basis for G.
229def l_adic_failure( B, l ): 230def l_adic_failure( B, l ):
230 231
231 r = len(B) 232 r = len(B)
232 GB = make_good_basis( B, l ) 233 GB = make_good_basis( B, l )
233 234
234 # Computes the parameters over Q4. For l odd, they are the same as over Q. 235 # Computes the parameters for G over Q4. For l odd, they are the same as
236 # over Q.
235 p = parameters_Q4( GB, l ) 237 p = parameters_Q4( GB, l )
236 maxM = max( [ sum(x) for x in p ] ) 238 maxM = max( [ sum(x) for x in p ] )
237 maxN = max( maxM, len(GB)-1 ) 239 maxN = max( maxM, len(GB)-1 )
@@ -281,15 +283,10 @@ def l_adic_failure_from_data( B, l, tablel, M, N ):
281 283
282 return l^(r*n-tablel[m-1][0][n-1]) 284 return l^(r*n-tablel[m-1][0][n-1])
283 285
284# Returns the l-dvisibility parameters of G over Q, given a good basis gb of G, 286# Returns the l-dvisibility parameters of G over Q, given a good basis b of
285# as a list of pairs (di,hi). 287# G, as a list of pairs (di,hi).
286def parameters_Q( gb, l ): 288def parameters_Q( b, l ):
287 #ret = [] 289 return [x for a in [[(i,0)]*len(b[i]) for i in range(len(b))] for x in a]
288 #for i in range( len( gb ) ):
289 # for j in gb[i]:
290 # ret.append( (i,0) )
291 #return ret
292 return [x for a in [[(i,0)]*len(gb[i]) for i in range(len(gb))] for x in a]
293 290
294# Computes the l-divisibility parameters of G over Q4, given a good basis gb 291# Computes the l-divisibility parameters of G over Q4, given a good basis gb
295# over Q for G. Returns a list of pairs (di,hi). 292# over Q for G. Returns a list of pairs (di,hi).
@@ -300,16 +297,13 @@ def parameters_Q4( gb, l ):
300 return parameters_Q( gb, l ) 297 return parameters_Q( gb, l )
301 else: 298 else:
302 # Converts from "good basis format" to simple list 299 # Converts from "good basis format" to simple list
303 #b = []
304 #for x in gb:
305 # b += x
306 b = [ x for a in gb for x in a ] 300 b = [ x for a in gb for x in a ]
307 301
308 M = exponent_matrix( b ) 302 M = exponent_matrix( b )
309 303
310 # Thanks to my terrible notation, the elements of b are what are called 304 # Thanks to my bad notation, the elements of b are what are called
311 # g_i in the article, while the elements of bb will be the b_i's. 305 # g_i in the article, while the elements of bb will be the b_i's.
312 bb = [ abs(b[i]) ^ (2^(-divisibility(M[i],2))) for i in range(len(b)) ] 306 bb = [ abs(b[i])^(2^(-divisibility(M[i],2))) for i in range(len(b)) ]
313 307
314 # Computing a combination of bb elements of the form 2 * square. 308 # Computing a combination of bb elements of the form 2 * square.
315 MM = exponent_matrix( bb + [2] ).change_ring( GF( 2 ) ) 309 MM = exponent_matrix( bb + [2] ).change_ring( GF( 2 ) )
@@ -322,7 +316,7 @@ def parameters_Q4( gb, l ):
322 # Basis elements that actually appear in the combination 316 # Basis elements that actually appear in the combination
323 c = [ b[i] for i in range(len(a[0:-1])) if a[i] != 0 ] 317 c = [ b[i] for i in range(len(a[0:-1])) if a[i] != 0 ]
324 318
325 # Return the parameters, changing only the ones for the element 319 # Return the parameters, changing only those of the element
326 # of highest divisibility that appears in the combination. 320 # of highest divisibility that appears in the combination.
327 ret = [] 321 ret = []
328 div_max = -1 322 div_max = -1
@@ -352,29 +346,14 @@ def compute_vl( p, n, m, r ):
352 return M - m + r*n - sum( ni ) 346 return M - m + r*n - sum( ni )
353 347
354# Computes a basis for G from a set of generators. 348# Computes a basis for G from a set of generators.
355# Returns a pair (B,torsion) where B is a list of rational numbers and torsion 349# Returns a pair (B,torsion) where B is a list of rational numbers and
356# is true if -1 is in G and false otherwise. 350# torsion is true if -1 is in G and false otherwise.
357def generators_to_basis( G ): 351def generators_to_basis( G ):
358 (BM,BM_primes) = exponent_matrix_with_sign_and_primes( G ) 352 (BM,BM_primes) = exponent_matrix_with_sign_and_primes( G )
359 BM = BM.echelon_form() 353 BM = BM.echelon_form()
360 BM_primes.append(-1) 354 BM_primes.append(-1)
361 355
362 #B = [] 356 B = [prod([BM_primes[i]^r[i] for i in range(len(r))]) for r in BM.rows()]
363 #torsion = False
364
365 #for r in BM.rows():
366 # gr = product( [ BM_primes[i]^r[i] for i in range(len(r)) ] )
367 # if gr == -1:
368 # torsion = True
369 # break
370 # elif gr == 1:
371 # break
372 # else:
373 # B.append(gr)
374
375 #return (B,torsion)
376
377 B = [ prod([BM_primes[i]^r[i] for i in range(len(r))]) for r in BM.rows() ]
378 357
379 return ( [ x for x in B if abs(x) != 1 ], -1 in B ) 358 return ( [ x for x in B if abs(x) != 1 ], -1 in B )
380 359
@@ -383,12 +362,6 @@ def generators_to_basis( G ):
383# using the algorithm outlined in the proof of Theorem 14 of (Debry-Perucca). 362# using the algorithm outlined in the proof of Theorem 14 of (Debry-Perucca).
384def make_good_basis( b, l ): 363def make_good_basis( b, l ):
385 M = exponent_matrix( b ) 364 M = exponent_matrix( b )
386 #d = []
387 #B = []
388 #for i in range(len(b)):
389 # di = divisibility( M[i], l )
390 # d.append( di )
391 # B.append( abs(b[i])^(1/(l^di)) )
392 d = [ divisibility(x,l) for x in M ] 365 d = [ divisibility(x,l) for x in M ]
393 B = [ abs(b[i])^(1/(l^d[i])) for i in range(len(b)) ] 366 B = [ abs(b[i])^(1/(l^d[i])) for i in range(len(b)) ]
394 367
@@ -398,8 +371,8 @@ def make_good_basis( b, l ):
398 371
399 while coeffs != []: 372 while coeffs != []:
400 373
401 # Computes which basis element (with non-zero coefficient in the linear 374 # Computes which basis element (with non-zero coefficient in the
402 # combination above) has maximal divisibility. 375 # linear combination above) has maximal divisibility.
403 maxi = -1 376 maxi = -1
404 maxd = -1 377 maxd = -1
405 for i in range(len(d)): 378 for i in range(len(d)):
@@ -407,12 +380,9 @@ def make_good_basis( b, l ):
407 maxd = d[i] 380 maxd = d[i]
408 maxi = i 381 maxi = i
409 382
410 x = [ (a/coeffs[maxi]).lift() for a in coeffs ] # Now a vector of ints 383 x = [ (a/coeffs[maxi]).lift() for a in coeffs ] # Now a vector of int
411 384
412 #new_elt = 1 385 new_elt = prod([b[i]^(x[i]*l^(d[maxi]-d[i])) for i in range(len(d))])
413 #for i in range(len(d)):
414 # new_elt *= b[i]^( x[i] * l^(d[maxi]-d[i]) )
415 new_elt = prod([ b[i]^(x[i]*l^(d[maxi]-d[i])) for i in range(len(d)) ])
416 386
417 b[maxi] = new_elt 387 b[maxi] = new_elt
418 M = exponent_matrix( b ) 388 M = exponent_matrix( b )
@@ -421,20 +391,13 @@ def make_good_basis( b, l ):
421 391
422 coeffs = find_combination( exponent_matrix( B ), l ) 392 coeffs = find_combination( exponent_matrix( B ), l )
423 393
424 #GB = [[]]
425 #for i in range(len(d)):
426 # while( len(GB) <= d[i] ):
427 # GB.append([])
428 # GB[d[i]].append(b[i])
429 #return GB
430
431 return [[b[i] for i in range(len(b)) if d[i]==j] for j in range(max(d)+1)] 394 return [[b[i] for i in range(len(b)) if d[i]==j] for j in range(max(d)+1)]
432 395
433# Takes a good basis B and adjusts the sign of the elements so that there is at 396# Takes a good basis B and adjusts the sign of the elements so that there is
434# most one negative generator (of positive divisibility). The input is a good 397# at most one negative generator (of positive divisibility). The input is a
435# basis in the format returned by make_good_basis. 398# good basis in the format returned by make_good_basis.
436# Returns a pair (B,d), where B is the updated basis and d is the divisibility 399# Returns a pair (B,d), where B is the updated basis and d is the
437# parameter of the only negative element remained. 400# divisibility parameter of the only negative element remained.
438# The sign of the d=0 elements is just ignored in the other steps of the 401# The sign of the d=0 elements is just ignored in the other steps of the
439# algorithm, so we keep them negative. 402# algorithm, so we keep them negative.
440def adjust_sign( B ): 403def adjust_sign( B ):
@@ -491,12 +454,8 @@ def exponent_matrix( B ):
491# Returns a pair (M,L) where M is the modified exponent matrix and L is the 454# Returns a pair (M,L) where M is the modified exponent matrix and L is the
492# list of primes appearing in the factorization. 455# list of primes appearing in the factorization.
493def exponent_matrix_with_sign_and_primes( B ): 456def exponent_matrix_with_sign_and_primes( B ):
494 #prime_list = set()
495 #for g in B:
496 # prime_list |= set( prime_factors( g ) )
497 #prime_list = list( prime_list )
498 457
499 prime_list = list({ x for a in [prime_factors(g) for g in B] for x in a }) 458 prime_list = list({x for a in [prime_factors(g) for g in B] for x in a})
500 np = len( prime_list ) 459 np = len( prime_list )
501 460
502 rows = [] 461 rows = []
@@ -516,8 +475,8 @@ def TotalKummerFailure( G ):
516 475
517# Input: any set of generators for a subgroup G of Q*. 476# Input: any set of generators for a subgroup G of Q*.
518# If output=False, returns a 4-uple (t,MM,NN,D): 477# If output=False, returns a 4-uple (t,MM,NN,D):
519# - t is a pair, where t[0] is the rank of G and t[1] is either True (if G has 478# - t is a pair, where t[0] is the rank of G and t[1] is either True (if G
520# torsion) or False (is it does not). 479# has torsion) or False (is it does not).
521# - MM is the pair (M0,divisors(M0)) 480# - MM is the pair (M0,divisors(M0))
522# - NN is the pair (N0,divisors(N0)) 481# - NN is the pair (N0,divisors(N0))
523# - D is a table F, where F[j][i] is the ration between phi(m)n^r and the 482# - D is a table F, where F[j][i] is the ration between phi(m)n^r and the
@@ -543,9 +502,6 @@ def total_kummer_failure( G, output ):
543 adelic_failure_table = adelic_failure_gb( GB, d ) 502 adelic_failure_table = adelic_failure_gb( GB, d )
544 503
545 # Computing the bounds M0 and N0 504 # Computing the bounds M0 and N0
546 #N0 = 1
547 #for i in range(len( bad_primes )):
548 # N0 *= bad_primes[i] ^ len( l_adic_failure_table[i][-1][0] )
549 N0 = prod( [ bad_primes[i] ^ len( l_adic_failure_table[i][-1][0] ) \ 505 N0 = prod( [ bad_primes[i] ^ len( l_adic_failure_table[i][-1][0] ) \
550 for i in range(len(bad_primes)) ] ) 506 for i in range(len(bad_primes)) ] )
551 # Extra factors of 2 may come from the adelic failure 507 # Extra factors of 2 may come from the adelic failure
@@ -596,9 +552,9 @@ def total_kummer_failure( G, output ):
596# as the ration between 2^eN^r and the degree of Q_{M,N} over Q_M, where e=1 552# as the ration between 2^eN^r and the degree of Q_{M,N} over Q_M, where e=1
597# if N is even and e=0 otherwise. 553# if N is even and e=0 otherwise.
598 554
599# Makes the failure table for the torsion case when M/N is even. In this case, 555# Makes the failure table for the torsion case when M/N is even. In this
600# an entry of the table is doubled if the corresponding value of N (actually, 556# case an entry of the table is doubled if the corresponding value of N
601# of gcd(N,N0) ) is even, and is kept the same otherwise. 557# (actually, of gcd(N,N0) ) is even, and is kept the same otherwise.
602# The expected degree (over Q) 2^e * phi(M) * N^r, where e=1 if N is even and 558# The expected degree (over Q) 2^e * phi(M) * N^r, where e=1 if N is even and
603# e=0 otherwise. 559# e=0 otherwise.
604def torsion_table_even( data ): 560def torsion_table_even( data ):
@@ -615,8 +571,8 @@ def torsion_table_even( data ):
615 571
616# Makes the failure table for the torsion case when M/N is odd. In this case 572# Makes the failure table for the torsion case when M/N is odd. In this case
617# the entry at (M,N) is taken from the torsion-free entry at (2M,N). 573# the entry at (M,N) is taken from the torsion-free entry at (2M,N).
618# In other words, the expected degree (over Q) 2^e * phi(M) * N^r, where e=1 if 574# In other words, the expected degree (over Q) 2^e * phi(M) * N^r, where e=1
619# N is even and e=0 otherwise. 575# if N is even and e=0 otherwise.
620def torsion_table_odd( data ): 576def torsion_table_odd( data ):
621 577
622 ( ( r, torsion ), ( M0, divs_M0 ), ( N0, divs_N0 ), FT ) = data 578 ( ( r, torsion ), ( M0, divs_M0 ), ( N0, divs_N0 ), FT ) = data
@@ -672,17 +628,17 @@ def print_total_table( data ):
672 628
673 if torsion: 629 if torsion:
674 print "The following table shows the total failure of Kummer degrees", 630 print "The following table shows the total failure of Kummer degrees",
675 print "in case the quotient M/N is ODD and is read as the previous one." 631 print "if the quotient M/N is ODD and is read as the previous one."
676 print "" 632 print ""
677 633
678 # A good strategy is the following: 634 # A good strategy is the following:
679 # A little translation exercise: the failure at (M,N) in the torsion 635 # A little translation exercise: the failure at (M,N) in the torsion
680 # case is either the same as that for (2M,N) in the torsion-free case 636 # case is either the same as that for (2M,N) in the torsion-free
681 # (if M is even) or its double (if M is odd). 637 # case (if M is even) or its double (if M is odd).
682 # However, due to problems in reading the table for bigger M, it is 638 # However, due to problems in reading the table for bigger M, it is
683 # easier to just compute the degree every time, and then deduce the 639 # easier to just compute the degree every time, and then deduce the
684 # failure. This is not too inefficient, since we can use the data that 640 # failure. This is not too inefficient, since we can use the data
685 # we have already computed via kummer_degree_from_total_table. 641 # that we have already computed via kummer_degree_from_total_table.
686 new_FT = torsion_table_odd( data ) 642 new_FT = torsion_table_odd( data )
687 # Printing the new table 643 # Printing the new table
688 tt = [ ["","|"] + divs_M0 ] 644 tt = [ ["","|"] + divs_M0 ]
@@ -717,7 +673,7 @@ def print_case_list( data ):
717 print "or if M/N is ODD and (gcd(M,M0)),gcd(N,N0)) is one of the", 673 print "or if M/N is ODD and (gcd(M,M0)),gcd(N,N0)) is one of the",
718 print "following:" 674 print "following:"
719 print [ (divs_M0[j], divs_N0[i]) \ 675 print [ (divs_M0[j], divs_N0[i]) \
720 for i in range(len(divs_N0)) for j in range(len(divs_M0)) \ 676 for i in range(len(divs_N0)) for j in range(len(divs_M0))\
721 if FT_odd[i][j] == f ] 677 if FT_odd[i][j] == f ]
722 678
723 print "" 679 print ""
@@ -758,10 +714,10 @@ def KummerDegree( G, M, N ):
758 data = total_kummer_failure(G,False) 714 data = total_kummer_failure(G,False)
759 ((r,torsion),(M0,divs_M0),(N0,divs_N0),FT) = data 715 ((r,torsion),(M0,divs_M0),(N0,divs_N0),FT) = data
760 716
761 exp_deg = euler_phi(M) * N^r 717 e_deg = euler_phi(M) * N^r
762 718
763 if torsion and N % 2 == 0: 719 if torsion and N % 2 == 0:
764 exp_deg *= 2 720 e_deg *= 2
765 721
766 if torsion: 722 if torsion:
767 if (M/N)%2 == 0: 723 if (M/N)%2 == 0:
@@ -771,4 +727,4 @@ def KummerDegree( G, M, N ):
771 else: 727 else:
772 failure = FT 728 failure = FT
773 729
774 return exp_deg/failure[divs_N0.index(gcd(N,N0))][divs_M0.index(gcd(M,M0))] 730 return e_deg/failure[divs_N0.index(gcd(N,N0))][divs_M0.index(gcd(M,M0))]

Generated with cgit - Back to sebastiano.tronto.net