branching.py

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