quarter.py
Checks: OBSERVATORY: The cofactor readout theorem.
Cited on: OBSERVATORY.
To run it: save quarter.py, with clock.py, cofactor.py, module_law.py, rung.py, staircase.py, tame.py, triangle.py, weld.py, wild.py beside it; standard library only.
"""quarter.py -- over 2, the wild departure of a field holding i read off
the cofactor of i - 1: the lam <= e at which some field holds i are
exactly the even ones below e, and the cofactor readout of the odd
primes holds at 2 with lam in place of l.
QUESTION. Let K/Q_2 be totally ramified of degree e = 2^n >= 4, cut out
by an Eisenstein F with root pi, u = 2/pi^e (triangle.py), and lam the
wild departure of wild.py, the least level where a coefficient digit of
F leaves the anchor design A_e = x^e + 2x^(e/2) + 4x^(e/4) - 6. wild.py
proved min(lam, 3e/2) is the width of the head; weld.py that a field
without i has lam <= e, so lam > e forces i into K. Which lam <= e admit
i? staircase.py's fields over 2 with i all have lam > e. Is an odd lam < e ever a field with i, is lam
= e, and what fixes lam when i is in K?
THE DERIVATION (on paper, before the engine).
(1) THE QUARTER RELATION. With h = e/2, i - 1 has level h in K
((i - 1)^2 = -2i), so write i - 1 = pi^h tau, tau a unit, and tau
= 1 + y (the residue field is F_2), j = v(y) >= 1, the level of
tau's principal part. i^2 = -1 reads 2 + 2 pi^h tau + pi^e tau^2
= 0, and 2 = u pi^e turns it into
u (1 + pi^h tau) = -tau^2.
(2) THE READOUT. wild.py's S_0 = 1 + u + u pi^h + u^2 pi^(5e/4) has
v(S_0) = lam below the cap 3e/2. Multiply by the unit 1 + pi^h
tau and substitute (1): 1 - tau^2 + pi^h (tau - tau^2) = -(y^2 +
2y + pi^h y + pi^h y^2), and u^2 (1 + pi^h tau) = tau^4/(1 + pi^h
tau), whose correction to tau^4 sits h deeper, past 3e/2, so
S_0 (1 + pi^h tau) = -(y^2 + 2y + pi^h y + pi^h y^2)
+ pi^(5e/4) tau^4 mod pi^(3e/2).
2y sits at e + j and pi^h y^2 at h + 2j; both lie above 2j when
j < h and at or above 3e/2 when j >= h, and pi^(5e/4) tau^4 =
pi^(5e/4) mod pi^(3e/2) at j >= e/16 and otherwise sits above
2j. With
xi = v(y (y + pi^h)),
which is 2j at j < h, e + v(y/pi^h + 1) > e at j = h and h + j at
j > h, this is v(S_0) = v(y(y + pi^h) + pi^(5e/4)) below 3e/2:
lam = xi when xi < 5e/4,
lam = 5e/4 when xi > 5e/4,
lam > 5e/4 when xi = 5e/4,
the QUARTER READOUT. So j < h gives lam = 2j, even and below e,
and j >= h gives lam > e: a field holding i has lam in {2, 4, ...,
e - 2} or lam > e, never odd below e and never e. Since pi^e y (y
+ pi^h) = (i - 1 - pi^h)(i - 1 - pi^h + pi^e), xi reads off i with
no division.
(3) THE CLIMB. Let zeta be a primitive 2^N-th root of unity, N >= 2,
zeta - 1 = pi^c tau_N, c = e/2^(N-1), i_tau the level of tau_N's
principal part. For x of level y <= e/4, (1 + x)^2 - 1 = x^2 (1
+ 2/x), the correction at level e - y >= 3e/4, and squaring a
principal unit of level k < e doubles k. So the cofactor of
i - 1 = zeta^(2^(N-2)) - 1 has principal level 2^(N-2) i_tau
when that is below h, and at least h otherwise. With (2):
min(lam, e) = min(2^(N-1) i_tau, e),
the odd primes' cofactor readout (cofactor.py) at p = 2, lam in
the place of l and the bend s = e the same cap. So lam >= 2^(N-1)
and below e lam is a multiple of 2^(N-1).
(4) THE DESIGN. cofactor.py's x^k + a varpi x^i - varpi over
Q_2(zeta_(2^N)), a = 1, has tau = 1/(1 - pi^i), i_tau = i, and
its norm A^q + B^q (q = 2^(N-1)) is Eisenstein of degree e = k q.
At k a power of 2 and 1 <= i < k, (3) predicts lam = 2^(N-1) i <
e, every multiple of 2^(N-1) below e; N is kept at odd i, since a
higher root would make lam a multiple of 2^N.
THE ENGINE. N, the root and the class data as cofactor.py reads them
(staircase.py's read_deep and root_search); i_tau at every primitive
root by cofactor.py's cofactor_level; i = zeta^(2^(N-2)) and its
inverse, and xi = v((i - 1 - pi^h)(i - 1 - pi^h + pi^e)) - e; lam by
wild.py's wild_departure off the coefficients. The admission census
reads i by root_search at N = 2 alone, a returned root certified by
Hensel (v(z^2 + 1) > 2e = 2 v(2z)); None is exhaustive, since a true
root's truncations survive every floor the search applies.
TRANSPLANTS. The climb (3) is cofactor.py's (2) rerun at p = 2, where
the correction bound is e - y and not (p - 1)^2 s/p, re-derived above.
The cap of (3) is s = e where wild.py's is 3e/2: below e, (2) is the
reading, and between e and 3e/2 only (2)'s piecewise law, not (3),
says what lam is.
POPULATIONS. Designs (N, k; i): (2, 2; 1), (2, 4; 1..3), (2, 8; 1..7),
(3, 2; 1), (3, 4; 1..3), (4, 2; 1), e = 4 to 16. staircase.py's
family Phi_(2^N)(1 + x^k + 2 r(x)) at (N, k) = (2, 2), (2, 4), (2, 8),
(3, 1), (3, 2), (4, 1), r = 0 and two random r. The census: wild.py's
designed polynomials at e = 4, 8, 16, lam = 1 .. 3e/2 + 1, four draws
each, digits random above lam.
PREDICTIONS, fixed before the run.
C CONTROL, run first. (a) The level reader returns 1..5 on pi^c (1 +
pi^j) at Q_2(zeta_8) and Q_2(zeta_16). (b) At both, N = 3, 4, the
readout (3) holds and min(lam, e) = e. (c) Every census polynomial
reads its designed lam, and A_e at e = 4, 8, 16 holds i.
R THE 2-ADIC COFACTOR READOUT. At every field with N >= 2 and every
primitive 2^N-th root, min(lam, e) = min(2^(N-1) i_tau, e).
Q THE QUARTER READOUT. At every field with N >= 2 and both of +-i,
min(lam, 3e/2) is min(xi, 3e/2) when xi < 5e/4 and 5e/4 when xi >
5e/4, and lam > 5e/4 when xi = 5e/4.
D THE DESIGN. lam = 2^(N-1) i at every design, N kept at odd i.
A THE ADMISSION. In the census, every field holding i has lam even
below e or lam > e, and every field with lam > e holds i.
KILLS, as printed observables: a C line off (nothing below is read); one
(field, root) off R; one (field, +-i) off Q; one design off D; one census
field with i at odd lam < e or at lam = e, or one with lam > e without i.
FINDINGS. Every prediction landed: 9/9 checks PASS, no kill fired.
C The reader returns 1..5 at both fields. Q_2(zeta_8) reads N = 3,
lam = 6, xi = 5 = 5e/4 at both of +-i; Q_2(zeta_16) N = 4, lam = 12,
xi = 10 = 5e/4: the tie branch, lam past 5e/4. 180 designed
polynomials read their designed lam (A's census draws 180 more
from the same designer), and A_e holds i at e = 4, 8, 16.
R 34 fields, N from 2 to 4, every primitive root: min(lam, e) =
min(2^(N-1) i_tau, e).
Q The same 34 at both of +-i. All three branches met: lam = xi in (e,
5e/4) (e = 8, lam = xi = 9; e = 16, lam = xi = 18, 19); xi > 5e/4
giving lam = 5e/4 (e = 4, 8, 16 at r = 0, xi from 8 to past the
precision, where it prints the cap, 99 at e = 16, the two roots
reading different xi); the tie xi = 5e/4 at the cyclotomic fields,
lam = 3e/2.
D 16 designs: lam = 2^(N-1) i at each, every even lam from 2 to e - 2
at N = 2 and e = 4, 8, 16, the multiples of 4 at N = 3 and lam = 8
at N = 4, e = 16.
A 180 census fields: i held at no odd lam below e and at no lam = e;
at every lam > e, 4 of 4; at the even lam below e, rarely (e = 16:
1 of 4 at lam = 8, 2 of 4 at 14, none at 2 to 6, 10, 12), so the
even lam below e are the designs' to realize, not the census's.
Tiers: the quarter readout (2) and the cofactor readout at 2 (3)
theorems, their proof the derivation above; the design (4) a theorem
given (3); the admission a corollary of (2) and weld.py's bound.
RUN RECORD. 9/9, 11.0 s wall, peak working set 14.5 MB under a memory guard,
green on the first run.
"""
import os
os.environ.setdefault("OPENBLAS_NUM_THREADS", "1")
import random
from module_law import check, section, CHECKS
from tame import INF
from weld import Units
from staircase import root_search, cyclo
from wild import wild_departure, designed, anchor
from cofactor import design, val, cofactor_level, read_field
SEED = 1430
# ------------------------------------------------------------ the readers
def lam_of(e, b, d):
return wild_departure(e, b, d)
def quarter_m(U, iota):
"""m = v((i - 1 - pi^h)(i - 1 - pi^h + pi^e)) - e."""
e, mod = U.e, U.mod
ph = U.loc.pi_pow(e // 2, mod)
pe = U.loc.pi_pow(e, mod)
a = [(x - (k == 0) - y) % mod for k, (x, y) in enumerate(zip(iota, ph))]
b = [(x + y) % mod for x, y in zip(a, pe)]
return val(U, U.mul(a, b)) - e
def quarter_ok(e, lam, m):
cap, q = 3 * e // 2, 5 * e // 4
if m == q:
return lam > q
want = m if m < q else q
return min(lam, cap) == min(want, cap)
def fourth_roots(r):
"""i and its inverse, from the primitive 2^N-th root r['root']."""
U, N = r["U"], r["N"]
z = [x % U.mod for x in r["root"]]
iota = U.pw(z, 2 ** (N - 2))
return [iota, U.pw(iota, 3)]
def read(e, b, d):
r = read_field(2, e, b, d)
r["lam"] = lam_of(e, b, d)
r["ms"] = [quarter_m(r["U"], t) for t in fourth_roots(r)] \
if r["root"] is not None and r["N"] >= 2 else []
return r
def readout_ok(r, e):
N = r["N"]
return (r["root"] is not None and r["higher"] is None and r["taus"]
and all(min(r["lam"], e) == min(2 ** (N - 1) * t, e)
for t in r["taus"]))
def show(r, e, label):
lam = "inf" if r["lam"] >= INF else r["lam"]
print(f" e={e:2d} N={r['N']} {label:30s} lam={lam:>3} "
f"i_tau {sorted(set(r['taus']))} xi {r['ms']}")
def holds_i(e, b, d):
Lp = 4 * e
z = root_search(2, e, b, d, 2, Lp)
if z is None:
return False
U = Units(2, e, b, d, Lp)
z = [x % U.mod for x in z]
w = U.mul(z, z)
w = [(x + (k == 0)) % U.mod for k, x in enumerate(w)]
assert val(U, w) > 2 * e, "Hensel certificate failed"
return True
# ------------------------------------------------------------ sections
def section_control(rng):
section("C CONTROL: the reader, the cyclotomic fields, the census "
"polynomials")
for name, N, gen in [("Q_2(zeta_8)", 3, cyclo(2, 3, 1, [])),
("Q_2(zeta_16)", 4, cyclo(2, 4, 1, []))]:
e, b, d = gen
r = read(e, b, d)
U, c = r["U"], r["c"]
got = []
for j in range(1, 6):
pc = U.loc.pi_pow(c, U.mod)
pj = U.loc.pi_pow(c + j, U.mod)
got.append(cofactor_level(U, [(x + y) % U.mod
for x, y in zip(pc, pj)], c))
check(f"Ca {name}: the reader returns 1..5", got == [1, 2, 3, 4, 5],
f"read {got}")
show(r, e, name)
check(f"Cb {name}: N = {N}, the readout holds, min(lam, e) = e",
r["N"] == N and readout_ok(r, e) and min(r["lam"], e) == e,
f"N {r['N']}, lam {r['lam']}")
bad = n = 0
for e in (4, 8, 16):
for lam in range(1, 3 * e // 2 + 2):
for _ in range(4):
b, d = designed(rng, e, lam, 2 * e + 4)
n += 1
bad += lam_of(e, b, d) != lam
anc = [holds_i(e, *anchor(e)) for e in (4, 8, 16)]
check("Cc the census reads its designed lam; A_e holds i at e = 4, 8, "
"16", bad == 0 and all(anc), f"{n} polynomials, {bad} off; "
f"anchors {anc}")
DESIGNS = [(2, 2, 1)] + [(2, 4, i) for i in (1, 2, 3)] \
+ [(2, 8, i) for i in range(1, 8)] + [(3, 2, 1)] \
+ [(3, 4, i) for i in (1, 2, 3)] + [(4, 2, 1)]
CYCLO = [(2, 2), (2, 4), (2, 8), (3, 1), (3, 2), (4, 1)]
def section_fields(rng):
section("R, Q, D THE COFACTOR READOUT AT 2, THE QUARTER READOUT, "
"THE DESIGN")
bad = dict(R=0, Q=0, D=0)
n = dict(R=0, Q=0, D=0)
rows = []
for N, k, i in DESIGNS:
e, b, d = design(2, N, k, i, 1)
rows.append((e, b, d, f"design N={N} k={k} i={i}", (N, i)))
for N, k in CYCLO:
for t in range(3):
rr = [] if t == 0 else [rng.randrange(4) for _ in range(k)]
e, b, d = cyclo(2, N, k, rr)
rows.append((e, b, d, f"Phi_2^{N}(1+x^{k}+2r) r={rr}", None))
for e, b, d, label, des in rows:
r = read(e, b, d)
show(r, e, label)
n["R"] += 1
okR = readout_ok(r, e)
bad["R"] += not okR
okQ = r["N"] >= 2 and len(r["ms"]) == 2 and all(
quarter_ok(e, r["lam"], m) for m in r["ms"])
n["Q"] += 1
bad["Q"] += not okQ
okD = True
if des is not None:
N, i = des
n["D"] += 1
okD = r["lam"] == 2 ** (N - 1) * i and (i % 2 == 0
or r["N"] == N)
bad["D"] += not okD
if not (okR and okQ and okD):
print(f" OFF: R {okR} Q {okQ} D {okD}")
check("R min(lam, e) = min(2^(N-1) i_tau, e) at every root",
bad["R"] == 0, f"{n['R']} fields, {bad['R']} off")
check("Q the quarter readout at both of +-i",
bad["Q"] == 0, f"{n['Q']} fields, {bad['Q']} off")
check("D the design: lam = 2^(N-1) i, N kept at odd i",
bad["D"] == 0, f"{n['D']} designs, {bad['D']} off")
def section_admission(rng):
section("A THE ADMISSION: which lam hold i")
bad = 0
for e in (4, 8, 16):
tally = {}
for lam in range(1, 3 * e // 2 + 2):
for _ in range(4):
b, d = designed(rng, e, lam, 2 * e + 4)
has = holds_i(e, b, d)
tally.setdefault(lam, []).append(has)
allowed = (lam < e and lam % 2 == 0) or lam > e
if (has and not allowed) or (lam > e and not has):
bad += 1
line = " ".join(f"{lam}:{sum(v)}/{len(v)}"
for lam, v in sorted(tally.items()))
print(f" e={e:2d} lam:with-i {line}")
check("A i only at even lam < e or lam > e, and always at lam > e",
bad == 0, f"{bad} off")
def main():
rng = random.Random(SEED)
section_control(rng)
if not all(CHECKS):
print("\ncontrol failed: nothing below is read")
raise SystemExit(1)
section_fields(rng)
section_admission(rng)
print()
print(f"{sum(CHECKS)}/{len(CHECKS)} checks PASS")
if not all(CHECKS):
raise SystemExit(1)
if __name__ == "__main__":
main()