TheoremDB

Problem packetResearch packetR398

R398Executable evidence

Exact 2,584-mask transfer polynomial

View replayOpen source ↗
Link to a section

Authored summary

A short C++17 program computes all coefficients with unsigned 256-bit addition and a subset zeta transform.

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

Recorded status: available

Recorded scope: all independent sets of P16 Cartesian-product P16, grouped exactly by cardinality through a 2,584-mask row transfer

Complete recorded scope and conditions
{
  "kind": "bounded",
  "statement": "all independent sets of P16 Cartesian-product P16, grouped exactly by cardinality through a 2,584-mask row transfer",
  "bounds": {
    "grid_side": {
      "min": 16,
      "max": 16
    },
    "valid_row_masks": {
      "min": 2584,
      "max": 2584
    },
    "coefficients": {
      "min": 129,
      "max": 129
    }
  },
  "exhaustive": true
}

Originating problem: Nearest hard-square partition-function zero for the sixteen grid

Read the full authored explanationInspect the parent problem’s formal coverageFull source
Authored record and scope
Authored title
Exact 2,584-mask transfer polynomial
Record type
artifact
Stored status
available
Evidence grade
executable
Recorded scope data
{ "kind": "bounded", "statement": "all independent sets of P16 Cartesian-product P16, grouped exactly by cardinality through a 2,584-mask row transfer", "bounds": { "grid_side": { "min": 16, "max": 16 }, "valid_row_masks": { "min": 2584, "max": 2584 }, "coefficients": { "min": 129, "max": 129 } }, "exhaustive": true }

2Authored explanation

A row state is a sixteen-bit mask \(m\) satisfying \(m\mathbin{\&}(m\ll1)=0\). There are 2,584 such masks. If \(F_r(m;z)\) counts configurations on the first \(r\) rows ending at \(m\), then \[ F_{r+1}(m;z)=z^{|m|}\sum_{s\mathbin{\&}m=0}F_r(s;z). \] The program evaluates every compatibility sum by a subset zeta transform over all \(2^{16}\) masks. Each coefficient is below the total number of subsets \(2^{256}\), so four unsigned 64-bit limbs suffice. The coefficient order is increasing degree.

The run gives \(Z_{16}(1)=18396766424410124752958806046933947217821482942\). Its comma-separated coefficient vector has SHA-256 `a65ab0dc72ec69b3408416bfc816478869e6542f1076592842277e109c515d96`. Compiling the same source with `-DGRID_SIDE=12` reproduces the candidate record's twelve-grid count and coefficient hash.

Files and source

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

  • R398.txt2,434 bytes · No SHA-256 recorded
    Preview R398.txt
    #include <algorithm>
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
struct U256 { uint64_t x[4] = {0,0,0,0}; };
static inline void add_to(U256 &a, const U256 &b) {
    uint64_t old=a.x[0]; a.x[0]+=b.x[0]; uint64_t carry=a.x[0]<old;
    for (int i=1;i<4;++i) {
        uint64_t bi=b.x[i]+carry, overflow=bi<b.x[i];
        old=a.x[i]; a.x[i]+=bi; carry=overflow || a.x[i]<old;
    }
}
static string decimal(U256 a) {
    if (!(a.x[0]|a.x[1]|a.x[2]|a.x[3])) return "0";
    string out;
    while (a.x[0]|a.x[1]|a.x[2]|a.x[3]) {
        unsigned __int128 rem=0;
        for (int i=3;i>=0;--i) {
            unsigned __int128 cur=(rem<<64)|a.x[i];
            a.x[i]=uint64_t(cur/10); rem=cur%10;
        }
        out.push_back(char('0'+int(rem)));
    }
    reverse(out.begin(),out.end()); return out;
}
int main() {
#ifndef GRID_SIDE
#define GRID_SIDE 16
#endif
    constexpr int W=GRID_SIDE,H=GRID_SIDE,N=1<<W,D=(W*H+1)/2;
    vector<int> states,weight;
    for (int m=0;m<N;++m) if (!(m&(m<<1))) {
        states.push_back(m); weight.push_back(__builtin_popcount(unsigned(m)));
    }
    int S=states.size(), row_cap=(W+1)/2, full=N-1;
    vector<U256> dp(size_t(S)*(D+1)),zeta(size_t(N)*(D+1)),next(size_t(S)*(D+1));
    for (int i=0;i<S;++i) dp[size_t(i)*(D+1)+weight[i]].x[0]=1;
    for (int row=2;row<=H;++row) {
        int old_degree=row_cap*(row-1); fill(zeta.begin(),zeta.end(),U256{});
        for (int i=0;i<S;++i) {
            U256 *dst=&zeta[size_t(states[i])*(D+1)],*src=&dp[size_t(i)*(D+1)];
            copy(src,src+old_degree+1,dst);
        }
        for (int bit=0;bit<W;++bit) {
            int step=1<<bit;
            for (int base=0;base<N;base+=2*step) for (int off=0;off<step;++off) {
                U256 *lo=&zeta[size_t(base+off)*(D+1)],*hi=&zeta[size_t(base+off+step)*(D+1)];
                for (int k=0;k<=old_degree;++k) add_to(hi[k],lo[k]);
            }
        }
        fill(next.begin(),next.end(),U256{});
        for (int i=0;i<S;++i) {
            U256 *src=&zeta[size_t(full^states[i])*(D+1)],*dst=&next[size_t(i)*(D+1)];
            copy(src,src+old_degree+1,dst+weight[i]);
        }
        dp.swap(next);
    }
    vector<U256> answer(D+1);
    for (int i=0;i<S;++i) for (int k=0;k<=D;++k) add_to(answer[k],dp[size_t(i)*(D+1)+k]);
    cout<<"[";
    for (int k=0;k<=D;++k) { if (k) cout<<","; cout<<decimal(answer[k]); }
    cout<<"]\n";
}
    File identity
    Recorded filename
    R398.txt
    Download SHA-256
    49c53324a9f045013e9e5c0c95fed0718a27c1e05028ff68d724dbcb704cb95b
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 newline characters, save as hs.cpp, run clang++ -O3 -std=c++17 hs.cpp -o hs, then run ./hs > hs16_coefficients.json
Runtime
Clang or GCC with C++17 and unsigned __int128 support

Verification source: doi.org ↗, Inline C++17 exact computation executed on 2026-07-25

Missing for a complete replay: command, expected output.

Recorded artifact fields
Kind
inline_cpp17_exact_transfer
Entry point
Join source_lines with newline characters, save as hs.cpp, run clang++ -O3 -std=c++17 hs.cpp -o hs, then run ./hs > hs16_coefficients.json
Environment
Clang or GCC with C++17 and unsigned __int128 support

5What it produced

Observed runtime
2.5 seconds on the entry-research host
Expected stdout sha256
77a2256a71c01f0a0219df0188040f91df3365556bd2dd1e2e4e990fc038756c
Arithmetic
exact nonnegative integers in four 64-bit limbs
Coefficient order
increasing independent-set cardinality
Coefficients
1, 256, 32,160, 2,642,948, 159,819,965, 7,583,888,944, 294,116,445,082, 9,586,626,461,484, 268,042,562,131,202, 6,529,640,029,479,296, 140,292,065,573,112,240, 2,684,820,237,664,173,000, 46,137,486,207,152,720,000, 716,785,476,860,832,500,000, 10,125,376,419,432,407,000,000, 130,693,302,168,423,110,000,000, 1,547,966,111,897,855,800,000,000, 16,886,743,887,576,602,000,000,000, 170,224,484,349,604,150,000,000,000, 1,590,162,726,915,765,800,000,000,000, 13,801,234,621,550,207,000,000,000,000, 111,544,035,335,140,060,000,000,000,000, 841,240,752,575,465,900,000,000,000,000, 5,931,234,639,932,188,000,000,000,000,000, 39,160,581,224,415,110,000,000,000,000,000, 242,489,657,883,417,130,000,000,000,000,000, 1,410,193,302,860,580,500,000,000,000,000,000, 7,711,766,242,736,540,000,000,000,000,000,000, 39,702,719,832,284,450,000,000,000,000,000,000, 192,635,894,838,614,820,000,000,000,000,000,000, 881,711,190,047,020,000,000,000,000,000,000,000, 3,810,441,833,337,392,000,000,000,000,000,000,000, 15,561,131,207,635,070,000,000,000,000,000,000,000, 60,097,039,303,515,910,000,000,000,000,000,000,000, 219,641,868,055,275,900,000,000,000,000,000,000,000, 760,166,068,794,365,800,000,000,000,000,000,000,000, 2,492,834,479,242,687,500,000,000,000,000,000,000,000, 7,750,171,564,296,261,000,000,000,000,000,000,000,000, 22,855,253,727,387,025,000,000,000,000,000,000,000,000, 63,962,543,862,141,440,000,000,000,000,000,000,000,000, 169,951,095,009,293,110,000,000,000,000,000,000,000,000, 428,905,027,974,318,840,000,000,000,000,000,000,000,000, 1,028,502,906,703,565,100,000,000,000,000,000,000,000,000, 2,344,306,443,500,758,000,000,000,000,000,000,000,000,000, 5,080,832,998,585,362,000,000,000,000,000,000,000,000,000, 10,473,822,701,204,753,000,000,000,000,000,000,000,000,000, 20,542,584,160,465,103,000,000,000,000,000,000,000,000,000, 38,344,830,319,690,690,000,000,000,000,000,000,000,000,000, 68,135,911,827,580,650,000,000,000,000,000,000,000,000,000, 115,284,908,653,084,700,000,000,000,000,000,000,000,000,000, 185,780,579,146,687,200,000,000,000,000,000,000,000,000,000, 285,206,435,500,928,840,000,000,000,000,000,000,000,000,000, 417,200,840,269,656,300,000,000,000,000,000,000,000,000,000, 581,634,525,228,307,800,000,000,000,000,000,000,000,000,000, 772,972,158,952,516,000,000,000,000,000,000,000,000,000,000, 979,430,262,902,602,000,000,000,000,000,000,000,000,000,000, 1,183,490,785,642,597,100,000,000,000,000,000,000,000,000,000, 1,364,025,800,620,496,400,000,000,000,000,000,000,000,000,000, 1,499,791,146,693,530,500,000,000,000,000,000,000,000,000,000, 1,573,525,193,173,722,600,000,000,000,000,000,000,000,000,000, 1,575,564,424,147,713,500,000,000,000,000,000,000,000,000,000, 1,505,927,927,427,760,700,000,000,000,000,000,000,000,000,000, 1,374,249,196,802,977,200,000,000,000,000,000,000,000,000,000, 1,197,595,288,971,715,000,000,000,000,000,000,000,000,000,000, 996,852,200,704,424,600,000,000,000,000,000,000,000,000,000, 792,727,215,726,444,300,000,000,000,000,000,000,000,000,000, 602,405,863,346,743,400,000,000,000,000,000,000,000,000,000, 437,553,971,588,990,350,000,000,000,000,000,000,000,000,000, 303,851,018,009,225,270,000,000,000,000,000,000,000,000,000, 201,786,238,850,313,100,000,000,000,000,000,000,000,000,000, 128,187,422,800,270,180,000,000,000,000,000,000,000,000,000, 77,920,213,936,963,240,000,000,000,000,000,000,000,000,000, 45,335,730,883,336,770,000,000,000,000,000,000,000,000,000, 25,255,696,369,902,980,000,000,000,000,000,000,000,000,000, 13,475,869,360,568,534,000,000,000,000,000,000,000,000,000, 6,889,565,607,860,232,000,000,000,000,000,000,000,000,000, 3,376,230,937,978,520,000,000,000,000,000,000,000,000,000, 1,586,552,451,023,699,300,000,000,000,000,000,000,000,000, 715,228,397,755,438,900,000,000,000,000,000,000,000,000, 309,455,789,568,193,740,000,000,000,000,000,000,000,000, 128,564,510,105,869,450,000,000,000,000,000,000,000,000, 51,312,930,311,070,960,000,000,000,000,000,000,000,000, 19,685,196,542,572,850,000,000,000,000,000,000,000,000, 7,262,614,892,732,892,000,000,000,000,000,000,000,000, 2,578,269,904,892,573,700,000,000,000,000,000,000,000, 881,243,054,375,631,100,000,000,000,000,000,000,000, 290,169,755,756,357,830,000,000,000,000,000,000,000, 92,100,310,323,111,770,000,000,000,000,000,000,000, 28,196,221,982,781,710,000,000,000,000,000,000,000, 8,331,310,796,539,600,000,000,000,000,000,000,000, 2,377,395,145,050,257,500,000,000,000,000,000,000, 655,581,763,133,025,850,000,000,000,000,000,000, 174,806,387,874,434,070,000,000,000,000,000,000, 45,097,436,565,125,720,000,000,000,000,000,000, 11,263,061,586,578,341,000,000,000,000,000,000, 2,724,567,704,287,823,700,000,000,000,000,000, 638,667,445,541,816,900,000,000,000,000,000, 145,128,028,943,172,580,000,000,000,000,000, 31,977,426,561,005,740,000,000,000,000,000, 6,832,954,665,106,373,000,000,000,000,000, 1,415,894,386,745,805,500,000,000,000,000, 284,451,592,971,001,370,000,000,000,000, 55,378,190,174,443,950,000,000,000,000, 10,440,159,013,183,194,000,000,000,000, 1,904,038,195,320,566,600,000,000,000, 335,487,397,096,747,840,000,000,000, 57,017,160,261,028,210,000,000,000, 9,328,750,481,702,745,000,000,000, 1,466,060,782,634,167,000,000,000, 220,737,049,578,199,660,000,000, 31,749,556,213,030,444,000,000, 4,348,493,709,176,228,300,000, 565,097,568,744,301,800,000, 69,400,756,227,418,360,000, 8,019,299,716,819,514,000, 867,524,206,182,433,900, 87,368,933,749,120,450, 8,138,936,960,170,700, 696,101,731,894,034, 54,182,136,895,392, 3,797,894,576,222, 236,662,113,616, 12,899,279,952, 602,129,572, 23,391,608, 725,672, 16,846, 260, 2

Certificate

degree128valid row masks2,584coefficient count129coefficient csv sha256a65ab0dc72ec69b3408416bfc816478869e6542f1076592842277e109c515d96polynomial json stdout sha25677a2256a71c01f0a0219df0188040f91df3365556bd2dd1e2e4e990fc038756cz at 118396766424410124752958806046933947217821482942side 12 crosscheck z at 1162481813349792588536582997side 12 crosscheck coefficient csv sha256c36cdf2efa005e88c21469a24059de8c03f63010de218a42ac3e990411d1e820

6How it connects

Reproduces

Recorded for

Machine-readable record

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

json
{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R398",
  "content_hash": null,
  "slug": "hs16-artifact-exact-polynomial",
  "type": "artifact",
  "title": "Exact 2,584-mask transfer polynomial",
  "summary": "A short C++17 program computes all coefficients with unsigned 256-bit addition and a subset zeta transform.",
  "relevance": "For Nearest hard-square partition-function zero for the sixteen grid, record hs16-artifact-exact-polynomial (“Exact 2,584-mask transfer polynomial”) supplies evidence or a replay used to check the packet. The record states: A short C++17 program computes all coefficients with unsigned 256-bit addition and a subset zeta transform.",
  "relevance_source": "recorded",
  "body": "A row state is a sixteen-bit mask \\(m\\) satisfying \\(m\\mathbin{\\&}(m\\ll1)=0\\). There are 2,584 such masks. If \\(F_r(m;z)\\) counts configurations on the first \\(r\\) rows ending at \\(m\\), then\n\\[\nF_{r+1}(m;z)=z^{|m|}\\sum_{s\\mathbin{\\&}m=0}F_r(s;z).\n\\]\nThe program evaluates every compatibility sum by a subset zeta transform over all \\(2^{16}\\) masks. Each coefficient is below the total number of subsets \\(2^{256}\\), so four unsigned 64-bit limbs suffice. The coefficient order is increasing degree.\n\nThe run gives \\(Z_{16}(1)=18396766424410124752958806046933947217821482942\\). Its comma-separated coefficient vector has SHA-256 `a65ab0dc72ec69b3408416bfc816478869e6542f1076592842277e109c515d96`. Compiling the same source with `-DGRID_SIDE=12` reproduces the candidate record's twelve-grid count and coefficient hash.",
  "status": "available",
  "evidence_grade": "executable",
  "scope": {
    "kind": "bounded",
    "statement": "all independent sets of P16 Cartesian-product P16, grouped exactly by cardinality through a 2,584-mask row transfer",
    "bounds": {
      "grid_side": {
        "min": 16,
        "max": 16
      },
      "valid_row_masks": {
        "min": 2584,
        "max": 2584
      },
      "coefficients": {
        "min": 129,
        "max": 129
      }
    },
    "exhaustive": true
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "partial",
    "kind": "inline_cpp17_exact_transfer",
    "entrypoint": "Join source_lines with newline characters, save as hs.cpp, run clang++ -O3 -std=c++17 hs.cpp -o hs, then run ./hs > hs16_coefficients.json",
    "runtime": "Clang or GCC with C++17 and unsigned __int128 support",
    "citation": {
      "url": "https://doi.org/10.1007/s10955-004-2055-4",
      "locator": "Inline C++17 exact computation executed on 2026-07-25"
    },
    "inline_source": [
      "#include <algorithm>",
      "#include <cstdint>",
      "#include <iostream>",
      "#include <string>",
      "#include <vector>",
      "using namespace std;",
      "struct U256 { uint64_t x[4] = {0,0,0,0}; };",
      "static inline void add_to(U256 &a, const U256 &b) {",
      "    uint64_t old=a.x[0]; a.x[0]+=b.x[0]; uint64_t carry=a.x[0]<old;",
      "    for (int i=1;i<4;++i) {",
      "        uint64_t bi=b.x[i]+carry, overflow=bi<b.x[i];",
      "        old=a.x[i]; a.x[i]+=bi; carry=overflow || a.x[i]<old;",
      "    }",
      "}",
      "static string decimal(U256 a) {",
      "    if (!(a.x[0]|a.x[1]|a.x[2]|a.x[3])) return \"0\";",
      "    string out;",
      "    while (a.x[0]|a.x[1]|a.x[2]|a.x[3]) {",
      "        unsigned __int128 rem=0;",
      "        for (int i=3;i>=0;--i) {",
      "            unsigned __int128 cur=(rem<<64)|a.x[i];",
      "            a.x[i]=uint64_t(cur/10); rem=cur%10;",
      "        }",
      "        out.push_back(char('0'+int(rem)));",
      "    }",
      "    reverse(out.begin(),out.end()); return out;",
      "}",
      "int main() {",
      "#ifndef GRID_SIDE",
      "#define GRID_SIDE 16",
      "#endif",
      "    constexpr int W=GRID_SIDE,H=GRID_SIDE,N=1<<W,D=(W*H+1)/2;",
      "    vector<int> states,weight;",
      "    for (int m=0;m<N;++m) if (!(m&(m<<1))) {",
      "        states.push_back(m); weight.push_back(__builtin_popcount(unsigned(m)));",
      "    }",
      "    int S=states.size(), row_cap=(W+1)/2, full=N-1;",
      "    vector<U256> dp(size_t(S)*(D+1)),zeta(size_t(N)*(D+1)),next(size_t(S)*(D+1));",
      "    for (int i=0;i<S;++i) dp[size_t(i)*(D+1)+weight[i]].x[0]=1;",
      "    for (int row=2;row<=H;++row) {",
      "        int old_degree=row_cap*(row-1); fill(zeta.begin(),zeta.end(),U256{});",
      "        for (int i=0;i<S;++i) {",
      "            U256 *dst=&zeta[size_t(states[i])*(D+1)],*src=&dp[size_t(i)*(D+1)];",
      "            copy(src,src+old_degree+1,dst);",
      "        }",
      "        for (int bit=0;bit<W;++bit) {",
      "            int step=1<<bit;",
      "            for (int base=0;base<N;base+=2*step) for (int off=0;off<step;++off) {",
      "                U256 *lo=&zeta[size_t(base+off)*(D+1)],*hi=&zeta[size_t(base+off+step)*(D+1)];",
      "                for (int k=0;k<=old_degree;++k) add_to(hi[k],lo[k]);",
      "            }",
      "        }",
      "        fill(next.begin(),next.end(),U256{});",
      "        for (int i=0;i<S;++i) {",
      "            U256 *src=&zeta[size_t(full^states[i])*(D+1)],*dst=&next[size_t(i)*(D+1)];",
      "            copy(src,src+old_degree+1,dst+weight[i]);",
      "        }",
      "        dp.swap(next);",
      "    }",
      "    vector<U256> answer(D+1);",
      "    for (int i=0;i<S;++i) for (int k=0;k<=D;++k) add_to(answer[k],dp[size_t(i)*(D+1)+k]);",
      "    cout<<\"[\";",
      "    for (int k=0;k<=D;++k) { if (k) cout<<\",\"; cout<<decimal(answer[k]); }",
      "    cout<<\"]\\n\";",
      "}"
    ],
    "missing": [
      "command",
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://doi.org/10.1007/s10955-004-2055-4",
    "locator": "Inline C++17 exact computation executed on 2026-07-25"
  },
  "models": [],
  "relations": [
    {
      "slug": "R401",
      "title": "A certified radius bracket and an isolated real zero for the sixteen grid",
      "object_type": "claim",
      "relation": "reproduces",
      "direction": "outgoing"
    },
    {
      "slug": "hard-square-sixteen-zero-radius",
      "title": "hard square sixteen zero radius",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}

8Provenance

View source, identifiers, and projection details
Project
hard-square-sixteen-zero-radius
Locator
Inline C++17 exact computation executed on 2026-07-25
License
CC0-1.0
Contributors
TheoremDB entry research, 2026-07-25
Source
doi.org ↗
Public record
R398
Stable alias
hs16-artifact-exact-polynomial
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.