#!/usr/bin/env python3 """Exact checks for the three-label, one-bit interlacement test. Run: python3 verify_interlacement.py Requires Python 3.10+ and the standard library. No input files or network. The graphs are simple and labelled. Bit order for the six symmetric table entries is 00, 01, 02, 11, 12, 22, from least to most significant. """ from array import array from fractions import Fraction from itertools import combinations, product from math import comb def require(condition, message): if not condition: raise AssertionError(message) def labels_table(rule): indexing = ((0, 1, 2), (1, 3, 4), (2, 4, 5)) return [[(rule >> index) & 1 for index in row] for row in indexing] def graph_from_word(word): endpoints = {} for i, letter in enumerate(word): endpoints.setdefault(letter, []).append(i) require(all(len(pair) == 2 for pair in endpoints.values()), "invalid word") crossings = set() for u, v in combinations(sorted(endpoints), 2): a, b = endpoints[u] c, d = endpoints[v] if a < c < b < d or c < a < d < b: crossings.add((u, v)) return crossings def counts_by_walsh(n): """Histogram of activated edge sets; take all binary Fourier coefficients.""" edges = list(combinations(range(n), 2)) frequencies = array("i", [0]) * (1 << len(edges)) for label_number in range(3**n): value = label_number roles = [] for _ in range(n): value, role = divmod(value, 3) roles.append(role) mask = 0 for j, (u, v) in enumerate(edges): if (roles[u] + roles[v]) % 3 == 0: mask |= 1 << j frequencies[mask] += 1 half = 1 while half < len(frequencies): for start in range(0, len(frequencies), 2 * half): for a in range(start, start + half): b = a + half x, y = frequencies[a], frequencies[b] frequencies[a], frequencies[b] = x + y, x - y half *= 2 return array("i", ((3**n - bias) // 2 for bias in frequencies)) def colour_columns(n, table): """One bit per assignment in each edge column. No Fourier transform.""" edges = list(combinations(range(n), 2)) columns = [0] * len(edges) for row, colours in enumerate(product(range(3), repeat=n)): for j, (u, v) in enumerate(edges): if table[colours[u]][colours[v]]: columns[j] |= 1 << row return columns def gray_counts(columns): """Update a full truth table by XOR when exactly one graph edge flips.""" graph = 0 truth_table = 0 for step in range(1, 1 << len(columns)): toggle = step & -step graph ^= toggle truth_table ^= columns[toggle.bit_length() - 1] yield graph, truth_table.bit_count() def is_four_cycle(mask, edges, n): if mask.bit_count() != 4: return False degree = [0] * n for j, (a, b) in enumerate(edges): if mask & (1 << j): degree[a] += 1 degree[b] += 1 return degree.count(2) == 4 and degree.count(0) == n - 4 def check_all_graphs(n): edges = list(combinations(range(n), 2)) reference = counts_by_walsh(n) minimum = min(reference[1:]) minimisers = 0 for g, hits in gray_counts(colour_columns(n, labels_table(17))): require(hits == reference[g], f"methods disagree at n={n}, G={g}") require((hits == minimum) == is_four_cycle(g, edges, n), f"unexpected equality case at n={n}, G={g}") if hits == minimum: minimisers += 1 require(minimum * 27 == 8 * 3**n, "wrong sharp bound") require(minimisers == 3 * comb(n, 4), "wrong equality count") print(f"n={n}: {len(reference)-1} graphs, {3**n} colourings, " f"minimum {minimum}, {minimisers} minimisers; both methods agree") def scan_all_uniform_rules(n=6): minima = [] for rule in range(64): columns = colour_columns(n, labels_table(rule)) minima.append(min(hits for _, hits in gray_counts(columns))) top = max(minima) winners = [rule for rule, value in enumerate(minima) if value == top] require(top * 27 == 8 * 3**n and 17 in winners, "rule scan failed") print(f"64 uniform rules on n={n}: {len(winners)} attain {top}/{3**n}") print(f"one off-diagonal pair only: {minima[16]}/{3**n}; " f"equal labels only: {minima[41]}/{3**n}") equal_on_clique = 0 for colours in product(range(3), repeat=5): matching_pairs = sum(colours[i] == colours[j] for i, j in combinations(range(5), 2)) equal_on_clique += matching_pairs % 2 require(equal_on_clique == 60, "K5 example for the equality-only table failed") print(f"equal labels only on K5: {equal_on_clique}/243") def cycle_hits_by_composition(table): """Explicitly enumerate 81 colourings of K2,2 and collect their weights.""" coefficients = {} for labels in product(range(3), repeat=4): a, b, c, d = labels detected = table[a][c] ^ table[b][c] ^ table[a][d] ^ table[b][d] if detected: powers = tuple(labels.count(i) for i in range(3)) coefficients[powers] = coefficients.get(powers, 0) + 1 return coefficients def check_unequal_probabilities(denominator=60): weight_points = [(i, j, denominator - i - j) for i in range(denominator + 1) for j in range(denominator - i + 1)] best = 0 arg_weights = set() for rule in range(64): terms = cycle_hits_by_composition(labels_table(rule)) for weights in weight_points: x, y, z = weights hits = sum(coef * x**i * y**j * z**k for (i, j, k), coef in terms.items()) if hits > best: best = hits arg_weights = {weights} elif hits == best: arg_weights.add(weights) result = Fraction(best, denominator**4) require(result == Fraction(8, 27), "weighted search contradicts theorem") require(arg_weights == {(denominator // 3,) * 3}, "unexpected maximising weights") print(f"C4: {64 * len(weight_points)} rule/weight choices, exact maximum " f"{result}, weights {sorted(arg_weights)} divided by {denominator}") def check_field_identity(n=4): """Compare edge parities with a quadratic over F4 for every graph and labelling.""" edges = list(combinations(range(n), 2)) powers = (1, 2, 3) # 1, w, w^2 = w+1; addition in F4 is bitwise XOR. count = 0 for roles in product(range(3), repeat=n): for g in range(1 << len(edges)): lamp = 0 polynomial = 0 for j, (u, v) in enumerate(edges): if g & (1 << j): exponent = (roles[u] + roles[v]) % 3 lamp ^= int(exponent == 0) polynomial ^= powers[exponent] trace = int(polynomial in (2, 3)) require(lamp == ((g.bit_count() & 1) ^ trace), "trace mismatch") count += 1 print(f"finite-field identity: all {count} graph/colour assignments on n={n}") if __name__ == "__main__": require(not graph_from_word("AABBCCDD"), "expected an empty graph") require(graph_from_word("ABCDBADC") == {("A", "C"), ("A", "D"), ("B", "C"), ("B", "D")}, "wrong C4 witness") print("words AABBCCDD and ABCDBADC realise the empty graph and C4") check_field_identity() for size in (4, 5, 6, 7): check_all_graphs(size) scan_all_uniform_rules() check_unequal_probabilities() print(f"12 independent lamps: {100 * (1 - (19/27)**12):.6f}%")