"""Verify the weighted spectral-tree mutation certificates with integer arithmetic.""" import argparse import json from collections import Counter from math import lcm from pathlib import Path def require(value, message): if not value: raise ValueError(message) def identity(n): return [[int(i == j) for j in range(n)] for i in range(n)] def negate(matrix): return [[-x for x in row] for row in matrix] def mutate(matrix, k): pivot = matrix[k] for i, row in enumerate(matrix): if i == k or not row[k]: continue c = row[k] for j, z in enumerate(pivot): if c * z > 0: row[j] += abs(c) * z row[k] = -c matrix[k] = [-z for z in pivot] class Framed: def __init__(self, matrix): self.n = len(matrix) self.start = [row[:] for row in matrix] self.rows = [row + unit for row, unit in zip(matrix, identity(self.n))] self.word = [] self.red = 0 def step(self, k): require(type(k) is int and 0 <= k < self.n, 'Invalid mutation label') c = self.rows[k][self.n:] require(min(c) >= 0 and max(c) > 0 or max(c) <= 0 and min(c) < 0, 'A coefficient row has no tropical sign') self.red += max(c) <= 0 self.word.append(k) mutate(self.rows, k) def permutation(self, expected): """Map semantic labels to slots in the current seed.""" slots = {tuple(row[self.n:]): i for i, row in enumerate(self.rows)} require(len(slots) == self.n and all(tuple(row) in slots for row in expected), 'The required direction basis was not reached') return [slots[tuple(row)] for row in expected] def endpoint(self): """Map terminal slots to initial slots, checking both framed blocks.""" semantic = self.permutation(negate(identity(self.n))) p = [semantic.index(i) for i in range(self.n)] require(all(row[:self.n] == [self.start[p[i]][j] for j in p] for i, row in enumerate(self.rows)), 'Incorrect terminal principal block') return p def strips(dim): return [(k, i, m) for i, d in dim.items() for m in range(1, d) for k in ('s', 't')] def direction(label, dim): kind, i = label[:2] if kind in ('frame', 'incoming'): return {('p', i, dim[i]): 1} if kind == 'outgoing': return {('p', i, 1): -1} if kind == 'edge': j = label[2] return {('p', j, dim[j]): 1, ('p', i, 1): -1} m = label[2] if kind == 's': return {('x', i, m): -1, ('x', i, m + 1): 1} return {('x', i, m): 1, ('x', i, m + 1): -1, ('p', i, m): 1, ('p', i, m + 1): -1} def principal(labels, dim, weight): """Compute -delta_j times the symplectic pairing of two direction vectors.""" vectors = [direction(z, dim) for z in labels] delta = [lcm(weight[z[1]], weight[z[2]]) if z[0] == 'edge' else max(weight.values()) if z[0] in ('incoming', 'outgoing') else weight[z[1]] for z in labels] rows = [] for v in vectors: row = [] for w, dj in zip(vectors, delta): entry = 0 for (kind, i, m), x in v.items(): if kind == 'x': numerator = dj * x * w.get(('p', i, m), 0) else: numerator = -dj * x * w.get(('x', i, m), 0) require(numerator % weight[i] == 0, 'Nonintegral pairing') entry += numerator // weight[i] row.append(entry) rows.append(row) return rows def character_matrix(dim, weight, edges, root, labels): """Independently expand the directions in the rooted spectral character basis.""" incoming = {j: (i, j) for i, j in edges} def unit(label): return Counter({label: 1}) def difference(first, second): row = first.copy() row.subtract(second) return row dual = {} for i, d in dim.items(): rho = Counter({('edge', a, b): lcm(weight[a], weight[b]) // weight[i] for a, b in edges if a == i}) if i == root: norm = unit(('frame', i)) else: a, b = incoming[i] norm = Counter({('edge', a, b): lcm(weight[a], weight[b]) // weight[i]}) old_p, old_x = Counter(), Counter() for m in range(1, d + 1): if m == d: p = unit(('principal', i)) x = difference(norm, rho) else: p = difference(unit(('s', i, m)), unit(('t', i, m))) x = difference(unit(('t', i, m)), rho) dual['p', i, m] = difference(p, old_p) dual['x', i, m] = difference(x, old_x) old_p, old_x = p, x result = [] for lab in labels: row = Counter() for key, factor in direction(lab, dim).items(): for target, coefficient in dual[key].items(): row[target] += factor * coefficient result.append([row[k] for k in labels + [('principal', i) for i in dim]]) return result def slot_map(slots, labels, word): return [slots[labels.index(k)] for k in word] def verify_gate(a, b, word): dim, weight = {0: a, 1: b}, {0: 1, 1: 2} local = strips(dim) + [('edge', 0, 1)] edge = len(local) - 1 require(all(0 <= k <= edge for k in word), 'Invalid local word') labels = local + [(kind, i) for i in dim for kind in ('outgoing', 'incoming')] seed = Framed(negate(principal(labels, dim, weight))) for k in word: seed.step(k) expected = identity(len(labels)) expected[edge] = [-int(j <= edge) for j in range(len(labels))] slots = seed.permutation(expected) require(slots[len(local):] == list(range(len(local), len(labels))), 'A spectator changed') # Also recover the paired tropical characters, including both principal coefficients. labels = local + [('frame', 0)] B = character_matrix(dim, weight, [(0, 1)], 0, labels) n = len(labels) require([r[:n] for r in B] == principal(labels, dim, weight), 'Spectral matrix mismatch') framed = Framed(negate([r[:n] for r in B])) char = identity(n + 2) for k in word: eps = 1 if min(framed.rows[k][n:]) >= 0 else -1 char[k] = [-x + sum(max(eps * z, 0) * char[j][h] for j, z in enumerate(B[k])) for h, x in enumerate(char[k])] mutate(B, k) framed.step(k) expected = identity(n) expected[edge] = [-int(j <= edge) for j in range(n)] slots = framed.permutation(expected) target = identity(n + 2) for j, (_, i, m) in enumerate(local[:-1]): target[j][edge] -= 2 if i == 0 else 1 target[j][-1] += 2 * m if i == 0 else a target[edge][edge], target[edge][-1] = -1, a require(all(char[j] == target[i] for i, j in enumerate(slots)), 'Character target mismatch') return len(word) def rectangle(i, j, dim): """Schrader-Shapiro's ordinary arrow-reversal word, in chronological order.""" a, b = dim[i], dim[j] lookup = {2 * b - 1: ('edge', i, j)} for k in range(1, b): lookup[2 * k - 1], lookup[2 * k] = ('s', j, k), ('t', j, k) for k in range(1, a): lookup[2 * (b + k) - 1], lookup[2 * (b + k - 1)] = ('s', i, k), ('t', i, k) cells = [(x, y) for x in range(2 * a - 1) for y in range(2 * b - 1)] cells.sort(key=lambda q: (q[0] - q[1], q[0] % 2, q[0] if q[0] % 2 == 0 else -q[0])) return [lookup[1 + x + y] for x, y in cells] def family(kind, n, r): require(n >= 2 and 1 <= r <= n, 'Invalid fundamental node') if kind == 'C': require(r < n, 'The evaluation node has no residual tree') dims, weights = [min(i, r) for i in range(1, n + 1)], [2] * (n - 1) + [1] elif kind == 'B': dims = [min(i, r) - r % 2 for i in range(1, n)] + [r // 2] weights = [1] * (n - 1) + [2] elif kind == 'F' and n == 4: dims = [(2, 3, 2, 1), (3, 6, 4, 2), (4, 8, 6, 3), (2, 4, 3, 2)][r - 1] weights = [1, 1, 2, 2] else: raise ValueError('Supported types are B, C and F4') return ({i: d for i, d in enumerate(dims, 1) if d}, {i: w for i, w in enumerate(weights, 1)}) def verify_tree(kind, rank, root, gates): dim, weight = family(kind, rank, root) edges = [(i, i - 1) if i <= root else (i - 1, i) for i in dim if i - 1 in dim] seams = [e for e in edges if weight[e[0]] != weight[e[1]]] require(len(seams) == 1, 'This case has no residual double bond') seam = seams[0] long, short = sorted(seam, key=weight.get) oriented = [(long, short) if e == seam else e for e in edges] pair = (dim[long], dim[short]) require(pair in gates, f'No supplied Baxter word for dimensions {pair}') labels = strips(dim) + [('edge', *e) for e in oriented] + [('frame', root)] seed = Framed(negate(principal(labels, dim, weight))) target = identity(seed.n) slots = list(range(seed.n)) def reverse(label, sequence): nonlocal slots for k in slot_map(slots, labels, sequence): seed.step(k) colors = set(label[1:]) target[labels.index(label)] = [-int(v == label or v[0] in ('s', 't') and v[1] in colors) for v in labels] slots = seed.permutation(target) bond = ('edge', long, short) local = strips({long: dim[long], short: dim[short]}) + [bond] reverse(bond, [local[k] for k in gates[pair]]) prefix = seed.word.copy() seam_slots = slots.copy() actual_labels = strips(dim) + [('edge', *e) for e in edges] + [('frame', root)] actual = principal(actual_labels, dim, weight) from_chars = character_matrix(dim, weight, edges, root, actual_labels) require(actual == [row[:seed.n] for row in from_chars], 'Rooted matrix constructors disagree') if seam != (long, short): reached = [[-seed.rows[i][j] for j in slots] for i in slots] require(reached == actual, 'The local word did not reach the actual tree orientation') for i, j in oriented: if (i, j) != (long, short): reverse(('edge', i, j), rectangle(i, j, dim)) frame = [('frame', root)] for m in range(dim[root] - 1, 0, -1): frame.extend([('t', root, m), ('s', root, m)]) reverse(('frame', root), frame) for i, d in dim.items(): for turn in range(d): which = 's' if turn % 2 == 0 else 't' for k in slot_map(slots, labels, [(which, i, m) for m in range(1, d)]): seed.step(k) p = seed.endpoint() w = seed.word if seam != (long, short): rotated = w[len(prefix):] + [p.index(k) for k in prefix] w = [seam_slots.index(k) for k in rotated] negative = Framed(negate(actual)) for k in w: negative.step(k) p = negative.endpoint() answer = Framed(actual) for k in reversed(w): answer.step(p[k]) answer.endpoint() return answer def main(): parser = argparse.ArgumentParser(description=__doc__) parser.add_argument('cases', nargs='*', metavar='TYPE,RANK,NODE') parser.add_argument('--emit', '--write-word', dest='write_word', type=Path, help='write a one-based word for a single case') args = parser.parse_args() records = json.loads(Path(__file__).with_name('words.json').read_text(encoding='ascii')) gates = {} for entry in records: a, b = entry['long'], entry['short'] require((a, b) not in gates, 'Repeated local word') gates[a, b] = [k - 1 for k in entry['word']] length = verify_gate(a, b, gates[a, b]) print(f'Bond ({a},{b}) verified, {length} mutations') cases = args.cases or ['B,8,2','B,6,3','B,5,4','B,7,5','B,7,6','B,9,7', 'B,2,2','B,3,3','B,4,4','B,5,5','B,6,6','B,7,7', 'C,6,2','C,4,3','C,7,3','C,5,4','C,8,4', 'C,6,5','C,9,5','F,4,1','F,4,2','F,4,4'] require(args.write_word is None or len(cases) == 1, 'Choose one case for word export') for case in cases: kind, n, r = case.upper().split(',') check = verify_tree(kind, int(n), int(r), gates) print(f'{case} residual matrix, rank {check.n}, length {len(check.word)}, red {check.red}') if args.write_word: rec = {'case': case, 'word': [k + 1 for k in check.word], 'terminal_permutation': [k + 1 for k in check.endpoint()], 'red': check.red} args.write_word.write_text(json.dumps(rec) + '\n', encoding='ascii') if __name__ == '__main__': main()