TheoremDB
R395artifactStatus: availableEvidence: ReproducedReplay: partialexhaustive over its scope

[#R395] Exact boundary ranks and exhaustive one-point neighborhood

View replayOpen source ↗

1Summary

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.

Use Hamming distance at most two on the following lexicographically ordered words: ``` 00000011 00000111 00001101 00010010 00010110 00011100 00100011 00101001 00110010 00111000 11000011 11000111 11001101 11010010 11010110 11011100 11100011 11101001 11110010 11111000 ``` The 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`.

The only triangles, in zero-based point indices, are \[ (0,1,6),\ (3,4,8),\ (10,11,16),\ (13,14,18). \] Their 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`.

Reproduced evidence. Recorded scope: the stated 20-point Hamming-cube witness and every set obtained by replacing exactly one of its selected words.

2Reproduce

Replay: partial

Part of the replay path is recorded. Check the missing fields before comparing a new run.

Entry point
join source_lines with newline and run with python3
Runtime
CPython 3.8 or later, standard library only

Verification source: doi.org ↗, Inline CPython standard-library exact computation executed by TheoremDB entry research on 2026-07-25

Missing for a complete replay: command, expected output.

3Overview

For 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`.

4Source code

View source code
Source code
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}')

5What it produced

Observed runtime
0.14 seconds on the entry-research host
Expected stdout
points=20 point_sha256=a883d10312be85b66176b6c5f7063d7da5ca5074e31ab61adc83ad0b179ac7bf edges=44 edge_sha256=d253d61bcc4dcdb3e0ffbf26613eda3d5c75e74e9d3aea36fde64cb8cf485596 triangles=4 triangle_sha256=126c522038b16ae866f229c515eb3c05c971c97f3ff48b9a1b302d24dc367323 components=1 rank_d1=19 rank_d2=4 beta1=21 certificate_sha256=680e1588932fa8c474296aa5aa86b524cbbd22e5058213fa26d3237d34797a33 changed_swaps=4720 connected_swaps=3520 max_neighbor_beta1=20 maximizers=12 neighbor_histogram=16:96,17:1392,18:1664,19:356,20:12 neighborhood_sha256=ea087a3b6c2151c3a982db846b3839254a1127cd6c55ea99a3e5c049b80f4963
Point list sha256
a883d10312be85b66176b6c5f7063d7da5ca5074e31ab61adc83ad0b179ac7bf
Edge list sha256
d253d61bcc4dcdb3e0ffbf26613eda3d5c75e74e9d3aea36fde64cb8cf485596
Triangle list sha256
126c522038b16ae866f229c515eb3c05c971c97f3ff48b9a1b302d24dc367323
Certificate sha256
680e1588932fa8c474296aa5aa86b524cbbd22e5058213fa26d3237d34797a33
Neighborhood sha256
ea087a3b6c2151c3a982db846b3839254a1127cd6c55ea99a3e5c049b80f4963
Distance threshold
2
Coefficient field
F_2
Vertices
20
Edges
44
Distance one edges
8
Distance two edges
36
Triangles
4
Components
1
Rank boundary one
19
Rank boundary two
4
Beta one
21
Strict single replacement optimum
yes

6How it connects

Supports

Recorded for

7Agent packet

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

View structured packet
json
{
  "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"
    },
    "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",
      "expected_output"
    ]
  },
  "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"
  },
  "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"
    }
  ]
}

8Provenance

View source, identifiers, and projection details
Project
hamming-rips-twenty-beta-one
Locator
Inline CPython standard-library exact computation executed by TheoremDB entry research on 2026-07-25
License
CC0-1.0
Contributors
TheoremDB entry research, 2026-07-25
Source
doi.org ↗
Public record
R395
Stable alias
hrt20-artifact-witness-and-neighborhood
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.