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