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