pinned.py
Checks: LATENCY: The threshold-miss law theorem; rule; pattern.
Cited on: LATENCY.
To run it: save pinned.py, with chains.py, hulls.py, manystream.py, poles.py, redundant.py beside it; needs numpy.
"""
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()