#!/usr/bin/env python3
# verify-pde-learning.py
# Companion script to "Partial Differential Equations in Machine Learning and AI: Naturality, Well-Posedness,
# and Spectral Rates" (Higher Categorical Semantics, 2026; byline Anonymous).
# 42 computational checks of the numerical statements in the paper. Python standard library only; fixed seed.
# Usage: python3 verify-pde-learning.py   (a few seconds; exit status 0 iff every check passes)
# The checks recompute examples and test instances of structural statements. They are evidence, not proofs.
# Written and run with AI assistance (Anthropic's Claude).
import math, cmath, random, sys, itertools
from fractions import Fraction as Fr

random.seed(20261117)
_n = [0, 0]
PI = math.pi


def sec(title):
    print('\n== ' + title + ' ==')


def check(name, ok, detail=''):
    _n[0] += 1
    _n[1] += 0 if ok else 1
    print(('PASS  ' if ok else 'FAIL  ') + name + (('\n      [' + detail + ']') if detail else ''))


def footer():
    print('\n%d checks, %d passed, %d failed' % (_n[0], _n[0] - _n[1], _n[1]))
    sys.exit(1 if _n[1] else 0)


def close(a, b, tol=1e-9):
    return abs(a - b) <= tol * (1 + abs(a) + abs(b))


# ---------- linear algebra (lists of lists) ----------
def eye(n):
    return [[1.0 if i == j else 0.0 for j in range(n)] for i in range(n)]


def tr(A):
    return [list(r) for r in zip(*A)]


def mm(A, B):
    Bt = list(zip(*B))
    return [[sum(a * b for a, b in zip(r, c)) for c in Bt] for r in A]


def mv(A, x):
    return [sum(a * b for a, b in zip(r, x)) for r in A]


def dot(x, y):
    return sum(a * b for a, b in zip(x, y))


def axpy(a, x, y):
    return [a * xi + yi for xi, yi in zip(x, y)]


def solve(A, b):
    n = len(A)
    M = [list(A[i]) + [b[i]] for i in range(n)]
    for c in range(n):
        p = max(range(c, n), key=lambda r: abs(M[r][c]))
        M[c], M[p] = M[p], M[c]
        piv = M[c][c]
        for r in range(c + 1, n):
            f = M[r][c] / piv
            if f:
                Mr, Mc = M[r], M[c]
                for k in range(c, n + 1):
                    Mr[k] -= f * Mc[k]
    x = [0.0] * n
    for i in range(n - 1, -1, -1):
        x[i] = (M[i][n] - sum(M[i][k] * x[k] for k in range(i + 1, n))) / M[i][i]
    return x


def inv(A):
    n = len(A)
    cols = [solve(A, [1.0 if i == j else 0.0 for i in range(n)]) for j in range(n)]
    return tr(cols)


def rank_exact(rows):
    M = [[Fr(v) for v in r] for r in rows]
    rk, ncol = 0, (len(M[0]) if M else 0)
    for c in range(ncol):
        p = next((r for r in range(rk, len(M)) if M[r][c] != 0), None)
        if p is None:
            continue
        M[rk], M[p] = M[p], M[rk]
        for r in range(rk + 1, len(M)):
            if M[r][c] != 0:
                f = M[r][c] / M[rk][c]
                M[r] = [a - f * b for a, b in zip(M[r], M[rk])]
        rk += 1
        if rk == len(M):
            break
    return rk


def inertia(A):
    """signature (positive, negative, zero) of a rational symmetric matrix by exact congruence"""
    n = len(A)
    M = [[Fr(v) for v in r] for r in A]
    pos = neg = zero = 0
    for k in range(n):
        if M[k][k] == 0:
            j = next((j for j in range(k + 1, n) if M[j][j] != 0), None)
            if j is not None:
                M[k], M[j] = M[j], M[k]
                for r in M:
                    r[k], r[j] = r[j], r[k]
            else:
                j = next((j for j in range(k + 1, n) if M[k][j] != 0), None)
                if j is None:
                    zero += 1
                    continue
                for c in range(n):
                    M[k][c] += M[j][c]
                for r in range(n):
                    M[r][k] += M[r][j]
        d = M[k][k]
        pos, neg = pos + (d > 0), neg + (d < 0)
        for i in range(k + 1, n):
            f = M[i][k] / d
            if f:
                for c in range(n):
                    M[i][c] -= f * M[k][c]
                for r in range(n):
                    M[r][i] -= f * M[r][k]
    return pos, neg, zero


def jacobi_eig(A, sweeps=60):
    """eigenvalues (ascending) and orthonormal eigenvectors (rows) of a real symmetric matrix"""
    n = len(A)
    a = [list(r) for r in A]
    v = eye(n)
    for _ in range(sweeps):
        off = sum(a[i][j] ** 2 for i in range(n) for j in range(i + 1, n))
        if off < 1e-22:
            break
        for p in range(n - 1):
            for q in range(p + 1, n):
                if abs(a[p][q]) < 1e-300:
                    continue
                th = (a[q][q] - a[p][p]) / (2 * a[p][q])
                t = (1 if th >= 0 else -1) / (abs(th) + math.sqrt(th * th + 1))
                c = 1 / math.sqrt(t * t + 1)
                s = t * c
                for k in range(n):
                    akp, akq = a[k][p], a[k][q]
                    a[k][p], a[k][q] = c * akp - s * akq, s * akp + c * akq
                for k in range(n):
                    apk, aqk = a[p][k], a[q][k]
                    a[p][k], a[q][k] = c * apk - s * aqk, s * apk + c * aqk
                for k in range(n):
                    vkp, vkq = v[k][p], v[k][q]
                    v[k][p], v[k][q] = c * vkp - s * vkq, s * vkp + c * vkq
    order = sorted(range(n), key=lambda i: a[i][i])
    return [a[i][i] for i in order], [[v[k][i] for k in range(n)] for i in order]


def tri_eigs(d, e, k):
    """the k smallest eigenvalues of the symmetric tridiagonal matrix (diagonal d, off-diagonal e) by Sturm bisection"""
    n = len(d)
    lo = min(d[i] - (abs(e[i - 1]) if i else 0) - (abs(e[i]) if i < n - 1 else 0) for i in range(n))
    hi = max(d[i] + (abs(e[i - 1]) if i else 0) + (abs(e[i]) if i < n - 1 else 0) for i in range(n))

    def count(x):
        c, q = 0, 1.0
        for i in range(n):
            q = d[i] - x - ((e[i - 1] ** 2) / q if i else 0.0)
            if q == 0:
                q = 1e-300
            if q < 0:
                c += 1
        return c
    out = []
    for j in range(k):
        a, b = lo, hi
        for _ in range(200):
            m = 0.5 * (a + b)
            if count(m) > j:
                b = m
            else:
                a = m
            if b - a < 1e-13 * (1 + abs(a)):
                break
        out.append(0.5 * (a + b))
    return out


def kron_sum(A, B):
    n, m = len(A), len(B)
    K = [[0.0] * (n * m) for _ in range(n * m)]
    for i in range(n):
        for j in range(n):
            for k in range(m):
                K[i * m + k][j * m + k] += A[i][j]
    for i in range(n):
        for k in range(m):
            for l in range(m):
                K[i * m + k][i * m + l] += B[k][l]
    return K


def lap1(n, bc='D'):
    """n x n matrix of -d^2/dx^2 with unit spacing: Dirichlet, Neumann (reflecting) or periodic"""
    L = [[0.0] * n for _ in range(n)]
    for i in range(n):
        L[i][i] = 2.0
        if i:
            L[i][i - 1] = -1.0
        if i < n - 1:
            L[i][i + 1] = -1.0
    if bc == 'N':
        L[0][0] = L[n - 1][n - 1] = 1.0
    if bc == 'P':
        L[0][n - 1] += -1.0
        L[n - 1][0] += -1.0
    return L


# ---------- calculus ----------
def simpson(f, a, b, n=2000):
    n += n % 2
    h = (b - a) / n
    s = f(a) + f(b)
    for i in range(1, n):
        s += (4 if i % 2 else 2) * f(a + i * h)
    return s * h / 3


def rk4(F, y, h):
    k1 = F(y)
    k2 = F([a + 0.5 * h * b for a, b in zip(y, k1)])
    k3 = F([a + 0.5 * h * b for a, b in zip(y, k2)])
    k4 = F([a + h * b for a, b in zip(y, k3)])
    return [a + h * (p + 2 * q + 2 * r + s) / 6 for a, p, q, r, s in zip(y, k1, k2, k3, k4)]


def d1(f, x, h=1e-4):
    return (f(x - 2 * h) - 8 * f(x - h) + 8 * f(x + h) - f(x + 2 * h)) / (12 * h)


def d2(f, x, h=1e-3):
    return (-f(x - 2 * h) + 16 * f(x - h) - 30 * f(x) + 16 * f(x + h) - f(x + 2 * h)) / (12 * h * h)


def d3(f, x, h=2e-3):
    return (f(x - 3 * h) - 8 * f(x - 2 * h) + 13 * f(x - h) - 13 * f(x + h) + 8 * f(x + 2 * h) - f(x + 3 * h)) / (8 * h ** 3)


def bisect(f, a, b, it=200):
    fa = f(a)
    for _ in range(it):
        m = 0.5 * (a + b)
        fm = f(m)
        if (fa < 0) == (fm < 0):
            a, fa = m, fm
        else:
            b = m
    return 0.5 * (a + b)


# ---------- polynomials in several variables: dict {exponent tuple: coefficient} ----------
def padd(p, q, c=1):
    r = dict(p)
    for k, v in q.items():
        r[k] = r.get(k, 0) + c * v
        if r[k] == 0:
            del r[k]
    return r


def pmul(p, q):
    r = {}
    for k1, v1 in p.items():
        for k2, v2 in q.items():
            k = tuple(a + b for a, b in zip(k1, k2))
            r[k] = r.get(k, 0) + v1 * v2
    return {k: v for k, v in r.items() if v != 0}


def pdiff(p, i):
    r = {}
    for k, v in p.items():
        if k[i]:
            kk = k[:i] + (k[i] - 1,) + k[i + 1:]
            r[kk] = r.get(kk, 0) + v * k[i]
    return {k: v for k, v in r.items() if v != 0}


def pvar(i, n):
    return {tuple(1 if j == i else 0 for j in range(n)): Fr(1)}


def pscale(p, c):
    return {k: v * c for k, v in p.items() if v * c != 0}


def peval(p, x):
    return sum(v * math.prod(xi ** e for xi, e in zip(x, k)) for k, v in p.items())


def plap(p, sig=None):
    n = len(next(iter(p))) if p else 0
    sig = sig or [1] * n
    r = {}
    for i in range(n):
        r = padd(r, pdiff(pdiff(p, i), i), sig[i])
    return r


def monomials(n, k):
    return [e for e in itertools.product(range(k + 1), repeat=n) if sum(e) == k]


def kernel_dim(op, n, k):
    """dimension of the kernel of a linear operator on homogeneous polynomials of degree k in n variables"""
    src = monomials(n, k)
    imgs = [op({m: Fr(1)}) for m in src]
    tgt = sorted({key for im in imgs for key in im})
    if not tgt:
        return len(src)
    return len(src) - rank_exact([[im.get(t, 0) for t in tgt] for im in imgs])


# ---------- special functions ----------
def besselj(n, x, m=400):
    return sum(math.cos(n * (PI * (j + 0.5) / m) - x * math.sin(PI * (j + 0.5) / m)) for j in range(m)) / m


def legendre(l):
    """coefficients (Fractions, ascending powers) of the Legendre polynomial P_l"""
    p0, p1 = [Fr(1)], [Fr(0), Fr(1)]
    if l == 0:
        return p0
    for k in range(1, l):
        nxt = [Fr(0)] * (k + 2)
        for i, c in enumerate(p1):
            nxt[i + 1] += Fr(2 * k + 1, k + 1) * c
        for i, c in enumerate(p0):
            nxt[i] -= Fr(k, k + 1) * c
        p0, p1 = p1, nxt
    return p1


def heat(x, t, k=1.0):
    return math.exp(-x * x / (4 * k * t)) / math.sqrt(4 * PI * k * t)


def charpoly_int(A):
    n = len(A)
    M = [[int(i == j) for j in range(n)] for i in range(n)]
    cs = [1]
    for k in range(1, n + 1):
        AM = [[sum(A[i][l] * M[l][j] for l in range(n)) for j in range(n)] for i in range(n)]
        c = -sum(AM[i][i] for i in range(n)) // k
        cs.append(c)
        M = [[AM[i][j] + (c if i == j else 0) for j in range(n)] for i in range(n)]
    return tuple(cs)


# ######################## CHECKS FOR THE PAPER ########################
def rk4t(F, y, t, h):
    k1 = F(t, y)
    k2 = F(t + 0.5 * h, [a + 0.5 * h * b for a, b in zip(y, k1)])
    k3 = F(t + 0.5 * h, [a + 0.5 * h * b for a, b in zip(y, k2)])
    k4 = F(t + h, [a + h * b for a, b in zip(y, k3)])
    return [a + h * (p + 2 * q + 2 * r + s) / 6 for a, p, q, r, s in zip(y, k1, k2, k3, k4)]


def flow(F, y, t0, t1, steps):
    h = (t1 - t0) / steps
    t = t0
    for _ in range(steps):
        y = rk4t(F, y, t, h)
        t += h
    return y


def norm(x):
    return math.sqrt(sum(a * a for a in x))


def gauss(x, m, v):
    return math.exp(-(x - m) ** 2 / (2 * v)) / math.sqrt(2 * PI * v)


def Phi(z):
    return 0.5 * (1 + math.erf(z / math.sqrt(2)))


sec('1. Padding is a boundary condition')


def conv_pad(x, w, mode):
    n = len(x)
    r = len(w) // 2

    def get(i):
        if 0 <= i < n:
            return x[i]
        if mode == 'zero':
            return 0.0
        if mode == 'circ':
            return x[i % n]
        i = i % (2 * n)
        return x[i] if i < n else x[2 * n - 1 - i]
    return [sum(w[j + r] * get(i + j) for j in range(-r, r + 1)) for i in range(n)]


n = 12
x = [random.gauss(0, 1) for _ in range(n)]
st = [-1.0, 2.0, -1.0]
e = max(norm(axpy(-1, conv_pad(x, st, m), mv(lap1(n, b), x))) for m, b in (('reflect', 'N'), ('zero', 'D'), ('circ', 'P')))
check('N1 the stencil (-1,2,-1) with reflect, zero and circular padding is the Neumann, Dirichlet and periodic Laplacian',
      e < 1e-12, 'max difference %.1e' % e)

res = 0.0
for k in range(n):
    v = [math.cos(PI * k * (j + 0.5) / n) for j in range(n)]
    res = max(res, norm(axpy(-4 * math.sin(PI * k / (2 * n)) ** 2, v, mv(lap1(n, 'N'), v))))
    v = [math.sin(PI * (k + 1) * (j + 1) / (n + 1)) for j in range(n)]
    res = max(res, norm(axpy(-4 * math.sin(PI * (k + 1) / (2 * (n + 1))) ** 2, v, mv(lap1(n, 'D'), v))))
    v = [math.cos(2 * PI * k * j / n) for j in range(n)]
    res = max(res, norm(axpy(-4 * math.sin(PI * k / n) ** 2, v, mv(lap1(n, 'P'), v))))
check('N2 the three paddings are diagonalized by the DCT-II, DST-I and DFT bases with eigenvalues 4 sin^2',
      res < 1e-12, 'max residual %.1e over 36 vectors' % res)


def even_ext(x):
    return list(x) + list(reversed(x))


def evenness(z):
    return norm([a - b for a, b in zip(z, reversed(z))]) / norm(z)


ws = [0.2, -0.5, 1.0, -0.5, 0.2]
wa = [0.2, -0.5, 1.0, 0.7, -0.3]
d_restr = max(norm(axpy(-1, conv_pad(even_ext(x), w, 'circ')[:n], conv_pad(x, w, 'reflect'))) for w in (ws, wa))
ev_s = evenness(conv_pad(even_ext(x), ws, 'circ'))
ev_a = evenness(conv_pad(even_ext(x), wa, 'circ'))


def two_layer_defect(w1, w2):
    a = conv_pad(conv_pad(x, w1, 'reflect'), w2, 'reflect')
    b = conv_pad(conv_pad(even_ext(x), w1, 'circ'), w2, 'circ')[:n]
    return norm(axpy(-1, a, b)) / norm(b)


c_s, c_a = two_layer_defect(ws, wa), two_layer_defect(wa, ws)
check('N3 half-sample reflect padding agrees with circular convolution on the doubled signal followed by restriction to the original positions',
      d_restr < 1e-12 and ev_s < 1e-12 and ev_a > 0.1 and c_s < 1e-12 and c_a > 0.01,
      'restriction %.0e; output odd part: symmetric kernel %.0e, asymmetric %.3f; two-layer defect %.0e vs %.3f' % (d_restr, ev_s, ev_a, c_s, c_a))


def odd_ext(x):
    return [0.0] + list(x) + [0.0] + [-a for a in reversed(x)]


def zero_vs_odd(w):
    a = conv_pad(x, w, 'zero')
    b = conv_pad(odd_ext(x), w, 'circ')[1:n + 1]
    return norm(axpy(-1, a, b)) / norm(a)


z1, z2 = zero_vs_odd([0.3, 1.0, 0.3]), zero_vs_odd(ws)
check('N4 a three-point symmetric stencil agrees with the Dirichlet image construction, while the tested five-point stencil differs',
      z1 < 1e-12 and z2 > 0.01, 'relative difference: radius 1 %.0e, radius 2 %.3f' % (z1, z2))


def shift(x):
    return [0.0] + list(x[:-1])


def shift_c(x):
    return [x[-1]] + list(x[:-1])


n = 20
x = [random.gauss(0, 1) for _ in range(n)]
r = 2
com = axpy(-1, conv_pad(shift(x), wa, 'zero'), shift(conv_pad(x, wa, 'zero')))
supp = [i for i in range(n) if abs(com[i]) > 1e-12]
comc = norm(axpy(-1, conv_pad(shift_c(x), wa, 'circ'), shift_c(conv_pad(x, wa, 'circ'))))
check('N5 circular convolution commutes with translation; zero padding fails only within the kernel radius of the boundary',
      comc < 1e-12 and len(supp) > 0 and all(i == 0 or i >= n - r for i in supp), 'commutator supported on positions %s of 0..%d' % (supp, n - 1))

n = 32
one = [1.0] * n
MD = [[(1.0 if i == j else 0.0) - 0.25 * lap1(n, 'D')[i][j] for j in range(n)] for i in range(n)]
MN = [[(1.0 if i == j else 0.0) - 0.25 * lap1(n, 'N')[i][j] for j in range(n)] for i in range(n)]
yD, yN = one, [random.random() for _ in range(n)]
m0 = sum(yN)
mx0 = max(yN)
okmax = True
for _ in range(200):
    yD, yN2 = mv(MD, yD), mv(MN, yN)
    okmax = okmax and max(yN2) <= max(yN) + 1e-15 and min(yN2) >= min(yN) - 1e-15
    yN = yN2
surv = sum(yD) / n
pred = 0.0
for k in range(1, n + 1):
    ip = sum(math.sin(PI * k * j / (n + 1)) for j in range(1, n + 1))
    pred += (1 - math.sin(PI * k / (2 * (n + 1))) ** 2) ** 200 * ip * ip * 2 / (n + 1) / n
check('N6 a smoothing layer with reflect padding conserves mass and obeys the maximum principle; zero padding leaks mass',
      abs(sum(yN) - m0) < 1e-10 and okmax and close(surv, pred, 1e-10) and 0.3 < surv < 0.9,
      'after 200 layers of (1/4,1/2,1/4) on 32 points: reflect mass change %.0e; zero-padded mass left %.4f (spectral formula %.4f)' % (abs(sum(yN) - m0), surv, pred))

sec('2. Discretization: what commutes with resampling')


def dft(x):
    N = len(x)
    return [sum(x[j] * cmath.exp(-2j * PI * k * j / N) for j in range(N)) / N for k in range(N)]


def coef(x, k):
    N = len(x)
    return sum(x[j] * cmath.exp(-2j * PI * k * j / N) for j in range(N)) / N


K = 5
a = [random.gauss(0, 1) for _ in range(K + 1)]
b = [random.gauss(0, 1) for _ in range(K + 1)]


def u(x):
    return sum(a[k] * math.cos(k * x) + b[k] * math.sin(k * x) for k in range(1, K + 1))


def mult_exact(x):
    return sum((a[k] * math.cos(k * x) + b[k] * math.sin(k * x)) / (1 + k * k) for k in range(1, K + 1))


def lap_exact(x):
    return sum((a[k] * math.cos(k * x) + b[k] * math.sin(k * x)) * k * k for k in range(1, K + 1))


def apply_mult(N):
    xs = [2 * PI * j / N for j in range(N)]
    c = dft([u(t) for t in xs])
    out = []
    for j in range(N):
        s = 0
        for k in range(N):
            f = k if k <= N // 2 else k - N
            s += c[k] / (1 + f * f) * cmath.exp(2j * PI * k * j / N)
        out.append(s.real)
    return max(abs(out[j] - mult_exact(xs[j])) for j in range(N))


def apply_stencil(N):
    h = 2 * PI / N
    xs = [j * h for j in range(N)]
    us = [u(t) for t in xs]
    out = [(2 * us[j] - us[j - 1] - us[(j + 1) % N]) / (h * h) for j in range(N)]
    ex = [lap_exact(t) for t in xs]
    return norm(axpy(-1, out, ex)) / norm(ex)


em = max(apply_mult(16), apply_mult(64))
es16, es64 = apply_stencil(16), apply_stencil(64)
sy16 = (math.sin(5 * PI / 16) / (5 * PI / 16)) ** 2
sy64 = (math.sin(5 * PI / 64) / (5 * PI / 64)) ** 2
check('A1 a Fourier multiplier commutes with resampling of band-limited inputs; a stencil does so only to second order',
      em < 1e-12 and es16 > 5 * es64 > 0 and close(sy16, 0.7175, 1e-3) and close(sy64, 0.9801, 1e-3),
      'multiplier error %.0e on 16 and 64 points; stencil relative error %.3f and %.4f; its symbol at k=5 is %.4f and %.4f of k^2' % (em, es16, es64, sy16, sy64))

K = 4
c = {}
for k in range(1, K + 1):
    c[k] = complex(random.gauss(0, 1), random.gauss(0, 1))
    c[-k] = c[k].conjugate()
c[0] = complex(0.3, 0)


def ub(x):
    return sum(c[k] * cmath.exp(1j * k * x) for k in c).real


exact = {k: sum(c[p] * c[k - p] for p in c if (k - p) in c) for k in range(-K, K + 1)}


def alias_err(N):
    xs = [2 * PI * j / N for j in range(N)]
    sq = [ub(t) ** 2 for t in xs]
    return max(abs(coef(sq, k) - exact[k]) for k in range(-K, K + 1))


e13, e12, e9 = alias_err(3 * K + 1), alias_err(3 * K), alias_err(2 * K + 1)
check('A2 squaring a signal of band K is alias-free in the band exactly when the grid has more than 3K points',
      e13 < 1e-12 and e12 > 1e-3 and e9 > 1e-3, 'K=4: error on 13 points %.0e, on 12 points %.3f, on 9 points %.3f' % (e13, e12, e9))


def relu_mean(N):
    return sum(max(math.sin(2 * PI * j / N), 0.0) for j in range(N)) / N


errs = {N: relu_mean(N) - 1 / PI for N in (8, 16, 32, 64)}
okf = all(close(relu_mean(N), 1 / (N * math.tan(PI / N)), 1e-13) for N in errs)
check('A3 a rectifier has unbounded band: the sampled mean of relu(sin) is cot(pi/N)/N, in error by -pi/(3 N^2)',
      okf and all(close(errs[N] * N * N, -PI / 3, 0.02) for N in errs) and close(errs[8] / errs[16], 4, 0.01),
      'error times N^2 = %s (limit %.4f)' % (', '.join('%.4f' % (errs[N] * N * N) for N in sorted(errs)), -PI / 3))


def relu_band(N):
    xs = [2 * PI * j / N for j in range(N)]
    v = [max(ub(t), 0.0) for t in xs]
    return [coef(v, k) for k in range(-K, K + 1)]


ref = relu_band(8192)
ea = {N: max(abs(p - q) for p, q in zip(relu_band(N), ref)) for N in (16, 32, 64, 128, 256)}
check('A4 the in-band aliasing error of a rectifier layer falls with oversampling at second order',
      all(ea[N] > ea[2 * N] for N in (16, 32, 64, 128)) and ea[256] < ea[16] / 100,
      'max coefficient error on 16..256 points: ' + ', '.join('%.1e' % ea[N] for N in sorted(ea)))

sec('3. Diffusion models and the heat equation')
W, MU, SD = [0.3, 0.7], [-1.5, 1.0], [0.4, 0.6]


def p_h(x, t):
    return sum(w * gauss(x, m, s * s + t) for w, m, s in zip(W, MU, SD))


def sc_h(x, t):
    return sum(w * gauss(x, m, s * s + t) * (-(x - m) / (s * s + t)) for w, m, s in zip(W, MU, SD)) / p_h(x, t)


def cdf_h(x, t):
    return sum(w * Phi((x - m) / math.sqrt(s * s + t)) for w, m, s in zip(W, MU, SD))


pts = [-2.0, -1.0, 0.0, 1.0, 2.0]
r1 = max(abs(d1(lambda t: p_h(x, t), 0.3) - 0.5 * d2(lambda y: p_h(y, 0.3), x)) for x in pts)
check('S1 the noised mixture density solves the heat equation p_t = p_xx / 2', r1 < 1e-6, 'max residual %.1e' % r1)

t = 0.5
r2 = 0.0
for x in pts:
    post = simpson(lambda y: y * p_h(y, 0) * gauss(x, y, t), -7, 7, 6000) / p_h(x, t)
    r2 = max(r2, abs(post - (x + t * sc_h(x, t))))
check('S2 Tweedie: the posterior mean of the clean sample is x + t * score', r2 < 1e-8, 'max difference %.1e' % r2)


def pf(eps=0.0):
    return lambda t, y: [-0.5 * (sc_h(y[0], t) + eps * math.sin(3 * y[0]))]


T = 1.0
x0s = [flow(pf(), [x], T, 0.0, 2000)[0] for x in pts]
r3 = max(abs(cdf_h(a, 0) - cdf_h(b, T)) for a, b in zip(x0s, pts))
check('S3 the probability-flow ODE dx/dt = -score/2 transports the noised law back to the data law',
      r3 < 1e-8, 'max change of the distribution function along five trajectories %.1e' % r3)

eps = 1e-3
x0p = [flow(pf(eps), [x], T, 0.0, 2000)[0] for x in pts]
sens = max(abs(a - b) for a, b in zip(x0s, x0p)) / eps
jac = max(p_h(b, T) / p_h(a, 0) for a, b in zip(x0s, pts))
amp = math.exp(10 ** 2 * T / 2)
check('S4 the backward heat equation amplifies mode 10 by e^50; the reverse flow with the score is Lipschitz in the score error',
      amp > 5e21 and sens < 5 and jac < 50,
      'backward amplification %.2e; sample displacement per unit score error %.3f; largest Jacobian of the reverse map %.2f' % (amp, sens, jac))


def sc2(x, t, a=1.0):
    return -x / t + (a / t) * math.tanh(a * x / t)


g1, g2 = d1(lambda y: sc2(y, 0.1), 0.0, 1e-5), d1(lambda y: sc2(y, 0.01), 0.0, 1e-6)
check('S5 for two-point data the slope of the score at the midpoint is -1/t + 1/t^2: the difficulty moves into small t',
      close(g1, 90, 1e-5) and close(g2, 9900, 1e-5), 'slope %.2f at t=0.1 and %.1f at t=0.01' % (g1, g2))


def ent(t):
    return simpson(lambda y: -p_h(y, t) * math.log(p_h(y, t)), -9, 9, 6000)


dh = (ent(0.301) - ent(0.299)) / 0.002
J = simpson(lambda y: p_h(y, 0.3) * sc_h(y, 0.3) ** 2, -9, 9, 6000)
check('S6 de Bruijn: under the heat flow the entropy grows at half the Fisher information', close(dh, J / 2, 1e-6),
      'dh/dt = %.6f, J/2 = %.6f' % (dh, J / 2))


def p_ou(x, t):
    e = math.exp(-t)
    return sum(w * gauss(x, m * e, s * s * e * e + 1 - e * e) for w, m, s in zip(W, MU, SD))


def kl_ou(t):
    return simpson(lambda y: p_ou(y, t) * math.log(p_ou(y, t) / gauss(y, 0, 1)), -9, 9, 6000)


k0 = kl_ou(0)
rat = {t: kl_ou(t) / (math.exp(-2 * t) * k0) for t in (0.25, 0.5, 1.0, 2.0)}
lim = kl_ou(4.0) * math.exp(8.0)
mean0 = sum(w * m for w, m in zip(W, MU))
check('S7 Ornstein-Uhlenbeck noising contracts relative entropy to the Gaussian at least at rate 2, and exactly so in the limit',
      all(v <= 1 + 1e-12 for v in rat.values()) and close(lim, mean0 ** 2 / 2, 0.02),
      'KL_0 = %.4f; KL_t / (e^{-2t} KL_0) = %s; e^{2t} KL_t at t=4 is %.5f (mean^2/2 = %.5f)' % (k0, ', '.join('%.3f' % rat[t] for t in sorted(rat)), lim, mean0 ** 2 / 2))

t = 0.5


def p2(x):
    return 0.5 * (gauss(x, 1, t) + gauss(x, -1, t))


def s_true(x):
    return sc2(x, t)


def dsm(s):
    f = lambda z: gauss(z, 0, 1) * 0.5 * sum((s(x0 + math.sqrt(t) * z) + z / math.sqrt(t)) ** 2 for x0 in (-1.0, 1.0))
    return simpson(f, -9, 9, 6000)


def esm(s):
    return simpson(lambda y: p2(y) * (s(y) - s_true(y)) ** 2, -10, 10, 6000)


J2 = simpson(lambda y: p2(y) * s_true(y) ** 2, -10, 10, 6000)
gaps = [dsm(s) - esm(s) for s in (lambda y: -math.tanh(y), lambda y: -y / 2 + math.sin(y))]
check('S8 denoising score matching differs from explicit score matching by the constant 1/t - J, so they have the same minimizer',
      close(gaps[0], gaps[1], 1e-8) and close(gaps[0], 1 / t - J2, 1e-8), 'gap %.6f for two test functions; 1/t - J = %.6f' % (gaps[0], 1 / t - J2))

sec('4. Characteristics: continuous normalizing flows and flow matching')
A_, B_, C_ = 1.3, 0.2, 0.8


def vf(t, y):
    th = math.tanh(A_ * y[0] + B_)
    return [C_ * th, C_ * A_ * (1 - th * th)]


r = 0.0
for x in (-1.5, -0.4, 0.3, 1.2):
    y, ld = flow(vf, [x, 0.0], 0.0, 1.0, 1000)
    yp = flow(vf, [x + 1e-4, 0.0], 0.0, 1.0, 1000)[0]
    ym = flow(vf, [x - 1e-4, 0.0], 0.0, 1.0, 1000)[0]
    r = max(r, abs(math.exp(ld) - (yp - ym) / 2e-4))
check('F1 along a characteristic the log-density changes at rate -div v (instantaneous change of variables)', r < 1e-6,
      'max difference between exp(int div v) and the derivative of the flow map %.1e' % r)

m_, s_ = 2.0, 0.5


def vfm(t, y):
    return [m_ + (t * s_ * s_ - (1 - t)) / ((1 - t) ** 2 + t * t * s_ * s_) * (y[0] - t * m_)]


r = max(abs(flow(vfm, [x], 0.0, 1.0, 2000)[0] - (m_ + s_ * x)) for x in (-2.0, -1.0, 0.0, 0.7, 2.0))
check('F2 flow matching between Gaussians with independent coupling integrates to the monotone transport map x -> m + s x',
      r < 1e-7, 'max error %.1e' % r)


def p_fm(x, t):
    return 0.5 * (gauss(x, t, (1 - t) ** 2) + gauss(x, -t, (1 - t) ** 2))


def v_fm(x, t):
    return (math.tanh(t * x / (1 - t) ** 2) - x) / (1 - t)


r = max(abs(d1(lambda t: p_fm(x, t), 0.5) + d1(lambda y: p_fm(y, 0.5) * v_fm(y, 0.5), x)) for x in (-1.0, -0.3, 0.2, 0.9))
sl = d1(lambda y: v_fm(y, 0.9), 0.0, 1e-6)
tstar = bisect(lambda t: d1(lambda y: v_fm(y, t), 0.0, 1e-5), 0.2, 0.6)
check('F3 the marginal velocity for two-point data satisfies the continuity equation; the midpoint turns from attracting to repelling at t = (3 - sqrt 5)/2',
      r < 1e-6 and close(sl, 890, 1e-5) and close(tstar, (3 - math.sqrt(5)) / 2, 1e-7),
      'continuity residual %.1e; slope at the midpoint changes sign at t = %.6f and is %.1f at t = 0.9' % (r, tstar, sl))

sec('5. Graph networks: diffusion, waves and sheaves')


def graph_lap(n, edges, signs=None):
    L = [[0.0] * n for _ in range(n)]
    for idx, (u_, v_) in enumerate(edges):
        s = 1.0 if signs is None else signs[idx]
        L[u_][u_] += 1
        L[v_][v_] += 1
        L[u_][v_] -= s
        L[v_][u_] -= s
    return L


def rand_graph(n, extra):
    edges = [(random.randrange(i), i) for i in range(1, n)]
    while len(edges) < n - 1 + extra:
        a_, b_ = sorted(random.sample(range(n), 2))
        if (a_, b_) not in edges:
            edges.append((a_, b_))
    return edges


def center(x):
    m = sum(x) / len(x)
    return [a - m for a in x]


n = 12
E1 = rand_graph(n, 8)
L = graph_lap(n, E1)
lam, _ = jacobi_eig(L)
tau = 1 / lam[-1]
rho = 1 - tau * lam[1]
X = [random.gauss(0, 1) for _ in range(n)]
e0 = dot(X, mv(L, X))
layers99 = None
prev = None
for k in range(1, 201):
    X = axpy(-tau, mv(L, X), X)
    if layers99 is None and dot(X, mv(L, X)) < 0.01 * e0:
        layers99 = k
    if k == 199:
        prev = norm(center(X))
ratio = norm(center(X)) / prev
pred99 = math.log(0.01) / (2 * math.log(rho))
check('G1 linear message passing contracts the non-constant part by 1 - tau*lambda_2 per layer (oversmoothing rate)',
      close(ratio, rho, 1e-4) and layers99 <= math.ceil(pred99),
      'lambda_2 = %.4f, lambda_max = %.4f; measured factor %.5f, predicted %.5f; 99%% of Dirichlet energy lost after %d layers (bound %.1f)' % (lam[1], lam[-1], ratio, rho, layers99, pred99))

n = 32
lp = 4 * math.sin(PI / 64) ** 2
Q5 = [(i, i ^ (1 << b)) for i in range(32) for b in range(5) if i < i ^ (1 << b)]
lq, _ = jacobi_eig(graph_lap(32, Q5))
K32 = [(i, j) for i in range(32) for j in range(i + 1, 32)]
x = [random.gauss(0, 1) for _ in range(32)]
y = axpy(-1 / 32, mv(graph_lap(32, K32), x), x)
lpath, _ = jacobi_eig(lap1(32, 'N'))
check('G2 the depth scale 1/(tau*lambda_2) of oversmoothing on 32 nodes: path 415 layers, hypercube 5, complete graph 1',
      close(lpath[1], lp, 1e-9) and close(1 / (0.25 * lp), 415.4, 1e-3) and close(lq[1], 2, 1e-9) and close(lq[-1], 10, 1e-9) and norm(center(y)) < 1e-12,
      'path lambda_2 = %.6f; hypercube lambda_2 = %.3f, lambda_max = %.3f; one layer on the complete graph leaves non-constant part %.0e' % (lpath[1], lq[1], lq[-1], norm(center(y))))

n = 12


def wave_run(L, tau2, steps, x0):
    xm, xc = list(x0), list(x0)
    inv_ = []
    dirs = []
    norms = []
    for _ in range(steps):
        xn = [2 * a - b - tau2 * c for a, b, c in zip(xc, xm, mv(L, xc))]
        d = axpy(-1, xc, xn)
        inv_.append(dot(d, d) / tau2 + dot(xn, mv(L, xc)))
        dirs.append(dot(xn, mv(L, xn)))
        norms.append(norm(xn))
        xm, xc = xc, xn
    return inv_, dirs, norms


x0 = center([random.gauss(0, 1) for _ in range(n)])
inv_, dirs, _ = wave_run(L, 3.6 / lam[-1], 500, x0)
drift = (max(inv_) - min(inv_)) / abs(inv_[0])
keep = (sum(dirs[400:]) / 100) / (sum(dirs[:100]) / 100)
_, _, norms = wave_run(L, 4.4 / lam[-1], 200, x0)
gr = norms[-1] / norms[-2]
check('G3 a second-order (wave) layer conserves a discrete energy and does not smooth; past the CFL bound it grows by 1.8633 per layer',
      drift < 1e-9 and 0.5 < keep < 2 and close(gr, (2.4 + math.sqrt(2.4 ** 2 - 4)) / 2, 1e-6),
      'invariant drift %.1e over 500 layers; late/early mean Dirichlet energy %.3f; growth factor %.4f at tau^2*lambda_max = 4.4' % (drift, keep, gr))

n = 10
E2 = rand_graph(n, 6)
lab = [random.choice([-1.0, 1.0]) for _ in range(n)]
lab[0], lab[1] = 1.0, -1.0
sg = [lab[u_] * lab[v_] for u_, v_ in E2]
LF = graph_lap(n, E2, sg)
L0 = graph_lap(n, E2)
lf, _ = jacobi_eig(LF)
l0, _ = jacobi_eig(L0)
X0 = [random.gauss(0, 1) for _ in range(n)]
Xs, Xo = list(X0), list(X0)
for _ in range(3000):
    Xs = axpy(-1 / lf[-1], mv(LF, Xs), Xs)
    Xo = axpy(-1 / l0[-1], mv(L0, Xo), Xo)
proj = dot(lab, X0) / n
sep = max(abs(Xs[i] - proj * lab[i]) for i in range(n))
flat = norm(center(Xo))
sgf = list(sg)
sgf[-1] = -sgf[-1]
lff, _ = jacobi_eig(graph_lap(n, E2, sgf))
C7 = [(i, (i + 1) % 7) for i in range(7)]
lc, _ = jacobi_eig(graph_lap(7, C7, [1.0] * 6 + [-1.0]))
check('G4 sheaf diffusion converges to the global sections: a balanced sign sheaf separates the two classes, a frustrated one has none',
      lf[0] < 1e-10 and lf[1] > 1e-3 and sep < 1e-8 and flat < 1e-8 and lff[0] > 1e-3 and close(lc[0], 4 * math.sin(PI / 14) ** 2, 1e-9),
      'balanced: kernel dimension 1, limit = labelling times %.4f (error %.0e), ordinary diffusion limit constant (%.0e); one flipped edge: smallest eigenvalue %.4f; frustrated 7-cycle %.5f' % (proj, sep, flat, lff[0], lc[0]))

E3 = [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (2, 4), (3, 4)]
nb = 0
okb = True
for bits in itertools.product([1, -1], repeat=7):
    labl = {0: 1}
    cons = True
    for _ in range(5):
        for (u_, v_), s in zip(E3, bits):
            if u_ in labl and v_ not in labl:
                labl[v_] = labl[u_] * s
            elif v_ in labl and u_ not in labl:
                labl[u_] = labl[v_] * s
    cons = all(labl[u_] * labl[v_] == s for (u_, v_), s in zip(E3, bits))
    Lr = [[Fr(0)] * 5 for _ in range(5)]
    for (u_, v_), s in zip(E3, bits):
        Lr[u_][u_] += 1
        Lr[v_][v_] += 1
        Lr[u_][v_] -= s
        Lr[v_][u_] -= s
    sing = rank_exact(Lr) < 5
    okb = okb and (sing == cons)
    nb += cons
check('G5 on a graph with 5 nodes and 7 edges, 16 = 2^(V-1) of the 128 sign sheaves have a global section: the others are the non-zero classes of H^1(G; Z/2)',
      nb == 16 and okb, '%d balanced; singular Laplacian exactly for these; 128/16 = 8 = 2^(E-V+1) classes' % nb)

sec('6. Residual networks as difference schemes')
n = 6
B = [[random.gauss(0, 1) for _ in range(n)] for _ in range(n)]
A = [[sum(B[k][i] * B[k][j] for k in range(n)) + (0.1 if i == j else 0) for j in range(n)] for i in range(n)]
la, _ = jacobi_eig(A)


def euler_growth(h, steps=400):
    x = [random.gauss(0, 1) for _ in range(n)]
    p = None
    for k in range(steps):
        if k == steps - 1:
            p = norm(x)
        x = axpy(-h, mv(A, x), x)
        s = norm(x)
        if s > 1e100 or s < 1e-100:
            x = [a / s for a in x]
            if k == steps - 1:
                p = p / s
    return norm(x) / p


g_lo, g_hi = euler_growth(1.9 / la[-1]), euler_growth(2.1 / la[-1])
check('R1 a residual layer x - h*A*x with A positive definite is stable exactly for h <= 2/lambda_max',
      g_lo < 1 and close(g_hi, 1.1, 1e-6), 'per-layer factor %.4f at h = 1.9/lambda_max and %.4f at 2.1/lambda_max' % (g_lo, g_hi))


def euler_rot(h, N):
    q, p = 1.0, 0.0
    for _ in range(N):
        q, p = q - h * p, p + h * q
    return math.hypot(q, p)


e1, e2 = euler_rot(0.1, 100), euler_rot(0.01, 1000)
check('R2 forward Euler on an antisymmetric layer is unstable for every step: the norm grows by (1+h^2)^(N/2)',
      close(e1, 1.01 ** 50, 1e-12) and close(e2, 1.0001 ** 500, 1e-12) and e1 > e2 > 1,
      'growth over time 10: %.4f at h = 0.1, %.4f at h = 0.01 (e^{hT/2} = %.4f)' % (e1, e2, math.exp(0.05)))


def leap_mod(hw, N=400):
    q, p = 1.0, 0.3
    I0 = p * p + q * q + hw * p * q
    drift = 0.0
    pn = None
    for k in range(N):
        if k == N - 1:
            pn = math.hypot(q, p)
        q = q + hw * p
        p = p - hw * q
        drift = max(drift, abs(p * p + q * q + hw * p * q - I0))
        s = math.hypot(q, p)
        if s > 1e100:
            q, p, pn = q / s, p / s, (pn / s if k == N - 1 else pn)
    return drift, math.hypot(q, p) / pn


d19, _ = leap_mod(1.9)
_, g21 = leap_mod(2.1)
q_edge, p_edge = 1, 0
for step in range(1, 41):
    q_edge += 2 * p_edge
    p_edge -= 2 * q_edge
check('R3 leapfrog has a positive invariant below h*omega = 2, linear growth at 2, and a growing eigenmode above 2',
      d19 < 1e-10 and (q_edge, p_edge) == (-79, 80)
      and close(g21, (2.41 + math.sqrt(2.41 ** 2 - 4)) / 2, 1e-6),
      'invariant drift %.1e at h*omega = 1.9; (q,p) at 2 after 40 steps (%d,%d); growth %.4f per layer at 2.1' % (d19, q_edge, p_edge, g21))


def cond2(M):
    a_, b_, c_, d_ = M[0][0], M[0][1], M[1][0], M[1][1]
    s = a_ * a_ + b_ * b_ + c_ * c_ + d_ * d_
    det = abs(a_ * d_ - b_ * c_)
    smax = math.sqrt((s + math.sqrt(max(s * s - 4 * det * det, 0))) / 2)
    return smax * smax / det


h = 0.5
M1 = [[1.0, h], [-h, 1 - h * h]]
conds = {}
P = [[1.0, 0.0], [0.0, 1.0]]
for k in range(1, 801):
    P = mm(M1, P)
    if k in (50, 200, 800):
        conds[k] = cond2(P)
par = (0.95 / 0.5) ** 50
check('R4 backpropagation through N symplectic layers has condition number at most (1+h/2)/(1-h/2); through a parabolic stack it grows geometrically',
      all(v <= 1.25 / 0.75 + 1e-9 for v in conds.values()) and par > 1e13,
      'leapfrog, h = 0.5: %s for N = 50, 200, 800 (bound %.4f); Euler on eigenvalues 1 and 10, h = 0.05, N = 50: %.2e' % (', '.join('%.4f' % conds[k] for k in sorted(conds)), 1.25 / 0.75, par))

sec('7. Kernels, spectral bias and conditioning')
N = 64
hh = 2 * PI / N


def Gper(x):
    x = (x + PI) % (2 * PI) - PI
    return math.cosh(abs(x) - PI) / (2 * math.sinh(PI))


def mu_disc(k):
    return (PI / N) * math.sinh(2 * PI / N) / (math.cosh(2 * PI / N) - math.cos(2 * PI * k / N))


Kmat = [[hh * Gper((i - j) * hh) for j in range(N)] for i in range(N)]
r = 0.0
for k in (0, 1, 5, 10, 16):
    v = [math.cos(k * i * hh) for i in range(N)]
    r = max(r, norm(axpy(-mu_disc(k), v, mv(Kmat, v))))
check('K1 the sampled H^1 kernel has eigenvalues sum_m 1/(1+(k+mN)^2): the continuum 1/(1+k^2) plus its aliases (Poisson summation)',
      r < 1e-12 and close(mu_disc(1), 0.5, 2e-3) and 1.02 < mu_disc(10) * 101 < 1.10,
      'residual %.0e; discrete/continuum eigenvalue %.4f at k=1, %.4f at k=10, %.4f at k=16' % (r, mu_disc(1) * 2, mu_disc(10) * 101, mu_disc(16) * 257))

yv = [math.cos(i * hh) + math.cos(8 * i * hh) for i in range(N)]
f = [0.0] * N
for _ in range(200):
    f = axpy(-1.0, mv(Kmat, axpy(-1, yv, f)), f)
res = axpy(-1, f, yv)
r1_, r8_ = abs(coef(res, 1)) * 2, abs(coef(res, 8)) * 2
st1 = math.log(0.01) / math.log(1 - mu_disc(1))
st8 = math.log(0.01) / math.log(1 - mu_disc(8))
st16 = math.log(0.01) / math.log(1 - mu_disc(16))
check('K2 kernel gradient descent learns mode k at rate mu_k: after 200 steps mode 1 is fitted and 3.8 per cent of mode 8 remains',
      r1_ < 1e-12 and close(r8_, (1 - mu_disc(8)) ** 200, 1e-9) and 0.03 < r8_ < 0.06,
      'residual amplitudes %.0e (k=1), %.4f (k=8); steps to 1 per cent: %.1f, %.0f, %.0f for k = 1, 8, 16' % (r1_, r8_, st1, st8, st16))

n = 31
AD = [[v * 32 * 32 for v in row] for row in lap1(n, 'D')]
ld, _ = jacobi_eig(AD)
kap = ld[-1] / ld[0]
AA = mm(tr(AD), AD)
l2, _ = jacobi_eig(AA)
kap2 = l2[-1] / l2[0]


def its(k_):
    return math.log(1e-6) / math.log((k_ - 1) / (k_ + 1))


check('K3 the strong-form (collocation) least-squares problem has the square of the condition number of the energy (Ritz) problem',
      close(kap, (math.sin(31 * PI / 64) / math.sin(PI / 64)) ** 2, 1e-8) and close(kap2, kap * kap, 1e-6),
      '31 unknowns: condition %.1f (Ritz) and %.0f (strong form); optimal-step gradient iterations for 1e-6: %.0f and %.0f' % (kap, kap2, its(kap), its(kap2)))

AP = [[v / (hh * hh) for v in row] for row in lap1(N, 'P')]


def rate_pinn(k):
    v = [math.cos(k * i * hh) for i in range(N)]
    w = mv(Kmat, mv(AP, mv(AP, v)))
    return dot(v, w) / dot(v, v)


rp1, rp16 = rate_pinn(1), rate_pinn(16)
check('K4 composing the kernel with the strong-form loss reverses the bias: mode rates k^4/(1+k^2) grow with k',
      close(rp1, mu_disc(1) * (4 / hh ** 2 * math.sin(hh / 2) ** 2) ** 2, 1e-9) and rp16 / rp1 > 100 and mu_disc(1) / mu_disc(16) > 100,
      'regression rates %.4f and %.5f at k = 1, 16 (ratio 1/%.0f); strong-form rates %.4f and %.1f (ratio %.0f)' % (mu_disc(1), mu_disc(16), mu_disc(1) / mu_disc(16), rp1, rp16, rp16 / rp1))

xd = [0.5, 1.7, 3.0, 4.4, 5.6]
ydat = [random.gauss(0, 1) for _ in xd]
cc = solve([[Gper(a_ - b_) for b_ in xd] for a_ in xd], ydat)


def uk(x):
    return sum(c_ * Gper(x - b_) for c_, b_ in zip(cc, xd))


r_int = max(abs(uk(a_) - y_) for a_, y_ in zip(xd, ydat))
r_ode = max(abs(uk(x) - d2(uk, x)) for x in (0.1, 1.1, 2.3, 3.7, 5.0, 6.0))
dl = 1e-5
r_jump = max(abs((uk(a_ + dl) - 2 * uk(a_) + uk(a_ - dl)) / dl + c_) for a_, c_ in zip(xd, cc))
check('K5 the kernel interpolant solves u - u\'\' = sum c_i delta_{x_i}: the representer theorem is a fundamental solution',
      r_int < 1e-12 and r_ode < 1e-6 and r_jump < 1e-3, 'interpolation %.0e; equation residual off the data %.1e; jump of u\' plus c_i %.1e' % (r_int, r_ode, r_jump))

sec('8. Langevin dynamics and stochastic gradient descent')


def fp_gap(V, lo, hi, n, beta, k=2):
    h = (hi - lo) / n
    xs = [lo + i * h for i in range(n + 1)]
    Vs = [V(x) for x in xs]
    D = 1 / beta
    d = []
    for i in range(n + 1):
        s = 0.0
        if i < n:
            s += math.exp(-beta * (Vs[i + 1] - Vs[i]) / 2)
        if i > 0:
            s += math.exp(-beta * (Vs[i - 1] - Vs[i]) / 2)
        d.append(D / h ** 2 * s)
    e = [-D / h ** 2] * n
    psi = [math.exp(-beta * v / 2) for v in Vs]
    res = 0.0
    for i in range(n + 1):
        s = d[i] * psi[i] + (e[i - 1] * psi[i - 1] if i > 0 else 0) + (e[i] * psi[i + 1] if i < n else 0)
        res = max(res, abs(s) / (D / h ** 2 * max(psi)))
    return tri_eigs(d, e, k), res


(ev1, rs1), (ev4, rs4) = fp_gap(lambda x: x * x / 2, -6, 6, 240, 1.0), fp_gap(lambda x: x * x / 2, -4, 4, 320, 4.0)
check('L1 the Gibbs density is stationary for the Fokker-Planck operator, and for a quadratic loss the spectral gap is the curvature at every temperature',
      rs1 < 1e-12 and rs4 < 1e-12 and abs(ev1[0]) < 1e-8 and close(ev1[1], 1, 5e-3) and close(ev4[1], 1, 5e-3),
      'gap %.4f at beta = 1 and %.4f at beta = 4' % (ev1[1], ev4[1]))

kr = {}
for beta in (4.0, 6.0, 8.0, 10.0):
    ev, _ = fp_gap(lambda x: (x * x - 1) ** 2, -2.2, 2.2, 880, beta)
    kr[beta] = (ev[1], math.sqrt(32) / PI * math.exp(-beta))
rt = {b_: kr[b_][0] / kr[b_][1] for b_ in kr}
check('L2 in a double well the gap is the Kramers rate (sqrt(32)/pi) e^{-beta*barrier}, exponentially small in the inverse temperature',
      all(0.7 < v < 1.05 for v in rt.values()) and abs(rt[10.0] - 1) < abs(rt[4.0] - 1) and abs(rt[10.0] - 1) < 0.12,
      'gap / Kramers = %s at beta = 4, 6, 8, 10; gap at beta = 10 is %.2e' % (', '.join('%.3f' % rt[b_] for b_ in sorted(rt)), kr[10.0][0]))

eta, lam_, sig = 0.1, 2.0, 1.5
v = 0.0
for _ in range(2000):
    v = (1 - eta * lam_) ** 2 * v + eta ** 2 * sig ** 2
check('L3 constant-step SGD on a quadratic has stationary variance eta*sigma^2/(lambda(2-eta*lambda)): a temperature eta*sigma^2/2 to first order',
      close(v, eta * sig ** 2 / (lam_ * (2 - eta * lam_)), 1e-12), 'variance %.5f; first-order value %.5f' % (v, eta * sig ** 2 / (2 * lam_)))

sec('9. Control: the Bellman operator and viscosity solutions')
nS, nA, gam = 6, 3, 0.9
Pm = []
for a_ in range(nA):
    rows = []
    for s in range(nS):
        w = [random.random() for _ in range(nS)]
        t_ = sum(w)
        rows.append([q / t_ for q in w])
    Pm.append(rows)
cost = [[random.random() for _ in range(nS)] for _ in range(nA)]


def bell(V):
    return [min(cost[a_][s] + gam * dot(Pm[a_][s], V) for a_ in range(nA)) for s in range(nS)]


def sup(x):
    return max(abs(a_) for a_ in x)


okc = okm = True
worst = 0.0
for _ in range(300):
    V = [random.gauss(0, 3) for _ in range(nS)]
    Wv = [random.gauss(0, 3) for _ in range(nS)]
    q = sup(axpy(-1, bell(V), bell(Wv))) / sup(axpy(-1, V, Wv))
    worst = max(worst, q)
    okc = okc and q <= gam + 1e-12
    Up = [a_ + abs(random.gauss(0, 1)) for a_ in V]
    okm = okm and all(p_ <= q_ + 1e-12 for p_, q_ in zip(bell(V), bell(Up)))
Vs = [0.0] * nS
for _ in range(2000):
    Vs = bell(Vs)
V = [0.0] * nS
e0 = sup(axpy(-1, V, Vs))
okr = True
for k in range(1, 60):
    V = bell(V)
    okr = okr and sup(axpy(-1, V, Vs)) <= gam ** k * e0 + 1e-12
check('Q1 the Bellman operator is monotone and a sup-norm contraction of factor gamma, so value iteration converges geometrically',
      okc and okm and okr and sup(axpy(-1, bell(Vs), Vs)) < 1e-12, 'largest observed contraction ratio %.4f (gamma = %.1f) over 300 pairs' % (worst, gam))

n = 20
h = 1.0 / n
u = [0.0] + [10.0] * (n - 1) + [0.0]
for _ in range(200):
    for i in range(1, n):
        u[i] = min(u[i - 1], u[i + 1]) + h
dist = [min(i * h, 1 - i * h) for i in range(n + 1)]
ev_ = max(abs(a_ - b_) for a_, b_ in zip(u, dist))
saw = [0.0, h, 2 * h, h, 0.0, h, 2 * h, 3 * h, 4 * h, 5 * h, 6 * h, 7 * h, 8 * h, 7 * h, 6 * h, 5 * h, 4 * h, 3 * h, 2 * h, h, 0.0]
res_saw = max(abs(saw[i] - (min(saw[i - 1], saw[i + 1]) + h)) for i in range(1, n))
neg = [-d for d in dist]
res_neg = max(abs(neg[i] - (min(neg[i - 1], neg[i + 1]) + h)) for i in range(1, n))
check('Q2 the monotone scheme for |u\'| = 1 converges to the distance function and rejects the other almost-everywhere solutions',
      ev_ < 1e-12 and res_saw > h and res_neg > h, 'error %.0e; residual of a sawtooth %.2f and of minus the distance %.2f (grid step %.2f)' % (ev_, res_saw, res_neg, h))

sec('10. How many numbers a solution operator needs')
n = 63
lamk = [4 * 64 * 64 * math.sin(k * PI / 128) ** 2 for k in range(1, n + 1)]
ell = [1 / v for v in lamk]
par = [math.exp(-0.01 * v) for v in lamk]
rank_e = sum(1 for v in ell if v / ell[0] > 1e-6)
rank_p = sum(1 for v in par if v / par[0] > 1e-6)
cont_p = max(k for k in range(1, 100) if math.exp(-0.01 * PI * PI * (k * k - 1)) > 1e-6)
n2 = 15
A2 = [[v * 16 * 16 for v in row] for row in lap1(n2, 'D')]
l15, v15 = jacobi_eig(A2)
tt = 0.37
U = [[0.0] * (2 * n2) for _ in range(2 * n2)]
for k in range(n2):
    w_ = math.sqrt(l15[k])
    cs, sn = math.cos(w_ * tt), math.sin(w_ * tt)
    for i in range(n2):
        for j in range(n2):
            pij = v15[k][i] * v15[k][j]
            U[i][j] += cs * pij
            U[i][n2 + j] += sn / w_ * pij
            U[n2 + i][j] += -w_ * sn * pij
            U[n2 + i][n2 + j] += cs * pij
Em = [[0.0] * (2 * n2) for _ in range(2 * n2)]
for i in range(n2):
    for j in range(n2):
        Em[i][j] = A2[i][j]
    Em[n2 + i][n2 + i] = 1.0
UEU = mm(tr(U), mm(Em, U))
iso = max(abs(UEU[i][j] - Em[i][j]) for i in range(2 * n2) for j in range(2 * n2)) / l15[-1]
check('O1 numerical rank at relative accuracy 1e-6: elliptic inverse 1000 modes (algebraic), heat flow at t = 0.01 eleven modes, wave flow all of them',
      rank_e == 63 and cont_p == 11 and rank_p in (11, 12) and close(ell[0], 1 / PI ** 2, 1e-3) and iso < 1e-10,
      'singular values 1/(pi k)^2 exceed 1e-6 of the first for k < 1000; heat: %d in the continuum, %d on a 63-point grid; wave propagator is an isometry of the energy (defect %.0e)' % (cont_p, rank_p, iso))

m = 60
Cm = [[(1 - max((i + 0.5) / m, (j + 0.5) / m)) / m for j in range(m)] for i in range(m)]
lc_, _ = jacobi_eig(Cm)
top = sorted(lc_, reverse=True)[:3]
exact3 = [1 / ((k - 0.5) ** 2 * PI ** 2) for k in (1, 2, 3)]
tail10 = 0.5 - sum(1 / ((k - 0.5) ** 2 * PI ** 2) for k in range(1, 11))
check('O2 translates of a step have covariance eigenvalues 1/((k-1/2)pi)^2: ten modes leave 14 per cent error, the n-width decays like n^(-1/2)',
      all(close(a_, b_, 2e-3) for a_, b_ in zip(top, exact3)) and close(math.sqrt(tail10 / 0.5), 0.1424, 5e-3),
      'eigenvalues %s (exact %s); relative error after 10 modes %.4f, after 100 modes %.4f' % (', '.join('%.5f' % v for v in top), ', '.join('%.5f' % v for v in exact3), math.sqrt(tail10 / 0.5), math.sqrt((0.5 - sum(1 / ((k - 0.5) ** 2 * PI ** 2) for k in range(1, 101))) / 0.5)))

footer()
