1#!/usr/bin/env python32"""Stage 3 preliminary check (throwaway; superseded by Stage C oracles).341. Verifies the explicit isomorphism psi: P(n,k) -> P(n,l) when k*l == 1 (mod n),5 gcd(k,n) = 1, defined by psi(v_{jk}) = u_j, psi(u_{jk}) = v_j, and the6 complement identification P(n,l) = P(n,n-l), for all 11 <= n <= 60 and7 all l with 5*l == +-1 (mod n). Lists the cases where the partner l' =8 min(l, n-l) is <= 4 (values then follow from the k = 2,3,4 literature).92. Replays the planned 12-vertex forcing order for S = {u_0..u_11} in P(n,5),10 n >= 13, step by step (each force must be legal at the moment it is applied).11"""12from math import gcd1314def P(n, k):15 adj = {}16 def add(a, b):17 if a == b:18 raise ValueError("self loop")19 adj.setdefault(a, set()).add(b); adj.setdefault(b, set()).add(a)20 for i in range(n):21 add(('u', i), ('u', (i + 1) % n)); add(('u', i), ('v', i)); add(('v', i), ('v', (i + k) % n))22 return adj2324def edges(adj):25 return {frozenset((a, b)) for a in adj for b in adj[a]}2627def is_iso_map(adj1, adj2, phi):28 if len(set(phi.values())) != len(adj1) or len(adj1) != len(adj2):29 return False30 return {frozenset((phi[a], phi[b])) for e in edges(adj1) for a, b in [tuple(e)]} == edges(adj2)3132print("== isomorphisms P(n,5) ~ P(n,l), 5*l == +-1 (mod n) ==")33small_partner = []34for n in range(11, 61):35 if gcd(5, n) != 1:36 print(f"n={n}: gcd(n,5)=5, inner subgraph is 5 cycles of length {n//5}; no inversion of 5 mod n")37 continue38 l = pow(5, -1, n) # 5*l == 1 (mod n)39 for ll, sign in ((l, '+1'), ((-l) % n, '-1')):40 if not (ll >= 1 and n > 2 * ll):41 ll_c = n - ll42 else:43 ll_c = ll44 # explicit map P(n,5) -> P(n,l) for 5*l == 145 A = P(n, 5)46 B = P(n, l)47 phi = {}48 for j in range(n):49 phi[('v', (j * 5) % n)] = ('u', j)50 phi[('u', (j * 5) % n)] = ('v', j)51 ok = is_iso_map(A, B, phi)52 # complement identification: P(n,l) ~ P(n,n-l) via v_i -> v_{-i}, u_i -> u_{-i}53 C = P(n, (n - l) % n) if 0 < (n - l) % n else None54 ok2 = C is not None and is_iso_map(B, C, {('u', i): ('u', (-i) % n) for i in range(n)} | {('v', i): ('v', (-i) % n) for i in range(n)})55 break56 partner = min(l, n - l)57 tag = ""58 if partner <= 4:59 tag = f" <-- partner k'={partner}: value known from literature"60 small_partner.append((n, partner))61 print(f"n={n}: 5^-1={l}, partner k'={partner}, explicit map ok={ok}, complement map ok={ok2}{tag}")62print("small partners:", small_partner)6364print("\n== replay of the 12-vertex forcing order, S={u_0..u_11}, P(n,5) ==")65def legal_force(adj, black, src, tgt):66 white = [w for w in adj[src] if w not in black]67 return src in black and white == [tgt]6869for n in range(13, 41):70 adj = P(n, 5)71 black = {('u', i) for i in range(12)}72 seq = [(('u', i), ('v', i)) for i in range(1, 11)] + [(('v', 5), ('v', 0)), (('v', 6), ('v', 11))]73 for j in range(12, n):74 seq += [(('u', j - 1), ('u', j)), (('v', j - 5), ('v', j))]75 ok = True76 for s, t in seq:77 if not legal_force(adj, black, s, t):78 ok = False; print(f"n={n}: ILLEGAL force {s}->{t}"); break79 black.add(t)80 print(f"n={n}: forces={len(seq)}, all legal={ok}, all black={len(black) == 2 * n}")81