diff options
Diffstat (limited to '')
| -rw-r--r-- | README.md | 34 | ||||
| -rw-r--r-- | kummer_degree.sage | 236 |
2 files changed, 108 insertions, 162 deletions
| @@ -9,39 +9,29 @@ Outputs the description of the failure of maximality for all possible values of | |||
| 9 | Example: | 9 | Example: |
| 10 | 10 | ||
| 11 | ``` | 11 | ``` |
| 12 | |||
| 12 | sage: TotalKummerFailure([-36,12,-1]) | 13 | sage: TotalKummerFailure([-36,12,-1]) |
| 13 | M_0 = 24 | 14 | M_0 = 24 |
| 14 | N_0 = 8 | 15 | N_0 = 8 |
| 15 | 16 | ||
| 16 | The following table shows the total failure of Kummer degrees in | 17 | The 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. | 18 | The 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). |
| 18 | Columns correspond to values of M, rows to values of N | ||
| 19 | |||
| 20 | The degree of the Kummer extension (M,N) can be extracted by taking | ||
| 21 | the value f (failure) of the entry at (gcd(N,N0),gcd(M,M0)) and | ||
| 22 | simply computing ed(M,N) / f, where ed(M,N) is the expected degree | ||
| 23 | of the Kummer extension. | ||
| 24 | In this case (-1 is in G), we have ed(M,N) = 2^e*phi(M)*N^r, | ||
| 25 | where e=1 if N is even and e=0 if N is odd. | ||
| 26 | where 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 | ||
| 35 | The following table shows the total failure of Kummer degrees in | 27 | The following table shows the total failure of Kummer degrees if the quotient M/N is ODD and is read as the previous one. |
| 36 | case the quotient M/N is ODD. | ||
| 37 | This 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 | |||
| 52 | Example: | 42 | Example: |
| 53 | ``` | 43 | ``` |
| 54 | sage: KummerDegree([-36,12,-1],120,24) | 44 | sage: KummerDegree([-36,12,-1],120,24) |
| 55 | 2304 | 45 | 4608 |
| 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). |
| 38 | def adelic_failure_gb( B, d ): | 38 | def 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. |
| 229 | def l_adic_failure( B, l ): | 230 | def 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). |
| 286 | def parameters_Q( gb, l ): | 288 | def 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. |
| 357 | def generators_to_basis( G ): | 351 | def 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). |
| 384 | def make_good_basis( b, l ): | 363 | def 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. |
| 440 | def adjust_sign( B ): | 403 | def 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. |
| 493 | def exponent_matrix_with_sign_and_primes( B ): | 456 | def 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. |
| 604 | def torsion_table_even( data ): | 560 | def 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. |
| 620 | def torsion_table_odd( data ): | 576 | def 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))] |
