"""Verify the KR reddening certificates with exact integer arithmetic.""" import argparse import hashlib import json import sys from pathlib import Path sys.dont_write_bytecode = True from kr_matrices import translated_seed EXPECTED_CASES = { ("E", 6, r) for r in (1, 2, 3, 5, 6) } | { ("E", 7, r) for r in (1, 2, 7) } | { ("F", 4, 1), ("F", 4, 4), ("G", 2, 1), ("G", 2, 2) } | { ("B", 3, 3), ("B", 4, 3), ("B", 4, 4), ("B", 5, 3), ("B", 6, 3), ("B", 5, 4), ("B", 5, 5), ("B", 6, 4), ("B", 6, 5), ("B", 7, 5), ("B", 7, 3), ("B", 8, 3), ("C", 4, 3), ("C", 5, 3), ("C", 5, 4), ("C", 6, 3), ("C", 6, 4), ("C", 7, 3), ("D", 5, 3), ("D", 6, 3), ("D", 6, 4), ("D", 7, 3), ("D", 8, 3), ("D", 9, 3) } TWO_WORDS = {("E", 6, 3), ("E", 6, 5), ("G", 2, 1)} def require(condition, message): if not condition: raise ValueError(message) def matrix_digest(matrix): encoded = json.dumps(matrix, separators=(",", ":")).encode("ascii") return hashlib.sha256(encoded).hexdigest() def replay(matrix, word): """Return the endpoint permutation and red count, or reject the word.""" size = len(matrix) extended = [ row + [int(i == j) for j in range(size)] for i, row in enumerate(matrix) ] red = 0 for step, vertex in enumerate(word, 1): require(type(vertex) is int and 1 <= vertex <= size, f"Invalid mutation vertex at step {step}") k = vertex - 1 pivot = extended[k] c_vector = pivot[size:] if min(c_vector) < 0 and max(c_vector) <= 0: red += 1 else: require(min(c_vector) >= 0 and max(c_vector) > 0, f"Coefficient row at step {step} has no color") for i, row in enumerate(extended): if i == k: continue link = row[k] if link: for j, entry in enumerate(pivot): if j != k: row[j] += (max(link, 0) * max(entry, 0) - max(-link, 0) * max(-entry, 0)) row[k] = -link extended[k] = [-entry for entry in pivot] permutation = [] for i, row in enumerate(extended, 1): negative_units = [j for j, v in enumerate(row[size:]) if v == -1] require(len(negative_units) == 1 and sum(abs(v) for v in row[size:]) == 1, f"Final coefficient row {i} is not a negative unit vector") permutation.append(negative_units[0]) require(sorted(permutation) == list(range(size)), "Final columns do not form a permutation") for i, j0 in enumerate(permutation): require(extended[i][:size] == [matrix[j0][k] for k in permutation], f"The restored exchange matrix differs in row {i + 1}") return [j + 1 for j in permutation], red def verify(filename): data = json.loads(filename.read_text(encoding="utf-8")) require(type(data["format_version"]) is int and data["format_version"] == 1, "Unknown certificate format") cases = data["cases"] require(isinstance(cases, list) and len(cases) == len(EXPECTED_CASES), "Unexpected number of cases") seen = set() count = 0 for case in cases: kind, rank, node = case["type"], case["dynkin_rank"], case["node"] key = (kind, rank, node) require(type(rank) is int and type(node) is int and key in EXPECTED_CASES and key not in seen, f"Unexpected or repeated case {key!r}") seen.add(key) label = f"{kind}{rank},{node}" matrix = translated_seed(kind, rank, node)["principal"] require(type(case["principal_rank"]) is int and len(matrix) == case["principal_rank"], f"{label} has an incorrect principal rank") require(matrix_digest(matrix) == case["matrix_sha256"], f"{label} has an incorrect matrix digest") certificates = case["certificates"] require(isinstance(certificates, list) and len(certificates) == (2 if key in TWO_WORDS else 1), f"{label} has an unexpected number of words") seen_words = set() for index, cert in enumerate(certificates, 1): word = cert["word"] require(isinstance(word, list) and type(cert["length"]) is int and len(word) == cert["length"], f"{label} word {index} has an incorrect length") endpoint, red = replay(matrix, word) require(tuple(word) not in seen_words, f"{label} contains a duplicate word") seen_words.add(tuple(word)) p = cert["end_permutation"] require(isinstance(p, list) and all(type(v) is int for v in p) and endpoint == p, f"{label} word {index} has an incorrect endpoint permutation") require(type(cert["red_mutations"]) is int and red == cert["red_mutations"], f"{label} word {index} has an incorrect count of red mutations") print(f"{label:5} rank {len(matrix):2} length {len(word):4} red {red:3}") count += 1 require(seen == EXPECTED_CASES, "The set of certified cases is incomplete") print(f"Verified {count} words for {len(seen)} cases.") if __name__ == "__main__": parser = argparse.ArgumentParser(description=__doc__) parser.add_argument("file", type=Path, nargs="?", default=Path(__file__).resolve().with_name("reddening_words.json")) try: verify(parser.parse_args().file) except (KeyError, TypeError, ValueError, OSError) as exc: sys.exit(f"Verification failed: {exc}")