Indexed text attachment
verify-topology.py
Source for Algebraic and Differential Topology in Higher Categories
View paper · Download original file
Lines 1061–1160 of 1961. Source text is displayed literally.
1061 tets = [[tuple(Fr(int(i == k)) for k in range(4)) for i in range(4)]]1062 for _ in range(m):1063 new = []1064 for t in tets:1065 for perm in itertools.permutations(t):1066 new.append([tuple(sum(p[k] for p in perm[:j]) / j for k in range(4)) for j in (1, 2, 3, 4)])1067 tets = new1068 lab = {}1069 for t in tets:1070 for v in t:1071 if v not in lab:1072 lab[v] = random.choice([k for k in range(4) if v[k] > 0])1073 cnt = tot = 01074 for t in tets:1075 l = [lab[v] for v in t]1076 if sorted(l) == [0, 1, 2, 3]:1077 M = [[Fr(1)] + list(v[:3]) for v in t]1078 # orientation of the cell times the sign of the labelling1079 rows = [[a - b for a, b in zip(v[:3], t[0][:3])] for v in t[1:]]1080 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])1081 + rows[0][2] * (rows[1][0] * rows[2][1] - rows[1][1] * rows[2][0]))1082 cnt += 11083 tot += (1 if det > 0 else -1) * perm_sign(l)1084 return cnt, tot, len(tets)1085 1086 1087r3 = [sperner3(2) for _ in range(20)]1088ref = r3[0][1]1089check('S3 Sperner in dimension three: an odd number of complete cells, with signed count of absolute value one',1090 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)))1091 1092 1093def fmap(p):1094 """a continuous self-map of the standard triangle (barycentric coordinates)"""1095 x, y, z = p1096 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)1097 s = sum(q)1098 return tuple(a / s for a in q)1099 1100 1101def sperner_fixed(n):1102 def pt(i, j):1103 return ((n - i - j) / n, i / n, j / n)1104 def lab(i, j):1105 p = pt(i, j)1106 q = fmap(p)1107 for k in range(3):1108 if p[k] > 0 and q[k] <= p[k]:1109 return k1110 return max(range(3), key=lambda k: p[k])1111 best = None1112 for t in sperner_grid(n):1113 if sorted(lab(*v) for v in t) == [0, 1, 2]:1114 c = tuple(sum(pt(*v)[k] for v in t) / 3 for k in range(3))1115 e = max(abs(a - b) for a, b in zip(c, fmap(c)))1116 best = e if best is None else min(best, e)1117 return best1118 1119 1120errs = [sperner_fixed(n) for n in (8, 32, 128)]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.0