{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R395",
  "content_hash": null,
  "slug": "hrt20-artifact-witness-and-neighborhood",
  "type": "artifact",
  "title": "Exact boundary ranks and exhaustive one-point neighborhood",
  "summary": "A standard-library verifier reproduces beta one equal to 21 and proves that all 4,720 changed one-point replacements have beta one at most 20 when connected.",
  "relevance": "For Largest first Betti number of a connected Hamming Rips complex, record hrt20-artifact-witness-and-neighborhood (“Exact boundary ranks and exhaustive one-point neighborhood”) supplies evidence or a replay used to check the packet. The record states: A standard-library verifier reproduces beta one equal to 21 and proves that all 4,720 changed one-point replacements have beta one at most 20 when connected.",
  "relevance_source": "recorded",
  "body": "Use Hamming distance at most two on the following lexicographically ordered words:\n```\n00000011 00000111 00001101 00010010 00010110\n00011100 00100011 00101001 00110010 00111000\n11000011 11000111 11001101 11010010 11010110\n11011100 11100011 11101001 11110010 11111000\n```\nThe newline-separated point list has SHA-256 digest `a883d10312be85b66176b6c5f7063d7da5ca5074e31ab61adc83ad0b179ac7bf`. There are eight distance-one edges and 36 distance-two edges. The canonical 44-edge list has digest `d253d61bcc4dcdb3e0ffbf26613eda3d5c75e74e9d3aea36fde64cb8cf485596`.\n\nThe only triangles, in zero-based point indices, are\n\\[\n(0,1,6),\\ (3,4,8),\\ (10,11,16),\\ (13,14,18).\n\\]\nTheir edge-boundary columns are `45`, `9800`, `128000000`, and `5800000000` in hexadecimal when edges are ordered lexicographically. Each has a different leading bit, so the four columns are independent. The verifier also constructs the vertex-edge boundary matrix and row reduces both matrices over \\(\\mathbb F_2\\). The complete canonical certificate has SHA-256 digest `680e1588932fa8c474296aa5aa86b524cbbd22e5058213fa26d3237d34797a33`.\n\nFor the local optimization audit, remove each selected word in turn and insert each of the 236 unselected words. This gives \\(20\\cdot236=4{,}720\\) changed sets. Exactly 3,520 are connected. Their beta-one histogram is 96 at 16, 1,392 at 17, 1,664 at 18, 356 at 19, and 12 at 20. None reaches 21, so the witness is a strict one-point-replacement optimum. The neighborhood report digest is `ea087a3b6c2151c3a982db846b3839254a1127cd6c55ea99a3e5c049b80f4963`.",
  "status": "available",
  "evidence_grade": "executable",
  "scope": {
    "kind": "bounded",
    "statement": "the stated 20-point Hamming-cube witness and every set obtained by replacing exactly one of its selected words",
    "bounds": {
      "ambient_words": {
        "min": 256,
        "max": 256
      },
      "selected_points": {
        "min": 20,
        "max": 20
      },
      "witness_edges": {
        "min": 44,
        "max": 44
      },
      "witness_triangles": {
        "min": 4,
        "max": 4
      },
      "changed_one_point_replacements": {
        "min": 4720,
        "max": 4720
      },
      "connected_replacements": {
        "min": 3520,
        "max": 3520
      }
    },
    "exhaustive": true
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "partial",
    "kind": "inline_python_exact_homology_and_neighborhood",
    "entrypoint": "join source_lines with newline and run with python3",
    "runtime": "CPython 3.8 or later, standard library only",
    "citation": {
      "url": "https://doi.org/10.4230/LIPIcs.SoCG.2025.14",
      "locator": "Inline CPython standard-library exact computation executed by TheoremDB entry research on 2026-07-25"
    },
    "outputs": "points=20 point_sha256=a883d10312be85b66176b6c5f7063d7da5ca5074e31ab61adc83ad0b179ac7bf\nedges=44 edge_sha256=d253d61bcc4dcdb3e0ffbf26613eda3d5c75e74e9d3aea36fde64cb8cf485596\ntriangles=4 triangle_sha256=126c522038b16ae866f229c515eb3c05c971c97f3ff48b9a1b302d24dc367323\ncomponents=1 rank_d1=19 rank_d2=4 beta1=21\ncertificate_sha256=680e1588932fa8c474296aa5aa86b524cbbd22e5058213fa26d3237d34797a33\nchanged_swaps=4720 connected_swaps=3520 max_neighbor_beta1=20 maximizers=12\nneighbor_histogram=16:96,17:1392,18:1664,19:356,20:12\nneighborhood_sha256=ea087a3b6c2151c3a982db846b3839254a1127cd6c55ea99a3e5c049b80f4963\n",
    "inline_source": [
      "from hashlib import sha256",
      "from itertools import combinations",
      "from json import dumps",
      "",
      "POINTS = tuple('00000011 00000111 00001101 00010010 00010110 00011100 00100011 00101001 00110010 00111000 11000011 11000111 11001101 11010010 11010110 11011100 11100011 11101001 11110010 11111000'.split())",
      "VALUES = tuple(int(word, 2) for word in POINTS)",
      "",
      "def gf2_rank(columns):",
      "    basis = {}",
      "    for value in columns:",
      "        while value:",
      "            pivot = value.bit_length() - 1",
      "            if pivot in basis:",
      "                value ^= basis[pivot]",
      "            else:",
      "                basis[pivot] = value",
      "                break",
      "    return len(basis), basis",
      "",
      "def analyze(values):",
      "    n = len(values)",
      "    edges = []",
      "    adjacency = [0] * n",
      "    for i, j in combinations(range(n), 2):",
      "        distance = bin(values[i] ^ values[j]).count('1')",
      "        if distance <= 2:",
      "            edges.append((i, j, distance))",
      "            adjacency[i] |= 1 << j",
      "            adjacency[j] |= 1 << i",
      "",
      "    seen = 1",
      "    while True:",
      "        old = seen",
      "        for i in range(n):",
      "            if seen >> i & 1:",
      "                seen |= adjacency[i]",
      "        if seen == old:",
      "            break",
      "    components = 1 if seen == (1 << n) - 1 else None",
      "",
      "    triangles = []",
      "    for i, j, k in combinations(range(n), 3):",
      "        if adjacency[i] >> j & 1 and adjacency[i] >> k & 1 and adjacency[j] >> k & 1:",
      "            triangles.append((i, j, k))",
      "",
      "    edge_index = {(i, j): index for index, (i, j, distance) in enumerate(edges)}",
      "    boundary_one = [(1 << i) | (1 << j) for i, j, distance in edges]",
      "    boundary_two = []",
      "    for i, j, k in triangles:",
      "        boundary_two.append((1 << edge_index[(i, j)]) |",
      "                            (1 << edge_index[(i, k)]) |",
      "                            (1 << edge_index[(j, k)]))",
      "    rank_one, basis_one = gf2_rank(boundary_one)",
      "    rank_two, basis_two = gf2_rank(boundary_two)",
      "    beta_one = len(edges) - rank_one - rank_two if components == 1 else None",
      "    return edges, triangles, boundary_two, basis_two, adjacency, components, rank_one, rank_two, beta_one",
      "",
      "edges, triangles, boundary_two, basis_two, adjacency, components, rank_one, rank_two, beta_one = analyze(VALUES)",
      "assert len(edges) == 44",
      "assert sum(distance == 1 for i, j, distance in edges) == 8",
      "assert sum(distance == 2 for i, j, distance in edges) == 36",
      "assert triangles == [(0, 1, 6), (3, 4, 8), (10, 11, 16), (13, 14, 18)]",
      "assert [format(value, 'x') for value in boundary_two] == ['45', '9800', '128000000', '5800000000']",
      "assert (components, rank_one, rank_two, beta_one) == (1, 19, 4, 21)",
      "",
      "point_sha = sha256(('\\n'.join(POINTS) + '\\n').encode()).hexdigest()",
      "edge_sha = sha256((dumps(edges, separators=(',', ':')) + '\\n').encode()).hexdigest()",
      "triangle_sha = sha256((dumps(triangles, separators=(',', ':')) + '\\n').encode()).hexdigest()",
      "assert point_sha == 'a883d10312be85b66176b6c5f7063d7da5ca5074e31ab61adc83ad0b179ac7bf'",
      "assert edge_sha == 'd253d61bcc4dcdb3e0ffbf26613eda3d5c75e74e9d3aea36fde64cb8cf485596'",
      "assert triangle_sha == '126c522038b16ae866f229c515eb3c05c971c97f3ff48b9a1b302d24dc367323'",
      "",
      "certificate = {",
      "    'points': POINTS,",
      "    'edges': edges,",
      "    'triangles': triangles,",
      "    'boundary_columns_hex': [format(value, 'x') for value in boundary_two],",
      "    'reduced_basis': [(pivot, format(basis_two[pivot], 'x')) for pivot in sorted(basis_two, reverse=True)],",
      "    'degrees': [neighbors.bit_count() for neighbors in adjacency],",
      "    'components': components,",
      "    'rank_boundary_1': rank_one,",
      "    'rank_boundary_2': rank_two,",
      "    'beta_1': beta_one,",
      "}",
      "certificate_payload = dumps(certificate, sort_keys=True, separators=(',', ':'))",
      "certificate_sha = sha256(certificate_payload.encode()).hexdigest()",
      "assert certificate_sha == '680e1588932fa8c474296aa5aa86b524cbbd22e5058213fa26d3237d34797a33'",
      "",
      "selected = set(VALUES)",
      "histogram = {}",
      "connected_swaps = 0",
      "maximum = -1",
      "maximizers = 0",
      "for position, old in enumerate(VALUES):",
      "    for new in range(256):",
      "        if new in selected:",
      "            continue",
      "        changed = list(VALUES)",
      "        changed[position] = new",
      "        result = analyze(tuple(changed))",
      "        neighbor_beta = result[-1]",
      "        if neighbor_beta is None:",
      "            continue",
      "        connected_swaps += 1",
      "        histogram[neighbor_beta] = histogram.get(neighbor_beta, 0) + 1",
      "        if neighbor_beta > maximum:",
      "            maximum = neighbor_beta",
      "            maximizers = 1",
      "        elif neighbor_beta == maximum:",
      "            maximizers += 1",
      "assert connected_swaps == 3520",
      "assert histogram == {16: 96, 17: 1392, 18: 1664, 19: 356, 20: 12}",
      "assert (maximum, maximizers) == (20, 12)",
      "",
      "neighborhood = {",
      "    'changed_swaps': 20 * (256 - 20),",
      "    'connected_swaps': connected_swaps,",
      "    'max_beta': maximum,",
      "    'max_achievers': maximizers,",
      "    'histogram': dict(sorted(histogram.items())),",
      "}",
      "neighborhood_payload = dumps(neighborhood, sort_keys=True, separators=(',', ':'))",
      "neighborhood_sha = sha256(neighborhood_payload.encode()).hexdigest()",
      "assert neighborhood_sha == 'ea087a3b6c2151c3a982db846b3839254a1127cd6c55ea99a3e5c049b80f4963'",
      "",
      "print(f'points=20 point_sha256={point_sha}')",
      "print(f'edges=44 edge_sha256={edge_sha}')",
      "print(f'triangles=4 triangle_sha256={triangle_sha}')",
      "print(f'components={components} rank_d1={rank_one} rank_d2={rank_two} beta1={beta_one}')",
      "print(f'certificate_sha256={certificate_sha}')",
      "print(f'changed_swaps=4720 connected_swaps={connected_swaps} max_neighbor_beta1={maximum} maximizers={maximizers}')",
      "print('neighbor_histogram=' + ','.join(f'{key}:{histogram[key]}' for key in sorted(histogram)))",
      "print(f'neighborhood_sha256={neighborhood_sha}')"
    ],
    "missing": [
      "command"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://doi.org/10.4230/LIPIcs.SoCG.2025.14",
    "locator": "Inline CPython standard-library exact computation executed by TheoremDB entry research on 2026-07-25"
  },
  "models": [],
  "continuation": null,
  "relations": [
    {
      "slug": "R397",
      "title": "The certified interval is 21 through 81",
      "object_type": "claim",
      "relation": "supports",
      "direction": "outgoing"
    },
    {
      "slug": "hamming-rips-twenty-beta-one",
      "title": "hamming rips twenty beta one",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}