wild_field.py
Checks: OBSERVATORY: The wild readout theorem.
Cited on: OBSERVATORY.
To run it: save wild_field.py, with clock.py, module_law.py, tame.py, tame_q.py, triangle.py, wild_q.py beside it; standard library only.
"""
wild_field.py -- two Eisenstein polynomials of one field over W(F_q),
q = 2^f: is the wild readout's capped departure min(lam, 3e/2) the
field's at q > 2, or only min(lam, e)?
QUESTION. wild_q.py: at q > 2 the top class's kernel (the one residue a
with a^e = ubar) has least landing 2e + min(lam, e); the units whose
pi'^2 digit y (pi' = T(a) pi) lies in F_2 keep 2e + min(lam, 3e/2), and
at lam = e, 0 or 2 y off F_2 land past 3e. Read on F and on G, the
Eisenstein polynomial of the uniformizer pi_1 = pi (1 + T(delta) pi) of
the same field.
DERIVATION (frozen before code). The kernel and its landings are the
field's (pi -> eps pi sends a -> a/eps, ubar -> ubar/eps^e), so
min(lam, e) is, and so is the number of y whose units land past 3e
(U_3 lands at 7e/2 or deeper). T(a) pi = T(a) pi_1 - T(a delta) pi_1^2
+ ..., so y_1 = y + delta/a: the deep pair of a lam > e polynomial, F_2
in the pi frame, is {delta/a, delta/a + 1} in the pi_1 frame, off F_2
iff delta is not in {0, a}; then G can have neither lam < e (least
landing 3e) nor lam > e (deep pair F_2): lam_G = e. TRANSPLANT
re-derived: at f = 1, delta/a is in F_2, and the f = 1 invariance
stands.
PREDICTIONS, over wild_q's anchor population (departures 1..3e/2 + 1
and the anchor itself), f = 2 (e = 2, 4, 8), f = 3 (e = 2, 4), dbar = 1
and one other, every delta in F_q:
P1 min(lam_G, e) = min(lam_F, e) at every pair.
P2 lam_F > e, delta not in {0, a}: lam_G = e, G's deep y the pair
{delta/a, delta/a + 1}.
P3 (the arm without the ingredient) lam_F > e, delta in {0, a} (as
frozen; the code reads delta = a alone, delta = 0 being G = F):
min(lam_G, 3e/2) = min(lam_F, 3e/2).
P4 lam_F = e: lam_G > e iff delta/a is one of F's deep y.
P5 G's deep-y count equals F's at every pair.
KILL, printed: the pairs off P1 .. P5, summed; any nonzero kills. P2's
arm must hold a pair at every (f, e). The headline (min(lam, 3e/2) is
not the field's at q > 2) stands iff P2 holds on its arm and P3's arm
prints lam_G > e.
CONTROLS, read first. C1 f = 1, e = 4 and 8, delta = 1:
min(lam_G, 3e/2) = min(lam_F, 3e/2) at every polynomial (wild.py's
theorem). C2 at every pair G is Eisenstein and G(pi_1) = 0 mod 2^N1 in
O_K (Cayley-Hamilton: the matrix of pi_1 is right).
DESIGN. O_K mod 2^N1, N1 = 7, as in tame_q.Ring; G is the
characteristic polynomial of multiplication by pi_1 on 1, pi, ..,
pi^(e-1), by Berkowitz's division-free recursion; G's b_i and d are its
coefficients halved, so G is read mod 2^6, which holds every level read
(at most 7e/2 + 1 < 6e).
FINDINGS (copied from the printed run).
- Controls: at f = 1, delta = 1, min(lam_G, 3e/2) = min(lam_F, 3e/2)
at 8 polynomials (e = 4) and 14 (e = 8), lam itself moving past the
cap (4: 6 -> 12, 7 -> 6); G Eisenstein with G(pi_1) = 0 at every
pair, here and below.
- The kill missed: 424 pairs at f = 2 (e = 2, 4, 8) and f = 3
(e = 2, 4), 344 of them with delta != 0 (the other 80 are G = F),
P1..P5 off 0. P2's arm, 136 pairs, every lam_G = e with
the deep pair at {delta/a, delta/a + 1} (f = 2, e = 4: lam_F = 6,
the cap, goes to 4). P3's arm (delta = a), 40 pairs, keeps
lam_G > e at all 40. At lam_F = e, 8 of 46 pairs go up to lam_G > e,
each where delta/a is a deep y of F.
- So at q > 2 one field holds Eisenstein polynomials with lam = e and
with lam > e: min(lam, e) is the field's and min(lam, 3e/2) is not.
That the polynomials of a field with lam > e share min(lam, 3e/2)
is a proof (the least landing past 3e is the field's); the run
reads it only on P3's 40 translates (e = 8: 12 <-> 13, anchor ->
12), one per polynomial: given P2, no other pair has both lam > e.
RUN RECORD. 13/13 checks, 2.5 s.
"""
import random
import sys
import time
from tame_q import Ring, build, fq_all, u_of, INF
from wild_q import anchor_digits, designed, lam_of, landing, unit
CHECKS = []
N1 = 7
def check(name, ok, detail=""):
CHECKS.append(bool(ok))
tail = f" ({detail})" if detail else ""
print(f" {'PASS' if ok else 'FAIL'} {name}{tail}")
def charpoly(R, M):
"""[1, c_1, .., c_n] with det(x I - M) = sum c_k x^(n-k), over Z_q."""
n, zero = len(M), (0,) * R.f
one = (1,) + (0,) * (R.f - 1)
P = [one, R.zneg(M[0][0])]
for r in range(1, n):
t = [one, R.zneg(M[r][r])]
v = [M[i][r] for i in range(r)]
for _ in range(r):
s = zero
for j in range(r):
s = R.zadd(s, R.zmul(M[r][j], v[j]))
t.append(R.zneg(s))
w = []
for i in range(r):
s = zero
for j in range(r):
s = R.zadd(s, R.zmul(M[i][j], v[j]))
w.append(s)
v = w
newP = []
for i in range(r + 2):
s = zero
for j in range(min(i, r) + 1):
s = R.zadd(s, R.zmul(t[i - j], P[j]))
newP.append(s)
P = newP
return P
def translate(R, delta):
"""G for pi_1 = pi + T(delta) pi^2; returns (G's ring mod 2^(N1-1),
Eisenstein?, G(pi_1) == 0?)."""
e, f = R.e, R.f
pi1 = R.add(R.pi_pow(1), R.scal(R.omega(delta), R.pi_pow(2)))
cols = [R.mul(pi1, R.pi_pow(j)) for j in range(e)]
M = [[cols[j][i] for j in range(e)] for i in range(e)]
P = charpoly(R, M)
coef = {i: P[e - i] for i in range(e + 1)}
ev = R.zero()
for i in range(e + 1):
ev = R.add(ev, R.scal(coef[i], R.power(pi1, i)))
zero_ok = all(not any(c) for c in ev)
eis = all(c % 2 == 0 for i in range(e) for c in coef[i]) and \
any((c // 2) % 2 for c in coef[0])
half = 2 ** (N1 - 1)
b = [(0,) * f] + [tuple((c // 2) % half for c in coef[i])
for i in range(1, e)]
d = tuple((-(c // 2)) % half for c in coef[0])
return Ring(2, f, e, b, d, N1 - 1), eis, zero_ok
def kernel_a(R, ub):
return [a for a in fq_all(2, R.f)[1:] if R.fq_pow(a, R.e) == ub][0]
def deep_ys(R, a):
"""The y whose kernel unit 1 + T(a) pi + T(a^2 y) pi^2 lands past 3e."""
e, n, zero = R.e, R.e.bit_length() - 1, (0,) * R.f
return {y for y in fq_all(2, R.f)
if landing(R, unit(R, 1, a, R.fq_mul(R.fq_mul(a, a), y), zero),
n) > 3 * e}
def read_pair(RF, delta):
"""lam, deep set and a for F and its translate G by delta."""
e = RF.e
RG, eis, zero_ok = translate(RF, delta)
out = []
for R in (RF, RG):
u = u_of(R)
ub = tuple(c % 2 for c in u[0])
dbar = tuple(c % 2 for c in R.d)
R0 = Ring(2, R.f, e, [None] * e, None, R.N)
lam = lam_of(R, dbar, anchor_digits(R0, e, dbar))
a = kernel_a(R, ub)
out.append((lam, deep_ys(R, a), a))
return out, eis, zero_ok
def fq_add(x, y):
return tuple((p + q) % 2 for p, q in zip(x, y))
def read_grid(rng, f, e, dbars, deltas=None):
F = fq_all(2, f)
R0 = Ring(2, f, e, [None] * e, None, N1)
top = 2 * e + 4
tally = {k: 0 for k in ("pairs", "P1", "P2", "P3", "P4", "P5", "C2",
"arm2", "arm3", "arm3_deep", "arm4", "arm4_up")}
rows = []
for dbar in dbars:
ref = anchor_digits(R0, e, dbar)
for dep in list(range(1, 3 * e // 2 + 2)) + [INF]:
RF = build(2, f, e, dbar, designed(rng, R0, F, e, dbar, ref, dep,
top), N1)
for delta in (deltas or F):
((lf, df, a), (lg, dg, ag)), eis, zok = read_pair(RF, delta)
tally["pairs"] += 1
tally["C2"] += not (eis and zok and a == ag)
cap = 3 * e // 2
tally["P1"] += min(lg, e) != min(lf, e)
tally["P5"] += len(dg) != len(df)
shift = R0.fq_mul(delta, R0.fq_inv(a))
if not any(delta):
pass
elif lf > e:
if delta == a:
tally["arm3"] += 1
tally["arm3_deep"] += lg > e
tally["P3"] += min(lg, cap) != min(lf, cap)
else:
tally["arm2"] += 1
pair = {shift, fq_add(shift, (1,) + (0,) * (f - 1))}
tally["P2"] += not (lg == e and dg == pair)
elif lf == e:
tally["arm4"] += 1
tally["arm4_up"] += lg > e
tally["P4"] += (lg > e) != (shift in df)
rows.append((dep, delta, lf, lg, len(df), len(dg)))
return tally, rows
def section_control(rng):
print("C f = 1, delta = 1: wild.py's invariance, and the translate")
for e in (4, 8):
t, rows = read_grid(rng, 1, e, [(1,)], deltas=[(1,)])
cap = 3 * e // 2
off = [r for r in rows if min(r[2], cap) != min(r[3], cap)]
check(f"C1 e = {e}: min(lam_G, 3e/2) = min(lam_F, 3e/2)", not off,
f"{t['pairs']} polys, off {off[:3]}; lam_F -> lam_G "
f"{[(r[2], r[3]) for r in rows]}")
check(f"C2 e = {e}: G Eisenstein, G(pi_1) = 0, one kernel a",
t["C2"] == 0,
f"{t['C2']} off")
def section_pairs(rng):
print("P f = 2, 3: two polynomials of one field")
total = {}
for f, es, other in ((2, (2, 4, 8), (0, 1)), (3, (2, 4), (0, 1, 0))):
for e in es:
t0 = time.time()
t, rows = read_grid(rng, f, e, [(1,) + (0,) * (f - 1), other])
for k, v in t.items():
total[k] = total.get(k, 0) + v
print(f" f = {f}, e = {e}: {t['pairs']} pairs; arm P2 "
f"{t['arm2']} (off {t['P2']}), arm P3 {t['arm3']} "
f"(lam_G > e at {t['arm3_deep']}, off {t['P3']}), "
f"lam_F = e {t['arm4']} (lam_G > e at {t['arm4_up']}, "
f"off {t['P4']}); P1 off {t['P1']}, P5 off {t['P5']}, "
f"C2 off {t['C2']}; {time.time() - t0:.1f} s")
check(f"P2's arm is nonempty at f = {f}, e = {e}", t["arm2"] > 0,
f"{t['arm2']} pairs")
lams = sorted({(r[2], r[3]) for r in rows if r[2] >= e})
print(f" (lam_F, lam_G) met with lam_F >= e: {lams}")
kill = sum(total[k] for k in ("P1", "P2", "P3", "P4", "P5"))
print(f" KILL count (P1..P5 off, summed): {kill}")
check("C2 at every pair", total["C2"] == 0, f"{total['C2']} off")
check("the kill did not fire", kill == 0, f"{kill}")
check("P3's arm keeps lam_G > e (the ingredient removed)",
total["arm3"] > 0 and total["arm3_deep"] == total["arm3"],
f"{total['arm3_deep']} of {total['arm3']}")
check("P4: some lam_F = e polynomial has a translate with lam_G > e",
total["arm4_up"] > 0, f"{total['arm4_up']} of {total['arm4']}")
def main():
rng = random.Random(1705)
t0 = time.time()
section_control(rng)
if not all(CHECKS):
print("control red: the run is void")
sys.exit(1)
section_pairs(rng)
print(f"{sum(CHECKS)}/{len(CHECKS)} checks passed, "
f"{time.time() - t0:.1f} s")
sys.exit(0 if all(CHECKS) else 1)
if __name__ == "__main__":
main()