"""numcubic.py -- n_L(K) / w_L(K) at a cubic field that is not Galois. QUESTION. numchar.py reads the gap n / w over an abelian field off the slice and the shadow of H_K. At a cubic K that is not Galois there is no H_K. Is n / w read off the local abelian parts of K at each l? THE ARGUMENT (written before the engine). Norm limitation (Milne, Class Field Theory v4.03 (2020), III, Theorem 3.5): Nm K_lam^x = Nm E_lam^x, E_lam the largest abelian subextension of K_lam / Q_l. At any finite K_lam, v_l(Nm x) = f v_lam(x), so Nm K_lam^x meets Z_l^x in Nm U_lam, which is therefore Nm U_E, of index e(E_lam / Q_l). N_l is generated by the Nm U_lam over lam | l. And G_l = Gal(Q(mu_(l^oo)) / K cap Q(mu_(l^oo))), Q(mu_(l^oo)) being Galois over Q. At a cubic that is not Galois, K has no subfield but Q and K, so K cap Q(mu_(l^oo)) = Q: G_l = Z_l^x, w = W(L) at every L. A gap at l needs every place over l ramified, so l totally ramified, one place, K_lam a cubic; E_lam = K_lam when K_lam / Q_l is Galois (disc(F) a square in Q_l), else Q_l. A tame Galois K_lam has l = 1 mod 3 (mu_3 in Q_l), and then always is. GUESS. N_l = Z_l^x except at l totally ramified with disc(F) a square in Q_l, where N_l is the index-3 subgroup: at l = 1 mod 3 the u with u^((l - 1)/3) = 1 mod l; at l = 3, +-(1 + 9Z_3), the one open subgroup of index 3 in Z_3^x. So n / w = prod gamma_l, gamma_l = l^(1 + v_l(L)) at tame l if (l - 1)/3 | L and l - 1 does not, gamma_3 = 3 at even L, 1 otherwise. DESIGN. Standard library, numwall.py and numchar.py. A field is a monic F = x^3 + a x^2 + b x + c, O = Z[t]/(F). At every l with l^2 | disc(F), Dedekind's criterion (F = prod g_i^(e_i) mod l, T = (F - prod g_i * prod g_i^(e_i - 1)) / l, l-maximal iff no g_i with e_i >= 2 divides T mod l) is required, a searched field failing it skipped (no pure cubic of the list fails), so O is l-maximal wherever l ramifies or divides disc(F), the splitting type is read off F mod l, and the plain units y of the box (l not | N(y)) are local units of O_K (x) Z_l: the group B their norms make lies in N_l, so n | n_box, and with N_l = N_guess (the argument) agreement of n_box and n_guess CERTIFIES n at that (K, L). Exponents mod l^k by numchar.py's exps, v_l at L by its vl_at. w by the Chebotarev form: v_l(w) <= the least v_l(N(v)^L - 1) over places v of K off l, N(v) = p^f <= 4000, the f read per place off the roots of F mod p (gcd with x^p - x); W(L) by its definition, the largest m with lambda(m) | L. Boxes: half-widths 8 and 12. Fields: pure cubics Q(m^(1/3)), m squarefree, 2 <= m <= 70, m not +-1 mod 9; every x^3 + a x^2 + b x + c with |a| <= 1, |b|, |c| <= 12, irreducible, disc(F) not a square, Dedekind passing at every l with l^2 | disc(F), one per value of disc(F). Every L <= 60. C CONTROLS, read first: C1 POSITIVE CONTROL: the guess's local recipe (splitting type off F mod l, the square test, the index-3 groups) on numchar.py's 12 cyclic cubic fields equals its slice reading at every L <= 60 (gaps at conductors 63, 91, 117, 133), where its Dedekind test passes; the fields where it does not are printed. C2 the Chebotarev form equals W(L) at every field that is not Galois, every L <= 60 (G_l = Z_l^x), and w_def at C1's fields. C3 the hand values of n / w at L = 1, 2, 4, 12: Q(7^(1/3)) 1, 7, 7, 1; Q(13^(1/3)) 1, 1, 13, 1; x^3 - 3x - 8 (disc -1620, Eisenstein at 3 after x -> x - 1, -20 a square in Q_3) 1, 3, 3, 3; Q(2^(1/3)), Q(3^(1/3)), Q(5^(1/3)) 1, 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, or one (field, L) where C2 is off W(L); boxes that disagree fail the instrument there. OBSERVED: the fields with a gap, the prime and the local type. FINDINGS (from the printed run, 5/5 checks PASS). C C1 at 360 (field, L) over the 6 cyclic cubics where Dedekind's test passes (conductors 7, 9, 13, 19 and one field each at 63 and 117, both with gaps), 0 off; it fails at the other 6, each at an unramified prime (2 at 63a, 91a, 117b, 133a; 3 at 91b, 133b), where the recipe still reads F mod l and answers Z_l^x, right there by the unramified place alone. C2 at 32280 (field, L), 0 off: w = W(L) at every field run. C3 every hand value. The two boxes agree everywhere. T1 held at 32280 (field, L) over 538 cubic fields not Galois (33 pure, 505 from the search), 0 off: the box equals the guess, so n is CERTIFIED at every (field, L) run, the box reaching the full Z_l^x at the 210 totally ramified places that are not Galois and exactly the index-3 group at the 28 that are. Of the 210, the 71 at l = 3 (printed under O) test the argument; at l = 2 and l = 2 mod 3 (139) Z_l^x has no open subgroup of index 3, so they test the box alone. O The ramified (field, l), l <= 181: 668 with a place of e = 1, 210 totally ramified not Galois, 23 totally ramified tame cyclic, 5 totally ramified wild cyclic (at 3). n = w at every L at 510 of the 538 fields; each of the other 28 has one cyclic l: every pure cubic run with a prime 1 mod 3 dividing m (14: m = 7, 13, 14, 21, 31, 38, 39, 42, 43, 57, 61, 65, 67, 70), 9 searched fields at 7 or 13 (discriminants 2597, -1176, -931, -588, -2891, -8619, -6468, -7007, -2695), and at 3 the 5 of discriminant 4212, 6885, -1620, -3564, -891, each 3 at every even L. RUN RECORD. 123.1 s from code/, peak commit 28.9 MB (rehearsal at |b|, |c| <= 2: 46 fields, 328.7 s before the box's exponents were made incremental and the Chebotarev scan stopped at v_l(W(L)); 13.3 s after). """ import os import sys import time from math import gcd, isqrt sys.path.insert(0, os.path.dirname(os.path.abspath(__file__))) import numwall as nw # noqa: E402 import numchar as nc # noqa: E402 CHECKS = [] LS = list(range(1, 61)) BOXES = (8, 12) def check(name, ok, detail=""): CHECKS.append(bool(ok)) print(f" [{'PASS' if ok else 'FAIL'}] {name}" + (f" -- {detail}" if detail else "")) # ------------------------------------------------------------ the field def disc3(F): c, b, a = F[0], F[1], F[2] return (a * a * b * b - 4 * b ** 3 - 4 * a ** 3 * c - 27 * c * c + 18 * a * b * c) def is_square(n): return n >= 0 and isqrt(n) ** 2 == n def roots_mod(F, p): """The roots of F mod p with multiplicity, by trial.""" out, G = [], [x % p for x in F] for r in range(p): while len(G) > 1: q, rem = synth(G, r, p) if rem: break out.append(r) G = q return out, G def synth(G, r, p): """G / (x - r) mod p, G low to high: (quotient, remainder).""" n = len(G) - 1 q = [0] * n acc = 0 for i in range(n, 0, -1): acc = (acc * r + G[i]) % p q[i - 1] = acc rem = (acc * r + G[0]) % p return q, rem def pmulmod(u, v, p): out = [0] * (len(u) + len(v) - 1) for i, a in enumerate(u): for j, b in enumerate(v): out[i + j] = (out[i + j] + a * b) % p return out def pdivmod(u, v, p): u = u[:] inv = pow(v[-1], -1, p) q = [0] * max(1, len(u) - len(v) + 1) while len(u) >= len(v) and any(u): c = u[-1] * inv % p s = len(u) - len(v) q[s] = c for i, b in enumerate(v): u[s + i] = (u[s + i] - c * b) % p while len(u) > 1 and u[-1] == 0: u.pop() if len(u) < len(v): break while len(u) > 1 and u[-1] == 0: u.pop() return q, u def factor_mod(F, p): """[(g_i, e_i)] with F = prod g_i^(e_i) mod p, g_i monic, F cubic or a product of linear factors mod p.""" rs, rest = roots_mod(F, p) out = {} for r in rs: out[((-r) % p, 1)] = out.get(((-r) % p, 1), 0) + 1 fac = [(list(k), e) for k, e in out.items()] if len(rest) > 1: inv = pow(rest[-1], -1, p) fac.append(([x * inv % p for x in rest], 1)) return fac def dedekind_ok(F, p): fac = factor_mod(F, p) G, H = [1], [1] for g, e in fac: G = pmul_z(G, g) for _ in range(e - 1): H = pmul_z(H, g) GH = pmul_z(G, H) T = [(F[i] - (GH[i] if i < len(GH) else 0)) for i in range(len(F))] assert all(t % p == 0 for t in T), (F, p, fac) T = [t // p % p for t in T] while len(T) > 1 and T[-1] == 0: T.pop() for g, e in fac: if e >= 2: if not any(T): return False _, r = pdivmod(T, g, p) if not any(r): return False return True def pmul_z(u, v): out = [0] * (len(u) + len(v) - 1) for i, a in enumerate(u): for j, b in enumerate(v): out[i + j] += a * b return out def split_type(F, p): """[(e, f)] per place over p, O assumed p-maximal.""" return sorted((e, len(g) - 1) for g, e in factor_mod(F, p)) def nroots(F, p): """deg gcd(F, x^p - x) mod p: the roots of a monic F of any degree, p not | disc.""" Fm = [x % p for x in F] r, base, k = [1], [0, 1], p while k: if k & 1: r = pdivmod(pmulmod(r, base, p), Fm, p)[1] base = pdivmod(pmulmod(base, base, p), Fm, p)[1] k >>= 1 r = r + [0] * (2 - len(r) + 1) r[1] = (r[1] - 1) % p while len(r) > 1 and r[-1] == 0: r.pop() a, b = Fm[:], r while len(b) > 1 or b[0]: a, b = b, pdivmod(a, b, p)[1] return len(a) - 1 class Cubic: def __init__(self, name, F): self.name, self.F, self.n = name, F, 3 self.D = disc3(F) self.ram = [p for p in nw.factor(abs(self.D))] self.maximal = all(dedekind_ok(F, p) for p in self.ram if self.D % (p * p) == 0) def square_in_Ql(D, l): v = nw.vp(D, l) if v % 2: return False u = D // l ** v if l == 2: return u % 8 == 1 return pow(u % l, (l - 1) // 2, l) == 1 # ------------------------------------------------------------- the guess def full_gens(l): m = l ** (3 if l == 2 else 1) return [u for u in range(1, m) if u % l] + [1 + m] def guess_gens(K, l): """Generators of N_guess in Z_l^x and the local type, a label.""" if K.D % l: return full_gens(l), "unramified" t = split_type(K.F, l) if any(e == 1 for e, f in t): return full_gens(l), "partly unramified" assert t == [(3, 1)], (K.name, l, t) if not square_in_Ql(K.D, l): return full_gens(l), "total, not Galois" if l == 3: return [26, 10], "total wild, cyclic" assert l % 3 == 1, (K.name, l) sub = [u for u in range(1, l) if pow(u, (l - 1) // 3, l) == 1] return sub + [1 + l], "total tame, cyclic" GEX = {} def guess_exps(K, l): key = (K.name, l) if key not in GEX: g, lab = guess_gens(K, l) GEX[key] = (nc.exps(g, l), lab) return GEX[key] def n_guess(K, L): n = 1 for l in nw.PR: if l > 3 * L + 1: break n *= l ** nc.vl_at(guess_exps(K, l)[0], L) return n # ------------------------------------------------------------- the box def box_norms(K, B): return sorted({nw.norm(y, K.F) for y in nw.box(3, B)}) def box_exps_all(K, B): """{l: exps of the plain unit norms mod l^k} for l <= 181.""" Ns = box_norms(K, B) out = {} for l in nw.PR: if l > 181: break K_ = nc.kmax(l) mod = l ** K_ full = nc.exps(full_gens(l), l) cur, gens = [1] * (K_ + 1), set() for N in Ns: u = N % mod if N % l == 0 or u in gens: continue gens.add(u) for k in range(1, K_ + 1): cur[k] = nw.lcm(cur[k], nc.order_lk(u, l, k)) if cur == full: break out[l] = cur return out def n_from(ex, L): n = 1 for l in nw.PR: if l > 3 * L + 1: break n *= l ** nc.vl_at(ex[l], L) return n # ------------------------------------------------------------------- w def carmichael(l, k): if l == 2: return 1 if k == 1 else 2 ** (k - 2) if k >= 3 else 2 return (l - 1) * l ** (k - 1) def W(L): m = 1 for l in nw.PR: if l > L + 1: break k = 0 while L % carmichael(l, k + 1) == 0: k += 1 m *= l ** k return m def place_norms(K, bound=4000): out = [] for p in nw.PR: if p > bound: break if K.D % p == 0: continue r = nroots(K.F, p) fs = {3: (1, 1, 1), 1: (1, 2), 0: (3,)}[r] out += [p ** f for f in fs if p ** f <= bound] return out def w_cheb(K, L, places): """The least v_l(N(v)^L - 1), stopping at v_l(W(L)), which every N(v) prime to l reaches.""" w, WL = 1, W(L) for l in nw.PR: if l > 3 * L + 1: break floor, m = nw.vp(WL, l), None for Nv in places: if Nv % l: v = nw.vp(pow(Nv, L, l ** 40) - 1, l) m = v if m is None else min(m, v) if m == floor: break w *= l ** m return w # --------------------------------------------------------------- fields def sqfree_int(m): return all(m % (p * p) for p in nw.PR if p * p <= m) def pure(): return [Cubic(f"Q({m}^(1/3))", [-m, 0, 0, 1]) for m in range(2, 71) if sqfree_int(m) and m % 9 not in (1, 8)] def has_root(F): c = F[0] for r in range(1, abs(c) + 1): if c % r == 0: for s in (r, -r): if sum(a * s ** i for i, a in enumerate(F)) == 0: return True return False def searched(lim=12, seen=()): out, seen = [], set(seen) for a in (-1, 0, 1): for b in range(-lim, lim + 1): for c in range(-lim, lim + 1): F = [c, b, a, 1] if c == 0 or has_root(F): continue D = disc3(F) if D in seen or is_square(D): continue K = Cubic(f"x^3{a:+d}x^2{b:+d}x{c:+d}", F) if not K.maximal: continue seen.add(D) out.append(K) return out # ------------------------------------------------------------- sections def section_control(): print("C CONTROLS") off, skipped, rows = [], [], 0 for A in nc.cubics(): K = Cubic(A.name, A.F) if not K.maximal: skipped.append((A.name, K.D)) continue for L in LS: rows += 1 if n_guess(K, L) != nc.n_guess(A, L): off.append((A.name, L, n_guess(K, L), nc.n_guess(A, L))) ex = box_exps_all(K, BOXES[1]) off += [(A.name, L, "box") for L in LS if n_from(ex, L) != nc.n_guess(A, L)] pl = place_norms(K) off += [(A.name, L, "w") for L in LS if w_cheb(K, L, pl) != nw.w_def(A, L)] check("C1 the local recipe and the box equal the slice reading at " "the cyclic cubics", not off and rows, f"{rows} (field, L), {len(off)} off {off[:4]}; Dedekind fails " f"at {skipped}") def section_census(Ks): print("T THE CENSUS") R, c2, boxoff = {}, [], [] for K in Ks: e1, e2 = box_exps_all(K, BOXES[0]), box_exps_all(K, BOXES[1]) pl = place_norms(K) for L in LS: w, WL = w_cheb(K, L, pl), W(L) if w != WL: c2.append((K.name, L, w, WL)) n1, n2 = n_from(e1, L), n_from(e2, L) if n1 != n2: boxoff.append((K.name, L, n1, n2)) R[(K.name, L)] = (WL, n_guess(K, L), n2) check("C2 the Chebotarev form of w equals W(L)", 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(7^(1/3))": (1, 7, 7, 1), "Q(13^(1/3))": (1, 1, 13, 1), "x^3+0x^2-3x-8": (1, 3, 3, 3), "Q(2^(1/3))": (1, 1, 1, 1), "Q(3^(1/3))": (1, 1, 1, 1), "Q(5^(1/3))": (1, 1, 1, 1)} got = {nm: tuple(R[(nm, L)][2] // R[(nm, L)][0] for L in (1, 2, 4, 12)) for nm in hand if (nm, 1) in R} check("C3 the hand values of n / w at L = 1, 2, 4, 12", got == hand, f"{sorted(got.items())}") bad = {(a, b) for a, b, _, _ in boxoff} kill = [(nm, L, n, g) for (nm, L), (w, g, n) in R.items() if n != g and (nm, L) not in bad] 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") types, at3 = {}, 0 for K in Ks: for l in K.ram: if l <= 181: lab = guess_exps(K, l)[1] types[lab] = types.get(lab, 0) + 1 at3 += l == 3 and lab == "total, not Galois" gaps = {L: R[(K.name, L)][2] // R[(K.name, L)][0] for L in LS} if any(g > 1 for g in gaps.values()): cyc = [l for l in K.ram if l <= 181 and guess_exps(K, l)[1].endswith("cyclic")] print(f" {K.name:22s} disc {K.D:7d}: cyclic at {cyc}; " f"L = 1..12: {[gaps[L] for L in range(1, 13)]}") print(f" local types at the ramified l: {sorted(types.items())}; " f"total, not Galois at l = 3: {at3}") none = sum(all(R[(K.name, L)][2] == R[(K.name, L)][0] for L in LS) for K in Ks) print(f" n = w at every L: {none} of {len(Ks)} fields") def main(): t0 = time.time() section_control() P = pure() Ks = P + searched(int(sys.argv[1]) if len(sys.argv) > 1 else 12, {K.D for K in P}) print(f"numcubic.py: {len(Ks)} cubic fields not Galois " f"({sum(K.name.startswith('Q(') for K in Ks)} pure), " f"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())