""" pinned.py -- a count over one pinned input family behind a product: does it kill z.U at (L1*, 1) at the slack-1 cells the tree of hulls leaves dead, where the private-zone floor prices only on derived limits? QUESTION, PREDICTIONS, KILL and CONTROLS: frozen before the run. At a slack-1 representable cell with M^ < 1 and L2* = 2, pin x at its top string (a+ >= a-; at its bottom string in the mirror) and let y run. In level-n coordinates the images' upper ends (the mirror's: likewise, decreasing in the index) form an exact progression p t + M^^2 e, p = M^ e, e = b^-L1*, t = b^N Y the y string's integer, at every level; their widths W(t) = w e (M^ + |Y| - (the other side) eps), eps = b^-N, tend to d = 2 M^ w e at the corner. A set of indices t0 < t1 has hull p(t1 - t0) + W at its least-width end. Near tau = M^^2 the generic multiplier caps a held set's index span at Sigma = floor((eta_max - d)/p); one more y digit sends n indices to at least b n + rho, their upper ends p(b sigma + I) long (sigma <= Sigma the parents' index span), met by at most H = floor(p(b Sigma + I) + w - d) + 1 children; H <= b, i.e. K = b - p(b Sigma + I) - (w - d) > 0, makes the held sizes climb past Sigma + 1: z.U dies at (L1*, 1). THE BAND (an estimate, the floor's rounding and the room dropped): with lambda = Lam2 - 1, K > 0 about where lambda > (M^/w)(2/(b - 1) - d(b + 1)/b + p), and the budget gains where lambda <= (M^/w)(1/(b - 1) - d): the count leaves a band about (M^/w)/(b - 1) wide. THE CAP, re-derived. Fix u near tau of large prime denominator q. A string whose hull lies within a bounded distance of b^n u dies, n -> infinity, once its hull exceeds eta(u) + b^L2/(q M^): z.h = N h b^-(n+1), and h b^-n = u + O(b^-n) moves the window's left ends by q.O(b^-n) over q consecutive z prefixes, so they stay a coset of (1/q)Z up to o(1). A climb of J <= Sigma + 2 levels from a singleton near b^n u stays within b^J.O(1) of b^(n+J) u, so the cap holds along it; as u -> tau- and q -> infinity the cap falls to eta_max and W rises to d, so the span bound tends to Sigma from above (exact at an integer too), and K > 0 survives the limit. The lower ends drift (pitch p - w e eps); the count reads only upper ends and never meets it. THE EXACT BRANCH (by hand). On the negative y box |u| -> M+ M-, the cap there is eta = (b/m)(1 - m(b - m)/(b - 1)^2), m = max a+-, and eta - 1 = (b - m)((b - 1)^2 - b m)/(m (b - 1)^2) > 0 as m <= b - 2 (M^ < 1). The count needs cap < 1 - 1/(b - 1) + W(b + 1)/b with W -> w^2 e; L1* >= 2 at slack 1 (b^L >= 2 M^ b > b), so W(b + 1)/b <= (b + 1)/(b(b - 1)^2) < 1/(b - 1) at b >= 3, the bound below 1: that branch kills nowhere. THE SIZE BOUND (by hand, in the count's limit). Where -1 < K <= 0 (the 15), H = b + 1: child k holds an upper end h iff h in [k + d - M-, k + M+], so the end children's windows cut to the hull, f1 = k0 + M+ - h0 and f2 = h0 + R - kb - d + M- (R = p(b sigma + I)), total R + w - d - b <= -K, and they hold E1 + E2 <= floor(-K/p) + 2 positions. n indices in r blocks send exactly b n + r (I = b), so every child holding <= n needs n <= E1 + E2 - r: a held set past n0 = floor(1 - K/p) indices sends a child n + 1 and climbs past Sigma + 1. An interior child alone holds h in (k - 1 + M+, k + 1 + d - M-), at least ceil((2 - w + d)/p) - 1 positions, more than n0 at the 15 (printed): a live set's children never fill it. PREDICTIONS (frozen). (Q1, by hand) the exact branch kills nowhere. (Q2) K > 0 at (5, 2, 3), K < 0 at (4, 2, 2). (Q3) K <= 0 at all 19 tree-certified gains. (Q4) K > 0 at most of the 274, unpriced at 5 to 40 of them, each in a band above the budget's edge. (Q5) K <= 0 at every (b, 2, b - 1), b = 3..200. (Q6) n0 = 59 at (7, 3, 4) of Sigma + 1 = 70; H = b + 1 and the interior child's own run above n0 at all 15; by brute at the four of radix 7 and 10, every phase, depth 3, the end children hold <= n0 + 1 and an interior child alone >= its bound. CONTROLS. (C1) images by Fractions from digit strings: upper ends and widths as above, every image, levels 0..3 (an exact equality: no plant reads it). (C2) H by brute: index windows of span Sigma at every phase near the corner, the children able to hold an image counted from exact boxes, = H (as run; frozen <= H), and <= b where K > 0. (C3) the 19 from hulls.py's Grid (K 200), certificate faults 0. FINDINGS (entered after the run; every number a print). - The controls hold. C1: every pinned image from digit strings at (5, 2, 3), (4, 2, 2) and the mirror (10, 6, 4), levels 0..3 (0..2 at b = 10), has its upper end on p t + M^^2 e (mirror -p t + ...) and width W(t): 5592, 1948 and 9654 images, 0 off. C2: at six cells, every phase of the period (b - 1) b^L1*, the brute count of children able to hold an image of a span-Sigma window's descendants equals the formula's H at each (5, 6, 11, 5, 4, 8), <= b at the four with K > 0; with the holders' interval one short (a scratch copy, run) all six fail. C3: hulls.py's Grid (K 200) certifies 19, 0 faults, 274 dead, radices 3..40. - Q1 HOLDS: the exact branch's cap exceeds the count's bound at all 12090 representable slack-1 cells with M^ < 1 to radix 200, least margin 0.00500 at (200, 2, 198) (the hand proof covers every radix). Q2 HOLDS: K = 21/40 at (5, 2, 3), -25/18 at (4, 2, 2). Q3 HOLDS: K <= 0 at all 19 gains, K from -1.950 to -1.039. Q5 HOLDS: K <= 0 at every (b, 2, b - 1), b = 3..200, largest -2/3 at b = 3. - Q4 HOLDS. THE KILL: K > 0 at 259 of the 274 (none of the 19), the least 0.0512 at (26, 10, 16): there z.U dies at (L1*, 1), proved. K <= 0 at 15, each L1* = 2, eta_max 0.926 to 0.994, the band ratio r = lambda w (b - 1)/M^ from 1.159 to 1.882 (the budget's edge at r = 1 - d(b - 1) or below): (7, 3, 4), (7, 4, 3), (10, 4, 6), (10, 6, 4), (15, 6, 9), (15, 9, 6), (18, 7, 11), (23, 9, 14), (23, 14, 9), (28, 11, 17), (28, 17, 11), (31, 12, 19), (36, 14, 22), (36, 22, 14), (39, 15, 24). Radices 41..200, representable, slack 1, L2* = 2, M^ < 1: K > 0 at 7136 of 7297; at the 161 others r runs 0.011 to 1.975, and the budget gains (chains.py's two_unit) at 88, all among the 161. - Q6 HOLDS. n0 from 35 (of Sigma + 1 = 137, at (10, 4, 6)) to 1298 (of 2039, at (36, 14, 22)); 237 of 2351 at (39, 15, 24), 59 of 70 at (7, 3, 4); H = b + 1 at all 15, the own run exceeding n0 by 4 or more. By brute both bounds are attained: the end children hold 60 = n0 + 1 at radix 7 and 36 at radix 10, an interior child alone 63 and 135, at 238 and 240 phases meeting b + 1 children; with the bar at n0 (a scratch copy, run; frozen as n0 - 1, the run's bar the nearer to the truth) all four fail. USAGE: python pinned.py [bmax [bfar]], bmax = 40 (the 274), bfar = 200. RUN RECORD: 8 20, 17/19 (the two radix-40 counts), 0.6 s (the rehearsal); 40 200, 19/19, 2.2 s, peak 34.0 MB, under a memory guard; with C1's plant dropped, C2 an equality and the budget's gains, 17/17, 4.1 s, 33.6 MB; with the size bound, 23/23, 4.7 s. """ import os import sys import time import itertools from fractions import Fraction as Fr from math import floor os.environ.setdefault("OPENBLAS_NUM_THREADS", "1") import chains # noqa: E402 import hulls # noqa: E402 import manystream as ms # noqa: E402 CHECKS = [] 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 tag(c): return (c.b, c.am, c.ap) def params(cell): """(L1, e, p, d, eta_max at L2 = 1, Sigma, K), exact.""" b, w, Mh = cell.b, cell.w, cell.Mh L1 = chains.floor_xy(cell) e = Fr(1, b ** L1) p, d = Mh * e, 2 * Mh * w * e eta = (b * (w - 1) - Mh ** 2 * w) / Mh Sigma = floor((eta - d) / p) K = b - p * (b * Sigma + cell.I) - (w - d) return L1, e, p, d, eta, Sigma, K def mirror(cell): return cell.am > cell.ap def x_box(cell, N): eps = Fr(1, cell.b ** N) if mirror(cell): xv = -cell.Mm * (1 - eps) else: xv = cell.Mp * (1 - eps) return xv - cell.Mm * eps, xv + cell.Mp * eps def image(cell, N, n, t, xb=None): """The pinned image of the y string with integer t, N digits read, in level-n coordinates (exact, from the boxes' corners).""" b = cell.b eps = Fr(1, b ** N) x0, x1 = xb if xb is not None else x_box(cell, N) y = t * eps y0, y1 = y - cell.Mm * eps, y + cell.Mp * eps pr = (x0 * y0, x0 * y1, x1 * y0, x1 * y1) s = b ** n return min(pr) * s, max(pr) * s, y0, y1 def section_c1(): print("C1 the pinned images from digit strings, levels 0..3") for c in (ms.Cell(5, 2, 3), ms.Cell(4, 2, 2), ms.Cell(10, 6, 4)): L1, e, p, d, eta, Sigma, K = params(c) Mh, w = c.Mh, c.w side = Mh # the far side's bound in the width other = c.Mp if mirror(c) else c.Mm D = range(-c.am, c.ap + 1) bad = seen = 0 for n in range(0, 3 if c.b > 6 else 4): N = n + L1 eps = Fr(1, c.b ** N) xb = x_box(c, N) for ds in itertools.product(D, repeat=N): t = 0 for dg in ds: t = t * c.b + dg lo, hi, y0, y1 = image(c, N, n, t, xb) if mirror(c): if y1 >= 0: continue up = -p * t + Mh ** 2 * e W = w * e * (side - t * eps - other * eps) else: if y0 <= 0: continue up = p * t + Mh ** 2 * e W = w * e * (side + t * eps - other * eps) seen += 1 bad += (hi != up) or (hi - lo != W) check(f"{tag(c)}: upper ends p t + M^^2 e and widths W(t) exact", bad == 0 and seen > 0, f"{seen} images, {bad} off") def brute_H(cell, nd=3): """Max over phases of the children able to hold an image of an index window of span Sigma's descendants, at the corner (exact boxes).""" L1, e, p, d, eta, Sigma, K = params(cell) b = cell.b N = nd + L1 edge = (cell.ap if not mirror(cell) else -cell.am) * (b ** N - 1) \ // (b - 1) period = (b - 1) * b ** L1 phases = period sgn = -1 if mirror(cell) else 1 # parent windows [t0, t0 + Sigma] (mirror: [t0 - Sigma, t0]) moving # inward from the corner by one index per phase xb1 = x_box(cell, N + 1) ok_cache = {} def holders(tp): if tp not in ok_cache: lo, hi, _, _ = image(cell, N + 1, nd + 1, tp, xb1) a = hi - cell.Mp z = lo + cell.Mm ok_cache[tp] = range(-(-a.numerator // a.denominator), z.numerator // z.denominator + 1) return ok_cache[tp] worst = 0 for ph in range(phases): far = edge - sgn * ph # the window's corner-side end near = far - sgn * Sigma t0, t1 = min(far, near), max(far, near) ch = set() for tp in range(b * t0 - cell.am, b * t1 + cell.ap + 1): ch.update(holders(tp)) worst = max(worst, len(ch)) Hf = floor(p * (b * Sigma + cell.I) + cell.w - d) + 1 return worst, Hf, K, phases def section_c2(): print("C2 H by brute at the corner, every phase") cells = [ms.Cell(5, 2, 3), ms.Cell(4, 2, 2), ms.Cell(10, 6, 4), ms.Cell(6, 2, 4), ms.Cell(7, 2, 5), ms.Cell(8, 3, 5)] for c in cells: if not (chains.representable(c) and c.Mh < 1): print(f" {tag(c)} skipped: not in the arm") continue worst, Hf, K, ph = brute_H(c) ok = worst == Hf and (K <= 0 or worst <= c.b) check(f"{tag(c)}: brute children {worst} = H {Hf}" f"{', <= b' if K > 0 else ''}", ok, f"K {float(K):+.4f}, {ph} phases") def section_hand(): print("Q2 the hand values") c = ms.Cell(5, 2, 3) L1, e, p, d, eta, Sigma, K = params(c) check("(5,2,3): L1* 2, p 3/100, d 3/40, eta_max 35/48, Sigma 21, " "K 21/40", (L1, p, d, eta, Sigma, K) == (2, Fr(3, 100), Fr(3, 40), Fr(35, 48), 21, Fr(21, 40)), f"K {K}") c = ms.Cell(4, 2, 2) L1, e, p, d, eta, Sigma, K = params(c) check("(4,2,2): Sigma 24, K < 0", Sigma == 24 and K < 0, f"K {K}") def section_exact_branch(bfar): print(f"Q1 the exact branch's cap against the count's bound, " f"radices 3..{bfar}") worst = None n = 0 for c in hulls.cells1(3, bfar): L1 = chains.floor_xy(c) e = Fr(1, c.b ** L1) cap = c.w * (1 - c.Mm * c.Mp) / c.Mh W = c.w ** 2 * e bound = 1 + W * (1 + Fr(1, c.b)) - c.w / c.b m = cap - bound n += 1 if worst is None or m < worst[0]: worst = (m, tag(c)) check("the exact branch's cap above the count's bound at every " "slack-1 cell, M^ < 1", worst[0] > 0, f"{n} cells, least margin {float(worst[0]):.5f} at {worst[1]}") def section_sweep(bmax): print(f"C3/Q3/Q4 the tree's gains and the 274, radices 3..{bmax}") gains, rest = [], [] faults = 0 for c in hulls.cells1(3, bmax): if c.Mh ** 2 + c.Mh <= 1: continue L1 = chains.floor_xy(c) g = hulls.Grid(c, L1, 1, 200) lv = False if g.eta_max >= g.d: lv, F, _ = g.live(g.eta_max) if lv: faults += g.check(F, g.certificate(F), g.eta_max) (gains if lv else rest).append(c) check("C3: the tree certifies 19, faults 0", len(gains) == 19 and faults == 0, f"{len(gains)} live, {len(rest)} dead, " f"faults {faults}") print(" the 19: " + " ".join(str(tag(c)) for c in gains)) kg = [c for c in gains if params(c)[6] > 0] check("Q3: K <= 0 at all 19 gains", not kg, f"K > 0 at {[tag(c) for c in kg]}") print(f" K at the gains: {min(float(params(c)[6]) for c in gains):.3f}" f" to {max(float(params(c)[6]) for c in gains):.3f}") kill = [c for c in rest if params(c)[6] > 0] spare = [c for c in rest if params(c)[6] <= 0] print(f" THE KILL: K > 0 at {len(kill)} of the {len(rest)}; " f"K <= 0 at {len(spare)}:") for c in spare: L1, e, p, d, eta, Sigma, K = params(c) lam = c.Mh ** 2 + c.Mh - 1 r = lam * c.w * (c.b - 1) / c.Mh print(f" {tag(c)} L1* {L1} Sigma {Sigma} K {float(K):+.4f}" f" eta_max {float(eta):.4f} band r {float(r):.3f}") check("Q4: unpriced at 5 to 40 of the 274", 5 <= len(spare) <= 40, f"{len(spare)}") if kill: least = min(kill, key=lambda c: params(c)[6]) print(f" least K among the kills {float(params(least)[6]):.4f}" f" at {tag(least)}") return gains, rest, kill, spare def brute_bound(cell, nd=3): """At the corner, every phase of a span-Sigma window: the most positions the two end children can hold together (phases meeting b + 1 children), and the fewest positions an interior child alone can hold (exact boxes).""" L1, e, p, d, eta, Sigma, K = params(cell) b = cell.b N = nd + L1 edge = (cell.ap if not mirror(cell) else -cell.am) * (b ** N - 1) \ // (b - 1) sgn = -1 if mirror(cell) else 1 xb1 = x_box(cell, N + 1) cache = {} def holders(tp): if tp not in cache: lo, hi, _, _ = image(cell, N + 1, nd + 1, tp, xb1) a, z = hi - cell.Mp, lo + cell.Mm cache[tp] = (-(-a.numerator // a.denominator), z.numerator // z.denominator) return cache[tp] most_ends, fewest_own, full = 0, None, 0 for ph in range((b - 1) * b ** L1): far = edge - sgn * ph near = far - sgn * Sigma t0, t1 = min(far, near), max(far, near) held, own = {}, {} for tp in range(b * t0 - cell.am, b * t1 + cell.ap + 1): k0, k1 = holders(tp) for k in range(k0, k1 + 1): held[k] = held.get(k, 0) + 1 if k0 == k1: own[k0] = own.get(k0, 0) + 1 lo, hi = min(held), max(held) if hi - lo == b: full += 1 most_ends = max(most_ends, held[lo] + held[hi]) for k in range(lo + 1, hi): c = own.get(k, 0) fewest_own = c if fewest_own is None else min(fewest_own, c) return most_ends, fewest_own, full def section_bound(spare): print("BOUND a held set at the 15 holds <= n0 = floor(1 - K/p)") rows = [] for c in spare: L1, e, p, d, eta, Sigma, K = params(c) n0 = floor(1 - K / p) U = 2 - c.w + d own = -floor(-U / p) - 1 H = floor(p * (c.b * Sigma + c.I) + c.w - d) + 1 rows.append((c, n0, own, H, Sigma)) print(f" {tag(c)} Sigma + 1 {Sigma + 1} n0 {n0} " f"own window >= {own} H {H}") check("(7,3,4): n0 59 of Sigma + 1 70", [(r[1], r[4] + 1) for r in rows if tag(r[0]) == (7, 3, 4)] == [(59, 70)]) check("H = b + 1 and the own window above n0 at all 15", len(rows) == 15 and all(H == c.b + 1 and own > n0 for c, n0, own, H, _ in rows), f"least own - n0 {min(own - n0 for _, n0, own, _, _ in rows)}") for c, n0, own, H, _ in rows: if c.b > 10: continue ends, fewest, full = brute_bound(c) check(f"{tag(c)} by brute: end children hold {ends} <= n0 + 1 " f"{n0 + 1}, an interior child alone {fewest} >= {own}", full > 0 and ends <= n0 + 1 and fewest >= own, f"{full} phases meet b + 1 children") def section_family(bfar): print(f"Q5 the family (b, 2, b - 1), b = 3..{bfar}") bad = [] least = None for b in range(3, bfar + 1): c = ms.Cell(b, 2, b - 1) L1, e, p, d, eta, Sigma, K = params(c) assert eta == 1 if K > 0: bad.append(b) if least is None or K > least[0]: least = (K, b) check("Q5: K <= 0 at every b", not bad, f"K > 0 at {bad[:10]}; " f"largest K {float(least[0]):.4f} at b = {least[1]}") def section_far(bmax, bfar): print(f"FAR the closed form at slack 1, L2* = 2, radices " f"{bmax + 1}..{bfar}") n = k = 0 rs, bg = [], [] for c in hulls.cells1(bmax + 1, bfar): if c.Mh ** 2 + c.Mh <= 1: continue n += 1 K = params(c)[6] if K > 0: k += 1 else: lam = c.Mh ** 2 + c.Mh - 1 rs.append(float(lam * c.w * (c.b - 1) / c.Mh)) naive, least, _, _ = chains.two_unit(c, chains.xy_head) if least < naive: bg.append((tag(c), K)) print(f" K > 0 at {k} of {n}; K <= 0 at {n - k}, band r " f"{min(rs):.3f} to {max(rs):.3f}") kb = [t for t, K in bg if K > 0] check("the budget's gains have K <= 0", not kb, f"{len(bg)} budget gains, {len(bg) - len(kb)} with K <= 0; " f"K > 0 at {kb}") def main(): bmax = int(sys.argv[1]) if len(sys.argv) > 1 else 40 bfar = int(sys.argv[2]) if len(sys.argv) > 2 else 200 t0 = time.time() section_c1() section_hand() section_c2() if not all(CHECKS): print("CONTROL FAILED; nothing below is read") raise SystemExit(1) section_exact_branch(bfar) gains, rest, kill, spare = section_sweep(bmax) if bmax >= 40: section_bound(spare) section_family(bfar) section_far(bmax, bfar) 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()