"""Certificate for Theorem thm:family-sharp (Section 3 of main.tex). Exact (rational interval arithmetic) certificate: every two-hidden-state fit of d_eps, 0 < eps <= 1/1000, has sum over hidden-incident edge pairs of 2(a-b)^2/(a+b) >= TARGET. Parametrization (proved in the paper): X = K^{-1}C = [[x,1-x],[y,1-y]], x > y, U = R X^{-1}, d = 1^T L X^{-1}, V = diag(d) X L^{-1} R, J = diag(d) X L^{-1} R X^{-1}. The closed forms below are re-derived and checked against these formulas with sympy. """ import sys from fractions import Fraction as Fr import sympy as sp TARGET = Fr(sys.argv[1]) if len(sys.argv) > 1 else Fr(7, 5) # ---------- symbolic derivation and check of closed forms ---------- x, y, e = sp.symbols('x y epsilon') R = sp.Matrix([[7, 5], [5, 7]]) / 3 + e * sp.Matrix([[3, 9], [1, 3]]) / 16 L = sp.Matrix([[251, 337], [265, 443]]) / 2880 X = sp.Matrix([[x, 1 - x], [y, 1 - y]]); Xi = X.inv() d = sp.ones(1, 2) * L * Xi; Dg = sp.diag(d[0], d[1]) U = R * Xi; V = Dg * X * L.inv() * R; J = Dg * X * L.inv() * R * Xi # closed forms used by the interval evaluator (written by hand, verified here) cf = { 'd1': (43 - 108*y) / (240*(x - y)), 'd2': (108*x - 43) / (240*(x - y)), 'U11': (112 - 192*y - e*(36*y - 9)) / (48*(x - y)), 'U12': (192*x - 112 + e*(36*x - 9)) / (48*(x - y)), 'U21': (80 - 192*y - e*(12*y - 3)) / (48*(x - y)), 'U22': (192*x - 80 + e*(12*x - 3)) / (48*(x - y)), 'V11': (43 - 108*y) * (336*x - 100 + e*(48*x - 17)) / (912*(x - y)), 'V12': (43 - 108*y) * (24 - 32*x + e*(48*x - 17)) / (304*(x - y)), 'V21': (108*x - 43) * (336*y - 100 + e*(48*y - 17)) / (912*(x - y)), 'V22': (108*x - 43) * (24 - 32*y + e*(48*y - 17)) / (304*(x - y)), # internal flows h1->h2 = -J12, h2->h1 = -J21 'W12': (108*y - 43) * (100 - 364*x + 240*x**2 + e*(17 - 116*x + 192*x**2)) / (912*(x - y)**2), 'W21': (108*x - 43) * (100 - 364*y + 240*y**2 + e*(17 - 116*y + 192*y**2)) / (912*(x - y)**2), } ref = {'d1': d[0], 'd2': d[1], 'U11': U[0, 0], 'U12': U[0, 1], 'U21': U[1, 0], 'U22': U[1, 1], 'V11': V[0, 0], 'V12': V[0, 1], 'V21': V[1, 0], 'V22': V[1, 1], 'W12': -J[0, 1], 'W21': -J[1, 0]} for k in cf: assert sp.simplify(cf[k] - ref[k]) == 0, k print('closed forms verified') # ---------- exact interval arithmetic ---------- class I: __slots__ = ('lo', 'hi') def __init__(s, lo, hi=None): s.lo = Fr(lo); s.hi = Fr(lo if hi is None else hi); assert s.lo <= s.hi def __add__(s, o): o = o if isinstance(o, I) else I(o); return I(s.lo + o.lo, s.hi + o.hi) __radd__ = __add__ def __neg__(s): return I(-s.hi, -s.lo) def __sub__(s, o): o = o if isinstance(o, I) else I(o); return I(s.lo - o.hi, s.hi - o.lo) def __rsub__(s, o): return I(o) - s def __mul__(s, o): o = o if isinstance(o, I) else I(o) p = [s.lo*o.lo, s.lo*o.hi, s.hi*o.lo, s.hi*o.hi]; return I(min(p), max(p)) __rmul__ = __mul__ def __truediv__(s, o): o = o if isinstance(o, I) else I(o) assert o.lo > 0 or o.hi < 0, 'division by interval containing 0' return s * I(1 / o.hi, 1 / o.lo) if o.lo > 0 else s * I(1 / o.hi, 1 / o.lo) def sq(s): if s.lo >= 0: return I(s.lo**2, s.hi**2) if s.hi <= 0: return I(s.hi**2, s.lo**2) return I(0, max(s.lo**2, s.hi**2)) def flows(X0, X1, Y0, Y1, E0, E1): x, y, e = I(X0, X1), I(Y0, Y1), I(E0, E1) dxy = x - y assert dxy.lo > 0 A = 43 - 108*y; Bx = 108*x - 43 qx = 100 - 364*x + 240*x.sq() + e*(17 - 116*x + 192*x.sq()) qy = 100 - 364*y + 240*y.sq() + e*(17 - 116*y + 192*y.sq()) f = { 'd1': A / (240*dxy), 'd2': Bx / (240*dxy), 'U11': (112 - 192*y - e*(36*y - 9)) / (48*dxy), 'U12': (192*x - 112 + e*(36*x - 9)) / (48*dxy), 'U21': (80 - 192*y - e*(12*y - 3)) / (48*dxy), 'U22': (192*x - 80 + e*(12*x - 3)) / (48*dxy), 'V11': A * (336*x - 100 + e*(48*x - 17)) / (912*dxy), 'V12': A * (24 - 32*x + e*(48*x - 17)) / (304*dxy), 'V21': Bx * (336*y - 100 + e*(48*y - 17)) / (912*dxy), 'V22': Bx * (24 - 32*y + e*(48*y - 17)) / (304*dxy), 'W12': (-A) * qx / (912*dxy.sq()), 'W21': Bx * qy / (912*dxy.sq()), } return f PAIRS = [('U11', 'V11'), ('U12', 'V21'), ('U21', 'V12'), ('U22', 'V22'), ('W12', 'W21')] def glow(a, b): """lower bound of 2(a-b)^2/(a+b) over a in [a.lo,a.hi], b in [b.lo,b.hi], a,b >= 0.""" alo, ahi, blo, bhi = max(a.lo, 0), a.hi, max(b.lo, 0), b.hi if alo > bhi: return 2*(alo - bhi)**2 / (alo + bhi) if blo > ahi: return 2*(blo - ahi)**2 / (blo + ahi) return Fr(0) # feasibility box (proved by hand in the proof of thm:family-sharp): x in [583/1000, 3/4+1/500], y in [2976/10000, 361/1000] XB = (Fr(583, 1000), Fr(752, 1000)); YB = (Fr(2976, 10000), Fr(361, 1000)); EB = (Fr(0), Fr(1, 1000)) stats = {'infeasible': 0, 'certified': 0, 'split': 0} minlb = [None] def certify(X0, X1, Y0, Y1, depth=0): f = flows(X0, X1, Y0, Y1, *EB) if any(v.hi < 0 for v in f.values()) or f['d1'].hi <= 0 or f['d2'].hi <= 0: stats['infeasible'] += 1; return lb = sum(glow(f[a], f[b]) for a, b in PAIRS) if lb >= TARGET: stats['certified'] += 1 if minlb[0] is None or lb < minlb[0]: minlb[0] = lb return assert depth < 40, (X0, X1, Y0, Y1, float(lb)) stats['split'] += 1 xm, ym = (X0 + X1) / 2, (Y0 + Y1) / 2 for a, b in [(X0, xm), (xm, X1)]: for c, dd in [(Y0, ym), (ym, Y1)]: certify(a, b, c, dd, depth + 1) certify(*XB, *YB) print('TARGET', TARGET, stats, 'min certified cell bound', float(minlb[0])) print('CERTIFIED')