"""Construct compact reddening words for every -Q(a,b), a,b >= 2. The default output is a recursive grammar, never an expanded mutation list. All external vertex indices are one-based. Internal indices are zero-based. The proof is in uniform_extension.tex; finite replay is an independent check. """ import argparse import hashlib import json import os from pathlib import Path import sys import tempfile import verify as spectral BASE_WORD = (5, 4, 2, 5, 4, 2, 5, 1, 4, 3, 5, 2, 3, 1, 4, 3, 1, 4, 1, 2, 3, 5) DEFAULT_MAX_MUTATIONS = 2_000_000 def require(condition, message): if not condition: raise ValueError(message) def matrix_digest(matrix): payload = json.dumps(matrix, separators=(",", ":")).encode("ascii") return hashlib.sha256(payload).hexdigest() def local_seed(a, b): dimensions = {0: a, 1: b} labels = spectral.strips(dimensions) + [("edge", 0, 1)] matrix = spectral.negate(spectral.principal(labels, dimensions, {0: 1, 1: 2})) weights = [1 if label[1] == 0 and label[0] != "edge" else 2 for label in labels] require(all(weights[i] * matrix[i][j] == -weights[j] * matrix[j][i] for i in range(len(matrix)) for j in range(len(matrix))), "Canonical matrix has an incorrect left symmetrizer") return labels, matrix, weights def growth_sides(a, b): """Alternate to the smaller dimension, then repeat the required end.""" require(type(a) is int and type(b) is int and a >= 2 and b >= 2, "This constructive grammar requires integer dimensions a,b >= 2") balanced = min(a, b) return [side for _ in range(balanced - 2) for side in (0, 1)] + \ [0] * (a - balanced) + [1] * (b - balanced) def build_grammar(a, b): sides = growth_sides(a, b) long_dimension = short_dimension = 2 nodes = [] previous_labels = previous_matrix = None length = len(BASE_WORD) for step, side in enumerate([None] + sides): if side is not None: long_dimension += side == 0 short_dimension += side == 1 length = 3 * length + 2 labels, matrix, weights = local_seed(long_dimension, short_dimension) rank = len(labels) node = { "id": step, "pair": [long_dimension, short_dimension], "rank": rank, "labels": [list(label) for label in labels], "left_symmetrizer": weights, "initial_matrix_sha256": matrix_digest(matrix), "word_length": length, } if side is None: node["word"] = list(BASE_WORD) else: lookup = {label: i for i, label in enumerate(labels)} embedding = [] for kind, color, height in previous_labels: if side == 1 and kind in ("s", "t") and color == 1: height += 1 embedding.append(lookup[(kind, color, height)]) retained = set(embedding) extra = [i for i in range(rank) if i not in retained] require(len(extra) == 2, "Extension did not add exactly two vertices") u, v = extra require(labels[u][0] == "s" and labels[v][0] == "t", "New vertices have the wrong order") old_dimension = (long_dimension - 1 if side == 0 else short_dimension - 1) height = old_dimension - 1 if side == 0 else 1 old_i = previous_labels.index(("s", side, height)) old_j = previous_labels.index(("t", side, height)) i, j = embedding[old_i], embedding[old_j] require(all(matrix[embedding[r]][embedding[c]] == previous_matrix[r][c] for r in range(len(embedding)) for c in range(len(embedding))), "The stated principal embedding does not preserve the old matrix") require(all(matrix[u][k] == (-1 if k == j else 0) and matrix[v][k] == (1 if k == i else 0) for k in embedding), "Extension does not have the required two unit attachments") require(matrix[u][v] == 2, "The new pair does not have exchange entry two") node.update({ "parent": step - 1, "grow": "long" if side == 0 else "short", "embedding": [k + 1 for k in embedding], "u": u + 1, "v": v + 1, "old_source_column": i + 1, "old_target_column": j + 1, }) nodes.append(node) previous_labels, previous_matrix = labels, matrix return { "format": "KR-two-strip-reddening-grammar-v1", "matrix_convention": "opposite spectral matrix -Q(a,b); row framing [B|I]", "indexing": "one-based vertex slots; chronological mutation words", "matrix_digest_encoding": "SHA256 of the dense integer matrix in compact ASCII JSON", "rule": "R_new = embed(R_parent), u, reverse(embed(R_parent)), v, embed(R_parent)", "construction": "alternate long and short to min(a,b), then repeat the remaining end", "target_pair": [a, b], "target_node": len(nodes) - 1, "word_length": length, "verification_mutations": sum(node["word_length"] for node in nodes), "nodes": nodes, } def iter_word(grammar, level=None, reverse=False, mapping=None): """Stream zero-based physical slots using an explicit stack, not recursion. Mapping sends the chosen node's vertices to slots of a larger matrix. Reversal reverses the chronological word; it does not permute its labels. """ nodes = grammar["nodes"] if level is None: level = grammar["target_node"] if mapping is None: mapping = tuple(range(nodes[level]["rank"])) else: mapping = tuple(mapping) stack = [("node", level, reverse, mapping)] while stack: task = stack.pop() if task[0] == "pivot": yield task[1] continue _, current, backwards, slots = task node = nodes[current] if current == 0: base = reversed(node["word"]) if backwards else node["word"] for k in base: yield slots[k - 1] continue subslots = tuple(slots[k - 1] for k in node["embedding"]) parent = node["parent"] u, v = slots[node["u"] - 1], slots[node["v"] - 1] if backwards: chronological = [("node", parent, True, subslots), ("pivot", v), ("node", parent, False, subslots), ("pivot", u), ("node", parent, True, subslots)] else: chronological = [("node", parent, False, subslots), ("pivot", u), ("node", parent, True, subslots), ("pivot", v), ("node", parent, False, subslots)] stack.extend(reversed(chronological)) class StreamingFramed(spectral.Framed): """Use the independent integer matrix mutation without retaining the word.""" def __init__(self, matrix): super().__init__(matrix) self.mutations = 0 def step(self, k): require(type(k) is int and 0 <= k < self.n, "Invalid mutation slot") coefficient = self.rows[k][self.n:] positive = any(x > 0 for x in coefficient) negative = any(x < 0 for x in coefficient) require(positive != negative, "Pivot coefficient row has no coherent tropical sign") self.red += negative self.mutations += 1 spectral.mutate(self.rows, k) def endpoint_on_core(state, matrix, mapping, weights): """Check the full old C block and the permuted old principal B block.""" ambient_rank = state.n rank = len(mapping) retained = set(mapping) permutation = [] for slot in mapping: coefficients = state.rows[slot][ambient_rank:] require(all(coefficients[k] == 0 for k in range(ambient_rank) if k not in retained), "Old coefficient row acquired an exterior initial coordinate") nonzero = [j for j, col in enumerate(mapping) if coefficients[col] != 0] require(len(nonzero) == 1 and coefficients[mapping[nonzero[0]]] == -1, "Terminal old coefficient block is not a negative permutation") permutation.append(nonzero[0]) require(sorted(permutation) == list(range(rank)), "Terminal old C block is singular") require(all(weights[i] == weights[permutation[i]] for i in range(rank)), "Terminal permutation does not preserve the symmetrizer") principal = [[state.rows[mapping[i]][mapping[j]] for j in range(rank)] for i in range(rank)] require(principal == [[matrix[permutation[i]][permutation[j]] for j in range(rank)] for i in range(rank)], "Terminal principal block is incorrect") return permutation, principal def verify_grammar(grammar, maximum_mutations=DEFAULT_MAX_MUTATIONS): """Replay each level once, checking the source for the following extension. Each replay includes both boundary probes. At a nonfinal level the next extension's new v is one of the probes, allowing a complete source test without a separate replay. Only the corner used by the next extension is required to be <=2; the opposite corner may legitimately be larger. """ total_expected = grammar["verification_mutations"] require(maximum_mutations >= 1, "The mutation limit must be positive") require(total_expected <= maximum_mutations, "Verification needs {:,} mutations, exceeding --max-mutations {:,}; " "raise that option explicitly to proceed".format(total_expected, maximum_mutations)) nodes = grammar["nodes"] records = [] total = 0 for level, node in enumerate(nodes): a, b = node["pair"] labels, matrix, weights = local_seed(a, b) rank = len(matrix) require(matrix_digest(matrix) == node["initial_matrix_sha256"], "Matrix digest mismatch") boundary_s = [labels.index(("s", 0, a - 1)), labels.index(("s", 1, 1))] boundary_t = [k + 1 for k in boundary_s] source = None if level + 1 < len(nodes): following = nodes[level + 1] next_labels, ambient, _ = local_seed(*following["pair"]) next_rank = len(ambient) mapping = [k - 1 for k in following["embedding"]] grow = 0 if following["grow"] == "long" else 1 u, v = following["u"] - 1, following["v"] - 1 ambient = [row + [0] for row in ambient] + [[0] * (next_rank + 1)] other = 1 - grow other_source = mapping[boundary_s[other]] ambient[next_rank][other_source] = 1 ambient[other_source][next_rank] = -1 probes = [None, None] probes[grow], probes[other] = v, next_rank corner_columns = [mapping[k] for k in boundary_t] ambient_labels = [list(label) for label in next_labels] + [["probe", other]] require(all(ambient[mapping[i]][mapping[j]] == matrix[i][j] for i in range(rank) for j in range(rank)), "Incorrect retained matrix") i, j = mapping[boundary_s[grow]], mapping[boundary_t[grow]] require(all(ambient[u][k] == (-1 if k == j else 0) and ambient[v][k] == (1 if k == i else 0) for k in mapping), "Incorrect source-extension attachments") require(ambient[u][v] == 2, "Incorrect source-extension pair") source = {"grow": following["grow"], "u": u, "v": v, "principal_rank": next_rank, "grow_side": grow} else: mapping = list(range(rank)) ambient = [row + [0, 0] for row in matrix] + [[0] * (rank + 2) for _ in range(2)] probes = [rank, rank + 1] corner_columns = boundary_t for side in (0, 1): ambient[probes[side]][boundary_s[side]] = 1 ambient[boundary_s[side]][probes[side]] = -1 ambient_labels = [list(label) for label in labels] + [["probe", 0], ["probe", 1]] state = StreamingFramed(ambient) for k in iter_word(grammar, level=level, mapping=mapping): state.step(k) require(state.mutations == node["word_length"], "Recursive word length mismatch") permutation, principal = endpoint_on_core(state, matrix, mapping, weights) if level == 0: require(state.red == 0 and permutation == [0, 1, 2, 4, 3], "The stated 22-letter base certificate failed") full_rows = [state.rows[k][state.n:] for k in probes] corners = [full_rows[side][corner_columns[side]] for side in (0, 1)] for side, row in enumerate(full_rows): require(row[probes[side]] == 1 and all(x >= 0 for x in row), "An unmutated probe lost its positive unit coordinate") checked_source = None if source is not None: u, v, grow = source["u"], source["v"], source["grow_side"] unit = [int(k == u) for k in range(state.n)] require(state.rows[u][state.n:] == unit, "The new negative attachment did not retain its unit coefficient row") require(corners[grow] <= 2, "The required extension corner exceeds two") require(all(state.rows[u][k] >= 0 for k in range(source["principal_rank"])), "The new u is not a source in the entire proposed extension") require(state.rows[u][v] == 2 - corners[grow], "Exchange/corner compatibility failed") checked_source = { "grow": source["grow"], "corner": corners[grow], "u": u + 1, "v": v + 1, "unit_coefficient_row": True, "full_source_row_nonnegative": True, "new_pair_exchange_entry": state.rows[u][v], } record = { "pair": [a, b], "rank": rank, "word_length": state.mutations, "red_pivots": state.red, "terminal_permutation": [k + 1 for k in permutation], "terminal_principal_sha256": matrix_digest(principal), "terminal_coefficient_sha256": matrix_digest( [[-int(j == permutation[i]) for j in range(rank)] for i in range(rank)]), "corners_long_short": corners, "probe_rows_old_initial_columns": [[row[k] for k in mapping] for row in full_rows], "probe_rows_full": full_rows, "ambient_labels": ambient_labels, "probe_slots": [k + 1 for k in probes], "corner_columns": [k + 1 for k in corner_columns], "next_source_test": checked_source, } records.append(record) total += state.mutations require(total == total_expected, "Total streamed mutation count mismatch") return { "verified": True, "arithmetic": "Python arbitrary-precision integers", "checks": ["every pivot sign", "terminal C=-P", "terminal B=P B_initial P^T", "weight-preserving permutation", "both full boundary probe rows", "all required extension attachments and complete source conditions"], "total_mutations": total, "records": records, } def write_json(result, destination): text = json.dumps(result, indent=2) + "\n" if destination is None: sys.stdout.write(text) return path = Path(destination) path.parent.mkdir(parents=True, exist_ok=True) temporary = None try: with tempfile.NamedTemporaryFile(mode="w", encoding="utf-8", dir=path.parent, prefix=path.name + ".", suffix=".tmp", delete=False) as stream: temporary = Path(stream.name) stream.write(text) os.replace(temporary, path) finally: if temporary is not None and temporary.exists(): temporary.unlink() def main(argv=None): parser = argparse.ArgumentParser( description="Construct a compact chronological reddening grammar for -Q(a,b), a,b>=2.", epilog="The default never expands the word. --verify replays all levels with exact " "integer matrices. --emit-word includes the final expanded one-based list. " "Both operations are guarded by --max-mutations; long words grow exponentially.") parser.add_argument("a", type=int, help="long-strip dimension, at least 2") parser.add_argument("b", type=int, help="short-strip dimension, at least 2") parser.add_argument("--output", type=Path, help="write JSON atomically to this path (default: stdout)") parser.add_argument("--verify", action="store_true", help="stream and verify all levels and source tests") parser.add_argument("--emit-word", action="store_true", help="include the expanded final mutation word") parser.add_argument("--max-mutations", type=int, default=DEFAULT_MAX_MUTATIONS, help="explicit ceiling for verification or expansion (default: %(default)s)") args = parser.parse_args(argv) try: require(args.max_mutations >= 1, "--max-mutations must be positive") grammar = build_grammar(args.a, args.b) if args.verify: grammar["verification"] = verify_grammar(grammar, args.max_mutations) if args.emit_word: require(grammar["word_length"] <= args.max_mutations, "Word expansion needs {:,} entries, exceeding --max-mutations {:,}; " "raise that option explicitly to proceed".format( grammar["word_length"], args.max_mutations)) grammar["expanded_word"] = [k + 1 for k in iter_word(grammar)] require(len(grammar["expanded_word"]) == grammar["word_length"], "Expanded word length mismatch") write_json(grammar, args.output) except (ValueError, OSError) as error: parser.error(str(error)) return 0 if __name__ == "__main__": raise SystemExit(main())