"""Integer Bernstein proof of the affine-covariance/Fourier bridge for pentagons. Run with Python 3 and NumPy. Every sign decision uses integer arithmetic. """ from fractions import Fraction as Q from functools import cache from itertools import product from math import comb, isqrt, lcm import numpy as np def det(a): """Determinant of (xx, xy, yy).""" return a[0] * a[2] - a[1] * a[1] def mixed(a, b): """Trace of adj(a) b for symmetric two-by-two matrices.""" return a[0] * b[2] + a[2] * b[0] - 2 * a[1] * b[1] def outer(x, y): return x * x, x * y, y * y def at_node(n, i, j, k, ell, covariance): # q times the vertices are 0, (x,-y), (q,0), (0,q), (-z,w). q = 64 * n * n x, y = 16 * n * (3 * n + i), (3 * n + i) * (7 * n + 9 * j) w, z = 16 * n * (3 * n + k), (3 * n + k) * (7 * n + 9 * ell) s = (x*x + q*q + z*z, -x*y - z*w, y*y + q*q + w*w) tt = outer(x + q - z, -y + q + w) adjacent = (2*q*x, q*(q-y-z), 2*q*w) a = tuple(5*si - ti for si, ti in zip(s, tt)) b = tuple(2*ei - ti + si for ei, ti, si in zip(adjacent, tt, s)) da, db, dab = det(a), det(b), mixed(a, b) gd = da + 5*db # G1 = a + sqrt(5)*b, G2 = a - sqrt(5)*b. if not covariance: # 49 det(G1) - 800 tr(adj(G1) G2). return 49*gd - 800*(2*da - 10*db), 49*dab area = y + q + z m = (y*(x+q) + q*q - z*z, -y*y + q*q + z*(q+w)) # Twelve times the uncentered second moment of each origin triangle. def triangle(px, py, sx, sy): return tuple(c + d + e for c, d, e in zip( outer(px+sx, py+sy), outer(px, py), outer(sx, sy))) left = triangle(x, -y, q, 0) middle = triangle(q, 0, 0, q) right = triangle(0, q, -z, w) e = tuple(y*l + q*c + z*r for l, c, r in zip(left, middle, right)) nn = tuple(3*area*t - 4*f for t, f in zip(e, outer(*m))) dn, ca, cb = det(nn), mixed(a, nn), mixed(b, nn) # 221^2 det(G1) det(N) - 110^2 tr(adj(G1) N)^2. return (221**2*dn*gd - 110**2*(ca*ca + 5*cb*cb), 221**2*dn*dab - 2*110**2*ca*cb) @cache def nodal_to_bernstein(n): """Positive integer multiple of the inverse Bernstein evaluation matrix.""" rows = [[Q(comb(n, i) * j**i * (n-j)**(n-i), n**n) for i in range(n+1)] + [Q(j == i) for i in range(n+1)] for j in range(n+1)] for k in range(n+1): h = next(i for i in range(k, n+1) if rows[i][k]) rows[k], rows[h] = rows[h], rows[k] d = rows[k][k] rows[k] = [v / d for v in rows[k]] for i in range(n+1): if i != k and rows[i][k]: d = rows[i][k] rows[i] = [v - d*w for v, w in zip(rows[i], rows[k])] inv = [row[n+1:] for row in rows] den = lcm(*(v.denominator for row in inv for v in row)) return np.array([[int(v*den) for v in row] for row in inv], dtype=object) def coefficients(n, covariance): vals = np.empty((n+1, n+1, n+1, n+1, 2), dtype=object) for ind in product(range(n+1), repeat=4): vals[ind] = at_node(n, *ind, covariance) op = nodal_to_bernstein(n) for axis in range(4): v = np.moveaxis(vals, axis, 0) vals = np.moveaxis((op @ v.reshape(n+1, -1)).reshape(v.shape), 0, axis) # Enclose sqrt(5) by adjacent rationals. Lowering each Bernstein # coefficient lowers the whole polynomial on the unit cube. d = 10**18 root = isqrt(5*d*d) a, b = vals[..., 0], vals[..., 1] lower = d*a + root*b + np.minimum(b, 0) cap = max(abs(int(lower.min())), abs(int(lower.max()))) fixed = (lower * 2**45) // cap assert max(abs(int(fixed.min())), abs(int(fixed.max()))) <= 2**45 return fixed.astype(np.int64) def halves(t, axis): """Lower Bernstein enclosures on the dyadic children (de Casteljau).""" v = np.moveaxis(t, axis, 0) n = v.shape[0] - 1 left, right = np.empty_like(v), np.empty_like(v) for step in range(n+1): left[step], right[n-step] = v[0], v[-1] if step < n: # Values start bounded by 2^45 and average toward the interior. v = (v[:-1] + v[1:]) // 2 return np.moveaxis(left, 0, axis), np.moveaxis(right, 0, axis) def infeasible(box): # Each constraint is multiaffine. Its minimum is attained at a vertex. lower = list(product(*box)) return (min(v*(1-u)+u*a*(1+v*b) for u, a, v, b in lower) > 1 or min(u*(1-v)+v*b*(1+u*a) for u, a, v, b in lower) > 1) def certify(): p = coefficients(4, False) c = coefficients(12, True) domain = ((Q(3,4), Q(1)), (Q(7,16), Q(1))) * 2 stats = dict(positive=0, infeasible=0, split=0, deepest=0) def inspect(box, p, c, depth): stats['deepest'] = max(stats['deepest'], depth) if p is not None and p.min() > 0: p = None if c is not None and c.min() > 0: c = None if p is None and c is None: stats['positive'] += 1 return if infeasible(box): stats['infeasible'] += 1 return assert depth < 60, ('unresolved box', box) axis = depth % 4 lo, hi = box[axis] mid = (lo+hi)/2 ps = (None, None) if p is None else halves(p, axis) cs = (None, None) if c is None else halves(c, axis) stats['split'] += 1 for interval, pk, ck in zip(((lo, mid), (mid, hi)), ps, cs): inspect(box[:axis] + (interval,) + box[axis+1:], pk, ck, depth+1) inspect(domain, p, c, 0) assert stats['positive'] + stats['infeasible'] == 1 + stats['split'] h = Q(7,40) k = Q(1161,1000)*Q(11,10) s = (k-1)/(k+1) bound_squared = s*s + (1+s)**2*h*h assert bound_squared < Q(231,1000)**2 < Q(47,200)**2 print('Positive or geometrically impossible on the whole domain.', stats) print('Squared physical radius upper bound:', bound_squared, '< (231/1000)^2') if __name__ == '__main__': certify()