Independent scholarship · Open accessThe monthly digest

Indexed text attachment

verify-topology.py

Source for Algebraic and Differential Topology in Higher Categories

View paper · Download original file

Lines 1121–1220 of 1961. Source text is displayed literally.

1121check('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,1122      'displacement at the centre of a complete cell: %s for n = 8, 32, 128' % ', '.join('%.4f' % e for e in errs))1123 1124 1125def hex_winner(n):1126    col = [[random.random() < 0.5 for _ in range(n)] for _ in range(n)]1127    nb = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, -1), (-1, 1)]1128    def connects(c, vertical):1129        seen = set()1130        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]1131        while stack:1132            i, j = stack.pop()1133            if (i, j) in seen:1134                continue1135            seen.add((i, j))1136            if (vertical and i == n - 1) or (not vertical and j == n - 1):1137                return True1138            for a, b in nb:1139                u, v = i + a, j + b1140                if 0 <= u < n and 0 <= v < n and col[u][v] == c and (u, v) not in seen:1141                    stack.append((u, v))1142        return False1143    return connects(True, True), connects(False, False)1144 1145 1146hx = [hex_winner(9) for _ in range(300)]1147check('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),1148      '300 random fillings of the 9 x 9 board; first player wins %d' % sum(a for a, _ in hx))1149 1150 1151def order_of_cover(kind, n=6):1152    """largest number of closed tiles meeting at a point, for a tiling of the plane by unit squares"""1153    best = 01154    for i in range(2 * n):1155        for j in range(2 * n):1156            p = (i / 2, j / 2)1157            cnt = 01158            for a in range(-1, n + 1):1159                for b in range(-1, n + 1):1160                    off = 0.5 * (b % 2) if kind == 'brick' else 0.01161                    if a + off <= p[0] <= a + off + 1 and b <= p[1] <= b + 1:1162                        cnt += 11163            best = max(best, cnt)1164    return best1165 1166 1167check('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',1168      order_of_cover('brick') == 3 and order_of_cover('grid') == 4, 'orders %d and %d' % (order_of_cover('brick'), order_of_cover('grid')))1169 1170sec('5. Homotopy and the cylinder')1171okpr = True1172for nm, K in NAMED[1:5]:1173    PK, N = prism(K)1174    for d in range(0, K.dim + 1):1175        P = [[0] * K.n(d) for _ in range(PK.n(d + 1))]1176        for j, x in enumerate(K.S[d]):1177            for i in range(d + 1):1178                P[PK.idx[d + 1][x[:i + 1] + tuple(v + N for v in x[i:])]][j] = (-1) ** i1179        i0 = chain_map(K, PK, {x[0]: x[0] for x in K.S[0]}, d)1180        i1 = chain_map(K, PK, {x[0]: x[0] + N for x in K.S[0]}, d)1181        lhs = mat_mul(PK.bd(d + 1), P)1182        if d > 0:1183            Pm = [[0] * K.n(d - 1) for _ in range(PK.n(d))]1184            for j, x in enumerate(K.S[d - 1]):1185                for i in range(d):1186                    Pm[PK.idx[d][x[:i + 1] + tuple(v + N for v in x[i:])]][j] = (-1) ** i1187            lhs = [[a + b for a, b in zip(r, q)] for r, q in zip(lhs, mat_mul(Pm, K.bd(d)))]1188        okpr = okpr and mat_eq(lhs, mat_sub(i1, i0))1189check('P1 the cylindric construction: the prism operator P satisfies dP + Pd = top - bottom', okpr, 'icosahedron, torus, projective plane, Klein bottle')1190 1191PR, _ = prism(RP2)1192PM, _ = prism(MB)1193check('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],1194      'projective plane times interval: %s' % homology(PR))1195 1196 1197def choice_map(K, num):1198    inv_ = {i: x for x, i in num.items()}1199    return {i: random.choice(inv_[i]) for i in inv_}1200 1201 1202okcont = True1203found = 01204for K in (T7, RP2, MB, ICO):1205    SK, num = sd(K)1206    for _ in range(3):1207        f, g = choice_map(K, num), choice_map(K, num)1208        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])1209        found += contig1210        for d in range(1, K.dim + 1):1211            Bd = K.bd(d + 1) if d < K.dim else []1212            Bbasis = independent_extend([], [[Fr(v) for v in c] for c in zip(*Bd)]) if Bd and Bd[0] else []1213            F, G = chain_map(SK, K, f, d), chain_map(SK, K, g, d)1214            for z in nullspace(SK.bd(d), SK.n(d)):1215                diff = [sum((F[i][k] - G[i][k]) * z[k] for k in range(SK.n(d))) for i in range(K.n(d))]1216                okcont = okcont and not independent_extend(Bbasis, [diff])1217check('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,1218      '%d pairs, all contiguous, on the torus, the projective plane, the Moebius band and the icosahedron' % found)1219 1220disc, _ = cone(circle(8))