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), 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())