{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R476",
  "content_hash": null,
  "slug": "lwf101-artifact-exhaustive-mitm",
  "type": "artifact",
  "title": "Complete 15-plus-15 meet-in-the-middle root sweep",
  "summary": "The compact C++ program evaluates every sign vector and emits a full histogram whose counts sum to 2^30.",
  "relevance": "This supplies a computation, dataset, or executable check used to assess the target problem.",
  "relevance_source": "derived",
  "body": "A mask bit equal to one means coefficient \\(+1\\), and a zero bit means \\(-1\\). The left mask covers exponents 1 through 15; the right mask covers exponents 16 through 30. For each left mask \\(l\\) and field element \\(x\\), the program computes the residue required of the right half for \\(x\\) to be a root. It compares this residue with all 32,768 right-half evaluations and increments one byte-sized counter per right mask. Scanning those counters covers every pair exactly once. The histogram is a compact fingerprint of the complete run. Its entries total 1,073,741,824. The winning masks \\((2118,22660)\\) reproduce the displayed polynomial and its 12 roots by direct evaluation.",
  "status": "available",
  "evidence_grade": "executable",
  "scope": {
    "kind": "bounded",
    "statement": "all sign vectors for degree-30 Littlewood polynomials over F_101 with constant coefficient 1",
    "bounds": {
      "left_masks": {
        "min": 32768,
        "max": 32768
      },
      "right_masks": {
        "min": 32768,
        "max": 32768
      },
      "combined_vectors": {
        "min": 1073741824,
        "max": 1073741824
      },
      "field_elements": {
        "min": 101,
        "max": 101
      }
    },
    "exhaustive": true
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "partial",
    "kind": "inline_cpp_computation",
    "entrypoint": "join source_lines with newline, compile using c++ -O3 -std=c++17 -pthread, and run",
    "runtime": "C++17 compiler with standard threads",
    "citation": {
      "url": "https://doi.org/10.1112/S1461157016000334",
      "locator": "Inline C++17 computation executed on 2026-07-24; observed wall time 1.46 seconds on a 10-core arm64 host"
    },
    "outputs": "vectors=1073741824 max_roots=12 left_mask=2118 right_mask=22660\nsigns=-1,1,1,-1,-1,-1,1,-1,-1,-1,-1,1,-1,-1,-1,-1,-1,1,-1,-1,-1,-1,1,-1,-1,-1,1,1,-1,1\nroots=20,30,43,47,63,64,66,72,75,93,94,96\nhistogram=0:410596694,1:396276760,2:189713264,3:59997436,4:14088666,5:2612332,6:398654,7:51664,8:5750,9:552,10:50,12:2\n",
    "inline_source": [
      "#include <algorithm>",
      "#include <array>",
      "#include <cstdint>",
      "#include <iostream>",
      "#include <thread>",
      "#include <vector>",
      "using namespace std;",
      "constexpr int P = 101, H = 15, N = 1 << H;",
      "static vector<uint8_t> left_eval(P*N), right_eval(P*N);",
      "struct Result { array<uint64_t, 102> hist{}; int best = -1; uint64_t code = ~uint64_t(0); };",
      "",
      "int main() {",
      "  int power[31][P];",
      "  for (int x = 0; x < P; ++x) {",
      "    power[0][x] = 1;",
      "    for (int k = 1; k <= 30; ++k) power[k][x] = power[k-1][x] * x % P;",
      "  }",
      "  for (int x = 0; x < P; ++x) {",
      "    int sl = 0, sr = 0;",
      "    for (int k = 1; k <= 15; ++k) sl += power[k][x];",
      "    for (int k = 16; k <= 30; ++k) sr += power[k][x];",
      "    left_eval[x*N] = uint8_t((P - sl % P) % P);",
      "    right_eval[x*N] = uint8_t((P - sr % P) % P);",
      "    for (int m = 1; m < N; ++m) {",
      "      int bit = __builtin_ctz((unsigned)m), prev = m & (m-1);",
      "      left_eval[x*N+m] = uint8_t((left_eval[x*N+prev] + 2*power[bit+1][x]) % P);",
      "      right_eval[x*N+m] = uint8_t((right_eval[x*N+prev] + 2*power[bit+16][x]) % P);",
      "    }",
      "  }",
      "  unsigned nt = max(1u, thread::hardware_concurrency());",
      "  vector<Result> result(nt);",
      "  vector<thread> workers;",
      "  for (unsigned tid = 0; tid < nt; ++tid) workers.emplace_back([&, tid] {",
      "    vector<uint8_t> count(N);",
      "    int lo = int(uint64_t(N) * tid / nt);",
      "    int hi = int(uint64_t(N) * (tid+1) / nt);",
      "    for (int l = lo; l < hi; ++l) {",
      "      fill(count.begin(), count.end(), 0);",
      "      for (int x = 0; x < P; ++x) {",
      "        uint8_t target = uint8_t((P - 1 - left_eval[x*N+l]) % P);",
      "        const uint8_t* rp = &right_eval[x*N];",
      "        for (int r = 0; r < N; ++r) count[r] += uint8_t(rp[r] == target);",
      "      }",
      "      for (int r = 0; r < N; ++r) {",
      "        int c = count[r];",
      "        result[tid].hist[c]++;",
      "        uint64_t code = (uint64_t(l) << H) | uint32_t(r);",
      "        if (c > result[tid].best || (c == result[tid].best && code < result[tid].code)) {",
      "          result[tid].best = c;",
      "          result[tid].code = code;",
      "        }",
      "      }",
      "    }",
      "  });",
      "  for (auto& worker : workers) worker.join();",
      "  Result all;",
      "  for (const auto& q : result) {",
      "    for (int i = 0; i <= 101; ++i) all.hist[i] += q.hist[i];",
      "    if (q.best > all.best || (q.best == all.best && q.code < all.code)) {",
      "      all.best = q.best;",
      "      all.code = q.code;",
      "    }",
      "  }",
      "  uint32_t lm = uint32_t(all.code >> H), rm = uint32_t(all.code) & (N-1);",
      "  cout << \"vectors=\" << uint64_t(N)*N << \" max_roots=\" << all.best",
      "       << \" left_mask=\" << lm << \" right_mask=\" << rm << '\\n';",
      "  cout << \"signs=\";",
      "  for (int k = 0; k < 30; ++k) {",
      "    int bit = k < 15 ? ((lm >> k) & 1) : ((rm >> (k-15)) & 1);",
      "    if (k) cout << ',';",
      "    cout << (bit ? 1 : -1);",
      "  }",
      "  cout << \"\\nroots=\";",
      "  bool first = true;",
      "  for (int x = 0; x < P; ++x) {",
      "    if ((1 + left_eval[x*N+lm] + right_eval[x*N+rm]) % P == 0) {",
      "      if (!first) cout << ',';",
      "      first = false;",
      "      cout << x;",
      "    }",
      "  }",
      "  cout << \"\\nhistogram=\";",
      "  first = true;",
      "  for (int i = 0; i <= 101; ++i) if (all.hist[i]) {",
      "    if (!first) cout << ',';",
      "    first = false;",
      "    cout << i << ':' << all.hist[i];",
      "  }",
      "  cout << '\\n';",
      "}"
    ],
    "missing": [
      "command"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://doi.org/10.1112/S1461157016000334",
    "locator": "Inline C++17 computation executed on 2026-07-24; observed wall time 1.46 seconds on a 10-core arm64 host"
  },
  "models": [],
  "continuation": null,
  "relations": [
    {
      "slug": "R478",
      "title": "The exact maximum number of roots is 12",
      "object_type": "claim",
      "relation": "supports",
      "direction": "outgoing"
    },
    {
      "slug": "littlewood-f101-max-roots-30",
      "title": "littlewood f101 max roots 30",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}