#!/usr/bin/env python3
# verify-topology-learning.py
# Companion script to "Algebraic and Differential Topology in Machine Learning and AI: Obstructions, Invariants,
# and Counts" (Higher Categorical Semantics, 2026; byline Anonymous).
# 25 computational checks of the numerical and finite statements in the paper. Python standard library only; fixed seeds.
# Usage: python3 verify-topology-learning.py   (under half a minute; 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)


# ######################## SIMPLICIAL TOPOLOGY (exact) ########################
def closure(facets):
    S = {}
    for f in facets:
        f = tuple(sorted(f))
        for k in range(1, len(f) + 1):
            for c in itertools.combinations(f, k):
                S.setdefault(k - 1, set()).add(c)
    return {d: sorted(v) for d, v in S.items()}


class Cx:
    """finite simplicial complex with vertices ordered; simplices are sorted tuples"""
    def __init__(s, facets):
        s.S = closure(facets)
        s.dim = max(s.S)
        s.idx = {d: {x: i for i, x in enumerate(s.S[d])} for d in s.S}

    def n(s, d):
        return len(s.S.get(d, []))

    def fvec(s):
        return [s.n(d) for d in range(s.dim + 1)]

    def chi(s):
        return sum((-1) ** d * s.n(d) for d in range(s.dim + 1))

    def bd(s, d):
        """boundary matrix C_d -> C_{d-1} (rows: (d-1)-simplices)"""
        if d <= 0 or d > s.dim:
            return [[0] * s.n(d) for _ in range(s.n(d - 1) if d > 0 else 0)]
        M = [[0] * s.n(d) for _ in range(s.n(d - 1))]
        for j, x in enumerate(s.S[d]):
            for i in range(d + 1):
                M[s.idx[d - 1][x[:i] + x[i + 1:]]][j] = (-1) ** i
        return M


def snf(M):
    """non-zero invariant factors of an integer matrix (Smith normal form)"""
    A = [list(r) for r in M]
    m = len(A)
    n = len(A[0]) if m else 0
    out = []
    t = 0
    while t < min(m, n):
        piv = None
        for i in range(t, m):
            for j in range(t, n):
                if A[i][j] and (piv is None or abs(A[i][j]) < abs(A[piv[0]][piv[1]])):
                    piv = (i, j)
        if piv is None:
            break
        A[t], A[piv[0]] = A[piv[0]], A[t]
        for r in A:
            r[t], r[piv[1]] = r[piv[1]], r[t]
        while True:
            done = True
            for i in range(t + 1, m):
                if A[i][t]:
                    q = A[i][t] // A[t][t]
                    if q:
                        A[i] = [a - q * b for a, b in zip(A[i], A[t])]
                    if A[i][t]:
                        A[t], A[i] = A[i], A[t]
                        done = False
            for j in range(t + 1, n):
                if A[t][j]:
                    q = A[t][j] // A[t][t]
                    if q:
                        for r in A:
                            r[j] -= q * r[t]
                    if A[t][j]:
                        for r in A:
                            r[t], r[j] = r[j], r[t]
                        done = False
            if done:
                bad = None
                for i in range(t + 1, m):
                    for j in range(t + 1, n):
                        if A[i][j] % A[t][t]:
                            bad = i
                            break
                    if bad is not None:
                        break
                if bad is None:
                    break
                A[t] = [a + b for a, b in zip(A[t], A[bad])]
        out.append(abs(A[t][t]))
        t += 1
    return out


def rank_mod(M, p):
    A = [[x % p for x in r] for r in M]
    rk = 0
    n = len(A[0]) if A else 0
    for c in range(n):
        piv = next((i for i in range(rk, len(A)) if A[i][c]), None)
        if piv is None:
            continue
        A[rk], A[piv] = A[piv], A[rk]
        inv_ = pow(A[rk][c], p - 2, p)
        A[rk] = [(x * inv_) % p for x in A[rk]]
        for i in range(len(A)):
            if i != rk and A[i][c]:
                f = A[i][c]
                A[i] = [(x - f * y) % p for x, y in zip(A[i], A[rk])]
        rk += 1
    return rk


BIGP = 1000003


def homology(K):
    """list over d of (betti number, torsion coefficients)"""
    facs = {d: snf(K.bd(d)) for d in range(1, K.dim + 1)}
    out = []
    for d in range(K.dim + 1):
        rk_d = len(facs.get(d, []))
        rk_up = len(facs.get(d + 1, []))
        out.append((K.n(d) - rk_d - rk_up, [x for x in facs.get(d + 1, []) if x > 1]))
    return out


def betti_mod(K, p):
    r = {d: rank_mod(K.bd(d), p) if K.n(d) and K.n(d - 1) else 0 for d in range(1, K.dim + 2)}
    return [K.n(d) - r.get(d, 0) - r.get(d + 1, 0) for d in range(K.dim + 1)]


def bettis(K):
    return [b for b, _ in homology(K)]


def perm_sign(seq):
    seq = list(seq)
    s = 1
    for i in range(len(seq)):
        for j in range(i + 1, len(seq)):
            if seq[i] > seq[j]:
                s = -s
    return s


def chain_map(K, L, vmap, d):
    """matrix of the simplicial map on d-chains"""
    M = [[0] * K.n(d) for _ in range(L.n(d))]
    for j, x in enumerate(K.S.get(d, [])):
        y = [vmap[v] for v in x]
        if len(set(y)) == d + 1:
            M[L.idx[d][tuple(sorted(y))]][j] = perm_sign(y)
    return M


def mat_mul(A, B):
    if not A or not B:
        return [[0] * (len(B[0]) if B else 0) for _ in A]
    Bt = list(zip(*B))
    return [[sum(a * b for a, b in zip(r, c)) for c in Bt] for r in A]


def mat_eq(A, B):
    return all(list(r) == list(q) for r, q in zip(A, B)) and len(A) == len(B)


def mat_sub(A, B):
    return [[a - b for a, b in zip(r, q)] for r, q in zip(A, B)]


def trace(M):
    return sum(M[i][i] for i in range(min(len(M), len(M[0]) if M else 0)))


def nullspace(M, ncols):
    """rational basis of the kernel"""
    A = [[Fr(x) for x in r] for r in M]
    piv = []
    rk = 0
    for c in range(ncols):
        p = next((i for i in range(rk, len(A)) if A[i][c] != 0), None)
        if p is None:
            continue
        A[rk], A[p] = A[p], A[rk]
        A[rk] = [x / A[rk][c] for x in A[rk]]
        for i in range(len(A)):
            if i != rk and A[i][c] != 0:
                f = A[i][c]
                A[i] = [x - f * y for x, y in zip(A[i], A[rk])]
        piv.append(c)
        rk += 1
    free = [c for c in range(ncols) if c not in piv]
    basis = []
    for f in free:
        v = [Fr(0)] * ncols
        v[f] = Fr(1)
        for i, c in enumerate(piv):
            v[c] = -A[i][f]
        basis.append(v)
    return basis


def independent_extend(base, cands):
    """greedily pick vectors of cands independent modulo span(base); returns (reduced rows, picked)"""
    rows = []
    def reduce(v):
        v = list(v)
        for r, c in rows:
            if v[c] != 0:
                f = v[c] / r[c]
                v = [a - f * b for a, b in zip(v, r)]
        return v
    def add(v):
        v = reduce(v)
        c = next((i for i, a in enumerate(v) if a != 0), None)
        if c is None:
            return False
        rows.append((v, c))
        return True
    for b in base:
        add([Fr(x) for x in b])
    picked = []
    for v in cands:
        if add(v):
            picked.append(v)
    return picked


def solve_coords(cols, v):
    """coordinates of v in the independent family cols (exact)"""
    n = len(cols)
    m = len(v)
    A = [[Fr(cols[j][i]) for j in range(n)] + [Fr(v[i])] for i in range(m)]
    rk = 0
    piv = []
    for c in range(n):
        p = next((i for i in range(rk, m) if A[i][c] != 0), None)
        if p is None:
            return None
        A[rk], A[p] = A[p], A[rk]
        A[rk] = [x / A[rk][c] for x in A[rk]]
        for i in range(m):
            if i != rk and A[i][c] != 0:
                f = A[i][c]
                A[i] = [x - f * y for x, y in zip(A[i], A[rk])]
        piv.append(c)
        rk += 1
    if any(A[i][n] != 0 for i in range(rk, m)):
        return None
    return [A[i][n] for i in range(n)]


def homology_trace(K, vmap, d):
    """trace of the map induced on H_d(K; Q) by a simplicial self-map"""
    n = K.n(d)
    Z = nullspace(K.bd(d), n) if d > 0 else [[Fr(int(i == j)) for i in range(n)] for j in range(n)]
    Bd = K.bd(d + 1) if d < K.dim else []
    Bcols = [list(c) for c in zip(*Bd)] if Bd and Bd[0] else []
    Bbasis = independent_extend([], [[Fr(x) for x in c] for c in Bcols])
    H = independent_extend(Bbasis, Z)
    if not H:
        return 0
    F = chain_map(K, K, vmap, d)
    cols = Bbasis + H
    t = Fr(0)
    for j, h in enumerate(H):
        img = [sum(F[i][k] * h[k] for k in range(n)) for i in range(n)]
        co = solve_coords(cols, img)
        t += co[len(Bbasis) + j]
    return t


def lefschetz_chain(K, vmap):
    return sum((-1) ** d * trace(chain_map(K, K, vmap, d)) for d in range(K.dim + 1))


def lefschetz_hom(K, vmap):
    return sum((-1) ** d * homology_trace(K, vmap, d) for d in range(K.dim + 1))


def sd(K):
    """barycentric subdivision; vertices are the simplices of K, numbered by (dim, index)"""
    num = {}
    for d in range(K.dim + 1):
        for x in K.S[d]:
            num[x] = len(num)
    facets = []
    for d in range(K.dim, -1, -1):
        for x in K.S[d]:
            if any(set(x) < set(y) for y in K.S.get(d + 1, [])):
                continue
            for perm in itertools.permutations(x):
                facets.append([num[tuple(sorted(perm[:k]))] for k in range(1, len(perm) + 1)])
    return Cx(facets), num


def cone(K, apex=None):
    top = max(v for x in K.S[0] for v in x) + 1 if apex is None else apex
    return Cx([list(x) + [top] for d in K.S for x in K.S[d]]), top


def suspension(K):
    top = max(v for x in K.S[0] for v in x) + 1
    return Cx([list(x) + [top] for x in K.S[K.dim]] + [list(x) + [top + 1] for x in K.S[K.dim]] +
              [list(x) + [top] for d in K.S for x in K.S[d]] + [list(x) + [top + 1] for d in K.S for x in K.S[d]])


def facets_of(K):
    return [x for d in K.S for x in K.S[d] if not any(set(x) < set(y) for y in K.S.get(d + 1, []))]


def prism(K):
    """K x I with vertices v (bottom) and v + N (top)"""
    N = max(v for x in K.S[0] for v in x) + 1
    F = []
    for x in facets_of(K):
        for i in range(len(x)):
            F.append(list(x[:i + 1]) + [v + N for v in x[i:]])
    return Cx(F), N


def is_pseudomanifold(K, closed=True):
    d = K.dim
    cnt = {}
    for x in K.S[d]:
        for i in range(d + 1):
            f = x[:i] + x[i + 1:]
            cnt[f] = cnt.get(f, 0) + 1
    vals = set(cnt.values())
    return (vals == {2}) if closed else (vals <= {1, 2})


def torus7():
    return Cx([[i, (i + 1) % 7, (i + 3) % 7] for i in range(7)] + [[i, (i + 2) % 7, (i + 3) % 7] for i in range(7)])


def rp2():
    return Cx([[1, 2, 4], [1, 2, 6], [1, 3, 4], [1, 3, 5], [1, 5, 6], [2, 3, 5], [2, 3, 6], [2, 4, 5], [3, 4, 6], [4, 5, 6]])


def klein():
    def v(i, j):
        if i == 4:
            i, j = 0, (-j) % 4
        return 4 * i + (j % 4)
    F = []
    for i in range(4):
        for j in range(4):
            F.append([v(i, j), v(i + 1, j), v(i + 1, j + 1)])
            F.append([v(i, j), v(i, j + 1), v(i + 1, j + 1)])
    return Cx(F)


def moebius():
    return Cx([[i, (i + 1) % 5, (i + 2) % 5] for i in range(5)])


def simplex_boundary(n):
    return Cx([c for c in itertools.combinations(range(n + 2), n + 1)])


def cross_sphere(n):
    """boundary of the (n+1)-dimensional cross-polytope; vertex 2i is +e_i, 2i+1 is -e_i"""
    return Cx([[2 * i + s for i, s in enumerate(signs)] for signs in itertools.product((0, 1), repeat=n + 1)])


def icosahedron():
    T, B = 0, 11
    u = lambda i: 1 + i % 5
    l = lambda i: 6 + i % 5
    F = []
    for i in range(5):
        F += [[T, u(i), u(i + 1)], [u(i), u(i + 1), l(i)], [u(i + 1), l(i), l(i + 1)], [B, l(i), l(i + 1)]]
    return Cx(F)


def grid_torus(m, d):
    """Freudenthal triangulation of (Z/m)^d"""
    def num(v):
        r = 0
        for a in v:
            r = r * m + a % m
        return r
    F = []
    for v in itertools.product(range(m), repeat=d):
        for perm in itertools.permutations(range(d)):
            w = list(v)
            s = [num(w)]
            for k in perm:
                w[k] += 1
                s.append(num(w))
            F.append(s)
    return Cx(F)


def circle(n):
    return Cx([[i, (i + 1) % n] for i in range(n)])


# ######################## CHECKS FOR THE PAPER ########################
random.seed(20261119)


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


def trig_poly(deg=3):
    co = [(random.gauss(0, 1), random.gauss(0, 1)) for _ in range(deg + 1)]
    return lambda t: sum(a * math.cos(k * t) + b * math.sin(k * t) for k, (a, b) in enumerate(co))


sec('1. Obstructions')
okbu = True
for _ in range(200):
    e = trig_poly()
    g = lambda t: e(t) - e(t + PI)
    t0 = bisect(g, 0.0, PI)
    okbu = okbu and abs(e(t0) - e(t0 + PI)) < 1e-9
check('O1 Borsuk-Ulam on the circle: every continuous code e: S^1 -> R identifies some pair of antipodal points', okbu, '200 random trigonometric encoders; collision found by bisection each time')


def cubic_odd():
    lin = [[random.gauss(0, 1) for _ in range(3)] for _ in range(2)]
    cub = [[random.gauss(0, 1) for _ in range(10)] for _ in range(2)]
    mons = [(3, 0, 0), (0, 3, 0), (0, 0, 3), (2, 1, 0), (2, 0, 1), (1, 2, 0), (0, 2, 1), (1, 0, 2), (0, 1, 2), (1, 1, 1)]
    def g(u, v):
        x = (math.sin(u) * math.cos(v), math.sin(u) * math.sin(v), math.cos(u))
        return [sum(l * a for l, a in zip(lin[i], x)) + sum(c * x[0] ** m[0] * x[1] ** m[1] * x[2] ** m[2] for c, m in zip(cub[i], mons)) for i in range(2)]
    return g


def find_zero_sphere(g):
    grid = []
    for i in range(1, 36):
        for j in range(72):
            u, v = PI * i / 36, 2 * PI * j / 72
            grid.append((vnorm(g(u, v)), u, v))
    grid.sort()
    best = 1.0
    for _, u, v in grid[:25]:
        for _ in range(80):
            f0 = g(u, v)
            h = 1e-6
            fu = [(a - b) / (2 * h) for a, b in zip(g(u + h, v), g(u - h, v))]
            fv = [(a - b) / (2 * h) for a, b in zip(g(u, v + h), g(u, v - h))]
            det = fu[0] * fv[1] - fu[1] * fv[0]
            if abs(det) < 1e-14:
                break
            du = (f0[0] * fv[1] - f0[1] * fv[0]) / det
            dv = (fu[0] * f0[1] - fu[1] * f0[0]) / det
            step = max(abs(du), abs(dv))
            sc = min(1.0, 0.2 / step) if step > 0 else 1.0
            u, v = u - sc * du, v - sc * dv
        best = min(best, vnorm(g(u, v)))
        if best < 1e-11:
            break
    return best


res2 = [find_zero_sphere(cubic_odd()) for _ in range(40)]
check('O2 Borsuk-Ulam on the sphere: every continuous code e: S^2 -> R^2 identifies a pair of antipodal points', max(res2) < 1e-9,
      '40 random cubic encoders; largest residual |e(x) - e(-x)| at the point found %.1e' % max(res2))


def bottleneck_radius(e, M=3000, bins=100):
    ts = [2 * PI * i / M for i in range(M)]
    cs = [e(t) for t in ts]
    lo, hi = min(cs), max(cs)
    groups = {}
    for t, c in zip(ts, cs):
        groups.setdefault(min(bins - 1, int((c - lo) / (hi - lo) * bins)), []).append(t)
    best = 0.0
    for b, g in groups.items():
        g = sorted(g)
        gap = max([g[i + 1] - g[i] for i in range(len(g) - 1)] + [g[0] + 2 * PI - g[-1]])
        arc = 2 * PI - gap
        best = max(best, 1.0 if arc >= PI else math.sin(arc / 2))
    return best


rad = [bottleneck_radius(trig_poly()) for _ in range(100)]
tight = max(abs(math.sin(2 * PI * i / 1000)) for i in range(1000))
check('O3 a one-dimensional bottleneck for the unit circle has worst-case reconstruction error at least 1, and the code cos(theta) attains 1',
      min(rad) > 0.995 and close(tight, 1.0, 1e-9), 'smallest radius of a fibre of the code over 100 random encoders: %.4f; error of the projection code: %.4f' % (min(rad), tight))


def qmul(a, b):
    return (a[0] * b[0] - a[1] * b[1] - a[2] * b[2] - a[3] * b[3], a[0] * b[1] + a[1] * b[0] + a[2] * b[3] - a[3] * b[2],
            a[0] * b[2] - a[1] * b[3] + a[2] * b[0] + a[3] * b[1], a[0] * b[3] + a[1] * b[2] - a[2] * b[1] + a[3] * b[0])


def qrotf(q):
    w, x, y, z = q
    return [[1 - 2 * (y * y + z * z), 2 * (x * y - w * z), 2 * (x * z + w * y)],
            [2 * (x * y + w * z), 1 - 2 * (x * x + z * z), 2 * (y * z - w * x)],
            [2 * (x * z - w * y), 2 * (y * z + w * x), 1 - 2 * (x * x + y * y)]]


def axis_q(u, th):
    n = vnorm(u)
    return (math.cos(th / 2),) + tuple(math.sin(th / 2) * a / n for a in u)


def canon(q):
    s = 1 if (q[0] > 1e-12 or (abs(q[0]) <= 1e-12 and next((a for a in q[1:] if abs(a) > 1e-12), 1) > 0)) else -1
    return tuple(s * a for a in q)


def euler(R):
    return (math.atan2(R[1][0], R[0][0]), math.asin(max(-1.0, min(1.0, -R[2][0]))), math.atan2(R[2][1], R[2][2]))


def six(R):
    return [R[0][0], R[1][0], R[2][0], R[0][1], R[1][1], R[2][1]]


def gram_schmidt(s):
    a1, a2 = s[:3], s[3:]
    n1 = vnorm(a1)
    b1 = [x / n1 for x in a1]
    d = sum(x * y for x, y in zip(b1, a2))
    c = [y - d * x for x, y in zip(b1, a2)]
    n2 = vnorm(c)
    b2 = [x / n2 for x in c]
    b3 = [b1[1] * b2[2] - b1[2] * b2[1], b1[2] * b2[0] - b1[0] * b2[2], b1[0] * b2[1] - b1[1] * b2[0]]
    return [[b1[i], b2[i], b3[i]] for i in range(3)]


def fro(A, B):
    return math.sqrt(sum((a - b) ** 2 for r, q in zip(A, B) for a, b in zip(r, q)))


Nst = 2000
u0 = [0.3, -0.5, 0.8]
jq = je = jm = j6 = 0.0
prevR = prevq = preve = None
for i in range(Nst + 1):
    th = 2 * PI * i / Nst
    R = qrotf(axis_q(u0, th))
    Ry = qrotf(axis_q([0, 1, 0], th))
    q, e = canon(axis_q(u0, th)), euler(Ry)
    if prevR is not None:
        jm = max(jm, fro(R, prevR))
        jq = max(jq, vnorm([a - b for a, b in zip(q, prevq)]))
        je = max(je, max(abs(a - b) for a, b in zip(e, preve)))
        j6 = max(j6, vnorm([a - b for a, b in zip(six(R), six(prevR))]))
    prevR, prevq, preve = R, q, e
check('O4 along a full turn the rotation matrix moves by small steps, the canonical quaternion jumps by 2 and the Euler angles by pi; the six-dimensional code does not jump',
      jm < 0.01 and close(jq, 2.0, 1e-3) and close(je, PI, 1e-2) and j6 <= jm + 1e-12,
      'largest step over 2000 steps: matrix %.4f, quaternion %.4f, Euler angles %.4f, 6D code %.4f' % (jm, jq, je, j6))

ok6 = True
lip = 0.0
for _ in range(200):
    q = [random.gauss(0, 1) for _ in range(4)]
    n = vnorm(q)
    R = qrotf(tuple(a / n for a in q))
    ok6 = ok6 and fro(gram_schmidt(six(R)), R) < 1e-12
    noise = [random.gauss(0, 1e-3) for _ in range(6)]
    R2 = gram_schmidt([a + b for a, b in zip(six(R), noise)])
    lip = max(lip, fro(R2, R) / vnorm(noise))
check('O5 the six-dimensional code (two columns, then Gram-Schmidt) is a continuous right inverse with a Lipschitz decoder', ok6 and lip < 3.0,
      '200 random rotations recovered to 1e-12; decoder moves by at most %.2f times a perturbation of the code' % lip)


def link_cycle(K, v):
    edges = [tuple(a for a in t if a != v) for t in K.S[2] if v in t]
    nxt = {}
    for a, b in edges:
        nxt.setdefault(a, []).append(b)
        nxt.setdefault(b, []).append(a)
    start = edges[0][0]
    cyc = [start]
    prev, cur = None, start
    while True:
        cand = [w for w in nxt[cur] if w != prev]
        if not cand:
            break
        w = cand[0]
        if w == start:
            break
        cyc.append(w)
        prev, cur = cur, w
    return cyc


def index_sum(K):
    h = {x[0]: random.random() for x in K.S[0]}
    tot = 0
    for x in K.S[0]:
        v = x[0]
        cyc = link_cycle(K, v)
        s = [h[w] > h[v] for w in cyc]
        changes = sum(1 for i in range(len(s)) if s[i] != s[(i + 1) % len(s)])
        tot += Fr(2 - changes, 2)
    return tot


surfs = [('sphere', simplex_boundary(2), 2), ('icosahedron', icosahedron(), 2), ('torus', torus7(), 0), ('projective plane', rp2(), 1), ('Klein bottle', klein(), 0)]
okidx = all(index_sum(K) == chi for _, K, chi in surfs for _ in range(100))
check('O6 hairy ball on meshes: the indices of the critical vertices of any generic function on a triangulated surface add up to the Euler characteristic',
      okidx, '100 random functions on each of five surfaces; sums 2, 2, 0, 1, 0')

okcp = True
for _ in range(50):
    k = 6
    xs = sorted(random.random() for _ in range(k))
    knots = [0.0] + xs + [1.0]
    ys = [random.gauss(0, 1) for _ in knots]
    slopes = [(ys[i + 1] - ys[i]) / (knots[i + 1] - knots[i]) for i in range(len(knots) - 1)]
    def net(x):
        return ys[0] + slopes[0] * x + sum((slopes[i] - slopes[i - 1]) * max(x - knots[i], 0.0) for i in range(1, len(slopes)))
    def pl(x):
        i = max(j for j in range(len(knots) - 1) if knots[j] <= x)
        return ys[i] + slopes[i] * (x - knots[i])
    okcp = okcp and all(abs(net(x) - pl(x)) < 1e-10 for x in [random.random() for _ in range(40)])
check('O7 a continuous piecewise linear function with k breakpoints is an affine function plus k rectifier units, exactly', okcp, '50 random functions with 6 breakpoints')


def polygon_winding(d, N):
    tot = 0.0
    for j in range(N):
        a = cmath.exp(2j * PI * d * j / N)
        b = cmath.exp(2j * PI * d * (j + 1) / N)
        tot += cmath.phase(b / a)
    return round(tot / (2 * PI))


def rep(d, N):
    r = d % N
    return r - N if r > N / 2 else r


cases = [(3, 5), (3, 7), (3, 12), (5, 8), (2, 5), (4, 9), (-3, 7), (7, 10)]
wind = {c: polygon_winding(*c) for c in cases}
check('O8 a closed piecewise linear curve with N pieces through the points of z -> z^d winds d times only if N > 2|d|; otherwise it winds d reduced modulo N',
      all(wind[c] == rep(*c) for c in cases) and wind[(3, 5)] == -2 and wind[(3, 7)] == 3, 'windings %s' % wind)

# --- O9: depth multiplies degree (own generator, so that later checks keep their random inputs)
def sq_point(u):
    u %= 8.0
    if u < 2:
        return (1.0, u - 1.0)
    if u < 4:
        return (3.0 - u, 1.0)
    if u < 6:
        return (-1.0, 5.0 - u)
    return (u - 7.0, -1.0)


def sq_param(x):
    m = max(abs(x[0]), abs(x[1]))
    a, b = x[0] / m, x[1] / m
    if a == 1.0 and b > -1.0:
        return 1.0 + b
    if b == 1.0:
        return 3.0 - a
    if a == -1.0:
        return 5.0 - b
    if b == -1.0:
        return 7.0 + a
    # not exactly on a side after division: choose the nearest side
    cands = [(abs(a - 1), 1.0 + b), (abs(b - 1), 3.0 - a), (abs(a + 1), 5.0 - b), (abs(b + 1), 7.0 + a)]
    return min(cands)[1]


def fold2(x):
    """a continuous piecewise linear map of the plane, linear on eight cones, of degree 2 on the boundary of the square"""
    m = max(abs(x[0]), abs(x[1]))
    p = sq_point(2.0 * sq_param(x))
    return (m * p[0], m * p[1])


def deep_curve(L, per_piece=4):
    npc = 4 * 2 ** L
    pts_ = []
    for j in range(npc * per_piece):
        x = sq_point(8.0 * j / (npc * per_piece))
        for _ in range(L):
            x = fold2(x)
        pts_.append(x)
    return pts_


def curve_winding(pts_):
    tot = 0.0
    for i in range(len(pts_)):
        a, b = complex(*pts_[i]), complex(*pts_[(i + 1) % len(pts_)])
        tot += cmath.phase(b / a)
    return round(tot / (2 * PI))


def count_pieces(pts_):
    """number of maximal straight pieces of a closed polygon given by its points in order"""
    n = len(pts_)
    c = 0
    for i in range(n):
        p, q, r_ = pts_[i - 1], pts_[i], pts_[(i + 1) % n]
        cr = (q[0] - p[0]) * (r_[1] - q[1]) - (q[1] - p[1]) * (r_[0] - q[0])
        if abs(cr) > 1e-9:
            c += 1
    return c


rg9 = random.Random(20261120)
lin_ok = True
for _ in range(200):
    # linear on each cone: additive on pairs of points of the same cone, and positively homogeneous
    th = rg9.uniform(0, 2 * PI)
    k8 = int(((th + PI / 4) % (2 * PI)) / (PI / 4))
    a0 = -PI / 4 + k8 * PI / 4
    t1, t2 = a0 + rg9.uniform(0.02, PI / 4 - 0.02), a0 + rg9.uniform(0.02, PI / 4 - 0.02)
    r1, r2 = rg9.uniform(0.3, 2), rg9.uniform(0.3, 2)
    x1, x2 = (r1 * math.cos(t1), r1 * math.sin(t1)), (r2 * math.cos(t2), r2 * math.sin(t2))
    f1, f2, f12 = fold2(x1), fold2(x2), fold2((x1[0] + x2[0], x1[1] + x2[1]))
    lin_ok = lin_ok and abs(f12[0] - f1[0] - f2[0]) < 1e-9 and abs(f12[1] - f1[1] - f2[1]) < 1e-9
deep = []
for L in range(1, 7):
    cv = deep_curve(L)
    deep.append((L, curve_winding(cv), count_pieces(cv)))
check('O9 depth multiplies degree: L compositions of one piecewise linear map with eight pieces wind 2^L times, with 4*2^L pieces, against the bound of more than 2^(L+1)',
      lin_ok and all(w == 2 ** L and pc == 4 * 2 ** L and pc > 2 * w for L, w, pc in deep),
      'map linear on each of eight cones (200 random pairs); (depth, winding, pieces): %s' % deep)

# --- O10: narrow networks
SLOPE = 0.2
def lrelu(v):
    return v if v > 0 else SLOPE * v
def lrelu_inv(v):
    return v if v > 0 else v / SLOPE


def narrow_net(rg, depth=4):
    layers = []
    while len(layers) < depth:
        A = [[rg.gauss(0, 1), rg.gauss(0, 1)], [rg.gauss(0, 1), rg.gauss(0, 1)]]
        dt = A[0][0] * A[1][1] - A[0][1] * A[1][0]
        if abs(dt) > 0.3:
            layers.append((A, [rg.gauss(0, 0.5), rg.gauss(0, 0.5)], dt))
    w = [rg.gauss(0, 1), rg.gauss(0, 1)]
    return layers, w, rg.gauss(0, 0.5)


def narrow_fwd(net, x):
    layers, w, c = net
    for A, b, _ in layers:
        x = (lrelu(A[0][0] * x[0] + A[0][1] * x[1] + b[0]), lrelu(A[1][0] * x[0] + A[1][1] * x[1] + b[1]))
    return w[0] * x[0] + w[1] * x[1] + c


def narrow_inv(net, y):
    layers = net[0]
    for A, b, dt in reversed(layers):
        z = (lrelu_inv(y[0]) - b[0], lrelu_inv(y[1]) - b[1])
        y = ((A[1][1] * z[0] - A[0][1] * z[1]) / dt, (-A[1][0] * z[0] + A[0][0] * z[1]) / dt)
    return y


rg10 = random.Random(20261121)
ok_conn = ok_unb = ok_circ = True
for _ in range(30):
    net = narrow_net(rg10)
    layers, w, c = net
    nw = math.hypot(*w)
    nrm = (w[0] / nw, w[1] / nw)
    tng = (-nrm[1], nrm[0])
    base = (-c / nw * nrm[0], -c / nw * nrm[1])
    for sgn in (1, -1):
        # two random points of the half-plane on one side of the last layer; the straight path between them, pulled back
        ys = []
        for _ in range(2):
            un, ut = sgn * rg10.uniform(0.1, 30), rg10.uniform(-30, 30)
            ys.append((base[0] + un * nrm[0] + ut * tng[0], base[1] + un * nrm[1] + ut * tng[1]))
        for i in range(41):
            t = i / 40
            x = narrow_inv(net, ((1 - t) * ys[0][0] + t * ys[1][0], (1 - t) * ys[0][1] + t * ys[1][1]))
            ok_conn = ok_conn and sgn * narrow_fwd(net, x) > 0
        # a ray inside the half-plane, pulled back, leaves every bounded set
        nr = [math.hypot(*narrow_inv(net, (base[0] + sgn * nrm[0] + s_ * tng[0], base[1] + sgn * nrm[1] + s_ * tng[1]))) for s_ in (1e2, 1e3, 1e4)]
        ok_unb = ok_unb and nr[0] < nr[1] < nr[2] and nr[2] > 50
    r0 = max(1.0, math.hypot(*narrow_inv(net, base)))   # a point of the decision boundary lies at this distance
    for R_ in (10 * r0, 100 * r0, 1000 * r0):
        sg = {narrow_fwd(net, (R_ * math.cos(2 * PI * i / 3600), R_ * math.sin(2 * PI * i / 3600))) > 0 for i in range(3600)}
        ok_circ = ok_circ and sg == {True, False}
tri = [(math.cos(PI / 2 + 2 * PI * k / 3), math.sin(PI / 2 + 2 * PI * k / 3)) for k in range(3)]
def island(x):
    return 1.0 - sum(max(0.0, a[0] * x[0] + a[1] * x[1]) for a in tri)
isl_out = max(island((4 * math.cos(2 * PI * i / 720), 4 * math.sin(2 * PI * i / 720))) for i in range(720))
check('O10 width: with two inputs, two units per layer and an injective activation both decision regions are connected and unbounded; three units can enclose a bounded region',
      ok_conn and ok_unb and ok_circ and island((0.0, 0.0)) > 0 and isl_out < 0,
      '30 random networks of depth 4: explicit paths inside each region, both classes on three circles of radius 10 to 1000 times the distance of the boundary; three-unit island: value %.1f at the centre, at most %.2f on the circle of radius 4' % (island((0.0, 0.0)), isl_out))

# --- O11: a global frame on the 3-sphere
rg11 = random.Random(20261122)
fr_err = 0.0
for _ in range(200):
    q = [rg11.gauss(0, 1) for _ in range(4)]
    n_ = vnorm(q)
    q = tuple(a / n_ for a in q)
    fr = [qmul(q, e_) for e_ in ((0, 1, 0, 0), (0, 0, 1, 0), (0, 0, 0, 1))]
    vs_ = [q] + fr
    for i in range(4):
        for j in range(4):
            fr_err = max(fr_err, abs(sum(a * b for a, b in zip(vs_[i], vs_[j])) - (1.0 if i == j else 0.0)))
check('O11 the 3-sphere has a global frame: at every unit quaternion q the vectors qi, qj, qk are orthonormal and tangent', fr_err < 1e-12,
      '200 random points; largest deviation from orthonormality %.1e' % fr_err)

sec('2. Invariants')


def hodge(K, k):
    n = K.n(k)
    L = [[0] * n for _ in range(n)]
    if k > 0:
        B = K.bd(k)
        L = mat_mul([list(r) for r in zip(*B)], B)
    if k < K.dim:
        B = K.bd(k + 1)
        U = mat_mul(B, [list(r) for r in zip(*B)])
        L = [[a + b for a, b in zip(r, q)] for r, q in zip(L, U)]
    return L


disc, _ = cone(circle(6))
models = [('sphere', simplex_boundary(2)), ('torus', torus7()), ('projective plane', rp2()), ('Klein bottle', klein()), ('Moebius band', moebius()), ('disc', disc)]
harm = {nm: [K.n(k) - rank_mod(hodge(K, k), BIGP) for k in range(3)] for nm, K in models}
check('V1 Hodge: the kernel of the k-th Hodge Laplacian has dimension the k-th Betti number over the reals',
      harm == {'sphere': [1, 0, 1], 'torus': [1, 2, 1], 'projective plane': [1, 0, 0], 'Klein bottle': [1, 1, 0], 'Moebius band': [1, 1, 0], 'disc': [1, 0, 0]}
      and all(harm[nm] == bettis(K) for nm, K in models), 'harmonic dimensions %s' % harm)

m2 = {nm: betti_mod(K, 2) for nm, K in models}
check('V2 real coefficients are blind to torsion: the projective plane and the disc have the same harmonic spaces, and are separated modulo 2; the Klein bottle and the torus the reverse',
      harm['projective plane'] == harm['disc'] and m2['projective plane'] == [1, 1, 1] and m2['disc'] == [1, 0, 0]
      and m2['Klein bottle'] == m2['torus'] == [1, 2, 1] and harm['Klein bottle'] != harm['torus'],
      'mod 2: projective plane %s, disc %s, Klein bottle %s, torus %s' % (m2['projective plane'], m2['disc'], m2['Klein bottle'], m2['torus']))

T7 = torus7()
L1 = [[float(v) for v in r] for r in hodge(T7, 1)]
ev, _ = jacobi_eig(L1)
nz = [v for v in ev if v > 1e-9]
gap, lmax = min(nz), max(ev)
steps = int(math.ceil(math.log(1e-11) / math.log(1 - gap / lmax)))
lims = []
for _ in range(4):
    X = [random.gauss(0, 1) for _ in range(len(L1))]
    for _ in range(steps):
        X = axpy(-1 / lmax, mv(L1, X), X)
    lims.append(X)
resid = max(vnorm(mv(L1, X)) / vnorm(X) for X in lims)
G = [[dot(a, b) for b in lims] for a in lims]
ge, _ = jacobi_eig(G)
rk = sum(1 for v in ge if v > 1e-8 * max(ge))
check('V3 simplicial message passing on edges converges to the harmonic 1-forms: a two-dimensional space on the torus, at the rate of the spectral gap',
      len(ev) - len(nz) == 2 and resid < 1e-9 and rk == 2, 'gap %.4f, largest eigenvalue %.4f, %d layers for 1e-11; limits of four random inputs span dimension %d' % (gap, lmax, steps, rk))


def rips_circulant(n, k, maxdim=None):
    def ok(c):
        return all(min((a - b) % n, (b - a) % n) <= k for a, b in itertools.combinations(c, 2))
    simp = []
    frontier = [(i,) for i in range(n)]
    while frontier:
        simp += frontier
        new = []
        for c in frontier:
            if maxdim is not None and len(c) > maxdim:
                continue
            for v in range(c[-1] + 1, n):
                if all(min((a - v) % n, (v - a) % n) <= k for a in c):
                    new.append(c + (v,))
        frontier = new
    return Cx(simp)


rb = {k: betti_mod(rips_circulant(12, k), 2) for k in (1, 2, 3, 4, 5)}
def trim(b):
    b = list(b)
    while len(b) > 1 and b[-1] == 0:
        b.pop()
    return b
rb = {k: trim(v) for k, v in rb.items()}
check('V4 Betti numbers for 12 equally spaced points match a circle at steps 1 to 3, a wedge of three 2-spheres at step 4, and a 5-sphere at step 5',
      rb[1] == rb[2] == rb[3] == [1, 1] and rb[4] == [1, 0, 3] and rb[5] == [1, 0, 0, 0, 0, 1], 'Betti numbers mod 2 by scale k = 1..5: %s' % rb)

r13 = trim(betti_mod(rips_circulant(13, 5), 2))
r13b = trim(betti_mod(rips_circulant(13, 4), 2))
check('V5 for 13 points the scale 5/13 lies between 1/3 and 2/5 and the complex is a 3-sphere', r13 == [1, 0, 0, 1] and r13b == [1, 1], 'Betti numbers at scales 4 and 5: %s, %s' % (r13b, r13))

angs = sorted(random.uniform(0, 2 * PI) for _ in range(16))
pts = [(math.cos(a), math.sin(a)) for a in angs]
gaps = [angs[i + 1] - angs[i] for i in range(15)] + [angs[0] + 2 * PI - angs[-1]]
maxchord = 2 * math.sin(max(gaps) / 2)


def rips_points(r):
    n = len(pts)
    adj = [[math.hypot(pts[i][0] - pts[j][0], pts[i][1] - pts[j][1]) <= r for j in range(n)] for i in range(n)]
    F = [[i] for i in range(n)] + [[i, j] for i in range(n) for j in range(i + 1, n) if adj[i][j]]
    F += [[i, j, k] for i in range(n) for j in range(i + 1, n) for k in range(j + 1, n) if adj[i][j] and adj[i][k] and adj[j][k]]
    F += [[i, j, k, l] for i in range(n) for j in range(i + 1, n) for k in range(j + 1, n) for l in range(k + 1, n)
          if adj[i][j] and adj[i][k] and adj[j][k] and adj[i][l] and adj[j][l] and adj[k][l]]
    return betti_mod(Cx(F), 2)[:2]


rmid = max(maxchord + 0.03, 1.2)
bs = {r: rips_points(r) for r in (0.15, rmid, 1.9)}
check('V6 a random sample of 16 points on the circle: the Rips complex has the Betti numbers (1,1) of the circle from the largest gap up to about sqrt 3, and not outside',
      rmid < 1.7 and bs[rmid] == [1, 1] and bs[0.15][0] > 1 and bs[1.9] == [1, 0], 'largest gap (chord) %.3f; (b0,b1) at r = 0.15, %.2f, 1.9: %s, %s, %s' % (maxchord, rmid, bs[0.15], bs[rmid], bs[1.9]))

# --- V7: stability of persistence (own generator)
def persistence0(f):
    """sublevel-set persistence in degree 0 of a function on the vertices of a cycle graph: finite pairs (birth, death)"""
    n = len(f)
    order = sorted(range(n), key=lambda i: f[i])
    parent = {}
    birth = {}
    pairs = []

    def find(i):
        while parent[i] != i:
            parent[i] = parent[parent[i]]
            i = parent[i]
        return i

    for v in order:
        parent[v] = v
        birth[v] = f[v]
        for u in ((v - 1) % n, (v + 1) % n):
            if u in parent:
                ru, rv = find(u), find(v)
                if ru != rv:
                    old, young = (ru, rv) if birth[ru] <= birth[rv] else (rv, ru)
                    if f[v] > birth[young]:
                        pairs.append((birth[young], f[v]))
                    parent[young] = old
    return pairs


def bottleneck(D1, D2):
    """bottleneck distance between two finite diagrams, with the diagonal; sup norm in the plane"""
    n1, n2 = len(D1), len(D2)
    cand = {0.0}
    for p in D1:
        cand.add((p[1] - p[0]) / 2)
        for q in D2:
            cand.add(max(abs(p[0] - q[0]), abs(p[1] - q[1])))
    for q in D2:
        cand.add((q[1] - q[0]) / 2)
    cand = sorted(cand)

    def feasible(delta):
        # left: points of D1, then diagonal copies of the points of D2; right: points of D2, then diagonal copies of D1
        NL = n1 + n2
        adj = [[] for _ in range(NL)]
        for i, p in enumerate(D1):
            for j, q in enumerate(D2):
                if max(abs(p[0] - q[0]), abs(p[1] - q[1])) <= delta + 1e-12:
                    adj[i].append(j)
            if (p[1] - p[0]) / 2 <= delta + 1e-12:
                adj[i].append(n2 + i)
        for j, q in enumerate(D2):
            if (q[1] - q[0]) / 2 <= delta + 1e-12:
                adj[n1 + j].append(j)
            adj[n1 + j].extend(range(n2, n2 + n1))
        match = {}

        def aug(u, seen):
            for v in adj[u]:
                if v in seen:
                    continue
                seen.add(v)
                if v not in match or aug(match[v], seen):
                    match[v] = u
                    return True
            return False

        return all(aug(u, set()) for u in range(NL))

    lo_, hi_ = 0, len(cand) - 1
    while lo_ < hi_:
        md = (lo_ + hi_) // 2
        if feasible(cand[md]):
            hi_ = md
        else:
            lo_ = md + 1
    return cand[lo_]


rg7 = random.Random(20261123)
ratio = 0.0
changed = 0
ok_st = True
for _ in range(60):
    n_ = 40
    f = [rg7.gauss(0, 1) for _ in range(n_)]
    # smooth a little so that the diagrams have bars of several lengths
    f = [(f[i - 1] + 2 * f[i] + f[(i + 1) % n_]) / 4 for i in range(n_)]
    eps_ = rg7.uniform(0.02, 0.3)
    g_ = [a + rg7.uniform(-eps_, eps_) for a in f]
    sup = max(abs(a - b) for a, b in zip(f, g_))
    D1, D2 = persistence0(f), persistence0(g_)
    dB = bottleneck(D1, D2)
    ok_st = ok_st and dB <= sup + 1e-12 and abs(min(f) - min(g_)) <= sup + 1e-12
    ratio = max(ratio, dB / sup)
    changed += 1 if len(D1) != len(D2) else 0
check('V7 stability: the persistence diagram of a function moves by at most the sup-norm of a perturbation, in the bottleneck distance, although the number of bars changes',
      ok_st and changed > 0, '60 random functions on a cycle of 40 vertices: largest ratio of bottleneck distance to perturbation %.3f; the number of bars changed in %d cases' % (ratio, changed))

sec('3. Counts')


def voronoi_junctions(G, K):
    sites = [(random.random(), random.random()) for _ in range(K)]
    lab = [[min(range(K), key=lambda s: (sites[s][0] - i / G) ** 2 + (sites[s][1] - j / G) ** 2) for j in range(G + 1)] for i in range(G + 1)]
    left = {lab[0][j] for j in range(G + 1)}
    right = {lab[G][j] for j in range(G + 1)}
    bottom = {lab[i][0] for i in range(G + 1)}
    top = {lab[i][G] for i in range(G + 1)}
    if (left & right) or (bottom & top):
        return None
    return sum(1 for i in range(G) for j in range(G) if len({lab[i][j], lab[i + 1][j], lab[i][j + 1], lab[i + 1][j + 1]}) >= 3)


vj = [v for v in (voronoi_junctions(60, 14) for _ in range(60)) if v is not None]
check('N1 Lebesgue: a partition of the square into regions none of which joins opposite sides has a point where three regions meet',
      len(vj) >= 30 and min(vj) >= 1, '%d random nearest-prototype classifiers with 14 classes: between %d and %d triple junctions' % (len(vj), min(vj), max(vj)))


def voronoi3(G, K):
    sites = [(random.random(), random.random(), random.random()) for _ in range(K)]
    lab = [[[min(range(K), key=lambda s: (sites[s][0] - i / G) ** 2 + (sites[s][1] - j / G) ** 2 + (sites[s][2] - k / G) ** 2) for k in range(G + 1)] for j in range(G + 1)] for i in range(G + 1)]
    faces = [({lab[0][j][k] for j in range(G + 1) for k in range(G + 1)}, {lab[G][j][k] for j in range(G + 1) for k in range(G + 1)}),
             ({lab[i][0][k] for i in range(G + 1) for k in range(G + 1)}, {lab[i][G][k] for i in range(G + 1) for k in range(G + 1)}),
             ({lab[i][j][0] for i in range(G + 1) for j in range(G + 1)}, {lab[i][j][G] for i in range(G + 1) for j in range(G + 1)})]
    if any(a & b for a, b in faces):
        return None
    return sum(1 for i in range(G) for j in range(G) for k in range(G)
               if len({lab[i + a][j + b][k + c] for a in (0, 1) for b in (0, 1) for c in (0, 1)}) >= 4)


v3 = [v for v in (voronoi3(18, 40) for _ in range(8)) if v is not None]
check('N2 in dimension three the same holds with four regions', len(v3) >= 3 and min(v3) >= 1, '%d classifiers with 40 classes on the cube: between %d and %d quadruple junctions' % (len(v3), min(v3), max(v3)))


def fmap(p):
    x, y, z = p
    q = (0.2 + 0.5 * y + 0.3 * z * z, 0.1 + 0.6 * z + 0.2 * x * y, 0.3 + 0.4 * x + 0.1 * y * y)
    s = sum(q)
    return tuple(a / s for a in q)


def door_walk(n):
    def pt(i, j):
        return ((n - i - j) / n, i / n, j / n)
    cache = {}
    def lab(v):
        if v not in cache:
            p = pt(*v)
            q = fmap(p)
            cache[v] = next((k for k in range(3) if p[k] > 0 and q[k] <= p[k]), max(range(3), key=lambda k: p[k]))
        return cache[v]
    def cells_of_edge(a, b):
        (i1, j1), (i2, j2) = sorted([a, b])
        out = []
        for c in [(i1 + i2 - j1 - j2 + 0, 0)]:
            pass
        # third vertices completing a grid triangle with edge ab
        cands = []
        di, dj = i2 - i1, j2 - j1
        if (di, dj) == (1, 0):
            cands = [(i1, j1 + 1), (i2, j2 - 1)]
        elif (di, dj) == (0, 1):
            cands = [(i1 + 1, j1), (i1 - 1, j2)]
        else:  # (1,-1)
            cands = [(i1, j1 - 1), (i2, j1)]
        return [c for c in cands if c[0] >= 0 and c[1] >= 0 and c[0] + c[1] <= n]
    best = None
    for i in range(n):
        a, b = (i, 0), (i + 1, 0)
        if {lab(a), lab(b)} != {0, 1}:
            continue
        steps = 0
        edge = (a, b)
        third = cells_of_edge(a, b)[0]
        prev_third = None
        while True:
            steps += 1
            tri = (edge[0], edge[1], third)
            if lab(third) == 2:
                best = steps if best is None else min(best, steps)
                break
            # leave through the other 01-edge
            other = edge[0] if lab(edge[0]) != lab(third) else edge[1]
            new_edge = (other, third)
            nxt = [c for c in cells_of_edge(*new_edge) if c not in tri]
            if not nxt:
                break
            edge, third = new_edge, nxt[0]
    return best


walks = {n: door_walk(n) for n in (16, 32, 64, 128)}
check('N3 finding a complete Sperner cell by walking through doors takes a number of steps proportional to the side of the grid, not to the number of cells',
      all(walks[n] is not None for n in walks) and walks[128] < 6 * 128 and 1.5 < walks[128] / walks[64] < 2.6,
      'steps %s for n = 16, 32, 64, 128; cells %s' % ([walks[n] for n in sorted(walks)], [n * n for n in sorted(walks)]))


def circle_fixed(d, eps, g, n=6000):
    h = lambda t: (d - 1) * t + eps * g(t)
    tot = cnt = 0
    for m in range(-abs(d) - 6, abs(d) + 7):
        prev = h(0.0) - 2 * PI * m
        for i in range(1, n + 1):
            cur = h(2 * PI * i / n) - 2 * PI * m
            if prev == 0 or prev * cur < 0:
                cnt += 1
                tot += -1 if cur > prev else 1
            prev = cur
    return tot, cnt


okcf = True
info = []
for d in (-2, 0, 1, 2, 3):
    for eps in (0.3, 2.0):
        g = trig_poly(4)
        s, c = circle_fixed(d, eps, g)
        okcf = okcf and s == 1 - d and c >= abs(1 - d) and (c - abs(1 - d)) % 2 == 0
        if eps == 2.0:
            info.append('d=%d: %d points, signed %d' % (d, c, s))
check('N4 fixed points of a circle map of degree d, counted with index, number 1 - d; a perturbed ring attractor (d = 1) has an even number, half of them stable',
      okcf, '; '.join(info))


def torus_zeros(eps):
    def v(t):
        return [math.sin(t[0]) + eps * math.sin(t[1] + 0.4), math.sin(t[1]) + eps * math.cos(t[0] - t[1])]
    found = []
    for i in range(16):
        for j in range(16):
            t = [2 * PI * (i + 0.37) / 16, 2 * PI * (j + 0.61) / 16]
            for _ in range(50):
                f0 = v(t)
                h = 1e-6
                a = [(p - q) / (2 * h) for p, q in zip(v([t[0] + h, t[1]]), v([t[0] - h, t[1]]))]
                b = [(p - q) / (2 * h) for p, q in zip(v([t[0], t[1] + h]), v([t[0], t[1] - h]))]
                det = a[0] * b[1] - a[1] * b[0]
                if abs(det) < 1e-12:
                    break
                t = [t[0] - (f0[0] * b[1] - f0[1] * b[0]) / det, t[1] - (a[0] * f0[1] - a[1] * f0[0]) / det]
            if vnorm(v(t)) < 1e-10:
                t = [x % (2 * PI) for x in t]
                if not any(min(abs(t[0] - s[0]), 2 * PI - abs(t[0] - s[0])) + min(abs(t[1] - s[1]), 2 * PI - abs(t[1] - s[1])) < 1e-5 for s, _ in found):
                    h = 1e-6
                    a = [(p - q) / (2 * h) for p, q in zip(v([t[0] + h, t[1]]), v([t[0] - h, t[1]]))]
                    b = [(p - q) / (2 * h) for p, q in zip(v([t[0], t[1] + h]), v([t[0], t[1] - h]))]
                    found.append((t, 1 if a[0] * b[1] - a[1] * b[0] > 0 else -1))
    return found


tz = {eps: torus_zeros(eps) for eps in (0.0, 0.3, 0.6)}
check('N5 the zeros of a drift field on a torus attractor have total index 0: in three examples a source, a sink and two saddles',
      all(sum(s for _, s in z) == 0 and len(z) >= 4 for z in tz.values()), 'zeros found for three perturbations: %s; index sums %s' % ([len(z) for z in tz.values()], [sum(s for _, s in z) for z in tz.values()]))

W1 = [[1.3, -0.4], [0.5, 1.1], [-0.8, 0.9], [0.2, -1.2]]
B1 = [0.1, -0.2, 0.3, 0.05]
W2 = [[0.9, 0.3, -0.5, 0.2], [-0.2, 0.8, 0.6, -0.7]]


def net_curve(t, shift):
    hdn = [math.tanh(W1[i][0] * math.cos(t) + W1[i][1] * math.sin(t) + B1[i]) for i in range(4)]
    return complex(sum(W2[0][i] * hdn[i] for i in range(4)) + shift, sum(W2[1][i] * hdn[i] for i in range(4)))


def net_winding(shift, n=4000):
    tot = 0.0
    prev = net_curve(0.0, shift)
    for i in range(1, n + 1):
        cur = net_curve(2 * PI * i / n, shift)
        tot += cmath.phase(cur / prev)
        prev = cur
    return round(tot / (2 * PI))


w0 = net_winding(0.0)
lo, hi = 0.0, 5.0
assert net_winding(hi) == 0
for _ in range(50):
    mid_ = (lo + hi) / 2
    if net_winding(mid_) == w0:
        lo = mid_
    else:
        hi = mid_
bstar = (lo + hi) / 2
mn = min(abs(net_curve(2 * PI * i / 20000, bstar)) for i in range(20000))


def signed_preimages(shift, alpha, n=4000):
    tot = 0
    prev = cmath.phase(net_curve(0.0, shift) * cmath.exp(-1j * alpha))
    for i in range(1, n + 1):
        cur = cmath.phase(net_curve(2 * PI * i / n, shift) * cmath.exp(-1j * alpha))
        if prev * cur < 0 and abs(prev - cur) < PI:
            tot += 1 if cur > prev else -1
        prev = cur
    return tot


sp = [signed_preimages(0.0, a) for a in (0.3, 2.0, -1.7)]
check('N6 the degree of a normalized network output is the signed number of preimages of any direction, and it changes only when the output passes through zero',
      abs(w0) == 1 and all(s == w0 for s in sp) and net_winding(bstar - 1e-3) == w0 and net_winding(bstar + 1e-3) == 0 and mn < 1e-3,
      'degree %d; signed preimages of three directions %s; degree drops to 0 at bias %.4f, where the smallest output norm is %.1e' % (w0, sp, bstar, mn))


# --- N7: zeros of odd networks (own generator)
rg12 = random.Random(20261124)
hist = {}
ok_odd = True
for _ in range(200):
    units = [(rg12.gauss(0, 2), rg12.gauss(0, 2), rg12.gauss(0, 1)) for _ in range(6)]
    fo = lambda t: sum(c_ * math.tanh(a_ * math.cos(t) + b_ * math.sin(t)) for a_, b_, c_ in units)
    M_ = 20000
    vals_ = [fo(2 * PI * (i + 0.5) / M_) for i in range(M_)]
    z_ = sum(1 for i in range(M_) if vals_[i - 1] * vals_[i] < 0)
    hist[z_] = hist.get(z_, 0) + 1
    ok_odd = ok_odd and z_ % 4 == 2
# Each tanh is bounded by 1 in absolute value, so this is a global lower bound.
biased_lower_bound = 10.0 - sum(abs(weight) for _, _, weight in units)
check('N7 the sampled sign crossings of the scalar odd networks number 2 modulo 4',
      ok_odd and biased_lower_bound > 0,
      '200 random networks with six tanh units: sign crossings on the unit circle %s; with output bias 10 the last output is at least %.4f' % (sorted(hist.items()), biased_lower_bound))

footer()
