""" branching.py -- the branching count: behind any producer, z.U at delay L needs each fibre of U's string to keep at least b children over a set of U's values of positive measure; a fibre of hull at most eta_max(L) has at most floor(b eta_max(L) + w) + 1 child boxes meeting it. Where that is below b, z.U dies at L whatever the producer. THE COUNT (theorem, by hand). z.U dies at L behind any producer whose values fill an interval reaching tau wherever b eta_max(L) + w < b - 1, eta_max(L) = (b^L (w - 1) - tau w)/Mh. Proof outline. A fibre (hull [f1, f2], F = b^n (f2 - f1)) read with z's prefixes N near Mh images to a hull at least w f1 + (Mh - delta) F wide whose left end steps f1 per N; off the neighbourhoods of rationals of small denominator (Dirichlet) those ends are dense mod b^L, so the hull fits a tile only if F <= eta(f1) + eps. The fibres with f1 near such a rational cover a summable measure, so a set A of positive measure near U's extreme has every fibre meeting it, and every ancestor, of hull at most eta_max(L) + eps; each such parent has at most c = floor(b eta_max(L) + w) + 1 children meeting A, and c^n strings of hull eta/b^n cannot cover |A| > 0 unless c >= b. The steps, at level-n scale, M^ = M+ wlog. (a) An interval W wide lies in a level-(n - L) tile for every left end of a set whose gaps mod b^L are below g only if W <= b^L (w - 1) + g. (b) For z's prefixes N with (N - M-)/b^n >= M^ - delta, the image's hull is [(N - M-) f1, (N + M+) f2] (f1 > 0), W >= w f1 + (M^ - delta) F, its left end stepping f1 per N; z is fresh, so all K = delta b^n such N meet the one fibre. (c) Dirichlet: f1/b^L lies within 1/(qK) of some p/q, q <= K; unless q <= Q0 the left ends' gaps mod b^L are below 2 b^L/Q0, so off E_n (those neighbourhoods, q <= Q0) F <= eta(f1) + eps, eta(u) = (b^L (w - 1) - w |u|)/M^. (d) B_n, the union of the fibres with f1 in E_n, has measure O(b^L Q0 log Q0/K + Q0^2 w/b^n), summable in n; near U's extreme take V of positive measure and A = V less the B_n, n >= m, so |A| > 0. (e) A fibre meeting A has every ancestor meeting A, each of hull <= h = eta_max(L) + eps; at the next level its hull is <= b h, and the child boxes (w wide, unit spacing) meeting it number <= floor(b h + w) + 1 = c; the strings meeting A at level n number <= S_m c^(n - m) and cover <= that times h/b^n, yet >= |A|. THE QUESTION. Down a product-fed chain at a slack-1 cell, does the count close floor-1 units at L = 0 behind any tree, and how far upstream of the budget's gains does it leave a floor-2 unit at L = 1 open? PREDICTIONS (frozen). P1: the count kills no certified life (the tree's 19 at link 2; at links j >= 3 the budget's gains and the tree's B0/Bv). P2: at L = 0 down every chain to radix 40 it leaves open only (4, 2, 2) at j >= 8, if that cell is in the population. P3: along the floor-2 runs it leaves 1 to 3 links open upstream of the budget's suffix at the median cell, and exactly the tree's edge link at under 10% of the 228. P4: at link 2 it kills a subset of the pinned count's 259, none of the 15 it leaves. KILL (frozen). "certified lives the count kills: N", N > 0 kills the count. "links the count leaves open past the budget: median X", X > 3 ends the count's use for the edge. CONTROL (read first). At the Mh = 1 slack-1 cells (b, 1, b - 1) and mirror, L = 1, tau = 1, the count kills; at (20, 8, 12) and its mirror, L = 1, tau = Mh^2, it leaves the link open (certified live). FINDINGS (entered after the run; every number a print, K = 200, radices 3..40). - Controls: the count kills L = 1 at every Mh = 1 cell to radix 40; (20, 8, 12) and its mirror left open (margin +2.0896). - P1 HELD: certified lives the count kills: 0 (the tree's 19 at link 2; at links j >= 3 the budget's 727 gains and the tree's B0 744, Bv 745 lives). The first kill does not fire. - P4 HELD: at link 2 the count kills 249 of the 274 the tree leaves dead, every one inside the pinned count's 259, none of the 15 (margin +1.1215 to +1.9722 there). - P3: links the count leaves open past the budget: median 2, total 896 of the 4207, at most 26 (at (40, 2, 38); the next two printed, 25 each, at (39, 2, 37) and (38, 2, 36)); none at 32 of the 228 cells, so no tree gain past the budget there; exactly the edge link at 79, so the tree's gains past the budget sit at the edge or nowhere there. "Under 10%" as frozen was wrong (79 of 228); the second kill (median > 3) does not fire. - P2 HELD: at L = 0, over the cells of T1's population, consumers j >= 2 with Lam_j <= 1 read until the first the count leaves open, or until tau < 10^-6 (or j = 400) where its tau -> 0 margin is negative: 26741 in all, a count the cutoffs set. The count leaves open only (4, 2, 2) from j = 8 (deeper units there not read; by hand its margin is 1/3 - 8 tau, tau = (2/3)^j). As the margin rises when tau falls, the tau -> 0 limit decides every deeper unit. In the limit tau -> 0, radices 3..200, it leaves open only (3, 1, 2), (3, 2, 1) (Mh = 1, so tau = 1 at every j and the limit never occurs) and (4, 2, 2). - THE INSTRUMENT. At (4, 2, 2), L = 0, j = 9..13, the producer's root read at level 1 is narrower than a window (b (hi - lo) 128 against d 142 at j = 9), a root a cover passes with no child; hulls.Grid gives it no verdict (B0's last control), so the grid's silence there is no life. RUN RECORD: bare (K = 40, radices 3..12) 0.4 s; K = 200, radices 3..40, 94.4 s, peak 38.3 MB under a memory guard; again 120.0 s, 38.4 MB, beside two readers. USAGE: python branching.py [K [bmax]], K = 40, bmax = 12 bare; the record run python branching.py 200 40. """ 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 import pinned # noqa: E402 import twolinks # noqa: E402 CHECKS = [] def check(name, ok, detail=""): CHECKS.append(bool(ok)) print(f" {'PASS' if ok else 'FAIL'} {name} ({detail})") def margin(cell, L, tau): """b eta_max(L) + w - (b - 1): the count kills iff negative.""" eta = (Fr(cell.b) ** L * (cell.w - 1) - tau * cell.w) / cell.Mh return cell.b * eta + cell.w - (cell.b - 1) def tag(c): return (c.b, c.am, c.ap) def section_control(): print("B0 controls") off = [b for b in range(3, 41) for c in (ms.Cell(b, 1, b - 1), ms.Cell(b, b - 1, 1)) if margin(c, 1, Fr(1)) >= 0] check("B0 the count kills L = 1 at every Mh = 1 cell, radices 3..40", not off, f"open at {off[:4]}") for c in (ms.Cell(20, 8, 12), ms.Cell(20, 12, 8)): m = margin(c, 1, c.Mh ** 2) check(f"B0 {tag(c)} at L = 1 left open (certified live)", m >= 0, f"margin {float(m):+.4f}") cell = ms.Cell(4, 2, 2) units = twolinks.chain(cell, 10) g = twolinks.link_grid(cell, units, 9, cell.w, 200) g0 = twolinks.make_grid(cell, g.d_fr, cell.Mh ** 9, (g.lo / Fr(g.G), g.hi / Fr(g.G)), 200, L=0) check("B0 a root narrower than a window gets no verdict ((4, 2, 2), " "j = 9, L = 0)", cell.b * (g0.hi - g0.lo) <= g0.d and not twolinks.verdict(g0)[0], f"b (hi - lo) {cell.b * (g0.hi - g0.lo)}, d {g0.d}") def section_link2(bmax): print(f"B1 link 2 at L = 1, radices 3..{bmax}") gains, rest, kill, spare = pinned.section_sweep(bmax) bad = [tag(c) for c in gains if margin(c, 1, c.Mh ** 2) < 0] dead = [c for c in rest if margin(c, 1, c.Mh ** 2) < 0] ks = {tag(c) for c in kill} print(f" the count kills {len(dead)} of the {len(rest)} the tree " f"leaves dead; outside the pinned count's {len(kill)}: " f"{[tag(c) for c in dead if tag(c) not in ks]}; among the " f"{len(spare)}: {[tag(c) for c in dead if c in spare]}") m15 = [float(margin(c, 1, c.Mh ** 2)) for c in spare] if m15: print(f" margin at the {len(spare)}: {min(m15):+.4f} to " f"{max(m15):+.4f}") return bad def section_chain(K, bmax): print(f"B2 floor-2 links j >= 3 at L = 1, radices 3..{bmax}, K {K}") rows = twolinks.section_links(K, bmax) bad = [(r["cell"], r["j"]) for r in rows if (r["A"] or r["B0"] or r["Bv"]) and margin(ms.Cell(*r["cell"]), 1, ms.Cell(*r["cell"]).Mh ** r["j"]) < 0] opens, exact, far = [], [], [] for c in sorted({r["cell"] for r in rows}): cell = ms.Cell(*c) mine = sorted((r for r in rows if r["cell"] == c), key=lambda r: r["j"]) ga = [r["j"] for r in mine if r["A"]] edge = ga[0] - 1 if ga else mine[-1]["j"] op = [r["j"] for r in mine if not r["A"] and margin(cell, 1, cell.Mh ** r["j"]) >= 0] opens.append(len(op)) if op == [edge]: exact.append(c) far.append((len(op), c, op[:3])) opens.sort() med = opens[len(opens) // 2] if opens else None print(f" links the count leaves open past the budget: median {med}," f" total {sum(opens)} of {len(rows)}, at most {max(opens or [0])}" f"; none at {opens.count(0)} cells; exactly the edge link at " f"{len(exact)} of {len(opens)} cells {exact[:6]}") far.sort(reverse=True) print(f" widest: {far[:3]}") return bad def section_floor1(bmax, bfar): print(f"B3 floor-1 consumers at L = 0, radices 3..{bmax}; the limit " f"tau -> 0 to {bfar}") read, opened = 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 j = 2 while True: tau = cell.Mh ** j lam = cell.Mh + tau if chains.unit_floor(cell, lam) == 1: read += 1 if margin(cell, 0, tau) >= 0: opened.append((tag(cell), j)) break if margin(cell, 0, Fr(0)) < 0 and tau < Fr(1, 10 ** 6): break j += 1 if j > 400: break print(f" {read} floor-1 consumers read; the first the count leaves " f"open per cell: {opened}") for c, j0 in opened: cell = ms.Cell(*c) units = twolinks.chain(cell, j0 + 6) out = [] for j in range(j0, j0 + 6): g = twolinks.link_grid(cell, units, j, cell.w, 200) g0 = twolinks.make_grid(cell, g.d_fr, cell.Mh ** j, (g.lo / Fr(g.G), g.hi / Fr(g.G)), 200, L=0) out.append((j, round(float(g0.eta_fr), 4), round(float(g0.d_fr), 4), twolinks.verdict(g0))) print(f" the grid at L = 0, K 200, at {c}: (j, eta_max(0), d, " f"live) {out}") lim = [] for b in range(3, bfar + 1): for am in range(1, b): c = ms.Cell(b, am, b - am) if margin(c, 0, Fr(0)) >= 0: lim.append(tag(c)) print(f" slack-1 cells where the count leaves L = 0 open as " f"tau -> 0, radices 3..{bfar}: {lim}") return opened, lim 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() if not all(CHECKS): print("CONTROL FAILED; nothing below is read") raise SystemExit(1) bad = section_link2(bmax) bad += section_chain(K, bmax) print(f" certified lives the count kills: {len(bad)} {bad[:4]}") check("P1 the count kills no certified life", not bad, f"{len(bad)}") section_floor1(bmax, 200) 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()