Independent scholarship · Open accessThe monthly digest

Indexed text attachment

verify-topology-learning.py

Source for Algebraic and Differential Topology in Machine Learning and AI: Obstructions, Invariants, and Counts

View paper · Download original file

Lines 1421–1520 of 1604. Source text is displayed literally.

1421 1422def door_walk(n):1423    def pt(i, j):1424        return ((n - i - j) / n, i / n, j / n)1425    cache = {}1426    def lab(v):1427        if v not in cache:1428            p = pt(*v)1429            q = fmap(p)1430            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]))1431        return cache[v]1432    def cells_of_edge(a, b):1433        (i1, j1), (i2, j2) = sorted([a, b])1434        out = []1435        for c in [(i1 + i2 - j1 - j2 + 0, 0)]:1436            pass1437        # third vertices completing a grid triangle with edge ab1438        cands = []1439        di, dj = i2 - i1, j2 - j11440        if (di, dj) == (1, 0):1441            cands = [(i1, j1 + 1), (i2, j2 - 1)]1442        elif (di, dj) == (0, 1):1443            cands = [(i1 + 1, j1), (i1 - 1, j2)]1444        else:  # (1,-1)1445            cands = [(i1, j1 - 1), (i2, j1)]1446        return [c for c in cands if c[0] >= 0 and c[1] >= 0 and c[0] + c[1] <= n]1447    best = None1448    for i in range(n):1449        a, b = (i, 0), (i + 1, 0)1450        if {lab(a), lab(b)} != {0, 1}:1451            continue1452        steps = 01453        edge = (a, b)1454        third = cells_of_edge(a, b)[0]1455        prev_third = None1456        while True:1457            steps += 11458            tri = (edge[0], edge[1], third)1459            if lab(third) == 2:1460                best = steps if best is None else min(best, steps)1461                break1462            # leave through the other 01-edge1463            other = edge[0] if lab(edge[0]) != lab(third) else edge[1]1464            new_edge = (other, third)1465            nxt = [c for c in cells_of_edge(*new_edge) if c not in tri]1466            if not nxt:1467                break1468            edge, third = new_edge, nxt[0]1469    return best1470 1471 1472walks = {n: door_walk(n) for n in (16, 32, 64, 128)}1473check('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',1474      all(walks[n] is not None for n in walks) and walks[128] < 6 * 128 and 1.5 < walks[128] / walks[64] < 2.6,1475      'steps %s for n = 16, 32, 64, 128; cells %s' % ([walks[n] for n in sorted(walks)], [n * n for n in sorted(walks)]))1476 1477 1478def circle_fixed(d, eps, g, n=6000):1479    h = lambda t: (d - 1) * t + eps * g(t)1480    tot = cnt = 01481    for m in range(-abs(d) - 6, abs(d) + 7):1482        prev = h(0.0) - 2 * PI * m1483        for i in range(1, n + 1):1484            cur = h(2 * PI * i / n) - 2 * PI * m1485            if prev == 0 or prev * cur < 0:1486                cnt += 11487                tot += -1 if cur > prev else 11488            prev = cur1489    return tot, cnt1490 1491 1492okcf = True1493info = []1494for d in (-2, 0, 1, 2, 3):1495    for eps in (0.3, 2.0):1496        g = trig_poly(4)1497        s, c = circle_fixed(d, eps, g)1498        okcf = okcf and s == 1 - d and c >= abs(1 - d) and (c - abs(1 - d)) % 2 == 01499        if eps == 2.0:1500            info.append('d=%d: %d points, signed %d' % (d, c, s))1501check('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',1502      okcf, '; '.join(info))1503 1504 1505def torus_zeros(eps):1506    def v(t):1507        return [math.sin(t[0]) + eps * math.sin(t[1] + 0.4), math.sin(t[1]) + eps * math.cos(t[0] - t[1])]1508    found = []1509    for i in range(16):1510        for j in range(16):1511            t = [2 * PI * (i + 0.37) / 16, 2 * PI * (j + 0.61) / 16]1512            for _ in range(50):1513                f0 = v(t)1514                h = 1e-61515                a = [(p - q) / (2 * h) for p, q in zip(v([t[0] + h, t[1]]), v([t[0] - h, t[1]]))]1516                b = [(p - q) / (2 * h) for p, q in zip(v([t[0], t[1] + h]), v([t[0], t[1] - h]))]1517                det = a[0] * b[1] - a[1] * b[0]1518                if abs(det) < 1e-12:1519                    break1520                t = [t[0] - (f0[0] * b[1] - f0[1] * b[0]) / det, t[1] - (a[0] * f0[1] - a[1] * f0[0]) / det]