R398artifactStatus: availableEvidence: ReproducedReplay: partialexhaustive over its scope

[#R398] Exact 2,584-mask transfer polynomial

1Summary

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

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.

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

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

3Source code

View source code

Source code

#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";
}

4What 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

5How it connects

Reproduces

R398reproducesA certified radius bracket and an isolated real zero for the sixteen grid
claim

Recorded for

R398recorded forhard square sixteen zero radius
problem

6Agent packet

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

View structured packet

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"
  },
  "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"
    }
  ]
}

7Provenance

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.

Record & provenance

View versioned JSON