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