numcubic.py
Checks: GROWTH: The gap read off the completions theorem; rule.
Cited on: GROWTH.
To run it: save numcubic.py, with numchar.py, numgap.py, numwall.py beside it; standard library only.
"""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())