"""Exact check of the open-trail growth bound (H2). Windows of memory 6 are the 6-step paths from the origin that use distinct bonds. A step from a window in an admissible direction (its bond is not a bond of the window) has weight 1/5 if the current endpoint is an earlier vertex of the window, x_s/3 = 1000/2883 if it continues straight, and x_t/3 = 200/561 if it turns. The script regenerates the windows and the matrix A_6, reads the positive integer vector v from h2_vector.json, and checks in integer arithmetic that A_6 v <= q v for q = 2499/2500 and that (max v / min v) * (x_t / q)^6 <= 10. With `--make` it first proposes v by floating-point power iteration. The inequalities are checked exactly, and the diagnostics are rounded for display. Run with assertions enabled (without python -O). The vector is read from (and, with --make, written to) h2_vector.json next to this script, or from the file given by --vector PATH.""" import sys, json, os from fractions import Fraction as Fr if not __debug__: sys.exit('h2_check.py: run without python -O (the certificate checks rely on assert statements)') DX = [(1, 0), (0, 1), (-1, 0), (0, -1)] M = 6 Q_NUM, Q_DEN = 2499, 2500 WT = {'s': Fr(1000, 2883), 't': Fr(200, 561), 'r': Fr(1, 5)} def bonds(w): p = (0, 0); out = set(); pts = [p] for d in w: n = (p[0] + DX[d][0], p[1] + DX[d][1]); out.add(frozenset((p, n))); p = n; pts.append(p) return out, pts def windows(): ws = [()] for _ in range(M): nxt = [] for w in ws: b, pts = bonds(w); p = pts[-1] for d in range(4): n = (p[0] + DX[d][0], p[1] + DX[d][1]) if frozenset((p, n)) not in b: nxt.append(w + (d,)) ws = nxt return ws def transitions(w): """admissible steps of the window w: list of (kind, successor)""" b, pts = bonds(w); p = pts[-1]; out = [] for d in range(4): n = (p[0] + DX[d][0], p[1] + DX[d][1]) if frozenset((p, n)) in b: continue kind = 'r' if p in pts[:-1] else ('s' if d == w[-1] else 't') out.append((kind, w[1:] + (d,))) return out VEC = os.path.join(os.path.dirname(os.path.abspath(__file__)), 'h2_vector.json') if '--vector' in sys.argv: VEC = sys.argv[sys.argv.index('--vector') + 1] def main(): ws = windows(); assert len(ws) == 916, len(ws) index = {w: i for i, w in enumerate(ws)} tr = [[(k, index[s]) for k, s in transitions(w)] for w in ws] if '--make' in sys.argv: v = [1.0] * len(ws) for _ in range(20000): nv = [sum(float(WT[k]) * v[j] for k, j in row) for row in tr]; mx = max(nv); v = [x / mx for x in nv] json.dump({'memory': M, 'vector': [int(round(x * 10**12)) for x in v]}, open(VEC, 'w')) v = json.load(open(VEC))['vector'] assert len(v) == len(ws) and all(isinstance(x, int) and x > 0 for x in v) # common denominator of the three weights D = 2883 * 561 * 5; num = {k: int(WT[k] * D) for k in WT}; assert all(Fr(num[k], D) == WT[k] for k in WT) worst = Fr(0) for i, row in enumerate(tr): lhs = sum(num[k] * v[j] for k, j in row) assert Q_DEN * lhs <= Q_NUM * D * v[i], ('row fails', i) worst = max(worst, Fr(lhs, D * v[i])) ratio = Fr(max(v), min(v)); cv = ratio * (Fr(200, 187) * Fr(Q_DEN, Q_NUM)) ** 6 assert cv <= 10 print('windows', len(ws), 'transitions', sum(len(r) for r in tr)) print('largest row ratio (A v)_w / v_w = %.12f <= %d/%d' % (float(worst), Q_NUM, Q_DEN)) print('max v / min v = %.6f, (max v / min v) (x_t / q)^6 = %.6f <= 10' % (float(ratio), float(cv))) print('H2 CHECK PASS: q = %d/%d, C_V = 10' % (Q_NUM, Q_DEN)) main()