"""Verify local DT certificates and the two base tests for infinite end repetition. The proof of arbitrary repetition is in repeated_extension.tex. This program checks its finite input, not an arbitrary truncation of that theorem. """ import argparse import hashlib import json from pathlib import Path import time import verify as v HERE = Path(__file__).resolve().parent def read_and_verify(path): record = json.loads(path.read_text()) a, b = record['long'], record['short'] labels = v.strips({0: a, 1: b}) + [('edge', 0, 1)] B = v.principal(labels, {0: a, 1: b}, {0: 1, 1: 2}) word = [k - 1 for k in record['word']] seed = v.Framed(B) for k in word: seed.step(k) permutation = seed.endpoint() v.require(permutation == [k - 1 for k in record['terminal_permutation']], 'Local terminal permutation differs from its certificate') if 'red' in record: v.require(seed.red == record['red'], 'Local red count differs') opposite_word = [permutation[k] for k in reversed(word)] return a, b, labels, v.negate(B), opposite_word, { 'pair': [a, b], 'rank': len(B), 'length': len(word), 'red': seed.red, 'file': path.name, 'sha256': hashlib.sha256(path.read_bytes()).hexdigest(), } def corner(labels, B, word, color, height): n = len(B) i = labels.index(('s', color, height)) j = labels.index(('t', color, height)) # The probe has the same weight as its sole neighbor, so its two entries # are +1 and -1, even when other old vertices have different weights. A = [row + [0] for row in B] + [[0] * (n + 1)] A[n][i], A[i][n] = 1, -1 seed = v.Framed(A) for k in word: seed.step(k) old_coefficients = [row[n + 1:2 * n + 1] for row in seed.rows[:n]] v.require(sorted(old_coefficients) == sorted(v.negate(v.identity(n))), 'The probe changed the isolated old reddening endpoint') H = seed.rows[n][n + 1:] v.require(H[-1] == 1 and min(H) >= 0, 'Incorrect probe coefficient row') return {'side': color, 'i': i + 1, 'j': j + 1, 'corner': H[j], 'row': H} def main(): parser = argparse.ArgumentParser(description=__doc__) parser.add_argument('--all', action='store_true', help='also replay every supplied local DT certificate') parser.add_argument('--output', type=Path) args = parser.parse_args() started = time.monotonic() base = HERE / 'certificates' / 'local_10_10.json' files = sorted((HERE / 'certificates').glob('local_*.json')) if args.all else [base] records = [] for path in files: a, b, labels, B, word, record = read_and_verify(path) records.append(record) print(f'Local ({a},{b}) verified: rank {len(B)}, length {len(word)}', flush=True) if path == base: probes = [corner(labels, B, word, 0, a - 1), corner(labels, B, word, 1, 1)] saved = json.loads((HERE / 'certificates' / 'corners_10_10.json').read_text()) v.require(saved['sha256'] == record['sha256'], 'Base file digest changed') v.require(probes == saved['corners'], 'Saved corner rows differ') v.require(all(z['corner'] <= 2 for z in probes), 'Base end test failed') print('Both (10,10) end tests verified: H = 2, 2', flush=True) output = {'verified': True, 'records': records, 'base_corners': probes, 'seconds': time.monotonic() - started} if args.output: args.output.write_text(json.dumps(output, indent=2) + '\n') if __name__ == '__main__': main()