""" twolinks.py -- a tree of hulls at a consumer's link: can consumer j >= 3 of a product-fed chain read one below its floor, through consumer j - 1's output stream, where the budget (the matching law's flag) says dead? THE INHERITED BEAT (property, by hand). A consumer at its floor reads its producer at inset 0 (its threshold Lam w - Mh eta <= b^L (w - 1) holds at eta = 0 by the floor's definition, and a hull of inset 0 is the producer string's box), so it lives behind any producer. At (20, 8, 12) and its mirror Lam_3 <= 1: with the two-unit certificate putting consumer 2 at 1, the n-unit chain reads naive - 1 at every n >= 2, where chains.programme's least is the naive sum. THE QUESTION, one level down. On the budget floor-1 consumers never gain (L = 0 needs 1 + Mh^(j-1) < 3/b, the inset at most w - 1); a tree hands narrower hulls, so T2 reads them at L = 0 on the grid. The probe reads the floor-2 run, Lam_j = Mh + Mh^j > 1, which at j >= 3 needs Mh > 0.6823. THE TRANSFER (re-derived). hulls.Grid reads its producer through d (a bound on every image's width at the next level), the producer's range and the box. Consumer j - 1 at delay L reads z (box w, |z| <= Mh) and its producer through a hull F wide (|u| <= tau_(j-2) = Mh^(j-1)); its image is a product of two intervals, an interval at most (Mh F + tau_(j-2) w)/b^L wide. So Grid with that d, tau = Mh^j in eta_max, and the range times_z^(j-2)(head range) certifies life at link j; rounding stays conservative (d up, eta down, range outward). ARMS, per link (j - 1, j), 3 <= j <= run_units, L_j* = 2, consumer j at L = 1. A: the budget (chains.links: floor chain / pairwise). B0: the tree, producer j - 1 at its floor reading inset 0. Bv: the same reading the floor chain's leftover v. C (j = 3): the head's own tree feeding consumer 2, F = min(eta*_1, w - v). PREDICTIONS (frozen). P1: every A gain is live under Bv. P2: tree gains past A are rare, a handful of links, at the run's last unit. P3: C adds at most what Bv adds. KILL (frozen). The script prints "tree gains past the matching: B0 N0, Bv Nv, C Nc"; killed iff all three are 0. CONTROLS, read first. (1) hulls.section_tree: (20, 8, 12) and its mirror live at eta_max, 0 faults. (2) Identity: the link grid built with the head's d, tau and range is hulls.Grid (live at eta_max, eta*) at every cell of radices 3..12. (3) P1. (4) One certificate child moved past its box at a live link is a fault. USAGE: python twolinks.py [K [bmax]], K = 40 and bmax = 12 bare; the record run is python twolinks.py 200 40. FINDINGS (entered after the run; every number is a print, K = 200, radices 3..40). - The controls read first: (20, 8, 12) and its mirror live at eta_max 1085/1083, 0 faults; the link grid at the head's parameters is Grid at every cell of radices 3..12; P1 held (727 budget gains, every one live under Bv); a child moved past its box makes 2 faults. - THE KILL MISSED. 228 cells carry a floor-2 consumer past 2, 4207 links. Tree gains past the matching: B0 17, Bv 18, C 1, at 18 cells, 0 checker faults. B0 and Bv agree but at (7, 2, 5), j = 7, live on the floor chain's leftover alone; C adds nothing to Bv (live at 10 of the 228 links at j = 3, past the budget only at (8, 3, 5), where Bv is too). - THE EDGE. The budget's gains are a suffix of the floor-2 run at all 228 cells, and every tree gain past them sits one link upstream of the suffix's first (0 off), or at the run's last unit where the suffix is empty ((8, 3, 5), j = 3 of a 4-unit chain). P2 as frozen ("at the run's last unit") was wrong at 17 of 18: where the grid certifies a gain past the budget, at 18 of 228 cells, it moves the budget's threshold by one link upstream. - THE CHAIN. With nu' the matching over the pairwise flags (budget at inset 0, or B0; at the head's link the budget or Grid), naive - nu' is below chains.programme's least at 98 of the 935 prefixes read at the 17 cells with a B0 gain, by 1 at every one, e.g. at (8, 3, 5) n = 3 (5 against 6), (12, 3, 9) and (17, 4, 13) n = 7 (13 against 14), (10, 2, 8) n = 14 (27 against 28). - T2. The first floor-1 unit past each run, 441 links (the chain of run_units holds one): eta_max(0) < 0 at 440, dead behind any producer (the generic multiplier); 0.0002 at the other, (14, 2, 12) j = 33, below its d, so the grid never runs. Units further down are not read. RUN RECORD: K = 40, radices 3..12, 0.5 s (the rehearsal); K = 200, radices 3..20, 6.0 s, 24.6 MB; K = 200, radices 3..40, 92.0 s, peak 38.7 MB under a memory guard. With T2: 6/6, 92.0 s, peak 38.9 MB. """ import math import os import sys import time from fractions import Fraction as Fr os.environ.setdefault("OPENBLAS_NUM_THREADS", "1") import chains # noqa: E402 import hulls # noqa: E402 import manystream as ms # noqa: E402 CHECKS = hulls.CHECKS check = hulls.check def make_grid(cell, d_fr, tau, rng, K, L=1): """hulls.Grid with its producer's d, the consumer's tau and the producer's range set; the consumer at delay L.""" g = hulls.Grid(cell, 2, L, K) g.d_fr = d_fr g.eta_fr = (Fr(cell.b) ** L * (cell.w - 1) - tau * cell.w) / cell.Mh g.d = math.ceil(d_fr * g.G) g.eta_max = math.floor(g.eta_fr * g.G) g.lo, g.hi = math.floor(rng[0] * g.G), math.ceil(rng[1] * g.G) return g def verdict(g): """(live at eta_max, checker faults or None).""" if g.eta_max < g.d: return False, None lv, F, _ = g.live(g.eta_max) return lv, (g.check(F, g.certificate(F), g.eta_max) if lv else None) def head_rng(cell): return chains.xy_head(cell)[3] def chain(cell, n): """Per consumer j = 2..n: (Lam_j, floor, the leftover v it reads on the floor chain, its producer's range).""" L1s, S, lams, rooms = chains.chain_units(cell, chains.xy_head, n) v, rng, out = S(L1s), head_rng(cell), [] for lam, rm in zip(lams, rooms): Ls = chains.unit_floor(cell, lam) out.append((lam, Ls, v, rng)) v = min(chains.leftover(cell, lam, Ls, min(v, cell.w - 1)), rm) rng = chains.times_z(cell, rng) return out def link_grid(cell, units, j, F, K): """Link (j - 1, j): producer consumer j - 1 at its floor reading a hull F wide.""" lam_p, Lp, _, rng_p = units[j - 3] tau_in = cell.Mh ** (j - 1) d_fr = (tau_in * cell.w + cell.Mh * F) / Fr(cell.b) ** Lp return make_grid(cell, d_fr, cell.Mh ** j, chains.times_z(cell, rng_p), K) def section_control(K): print("T0 controls") hulls.section_tree() off = [] for cell in hulls.cells1(3, 12): L1 = chains.floor_xy(cell) lam2 = cell.Mh ** 2 + cell.Mh L2 = 1 if lam2 > 1 else 0 g0 = hulls.Grid(cell, L1, L2, K) g1 = make_grid(cell, 2 * cell.Mh * cell.w / Fr(cell.b) ** L1, cell.Mh ** 2, head_rng(cell), K, L2) a = (g0.d, g0.eta_max, g0.lo, g0.hi) b = (g1.d, g1.eta_max, g1.lo, g1.hi) cap = min(g0.G + g0.d + 2 * g0.G, g0.Mm + g0.Mp) same = a == b and (g0.eta_max < g0.d or g0.live(g0.eta_max)[0] == g1.live(g1.eta_max)[0]) same = same and g0.eta_star(cap) == g1.eta_star(cap) if not same: off.append((cell.b, cell.am, cell.ap)) check("T0 the link grid at the head's d, tau, range is Grid, radices " "3..12", not off, f"off at {off[:4]}") def eta_star_head(cell, K): L1 = chains.floor_xy(cell) g = hulls.Grid(cell, L1, 1, K) return g.eta_star(min(g.G + g.d + 2 * g.G, g.Mm + g.Mp)), g.G def section_links(K, bmax): print(f"T1 the consumer links, radices 3..{bmax}, K {K}") t0 = time.time() rows, p1_off, planted, cells_run = [], [], None, 0 for b in range(3, bmax + 1): for cell in hulls.cells1(b, b): A1, L1s, S, _ = chains.xy_head(cell) if S(L1s) < 0: continue n = chains.run_units(cell, A1) units = chain(cell, n) ls = chains.links(cell, chains.xy_head, n) js = [j for j in range(3, n + 1) if units[j - 2][1] == 2] if not js: continue cells_run += 1 for j in js: _, gainA, pairA = ls[j - 2] v = units[j - 3][2] gv = link_grid(cell, units, j, cell.w - min(v, cell.w - 1), K) g0 = link_grid(cell, units, j, cell.w, K) lv, fv = verdict(gv) l0, f0 = verdict(g0) lc = fc = None if j == 3: es, G = eta_star_head(cell, K) F = cell.w - min(v, cell.w - 1) if es is not None: F = min(F, Fr(es, G)) lc, fc = verdict(link_grid(cell, units, j, F, K)) if gainA and not lv: p1_off.append((b, cell.am, cell.ap, j)) if planted is None and lv: F_, _ = gv.fixpoint(gv.eta_max) cert = gv.certificate(F_) s = next((s for s, k in enumerate(cert) if len(k) >= 2 and F_[s] >= gv.d), None) if s is not None: planted = gv.check(F_, cert, gv.eta_max, plant=(s, cert[s][0][0])) lam = units[j - 2][0] rows.append(dict(cell=(b, cell.am, cell.ap), j=j, n=n, lam=lam, A=gainA, A0=pairA, B0=l0, Bv=lv, C=lc, faults=(f0, fv, fc))) print(f" {cells_run} cells with a floor-2 consumer past 2, " f"{len(rows)} links, {time.time() - t0:.1f} s") faults = [r for r in rows if any(f not in (None, 0) for f in r["faults"])] check("T1 0 checker faults at every live link", not faults, f"{faults[:3]}") check("T1 P1: every budget gain is live under Bv", not p1_off, f"off at {p1_off[:4]}") check("T1 a child moved past its box is a fault", planted is not None and planted > 0, f"planted {planted}") pastB0 = [r for r in rows if r["B0"] and not r["A"]] pastBv = [r for r in rows if r["Bv"] and not r["A"]] pastC = [r for r in rows if r["C"] and not r["A"]] print(f" budget gains {sum(r['A'] for r in rows)}, live: B0 " f"{sum(r['B0'] for r in rows)}, Bv {sum(r['Bv'] for r in rows)}," f" C {sum(bool(r['C']) for r in rows)} (of " f"{sum(r['j'] == 3 for r in rows)} links at j = 3)") print(f" tree gains past the matching: B0 {len(pastB0)}, Bv " f"{len(pastBv)}, C {len(pastC)} at " f"{sorted({(r['cell'], r['j']) for r in pastB0 + pastBv + pastC})}") edge_off, not_suffix = [], [] for c in sorted({r["cell"] for r in rows}): run = sorted(r["j"] for r in rows if r["cell"] == c) ga = [r["j"] for r in rows if r["cell"] == c and r["A"]] if ga and ga != list(range(ga[0], run[-1] + 1)): not_suffix.append(c) for r in rows: if r["cell"] == c and (r["B0"] or r["Bv"]) and not r["A"]: edge = ga[0] - 1 if ga else run[-1] if r["j"] != edge: edge_off.append((c, r["j"], edge)) print(f" budget gains not a suffix of the floor-2 run at " f"{len(not_suffix)} cells {not_suffix[:4]}") print(f" tree gains off the edge (one link upstream of the budget's " f"first " f"gain, or the run's last unit where it has none): {edge_off}") seen = set() for r in pastB0 + pastBv + pastC: if (r["cell"], r["j"]) in seen: continue seen.add((r["cell"], r["j"])) cell = ms.Cell(*r["cell"]) naive, match, least, *_ = chains.programme(cell, chains.xy_head, r["j"]) last = r["j"] == r["n"] or chains.unit_floor( cell, cell.Mh + cell.Mh ** (r["j"] + 1)) < 2 gains = [q["j"] for q in rows if q["cell"] == r["cell"] and q["A"]] print(f" {r['cell']} j {r['j']} of run {r['n']}: Lam_j - 1 " f"{float(r['lam'] - 1):.5f}, B0 {r['B0']} Bv {r['Bv']} C " f"{r['C']}; at n = j naive {naive}, matching {match}, " f"least {least}, the run's last floor-2 unit {last}; budget " f"gains at j = {gains[:3]}{'...' if len(gains) > 3 else ''}") section_totals(rows, K) return rows def section_totals(rows, K): """Every prefix n of each cell with a B0 gain past the matching: the total naive - nu', nu' the matching over the pairwise flags (the budget's at inset 0, or the tree's B0; at the head's link the budget's or hulls.Grid's), against chains.programme's least.""" beats, read = [], 0 for c in sorted({r["cell"] for r in rows if r["B0"] and not r["A"]}): cell = ms.Cell(*c) A1, L1s, S, _ = chains.xy_head(cell) n = chains.run_units(cell, A1) ls = chains.links(cell, chains.xy_head, n) tree = {r["j"]: r["B0"] for r in rows if r["cell"] == c} head = False if ls[0][0] == 2: g = hulls.Grid(cell, L1s, 1, K) head = g.eta_max >= g.d and g.live(g.eta_max)[0] flags = [ls[0][2] or head] + [ls[j - 2][2] or tree.get(j, False) for j in range(3, n + 1)] nu = chains.matchings(flags) for m, (naive, match, least, *_) in chains.programme_all( cell, chains.xy_head, n).items(): read += 1 if naive - nu[m - 2] < least: beats.append((c, m, naive - nu[m - 2], least)) print(f" chains below the programme's least: {len(beats)} of {read} " f"prefixes read, by {sorted({b[3] - b[2] for b in beats})}, at " f"{sorted({b[0] for b in beats})}") print(f" first per cell: " f"{[b for i, b in enumerate(beats) if i == 0 or beats[i - 1][0] != b[0]]}") def section_floor1(K, bmax): """T2: each floor-1 consumer j >= 3 of the chain of run_units at L = 0, its producer at its floor reading inset 0.""" print(f"T2 floor-1 consumers at L = 0, radices 3..{bmax}, K {K}") read, live, top, neg = 0, [], None, 0 for b in range(3, bmax + 1): for cell in hulls.cells1(b, b): A1, L1s, S, _ = chains.xy_head(cell) if S(L1s) < 0: continue n = chains.run_units(cell, A1) units = chain(cell, n) for j in range(3, n + 1): if units[j - 2][1] != 1: continue g = link_grid(cell, units, j, cell.w, K) g0 = make_grid(cell, g.d_fr, cell.Mh ** j, (g.lo / Fr(g.G), g.hi / Fr(g.G)), K, L=0) read += 1 top = g0.eta_fr if top is None else max(top, g0.eta_fr) neg += g0.eta_fr < 0 if verdict(g0)[0]: live.append((b, cell.am, cell.ap, j)) print(f" {read} floor-1 links, eta_max(0) at most " f"{float(top):.4f}, below 0 (dead behind any producer, the " f"generic multiplier) at {neg}; live at L = 0: {live}") return read, live def main(): K = int(sys.argv[1]) if len(sys.argv) > 1 else 40 bmax = int(sys.argv[2]) if len(sys.argv) > 2 else 12 t0 = time.time() section_control(K) if not all(CHECKS): print("CONTROL FAILED; nothing below is read") raise SystemExit(1) section_links(K, bmax) section_floor1(K, bmax) 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()