#!/usr/bin/env python3
# verify-topology.py
# Companion script to "Algebraic and Differential Topology in Higher Categories" (Higher Categorical Semantics, 2026; byline Anonymous).
# 63 computational checks of the numerical and finite statements in the book. Python standard library only; fixed seeds.
# Usage: python3 verify-topology.py      (under half a minute; exit status 0 iff every check passes)
# Homology is computed exactly: Smith normal form over the integers, Gaussian elimination over prime fields.
# 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: PART ONE ########################
random.seed(20261119)
T7, RP2, KB, MB, ICO = torus7(), rp2(), klein(), moebius(), icosahedron()
S2 = simplex_boundary(2)
NAMED = [('sphere', S2), ('icosahedron', ICO), ('torus', T7), ('projective plane', RP2), ('Klein bottle', KB), ('Moebius band', MB)]


def rand_complex(nv=7, nf=6, dmax=3):
    return Cx([random.sample(range(nv), random.randint(1, dmax + 1)) for _ in range(nf)])


sec('1. Complexes as presheaves')
fv = {nm: K.fvec() for nm, K in NAMED}
okpm = all(is_pseudomanifold(K, closed=(nm != 'Moebius band')) for nm, K in NAMED)
check('C1 the six model complexes are pseudo-manifolds with f-vectors (4,6,4), (12,30,20), (7,21,14), (6,15,10), (16,48,32), (5,10,5)',
      okpm and fv['sphere'] == [4, 6, 4] and fv['icosahedron'] == [12, 30, 20] and fv['torus'] == [7, 21, 14] and fv['projective plane'] == [6, 15, 10]
      and fv['Klein bottle'] == [16, 48, 32] and fv['Moebius band'] == [5, 10, 5],
      'Euler characteristics %s' % ', '.join('%s %d' % (nm, K.chi()) for nm, K in NAMED))


def affinely_independent(pts):
    rows = [[Fr(a) - Fr(b) for a, b in zip(p, pts[0])] for p in pts[1:]]
    return rank_exact(rows) == len(pts) - 1


def moment(t, n):
    return [Fr(t) ** k for k in range(1, n + 1)]


okgp = all(affinely_independent([moment(t, 5) for t in c]) for c in itertools.combinations(range(1, 8), 6))
okgp3 = all(affinely_independent([moment(t, 3) for t in c]) for c in itertools.combinations(range(1, 8), 4))
check('C2 seven points on the moment curve of R^5 are in general position: every 2-complex on them is realized (dimension 2r+1)',
      okgp and okgp3, 'all 7 six-point subsets affinely independent in R^5; all 35 four-point subsets in R^3')


def nerve_of_stars(K):
    verts = [x[0] for x in K.S[0]]
    stars = {v: set(x for d in K.S for x in K.S[d] if v in x) for v in verts}
    F = []
    for k in range(1, K.dim + 3):
        for c in itertools.combinations(verts, k):
            if set.intersection(*[stars[v] for v in c]):
                F.append(c)
    return Cx(F)


oknerve = all(nerve_of_stars(K).S == K.S for _, K in NAMED)
check('C3 the nerve of the cover of a complex by its open vertex stars is the complex itself', oknerve, 'checked on the six model complexes')


def shuffles(p, q):
    """number of non-degenerate (p+q)-simplices of the product of a p-simplex and a q-simplex"""
    cnt = 0
    pts = list(itertools.product(range(p + 1), range(q + 1)))
    for c in itertools.combinations(pts, p + q + 1):
        if all(c[i][0] <= c[i + 1][0] and c[i][1] <= c[i + 1][1] for i in range(p + q)):
            cnt += 1
    return cnt


sh = [shuffles(1, 1), shuffles(2, 1), shuffles(2, 2), shuffles(3, 2)]
check('C4 the product of a p-simplex and a q-simplex has binomial(p+q,p) top simplices (the shuffles)', sh == [2, 3, 6, 10], 'counts %s' % sh)

nd = []
for n in (1, 2, 3, 4):
    # non-degenerate simplices of the nerve of the poset of non-empty subsets of an n-set = simplices of sd(simplex)
    K, _ = sd(Cx([list(range(n + 1))]))
    nd.append(K.n(n))
check('C5 the barycentric subdivision of an n-simplex has (n+1)! top simplices, one for each maximal flag of faces', nd == [2, 6, 24, 120], 'counts %s' % nd)

sec('2. Homology as a functor')
okdd = True
for _, K in NAMED + [('r', rand_complex()) for _ in range(10)]:
    for d in range(2, K.dim + 1):
        P = mat_mul(K.bd(d - 1), K.bd(d))
        okdd = okdd and all(v == 0 for r in P for v in r)
check('H1 the boundary of a boundary vanishes', okdd, 'six model complexes and ten random ones')

hom = {nm: homology(K) for nm, K in NAMED}
check('H2 Betti numbers and torsion by Smith normal form: sphere (1,0,1); torus (1,2,1); projective plane Z, Z/2, 0; Klein bottle Z, Z+Z/2, 0; Moebius band (1,1,0)',
      hom['sphere'] == [(1, []), (0, []), (1, [])] and hom['icosahedron'] == [(1, []), (0, []), (1, [])] and hom['torus'] == [(1, []), (2, []), (1, [])]
      and hom['projective plane'] == [(1, []), (0, [2]), (0, [])] and hom['Klein bottle'] == [(1, []), (1, [2]), (0, [])] and hom['Moebius band'] == [(1, []), (1, []), (0, [])],
      '; '.join('%s %s' % (nm, hom[nm]) for nm, _ in NAMED[2:5]))

okep = True
for K in [K for _, K in NAMED] + [rand_complex(8, 9, 3) for _ in range(20)]:
    okep = okep and K.chi() == sum((-1) ** d * b for d, b in enumerate(bettis(K)))
check('H3 Euler-Poincare: the alternating sum of the numbers of simplices is the alternating sum of the Betti numbers', okep, '6 model and 20 random complexes')

b2, b3 = betti_mod(RP2, 2), betti_mod(RP2, 3)
k2, k3 = betti_mod(KB, 2), betti_mod(KB, 3)
okuc = True
for K in [RP2, KB, T7] + [rand_complex(8, 9, 3) for _ in range(10)]:
    h = homology(K)
    for p in (2, 3):
        bp = betti_mod(K, p)
        for d in range(K.dim + 1):
            tor = sum(1 for t in h[d][1] if t % p == 0) + (sum(1 for t in h[d - 1][1] if t % p == 0) if d > 0 else 0)
            okuc = okuc and bp[d] == h[d][0] + tor
check('H4 mod-p Betti numbers see torsion: projective plane (1,1,1) mod 2 and (1,0,0) mod 3; Klein bottle (1,2,1) mod 2; universal coefficients',
      b2 == [1, 1, 1] and b3 == [1, 0, 0] and k2 == [1, 2, 1] and k3 == [1, 1, 0] and okuc, 'the Euler characteristic is 1, 1, 0, 0 in the four cases')


def components(K):
    par = {x[0]: x[0] for x in K.S[0]}
    def find(a):
        while par[a] != a:
            par[a] = par[par[a]]
            a = par[a]
        return a
    for e in K.S.get(1, []):
        par[find(e[0])] = find(e[1])
    return len({find(a) for a in par})


okh0 = all(bettis(K)[0] == components(K) for K in [rand_complex(10, 5, 2) for _ in range(30)])
check('H5 the zero-dimensional Betti number is the number of components', okh0, '30 random complexes')

okcone = True
for _, K in NAMED:
    CK, _ = cone(K)
    okcone = okcone and homology(CK) == [(1, [])] + [(0, [])] * CK.dim
ST = suspension(T7)
SR = suspension(RP2)
check('H6 a cone is acyclic and suspension shifts homology by one: the suspension of the projective plane has H_2 = Z/2',
      okcone and bettis(ST) == [1, 0, 2, 1] and homology(SR) == [(1, []), (0, []), (0, [2]), (0, [])], 'suspended torus %s' % bettis(ST))

okmv = True
for _ in range(30):
    fa = [random.sample(range(8), random.randint(1, 4)) for _ in range(5)]
    fb = [random.sample(range(8), random.randint(1, 4)) for _ in range(5)]
    A, B, U = Cx(fa), Cx(fb), Cx(fa + fb)
    inter = [x for d in A.S for x in A.S[d] if d in B.S and x in B.idx[d]]
    okmv = okmv and U.chi() == A.chi() + B.chi() - (Cx(inter).chi() if inter else 0)
check('H7 the Euler characteristic is additive: chi(A u B) = chi(A) + chi(B) - chi(A n B)', okmv, '30 random pairs')

G2, G3 = grid_torus(3, 2), grid_torus(4, 3)
bg3 = [betti_mod(G3, p) for p in (2, 3, BIGP)]
check('H8 Kunneth on product triangulations: the 2-torus has Betti numbers (1,2,1) and the 3-torus (1,3,3,1), over every field tried',
      is_pseudomanifold(G2) and is_pseudomanifold(G3) and bettis(G2) == [1, 2, 1] and all(b == [1, 3, 3, 1] for b in bg3),
      '3-torus on %d vertices with f-vector %s' % (G3.n(0), G3.fvec()))

sec('3. Invariance: subdivision, cones, approximation')
oksd = True
for nm, K in NAMED[2:5]:
    SK, _ = sd(K)
    oksd = oksd and homology(SK) == homology(K)
SRP, numrp = sd(RP2)
check('I1 barycentric subdivision does not change the homology groups, torsion included', oksd, 'subdivided projective plane: f-vector %s, homology %s' % (SRP.fvec(), homology(SRP)))


def last_vertex_map(K, num):
    inv_ = {i: x for x, i in num.items()}
    return {i: max(inv_[i]) for i in inv_}


okapp = True
for nm, K in NAMED[2:5]:
    SK, num = sd(K)
    vm = last_vertex_map(K, num)
    for d in range(1, K.dim + 1):
        okapp = okapp and mat_eq(mat_mul(K.bd(d), chain_map(SK, K, vm, d)), mat_mul(chain_map(SK, K, vm, d - 1), SK.bd(d)))
    # rank of the induced map on top homology mod 2 equals the Betti number
    d = K.dim
    Zs = nullspace(SK.bd(d), SK.n(d))
    img = [[sum(chain_map(SK, K, vm, d)[i][k] * z[k] for k in range(SK.n(d))) for i in range(K.n(d))] for z in Zs]
    okapp = okapp and (len(independent_extend([], img)) == bettis(K)[d])
check('I2 the last-vertex map from the subdivision back to the complex is a simplicial approximation of the identity: a chain map, onto in top homology',
      okapp, 'torus, projective plane, Klein bottle')

okcc = True
for nm, K in NAMED[:4]:
    CK, apex = cone(K)
    for d in range(0, CK.dim):
        n = CK.n(d)
        D = [[0] * n for _ in range(CK.n(d + 1))]
        for j, x in enumerate(CK.S[d]):
            if apex not in x:
                D[CK.idx[d + 1][x + (apex,)]][j] = (-1) ** (d + 1)
        lhs = mat_mul(CK.bd(d + 1), D)
        if d > 0:
            Dm = [[0] * CK.n(d - 1) for _ in range(n)]
            for j, x in enumerate(CK.S[d - 1]):
                if apex not in x:
                    Dm[CK.idx[d][x + (apex,)]][j] = (-1) ** d
            lhs = [[a + b for a, b in zip(r, q)] for r, q in zip(lhs, mat_mul(Dm, CK.bd(d)))]
            okcc = okcc and mat_eq(lhs, [[int(i == j) for j in range(n)] for i in range(n)])
        else:
            ai = CK.idx[0][(apex,)]
            okcc = okcc and mat_eq(lhs, [[int(i == j) - int(i == ai) for j in range(n)] for i in range(n)])
check('I3 the conic construction is a chain contraction: boundary of the cone on c plus the cone on the boundary of c is c', okcc,
      'in degree 0 the right-hand side is c minus (sum of coefficients) times the apex')


def mesh_after(m):
    tri = [[(Fr(0), Fr(0)), (Fr(1), Fr(0)), (Fr(0), Fr(1))]]
    for _ in range(m):
        new = []
        for t in tri:
            for perm in itertools.permutations(t):
                new.append([tuple(sum(p[k] for p in perm[:j]) / j for k in range(2)) for j in (1, 2, 3)])
        tri = new
    return max(math.sqrt(float((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)) for t in tri for a, b in itertools.combinations(t, 2)), len(tri)


meshes = [mesh_after(m) for m in range(0, 5)]
ratios = [meshes[i + 1][0] / meshes[i][0] for i in range(4)]
check('I4 each barycentric subdivision of a triangle multiplies the mesh by at most 2/3 and the number of triangles by 6',
      all(r <= 2 / 3 + 1e-12 for r in ratios) and [m[1] for m in meshes] == [1, 6, 36, 216, 1296],
      'mesh %s; ratios %s' % (', '.join('%.4f' % m[0] for m in meshes), ', '.join('%.4f' % r for r in ratios)))


def simplicial_degree(d, N):
    """degree of the simplicial approximation of z -> z^d from an N-gon to a triangle"""
    def img(j):
        ang = (d * 2 * PI * j / N) % (2 * PI)
        return int(ang // (2 * PI / 3)) % 3
    tot = 0
    for j in range(N):
        a, b = img(j), img((j + 1) % N)
        if (a, b) == (2, 0):
            tot += 1
        elif (a, b) == (0, 2):
            tot -= 1
    return tot


degs = {d: simplicial_degree(d, 60) for d in (-2, -1, 0, 1, 2, 3)}
fail = simplicial_degree(3, 8)
check('I5 a simplicial approximation of z -> z^d from a 60-gon to a triangle has degree d; on an octagon the same vertex rule gives degree 2 for d = 3',
      all(degs[d] == d for d in degs) and fail == 2, 'degrees %s; octagon, d = 3: degree %s' % (degs, fail))

sec('4. Sperner, Brouwer, dimension')


def sperner_grid(n):
    """triangular grid of side n: vertices (i,j), i+j<=n; returns list of (triangle, orientation)"""
    tris = []
    for i in range(n):
        for j in range(n - i):
            tris.append(((i, j), (i + 1, j), (i, j + 1)))
            if i + j < n - 1:
                tris.append(((i + 1, j), (i + 1, j + 1), (i, j + 1)))
    return tris


def sperner_label(n):
    lab = {}
    for i in range(n + 1):
        for j in range(n + 1 - i):
            k = n - i - j
            allowed = [c for c, v in ((0, k), (1, i), (2, j)) if v > 0]
            lab[(i, j)] = random.choice(allowed)
    return lab


def signed_rainbow(tris, lab):
    tot = cnt = 0
    for t in tris:
        l = [lab[v] for v in t]
        if sorted(l) == [0, 1, 2]:
            cnt += 1
            tot += perm_sign(l)
    return cnt, tot


okS = True
counts = []
for _ in range(200):
    n = 12
    lab = sperner_label(n)
    c, s = signed_rainbow(sperner_grid(n), lab)
    counts.append(c)
    okS = okS and c % 2 == 1 and s == 1
check('S1 Sperner: every admissible labelling of a subdivided triangle has an odd number of complete cells, and their signed count is +1',
      okS, '200 random labellings of the grid of side 12: between %d and %d complete cells' % (min(counts), max(counts)))

okE = True
for _ in range(200):
    n = 12
    lab = sperner_label(n)
    e = sum((1 if (lab[(i, 0)], lab[(i + 1, 0)]) == (0, 1) else -1 if (lab[(i, 0)], lab[(i + 1, 0)]) == (1, 0) else 0) for i in range(n))
    okE = okE and e == 1
check('S2 the signed count is the degree of the labelling on the boundary: on the side labelled 0 and 1 the signed number of 01-edges is +1', okE, '200 labellings')


def sperner3(m):
    """m-fold barycentric subdivision of a tetrahedron with coordinates; random Sperner labels"""
    tets = [[tuple(Fr(int(i == k)) for k in range(4)) for i in range(4)]]
    for _ in range(m):
        new = []
        for t in tets:
            for perm in itertools.permutations(t):
                new.append([tuple(sum(p[k] for p in perm[:j]) / j for k in range(4)) for j in (1, 2, 3, 4)])
        tets = new
    lab = {}
    for t in tets:
        for v in t:
            if v not in lab:
                lab[v] = random.choice([k for k in range(4) if v[k] > 0])
    cnt = tot = 0
    for t in tets:
        l = [lab[v] for v in t]
        if sorted(l) == [0, 1, 2, 3]:
            M = [[Fr(1)] + list(v[:3]) for v in t]
            # orientation of the cell times the sign of the labelling
            rows = [[a - b for a, b in zip(v[:3], t[0][:3])] for v in t[1:]]
            det = (rows[0][0] * (rows[1][1] * rows[2][2] - rows[1][2] * rows[2][1]) - rows[0][1] * (rows[1][0] * rows[2][2] - rows[1][2] * rows[2][0])
                   + rows[0][2] * (rows[1][0] * rows[2][1] - rows[1][1] * rows[2][0]))
            cnt += 1
            tot += (1 if det > 0 else -1) * perm_sign(l)
    return cnt, tot, len(tets)


r3 = [sperner3(2) for _ in range(20)]
ref = r3[0][1]
check('S3 Sperner in dimension three: an odd number of complete cells, with signed count of absolute value one',
      all(c % 2 == 1 and abs(s) == 1 and s == ref for c, s, _ in r3), '20 labellings of the second subdivision of a tetrahedron (%d cells): %d to %d complete cells' % (r3[0][2], min(c for c, _, _ in r3), max(c for c, _, _ in r3)))


def fmap(p):
    """a continuous self-map of the standard triangle (barycentric coordinates)"""
    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 sperner_fixed(n):
    def pt(i, j):
        return ((n - i - j) / n, i / n, j / n)
    def lab(i, j):
        p = pt(i, j)
        q = fmap(p)
        for k in range(3):
            if p[k] > 0 and q[k] <= p[k]:
                return k
        return max(range(3), key=lambda k: p[k])
    best = None
    for t in sperner_grid(n):
        if sorted(lab(*v) for v in t) == [0, 1, 2]:
            c = tuple(sum(pt(*v)[k] for v in t) / 3 for k in range(3))
            e = max(abs(a - b) for a, b in zip(c, fmap(c)))
            best = e if best is None else min(best, e)
    return best


errs = [sperner_fixed(n) for n in (8, 32, 128)]
check('S4 Brouwer from Sperner: a complete cell of mesh 1/n contains a point moved by O(1/n)', errs[0] > errs[1] > errs[2] and errs[2] < 0.01,
      'displacement at the centre of a complete cell: %s for n = 8, 32, 128' % ', '.join('%.4f' % e for e in errs))


def hex_winner(n):
    col = [[random.random() < 0.5 for _ in range(n)] for _ in range(n)]
    nb = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, -1), (-1, 1)]
    def connects(c, vertical):
        seen = set()
        stack = [(0, j) for j in range(n) if col[0][j] == c] if vertical else [(i, 0) for i in range(n) if col[i][0] == c]
        while stack:
            i, j = stack.pop()
            if (i, j) in seen:
                continue
            seen.add((i, j))
            if (vertical and i == n - 1) or (not vertical and j == n - 1):
                return True
            for a, b in nb:
                u, v = i + a, j + b
                if 0 <= u < n and 0 <= v < n and col[u][v] == c and (u, v) not in seen:
                    stack.append((u, v))
        return False
    return connects(True, True), connects(False, False)


hx = [hex_winner(9) for _ in range(300)]
check('S5 the Hex theorem (equivalent to Brouwer in the plane): a filled board has exactly one winner', all(a != b for a, b in hx),
      '300 random fillings of the 9 x 9 board; first player wins %d' % sum(a for a, _ in hx))


def order_of_cover(kind, n=6):
    """largest number of closed tiles meeting at a point, for a tiling of the plane by unit squares"""
    best = 0
    for i in range(2 * n):
        for j in range(2 * n):
            p = (i / 2, j / 2)
            cnt = 0
            for a in range(-1, n + 1):
                for b in range(-1, n + 1):
                    off = 0.5 * (b % 2) if kind == 'brick' else 0.0
                    if a + off <= p[0] <= a + off + 1 and b <= p[1] <= b + 1:
                        cnt += 1
            best = max(best, cnt)
    return best


check('S6 Lebesgue: a cover of the plane by small closed sets has order at least 3; the brick pattern attains 3, the square grid has 4',
      order_of_cover('brick') == 3 and order_of_cover('grid') == 4, 'orders %d and %d' % (order_of_cover('brick'), order_of_cover('grid')))

sec('5. Homotopy and the cylinder')
okpr = True
for nm, K in NAMED[1:5]:
    PK, N = prism(K)
    for d in range(0, K.dim + 1):
        P = [[0] * K.n(d) for _ in range(PK.n(d + 1))]
        for j, x in enumerate(K.S[d]):
            for i in range(d + 1):
                P[PK.idx[d + 1][x[:i + 1] + tuple(v + N for v in x[i:])]][j] = (-1) ** i
        i0 = chain_map(K, PK, {x[0]: x[0] for x in K.S[0]}, d)
        i1 = chain_map(K, PK, {x[0]: x[0] + N for x in K.S[0]}, d)
        lhs = mat_mul(PK.bd(d + 1), P)
        if d > 0:
            Pm = [[0] * K.n(d - 1) for _ in range(PK.n(d))]
            for j, x in enumerate(K.S[d - 1]):
                for i in range(d):
                    Pm[PK.idx[d][x[:i + 1] + tuple(v + N for v in x[i:])]][j] = (-1) ** i
            lhs = [[a + b for a, b in zip(r, q)] for r, q in zip(lhs, mat_mul(Pm, K.bd(d)))]
        okpr = okpr and mat_eq(lhs, mat_sub(i1, i0))
check('P1 the cylindric construction: the prism operator P satisfies dP + Pd = top - bottom', okpr, 'icosahedron, torus, projective plane, Klein bottle')

PR, _ = prism(RP2)
PM, _ = prism(MB)
check('P2 the cylinder on a complex has the homology of the complex, torsion included', homology(PR)[:3] == homology(RP2) and homology(PR)[3] == (0, []) and bettis(PM) == [1, 1, 0, 0],
      'projective plane times interval: %s' % homology(PR))


def choice_map(K, num):
    inv_ = {i: x for x, i in num.items()}
    return {i: random.choice(inv_[i]) for i in inv_}


okcont = True
found = 0
for K in (T7, RP2, MB, ICO):
    SK, num = sd(K)
    for _ in range(3):
        f, g = choice_map(K, num), choice_map(K, num)
        contig = all(tuple(sorted(set(f[a] for a in x) | set(g[a] for a in x))) in K.idx.get(len(set(f[a] for a in x) | set(g[a] for a in x)) - 1, {}) for d in SK.S for x in SK.S[d])
        found += contig
        for d in range(1, K.dim + 1):
            Bd = K.bd(d + 1) if d < K.dim else []
            Bbasis = independent_extend([], [[Fr(v) for v in c] for c in zip(*Bd)]) if Bd and Bd[0] else []
            F, G = chain_map(SK, K, f, d), chain_map(SK, K, g, d)
            for z in nullspace(SK.bd(d), SK.n(d)):
                diff = [sum((F[i][k] - G[i][k]) * z[k] for k in range(SK.n(d))) for i in range(K.n(d))]
                okcont = okcont and not independent_extend(Bbasis, [diff])
check('P3 contiguous simplicial maps induce the same map on homology: any two vertex-choice maps from the subdivision to the complex', okcont and found == 12,
      '%d pairs, all contiguous, on the torus, the projective plane, the Moebius band and the icosahedron' % found)

disc, _ = cone(circle(8))
check('P4 homotopy equivalent polyhedra have the same homology: Moebius band and circle (1,1); disc and point',
      bettis(MB) == [1, 1, 0] and bettis(circle(5)) == [1, 1] and bettis(disc) == [1, 0, 0], 'the band has the Euler characteristic 0 of its core circle')

sec('6. Traces and fixed points')


def automorphisms_affine7():
    out = []
    tri = set(T7.S[2])
    for a in range(1, 7):
        for b in range(7):
            vm = {x: (a * x + b) % 7 for x in range(7)}
            if all(tuple(sorted(vm[v] for v in t)) in tri for t in tri):
                out.append(((a, b), vm))
    return out


AUT = automorphisms_affine7()
okht = all(lefschetz_chain(T7, vm) == lefschetz_hom(T7, vm) for _, vm in AUT)
Ls = sorted(set(lefschetz_chain(T7, vm) for _, vm in AUT))
check('L1 Hopf trace formula: the alternating trace on chains equals the alternating trace on homology', okht,
      '%d affine automorphisms of the 7-vertex torus; Lefschetz numbers occurring: %s' % (len(AUT), Ls))


def has_fixed_simplex(K, vm):
    return any(tuple(sorted(vm[v] for v in x)) == x for d in K.S for x in K.S[d])


okfp = all(has_fixed_simplex(T7, vm) for _, vm in AUT if lefschetz_chain(T7, vm) != 0)
free = [ab for ab, vm in AUT if not has_fixed_simplex(T7, vm)]
check('L2 Lefschetz: a simplicial map with non-zero Lefschetz number fixes a simplex setwise, hence a point; the translations have L = 0 and fix nothing',
      okfp and all(lefschetz_chain(T7, vm) == 0 for ab, vm in AUT if ab in free) and len(free) >= 6, '%d automorphisms without fixed simplex: %s' % (len(free), free[:8]))

check('L3 the Lefschetz number of the identity is the Euler characteristic',
      all(lefschetz_chain(K, {x[0]: x[0] for x in K.S[0]}) == K.chi() == lefschetz_hom(K, {x[0]: x[0] for x in K.S[0]}) for _, K in NAMED), 'six model complexes')


def det2(M):
    return M[0][0] * M[1][1] - M[0][1] * M[1][0]


def torus_fixed(A):
    """number of points x of R^2/Z^2 with Ax = x, by enumeration"""
    B = [[A[0][0] - 1, A[0][1]], [A[1][0], A[1][1] - 1]]
    D = abs(det2(B))
    if D == 0:
        return None
    cnt = 0
    for i in range(D):
        for j in range(D):
            if (B[0][0] * i + B[0][1] * j) % D == 0 and (B[1][0] * i + B[1][1] * j) % D == 0:
                cnt += 1
    return cnt


oktf = True
for _ in range(40):
    A = [[random.randint(-3, 3) for _ in range(2)] for _ in range(2)]
    L = 1 - (A[0][0] + A[1][1]) + det2(A)
    n = torus_fixed(A)
    oktf = oktf and (n is None and L == 0 or n == abs(L))
check('L4 for a linear map of the 2-torus L = 1 - tr A + det A = det(I - A), and the number of fixed points is |L|', oktf, '40 random integer matrices')

CAT = [[2, 1], [1, 1]]
P = [[1, 0], [0, 1]]
per = []
for n in range(1, 9):
    P = mat_mul(P, CAT)
    per.append(torus_fixed(P))
# zeta function (1-t)^2 / (1 - 3t + t^2): log-derivative gives the counts
luc = [2, 3]
while len(luc) < 9:
    luc.append(3 * luc[-1] - luc[-2])
check('L5 periodic points of the cat map: N_n = |det(I - A^n)| = tr(A^n) - 2, giving 1, 5, 16, 45, 121, 320, 841, 2205',
      per == [1, 5, 16, 45, 121, 320, 841, 2205] and per == [luc[n] - 2 for n in range(1, 9)], 'counts %s' % per)

okanti = True
info = []
for n in (1, 2, 3):
    K = cross_sphere(n)
    anti = {x[0]: x[0] ^ 1 for x in K.S[0]}
    Lc = lefschetz_chain(K, anti)
    deg = homology_trace(K, anti, n)
    okanti = okanti and Lc == 0 and deg == (-1) ** (n + 1) and not has_fixed_simplex(K, anti)
    info.append('n=%d: degree %d' % (n, deg))
check('L6 the antipodal map of the n-sphere has degree (-1)^(n+1), Lefschetz number 1 + (-1)^n deg = 0, and no fixed point', okanti, '; '.join(info))


def rel_trace(K, A, vm):
    tot = 0
    for d in range(K.dim + 1):
        for x in K.S[d]:
            if d in A.S and x in A.idx[d]:
                continue
            y = [vm[v] for v in x]
            if len(set(y)) == d + 1 and tuple(sorted(y)) == x:
                tot += (-1) ** d * perm_sign(y)
    return tot


okadd = True
for ab, vm in AUT:
    if ab[1] == 0:
        A = Cx([[0]])
        okadd = okadd and lefschetz_chain(T7, vm) == lefschetz_chain(A, {0: 0}) + rel_trace(T7, A, vm)
rot = {0: 0, 11: 11}
rot.update({1 + i: 1 + (i + 1) % 5 for i in range(5)})
rot.update({6 + i: 6 + (i + 1) % 5 for i in range(5)})
poles = Cx([[0], [11]])
okadd = okadd and lefschetz_chain(ICO, rot) == 2 == lefschetz_chain(poles, {0: 0, 11: 11}) + rel_trace(ICO, poles, rot)
check('L7 traces are additive: L(f) = L(f on A) + L(f on K relative to A) for an invariant subcomplex A', okadd,
      'torus automorphisms fixing a vertex; the rotation of the icosahedron about an axis has L = 2 = two fixed poles')


def aut_group(K):
    verts = [x[0] for x in K.S[0]]
    top = set(K.S[K.dim])
    out = []
    for perm in itertools.permutations(verts):
        vm = dict(zip(verts, perm))
        if all(tuple(sorted(vm[v] for v in t)) in top for t in top):
            out.append(vm)
    return out


AR = aut_group(RP2)
check('L8 every self-map of the projective plane has L = 1: all 60 automorphisms of the 6-vertex triangulation fix a point',
      len(AR) == 60 and all(lefschetz_chain(RP2, vm) == 1 and has_fixed_simplex(RP2, vm) for vm in AR), 'automorphism group of order %d' % len(AR))

okmul = True
for _ in range(30):
    a, b = random.randint(-4, 4), random.randint(-4, 4)
    A = [[a, 0], [0, b]]
    okmul = okmul and (1 - a) * (1 - b) == 1 - (a + b) + a * b
check('L9 the Lefschetz number is multiplicative on products: for z^a x z^b on the torus, (1-a)(1-b) = det(I - diag(a,b))', okmul, '30 pairs of degrees')




# ######################## CHECKS: PART TWO ########################
def vsub(a, b):
    return [x - y for x, y in zip(a, b)]


def cross(a, b):
    return [a[1] * b[2] - a[2] * b[1], a[2] * b[0] - a[0] * b[2], a[0] * b[1] - a[1] * b[0]]


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


def gauss_link(c1, c2, n=200):
    """Gauss linking integral of two closed curves given as functions on [0, 2 pi)"""
    h = 2 * PI / n
    P = [c1((i + 0.5) * h) for i in range(n)]
    Q = [c2((i + 0.5) * h) for i in range(n)]
    dP = [vsub(c1((i + 1) * h), c1(i * h)) for i in range(n)]
    dQ = [vsub(c2((i + 1) * h), c2(i * h)) for i in range(n)]
    tot = 0.0
    for i in range(n):
        for j in range(n):
            r = vsub(P[i], Q[j])
            d = vnorm(r)
            tot += dot(r, cross(dP[i], dQ[j])) / d ** 3
    return tot / (4 * PI)


sec('7. General position')


def seg_cross(p, q, r, s):
    def o(a, b, c):
        return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])
    return o(p, q, r) * o(p, q, s) < 0 and o(r, s, p) * o(r, s, q) < 0


def trefoil(t):
    return [math.sin(t) + 2 * math.sin(2 * t), math.cos(t) - 2 * math.cos(2 * t), -math.sin(3 * t)]


def crossings(direction, n=240):
    d = [x / vnorm(direction) for x in direction]
    a = cross(d, [0.3, 0.5, 0.81])
    a = [x / vnorm(a) for x in a]
    b = cross(d, a)
    pts = [(dot(trefoil(2 * PI * i / n), a), dot(trefoil(2 * PI * i / n), b)) for i in range(n)]
    c = 0
    for i in range(n):
        for j in range(i + 2, n):
            if i == 0 and j == n - 1:
                continue
            if seg_cross(pts[i], pts[(i + 1) % n], pts[j], pts[(j + 1) % n]):
                c += 1
    return c


cz = crossings([0, 0, 1])
cr = [crossings([random.gauss(0, 1) for _ in range(3)]) for _ in range(12)]
check('M1 a generic projection of a closed curve from space to the plane has finitely many transverse double points: the trefoil shows 3 from above and never fewer',
      cz == 3 and min(cr) >= 3, 'twelve random directions: %s' % sorted(cr))


def sard_measure(delta):
    # f(x) = x^3 - 3x; the set |f'| < delta consists of intervals around +-1; total length of the image
    lo, hi = math.sqrt(1 - delta / 3), math.sqrt(1 + delta / 3)
    f = lambda x: x ** 3 - 3 * x
    return 2 * (max(f(lo), f(hi)) - f(1.0))


sm = [sard_measure(d) / d ** 2 for d in (0.1, 0.01, 0.001)]
check('M2 Sard, quantitatively: for x^3 - 3x the image of the set where |f\'| < delta has length delta^2/6 + O(delta^3)',
      all(close(v, 1 / 6, 0.03) for v in sm) and abs(sm[2] - 1 / 6) < abs(sm[0] - 1 / 6), 'length / delta^2 = %s' % ', '.join('%.5f' % v for v in sm))


def umbrella_rank(x, y):
    J = [[1, 0], [y, x], [0, 2 * y]]
    minors = [J[0][0] * J[1][1] - J[0][1] * J[1][0], J[0][0] * J[2][1] - J[0][1] * J[2][0], J[1][0] * J[2][1] - J[1][1] * J[2][0]]
    return 2 if any(m != 0 for m in minors) else 1


grid = [Fr(i, 4) for i in range(-8, 9)]
sing = [(x, y) for x in grid for y in grid if umbrella_rank(x, y) < 2]
dbl = all((0, 0 * y, y * y) == (0, 0 * (-y), (-y) * (-y)) for y in grid)
check('M3 the Whitney umbrella (x, xy, y^2) fails to be an immersion only at the origin and identifies (0,y) with (0,-y)', sing == [(Fr(0), Fr(0))] and dbl,
      'rank 2 at the other %d grid points' % (len(grid) ** 2 - 1))


def height(th, ph, R=2.0, r=1.0):
    return (R + r * math.cos(th)) * math.cos(ph)


idx = []
for th in (0.0, PI):
    for ph in (0.0, PI):
        hxx = d2(lambda t: height(t, ph), th)
        hyy = d2(lambda p: height(th, p), ph)
        hxy = (height(th + 1e-4, ph + 1e-4) - height(th + 1e-4, ph - 1e-4) - height(th - 1e-4, ph + 1e-4) + height(th - 1e-4, ph - 1e-4)) / 4e-8
        g = max(abs(d1(lambda t: height(t, ph), th)), abs(d1(lambda p: height(th, p), ph)))
        det = hxx * hyy - hxy * hxy
        idx.append((g < 1e-6, 0 if (det > 0 and hxx > 0) else 2 if (det > 0) else 1))
ind = sorted(i for _, i in idx)
check('M4 the height function on an upright torus has four non-degenerate critical points of index 0, 1, 1, 2; the alternating count is the Euler characteristic 0',
      all(g for g, _ in idx) and ind == [0, 1, 1, 2], 'indices %s' % ind)


def poly_roots(co):
    """roots of a complex polynomial (Durand-Kerner); co[0] is the leading coefficient"""
    n = len(co) - 1
    co = [c / co[0] for c in co]
    z = [(0.4 + 0.9j) ** k for k in range(n)]
    for _ in range(400):
        new = []
        for i in range(n):
            num = sum(co[k] * z[i] ** (n - k) for k in range(n + 1))
            den = 1
            for j in range(n):
                if j != i:
                    den *= z[i] - z[j]
            new.append(z[i] - num / den)
        z = new
    return z


def rational_preimages(w):
    # f(z) = (z^3 + (1+2i) z + 0.5) / (0.7 z^2 - 1i): solve p - w q = 0
    return poly_roots([1, -0.7 * w, 1 + 2j, 0.5 + 1j * w])


cnts = []
for w in (0.3 + 0.2j, -1.1 + 0.7j, 2.0 - 1.5j):
    rts = rational_preimages(w)
    f = lambda z: (z ** 3 + (1 + 2j) * z + 0.5) / (0.7 * z * z - 1j)
    cnts.append(sum(1 for z in rts if abs(f(z) - w) < 1e-8))
# antiholomorphic example: z -> conj(z)^2 has two preimages of each value, each with Jacobian determinant -4|z|^2 < 0
check('M5 the degree counted over a regular value does not depend on the value: a rational map of degree 3 has 3 preimages; conj(z)^2 has two, each of sign -1',
      cnts == [3, 3, 3], 'preimage counts %s; degree of conj(z)^2 is -2' % cnts)

sec('8. Framed manifolds and the main method')


def circle_degree(F, dF, value, n=4000):
    """signed number of preimages of an angle under a map of the circle given by a lift F"""
    tot = 0
    winding = round((F(2 * PI) - F(0)) / (2 * PI))
    for k in range(-abs(winding) - 2, abs(winding) + 3):
        target = value + 2 * PI * k
        prev = F(0) - target
        for i in range(1, n + 1):
            t = 2 * PI * i / n
            cur = F(t) - target
            if prev * cur < 0 or prev == 0:
                tot += 1 if cur > prev else -1
            prev = cur
    return tot, winding


okdeg = True
for a in (-2, -1, 0, 1, 2, 3):
    F = lambda t: a * t + 1.3 * math.sin(2 * t) + 0.4 * math.cos(3 * t)
    s, w = circle_degree(F, None, 0.7)
    okdeg = okdeg and s == a == w
check('F1 framed points: the signed number of preimages of a regular value of a circle map is its degree, also when the map folds back', okdeg, 'degrees -2..3 with a non-monotone lift')


def sphere_degree(F, n=160):
    """degree of a map of the 2-sphere by integrating the pulled-back area form"""
    tot = 0.0
    hu, hv = PI / n, 2 * PI / n
    def X(u, v):
        return F([math.sin(u) * math.cos(v), math.sin(u) * math.sin(v), math.cos(u)])
    for i in range(n):
        for j in range(n):
            u, v = (i + 0.5) * hu, (j + 0.5) * hv
            a = X(u, v)
            du = [(p - q) / (2e-5) for p, q in zip(X(u + 1e-5, v), X(u - 1e-5, v))]
            dv = [(p - q) / (2e-5) for p, q in zip(X(u, v + 1e-5), X(u, v - 1e-5))]
            tot += dot(a, cross(du, dv)) * hu * hv
    return tot / (4 * PI)


def susp(d):
    def F(x):
        r = math.hypot(x[0], x[1])
        if r < 1e-12:
            return [0.0, 0.0, 1.0 if x[2] > 0 else -1.0]
        z = complex(x[0], x[1]) / r
        w = z ** d if d >= 0 else (z.conjugate()) ** (-d)
        return [r * w.real, r * w.imag, x[2]]
    return F


sd_ = [sphere_degree(susp(d)) for d in (1, 2, 3, -2)]
check('F2 suspension preserves the degree: the suspension of z -> z^d on the 2-sphere has degree d',
      all(close(v, d, 2e-3) for v, d in zip(sd_, (1, 2, 3, -2))), 'integral of the pulled-back area form: %s' % ', '.join('%.4f' % v for v in sd_))


def collapse_degree(points, n=120):
    """degree of the Pontryagin-Thom collapse of framed points in the plane: sum over discs of the area integral"""
    tot = 0.0
    for (px, py, frame) in points:
        def G(y):
            # disc |y| < 1 -> sphere: y/(1-|y|^2) followed by inverse stereographic projection
            r2 = y[0] * y[0] + y[1] * y[1]
            Y = [y[0] / (1 - r2), y[1] / (1 - r2)]
            s = Y[0] * Y[0] + Y[1] * Y[1]
            return [2 * Y[0] / (s + 1), 2 * Y[1] / (s + 1), (1 - s) / (s + 1)]
        hr, ht = 1.0 / n, 2 * PI / n
        for i in range(n):
            for j in range(n):
                r, t = (i + 0.5) * hr, (j + 0.5) * ht
                def X(r_, t_):
                    x = [r_ * math.cos(t_), r_ * math.sin(t_)]
                    y = [frame[0][0] * x[0] + frame[0][1] * x[1], frame[1][0] * x[0] + frame[1][1] * x[1]]
                    return G(y)
                a = X(r, t)
                dr = [(p - q) / 2e-6 for p, q in zip(X(r + 1e-6, t), X(r - 1e-6, t))]
                dt = [(p - q) / 2e-6 for p, q in zip(X(r, t + 1e-6), X(r, t - 1e-6))]
                tot += dot(a, cross(dr, dt)) * hr * ht
    return tot / (4 * PI)


pos = [[1.0, 0.0], [0.0, 1.0]]
neg = [[0.0, 1.0], [1.0, 0.0]]
cd = [collapse_degree([(0, 0, pos)]), collapse_degree([(0, 0, neg)]), collapse_degree([(0, 0, pos), (3, 0, pos), (0, 3, neg)])]
check('F3 the Pontryagin-Thom collapse of framed points in the plane has degree the signed number of points',
      close(cd[0], 1, 5e-3) and close(cd[1], -1, 5e-3) and close(cd[2], 1, 5e-3), 'degrees %.4f, %.4f, %.4f for frames (+), (-), (+,+,-)' % tuple(cd))

sec('9. Degree, linking and the Hopf invariant')
cA = lambda s: [math.cos(s), math.sin(s), 0.0]
cB = lambda s: [1 + math.cos(s), 0.0, math.sin(s)]
cC = lambda s: [4 + math.cos(s), 0.0, math.sin(s)]
def tl(j, k=2):
    return lambda s: [(2 + 0.6 * math.cos(k * s + j * PI)) * math.cos(s), (2 + 0.6 * math.cos(k * s + j * PI)) * math.sin(s), 0.6 * math.sin(k * s + j * PI)]
l1, l0, l2 = gauss_link(cA, cB), gauss_link(cA, cC), gauss_link(tl(0), tl(1))
check('K1 the Gauss integral computes linking numbers: Hopf link 1, unlinked circles 0, the (2,4) torus link 2',
      close(abs(l1), 1, 1e-3) and abs(l0) < 1e-9 and close(abs(l2), 2, 1e-3), 'values %.8f, %.1e, %.8f' % (l1, l0, l2))


def stereo(x):
    return [x[0] / (1 - x[3]), x[1] / (1 - x[3]), x[2] / (1 - x[3])]


def fibre(zeta):
    """the Hopf fibre z1 = zeta z2, as a curve in R^3"""
    n = math.sqrt(1 + abs(zeta) ** 2)
    def c(t):
        e = cmath.exp(1j * t)
        z1, z2 = zeta * e / n, e / n
        return stereo([z1.real, z1.imag, z2.real, z2.imag])
    return c


def total_link(zs, ws):
    return sum(gauss_link(fibre(a), fibre(b)) for a in zs for b in ws)


h1 = total_link([0.3 + 0.2j], [-1.0 + 0.5j])
h4 = total_link([cmath.sqrt(0.3 + 0.2j), -cmath.sqrt(0.3 + 0.2j)], [cmath.sqrt(-1 + 0.5j), -cmath.sqrt(-1 + 0.5j)])
c3 = lambda w: [abs(w) ** (1 / 3) * cmath.exp(1j * (cmath.phase(w) + 2 * PI * k) / 3) for k in range(3)]
h9 = total_link(c3(0.3 + 0.2j), c3(-1 + 0.5j))
check('K2 the Hopf invariant as a linking number: two fibres of the Hopf map link once; for g o h with g of degree d the preimages link d^2 times',
      close(abs(h1), 1, 1e-3) and close(abs(h4), 4, 1e-3) and close(abs(h9), 9, 1e-3), 'linking %.6f for h; %.6f for z^2 o h; %.6f for z^3 o h' % (h1, h4, h9))


def twisted_fibre(zeta, d):
    """preimage of zeta under h o f, f(z1,z2) = (z1^d, z2)/norm: the curve z1^d = zeta z2 on the 3-sphere"""
    r = bisect(lambda r_: r_ ** d - abs(zeta) * math.sqrt(1 - r_ * r_), 1e-9, 1 - 1e-9)
    s = math.sqrt(1 - r * r)
    def c(t):
        z1 = r * cmath.exp(1j * t)
        z2 = s * cmath.exp(1j * (d * t - cmath.phase(zeta)))
        return stereo([z1.real, z1.imag, z2.real, z2.imag])
    return c


hd = [gauss_link(twisted_fibre(0.5 + 0.1j, d), twisted_fibre(-0.8 + 1.2j, d), 260) for d in (1, 2, 3)]
check('K3 for h o f with f of degree d on the 3-sphere the preimages link d times: the Hopf invariant is linear on this side and quadratic on the other',
      all(close(abs(v), d, 1e-3) for v, d in zip(hd, (1, 2, 3))), 'linking %s' % ', '.join('%.5f' % v for v in hd))


def framed_pushoff(t, eps=0.25):
    return lambda s: [(1 + eps * math.cos(t * s)) * math.cos(s), (1 + eps * math.cos(t * s)) * math.sin(s), eps * math.sin(t * s)]


sl = [gauss_link(cA, framed_pushoff(t)) for t in (0, 1, 2, -3)]
check('K4 a framing of a circle in space is an integer: the linking number of the circle with its push-off along the frame that turns t times is t',
      all(close(abs(v), abs(t), 1e-3) for v, t in zip(sl, (0, 1, 2, -3))) and sl[1] * sl[3] < 0, 'linking %s' % ', '.join('%.6f' % v for v in sl))


def hopf(x):
    z1, z2 = complex(x[0], x[1]), complex(x[2], x[3])
    w = 2 * z1 * z2.conjugate()
    return [w.real, w.imag, abs(z1) ** 2 - abs(z2) ** 2]


okh = True
for _ in range(50):
    x = [random.gauss(0, 1) for _ in range(4)]
    n = vnorm(x)
    x = [a / n for a in x]
    y = hopf(x)
    th = random.uniform(0, 2 * PI)
    e = cmath.exp(1j * th)
    z1, z2 = complex(x[0], x[1]) * e, complex(x[2], x[3]) * e
    y2 = hopf([z1.real, z1.imag, z2.real, z2.imag])
    J = [[(hopf([x[k] + (1e-6 if k == j else 0) for k in range(4)])[i] - hopf([x[k] - (1e-6 if k == j else 0) for k in range(4)])[i]) / 2e-6 for j in range(4)] for i in range(3)]
    # rank of the differential restricted to the tangent space: Gram matrix has rank 2 on the sphere
    G = [[sum(J[i][k] * J[j][k] for k in range(4)) for j in range(3)] for i in range(3)]
    ev, _ = jacobi_eig(G)
    okh = okh and close(vnorm(y), 1, 1e-9) and vnorm(vsub(y, y2)) < 1e-9 and ev[1] > 1.0
check('K5 the Hopf map takes the 3-sphere onto the 2-sphere, is constant on the circles e^{it}(z1,z2), and is a submersion', okh, '50 random points')

sec('10. Rotations and the first stem')


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 qconj(a):
    return (a[0], -a[1], -a[2], -a[3])


def qn2(a):
    return sum(x * x for x in a)


def qrot(q):
    """matrix of v -> q v q^{-1} on the imaginary quaternions"""
    n = qn2(q)
    cols = []
    for k in range(3):
        v = tuple([0] + [1 if i == k else 0 for i in range(3)])
        w = qmul(qmul(q, v), qconj(q))
        cols.append([w[1] / n, w[2] / n, w[3] / n])
    return [[cols[j][i] for j in range(3)] for i in range(3)]


def rq():
    return tuple(Fr(random.randint(-5, 5), random.randint(1, 4)) for _ in range(4))


okq = True
for _ in range(100):
    a, b, c = rq(), rq(), rq()
    okq = okq and qmul(qmul(a, b), c) == qmul(a, qmul(b, c)) and qn2(qmul(a, b)) == qn2(a) * qn2(b)
check('R1 the quaternions are associative and their norm is multiplicative', okq, '100 random rational triples, exactly')

okr = True
for _ in range(60):
    a, b = rq(), rq()
    if qn2(a) == 0 or qn2(b) == 0:
        continue
    A, B, AB = qrot(a), qrot(b), qrot(qmul(a, b))
    I3 = [[Fr(int(i == j)) for j in range(3)] for i in range(3)]
    det = (A[0][0] * (A[1][1] * A[2][2] - A[1][2] * A[2][1]) - A[0][1] * (A[1][0] * A[2][2] - A[1][2] * A[2][0]) + A[0][2] * (A[1][0] * A[2][1] - A[1][1] * A[2][0]))
    okr = okr and mat_mul([list(r) for r in zip(*A)], A) == I3 and det == 1 and mat_mul(A, B) == AB and qrot(tuple(-x for x in a)) == A
    okr = okr and ((A == I3) == (a[1] == a[2] == a[3] == 0))
check('R2 q -> (v -> q v q^-1) is a homomorphism onto rotations with kernel the real quaternions: the 3-sphere covers SO(3) twice', okr, '60 random rational pairs, exactly')


def mat_to_quat(R):
    t = R[0][0] + R[1][1] + R[2][2]
    cands = [(1 + t, R[2][1] - R[1][2], R[0][2] - R[2][0], R[1][0] - R[0][1]),
             (R[2][1] - R[1][2], 1 + R[0][0] - R[1][1] - R[2][2], R[0][1] + R[1][0], R[0][2] + R[2][0]),
             (R[0][2] - R[2][0], R[0][1] + R[1][0], 1 - R[0][0] + R[1][1] - R[2][2], R[1][2] + R[2][1]),
             (R[1][0] - R[0][1], R[0][2] + R[2][0], R[1][2] + R[2][1], 1 - R[0][0] - R[1][1] + R[2][2])]
    q = max(cands, key=lambda c: sum(x * x for x in c))
    n = math.sqrt(sum(x * x for x in q))
    return [x / n for x in q]


def axis_rot(u, th):
    n = vnorm(u)
    q = (math.cos(th / 2),) + tuple(math.sin(th / 2) * x / n for x in u)
    return [[float(v) for v in r] for r in qrot(q)]


def lift_class(loop, n=2000):
    """0 if the lift of a loop of rotations to unit quaternions closes, 1 if it ends at minus the start"""
    q0 = mat_to_quat(loop(0.0))
    q = q0
    for i in range(1, n + 1):
        c = mat_to_quat(loop(2 * PI * i / n))
        if sum(a * b for a, b in zip(c, q)) < 0:
            c = [-x for x in c]
        q = c
    return 0 if sum(a * b for a, b in zip(q, q0)) > 0 else 1


u, v = [0.3, -0.5, 0.8], [0.7, 0.6, -0.2]
cls = {(a, b): lift_class(lambda t, a=a, b=b: [[float(x) for x in r] for r in mat_mul(axis_rot(u, a * t), axis_rot(v, b * t))]) for a, b in ((1, 0), (2, 0), (1, 1), (1, 2), (3, 2), (0, 0))}
check('R3 the fundamental group of SO(3) has order two: a full turn lifts to a path from 1 to -1, two full turns to a closed path; the class of a product of turns is the parity of their number',
      all(cls[k] == (k[0] + k[1]) % 2 for k in cls), 'classes %s' % cls)


def rp_homology(n):
    out = []
    for k in range(n + 1):
        dk = (1 + (-1) ** k) if k >= 1 else None
        dk1 = (1 + (-1) ** (k + 1)) if k + 1 <= n else None
        rank_k = 1 if (dk is not None and dk != 0) else 0
        rank_k1 = 1 if (dk1 is not None and dk1 != 0) else 0
        out.append((1 - rank_k - rank_k1, [abs(dk1)] if dk1 not in (None, 0) and abs(dk1) > 1 else []))
    return out


check('R4 SO(3) is projective 3-space: its cellular complex Z <-0- Z <-2- Z <-0- Z has homology Z, Z/2, 0, Z',
      rp_homology(3) == [(1, []), (0, [2]), (0, []), (1, [])] and rp_homology(2) == homology(RP2), 'projective plane from the same recipe: %s' % rp_homology(2))


def bernoulli(m):
    B = [Fr(1)]
    for n in range(1, m + 1):
        B.append(-sum(Fr(math.comb(n + 1, k)) * B[k] for k in range(n)) / (n + 1))
    return B


Bn = bernoulli(16)
jorders = [(Bn[2 * k] / (4 * k)).denominator for k in range(1, 9)]
check('R5 the image of the J-homomorphism in the stems 3, 7, 11, 15, ... has order the denominator of B_2k/4k: 24, 240, 504, 480, 264, 65520, 24, 16320',
      jorders == [24, 240, 504, 480, 264, 65520, 24, 16320], 'computed from Bernoulli numbers: %s' % jorders)


def framed_circle_class(t, n=3):
    """class in pi_1(SO(3)) of the normal framing of the unit circle in R^4 that turns t times relative to the product framing"""
    # frame along the circle: (radial, e_z, e_w) rotated in the (e_z, e_w) plane by t s; as a loop in SO(3) about the radial axis
    return lift_class(lambda s: axis_rot([1.0, 0.0, 0.0], t * s))


fc = [framed_circle_class(t) for t in (0, 1, 2, 3)]
check('R6 in codimension three and more the framings of a circle are counted modulo two: the turning number t gives the class t mod 2',
      fc == [0, 1, 0, 1], 'classes %s for t = 0, 1, 2, 3; in codimension two (K4) t itself is the invariant' % fc)

sec('11. The Arf invariant and the second stem')


def quad_forms(g):
    """all quadratic refinements of the standard symplectic form on F_2^{2g}, as dictionaries of values"""
    vecs = list(itertools.product((0, 1), repeat=2 * g))
    out = []
    for c in vecs:
        q = {x: (sum(c[i] * x[i] for i in range(2 * g)) + sum(x[i] * x[g + i] for i in range(g))) % 2 for x in vecs}
        out.append((c, q))
    return vecs, out


def omega(x, y, g):
    return sum(x[i] * y[g + i] + x[g + i] * y[i] for i in range(g)) % 2


arf_counts = {}
okmaj = okref = True
for g in (1, 2, 3):
    vecs, forms = quad_forms(g)
    a0 = a1 = 0
    for c, q in forms:
        arf = sum(c[i] * c[g + i] for i in range(g)) % 2
        ones = sum(q.values())
        okmaj = okmaj and ones == 2 ** (2 * g - 1) + (-1 if arf == 0 else 1) * 2 ** (g - 1)
        a0 += arf == 0
        a1 += arf == 1
    arf_counts[g] = (a0, a1)
    c, q = forms[random.randrange(len(forms))]
    okref = okref and all(q[tuple((a + b) % 2 for a, b in zip(x, y))] == (q[x] + q[y] + omega(x, y, g)) % 2 for x in vecs for y in vecs)
check('A1 quadratic refinements of the intersection form in genus g: 2^(g-1)(2^g+1) of Arf invariant 0 and 2^(g-1)(2^g-1) of Arf invariant 1',
      arf_counts == {1: (3, 1), 2: (10, 6), 3: (36, 28)} and okref, 'counts %s' % arf_counts)
check('A2 the Arf invariant is the majority vote: q takes the value 1 on 2^(2g-1) - 2^(g-1) vectors if Arf = 0 and on 2^(2g-1) + 2^(g-1) if Arf = 1', okmaj, 'all 4 + 16 + 64 forms')

okadd = True
_, f1 = quad_forms(1)
_, f2 = quad_forms(2)
def arf_vote(q, g):
    return 0 if sum(q.values()) < 2 ** (2 * g - 1) else 1
for c1, q1 in f1:
    for c2, q2 in f2:
        # orthogonal sum on F_2^2 + F_2^4
        tot = sum((q1[x] + q2[y]) % 2 for x in q1 for y in q2)
        okadd = okadd and (0 if tot < 2 ** 5 else 1) == (arf_vote(q1, 1) + arf_vote(q2, 2)) % 2
check('A3 the Arf invariant is additive under orthogonal sums', okadd, 'all 4 x 16 sums of a genus-1 and a genus-2 form')


def sp4():
    J = [[0, 0, 1, 0], [0, 0, 0, 1], [1, 0, 0, 0], [0, 1, 0, 0]]
    out = []
    for bits in range(1 << 16):
        M = [[(bits >> (4 * i + j)) & 1 for j in range(4)] for i in range(4)]
        ok = True
        for i in range(4):
            for j in range(i, 4):
                v = sum(M[a][i] * J[a][b] * M[b][j] for a in range(4) for b in range(4) if J[a][b]) % 2
                if v != J[i][j]:
                    ok = False
                    break
            if not ok:
                break
        if ok:
            out.append(M)
    return out


SP = sp4()
vecs2, forms2 = quad_forms(2)
def act(M, x):
    return tuple(sum(M[i][j] * x[j] for j in range(4)) % 2 for i in range(4))
orbit_of = {}
keys = [tuple(q[x] for x in vecs2) for _, q in forms2]
seen = set()
orbits = []
for k in keys:
    if k in seen:
        continue
    q = dict(zip(vecs2, k))
    orb = set()
    for M in SP:
        orb.add(tuple(q[act(M, x)] for x in vecs2))
    seen |= orb
    orbits.append(len(orb))
check('A4 the symplectic group Sp(4, F_2) has order 720 and exactly two orbits on the 16 quadratic refinements, of sizes 10 and 6', len(SP) == 720 and sorted(orbits) == [6, 10],
      'orbit sizes %s' % sorted(orbits))


def surgery_reduce(q, g):
    """kill classes with q = 0 one at a time; returns the dimension of what cannot be killed"""
    vecs = list(q.keys())
    add = lambda x, y: tuple((a + b) % 2 for a, b in zip(x, y))
    U = set(vecs)
    R = {tuple([0] * (2 * g))}
    while True:
        x = next((y for y in sorted(U) if y not in R and q[y] == 0), None)
        if x is None:
            break
        U = {y for y in U if omega(x, y, g) == 0}
        R = R | {add(r, x) for r in R}
    return (len(U).bit_length() - 1) - (len(R).bit_length() - 1)


okred = True
for g in (1, 2, 3):
    vecs, forms = quad_forms(g)
    for c, q in forms:
        arf = sum(c[i] * c[g + i] for i in range(g)) % 2
        okred = okred and surgery_reduce(q, g) == 2 * arf
check('A5 surgery on classes with q = 0 reduces a form of Arf invariant 0 to nothing and one of Arf invariant 1 to a torus on which q is 1 on every non-zero class',
      okred, 'all forms of genus 1, 2, 3')

sec('12. Stable stems as the homotopy of the unit')


def commutator_index(n):
    els = list(itertools.permutations(range(n)))
    mul = lambda a, b: tuple(a[b[i]] for i in range(n))
    inv_ = lambda a: tuple(sorted(range(n), key=lambda i: a[i]))
    gens = set()
    for a in els:
        for b in els:
            gens.add(mul(mul(a, b), mul(inv_(a), inv_(b))))
    G = set(gens)
    frontier = list(gens)
    while frontier:
        x = frontier.pop()
        for y in gens:
            z = mul(x, y)
            if z not in G:
                G.add(z)
                frontier.append(z)
    return len(els) // len(G)


ci = [commutator_index(n) for n in (2, 3, 4, 5)]
check('T1 the abelianization of the symmetric group has order 2 for n >= 2: the sign is the first stable stem', ci == [2, 2, 2, 2], 'index of the commutator subgroup for n = 2..5: %s' % ci)


def angle_defect_sum(verts, tris):
    ang = {i: 0.0 for i in range(len(verts))}
    for t in tris:
        for k in range(3):
            a, b, c = verts[t[k]], verts[t[(k + 1) % 3]], verts[t[(k + 2) % 3]]
            u_, v_ = vsub(b, a), vsub(c, a)
            ang[t[k]] += math.acos(max(-1.0, min(1.0, dot(u_, v_) / (vnorm(u_) * vnorm(v_)))))
    return sum(2 * PI - a for a in ang.values())


tet = [[random.gauss(0, 1) for _ in range(3)] for _ in range(4)]
d_tet = angle_defect_sum(tet, [(0, 1, 2), (0, 1, 3), (0, 2, 3), (1, 2, 3)])
m_, n_ = 6, 9
tv = [[(2 + math.cos(2 * PI * i / m_)) * math.cos(2 * PI * j / n_), (2 + math.cos(2 * PI * i / m_)) * math.sin(2 * PI * j / n_), math.sin(2 * PI * i / m_)] for i in range(m_) for j in range(n_)]
tt = []
for i in range(m_):
    for j in range(n_):
        a, b, c, d = i * n_ + j, ((i + 1) % m_) * n_ + j, ((i + 1) % m_) * n_ + (j + 1) % n_, i * n_ + (j + 1) % n_
        tt += [(a, b, c), (a, c, d)]
d_tor = angle_defect_sum(tv, tt)
check('T2 the Euler characteristic as a total curvature: the angle defects of a polyhedral surface add up to 2 pi chi', close(d_tet, 4 * PI, 1e-9) and abs(d_tor) < 1e-9,
      'random tetrahedron %.6f = 4 pi; polyhedral torus %.1e' % (d_tet, d_tor))


footer()
