"""numwall.py -- the wall over a number ring against w_L(K). QUESTION. Over Z the wall at L (the largest M with lambda(M) | L) is Adams' number W(L), and it is also the largest m with Gal(Q(mu_m)/Q) of exponent dividing L, because Gal(Q(mu_m)/Q) is (Z/m)^x: a fact of Z, re-derived for K here, not assumed. Over the ring of integers O_K of a number field the wall W_K is an ideal, read off (O_K/M)^x, while w_L(K), the largest m with Gal(K(mu_m)/K) of exponent dividing L (the name is Serre's; the integer is defined here, its Chebotarev form D7 resting on Chebotarev's density theorem), is an integer read off K's cyclotomic extensions. What does one read of the other? THE OBJECTS (K Galois over Q, so the places over p are conjugate). W_K = prod_p rad(p)^(a_p), a_p the largest a with lambda(P^a) = (N(P) - 1) E_P(a) dividing L (the module law), P any place over p; c the positive generator of W_K cap Z, so v_l(c) = ceil(a_l / e_l). w = w_L(K), as defined above. n = n_L(K), the NORM WALL: the largest m with N_(K/Q)((O_K/m)^x) of exponent dividing L; equivalently the gcd over y in O_K of N(y)^s (N(y)^L - 1) at large s. The wall is Adams' gcd ideal over y in O_K of y^s (y^L - 1): n is the same gcd taken after the norm. THE ARGUMENT (written before the engine). D1 c | W(L): Z/c embeds in O_K/W_K, so (Z/c)^x has exponent | L. D2 W(L) | w: Gal(K(mu_m)/K) embeds in Gal(Q(mu_m)/Q) = (Z/m)^x. D3 w | n: the principal ideal (y), y prime to m, has Artin symbol |N(y)| on Q(mu_m), so H_el(m) = N((O_K/m)^x) lies in Gal(K(mu_m)/K), which also holds -1 when K has a real place. D4 the Artin map takes the ideals prime to m onto Gal(K(mu_m)/K) and the principal ones onto H+ = {|N(y)|}, inside , so Gal / H+ is Gal(K(mu_m) cap H / K), H the Hilbert class field. K(mu_oo) cap H lies in Q^ab cap H, which is unramified over K; an abelian field over Q is generated over Q by its inertia groups (Q has no unramified extension), so one unramified over K and inside K(mu_oo) is K itself when every inertia group of K is already that of the bigger field: at K = Q(mu_m) always, at a quadratic K of prime discriminant since then one inertia group of order 2 generates. There Gal = H+, so n = w at even L. For quadratic K, K(mu_m) cap H lies in the genus field, so Gal / H+ is a quotient of its group, of exponent 2: g^2 lies in H+ for every g, so n | w_(2L) at even L, and a prime of n / w is one l whose K(mu_(l^k)) meets the genus field beyond K, which needs l | D. D5 at l unramified in K the local norm maps O_P^x onto Z_l^x, so the l-part of n is W(L)'s. D6 v_l(w) > v_l(W(L)) needs K cap Q(mu_(l^oo)) != Q, so l ramified in K. D7 the Chebotarev form: v_l(w) = min over places v not over l of v_l(N(v)^L - 1): Frobenius at v acts on mu_(l^k) as N(v), and every element of Gal(K(mu_(l^k))/K) is a Frobenius. DESIGN. Standard library only; one process. Fields: Q (m = 1, the control); Q(sqrt d) at every squarefree d, 2 <= |d| <= 50, and d = -1; Q(mu_m) at m = 3, 4, 5, 7, 8, 9, 12. L: every even L <= 60. Q(mu_3) and Q(mu_4) repeat d = -3, -1 as C4's control, so the 69 fields are 67 distinct. The local ring at P is a TOWER W_f[x]/(g): W_f = Z_p[y]/(h), h irreducible mod p of degree f, g Eisenstein over Z_p of degree e (g = x - p at e = 1): Q_p(sqrt d) by x^2 - d or (x + 1)^2 - d, and Q_p(mu_m) by Phi_(p^k)(x + 1) over W_f, f the order of p mod m'. E(a) is the largest order in U_1/U_a of the generators 1 + y^j x^i. w by its definition, per prime l (the exponent of Gal(K(mu_M)/K) is the lcm over l^k || M of the exponents at l^k, since K(mu_M) is the compositum): Gal(K(mu_(l^k))/K) is the image in (Z/l^k)^x of the a mod lcm(f_K, l^k) with a mod f_K in H_K, K the fixed field of H_K in Q(mu_(f_K)). Only l <= nL + 1 can enter (the image mod l has index at most n in a cyclic group of order l - 1). n by the norm Adams gcd over a box of y in O_K = Z[t]/(F), s = 64, read at two boxes. C CONTROLS, read before any verdict: C1 the tower's (N(P) - 1) E(a) is the exponent of the whole unit group of O_P/P^a at every local ring a wall can meet (N(P) <= 61) and every a with N(P)^a <= 20,000; and E(1..9) at Z_2, Q_2(sqrt -2), Q_2(i), Q_2(sqrt -5) as module_law.py printed them. C2 K = Q: W = (W(L)) and c = w = n = W(L), W(L) by its closed form 2^(v_2(L) + 2) prod (p^(v_p(L) + 1) : p odd, p - 1 | L). C3 the Adams gcd ideal over a box of y in O_K has index N(W_K); it lies in W_K by definition, so equal index is equality; at every L for degree <= 2, at L = 2, 4, 6, 12, 24, 60 above. C4 Q(mu_3), Q(mu_4) agree with d = -3, -1 on N(W), c, w, n. C5 w by definition equals w by D7 (places v with N(v) <= 4000). C6 the hand values at L = 2: Q(i) W = P2^2, c 2, w 24, n 24; Q(sqrt -3) W = P3, c 3, w = n = 24; Q(sqrt 5) W = (1), c 1, w = n = 120; Q(sqrt -15) W = P2^3 P2'^3 P3, c 24, w 24, n 120. C7 n read at two boxes agrees. C8 at every place P alone over its p (N(P) <= 61), a_P read a second way: v_P(x) = v_p(N(x)) / f, the norm taken in Z[t]/(F) mod p^(41 f), and a_P the least v_P(g^L - 1) over a generator t of (O/P)^x and the 1 + t^j pi^b (j < f, b >= 1, pi of valuation 1, both found by search), which generate (O/P^a)^x since each U_b/U_(b+1) is the residue field under addition; b runs while b < the running least. PREDICTIONS AND KILLS, frozen before the engine. T1 c | W(L) | w | n at every (K, L). T2 n = w at every cyclotomic field and every quadratic field of prime discriminant. T3 quadratic K: n | w_(2L), every prime of n / w divides D. T5 v_l(n) = v_l(W(L)) at every l unramified in K. T6 v_l(w) > v_l(W(L)) only at l ramified in K. A KILL is any printed violation of T1-T6; a control miss fails the instrument. OBSERVED, no prediction: where c = W(L), where w = W(L), where n != w. FINDINGS (from the printed run, 14/14 checks PASS). C every control held: C1 at 1089 (ring, a) over 145 local rings, 0 off, and E(1..9) at the four rings at 2 as module_law.py printed; C2 at every even L <= 60; C3 at 1950 (field, L), 0 off; C4; C5 at 2070 (field, L), 0 off; C6 (Q(i): W = P2^2, norm 4, c 2, w 24, n 24; Q(sqrt -3): W = P3, c 3, w = n = 24; Q(sqrt 5): W = (1), c 1, w = n = 120; Q(sqrt -15): W = P2^3 P2'^3 P3, norm 192, c 24, w 24, n 120); C7 at 2070; C8 at 6900 (field, place, L), 0 off, the eight depths past C1 among them: 18, 22, 18 over 2 of Q(mu_8) at L = 16, 32, 48; 12, 12, 18 over 3 of Q(mu_9) at 18, 36, 54; 8 over 7 of Q(mu_7) at 42; 8 over 2 of Q(mu_12) at 48. A tower with E lowered at depth 7, in a scratch copy, fails C8 at 104 (field, place, L). T every prediction held: T1 at 2070 (field, L), T2 at 750, T3, T5 and T6 with 0 off. O c = W(L) at 115 of 2070, w = W(L) at 1915, W_K = (1) at 72, and n != w at 439, over 26 quadratic fields, every one of composite discriminant. The 178 odd (field, L, l) in n / w are l^(1 + v_l(L)), at the L with (l - 1)/2 | L and (l - 1) not | L: l = 5 over d = -35, -30, -15, -10, -5, 10, 15, 30, 35; 13 over d = -39, -26, -13, 26, 39; 17 over d = -34, -17, 34; 29, 37, 41 over -29, -37, -41. 2 exactly divides n / w at every even L over d = -46, -38, -30, -22, -14, -6, 10, 26, 34, 42. Read at L = 2, 12, 60: Q(mu_7) has W_K = (1), c = 1 at L = 2 and the place over 7, c = 7, at 12 and 60, while w = 168, 65520, 6814407600; Q(sqrt 17)'s wall is the same ideal at L = 12 and 60. WHY the odd gaps (a proof): at odd l | D with K not Q(sqrt l*), K cap Q(mu_(l^oo)) = Q, so Gal(K(mu_(l^k))/K) is all of the cyclic (Z/l^k)^x, exponent (l - 1) l^(k - 1); the norm of a local unit a + b sqrt(l u) is a^2 - l u b^2 = a^2 mod l, and 1 + l Z_l is all squares, so the norm image is the squares, exponent (l - 1)/2 l^(k - 1). Hence v_l(n / w) = 1 + v_l(L) exactly when (l - 1)/2 | L and l - 1 does not, which at even L needs l = 1 mod 4. The relation: no ideal map from W_K to w. They are Adams' gcd over O_K taken before the norm (W_K) and after it (n, which is w up to the genus field), and they meet at Adams' number, c | W(L) | w | n. Residue degree takes from the wall (a place enters only when N(P) - 1 | L), ramification adds to w (only at l | D). RUN RECORD. 124.4 s, peak commit 29.3 MB; with the gap tally, 123.2 s, 31.0 MB, every earlier print unchanged; its label read (field, L, l), 124.6 s, 29.4 MB; with C8, 124.4 s, 31.1 MB, C8 itself under a second. An earlier run built towers for places no wall meets (an irreducible of degree 6 mod 61 by trial) and recomputed (Z/l^k)^x per field at T3; both stopped by the clock, redesigned, not rerun as they were. """ import sys import time from itertools import product from math import gcd, isqrt CHECKS, NAMES = [], [] LS = list(range(2, 61, 2)) def check(name, ok, detail=""): CHECKS.append(bool(ok)) NAMES.append(name) print(f" [{'PASS' if ok else 'FAIL'}] {name}" + (f" -- {detail}" if detail else "")) def section(title): print() print("=" * 72) print(title) print("=" * 72) # ------------------------------------------------------------ arithmetic def lcm(a, b): return a // gcd(a, b) * b def vp(n, p): if n == 0: return 10 ** 9 v = 0 while n % p == 0: n //= p v += 1 return v def primes_up_to(n): s = bytearray([1]) * (n + 1) s[0] = s[1] = 0 for i in range(2, isqrt(n) + 1): if s[i]: s[i * i::i] = bytearray(len(s[i * i::i])) return [i for i in range(n + 1) if s[i]] PR = primes_up_to(5000) def factor(n): out = {} for p in PR: if p * p > n: break while n % p == 0: out[p] = out.get(p, 0) + 1 n //= p if n > 1: out[n] = out.get(n, 0) + 1 return out def mult_order(a, m): if m == 1: return 1 k, x = 1, a % m while x != 1: x = x * a % m k += 1 return k def adams_closed(L): """W(L) at even L by its closed form.""" w = 2 ** (vp(L, 2) + 2) for p in PR[1:]: if p - 1 > L: break if L % (p - 1) == 0: w *= p ** (vp(L, p) + 1) return w def kronecker(D, a): """(D / a) for a > 0.""" r = 1 while a % 2 == 0: a //= 2 if D % 2 == 0: return 0 r *= 1 if D % 8 in (1, 7) else -1 # Jacobi (D / a), a odd x, y = D % a, a while x: while x % 2 == 0: x //= 2 if y % 8 in (3, 5): r = -r x, y = y, x if x % 4 == 3 and y % 4 == 3: r = -r x %= y return r if y == 1 else 0 def poly_mod_p_irreducible(h, p): """h monic, coefficients low to high, irreducible over F_p (by trial division by every monic polynomial of degree <= deg h / 2).""" n = len(h) - 1 for d in range(1, n // 2 + 1): for tail in product(range(p), repeat=d): q = list(tail) + [1] r = [c % p for c in h] while len(r) - 1 >= d: c = r[-1] if c: for i in range(d + 1): r[len(r) - 1 - d + i] = (r[len(r) - 1 - d + i] - c * q[i]) % p r.pop() if not any(r): return False return True def irreducible(p, f): if f == 1: return [0, 1] for tail in product(range(p), repeat=f): h = list(tail) + [1] if poly_mod_p_irreducible(h, p): return h raise ValueError def cyclotomic(m): """Phi_m, coefficients low to high.""" num = [-1] + [0] * (m - 1) + [1] for d in range(1, m): if m % d == 0: q = cyclotomic(d) out = [0] * (len(num) - len(q) + 1) r = num[:] for i in range(len(out) - 1, -1, -1): c = r[i + len(q) - 1] out[i] = c for j, qj in enumerate(q): r[i + j] -= c * qj num = out return num def shift1(g): """g(x + 1).""" out = [0] * len(g) for i, c in enumerate(g): b = 1 for j in range(i + 1): out[j] += c * b b = b * (i - j) // (j + 1) return out # ------------------------------------------------------- the local tower class Tower: """O_P = W_f[x]/(g), W_f = Z_p[y]/(h), carried mod p^N; an element is e lists of f integers, z[i][j] the coefficient of x^i y^j.""" def __init__(self, p, h, g): self.p, self.h, self.g = p, h, g self.f, self.e = len(h) - 1, len(g) - 1 self.q = p ** self.f self.Ecache = {} def wmul(self, u, w, mod): f, h = self.f, self.h prod_ = [0] * (2 * f - 1) for i, a in enumerate(u): if a: for j, b in enumerate(w): prod_[i + j] += a * b for d in range(2 * f - 2, f - 1, -1): c = prod_[d] if c: prod_[d] = 0 for k in range(f): prod_[d - f + k] -= c * h[k] return [c % mod for c in prod_[:f]] def mul(self, u, w, mod): e, f, g = self.e, self.f, self.g prod_ = [[0] * f for _ in range(2 * e - 1)] for i, a in enumerate(u): if any(a): for j, b in enumerate(w): if any(b): c = self.wmul(a, b, mod) prod_[i + j] = [(s + t) % mod for s, t in zip(prod_[i + j], c)] for d in range(2 * e - 2, e - 1, -1): c = prod_[d] if any(c): prod_[d] = [0] * f for k in range(e): prod_[d - e + k] = [(s - g[k] * t) % mod for s, t in zip(prod_[d - e + k], c)] return prod_[:e] def power(self, u, k, mod): r = self.one() while k: if k & 1: r = self.mul(r, u, mod) u = self.mul(u, u, mod) k >>= 1 return r def one(self): z = [[0] * self.f for _ in range(self.e)] z[0][0] = 1 return z def val(self, z, N): best, mod = self.e * N, self.p ** N for i, c in enumerate(z): for cij in c: cij %= mod if cij: best = min(best, self.e * vp(cij, self.p) + i) return best def minus_one(self, z, mod): w = [c[:] for c in z] w[0][0] = (w[0][0] - 1) % mod return w def prec(self, a): return a // self.e + 2 def xpow(self, i, mod): x = [[0] * self.f for _ in range(self.e)] if self.e == 1: x[0][0] = self.p else: x[1][0] = 1 return self.power(x, i, mod) def ypow(self, j): z = [[0] * self.f for _ in range(self.e)] z[0][j] = 1 return z def E(self, a): """The exponent of U_1/U_a from the generators 1 + y^j x^i.""" if a in self.Ecache: return self.Ecache[a] N = self.prec(a) mod, best = self.p ** N, 0 for i in range(1, a): xi = self.xpow(i, mod) for j in range(self.f): z = self.mul(self.ypow(j), xi, mod) z[0][0] = (z[0][0] + 1) % mod m = 0 while self.val(self.minus_one(z, mod), N) < a: z = self.power(z, self.p, mod) m += 1 best = max(best, m) self.Ecache[a] = self.p ** best return self.Ecache[a] def lam(self, a): return 1 if a == 0 else (self.q - 1) * self.E(a) def depth(self, L): """a_P: the largest a with lambda(P^a) | L.""" if L % (self.q - 1): return 0 a = 1 while L % self.lam(a + 1) == 0: a += 1 return a def whole_exponent_is(self, a, lam): """True iff lam is the exponent of (O_P/P^a)^x, every unit read.""" N = self.prec(a) mod = self.p ** N xs = [self.xpow(i, mod) for i in range(a)] digits = [list(t) for t in product(range(self.p), repeat=self.f)] units = [] for combo in product(range(len(digits)), repeat=a): if combo[0] == 0: continue z = [[0] * self.f for _ in range(self.e)] for i, k in enumerate(combo): if k: d = [[0] * self.f for _ in range(self.e)] d[0] = digits[k][:] t = self.mul(d, xs[i], mod) z = [[(s + u) % mod for s, u in zip(r1, r2)] for r1, r2 in zip(z, t)] units.append(z) def is_one(z): return self.val(self.minus_one(z, mod), N) >= a if not all(is_one(self.power(u, lam, mod)) for u in units): return False for l in factor(lam): if all(is_one(self.power(u, lam // l, mod)) for u in units): return False return True # ------------------------------------------------------------ the fields class Field: """A Galois field K: O_K = Z[t]/(F), K the fixed field of H_K in Q(mu_fK), and its local towers.""" def __init__(self, name, F, fK, HK, ram, local, ef, cyc): self.name, self.F, self.fK, self.HK = name, F, fK, HK self.n = len(F) - 1 self.ram, self.local, self.ef, self.cyc = ram, local, ef, cyc self.towers = {} def tower(self, p): if p not in self.towers: e, f, h, g = self.local(p) self.towers[p] = (Tower(p, h, g), e, f, self.n // (e * f)) return self.towers[p] def residue(self, p): e, f = self.ef(p) return e, f, self.n // (e * f) def quad(d): D = d if d % 4 == 1 else 4 * d F = [-(d - 1) // 4, -1, 1] if d % 4 == 1 else [-d, 0, 1] fK = abs(D) HK = {a for a in range(1, fK + 1) if gcd(a, fK) == 1 and kronecker(D, a) == 1} ram = set(factor(abs(D))) def local(p): k = kronecker(D, p) if k == 1: return 1, 1, [0, 1], [-p, 1] if k == -1: return 1, 2, irreducible(p, 2), [-p, 1] if p == 2 and d % 4 == 3: return 2, 1, [0, 1], [1 - d, 2, 1] return 2, 1, [0, 1], [-d, 0, 1] def ef(p): k = kronecker(D, p) return (1, 1) if k == 1 else (1, 2) if k == -1 else (2, 1) name = "Q(i)" if d == -1 else f"Q(sqrt{d})" K = Field(name, F, fK, HK, ram, local, ef, False) K.D = D return K def cyc(m): F = cyclotomic(m) if m > 1 else [-1, 1] ram = set(factor(m)) if m > 1 else set() def local(p): k, m1 = 0, m while m1 % p == 0: m1 //= p k += 1 f = mult_order(p, m1) h = irreducible(p, f) g = shift1(cyclotomic(p ** k)) if k else [-p, 1] return (len(g) - 1), f, h, g def ef(p): k, m1 = 0, m while m1 % p == 0: m1 //= p k += 1 return (p ** k - p ** (k - 1) if k else 1), mult_order(p, m1) name = "Q" if m == 1 else f"Q(mu_{m})" return Field(name, F, max(m, 1), {1 % max(m, 1)} if m > 1 else {0}, ram, local, ef, True) def fields(): ds = [-1] + [d for d in range(-50, 51) if abs(d) >= 2 and all(d % (p * p) for p in (2, 3, 5, 7))] return ([cyc(1)] + [quad(d) for d in ds] + [cyc(m) for m in (3, 4, 5, 7, 8, 9, 12)]) # ----------------------------------------------------- the three objects def wall(K, L): """{p: a_p} over the p with N(P) - 1 | L.""" out = {} for p in PR: if p - 1 > L: break e, f, g = K.residue(p) if L % (p ** f - 1): continue T = K.tower(p)[0] a = T.depth(L) if a: out[p] = a return out def wall_norm(K, W): N = 1 for p, a in W.items(): e, f, g = K.residue(p) N *= p ** (f * g * a) return N def contraction(K, W): c = 1 for p, a in W.items(): e, f, g = K.residue(p) c *= p ** (-(-a // e)) return c GAL = {} def gal_exp(K, l, k): """The exponent of Gal(K(mu_(l^k))/K) in (Z/l^k)^x.""" M = l ** k fK, s, f0 = K.fK, 0, K.fK while f0 % l == 0: f0 //= l s += 1 key = (K.name, l, k) if s else (l, k) if key in GAL: return GAL[key] if s == 0: # a mod l^k and a mod fK are independent (CRT): the image is all # of (Z/l^k)^x as soon as H_K is nonempty img = [a for a in range(1, M) if a % l] else: big = l ** max(s, k) mod = big * f0 img = set() units_f0 = [b for b in range(f0) if gcd(b, f0) == 1] or [0] # CRT: x = a mod big, b mod f0 inv = pow(f0, -1, big) if big > 1 else 0 for a in range(big): if a % l == 0: continue for b in units_f0: x = (b + f0 * ((a - b) * inv % big)) % mod if (x % fK) in K.HK: img.add(a % M) break img = sorted(img) ex = 1 for a in img: ex = lcm(ex, mult_order(a, M)) GAL[key] = ex return ex def w_def(K, L): w = 1 for l in PR: if l > K.n * L + 1: break k = 0 while L % gal_exp(K, l, k + 1) == 0: k += 1 w *= l ** k return w NV = {} def place_norms(K, bound): if (K.name, bound) not in NV: out = [] for p in PR: if p > bound: break e, f, g = K.residue(p) if p ** f <= bound: out.append((p, p ** f)) NV[(K.name, bound)] = out return NV[(K.name, bound)] def w_cheb(K, L, bound=4000): w = 1 for l in PR: if l > K.n * L + 1: break m = None for p, Nv in place_norms(K, bound): if p != l: v = vp(pow(Nv, L, l ** 40) - 1, l) m = v if m is None else min(m, v) if m == 0: break w *= l ** m return w def det(M): """Bareiss, exact integers.""" M = [r[:] for r in M] n, sign, prev = len(M), 1, 1 for k in range(n - 1): if M[k][k] == 0: for i in range(k + 1, n): if M[i][k]: M[k], M[i] = M[i], M[k] sign = -sign break else: return 0 for i in range(k + 1, n): for j in range(k + 1, n): M[i][j] = (M[i][j] * M[k][k] - M[i][k] * M[k][j]) // prev prev = M[k][k] return sign * M[n - 1][n - 1] def pmul(u, w, F, mod=None): n = len(F) - 1 prod_ = [0] * (2 * n - 1) for i, a in enumerate(u): if a: for j, b in enumerate(w): prod_[i + j] += a * b for d in range(2 * n - 2, n - 1, -1): c = prod_[d] if c: prod_[d] = 0 for k in range(n): prod_[d - n + k] -= c * F[k] r = prod_[:n] return [c % mod for c in r] if mod else r def ppow(u, k, F, mod): r = [1] + [0] * (len(F) - 2) while k: if k & 1: r = pmul(r, u, F, mod) u = pmul(u, u, F, mod) k >>= 1 return r def norm(y, F): n = len(F) - 1 rows, v = [], y[:] for _ in range(n): rows.append(v) v = pmul(v, [0, 1] + [0] * (n - 2), F) if n > 1 else v return det(rows) if n > 1 else y[0] * 1 def box(n, B): return [list(t) for t in product(range(-B, B + 1), repeat=n) if any(t)] NORMS = {} def norms(K, B): key = (K.name, B) if key not in NORMS: NORMS[key] = sorted({norm(y, K.F) for y in box(K.n, B)}) return NORMS[key] def norm_wall(K, L, B, s=64): g = 0 for N in norms(K, B): if g == 0: g = abs(N ** s * (N ** L - 1)) else: g = gcd(g, pow(N, s, g) * (pow(N, L, g) - 1) % g) return g def adams_index(K, L, B, s=64): """The index in O_K of the ideal generated by W(L) and the y^s (y^L - 1), y over the box.""" n, D = K.n, adams_closed(L) basis = [[D if j == i else 0 for j in range(n)] for i in range(n)] def insert(v): v = [c % D for c in v] for i in range(n): if v[i] == 0: continue b = basis[i] g, s1, s2 = xgcd(b[i], v[i]) nb = [(s1 * x + s2 * y) for x, y in zip(b, v)] v = [(b[i] // g) * y - (v[i] // g) * x for x, y in zip(b, v)] nb[i] = g basis[i] = [nb[j] % D if j > i else nb[j] for j in range(n)] v = [c % D for c in v] tpow = [[int(j == i) for j in range(n)] for i in range(n)] for y in box(n, B): z = ppow(y, L, K.F, D) z[0] -= 1 z = pmul(ppow(y, s, K.F, D), z, K.F, D) if not any(z): continue for tj in tpow: insert(pmul(z, tj, K.F, D)) idx = 1 for i in range(n): idx *= basis[i][i] return idx def xgcd(a, b): x0, x1, y0, y1 = 1, 0, 0, 1 while b: q = a // b a, b = b, a - q * b x0, x1 = x1, x0 - q * x1 y0, y1 = y1, y0 - q * y1 if a < 0: a, x0, y0 = -a, -x0, -y0 return a, x0, y0 CAP = 40 GENS = {} def v_place(K, x, p, f, mod): """v_P(x) at the one place P over p, read off the norm, capped.""" N = norm([c % mod for c in x], K.F) % mod v = CAP * f if N == 0 else vp(N, p) assert v % f == 0 return min(v // f, CAP) def place_gens(K, p): """At the one place P over p: (t, pi), t a generator of (O/P)^x and v_P(pi) = 1, both searched over boxes of O_K growing from 2.""" if (K.name, p) not in GENS: e, f, g = K.residue(p) q, mod = p ** f, p ** (f * (CAP + 1)) rs = list(factor(q - 1)) if q > 2 else [] t, pi = None, ([p] + [0] * (K.n - 1) if e == 1 else None) for y in (y for B in range(2, p + 1) for y in box(K.n, B)): if t is None and v_place(K, y, p, f, mod) == 0 and all( v_place(K, sub1(ppow(y, (q - 1) // r, K.F, mod)), p, f, mod) == 0 for r in rs): t = y if pi is None and v_place(K, y, p, f, mod) == 1: pi = y if t is not None and pi is not None: break assert t is not None and pi is not None GENS[(K.name, p)] = (t, pi, f, mod) return GENS[(K.name, p)] def sub1(x): return [x[0] - 1] + x[1:] def depth_by_norm(K, p, L): """a_P = min over the generators t, 1 + t^j pi^b of v_P(g^L - 1), at a place alone over p; b runs while b < the running min.""" t, pi, f, mod = place_gens(K, p) F = K.F a = v_place(K, sub1(ppow(t, L, F, mod)), p, f, mod) b, pib = 1, pi while b < a: tj = [1] + [0] * (K.n - 1) for j in range(f): g = pmul(tj, pib, F, mod) g[0] += 1 a = min(a, v_place(K, sub1(ppow(g, L, F, mod)), p, f, mod)) tj = pmul(tj, t, F, mod) b += 1 pib = pmul(pib, pi, F, mod) assert a < CAP return a def prime_disc(K): if K.cyc: return False D = K.D return len(factor(abs(D))) == 1 # -------------------------------------------------------------- sections BOXES = {1: (60, 120), 2: (30, 45), 4: (4, 5), 6: (2, 3)} ABOX = {1: 30, 2: 4, 4: 1, 6: 1} def section_control(Ks): section("C CONTROLS") t0 = time.time() # C1 the tower against the whole unit group tested = bad = 0 seen = set() for K in Ks: for p in PR: if p > 61: break e, f, g = K.residue(p) if p ** f > 61: continue T = K.tower(p)[0] key = (p, tuple(T.h), tuple(T.g)) if key in seen: continue seen.add(key) a = 1 while T.q ** a <= 20000: tested += 1 if not T.whole_exponent_is(a, T.lam(a)): bad += 1 print(f" miss: {K.name} p {p} a {a}") a += 1 check("C1 (N(P) - 1) E(a) is the whole unit group's exponent, every " "ring a wall meets (N(P) <= 61), N(P)^a <= 20,000", bad == 0, f"{tested} (ring, a), {bad} off, {len(seen)} rings") rec = {"Z_2": ([0, 1], [-2, 1], [1, 2, 2, 4, 8, 16, 32, 64, 128]), "x^2 + 2": ([0, 1], [2, 0, 1], [1, 2, 4, 4, 4, 8, 8, 16, 16]), "Q_2(i)": ([0, 1], [2, 2, 1], [1, 2, 4, 4, 4, 4, 4, 8, 8]), "Q_2(sqrt -5)": ([0, 1], [6, 2, 1], [1, 2, 4, 4, 4, 4, 8, 8, 16])} ok = True for nm, (h, g, seq) in rec.items(): T = Tower(2, h, g) got = [T.E(a) for a in range(1, 10)] ok &= got == seq if got != seq: print(f" {nm}: {got} against {seq}") check("C1 E(1..9) at Z_2, x^2 + 2, Q_2(i), Q_2(sqrt -5) as " "module_law.py printed", ok) # C2 K = Q Q = Ks[0] bad = 0 for L in LS: W = wall(Q, L) WL = adams_closed(L) vals = (wall_norm(Q, W), contraction(Q, W), w_def(Q, L), norm_wall(Q, L, BOXES[1][0])) if any(v != WL for v in vals): bad += 1 print(f" Q, L {L}: {vals} against {WL}") check("C2 K = Q: N(W) = c = w = n = W(L) at every even L <= 60", bad == 0, f"{bad} off") print(f" ({time.time() - t0:.1f} s)") def run_census(Ks): section("THE CENSUS every field, every even L <= 60") t0 = time.time() R = {} for K in Ks: for L in LS: W = wall(K, L) R[(K.name, L)] = dict( W=W, NW=wall_norm(K, W), c=contraction(K, W), WL=adams_closed(L), w=w_def(K, L), n=norm_wall(K, L, BOXES[K.n][1])) print(f" {len(Ks)} fields x {len(LS)} L ({time.time() - t0:.1f} s)") return R def section_checks(Ks, R): section("C3-C8 THE SECOND ROUTES") t0 = time.time() # C3 the Adams ideal bad = n_ = 0 for K in Ks: Lset = LS if K.n <= 2 else [L for L in (2, 4, 6, 12, 24, 60) if L in LS] for L in Lset: n_ += 1 idx = adams_index(K, L, ABOX[K.n]) if idx != R[(K.name, L)]["NW"]: bad += 1 if bad <= 8: print(f" {K.name} L {L}: index {idx}, N(W) " f"{R[(K.name, L)]['NW']}") check("C3 the Adams gcd ideal over a box has index N(W_K)", bad == 0, f"{n_} (field, L), {bad} off") # C4 pairs = (("Q(mu_3)", "Q(sqrt-3)"), ("Q(mu_4)", "Q(i)")) ok = all(R[(a, L)][k] == R[(b, L)][k] for a, b in pairs for L in LS for k in ("NW", "c", "w", "n")) check("C4 Q(mu_3), Q(mu_4) agree with d = -3, -1 on N(W), c, w, n", ok) # C5 bad = 0 for K in Ks: for L in LS: if w_cheb(K, L) != R[(K.name, L)]["w"]: bad += 1 if bad <= 8: print(f" {K.name} L {L}: Chebotarev " f"{w_cheb(K, L)}, definition " f"{R[(K.name, L)]['w']}") check("C5 w by definition = w by the Chebotarev gcd, N(v) <= 4000", bad == 0, f"{len(Ks) * len(LS)} (field, L), {bad} off") # C6 hand = {"Q(i)": ({2: 2}, 2, 24, 24), "Q(sqrt-3)": ({3: 1}, 3, 24, 24), "Q(sqrt5)": ({}, 1, 120, 120), "Q(sqrt-15)": ({2: 3, 3: 1}, 24, 24, 120)} ok = True for nm, (W, c, w, n) in hand.items(): r = R[(nm, 2)] got = (r["W"], r["c"], r["w"], r["n"]) ok &= got == (W, c, w, n) print(f" {nm}, L = 2: W {r['W']} (norm {r['NW']}), c {r['c']}, " f"w {r['w']}, n {r['n']}") check("C6 the four hand values at L = 2", ok) # C7 bad = 0 for K in Ks: for L in LS: if norm_wall(K, L, BOXES[K.n][0]) != R[(K.name, L)]["n"]: bad += 1 check("C7 n read at two boxes agrees", bad == 0, f"{len(Ks) * len(LS)} (field, L), {bad} off") # C8 the depth by the norm, at every place alone over its p n_ = bad = past = 0 for K in Ks: for p in PR: e, f, g = K.residue(p) if p ** f > 61: if p > 61: break continue if g != 1: continue T = K.tower(p)[0] for L in LS: a1, a2 = T.depth(L), depth_by_norm(K, p, L) n_ += 1 bad += a1 != a2 if a1 and T.q ** a1 > 20000: past += 1 print(f" past C1: {K.name} p {p} L {L}: tower {a1}, " f"norm {a2}") elif a1 != a2: print(f" {K.name} p {p} L {L}: tower {a1}, norm {a2}") check("C8 the depth read off the norm = the tower's, every place alone " "over its p", bad == 0, f"{n_} (field, place, L), {past} past C1, {bad} off") print(f" ({time.time() - t0:.1f} s)") def section_verdict(Ks, R): section("T THE PREDICTIONS") t1 = [] t2 = [] t3 = [] t5 = [] t6 = [] for K in Ks: for L in LS: r = R[(K.name, L)] c, WL, w, n = r["c"], r["WL"], r["w"], r["n"] if WL % c or w % WL or n % w: t1.append((K.name, L)) if (K.cyc or prime_disc(K)) and n != w: t2.append((K.name, L)) if not K.cyc and K.n == 2: if L * 2 <= 120 and w_def(K, 2 * L) % n: t3.append((K.name, L, "n | w_2L")) for l in factor(n // w) if n % w == 0 else []: if l not in K.ram: t3.append((K.name, L, l)) for l in set(factor(n)) | set(factor(WL)): if l not in K.ram and vp(n, l) != vp(WL, l): t5.append((K.name, L, l)) for l in factor(w): if vp(w, l) > vp(WL, l) and l not in K.ram: t6.append((K.name, L, l)) tot = len(Ks) * len(LS) check("T1 c | W(L) | w | n at every (K, L)", not t1, f"{tot} (field, L), {len(t1)} off {t1[:5]}") nt2 = sum(len(LS) for K in Ks if K.cyc or prime_disc(K)) check("T2 n = w at every cyclotomic and prime-discriminant field", not t2, f"{nt2} (field, L), {len(t2)} off {t2[:5]}") check("T3 quadratic: n | w_2L and n / w on primes dividing D", not t3, f"{len(t3)} off {t3[:5]}") check("T5 v_l(n) = v_l(W(L)) at every l unramified in K", not t5, f"{len(t5)} off {t5[:5]}") check("T6 v_l(w) > v_l(W(L)) only at l ramified in K", not t6, f"{len(t6)} off {t6[:5]}") def section_observed(Ks, R): section("O OBSERVED") tot = len(Ks) * len(LS) cW = sum(r["c"] == r["WL"] for r in R.values()) wW = sum(r["w"] == r["WL"] for r in R.values()) nw = [(k, r["n"] // r["w"]) for k, r in R.items() if r["n"] != r["w"]] triv = sum(r["NW"] == 1 for r in R.values()) print(f" c = W(L) at {cW} of {tot}; w = W(L) at {wW} of {tot}; " f"W_K = (1) at {triv} of {tot}; n != w at {len(nw)} of {tot}") byK = {} for (nm, L), q in nw: byK.setdefault(nm, []).append((L, q)) for nm, rows in byK.items(): print(f" n / w at {nm}: {rows[:6]}{' ...' if len(rows) > 6 else ''}" f" ({len(rows)} L)") odd, two, form = {}, [], 0 for nm, rows in byK.items(): for L, q in rows: for l, e in factor(q).items(): if l > 2: form += (e == 1 + vp(L, l) and L % ((l - 1) // 2) == 0 and L % (l - 1) != 0) odd.setdefault(l, set()).add(nm) if len(rows) == len(LS) and all(q % 4 == 2 for L, q in rows): two.append(nm) nodd = sum(1 for (nm, L), q in nw for l in factor(q) if l > 2) print(f" {len(byK)} fields with n != w; odd (field, L, l) in n / w: " f"{nodd}, " f"of the form l^(1 + v_l(L)), (l - 1)/2 | L, (l - 1) not | L: " f"{form}") for l in sorted(odd): print(f" l = {l}: {sorted(odd[l])}") print(f" 2 || n / w at every L: {two}") print(" per field at L = 2, 12, 60: (N(W), c, W(L), w, n)") for K in Ks: row = [(R[(K.name, L)]["NW"], R[(K.name, L)]["c"], R[(K.name, L)]["WL"], R[(K.name, L)]["w"], R[(K.name, L)]["n"]) for L in (2, 12, 60)] print(f" {K.name:12s} {row}") def main(): t0 = time.time() Ks = fields() print(f"numwall.py: {len(Ks)} fields, L over every even L <= 60") section_control(Ks) R = run_census(Ks) section_checks(Ks, R) section_verdict(Ks, R) section_observed(Ks, R) print() print(f"{sum(CHECKS)}/{len(CHECKS)} checks PASS " f"({time.time() - t0:.1f} s)") return 0 if all(CHECKS) else 1 if __name__ == "__main__": sys.exit(main())