"""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, C4), 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, 6/6 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), printed and skipped. C2 at 32280 (field, L), 0 off: w = W(L) at every field run. C3 every hand value. C4 all 33 pure cubics pass Dedekind's test. 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. 130.0 s from code/, peak commit 29.2 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() check("C4 every pure cubic of the list passes Dedekind's test", all(K.maximal for K in P), f"{len(P)} fields") 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())