TheoremDB

Problem packetResearch packetR245

R245Executable evidence

Exact two-connectivity frontier transfer for the three-cube box

View replayOpen source ↗
Link to a section

Authored summary

A standard-library Python program branches on every voxel, merges equivalent frontier states, and certifies the full first-Betti histogram.

Executable material is recorded. Successful replay is a separate check.

Recorded status: available

Recorded scope: all 2^27 subsets of the 27 voxels in a 3 by 3 by 3 box, grouped by exact frontier states while retaining both connectivity partitions and Euler characteristic

Complete recorded scope and conditions
{
  "kind": "bounded",
  "statement": "all 2^27 subsets of the 27 voxels in a 3 by 3 by 3 box, grouped by exact frontier states while retaining both connectivity partitions and Euler characteristic",
  "bounds": {
    "side_length": {
      "min": 3,
      "max": 3
    },
    "binary_variables": {
      "min": 27,
      "max": 27
    },
    "maximum_cached_states_at_one_step": {
      "min": 29637,
      "max": 29637
    }
  },
  "exhaustive": true
}

Originating problem: Exact tunnel probability for site percolation on a four by four by four cubical box

Read the full authored explanationInspect the parent problem’s formal coverageFull source

Recorded relationships: The exact three-cube tunnel probability is 4,355 over 16,384

Authored record and scope
Authored title
Exact two-connectivity frontier transfer for the three-cube box
Record type
artifact
Stored status
available
Evidence grade
executable
Recorded scope data
{ "kind": "bounded", "statement": "all 2^27 subsets of the 27 voxels in a 3 by 3 by 3 box, grouped by exact frontier states while retaining both connectivity partitions and Euler characteristic", "bounds": { "side_length": { "min": 3, "max": 3 }, "binary_variables": { "min": 27, "max": 27 }, "maximum_cached_states_at_one_step": { "min": 29637, "max": 29637 } }, "exhaustive": true }
Linked research record IDs
R247

2Authored explanation

Voxels are introduced in lexicographic \((z,y,x)\) order. A state retains the selected bit for each active voxel, the canonical partition of selected voxels under 26-adjacency, the partition of unselected voxels under 6-adjacency, an exterior flag on each background component, closed-component totals, and the current Euler characteristic.

Each of the 343 cubical cells is finalized when its last incident voxel is introduced. Its sign is \((-1)^d\), where \(d\) is its dimension, and it contributes exactly when at least one incident voxel is selected. A component is counted when its final frontier voxel is forgotten. Every step checks that the sum of state multiplicities is \(2^i\), so the transfer accounts for every bit string.

The 343 incidence records have SHA-256 digest `63d4b0719908ac018e69de4459b95d63bb5332878c7f3ba5ac840f99562f350d`. The sorted state-and-multiplicity stream across all 27 steps has digest `3cb381d323714ed3209e2a0ba249d7c7a87e44c638ea103602850f63ee12e7c1`. The deterministic report has digest `44626fe9d0de5fb11a14ac75915a5a6ebefffda3fb9c50cab10cd0cda9b4a4b1`.

Files and source

Files embedded in this record. Matching a file hash confirms its identity.

  • R245.txt5,867 bytes · No SHA-256 recorded
    Preview R245.txt
    from collections import defaultdict
import hashlib

N = 3
V = N ** 3

def voxel(x, y, z):
    return x + N * y + N * N * z

last = list(range(V))
for z in range(N):
    for y in range(N):
        for x in range(N):
            u = voxel(x, y, z)
            for dz in (-1, 0, 1):
                for dy in (-1, 0, 1):
                    for dx in (-1, 0, 1):
                        xx, yy, zz = x + dx, y + dy, z + dz
                        if 0 <= xx < N and 0 <= yy < N and 0 <= zz < N:
                            last[u] = max(last[u], voxel(xx, yy, zz))

factors_at = [[] for _ in range(V)]
factor_lines = []
for cz in range(2 * N + 1):
    for cy in range(2 * N + 1):
        for cx in range(2 * N + 1):
            dimension = (cx & 1) + (cy & 1) + (cz & 1)
            incident = tuple(
                voxel(x, y, z)
                for z in range(N)
                for y in range(N)
                for x in range(N)
                if 2 * x <= cx <= 2 * x + 2
                and 2 * y <= cy <= 2 * y + 2
                and 2 * z <= cz <= 2 * z + 2
            )
            sign = 1 if dimension % 2 == 0 else -1
            factors_at[max(incident)].append((sign, incident))
            factor_lines.append(f'{cx},{cy},{cz}:{dimension}:{sign}:' + ','.join(map(str, incident)))

assert len(factor_lines) == 343
factor_digest = hashlib.sha256(('\n'.join(factor_lines) + '\n').encode()).hexdigest()
assert factor_digest == '63d4b0719908ac018e69de4459b95d63bb5332878c7f3ba5ac840f99562f350d'

dp = {((), 0, 0, 0): 1}
active = []
state_counts = []
certificate = hashlib.sha256()
for step in range(V):
    z, rem = divmod(step, N * N)
    y, x = divmod(rem, N)
    current = active + [step]
    position = {u: i for i, u in enumerate(current)}
    keep = [i for i, u in enumerate(current) if last[u] > step]
    nxt = defaultdict(int)
    for (old_codes, fg0, bg0, chi0), multiplicity in dp.items():
        for selected in (0, 1):
            size = len(current)
            parent = list(range(size))
            colors = [code[1] for code in old_codes] + [selected]
            exterior = [code[2] for code in old_codes] + [int(
                not selected and (x in (0, N-1) or y in (0, N-1) or z in (0, N-1)))]
            first = {}
            for i, code in enumerate(old_codes):
                label = code[0]
                if label in first:
                    parent[i] = first[label]
                else:
                    first[label] = i
            def root(a):
                while parent[a] != a:
                    parent[a] = parent[parent[a]]
                    a = parent[a]
                return a
            for i in range(size - 1):
                r = root(i)
                exterior[r] |= exterior[i]
            def unite(a, b):
                ra, rb = root(a), root(b)
                if ra != rb:
                    parent[rb] = ra
                    exterior[ra] |= exterior[rb]
            for i, u in enumerate(current[:-1]):
                if colors[i] != selected:
                    continue
                uz, urem = divmod(u, N * N)
                uy, ux = divmod(urem, N)
                dx, dy, dz = abs(ux-x), abs(uy-y), abs(uz-z)
                adjacent = max(dx, dy, dz) <= 1 if selected else dx + dy + dz == 1
                if adjacent:
                    unite(size - 1, i)
            chi = chi0
            for sign, incident in factors_at[step]:
                present = bool(selected)
                if not present:
                    present = any(colors[position[u]] for u in incident if u != step)
                if present:
                    chi += sign
            keep_roots = {root(i) for i in keep}
            closing = {}
            for i in range(size):
                closing.setdefault(root(i), i)
            fg, bg = fg0, bg0
            for r, representative in closing.items():
                if r not in keep_roots:
                    if colors[representative]:
                        fg += 1
                    elif not exterior[r]:
                        bg += 1
            labels = {}
            new_codes = []
            for i in keep:
                r = root(i)
                label = labels.setdefault(r, len(labels))
                new_codes.append((label, colors[i], int(bool(exterior[r]))))
            nxt[(tuple(new_codes), fg, bg, chi)] += multiplicity
    dp = dict(nxt)
    active = [u for u in current if last[u] > step]
    state_counts.append(len(dp))
    assert sum(dp.values()) == 1 << (step + 1)
    for state, multiplicity in sorted(dp.items()):
        certificate.update((repr(state) + ':' + str(multiplicity) + '\n').encode())

histogram = defaultdict(int)
for (_, foreground, bounded_background, chi), count in dp.items():
    beta1 = foreground + bounded_background - chi
    assert beta1 >= 0
    histogram[beta1] += count
expected = {0: 98541568, 1: 27030016, 2: 7812864, 3: 805376, 4: 27648, 5: 256}
assert dict(sorted(histogram.items())) == expected
assert sum(histogram.values()) == 1 << 27
favorable = sum(count for beta, count in histogram.items() if beta)
assert favorable == 35676160
assert certificate.hexdigest() == '3cb381d323714ed3209e2a0ba249d7c7a87e44c638ea103602850f63ee12e7c1'

report_lines = [f'factor_sha256={factor_digest}', f'frontier_sha256={certificate.hexdigest()}',
                'states=' + ','.join(map(str, state_counts))]
report_lines.extend(f'beta1[{beta}]={histogram[beta]}' for beta in sorted(histogram))
report_lines.extend([f'favorable={favorable}', f'zero={histogram[0]}',
                     f'total={sum(histogram.values())}'])
report = '\n'.join(report_lines) + '\n'
assert hashlib.sha256(report.encode()).hexdigest() == '44626fe9d0de5fb11a14ac75915a5a6ebefffda3fb9c50cab10cd0cda9b4a4b1'
print(report, end='')
print('report_sha256=' + hashlib.sha256(report.encode()).hexdigest())
    File identity
    Recorded filename
    R245.txt
    Download SHA-256
    b2576f9abce7dbad3cdb426424d6d25911fe632d5d9a5196ff184f6388d496c8
Continue this work
Replay material: partial

4Reproduce

Replay package: partial

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

Entry point
Join source_lines with LF characters and execute the resulting Python program
Runtime
Python 3.10 or newer, standard library

Verification source: arxiv.org ↗, Python 3.10 standard-library computation executed by TheoremDB entry research on 2026-07-25

Expected output

factor_sha256=63d4b0719908ac018e69de4459b95d63bb5332878c7f3ba5ac840f99562f350d
frontier_sha256=3cb381d323714ed3209e2a0ba249d7c7a87e44c638ea103602850f63ee12e7c1
states=2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,10080,7204,14359,9790,1903,3806,7580,14987,29637,17975,2978,5701,874,22
beta1[0]=98541568
beta1[1]=27030016
beta1[2]=7812864
beta1[3]=805376
beta1[4]=27648
beta1[5]=256
favorable=35676160
zero=98541568
total=134217728
report_sha256=44626fe9d0de5fb11a14ac75915a5a6ebefffda3fb9c50cab10cd0cda9b4a4b1

Missing for a complete replay: command.

Recorded artifact fields
Kind
inline_python_exact_frontier_transfer
Entry point
Join source_lines with LF characters and execute the resulting Python program
Environment
Python 3.10 or newer, standard library

5What it produced

Expected stdout
factor_sha256=63d4b0719908ac018e69de4459b95d63bb5332878c7f3ba5ac840f99562f350d frontier_sha256=3cb381d323714ed3209e2a0ba249d7c7a87e44c638ea103602850f63ee12e7c1 states=2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,10080,7204,14359,9790,1903,3806,7580,14987,29637,17975,2978,5701,874,22 beta1[0]=98541568 beta1[1]=27030016 beta1[2]=7812864 beta1[3]=805376 beta1[4]=27648 beta1[5]=256 favorable=35676160 zero=98541568 total=134217728 report_sha256=44626fe9d0de5fb11a14ac75915a5a6ebefffda3fb9c50cab10cd0cda9b4a4b1
Cubical incidence sha256
63d4b0719908ac018e69de4459b95d63bb5332878c7f3ba5ac840f99562f350d
Frontier state certificate sha256
3cb381d323714ed3209e2a0ba249d7c7a87e44c638ea103602850f63ee12e7c1
Report sha256
44626fe9d0de5fb11a14ac75915a5a6ebefffda3fb9c50cab10cd0cda9b4a4b1
Frontier state counts
2, 4, 8, 16, 32, 64, 128, 256, 512, 1,024, 2,048, 4,096, 8,192, 10,080, 7,204, 14,359, 9,790, 1,903, 3,806, 7,580, 14,987, 29,637, 17,975, 2,978, 5,701, 874, 22

Betti histogram

098,541,568127,030,01627,812,8643805,376427,6485256

6How it connects

Verifies

Supported by

Used by

Recorded for

Machine-readable record

Copy the structured record when continuing this work with an agent.

json
{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R245",
  "content_hash": null,
  "slug": "fcptp-artifact-three-cube-frontier-transfer",
  "type": "artifact",
  "title": "Exact two-connectivity frontier transfer for the three-cube box",
  "summary": "A standard-library Python program branches on every voxel, merges equivalent frontier states, and certifies the full first-Betti histogram.",
  "relevance": "For Exact tunnel probability for site percolation on a four by four by four cubical box, record fcptp-artifact-three-cube-frontier-transfer (“Exact two-connectivity frontier transfer for the three-cube box”) supplies evidence or a replay used to check the packet. The record states: A standard-library Python program branches on every voxel, merges equivalent frontier states, and certifies the full first-Betti histogram.",
  "relevance_source": "recorded",
  "body": "Voxels are introduced in lexicographic \\((z,y,x)\\) order. A state retains the selected bit for each active voxel, the canonical partition of selected voxels under 26-adjacency, the partition of unselected voxels under 6-adjacency, an exterior flag on each background component, closed-component totals, and the current Euler characteristic.\n\nEach of the 343 cubical cells is finalized when its last incident voxel is introduced. Its sign is \\((-1)^d\\), where \\(d\\) is its dimension, and it contributes exactly when at least one incident voxel is selected. A component is counted when its final frontier voxel is forgotten. Every step checks that the sum of state multiplicities is \\(2^i\\), so the transfer accounts for every bit string.\n\nThe 343 incidence records have SHA-256 digest `63d4b0719908ac018e69de4459b95d63bb5332878c7f3ba5ac840f99562f350d`. The sorted state-and-multiplicity stream across all 27 steps has digest `3cb381d323714ed3209e2a0ba249d7c7a87e44c638ea103602850f63ee12e7c1`. The deterministic report has digest `44626fe9d0de5fb11a14ac75915a5a6ebefffda3fb9c50cab10cd0cda9b4a4b1`.",
  "status": "available",
  "evidence_grade": "executable",
  "scope": {
    "kind": "bounded",
    "statement": "all 2^27 subsets of the 27 voxels in a 3 by 3 by 3 box, grouped by exact frontier states while retaining both connectivity partitions and Euler characteristic",
    "bounds": {
      "side_length": {
        "min": 3,
        "max": 3
      },
      "binary_variables": {
        "min": 27,
        "max": 27
      },
      "maximum_cached_states_at_one_step": {
        "min": 29637,
        "max": 29637
      }
    },
    "exhaustive": true
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "partial",
    "kind": "inline_python_exact_frontier_transfer",
    "entrypoint": "Join source_lines with LF characters and execute the resulting Python program",
    "runtime": "Python 3.10 or newer, standard library",
    "citation": {
      "url": "https://arxiv.org/abs/1910.12803",
      "locator": "Python 3.10 standard-library computation executed by TheoremDB entry research on 2026-07-25"
    },
    "outputs": "factor_sha256=63d4b0719908ac018e69de4459b95d63bb5332878c7f3ba5ac840f99562f350d\nfrontier_sha256=3cb381d323714ed3209e2a0ba249d7c7a87e44c638ea103602850f63ee12e7c1\nstates=2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,10080,7204,14359,9790,1903,3806,7580,14987,29637,17975,2978,5701,874,22\nbeta1[0]=98541568\nbeta1[1]=27030016\nbeta1[2]=7812864\nbeta1[3]=805376\nbeta1[4]=27648\nbeta1[5]=256\nfavorable=35676160\nzero=98541568\ntotal=134217728\nreport_sha256=44626fe9d0de5fb11a14ac75915a5a6ebefffda3fb9c50cab10cd0cda9b4a4b1\n",
    "inline_source": [
      "from collections import defaultdict",
      "import hashlib",
      "",
      "N = 3",
      "V = N ** 3",
      "",
      "def voxel(x, y, z):",
      "    return x + N * y + N * N * z",
      "",
      "last = list(range(V))",
      "for z in range(N):",
      "    for y in range(N):",
      "        for x in range(N):",
      "            u = voxel(x, y, z)",
      "            for dz in (-1, 0, 1):",
      "                for dy in (-1, 0, 1):",
      "                    for dx in (-1, 0, 1):",
      "                        xx, yy, zz = x + dx, y + dy, z + dz",
      "                        if 0 <= xx < N and 0 <= yy < N and 0 <= zz < N:",
      "                            last[u] = max(last[u], voxel(xx, yy, zz))",
      "",
      "factors_at = [[] for _ in range(V)]",
      "factor_lines = []",
      "for cz in range(2 * N + 1):",
      "    for cy in range(2 * N + 1):",
      "        for cx in range(2 * N + 1):",
      "            dimension = (cx & 1) + (cy & 1) + (cz & 1)",
      "            incident = tuple(",
      "                voxel(x, y, z)",
      "                for z in range(N)",
      "                for y in range(N)",
      "                for x in range(N)",
      "                if 2 * x <= cx <= 2 * x + 2",
      "                and 2 * y <= cy <= 2 * y + 2",
      "                and 2 * z <= cz <= 2 * z + 2",
      "            )",
      "            sign = 1 if dimension % 2 == 0 else -1",
      "            factors_at[max(incident)].append((sign, incident))",
      "            factor_lines.append(f'{cx},{cy},{cz}:{dimension}:{sign}:' + ','.join(map(str, incident)))",
      "",
      "assert len(factor_lines) == 343",
      "factor_digest = hashlib.sha256(('\\n'.join(factor_lines) + '\\n').encode()).hexdigest()",
      "assert factor_digest == '63d4b0719908ac018e69de4459b95d63bb5332878c7f3ba5ac840f99562f350d'",
      "",
      "dp = {((), 0, 0, 0): 1}",
      "active = []",
      "state_counts = []",
      "certificate = hashlib.sha256()",
      "for step in range(V):",
      "    z, rem = divmod(step, N * N)",
      "    y, x = divmod(rem, N)",
      "    current = active + [step]",
      "    position = {u: i for i, u in enumerate(current)}",
      "    keep = [i for i, u in enumerate(current) if last[u] > step]",
      "    nxt = defaultdict(int)",
      "    for (old_codes, fg0, bg0, chi0), multiplicity in dp.items():",
      "        for selected in (0, 1):",
      "            size = len(current)",
      "            parent = list(range(size))",
      "            colors = [code[1] for code in old_codes] + [selected]",
      "            exterior = [code[2] for code in old_codes] + [int(",
      "                not selected and (x in (0, N-1) or y in (0, N-1) or z in (0, N-1)))]",
      "            first = {}",
      "            for i, code in enumerate(old_codes):",
      "                label = code[0]",
      "                if label in first:",
      "                    parent[i] = first[label]",
      "                else:",
      "                    first[label] = i",
      "            def root(a):",
      "                while parent[a] != a:",
      "                    parent[a] = parent[parent[a]]",
      "                    a = parent[a]",
      "                return a",
      "            for i in range(size - 1):",
      "                r = root(i)",
      "                exterior[r] |= exterior[i]",
      "            def unite(a, b):",
      "                ra, rb = root(a), root(b)",
      "                if ra != rb:",
      "                    parent[rb] = ra",
      "                    exterior[ra] |= exterior[rb]",
      "            for i, u in enumerate(current[:-1]):",
      "                if colors[i] != selected:",
      "                    continue",
      "                uz, urem = divmod(u, N * N)",
      "                uy, ux = divmod(urem, N)",
      "                dx, dy, dz = abs(ux-x), abs(uy-y), abs(uz-z)",
      "                adjacent = max(dx, dy, dz) <= 1 if selected else dx + dy + dz == 1",
      "                if adjacent:",
      "                    unite(size - 1, i)",
      "            chi = chi0",
      "            for sign, incident in factors_at[step]:",
      "                present = bool(selected)",
      "                if not present:",
      "                    present = any(colors[position[u]] for u in incident if u != step)",
      "                if present:",
      "                    chi += sign",
      "            keep_roots = {root(i) for i in keep}",
      "            closing = {}",
      "            for i in range(size):",
      "                closing.setdefault(root(i), i)",
      "            fg, bg = fg0, bg0",
      "            for r, representative in closing.items():",
      "                if r not in keep_roots:",
      "                    if colors[representative]:",
      "                        fg += 1",
      "                    elif not exterior[r]:",
      "                        bg += 1",
      "            labels = {}",
      "            new_codes = []",
      "            for i in keep:",
      "                r = root(i)",
      "                label = labels.setdefault(r, len(labels))",
      "                new_codes.append((label, colors[i], int(bool(exterior[r]))))",
      "            nxt[(tuple(new_codes), fg, bg, chi)] += multiplicity",
      "    dp = dict(nxt)",
      "    active = [u for u in current if last[u] > step]",
      "    state_counts.append(len(dp))",
      "    assert sum(dp.values()) == 1 << (step + 1)",
      "    for state, multiplicity in sorted(dp.items()):",
      "        certificate.update((repr(state) + ':' + str(multiplicity) + '\\n').encode())",
      "",
      "histogram = defaultdict(int)",
      "for (_, foreground, bounded_background, chi), count in dp.items():",
      "    beta1 = foreground + bounded_background - chi",
      "    assert beta1 >= 0",
      "    histogram[beta1] += count",
      "expected = {0: 98541568, 1: 27030016, 2: 7812864, 3: 805376, 4: 27648, 5: 256}",
      "assert dict(sorted(histogram.items())) == expected",
      "assert sum(histogram.values()) == 1 << 27",
      "favorable = sum(count for beta, count in histogram.items() if beta)",
      "assert favorable == 35676160",
      "assert certificate.hexdigest() == '3cb381d323714ed3209e2a0ba249d7c7a87e44c638ea103602850f63ee12e7c1'",
      "",
      "report_lines = [f'factor_sha256={factor_digest}', f'frontier_sha256={certificate.hexdigest()}',",
      "                'states=' + ','.join(map(str, state_counts))]",
      "report_lines.extend(f'beta1[{beta}]={histogram[beta]}' for beta in sorted(histogram))",
      "report_lines.extend([f'favorable={favorable}', f'zero={histogram[0]}',",
      "                     f'total={sum(histogram.values())}'])",
      "report = '\\n'.join(report_lines) + '\\n'",
      "assert hashlib.sha256(report.encode()).hexdigest() == '44626fe9d0de5fb11a14ac75915a5a6ebefffda3fb9c50cab10cd0cda9b4a4b1'",
      "print(report, end='')",
      "print('report_sha256=' + hashlib.sha256(report.encode()).hexdigest())"
    ],
    "missing": [
      "command"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://arxiv.org/abs/1910.12803",
    "locator": "Python 3.10 standard-library computation executed by TheoremDB entry research on 2026-07-25"
  },
  "models": [],
  "continuation": null,
  "relations": [
    {
      "slug": "R247",
      "title": "The exact three-cube tunnel probability is 4,355 over 16,384",
      "object_type": "claim",
      "relation": "verifies",
      "direction": "outgoing"
    },
    {
      "slug": "R248",
      "title": "First homology reduces to two connectivity counts and Euler characteristic",
      "object_type": "claim",
      "relation": "supports",
      "direction": "incoming"
    },
    {
      "slug": "R246",
      "title": "The four-cube exact numerator remains open in this entry",
      "object_type": "attempt",
      "relation": "uses",
      "direction": "incoming"
    },
    {
      "slug": "four-cube-site-percolation-tunnel-probability",
      "title": "four cube site percolation tunnel probability",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}

8Provenance

View source, identifiers, and projection details
Project
four-cube-site-percolation-tunnel-probability
Locator
Python 3.10 standard-library computation executed by TheoremDB entry research on 2026-07-25
License
CC0-1.0
Contributors
TheoremDB entry research, 2026-07-25
Source
arxiv.org ↗
Public record
R245
Stable alias
fcptp-artifact-three-cube-frontier-transfer
Projection
Reproduction fields are derived from the immutable record.

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

Sign in to follow

Sign in in another tab, then return here.

Open sign-in in another tab

Report a problem

Report location:

Your ChatGPT account

Opening ChatGPT

ChatGPT is opening in a new tab.