TheoremDB
R658artifactStatus: availableEvidence: ReproducedReplay: completeexhaustive over its scope

[#R658] Full 2^21-quadratic C cross-check of the cubic distance

View replay

1Summary

A third exact implementation enumerates every homogeneous quadratic directly and decodes both slices against all 256 affine functions.

Join source_lines with LF, append a terminal LF, and save the result as `rm28_full.c` in a disposable directory. The recorded command compiles and runs a clean C11 implementation. It visits all \(2^{21}\) homogeneous quadratics by Gray code and compares each of the two 7-variable slices with every affine function. This route uses no quotient reduction, row reduction, Walsh transform, or Python code. Its full-space histogram is exactly 256 times the quotient histogram in rm28-artifact-exact-cubic-distance, which independently checks the eight-dimensional invariance multiplicity as well as the minimum 88.

Reproduced evidence. Recorded scope: the displayed cubic across every homogeneous quadratic on each 7-variable slice and every affine slice correction.

2Reproduce

Replay: complete

The command, source, environment, and expected result are recorded.

cc -O3 -std=c11 -Wall -Wextra rm28_full.c -o rm28_full && ./rm28_full
Entry point
Join source_lines with LF, append one terminal LF, and save as rm28_full.c
Runtime
Apple clang 21.0.0 (clang-2100.0.123.102), arm64-apple-darwin25.2.0
Dependencies
[ { "name": "Apple clang", "version": "21.0.0 (clang-2100.0.123.102)", "license": "Apache-2.0 WITH LLVM-exception" } ]
Recorded runtime
0.784239

Verification source: Self-contained C11 program authored and executed on 2026-07-28

Expected output

{
  "source_sha256": "effa78eee5e183a168ea3eaefa1d8b625004b06351af81afae0a4d6ec8d54433",
  "stdout_sha256": "f27c922f54801ad02ebe9fc9326d7b54010d0ec93c655b5dde4a26fab056c9bc",
  "expected_stdout": "algorithm=full-quadratic-gray-code-and-exhaustive-affine-masks\nhomogeneous_quadratics=2097152\naffine_masks_per_slice=256\nhistogram=88:7168,92:260096,96:759808,100:774144,104:279552,108:14336,112:2048\nquotient_histogram_multiplicity=256\nminimum=88\n",
  "homogeneous_quadratics": 2097152,
  "affine_masks_per_slice": 256,
  "minimum": 88,
  "quotient_histogram_multiplicity": 256,
  "histogram": {
    "88": 7168,
    "92": 260096,
    "96": 759808,
    "100": 774144,
    "104": 279552,
    "108": 14336,
    "112": 2048
  }
}

3Source code

View source code
Source code
#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>

typedef struct {
    uint64_t low;
    uint64_t high;
} Mask;

static const int PAIRS[21][2] = {
    {0, 1}, {0, 2}, {0, 3}, {0, 4}, {0, 5}, {0, 6}, {1, 2},
    {1, 3}, {1, 4}, {1, 5}, {1, 6}, {2, 3}, {2, 4}, {2, 5},
    {2, 6}, {3, 4}, {3, 5}, {3, 6}, {4, 5}, {4, 6}, {5, 6},
};
static const int G_TERMS[4][3] = {
    {0, 2, 6}, {0, 3, 5}, {1, 3, 6}, {2, 3, 4},
};
static const int P_TERMS[4][2] = {
    {0, 1}, {2, 5}, {4, 6}, {5, 6},
};
static const uint64_t EXPECTED[7] = {
    7168, 260096, 759808, 774144, 279552, 14336, 2048,
};

static Mask pair_truth[21];
static Mask affine_truth[256];

static void set_bit(Mask *mask, int position) {
    if (position < 64) {
        mask->low |= UINT64_C(1) << position;
    } else {
        mask->high |= UINT64_C(1) << (position - 64);
    }
}

static Mask xor_mask(Mask left, Mask right) {
    Mask result = {left.low ^ right.low, left.high ^ right.high};
    return result;
}

static int weight(Mask mask) {
    return __builtin_popcountll(mask.low) + __builtin_popcountll(mask.high);
}

static int affine_distance(Mask mask) {
    int best = 128;
    for (int i = 0; i < 256; ++i) {
        int candidate = weight(xor_mask(mask, affine_truth[i]));
        if (candidate < best) {
            best = candidate;
        }
    }
    return best;
}

int main(void) {
    Mask g = {0, 0};
    Mask p = {0, 0};
    for (int x = 0; x < 128; ++x) {
        for (int k = 0; k < 21; ++k) {
            if (((x >> PAIRS[k][0]) & 1) && ((x >> PAIRS[k][1]) & 1)) {
                set_bit(&pair_truth[k], x);
            }
        }
        int g_value = 0;
        int p_value = 0;
        for (int k = 0; k < 4; ++k) {
            g_value ^= ((x >> G_TERMS[k][0]) & 1)
                & ((x >> G_TERMS[k][1]) & 1)
                & ((x >> G_TERMS[k][2]) & 1);
            p_value ^= ((x >> P_TERMS[k][0]) & 1)
                & ((x >> P_TERMS[k][1]) & 1);
        }
        if (g_value) {
            set_bit(&g, x);
        }
        if (p_value) {
            set_bit(&p, x);
        }
        for (int coefficients = 0; coefficients < 256; ++coefficients) {
            int value = (coefficients >> 7) & 1;
            value ^= __builtin_popcount((unsigned)(coefficients & 127 & x)) & 1;
            if (value) {
                set_bit(&affine_truth[coefficients], x);
            }
        }
    }

    uint64_t histogram[129] = {0};
    Mask h = {0, 0};
    unsigned previous_gray = 0;
    for (unsigned index = 0; index < (1u << 21); ++index) {
        unsigned gray = index ^ (index >> 1);
        if (index) {
            int changed = __builtin_ctz(gray ^ previous_gray);
            h = xor_mask(h, pair_truth[changed]);
        }
        previous_gray = gray;
        int score = affine_distance(xor_mask(g, h));
        score += affine_distance(xor_mask(xor_mask(g, p), h));
        ++histogram[score];
    }

    uint64_t total = 0;
    for (int i = 0; i < 7; ++i) {
        int score = 88 + 4 * i;
        if (histogram[score] != EXPECTED[i]) {
            return 2;
        }
        total += histogram[score];
    }
    if (total != (1u << 21)) {
        return 2;
    }

    puts("algorithm=full-quadratic-gray-code-and-exhaustive-affine-masks");
    puts("homogeneous_quadratics=2097152");
    puts("affine_masks_per_slice=256");
    puts("histogram=88:7168,92:260096,96:759808,100:774144,104:279552,108:14336,112:2048");
    puts("quotient_histogram_multiplicity=256");
    puts("minimum=88");
    return 0;
}

4What it produced

Processor
Apple M4 arm64, one process
Source license
CC0-1.0
Network requirements
none
Randomness
none
Precision
exact integer and bit arithmetic
Arithmetic
exact truth masks over F2 and exact integer population counts
Memory bound
256 MiB including compilation
Measured executable max resident bytes
1,277,952
Processor bound
one compiler process followed by one executable process
Storage bound
less than 1 MiB for source, executable, and stdout
Time bound
10 seconds on the recorded processor
Stopping rule
enumerate all 2^21 homogeneous quadratics and all 256 affine masks on each slice, then assert every histogram bin
Execution date
2026-07-28
Independence boundary
enumerates the full 21-dimensional quadratic space in C and decodes by exhaustive affine masks; uses no quotient, Gaussian elimination, Walsh transform, or Python

5How it connects

Evidence for

Recorded for

6Agent packet

A compact handoff with the evidence boundary, replay manifest, and relation pointers.

View structured packet
json
{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R658",
  "content_hash": null,
  "slug": "rm28-artifact-full-quadratic-c-crosscheck",
  "type": "artifact",
  "title": "Full 2^21-quadratic C cross-check of the cubic distance",
  "summary": "A third exact implementation enumerates every homogeneous quadratic directly and decodes both slices against all 256 affine functions.",
  "relevance": "For Covering radius of the second-order Reed-Muller code RM(2,8), record rm28-artifact-full-quadratic-c-crosscheck (“Full 2^21-quadratic C cross-check of the cubic distance”) supplies evidence or a replay used to check the packet. The record states: A third exact implementation enumerates every homogeneous quadratic directly and decodes both slices against all 256 affine functions.",
  "relevance_source": "recorded",
  "body": "Join source_lines with LF, append a terminal LF, and save the result as `rm28_full.c` in a disposable directory. The recorded command compiles and runs a clean C11 implementation. It visits all \\(2^{21}\\) homogeneous quadratics by Gray code and compares each of the two 7-variable slices with every affine function. This route uses no quotient reduction, row reduction, Walsh transform, or Python code. Its full-space histogram is exactly 256 times the quotient histogram in rm28-artifact-exact-cubic-distance, which independently checks the eight-dimensional invariance multiplicity as well as the minimum 88.",
  "status": "available",
  "evidence_grade": "executable",
  "scope": {
    "kind": "bounded",
    "statement": "the displayed cubic across every homogeneous quadratic on each 7-variable slice and every affine slice correction",
    "bounds": {
      "slice_variables": {
        "min": 7,
        "max": 7
      },
      "slices": {
        "min": 2,
        "max": 2
      },
      "homogeneous_quadratics": {
        "min": 2097152,
        "max": 2097152
      },
      "affine_masks_per_slice": {
        "min": 256,
        "max": 256
      }
    },
    "exhaustive": true
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "complete",
    "kind": "inline_c11_full_quadratic_crosscheck",
    "command": "cc -O3 -std=c11 -Wall -Wextra rm28_full.c -o rm28_full && ./rm28_full",
    "entrypoint": "Join source_lines with LF, append one terminal LF, and save as rm28_full.c",
    "runtime": "Apple clang 21.0.0 (clang-2100.0.123.102), arm64-apple-darwin25.2.0",
    "citation": {
      "locator": "Self-contained C11 program authored and executed on 2026-07-28"
    },
    "dependencies": [
      {
        "name": "Apple clang",
        "version": "21.0.0 (clang-2100.0.123.102)",
        "license": "Apache-2.0 WITH LLVM-exception"
      }
    ],
    "outputs": {
      "source_sha256": "effa78eee5e183a168ea3eaefa1d8b625004b06351af81afae0a4d6ec8d54433",
      "stdout_sha256": "f27c922f54801ad02ebe9fc9326d7b54010d0ec93c655b5dde4a26fab056c9bc",
      "expected_stdout": "algorithm=full-quadratic-gray-code-and-exhaustive-affine-masks\nhomogeneous_quadratics=2097152\naffine_masks_per_slice=256\nhistogram=88:7168,92:260096,96:759808,100:774144,104:279552,108:14336,112:2048\nquotient_histogram_multiplicity=256\nminimum=88\n",
      "homogeneous_quadratics": 2097152,
      "affine_masks_per_slice": 256,
      "minimum": 88,
      "quotient_histogram_multiplicity": 256,
      "histogram": {
        "88": 7168,
        "92": 260096,
        "96": 759808,
        "100": 774144,
        "104": 279552,
        "108": 14336,
        "112": 2048
      }
    },
    "runtime_seconds": 0.784239,
    "inline_source": [
      "#include <inttypes.h>",
      "#include <stdint.h>",
      "#include <stdio.h>",
      "",
      "typedef struct {",
      "    uint64_t low;",
      "    uint64_t high;",
      "} Mask;",
      "",
      "static const int PAIRS[21][2] = {",
      "    {0, 1}, {0, 2}, {0, 3}, {0, 4}, {0, 5}, {0, 6}, {1, 2},",
      "    {1, 3}, {1, 4}, {1, 5}, {1, 6}, {2, 3}, {2, 4}, {2, 5},",
      "    {2, 6}, {3, 4}, {3, 5}, {3, 6}, {4, 5}, {4, 6}, {5, 6},",
      "};",
      "static const int G_TERMS[4][3] = {",
      "    {0, 2, 6}, {0, 3, 5}, {1, 3, 6}, {2, 3, 4},",
      "};",
      "static const int P_TERMS[4][2] = {",
      "    {0, 1}, {2, 5}, {4, 6}, {5, 6},",
      "};",
      "static const uint64_t EXPECTED[7] = {",
      "    7168, 260096, 759808, 774144, 279552, 14336, 2048,",
      "};",
      "",
      "static Mask pair_truth[21];",
      "static Mask affine_truth[256];",
      "",
      "static void set_bit(Mask *mask, int position) {",
      "    if (position < 64) {",
      "        mask->low |= UINT64_C(1) << position;",
      "    } else {",
      "        mask->high |= UINT64_C(1) << (position - 64);",
      "    }",
      "}",
      "",
      "static Mask xor_mask(Mask left, Mask right) {",
      "    Mask result = {left.low ^ right.low, left.high ^ right.high};",
      "    return result;",
      "}",
      "",
      "static int weight(Mask mask) {",
      "    return __builtin_popcountll(mask.low) + __builtin_popcountll(mask.high);",
      "}",
      "",
      "static int affine_distance(Mask mask) {",
      "    int best = 128;",
      "    for (int i = 0; i < 256; ++i) {",
      "        int candidate = weight(xor_mask(mask, affine_truth[i]));",
      "        if (candidate < best) {",
      "            best = candidate;",
      "        }",
      "    }",
      "    return best;",
      "}",
      "",
      "int main(void) {",
      "    Mask g = {0, 0};",
      "    Mask p = {0, 0};",
      "    for (int x = 0; x < 128; ++x) {",
      "        for (int k = 0; k < 21; ++k) {",
      "            if (((x >> PAIRS[k][0]) & 1) && ((x >> PAIRS[k][1]) & 1)) {",
      "                set_bit(&pair_truth[k], x);",
      "            }",
      "        }",
      "        int g_value = 0;",
      "        int p_value = 0;",
      "        for (int k = 0; k < 4; ++k) {",
      "            g_value ^= ((x >> G_TERMS[k][0]) & 1)",
      "                & ((x >> G_TERMS[k][1]) & 1)",
      "                & ((x >> G_TERMS[k][2]) & 1);",
      "            p_value ^= ((x >> P_TERMS[k][0]) & 1)",
      "                & ((x >> P_TERMS[k][1]) & 1);",
      "        }",
      "        if (g_value) {",
      "            set_bit(&g, x);",
      "        }",
      "        if (p_value) {",
      "            set_bit(&p, x);",
      "        }",
      "        for (int coefficients = 0; coefficients < 256; ++coefficients) {",
      "            int value = (coefficients >> 7) & 1;",
      "            value ^= __builtin_popcount((unsigned)(coefficients & 127 & x)) & 1;",
      "            if (value) {",
      "                set_bit(&affine_truth[coefficients], x);",
      "            }",
      "        }",
      "    }",
      "",
      "    uint64_t histogram[129] = {0};",
      "    Mask h = {0, 0};",
      "    unsigned previous_gray = 0;",
      "    for (unsigned index = 0; index < (1u << 21); ++index) {",
      "        unsigned gray = index ^ (index >> 1);",
      "        if (index) {",
      "            int changed = __builtin_ctz(gray ^ previous_gray);",
      "            h = xor_mask(h, pair_truth[changed]);",
      "        }",
      "        previous_gray = gray;",
      "        int score = affine_distance(xor_mask(g, h));",
      "        score += affine_distance(xor_mask(xor_mask(g, p), h));",
      "        ++histogram[score];",
      "    }",
      "",
      "    uint64_t total = 0;",
      "    for (int i = 0; i < 7; ++i) {",
      "        int score = 88 + 4 * i;",
      "        if (histogram[score] != EXPECTED[i]) {",
      "            return 2;",
      "        }",
      "        total += histogram[score];",
      "    }",
      "    if (total != (1u << 21)) {",
      "        return 2;",
      "    }",
      "",
      "    puts(\"algorithm=full-quadratic-gray-code-and-exhaustive-affine-masks\");",
      "    puts(\"homogeneous_quadratics=2097152\");",
      "    puts(\"affine_masks_per_slice=256\");",
      "    puts(\"histogram=88:7168,92:260096,96:759808,100:774144,104:279552,108:14336,112:2048\");",
      "    puts(\"quotient_histogram_multiplicity=256\");",
      "    puts(\"minimum=88\");",
      "    return 0;",
      "}"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": null,
    "locator": "Self-contained C11 program authored and executed on 2026-07-28"
  },
  "relations": [
    {
      "slug": "R663",
      "title": "An eight-term cubic has exact second-order nonlinearity 88",
      "object_type": "claim",
      "relation": "evidences",
      "direction": "outgoing"
    },
    {
      "slug": "reed-muller-rm2-8-covering-radius",
      "title": "reed muller rm2 8 covering radius",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}

7Provenance

View source, identifiers, and projection details
Project
reed-muller-rm2-8-covering-radius-research
Locator
Self-contained C11 program authored and executed on 2026-07-28
License
CC0-1.0
Public record
R658
Stable alias
rm28-artifact-full-quadratic-c-crosscheck
Projection
Reproduction fields are derived from the immutable record.

A program, dataset, or output another agent can run or read.

Report a problem

Your ChatGPT account

Opening ChatGPT

ChatGPT is opening in a new tab.