lattice.py
Cited on: REDUNDANT.
To run it: save lattice.py, with chains.py, hulls.py, manystream.py, poles.py, redundant.py beside it; needs numpy.
"""
lattice.py -- the sum head's tree of hulls on its lattice: does x + y
feed z·U past its budget?
QUESTION, PREDICTIONS, KILL, ARMS and CONTROL: frozen before this
file. The sum x + y read at lead 1 hands
U = (x + y)/b, whose images at U's level m are windows d = 2w/b^L1 wide
starting on a lattice of pitch p = 1/b^L1, offset -2M-/b^L1, the same
relative to every string's value. A tree of hulls (hulls.py) holds every
LATTICE window of a parent's interval in one child; the DENSE arm holds
every window. On the grid of step 1/((b - 1) b^L1) every lattice start,
end and box end is a grid point.
THE DRIFT (the estimate behind P1, P2). In pitches, B = b^L1, a hull
holds j + 1 windows; the budget's is j = B - 1, one integer step and no
drift. At j = B - 1 - x the children's offsets fall x a step; a parent
of j holds 2b + bj + 1 windows, which takes all b + 1 children, a drift
of bx inside an offset range of B/(b - 1) - (2w - 1) + x pitches: so
x <= (b^2 - b - 1)/(b - 1)^2 at L1 = 2, under 2 at every b >= 3,
carried over from the product unchecked: that the first child's
alignment leaves room for it.
PREDICTIONS (frozen). (P1) eta*, the least lattice-tree hull, is the
budget's 1 + d - p or one pitch below it at every slack-1 sum-fed cell,
never two below. (P2) one below at most cells. (P3) where one below,
z·U gains at (L1*, L2* - 1) wherever 0 < Lam2 - 1 <= (Mh/w)(S + p) and
the room allows, cells the budget's criterion does not have.
KILL. "eta* = 1 + d - p at every cell" over the slack-1 sum-fed cells
of radices 3..24. P1 dies on any "two below" line.
CONTROL, printed after the sweep, not gating it. (i) At eta = 1 + d - p the state o = -M- is
sustained and the root covered at every cell. (ii) The greedy with
pitch one grid step equals hulls.py's Grid greedy at (4, 2, 2) and
(20, 8, 12), F arrays identical. (iii) The exact checker passes a
certificate and finds a fault with one child moved past its box.
(iv) (added when the script was carried, since the checker shares
lat() with the greedy and cannot see a misplaced lattice): the image
starts, computed exactly from digit strings, are all lattice points,
and none is once the lattice is moved one grid step.
As run: control (ii) compares against hulls.py's greedy with this
greedy's d one grid step wider: hulls.py's holds every window whose
start lies between grid points (a child starting at most d below the
reach), this one only windows starting on its lattice, so at pitch one
step this dense arm is a looser model than hulls.py's. The DENSE arm's
eta* is
printed beside each cell (designed after the first run, as the
positive check that the engine finds drift on this geometry).
FINDINGS (entered after the run; every number is a print).
- The controls hold: pitch one step reproduces hulls.py's F arrays
at (4, 2, 2) and (20, 8, 12); at (5, 2, 3) the certificate at
1 + d - p has 0 faults and 2 once one child is moved past its box;
the narrowed state and the root live at 1 + d - p at every cell.
(iv): the 961 image starts at (5, 2, 3) are all lattice points, d
wide, and none is with the lattice moved one step; a lattice
misplaced by one step in the engine fails (iv) while (iii) passes
(a scratch copy, run). A pitch too fine passes (iv).
- THE KILL FIRED. eta* = 1 + d - p at all 253 slack-1 sum-fed cells
of radices 3..24, and at all 741 to radix 40 (L1* = 2 at each):
not one pitch below anywhere. P1 holds, P2 and P3 die. The lattice
tree gains exactly the budget's 72 cells, (b, 2, b - 2) and its
mirror, every certificate exact, and nothing else.
- The dense arm drifts below its own 1 + d at all 741 cells, by
exactly b - 2 grid steps at each on the grid K = b^L1 (1 to 38),
and is dead at 1 + d - p at all 741: the drift buys
less than a pitch (b - 1 grid steps), which the lattice budget
already holds. The tree's drift and the lattice buy the same slack.
- A dead verdict prices nothing (whole intervals, increasing order):
the sum head's converse stays open, with no tree counterexample.
RUN RECORD: radices 3..8, 0.2 s, 17.0 MB (the rehearsal); 3..24,
5.9 s, 41.4 MB; with the dense eta*, 17.8 s, 42.6 MB; 3..40, 359.6 s,
185.2 MB; all under a memory guard, K = b^L1 (exact on the lattice).
Bare, with (iv): radices 3..8, 6/6 checks, 0.3 s.
"""
import os
os.environ.setdefault("OPENBLAS_NUM_THREADS", "1")
import sys # noqa: E402
import time # noqa: E402
from fractions import Fraction as Fr # noqa: E402
import numpy as np # noqa: E402
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}")
class LGrid(hulls.Grid):
"""A tree on lattice windows: pitch P and offset c0 in grid units.
head 'sum' sets d, eta_max and the range from the sum head; 'xy'
keeps hulls.Grid's. dense=True sets P = 1, c0 = 0."""
def __init__(self, cell, L1, L2, K, head="sum", dense=False):
super().__init__(cell, L1, L2, K)
b, G = cell.b, self.G
B = b ** L1
if head == "sum":
assert K % B == 0
Mh, w = cell.Mh, cell.w
tau = 2 * Mh / b
self.d_fr = 2 * w / Fr(B)
self.eta_fr = (Fr(b) ** L2 * (w - 1) - tau * w) / Mh
self.d = int(self.d_fr * G)
self.eta_max = int(self.eta_fr * G // 1)
lo, hi = -2 * cell.Mm / b, 2 * cell.Mp / b
assert (lo * G).denominator == 1 and (hi * G).denominator == 1
self.lo, self.hi = int(lo * G), int(hi * G)
self.P = G // B
self.c0 = (-2 * cell.am * K // B) % self.P
if dense or head != "sum":
self.P, self.c0 = 1, 0
def lat(self, x):
"""The first lattice point >= x."""
return x + ((self.c0 - x) % self.P)
def greedy(self, F, start, record=False):
top = self.o + F
PM = np.maximum.accumulate(top)
if record:
idx = np.where(top == PM, np.arange(self.N), 0)
PA = np.maximum.accumulate(idx)
tn = self.lat(start)
picks = []
for e in range(-self.cell.am, self.cell.ap + 1):
j = tn - e * self.G + self.Mm
ok = j >= 0
jj = np.clip(j, 0, self.N - 1)
new = self.lat(e * self.G + PM[jj] - self.d + 1)
take = ok & (new > tn)
if record:
picks.append((e, np.where(take, PA[jj], -1)))
tn = np.where(take, new, tn)
me = tn + self.d - 1
return (me, picks) if record else me
def check(self, F, cert, eta, plant=None):
"""Exact, pure-integer: each state's lattice windows (and the
root's) held, each in one recorded child inside its box with
F <= eta, children in increasing order."""
b, G, d = self.b, self.G, self.d
Fl = [int(x) for x in F]
bad = sum(x > eta for x in Fl)
for s, kids in enumerate(cert):
if s < self.N:
o0 = s - self.Mm
lo, hi = b * o0, b * (o0 + Fl[s])
else:
lo, hi = b * self.lo, b * self.hi
tn, last_e = self.lat(lo), None
for e, i in kids:
oe, Fe = i - self.Mm, Fl[i]
if plant is not None and (s, e) == plant:
oe += G
if not (-self.cell.am <= e <= self.cell.ap):
bad += 1
if last_e is not None and e <= last_e:
bad += 1
if not (-self.Mm <= oe and oe + Fe <= self.Mp):
bad += 1
st = e * G + oe
if st > tn:
bad += 1
tn = max(tn, self.lat(st + Fe - d + 1))
last_e = e
if tn + d <= hi:
bad += 1
return bad
def section_control():
print("L0 controls")
for cell in (ms.Cell(4, 2, 2), ms.Cell(20, 8, 12)):
L1 = chains.floor_xy(cell)
g0 = hulls.Grid(cell, L1, 1, 40)
g1 = LGrid(cell, L1, 1, 40, head="xy")
g1.d += 1 # hulls.py's greedy holds windows one grid step wider
F0, _ = g0.fixpoint(g0.G + g0.d - 3)
F1, _ = g1.fixpoint(g0.G + g0.d - 3)
check(f"({cell.b},{cell.am},{cell.ap}): pitch one step is "
f"hulls.py's greedy", np.array_equal(F0, F1))
cell = ms.Cell(5, 2, 3)
L1 = chains.sum_floor(cell)
K = cell.b ** L1
g = LGrid(cell, L1, 1, K)
h0 = g.G + g.d - g.P
lv, F, _ = g.live(h0)
cert = g.certificate(F)
bad = g.check(F, cert, h0)
s = next(s for s, k in enumerate(cert) if len(k) >= 2 and F[s] >= g.d)
planted = g.check(F, cert, h0, plant=(s, cert[s][0][0]))
check("(5,2,3) sum head at 1 + d - p: live, 0 checker faults, a fault "
"once one child is moved past its box",
lv and bad == 0 and planted > 0,
f"L1 {L1}, faults {bad}, planted {planted}")
starts, widths = image_starts(cell, L1, g.G)
on = sum(g.lat(x) == x for x in starts)
g.c0 = (g.c0 + 1) % g.P
moved = sum(g.lat(x) == x for x in starts)
check("(5,2,3) image starts from digit strings: every one a lattice "
"point, d wide; none once the lattice moves one step",
on == len(starts) and widths == {g.d} and moved == 0,
f"{len(starts)} images, {on} on, {moved} on when moved")
def image_starts(cell, L1, G):
"""The sum head's images at U's level 1, from the digit strings x
and y of length L1: U = (x + y)/b, read in grid units. Exact, and
independent of lat()."""
b, t = cell.b, L1
D = range(-cell.am, cell.ap + 1)
vals = {0}
for _ in range(t):
vals = {b * v + e for v in vals for e in D}
starts, widths = [], set()
for X in vals:
for Y in vals:
lo = (Fr(X) - cell.Mm + Fr(Y) - cell.Mm) / Fr(b) ** t / b
hi = (Fr(X) + cell.Mp + Fr(Y) + cell.Mp) / Fr(b) ** t / b
lo, hi = lo * b * G, hi * b * G
assert lo.denominator == 1 and hi.denominator == 1
starts.append(int(lo))
widths.add(int(hi - lo))
return starts, widths
def cells1(bmin, bmax):
for b in range(bmin, bmax + 1):
for am in range(1, b):
cell = ms.Cell(b, am, b - am)
if chains.sum_fed_ok(cell):
yield cell
def section_sweep(bmax):
print(f"L1 the lattice tree against the budget, radices 3..{bmax}")
rows = []
t0 = time.time()
for cell in cells1(3, bmax):
L1 = chains.sum_floor(cell)
K = cell.b ** L1
lam2 = cell.Mh * (1 + Fr(2, cell.b))
L2 = 1 if lam2 > 1 else 0
naive, least, _, S0 = chains.two_unit(cell, chains.sum_head)
g = LGrid(cell, L1, L2, K)
gd = LGrid(cell, L1, L2, K, dense=True)
P = g.P
h0 = g.G + g.d - P
nar = g.fixpoint(h0)[0][0] >= min(h0, g.Mp + g.Mm)
root0 = g.live(h0)[0]
below = 0
while below < 4 and g.live(h0 - (below + 1) * P)[0]:
below += 1
lv = g.eta_max >= g.d and g.live(g.eta_max)[0]
bad = None
if lv:
F = g.fixpoint(g.eta_max)[0]
bad = g.check(F, g.certificate(F), g.eta_max)
dv = gd.eta_max >= gd.d and gd.live(gd.eta_max)[0]
dbelow = 0
while dbelow < 4 and gd.live(h0 - (dbelow + 1) * P)[0]:
dbelow += 1
dzero = gd.live(h0)[0]
dstar = gd.eta_star(gd.G + gd.d + 2 * gd.G)
dgap = None if dstar is None else gd.G + gd.d - dstar
law = least < naive
rows.append((cell, L1, L2, nar, root0, below, lv, bad, dv, dzero,
dbelow, law, dgap))
tag = "GAIN" if lv and not law else ("gain" if lv else "")
print(f" ({cell.b},{cell.am},{cell.ap}) L1 {L1} L2 {L2}: "
f"narrowed {nar}, root at 1+d-p {root0}; pitches below "
f"{below}; z·U {'live' if lv else 'dead'}"
f"{'' if bad is None else f' (faults {bad})'}, law "
f"{'gain' if law else 'none'}; dense: at 1+d-p {dzero}, "
f"below {dbelow}, z·U {'live' if dv else 'dead'}, eta* "
f"below 1 + d by {dgap}/{gd.G} {tag}",
flush=True)
print(f" cells {len(rows)}, {time.time() - t0:.1f} s")
return rows
def main():
bmax = int(sys.argv[1]) if len(sys.argv) > 1 else 8
section_control()
if not all(CHECKS):
print("CONTROL FAILED; nothing below is read")
raise SystemExit(1)
rows = section_sweep(bmax)
check("control (i): the narrowed state and the root at 1 + d - p, "
"every cell", all(r[3] and r[4] for r in rows))
hist = {}
for r in rows:
hist[r[5]] = hist.get(r[5], 0) + 1
print(f" pitches below the budget's hull: {sorted(hist.items())}")
print(f" eta* = 1 + d - p at every cell: "
f"{all(r[5] == 0 for r in rows)}")
past = [(r[0].b, r[0].am, r[0].ap) for r in rows if r[6] and not r[11]]
lost = [(r[0].b, r[0].am, r[0].ap) for r in rows if r[11] and not r[6]]
dpast = [(r[0].b, r[0].am, r[0].ap) for r in rows
if r[8] and not r[11]]
print(f" lattice z·U live where the budget says none: {past}")
print(f" budget gains the lattice tree misses: {lost}")
print(f" dense z·U live where the budget says none: {dpast}")
dg = [r[12] for r in rows]
print(f" dense arm (designed after the first run): eta* below its "
f"own 1 + d at {sum(1 for x in dg if x and x > 0)} of {len(dg)}"
f" cells, by {min(x for x in dg if x is not None)} to "
f"{max(x for x in dg if x is not None)} grid steps")
faults = [r[7] for r in rows if r[7]]
check("every live certificate exact", not faults, f"{faults[:5]}")
print(f"{sum(CHECKS)}/{len(CHECKS)} checks passed")
raise SystemExit(0 if all(CHECKS) else 1)
if __name__ == "__main__":
main()