{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R656",
  "content_hash": null,
  "slug": "rm28-artifact-bitset-crosscheck",
  "type": "artifact",
  "title": "Independent bitset cross-check of the cubic distance",
  "summary": "A second implementation replaces Walsh transforms with 128-bit truth masks and exhaustive comparison against all 256 affine functions on each slice.",
  "relevance": "For Covering radius of the second-order Reed-Muller code RM(2,8), record rm28-artifact-bitset-crosscheck (“Independent bitset cross-check of the cubic distance”) supplies evidence or a replay used to check the packet. The record states: A second implementation replaces Walsh transforms with 128-bit truth masks and exhaustive comparison against all 256 affine functions on each slice.",
  "relevance_source": "recorded",
  "body": "Join source_lines with LF, append a terminal LF, and save the result as `rm28_bitset.py` in a disposable directory. This program builds truth tables as Python integers, obtains affine distance by checking all 256 affine truth masks, and uses a separate echelon-basis implementation for the eight-dimensional invariance span. For each of the 8,192 quotient representatives it also retests the score after every one of the eight span-generator shifts, for 65,536 invariance checks. The score histogram, minimum, direct correction weight, and both truth-table digests match rm28-artifact-exact-cubic-distance.",
  "status": "available",
  "evidence_grade": "executable",
  "scope": {
    "kind": "bounded",
    "statement": "an independent exact replay of the displayed cubic over every representative of the quadratic quotient",
    "bounds": {
      "variables": {
        "min": 8,
        "max": 8
      },
      "affine_masks_per_slice": {
        "min": 256,
        "max": 256
      },
      "quotient_representatives": {
        "min": 8192,
        "max": 8192
      },
      "generator_invariance_checks": {
        "min": 65536,
        "max": 65536
      }
    },
    "exhaustive": true
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "complete",
    "kind": "inline_python_exact_bitset_crosscheck",
    "command": "python3 rm28_bitset.py",
    "entrypoint": "Join source_lines with LF, append one terminal LF, and save as rm28_bitset.py",
    "runtime": "CPython 3.9.6 or later, standard library, macOS 26.2 arm64",
    "citation": {
      "locator": "Independent self-contained CPython program authored and executed on 2026-07-28"
    },
    "dependencies": [
      {
        "name": "CPython standard library",
        "version": "3.9.6 or later",
        "license": "Python-2.0"
      }
    ],
    "outputs": {
      "source_sha256": "c483ef2f691dda7c9f787d58445bd4e46c97716a549259c76ff85d6adb85ffcc",
      "stdout_sha256": "ab348e9d9fcf424527ffb2fea5c8fda75f99e76b28e10ef4473037516f5a8ba6",
      "expected_stdout": "algorithm=integer-bitsets-and-exhaustive-affine-masks\nspan_rank=8\nquotient_dimension=13\nrepresentatives=8192\ngenerator_invariance_checks=65536\nhistogram=88:28,92:1016,96:2968,100:3024,104:1092,108:56,112:8\nminimum=88\ndirect_weight=88\nslice_weights=40,48\nwitness_truth_sha256=47299b7d07c1a0de9de3c88d211b1b39d6d3d45259662df9aa77c9638874cc26\ncorrected_truth_sha256=22c23f99ad7843999487757749e4f4c9b9879151db4d016c5e91597eccccaea6\n",
      "span_rank": 8,
      "quotient_dimension": 13,
      "representatives": 8192,
      "generator_invariance_checks": 65536,
      "minimum": 88,
      "histogram": {
        "88": 28,
        "92": 1016,
        "96": 2968,
        "100": 3024,
        "104": 1092,
        "108": 56,
        "112": 8
      }
    },
    "runtime_seconds": 15.194502,
    "inline_source": [
      "from collections import Counter",
      "from hashlib import sha256",
      "from itertools import combinations",
      "",
      "PAIRS = list(combinations(range(7), 2))",
      "G_TERMS = [(0, 2, 6), (0, 3, 5), (1, 3, 6), (2, 3, 4)]",
      "P_TERMS = [(0, 1), (2, 5), (4, 6), (5, 6)]",
      "F_TERMS = [",
      "    (0, 1, 2),",
      "    (0, 3, 6),",
      "    (0, 5, 7),",
      "    (0, 6, 7),",
      "    (1, 3, 7),",
      "    (1, 4, 6),",
      "    (2, 4, 7),",
      "    (3, 4, 5),",
      "]",
      "Q_TERMS = [(0, 3), (1, 2), (1, 3), (1, 6)]",
      "",
      "",
      "def popcount(value):",
      "    return bin(value).count(\"1\")",
      "",
      "",
      "def truth_values(variable_count, terms):",
      "    return [",
      "        sum(all((x >> i) & 1 for i in term) for term in terms) & 1",
      "        for x in range(1 << variable_count)",
      "    ]",
      "",
      "",
      "def truth_mask(variable_count, terms):",
      "    values = truth_values(variable_count, terms)",
      "    return sum(bit << x for x, bit in enumerate(values))",
      "",
      "",
      "pair_truth = [truth_mask(7, [pair]) for pair in PAIRS]",
      "g_truth = truth_mask(7, G_TERMS)",
      "p_truth = truth_mask(7, P_TERMS)",
      "",
      "affine_masks = []",
      "for coefficients in range(256):",
      "    constant = (coefficients >> 7) & 1",
      "    mask = 0",
      "    for x in range(128):",
      "        value = constant",
      "        value ^= popcount(coefficients & 127 & x) & 1",
      "        mask |= value << x",
      "    affine_masks.append(mask)",
      "",
      "",
      "def affine_distance(mask):",
      "    return min(popcount(mask ^ affine) for affine in affine_masks)",
      "",
      "",
      "def coefficient_mask(terms):",
      "    result = 0",
      "    for term in terms:",
      "        result ^= 1 << PAIRS.index(tuple(sorted(term)))",
      "    return result",
      "",
      "",
      "p_coefficient = coefficient_mask(P_TERMS)",
      "derivative_coefficients = []",
      "for variable in range(7):",
      "    derivative = [",
      "        tuple(i for i in term if i != variable)",
      "        for term in G_TERMS",
      "        if variable in term",
      "    ]",
      "    derivative_coefficients.append(coefficient_mask(derivative))",
      "generators = [p_coefficient, *derivative_coefficients]",
      "",
      "pivot_rows = {}",
      "for generator in generators:",
      "    row = generator",
      "    while row:",
      "        pivot = row.bit_length() - 1",
      "        if pivot in pivot_rows:",
      "            row ^= pivot_rows[pivot]",
      "        else:",
      "            pivot_rows[pivot] = row",
      "            break",
      "assert len(pivot_rows) == 8",
      "",
      "free_columns = [i for i in range(21) if i not in pivot_rows]",
      "assert len(free_columns) == 13",
      "",
      "",
      "def quadratic_truth(coefficient):",
      "    result = 0",
      "    for i, basis in enumerate(pair_truth):",
      "        if (coefficient >> i) & 1:",
      "            result ^= basis",
      "    return result",
      "",
      "",
      "generator_truth = [quadratic_truth(generator) for generator in generators]",
      "",
      "",
      "def pair_score(h_truth):",
      "    return affine_distance(g_truth ^ h_truth) + affine_distance(",
      "        g_truth ^ p_truth ^ h_truth",
      "    )",
      "",
      "",
      "histogram = Counter()",
      "invariance_checks = 0",
      "for selector in range(8192):",
      "    coefficient = sum(",
      "        1 << column",
      "        for i, column in enumerate(free_columns)",
      "        if (selector >> i) & 1",
      "    )",
      "    h_truth = quadratic_truth(coefficient)",
      "    score = pair_score(h_truth)",
      "    histogram[score] += 1",
      "    for shift in generator_truth:",
      "        assert pair_score(h_truth ^ shift) == score",
      "        invariance_checks += 1",
      "",
      "expected = [(88, 28), (92, 1016), (96, 2968), (100, 3024)]",
      "expected += [(104, 1092), (108, 56), (112, 8)]",
      "assert sorted(histogram.items()) == expected",
      "assert invariance_checks == 65536",
      "",
      "f_values = truth_values(8, F_TERMS)",
      "q_values = truth_values(8, Q_TERMS)",
      "corrected = [u ^ v for u, v in zip(f_values, q_values)]",
      "assert sum(corrected) == 88",
      "slice_weights = [sum(corrected[0::2]), sum(corrected[1::2])]",
      "assert slice_weights == [40, 48]",
      "",
      "print(\"algorithm=integer-bitsets-and-exhaustive-affine-masks\")",
      "print(\"span_rank=8\")",
      "print(\"quotient_dimension=13\")",
      "print(\"representatives=8192\")",
      "print(\"generator_invariance_checks=65536\")",
      "print(\"histogram=88:28,92:1016,96:2968,100:3024,104:1092,108:56,112:8\")",
      "print(\"minimum=88\")",
      "print(\"direct_weight=88\")",
      "print(\"slice_weights=40,48\")",
      "print(f\"witness_truth_sha256={sha256(bytes(f_values)).hexdigest()}\")",
      "print(f\"corrected_truth_sha256={sha256(bytes(corrected)).hexdigest()}\")"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": null,
    "locator": "Independent self-contained CPython program authored and executed on 2026-07-28"
  },
  "relations": [
    {
      "slug": "R657",
      "title": "Exact quotient and Walsh replay for the distance-88 cubic",
      "object_type": "artifact",
      "relation": "tests",
      "direction": "outgoing"
    },
    {
      "slug": "reed-muller-rm2-8-covering-radius",
      "title": "reed muller rm2 8 covering radius",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}