wild_q.py
Checks: OBSERVATORY: The wild readout theorem.
Cited on: OBSERVATORY.
To run it: save wild_q.py, with clock.py, module_law.py, tame.py, tame_q.py, triangle.py beside it; standard library only.
"""
wild_q.py -- the wild readout over 2 when the residue field is F_q,
q = 2^f > 2: the anchor design rescaled, and a top class whose second
digit no longer sits in F_2.
QUESTION. The wild readout over 2 rests on u = 1 = -1 mod pi, true
only at f = 1. Over W(F_q), K totally ramified of degree e over W,
F = x^e + sum 2 b_i x^i - 2 d, ubar = 1/dbar is any element of F_q^x.
What do the anchor design and the classes' landings become?
THE ARGUMENT (written before the engine).
(1) RESCALING. pi' = T(a) pi, a the one residue with a^e = ubar (the
Frobenius is bijective on F_q), is a root of T(a)^e F(x/T(a)), with
u' = u/T(ubar) and ubar' = 1; valuations are unchanged, so each f = 1
step that uses only ubar = 1 carries over in pi'.
(2) THE ANCHOR is T(a)^-e A_e(T(a) x):
A_e^dbar = x^e + 2 T(dbar^(1/2)) x^(e/2) + 4 T(dbar^(3/4)) x^(e/4)
- 6 T(dbar) (no x^(e/4) term at e = 2),
its coefficient digits dbar^(1/2) at level e/2, dbar at e and
dbar^(3/4) at 5e/4. lam is the first level where F's coefficient
digits leave A_e^dbar's. S0 = u + T(ubar) + T(ubar^(1/2)) u pi^(e/2)
+ T(ubar^(1/4)) u^2 pi^(5e/4) is T(ubar) times the f = 1 element read
in pi', so min(v(S0), 3e/2) = min(lam, 3e/2) by the triangle.
(3) THE TOP CLASS (1, n), e = 2^n: z = 1 + T(a) pi + T(a^2 y) pi^2 + ...
of residue a. Off the kernel (a^e != ubar) it lands at 2e. On it
u + h_n = S0 + V mod pi^(3e/2), V = T(ubar) pi'^e q'^2 (q'^2 + u'),
q' of residue y^(e/4) (e = 2: V = T(ubar) pi'^2 y'(y' + u')), so V's
level-e digit is ubar^2 (y^e + y^(e/2)): nonzero iff y is not in F_2.
At f = 1 y is always in F_2, which is why the f = 1 cap is 3e/2. On the
kernel: lam < e, every unit at 2e + lam; y in F_2, the f = 1 argument
unchanged (v(q') >= e/4 or q' = 1 mod pi^(e/4)): 2e + lam below the
cap, at least 7e/2 at it, one of z and z g (g = 1 + pi^3) exactly
there; y not in F_2 and lam > e, exactly 3e; y not in F_2 and lam = e,
3e unless ubar^2 (y^e + y^(e/2)) = sigma, sigma the level-e digit of
S0, then deeper. y -> y^e + y^(e/2) is 2-to-1 onto the trace-0 half
(Artin-Schreier after the Frobenius), so 0 or 2 such y.
(4) THE CLASSES c >= 2, c 2^m = e: the kernel is the one a with
a^(2^m) = ubar; on it 2e + min(l, 2^m), l = v(u + T(ubar)) =
min(e v_2(d + T(dbar)), e v_2(b_i) + i), the departure from
x^e + 2 T(dbar) (the sign +, not the odd prime's -); every kernel unit
when l < 2^m, else all but one t_1. Off it 2e.
PREDICTIONS over f = 2 (e = 2, 4, 6, 8, 16) and f = 3 (e = 2, 4, 8),
two dbar per (f, e) (1 and one other), the departures lam = 1..3e/2 + 1
from A_e^dbar and the anchor itself, and departures l = 1..e + 1 from
x^e + 2 T(dbar); every a in F_q^x, every y (or t_1) in F_q, a random
third digit:
W1 min(v(S0), 3e/2) = min(lam, 3e/2) at every polynomial.
W2 every top-class unit lands as (3) says; at lam = e the count of
deep y off F_2 is 0 or 2 and matches the sigma rule.
W3 every c >= 2 unit lands as (4) says, l off the coefficients equal
to v(u + T(ubar)).
W4 (the change) at f > 1 some kernel unit with lam > e lands at 3e,
below the f = 1 law's 2e + min(lam, 3e/2).
W5 (added after the first run, to print the headline rather than
derive it from W2) the kernel's least landing is 2e + min(lam, e)
at every f > 1 polynomial with a top class.
KILLS, as prints.
K1 a polynomial off W1: the anchor's lift is wrong.
K2 a unit off W2 or W3: the reading is wrong.
CONTROL, read first: the same reader at f = 1, e = 4 and 8, dbar = 1,
the anchor and designed departures: W1, W2 and W3 hold, and the class's
least landing is 2e + min(lam, 3e/2) (wild.py's law); every y is in F_2
there by construction.
PLANT, for K1: the f = 1 anchor A_e unrescaled, at dbar != 1, read as
the anchor at f > 1 must fire K1 at some polynomial.
FINDINGS (entered after the run).
- The control holds: at f = 1, e = 4 and 8, W1-W3 hold at 13 and 23
polynomials and the least landing is 2e + min(lam, 3e/2) at every
one.
- K1 and K2 did not fire: over f = 2 (e = 2, 4, 6, 8, 16) and f = 3
(e = 2, 4, 8), 276 polynomials, 7016 top-class units (876 of them on
the kernel with y off F_2) and 18472 units of the classes c >= 2,
every one lands as (3) and (4) say, min(v(S0), 3e/2) = min(lam, 3e/2)
at every polynomial, and l read off the coefficients is
v(u + T(ubar)) at each.
- At lam = e the deep off-F_2 count is 0 at 9 of the 14 polynomials
and 2 at 5, each set the sigma rule's.
- W4 holds: 248 kernel units with lam > e land at 3e, below the f = 1
law's 2e + min(lam, 3e/2). W5 holds: the kernel's least landing is
2e + min(lam, e) at all 262 polynomials with a top class (with
min(lam, 3e/2) in its place W5 fails, first at f = 2, e = 2), and
its F_2-digit part keeps the f = 1 reading.
- The plant fired: the unrescaled A_e at dbar = (0, 1), e = 4, leaves
7 polynomials off W1.
RUN RECORD. 11/11 checks, 19.1 s, peak commit 8.1 MB; with
C2 cut (it held by construction) and W5 added, 10/10, 19.1 s, 8.2 MB.
"""
import random
import time
from tame_q import Ring, build, fq_all, u_of, INF
CHECKS = []
N = 6
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 classes(e):
out, m = [], 0
while e % 2 ** m == 0:
out.append((e // 2 ** m, m))
m += 1
return out
def roots(R, x):
"""(x^(1/2), x^(1/4), x^(3/4)) in F_q."""
h = R.fq_pow(x, R.q // 2)
k = R.fq_pow(h, R.q // 2)
return h, k, R.fq_pow(k, 3)
def anchor_digits(R, e, dbar, rescaled=True):
"""{level: digit} of A_e^dbar past level 0 (of A_e if not rescaled)."""
one = (1,) + (0,) * (R.f - 1)
h, _, k3 = roots(R, dbar) if rescaled else (one, one, one)
dd = dbar if rescaled else one
out = {e // 2: h, e: dd}
if e >= 4:
out[5 * e // 4] = k3
return out
def designed(rng, R0, F, e, dbar, ref, dep, top):
"""Coefficient digits equal to ref's below dep, off it at dep,
random above, to level top (dep = INF: ref itself)."""
digs = []
for r in range(1, top + 1):
a = ref.get(r, F[0])
if r < dep:
digs.append(a)
elif r == dep:
digs.append(rng.choice([c for c in F if c != a]))
else:
digs.append(rng.choice(F))
return digs
def ring_A(f, e, dbar, digs):
return build(2, f, e, dbar, digs, N)
def ring_B(f, e, dbar, digs):
"""d's digits shifted so the reference is x^e + 2 T(dbar)."""
R1 = build(2, f, e, dbar, digs, N)
two_t = R1.zmul((2,) + (0,) * (f - 1), R1.omega(dbar))
return Ring(2, f, e, R1.b, R1.zadd(R1.d, R1.zneg(two_t)), N)
def lam_of(R, dbar, ref):
"""The first level where F's coefficient digits leave those of the
anchor whose digits past level 0 are ref (level 0 is dbar)."""
e, f = R.e, R.f
two = (2,) + (0,) * (f - 1)
d = R.zadd(R.omega(dbar), R.zmul(two, R.omega(ref[e])))
best = e * R.zval(R.zadd(R.d, R.zneg(d)))
bref = {e // 2: R.omega(ref[e // 2])}
if e >= 4:
bref[e // 4] = R.zmul(two, R.omega(ref[5 * e // 4]))
for i in range(1, e):
x = R.b[i]
if i in bref:
x = R.zadd(x, R.zneg(bref[i]))
v = R.zval(x)
if v < INF:
best = min(best, e * v + i)
return best
def l_of(R, dbar):
"""min(e v_2(d + T(dbar)), e v_2(b_i) + i)."""
e = R.e
best = e * R.zval(R.zadd(R.d, R.omega(dbar)))
for i in range(1, e):
v = R.zval(R.b[i])
if v < INF:
best = min(best, e * v + i)
return best
def teich(R, c):
z = R.zero()
z[0] = R.omega(c)
return z
def s_zero(R, u, ub):
e = R.e
h, k, _ = roots(R, ub)
s = R.add(u, teich(R, ub))
s = R.add(s, R.scal(R.omega(h), R.mul(u, R.pi_pow(e // 2))))
if e >= 4:
s = R.add(s, R.scal(R.omega(k),
R.mul(R.mul(u, u), R.pi_pow(5 * e // 4))))
return s
def digit_at(R, x, ub, r):
"""The Teichmuller digit of x at level r, all lower digits zero."""
i, k = r % R.e, r // R.e
w = tuple((c // 2 ** k) % 2 for c in x[i])
return R.fq_mul(w, R.fq_pow(ub, k))
def landing(R, z, m):
y = z
for _ in range(m + 1):
y = R.mul(y, y)
y[0] = R.zadd(y[0], R.zneg(R.one()[0]))
return R.val(y)
def unit(R, c, a, t1, r):
z = R.add(R.one(), R.scal(R.omega(a), R.pi_pow(c)))
z = R.add(z, R.scal(R.omega(t1), R.pi_pow(c + 1)))
return R.add(z, R.scal(R.omega(r), R.pi_pow(c + 2)))
def read_top(R, rng, F, ub, lam, sigma, tally):
"""W2 at one polynomial: the off units, and the least landing."""
e, n = R.e, R.e.bit_length() - 1
off, least, deep_gen = [], INF, []
f2 = (F[0], F[1])
sig = None if sigma is None else R.fq_mul(sigma, R.fq_inv(
R.fq_mul(ub, ub)))
g = R.add(R.one(), R.pi_pow(3))
for a in F[1:]:
ker = R.fq_pow(a, e) == ub
for y in F:
z = unit(R, 1, a, R.fq_mul(R.fq_mul(a, a), y), rng.choice(F))
v = landing(R, z, n)
if ker:
least = min(least, v)
if not ker:
ok = v == 2 * e
elif lam < e:
ok = v == 2 * e + lam
elif y in f2:
if lam < 3 * e // 2:
ok = v == 2 * e + lam
else:
v2 = landing(R, R.mul(z, g), n)
ok = v >= 7 * e // 2 and min(v, v2) == 7 * e // 2
least = min(least, v2)
elif lam > e:
ok = v == 3 * e
tally["w4"] += v < 2 * e + min(lam, 3 * e // 2)
else:
ye = R.fq_pow(y, e)
hit = fq_add(ye, R.fq_pow(y, e // 2)) == sig
ok = v > 3 * e if hit else v == 3 * e
if v > 3 * e:
deep_gen.append(y)
if not ok:
off.append((a, y, v))
tally["units"] += 1
tally["generic"] += ker and y not in f2
if lam == e and R.q > 2:
tally["eq"].append(len(deep_gen))
if len(deep_gen) not in (0, 2):
off.append(("count", len(deep_gen)))
return off, least
def read_lower(R, rng, F, ub, l, tally):
"""W3 at one polynomial: every class with c >= 2."""
e, off = R.e, []
for c, m in classes(e):
if c < 2:
continue
for a in F[1:]:
ker = R.fq_pow(a, 2 ** m) == ub
vals = [landing(R, unit(R, c, a, t1, rng.choice(F)), m)
for t1 in F]
tally["lower"] += len(vals)
if not ker:
bad = [v for v in vals if v != 2 * e]
elif l < 2 ** m:
bad = [v for v in vals if v != 2 * e + l]
else:
deep = [v for v in vals if v > 2 * e + 2 ** m]
bad = [v for v in vals if v < 2 * e + 2 ** m]
if len(deep) != 1:
bad.append(("deep", len(deep)))
if bad:
off.append((c, m, a, bad[:3]))
return off
def fq_add(x, y):
return tuple((a + c) % 2 for a, c in zip(x, y))
def read_field(rng, f, e, dbars, plant=False, record=None):
"""Every polynomial of the population at (f, e); returns the offs."""
R0 = Ring(2, f, e, [None] * e, None, N)
F = fq_all(2, f)
top = 2 * e + 4
w1, w2, w3 = [], [], []
tally = dict(units=0, generic=0, w4=0, eq=[], lower=0, polys=0)
pow2 = e & (e - 1) == 0
for dbar in dbars:
pops = []
if pow2:
ref = anchor_digits(R0, e, dbar)
for dep in list(range(1, 3 * e // 2 + 2)) + [INF]:
pops.append(("A", dep, ring_A(f, e, dbar, designed(
rng, R0, F, e, dbar, ref, dep, top))))
refb = {}
for dep in range(1, e + 2):
pops.append(("B", dep, ring_B(f, e, dbar, designed(
rng, R0, F, e, dbar, refb, dep, top))))
for kind, dep, R in pops:
tally["polys"] += 1
u = u_of(R)
ub = tuple(a % 2 for a in u[0])
l = l_of(R, dbar)
lu = R.val(R.add(u, teich(R, ub)))
if l != min(lu, e * N) or (kind == "B" and l != dep):
w3.append((kind, dep, "l", l, lu))
w3 += [(kind, dep, x) for x in read_lower(R, rng, F, ub, l,
tally)]
if not pow2:
continue
lam = lam_of(R, dbar, anchor_digits(R0, e, dbar,
rescaled=not plant))
s0 = s_zero(R, u, ub)
vs = R.val(s0)
cap = 3 * e // 2
if min(vs, cap) != min(lam, cap) or (kind == "A" and not plant
and min(lam, cap)
!= min(dep, cap)):
w1.append((kind, dep, lam, vs))
if plant:
continue
sigma = digit_at(R, s0, ub, e) if vs == e else None
off, least = read_top(R, rng, F, ub, lam, sigma, tally)
w2 += [(kind, dep, x) for x in off]
if record is not None:
record.append((kind, dep, lam, least))
return w1, w2, w3, tally
def section_control(rng):
print("C the reader at f = 1 against wild.py's law")
for e in (4, 8):
rec = []
w1, w2, w3, t = read_field(rng, 1, e, [(1,)], record=rec)
check(f"C1 e = {e}: W1, W2, W3 hold at f = 1",
not (w1 or w2 or w3),
f"{t['polys']} polys, {t['units']} top units; off "
f"{(w1 + w2 + w3)[:4]}")
off = [(k, d, lam, le) for k, d, lam, le in rec
if le != 2 * e + min(lam, 3 * e // 2)]
check(f"C3 e = {e}: the least landing is 2e + min(lam, 3e/2) at "
f"{len(rec)} polys", not off, f"off at {off[:4]}")
def section_fields(rng):
print("W the readout at f = 2 and 3")
grid = ((2, (2, 4, 6, 8, 16)), (3, (2, 4, 8)))
k1 = k2 = 0
w4 = 0
eqs = []
least_off, nleast = [], 0
for f, es in grid:
F = fq_all(2, f)
for e in es:
t0 = time.time()
other = rng.choice([c for c in F[2:]])
rec = []
w1, w2, w3, t = read_field(rng, f, e, [F[1], other],
record=rec)
least_off += [(f, e, d, lam, le) for k, d, lam, le in rec
if le != 2 * e + min(lam, e)]
nleast += len(rec)
k1 += len(w1)
k2 += len(w2) + len(w3)
w4 += t["w4"]
eqs += t["eq"]
print(f" f = {f}, e = {e:2d}, dbar in (1, {other}): "
f"{t['polys']} polys, {t['units']} top units "
f"({t['generic']} on the kernel off F_2), {t['lower']} "
f"c >= 2 units; W1 off {len(w1)}, W2 off {len(w2)}, "
f"W3 off {len(w3)}; {time.time() - t0:.1f} s")
for x in (w1 + w2 + w3)[:3]:
print(f" off: {x}")
check("K1 did not fire: min(v(S0), 3e/2) = min(lam, 3e/2) everywhere",
k1 == 0, f"{k1} off")
check("K2 did not fire: every unit lands as (3) and (4) say",
k2 == 0, f"{k2} off")
print(f" deep off-F_2 counts at lam = e: {sorted(eqs)}")
check("W2 the lam = e counts are 0 or 2, both seen",
set(eqs) <= {0, 2} and set(eqs) == {0, 2}, f"read {set(eqs)}")
check(f"W5 the kernel's least landing is 2e + min(lam, e) at all "
f"{nleast} polynomials with a top class", not least_off,
f"off at {least_off[:4]}")
check("W4 some kernel unit with lam > e lands below the f = 1 law",
w4 > 0, f"{w4} units at 3e")
print("P the plant: A_e unrescaled read as the anchor at dbar != 1")
F = fq_all(2, 2)
w1, _, _, _ = read_field(rng, 2, 4, [F[2]], plant=True)
check("PLANT K1 fires on the unrescaled anchor", len(w1) > 0,
f"{len(w1)} polys off, first {w1[:2]}")
def main():
t0 = time.time()
rng = random.Random(1704)
section_control(rng)
if not all(CHECKS):
print("\nCONTROL FAILED: nothing below is read.")
raise SystemExit(1)
section_fields(rng)
print(f"{sum(CHECKS)}/{len(CHECKS)} checks passed, "
f"{time.time() - t0:.1f} s")
raise SystemExit(0 if all(CHECKS) else 1)
if __name__ == "__main__":
main()