#!/usr/bin/env python3 """Exact checks for the three-role parity fingerprint (Python 3.10+). python3 verify_three_roles.py --small # five witnesses and all n=4 graphs; stdlib python3 verify_three_roles.py # all 64 tables and all n=4..7 graphs; NumPy Entry bits, least significant first: 00, 01, 02, 11, 12, 22. No network, external data, random numbers, or graph-isomorphism library. """ import argparse from fractions import Fraction from itertools import combinations, combinations_with_replacement, product from math import comb from collections import Counter ENTRIES = tuple(combinations_with_replacement(range(3), 2)) INDEX = {(a, b): i for i, (a, b) in enumerate(ENTRIES)} INDEX.update({(b, a): i for i, (a, b) in enumerate(ENTRIES)}) BOUND = Fraction(8, 27) F0 = 17 IDENTITY = 41 def checked(condition, message): if not condition: raise AssertionError(message) def graph_edges(n): return tuple(combinations(range(n), 2)) def candidates(): """Return the 21 tables and metadata (k, singled-out role or None, complement).""" winners = {} rejected = set() for k in range(3): fixed = 2 * k % 3 for role in (None, 0, 1, 2): for complement in (0, 1): def bit(a, b): return ((a + b) % 3 == k) ^ (a == role) ^ (b == role) ^ complement table = sum(int(bit(a, b)) << i for i, (a, b) in enumerate(ENTRIES)) if complement and role == fixed: rejected.add(table) else: checked(table not in winners, "duplicate table") winners[table] = (k, role, complement) checked(len(winners) == 21 and len(rejected - winners.keys()) == 3, "family sizes") return winners def hits(n, edges, table): """Direct definition, one sum modulo two per colouring.""" return sum(sum((table >> INDEX[roles[u], roles[v]]) & 1 for u, v in edges) % 2 for roles in product(range(3), repeat=n)) def witnesses(): return [ ("C4", 4, ((0, 2), (0, 3), (1, 2), (1, 3))), ("K2", 2, graph_edges(2)), ("K3", 3, graph_edges(3)), ("K4", 4, graph_edges(4)), ("K5", 5, graph_edges(5)), ] def check_witnesses(family): remaining = set(range(64)) tallies = {} for name, n, edges in witnesses(): values = [hits(n, edges, t) for t in range(64)] tallies[name] = values remaining = {t for t in remaining if Fraction(values[t], 3**n) >= BOUND} print(f"{name}: {len(remaining)} survive") if name == "K4": checked(remaining == set(family) | {IDENTITY}, "four-vertex witnesses") checked(remaining == set(family), "five witnesses vs. symbolic family") checked(tallies["K4"][47] == 20 and tallies["K5"][IDENTITY] == 60, "K4/K5 counterexamples") print("n >= 5 candidate IDs:", sorted(remaining)) print("extra ID at n=4:", IDENTITY) print("without a nonconstant gauge:", sorted(t for t, (_, r, _) in family.items() if r is None)) def bipartite_masks(n, p, q): """All labelled copies of K[p,q] plus isolated vertices, in edge-bit order.""" edge_bit = {pair: 1 << i for i, pair in enumerate(graph_edges(n))} masks = set() for vertices in combinations(range(n), p + q): for left in combinations(vertices, p): right = set(vertices) - set(left) mask = sum(edge_bit[min(u, v), max(u, v)] for u in left for v in right) masks.add(mask) return masks def check_direct_four(family): edges = graph_edges(4) graphs = [tuple(edge for j, edge in enumerate(edges) if mask & (1 << j)) for mask in range(1, 1 << len(edges))] minima = [min(hits(4, graph, t) for graph in graphs) for t in range(64)] checked({t for t, v in enumerate(minima) if v == 24} == set(family) | {IDENTITY} and max(minima) == 24, "direct 4-vertex exhaustive check") ieq = {mask for mask, graph in enumerate(graphs, 1) if hits(4, graph, IDENTITY) == 24} checked(ieq == bipartite_masks(4, 2, 2), "I3 equality at n=4") print("n=4 direct parity: 63 graphs x 64 tables x 81 colourings") def check_weight_grid(denominator=60): """Weighted C4 count from its nine unordered row/column rectangles.""" pairs = tuple(combinations(range(3), 2)) rectangles = [] for table in range(64): def bit(a, b): return (table >> INDEX[a, b]) & 1 rectangles.append([(a, b, c, d) for a, b in pairs for c, d in pairs if bit(a, c) ^ bit(b, c) ^ bit(a, d) ^ bit(b, d)]) best = 0 best_weights = set() for a in range(denominator + 1): for b in range(denominator - a + 1): w = (a, b, denominator - a - b) top = max(4 * sum(w[i] * w[j] * w[k] * w[l] for i, j, k, l in odd) for odd in rectangles) if top > best: best = top best_weights.clear() if top == best: best_weights.add(w) checked(Fraction(best, denominator**4) == BOUND and best_weights == {(denominator // 3,) * 3}, "weighted grid") print(f"C4: {64 * comb(denominator + 2, 2)} table/weight pairs; maximum {BOUND}") def check_trace_model(): """Multiplication table uses 0, 1, omega, omega^2 in a polynomial basis.""" mul = ((0, 0, 0, 0), (0, 1, 2, 3), (0, 2, 3, 1), (0, 3, 1, 2)) elements = (1, 2, 3) for k, g, complement in product(range(3), (None, 0, 1, 2), range(2)): fixed = 2 * k % 3 t = 0 if g is None else elements[(fixed - g) % 3] d = mul[t][t] for i, j in product(range(3), repeat=2): x, y = elements[(i - fixed) % 3], elements[(j - fixed) % 3] field_value = mul[x][y] ^ mul[d][mul[x][x] ^ mul[y][y]] bit = ((i + j) % 3 == k) ^ (i == g) ^ (j == g) ^ complement checked(bit == (1 ^ complement ^ (field_value in (2, 3))), "trace identity") pinned = Counter(mul[x][y] ^ x ^ y for x in elements for y in elements) checked([pinned[j] for j in range(4)] == [2, 5, 1, 1], "pinned K2") print("All 24 field identities hold on each of the nine role pairs; pinned K2 checked.") def all_counts(n, table, edge_indices, np): """Walsh transform of the exact multiplicities of the activated edge sets.""" num_masks = 1 << len(edge_indices) masks = np.zeros(3**n, dtype=np.int32) for j, entry in enumerate(edge_indices): active = (table >> entry.astype(np.int32)) & 1 masks |= active << j # Absolute values throughout are bounded by 3**7; use signed int32. spectrum = np.bincount(masks, minlength=num_masks).astype(np.int32) half = 1 while half < num_masks: blocks = spectrum.reshape(-1, 2 * half) left = blocks[:, :half].copy() right = blocks[:, half:] np.add(left, right, out=blocks[:, :half]) np.subtract(left, right, out=right) half *= 2 return (3**n - spectrum) // 2 def full_scan(n, family, np): roles = np.array(tuple(product(range(3), repeat=n)), dtype=np.uint8) index = np.array([[INDEX[a, b] for b in range(3)] for a in range(3)], dtype=np.uint8) edge_indices = [index[roles[:, u], roles[:, v]] for u, v in graph_edges(n)] c4 = bipartite_masks(n, 2, 2) p3 = bipartite_masks(n, 1, 2) k24 = bipartite_masks(n, 2, 4) threshold = 8 * 3**(n-3) winners = set() for table in range(64): counts = all_counts(n, table, edge_indices, np) minimum = int(counts[1:].min()) checked(minimum <= threshold, (n, table, minimum)) if minimum == threshold: winners.add(table) equal = set(np.flatnonzero(counts == threshold).tolist()) expected = c4 if table in family and family[table][1] is not None: expected = c4 | p3 checked(equal == expected, ("first equality", n, table, len(equal))) if table == F0: second = int(counts[counts > minimum].min()) if n >= 6: checked(Fraction(second, 3**n) == Fraction(80, 243), ("second", n)) checked(set(np.flatnonzero(counts == second).tolist()) == k24, ("second equality", n)) else: checked(Fraction(second, 3**n) == Fraction(1, 3), ("second", n)) base_summary = (minimum, len(c4), second, int(np.count_nonzero(counts == second))) expected = set(family) | ({IDENTITY} if n == 4 else set()) checked(winners == expected and len(c4) == 3 * comb(n, 4), ("winners", n)) m, a, s, b = base_summary print(f"n={n}: {2**len(edge_indices)-1} nonempty graphs, {len(winners)} tables; " f"F0 minima {m}/{3**n} ({a} graphs), then {s}/{3**n} ({b} graphs)", flush=True) def main(): parser = argparse.ArgumentParser(description=__doc__) parser.add_argument("--small", action="store_true", help="use only the standard library") options = parser.parse_args() family = candidates() check_witnesses(family) check_direct_four(family) check_weight_grid() check_trace_model() if not options.small: import numpy as np for n in range(4, 8): full_scan(n, family, np) print("All requested checks passed.") if __name__ == "__main__": main()