"""numchar.py -- n_L(K) / w_L(K) over an abelian field, by its characters. QUESTION. numwall.py and numgap.py read the gap n / w over Q(mu_m) (none) and over quadratic fields (whole). Over an abelian field K, the fixed field of H_K in (Z/f)^x = prod_p U_p, U_p = (Z/p^(a_p))^x, does the gap read off K's characters? THE OBJECTS. At a prime l, the SLICE S_l = {u in U_l : (u, 1, ..., 1) in H_K} and the SHADOW P_l = the projection of H_K to U_l, both lifted to Z_l^x. Dually S_l is the common kernel of the l-components of every character of K, P_l that of the l-pure characters. THE ARGUMENT (written before the engine; its local input cited after the run). G_l = P_l: Gal(K(mu_(l^oo))/K) is the set of u with some (x_p (p != l), u) in H_K, Galois theory of Q(mu_(f l^oo)). N_l in S_l: for a local unit y_l take a global y in O_K, y = y_l to high l-adic order and y = 1 mod p^(a_p) at the other p | f. Then N(y) mod f is (N(y_l), 1, ..., 1), and |N(y)| is the norm of the ideal (y), a product of p^(f_p), f_p the order of p in (Z/f)^x / H_K (the decomposition law), so it lies in H_K; -1 does when N(y) < 0, since K then has a real place. S_l in N_l: [U_l : S_l] is the order of the inertia group at l in (Z/f)^x / H_K, so e_l(K); local class field theory gives [Z_l^x : N_l] = e_l at an abelian K_lambda / Q_l. Equality. The local input is Milne, Class Field Theory v4.03 (2020), I, Theorem 1.1: (K^x : Nm L^x) = [L : K] at a finite abelian L / K of local fields; and the proof of I, Lemma 1.3: Nm L^x cap U_K = Nm U_L. The valuation takes Nm L^x onto f Z, so [U_K : Nm U_L] = e. The inclusion needs only the chain's own lemma (the unit norms mod m lie in Gal(K(mu_m)/K), Frobenius acting as the norm) at m = f, which reads N(y) mod f in H_K for every y prime to f. GUESS: v_l(n) and v_l(w) are read off S_l and P_l. DESIGN. Standard library and numwall.py. A field is (f, generating characters), each character a map (Z/f)^x -> Z/12 (orders 2, 3, 4): quadratic characters by the Kronecker symbol, order 3 and 4 by the index at a primitive root mod p or 9, and at 16 by a = +-5^j. O = Z[theta], theta = sum over H_K of zeta_f^h + t zeta_f^(2h), the least t >= 0 with distinct conjugates, its minimal polynomial from floating conjugates rounded and checked. O need not be O_K, so the box reads N_l by the VALUATION TRICK: over the norms N of a box, at v = v_l(N), N / N0 (N0 the first norm at that v) and, when deg K | v, N / l^v, each the norm of an l-adic element of unit norm, so in N_l because K is Galois (every place over l has one norm group A, and A meets Z_l^x in N_l; at two places with different norm groups a product of norms can leave N_l); y = l^r u covers every local unit u once the box holds l^r O_K. The group B they generate lies in N_l, so n_guess | n_true | n_box, and equality of n_box and n_guess CERTIFIES n at that (K, L). Exponents mod l^k are lcms of generator orders; v_l at L is the largest k with the exponent mod l^k dividing L. w by numwall's definition. Boxes: half-widths 30, 45 at degree 2; 8, 12 at 3; 6, 8 at 4. Fields: biquadratic Q(sqrt D1, sqrt D2), every pair of fundamental discriminants with conductor <= 60; cyclic cubic at conductors 7, 9, 13, 19, 63, 91, 117, 133 (every field); cyclic quartic: order-4 characters at 5, 13, 16 (both) alone and times chi_(-3), chi_(-4), chi_8, chi_(-8) where the conductor stays <= 65, and chi_5 chi_13 of order 4. Every L <= 60. C CONTROLS, read first: C1 Q(i) through the order Z[3i] (F = t^2 + 9) at L = 1: units of the order give n = 12, the trick gives n = w = 4. C2 the shadow's v_l equals w by definition at every field, l, L. C3 the guess reproduces numgap.py's law at its 61 quadratic fields and n = w at numwall.py's Q(mu_m), every L <= 60, w by its definition. C4 the hand values (n / w at L = 1, 2, 4, 12): Q(i, sqrt 5) 1, 1, 1, 1; Q(sqrt -3, sqrt -5) 2, 5, 1, 1; the cubic of conductor 63 1, 21, 21, 3; of 91 1, 7, 91, 1; the quartic chi_5 chi_(-3) of conductor 15: 15, 1, 1, 1. PREDICTIONS AND KILLS, frozen before the engine. T1 n_box = n_guess at every (field, L), the two boxes agreeing. A KILL is one printed (field, L) where n_box != n_guess with the two boxes agreeing; boxes that disagree fail the instrument there. OBSERVED: the fields and L with n != w, and the shapes of the gaps. FINDINGS (from the printed run, 6/6 checks PASS). C C1 units of Z[3i] give n = 12 at L = 1, the trick n = w = 4. C2 at 3480 (field, L), 0 off. C3 at 61 quadratic and 7 cyclotomic fields, every L <= 60, 0 off. C4 every hand value. The frozen boxes (4, 6) at degree 4 disagreed at 60 (field, L), 30 at each of Q(sqrt -1, sqrt -10) and Q(sqrt -3, sqrt -5) (theta^4 = -25 and its kin, an order deep at 5), the small box reading n 5, 25 or 125 times too big; redesigned to (6, 8), the two boxes agree everywhere. T1 held at 3480 (field, L) over 58 fields (33 biquadratic of conductor <= 60, 12 cyclic cubic of conductor <= 133, 13 cyclic quartic of conductor <= 65), 0 off: the box at its larger size equals the guess, so n is CERTIFIED and N_l is read off the slice at every (field, L) run. The guess with the shadow in place of the slice, in a scratch copy, misses T1 at 1189 and C3 at 1363. O n = w at every L at 28 fields: every prime-power-conductor cubic and quartic (7, 9, 13, 19; 5, 13, 16 both) and 20 biquadratic fields, Q(i, sqrt 5) among them, the compositum closing Q(sqrt -5)'s gaps. Gaps no quadratic field has: 4 || n / w at odd L over Q(sqrt 2, sqrt 3), Q(sqrt -2, sqrt 3), Q(sqrt 2, sqrt 7), Q(sqrt -2, sqrt 7), Q(sqrt 2, sqrt -5), Q(sqrt -2, sqrt -5) (S_2 = 1 + 8Z_2 against a shadow of 2-pure chi_8 or chi_(-8)); 2 at every L over Q(i, sqrt -10), Q(i, sqrt -14), Q(i, sqrt -6); a wild 3 of fixed size at every even L over the cubics of conductor 63 and 117 (S_3 = +-(1 + 9Z_3)); gaps at odd L only over C4[5*-3] (15 at L = 1, 45 at 3, 75 at 5), C4[5*-4], C4[5*-8], C4[13*-3], C4[13*-4] and C4[16-*-3], not C4[16+*-3] nor C4[5*8] (2 at even L); and at the quartic chi_5 chi_13, 5^(1 + v_5(L)) where 4 does not divide L and 13^(1 + v_13(L)) where 3 | L, 12 not | L. RUN RECORD. 64.8 s, peak commit 66.8 MB (first run, boxes (4, 6): 37.8 s, 36.7 MB). """ import cmath import os import sys import time from math import gcd sys.path.insert(0, os.path.dirname(os.path.abspath(__file__))) import numwall as nw # noqa: E402 import numgap as ng # noqa: E402 CHECKS = [] LS = list(range(1, 61)) def check(name, ok, detail=""): CHECKS.append(bool(ok)) print(f" [{'PASS' if ok else 'FAIL'}] {name}" + (f" -- {detail}" if detail else "")) # ------------------------------------------------------------ characters def units(f): return [a for a in range(1, f + 1) if gcd(a, f) == 1] if f > 1 else [0] def quad_char(D): return lambda a: 0 if nw.kronecker(D, a) == 1 else 6 def index_table(m): """a mod m -> index at a generator of (Z/m)^x, m an odd prime power.""" phi = len(units(m)) for g in range(2, m): if gcd(g, m) == 1 and nw.mult_order(g, m) == phi: t, x = {}, 1 for i in range(phi): t[x] = i x = x * g % m return t raise ValueError(m) def char_odd(m, order, s=1): t = index_table(m) return lambda a: (12 // order) * (s * t[a % m]) % 12 def char16(s, odd): """order 4 at 16: a = (-1)^e 5^j -> 3 (s j) + 6 e odd.""" t = {} for e in (0, 1): for j in range(4): t[(-1) ** e * pow(5, j, 16) % 16] = (e, j) def chi(a): e, j = t[a % 16] return (3 * s * j + 6 * e * odd) % 12 return chi class Ab: """An abelian field: the fixed field of H_K in Q(mu_f).""" def __init__(self, name, f, chars): self.name, self.fK, self.cyc = name, f, False self.HK = {a for a in units(f) if all(c(a) == 0 for c in chars)} self.n = len(units(f)) // len(self.HK) self.F = period_poly(f, self.HK, self.n) def period_poly(f, H, n): if n == 1: return [-1, 1] z = [cmath.exp(2j * cmath.pi * k / f) for k in range(f)] reps, seen = [], set() for c in units(f): if c not in seen: reps.append(c) seen |= {c * h % f for h in H} for t in range(6): roots = [sum(z[c * h % f] + t * z[2 * c * h % f] for h in H) for c in reps] if min(abs(a - b) for i, a in enumerate(roots) for b in roots[i + 1:]) < 1e-6: continue P = [1 + 0j] for r in roots: P = [0j] + P for i in range(len(P) - 1): P[i] -= r * P[i + 1] F = [round(c.real) for c in P] assert all(abs(c - F[i]) < 1e-6 for i, c in enumerate(P)), P return F raise ValueError((f, n)) def fundamental(lim): out = [] for D in range(-lim, lim + 1): if D in (0, 1): continue if D % 4 == 1 and all(D % (p * p) for p in nw.PR[:6]): out.append(D) elif D % 4 == 0 and (D // 4) % 4 in (2, 3) and \ all((D // 4) % (p * p) for p in nw.PR[:6]): out.append(D) return out def sqfree(D): return D // 4 if D % 4 == 0 else D def biquadratics(lim): Ds, seen, out = fundamental(lim), set(), [] for i, D1 in enumerate(Ds): for D2 in Ds[i + 1:]: f = nw.lcm(abs(D1), abs(D2)) if f > lim: continue d3 = sqfree(D1) * sqfree(D2) g = gcd(sqfree(D1), sqfree(D2)) d3 //= g * g key = frozenset((sqfree(D1), sqfree(D2), d3)) if key in seen: continue seen.add(key) e1, e2 = sorted(key, key=lambda d: (abs(d), d))[:2] out.append(Ab(f"Q(sqrt{e1},sqrt{e2})", f, [quad_char(D1), quad_char(D2)])) return out def cubics(): out = [] for f, ps in ((7, (7,)), (9, (9,)), (13, (13,)), (19, (19,)), (63, (7, 9)), (91, (7, 13)), (117, (9, 13)), (133, (7, 19))): tags = ((((1,), ""),) if len(ps) == 1 else (((1, 1), "a"), ((1, 2), "b"))) for s2, tag in tags: chs = [char_odd(p, 3, si) for p, si in zip(ps, s2)] out.append(Ab(f"C3[{f}{tag}]", f, [lambda a, chs=chs: sum(c(a) for c in chs) % 12])) return out def quartics(): base = [("5", 5, char_odd(5, 4)), ("13", 13, char_odd(13, 4)), ("16+", 16, char16(1, 0)), ("16-", 16, char16(1, 1))] quads = [("-3", -3), ("-4", -4), ("8", 8), ("-8", -8)] out = [] for nm, m, c in base: out.append(Ab(f"C4[{nm}]", m, [c])) for qn, D in quads: f = nw.lcm(m, abs(D)) if f > 65 or (m == 16 and D % 2 == 0): continue q = quad_char(D) out.append(Ab(f"C4[{nm}*{qn}]", f, [lambda a, c=c, q=q: (c(a) + q(a)) % 12])) c5, c13 = char_odd(5, 4), char_odd(13, 4) out.append(Ab("C4[5*13]", 65, [lambda a: (c5(a) + c13(a)) % 12])) return out # ------------------------------------------------------------- exponents def kmax(l): k = 1 while l ** (k - 3) <= 61: k += 1 return k + 1 def order_lk(g, l, k): """The order of g in (Z/l^k)^x, g prime to l.""" if k == 0 or l ** k == 2: return 1 m = l ** k g %= m if l == 2: if g % 4 == 1: return 2 ** max(0, k - nw.vp(g - 1, 2)) if g != 1 else 1 if k == 2: return 2 v = nw.vp(g * g - 1, 2) if g * g % m != 1 else k return 2 * 2 ** max(0, k - v) t = nw.mult_order(g % l, l) u = pow(g, t, m) v = nw.vp(u - 1, l) if u != 1 else k return t * l ** max(0, k - v) def exps(gens, l): """[exponent mod l^k for k = 0..kmax(l)] of the group the gens make.""" K = kmax(l) out = [1] * (K + 1) for g in gens: for k in range(1, K + 1): out[k] = nw.lcm(out[k], order_lk(g, l, k)) return out def vl_at(ex, L): k = 0 while k + 1 < len(ex) and L % ex[k + 1] == 0: k += 1 assert k < len(ex) - 1, (ex, L) return k def local_gens(K, l): """Generators of the slice and of the shadow at l, lifted.""" f, a = K.fK, 0 while f % l == 0: f //= l a += 1 a1 = max(a, 3 if l == 2 else 1) m = l ** a1 if a == 0: U = [u for u in range(1, m) if u % l] return U + [1 + m], U + [1 + m] big = l ** a inv = pow(f, -1, big) sl, sh = set(), set() for x in K.HK: sh.add(x % big) for u in range(1, big): if u % l == 0: continue x = (1 + f * ((u - 1) * inv % big)) % K.fK if x in K.HK: sl.add(u) lift = lambda S: [u for u in range(1, m) if u % l and u % big in S] return lift(sl) + [1 + m], lift(sh) + [1 + m] LOCAL = {} def guess_exps(K, l): key = (K.name, l) if key not in LOCAL: s, p = local_gens(K, l) LOCAL[key] = (exps(s, l), exps(p, l)) return LOCAL[key] def n_guess(K, L, which=0): n = 1 for l in nw.PR: if l > K.n * L + 1: break n *= l ** vl_at(guess_exps(K, l)[which], L) return n # ------------------------------------------------------------- the box BOXV = {} def box_exps(K, l, B): key = (K.name, l, B) if key in BOXV: return BOXV[key] K_ = kmax(l) mod = l ** K_ first, gens = {}, set() full = None if K.fK % l: full = exps([u for u in range(1, l ** (3 if l == 2 else 1) + 1) if u % l] + [1 + l ** (3 if l == 2 else 1)], l) seen = 0 for N in nw.norms(K, B): v = nw.vp(N, l) u = (N // l ** v) % mod if v % K.n == 0: gens.add(u) if v in first: gens.add(u * pow(first[v], -1, mod) % mod) else: first[v] = u if full and len(gens) >= seen + 16: seen = len(gens) if exps(gens, l) == full: break BOXV[key] = exps(gens, l) return BOXV[key] def n_box(K, L, B): n = 1 for l in nw.PR: if l > K.n * L + 1: break n *= l ** vl_at(box_exps(K, l, B), L) return n BOXES = {2: (30, 45), 3: (8, 12), 4: (6, 8)} # ------------------------------------------------------------- sections def section_control(): print("C CONTROLS") K = Ab("Q(i) by Z[3i]", 4, [quad_char(-4)]) K.F = [9, 0, 1] plain = nw.norm_wall(K, 1, 45) trick = n_box(K, 1, 45) w = nw.w_def(K, 1) check("C1 Q(i) through Z[3i], L = 1: units give 12, the trick 4 = w", (plain, trick, w) == (12, 4, 4), f"units {plain}, trick {trick}, " f"w {w}") quads = [K for K in nw.fields() if not K.cyc] cycs = [K for K in nw.fields() if K.cyc and K.name != "Q"] off = [(K.name, L) for K in quads for L in LS if n_guess(K, L) != ng.gap_law(K.D, L) * nw.w_def(K, L)] off += [(K.name, L) for K in cycs for L in LS if n_guess(K, L) != nw.w_def(K, L)] check("C3 the slice reproduces the quadratic law and n = w at Q(mu_m)", not off, f"{len(quads)} quadratic, {len(cycs)} cyclotomic fields, " f"every L <= 60, {len(off)} off {off[:4]}") return quads + cycs def section_census(Ks): print("T THE CENSUS") c2, R, boxoff = [], {}, [] for K in Ks: b1, b2 = BOXES[K.n] for L in LS: w = nw.w_def(K, L) ng_, ns = n_guess(K, L), n_guess(K, L, 1) if ns != w: c2.append((K.name, L, ns, w)) n1, n2 = n_box(K, L, b1), n_box(K, L, b2) if n1 != n2: boxoff.append((K.name, L, n1, n2)) R[(K.name, L)] = (w, ng_, n2) check("C2 the shadow's w equals w by definition", not c2, f"{len(R)} (field, L), {len(c2)} off {c2[:3]}") check("C the two boxes agree", not boxoff, f"{len(boxoff)} off {boxoff[:4]}") hand = {"Q(sqrt-1,sqrt-5)": (1, 1, 1, 1), "Q(sqrt-3,sqrt-5)": (2, 5, 1, 1), "C3[63a]": (1, 21, 21, 3), "C3[63b]": (1, 21, 21, 3), "C3[91a]": (1, 7, 91, 1), "C3[91b]": (1, 7, 91, 1), "C4[5*-3]": (15, 1, 1, 1)} got = {nm: tuple(R[(nm, L)][1] // R[(nm, L)][0] for L in (1, 2, 4, 12)) for nm in hand if (nm, 1) in R} check("C4 the hand values of n / w at L = 1, 2, 4, 12", got == hand, f"{sorted(got.items())}") kill = [(nm, L, n, g) for (nm, L), (w, g, n) in R.items() if n != g and (nm, L) not in {(a, b) for a, b, _, _ in boxoff}] check("T1 n_box = n_guess at every (field, L)", not kill, f"{len(R)} (field, L) over {len(Ks)} fields, {len(kill)} off " f"{kill[:4]}") return R def section_observed(Ks, R): print("O OBSERVED") for K in Ks: gaps = {L: R[(K.name, L)][1] // R[(K.name, L)][0] for L in LS} nz = {L: g for L, g in gaps.items() if g > 1} if nz: fac = sorted({p for g in nz.values() for p in nw.factor(g)}) print(f" {K.name:24s} f {K.fK:3d} deg {K.n}: gap primes " f"{fac} at {len(nz)} L; L = 1..12: " f"{[gaps[L] for L in range(1, 13)]}") none = [K.name for K in Ks if all(R[(K.name, L)][1] == R[(K.name, L)][0] for L in LS)] print(f" n = w at every L: {len(none)} fields: {none}") def main(): t0 = time.time() section_control() Ks = biquadratics(60) + cubics() + quartics() print(f"numchar.py: {len(Ks)} fields " f"({sum(K.n == 4 for K in Ks)} quartic, " f"{sum(K.n == 3 for K in Ks)} cubic), every L <= 60") R = section_census(Ks) section_observed(Ks, R) 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())