"""Arb verification for Taylor expansion of the square's two test functions. Python 3.10+ with python-flint 0.9.0. Run `python local_certificate.py`. """ import argparse from functools import lru_cache from itertools import product from math import comb, factorial from flint import arb, acb, ctx if not __debug__: raise RuntimeError("The certificate requires Python assertions. Run without -O.") ctx.prec = 200 parser = argparse.ArgumentParser() parser.add_argument("--order", type=int, default=22) parser.add_argument( "--radius", help="Use the same positive radius in all four coordinates" ) parser.add_argument("--box", help="Four comma-separated positive radii a,c,p,q") parser.add_argument( "--cauchy", help="Radius >1 for t in the scaled polydisc z_i=t R_i v_i" ) args = parser.parse_args() N = args.order if args.radius and args.box: parser.error("Choose exactly one of --radius and --box.") if args.radius: r = arb(args.radius) rr = [r] * 4 cauchy_radius = 1 / (3 * r) else: rr = list(map(arb, (args.box or "0.21,0.045,0.20,0.28").split(","))) cauchy_radius = arb("1.82") if args.cauchy: cauchy_radius = arb(args.cauchy) assert len(rr) == 4 and all(v > 0 for v in rr) zero = (0, 0, 0, 0) indices = sorted((u for u in product(range(N + 1), repeat=4) if sum(u) <= N), key=sum) def root(): denom = 2**150 left, right = 9 * denom // 10, denom lo = arb(left) / denom hi = arb(right) / denom assert lo.tan() * lo.tanh() < 1 and hi.tan() * hi.tanh() > 1 while right - left > 1: mid = (left + right) // 2 x = arb(mid) / denom f = x.tan() * x.tanh() - 1 if f > 0: right = mid elif f < 0: left = mid else: raise AssertionError("root not separated") return arb(left).union(arb(right)) / denom k = root() sigma = k * k.tanh() assert 8 * sigma > arb(11) / 2 def plus(*polys): out = {} for p in polys: for u, x in p.items(): out[u] = out.get(u, 0) + x return out def times(p, q): out = {} by_degree = [[] for _ in range(N + 1)] for v, y in q.items(): by_degree[sum(v)].append((v, y)) for u, x in p.items(): for grade in by_degree[: N + 1 - sum(u)]: for v, y in grade: w = (u[0] + v[0], u[1] + v[1], u[2] + v[2], u[3] + v[3]) out[w] = out.get(w, 0) + x * y return out def scale(p, f): return {u: x * f for u, x in p.items()} def swap(p): return {(a, c, q, h): (-1) ** a * x for (a, c, h, q), x in p.items()} one = {zero: arb(1)} a, c, p, q = ({tuple(int(j == i) for j in range(4)): arb(1)} for i in range(4)) @lru_cache(None) def moment(axis, freq, endpoint, n): # Integral of z^n exp(lambda z) on [-1,1] or evaluation at endpoint. lam = acb(0, k * freq) if axis == "x" else acb(k * freq) if endpoint: return (lam * endpoint).exp() * endpoint**n if not freq: return acb(0 if n % 2 else (arb(2) / (n + 1))) boundary = lam.exp() - (-1) ** n * (-lam).exp() return (boundary - (n * moment(axis, freq, 0, n - 1) if n else 0)) / lam @lru_cache(None) def power_terms(freqx, freqy, u): # l_a=i*freqx*x-freqy*y, l_c=i*freqx*y+freqy*x, l_p=i*freqx*xy, l_q=freqy*xy. i, j, l, m = u if (l and not freqx) or (m and not freqy): return () terms = {} for h in range(i + 1): for b in range(j + 1): xp = h + b + l + m yp = i - h + j - b + l + m eu = h + j - b + l v = ( comb(i, h) * comb(j, b) * freqx**eu * freqy ** (i + j + l + m - eu) * (-1) ** (i - h) ) if v: old = terms.get((xp, yp), (0, 0)) re = (1, 0, -1, 0)[eu % 4] * v im = (0, 1, 0, -1)[eu % 4] * v terms[xp, yp] = (old[0] + re, old[1] + im) mult = k ** sum(u) for z in u: mult /= factorial(z) return tuple( (xp, yp, acb(re, im) * mult) for (xp, yp), (re, im) in terms.items() if re or im ) @lru_cache(None) def exponential(freqx, freqy, ex, ey, dx=0, dy=0): out = {} for u in indices: terms = power_terms(freqx, freqy, u) if terms: out[u] = sum( v * moment("x", freqx, ex, xp + dx) * moment("y", freqy, ey, yp + dy) for xp, yp, v in terms ) return out def exp_part(fx, fy, ex, ey, dx=0, dy=0, imag=False): return { u: (x.imag if imag else x.real) for u, x in exponential(fx, fy, ex, ey, dx, dy).items() } def reference_energy_moment(dx, dy): summands = plus( exp_part(2, 0, 0, 0, dx, dy), scale( plus(exp_part(0, 2, 0, 0, dx, dy), exp_part(0, -2, 0, 0, dx, dy)), arb(1) / 2, ), ) return scale(summands, k * k / 2) def speed(lin, trans): z = plus(scale(lin, 2), times(lin, lin), times(trans, trans)) power = one ans = one coeff = arb(1) for j in range(1, N + 1): power = times(power, z) coeff = coeff * (arb(3) / 2 - j) / j ans = plus(ans, scale(power, coeff)) return ans def assemble(): jac0 = plus(one, scale(times(a, a), -1), scale(times(c, c), -1)) jacx = plus(q, times(a, q), scale(times(c, p), -1)) jacy = plus(p, scale(times(a, p), -1), scale(times(c, q), -1)) E = plus( times(jac0, reference_energy_moment(0, 0)), times(jacx, reference_energy_moment(1, 0)), times(jacy, reference_energy_moment(0, 1)), ) edge_speed = {} for sign in [1, -1]: edge_speed[0, sign] = speed(plus(a, scale(p, sign)), plus(c, scale(q, sign))) edge_speed[sign, 0] = speed( plus(scale(a, -1), scale(q, sign)), plus(c, scale(p, sign)) ) L8 = scale(plus(*edge_speed.values()), arb(1) / 4) B = {} mean = {} for (x, y), v in edge_speed.items(): cosh = scale(plus(exp_part(0, 2, x, y), exp_part(0, -2, x, y)), arb(1) / 2) mixed = scale(plus(exp_part(2, 2, x, y), exp_part(2, -2, x, y)), arb(1) / 2) square = scale( plus( {zero: arb(2)}, cosh, scale(exp_part(2, 0, x, y), -1), scale(mixed, -1) ), arb(1) / 4, ) moment1 = scale( plus(exp_part(1, 1, x, y, imag=True), exp_part(1, -1, x, y, imag=True)), arb(1) / 2, ) B = plus(B, times(v, square)) mean = plus(mean, times(v, moment1)) H = plus( times(times(L8, L8), E), scale(times(L8, B), -sigma), scale(times(mean, mean), sigma / 8), ) weighted = times(plus(one, a), H) return plus(weighted, swap(weighted)) if __name__ == "__main__": S = assemble() print("k =", k.str(15), "sigma =", sigma.str(15)) for u in indices: if sum(u) <= 4 and not S.get(u, arb(0)).contains(0): print(u, S[u].str(12)) # For |z_i|<=r, each degree-n monomial is at most r^(n-2) times # min_{i,j chosen from that monomial} |z_i z_j|. Bound that product # by a multiple of Q=sum_i d_i z_i^2 with the arithmetic-geometric mean. d = list(map(arb, ("5.8", "28", "1.8", "1.8"))) for i in range(4): v = tuple(2 * int(i == j) for j in range(4)) assert S[v] < -d[i] for u in indices: if sum(u) <= 1 or (sum(u) == 2 and 2 not in u): assert S.get(u, arb(0)).contains(0) cost = [arb(0) for _ in range(N + 1)] for u, coef in S.items(): deg = sum(u) if deg <= 2 or (all(v % 2 == 0 for v in u) and coef < 0): continue candidates = [] radii = arb(1) for i in range(4): radii *= rr[i] ** u[i] if u[i] >= 2: candidates.append(1 / (d[i] * rr[i] ** 2)) for j in range(i): if u[i] and u[j]: candidates.append(1 / (2 * (d[i] * d[j]).sqrt() * rr[i] * rr[j])) cost[deg] += abs(coef) * radii * min(candidates, key=float) for deg, v in enumerate(cost): if deg >= 3: print("relative cost degree", deg, v.str(10)) # Bound the holomorphic extension on a real direction's complex t circle. z = cauchy_radius assert z > 1 aa, cc, pp, qq = rr bb = pp.union(qq).upper() assert z**2 * ((aa + pp) ** 2 + (cc + qq) ** 2) < 1 assert z**2 * ((aa + qq) ** 2 + (cc + pp) ** 2) < 1 displacement = z * (aa + cc + bb) ub = displacement.cosh() * (1 + displacement).cosh() grad = ((2 * displacement).cosh() + (2 * (1 + displacement)).cosh()) / 2 jac = 1 + z * (pp + qq) + z**2 * (aa**2 + cc**2 + (aa + cc) * (pp + qq)) speed2 = (1 + z * (aa + bb)) ** 2 + (z * (cc + bb)) ** 2 height = 2 * (1 + z * aa) * speed2 * (4 * jac * grad + 16 * sigma * ub**2) lower = d[0] * rr[0] ** 2 for dd, rad in zip(d, rr): lower = lower.union(dd * rad**2) tail = height / z ** (N + 1) / (1 - 1 / z) / lower.lower() total = sum(cost) + tail print( "Cauchy height", height.str(10), "relative tail", tail.str(12), "total", total.str(12), "radii", *[x.str(8) for x in rr], ) assert total < 1