{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R59",
  "content_hash": null,
  "slug": "bbmb-claim-verified-through-100-million",
  "type": "claim",
  "title": "The bound and equality characterization hold through 100 million",
  "summary": "Exact search verifies the proposed bound for all 50 million odd inputs through \\(10^8\\), with equality exactly at the 26 Mersenne inputs in that range; the bound and equality characterization for odd \\(n>10^8\\) remain open.",
  "relevance": "For Sharp multipliers for balanced binary products, record bbmb-claim-verified-through-100-million (“The bound and equality characterization hold through 100 million”) records a bound, answer, status fact, or structural consequence. The record states: Exact search verifies the proposed bound for all 50 million odd inputs through \\(10^8\\), with equality exactly at the 26 Mersenne inputs in that range; the bound and equality characterization for odd \\(n>10^8\\) remain open.",
  "relevance_source": "recorded",
  "body": "For each odd \\(n\\leq10^8\\), the computation set \\(m=\\operatorname{bitlength}(n)\\), \\(B=2^{m-1}+1\\), and tested \\(k=1,2,\\ldots,B\\) in order. The first \\(k\\) for which \\(kn\\) had even bit length and half of its bits equal to 1 was recorded as \\(k(n)\\).\n\nThis loop gives a finite stopping proof for each input. Finding a balanced product at \\(k\\) proves minimality because every smaller multiplier has been rejected. Exhausting \\(1\\leq k\\leq B\\) would exhibit a counterexample to the bound. A hit at \\(B\\) is compared directly with \\(n=2^m-1\\), so either direction of the proposed equality characterization would stop the run on its first failure.\n\nThe run checked 50,000,000 odd values of \\(n\\) and 724,052,131 multiplier candidates. It found no failure. Equality occurred 26 times, at \\(n=2^m-1\\) for \\(1\\leq m\\leq26\\). The largest minimum in range was \\(k(67108863)=33554433\\). The FNV-1a checksum of the little-endian 64-bit words \\((n\\ll32)\\mathbin{|}k(n)\\), in increasing \\(n\\), is `6955bbea71c91c4c`.\n\nThis record certifies the stated finite range. The universal bound and the converse assertion about equality remain open in this entry.",
  "status": "supported",
  "evidence_grade": "computational",
  "scope": {
    "kind": "bounded",
    "statement": "every odd integer n from 1 through 100000000",
    "bounds": {
      "n": {
        "min": 1,
        "max": 100000000
      }
    },
    "exhaustive": true
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "source_only",
    "kind": "claim",
    "citation": {
      "url": "https://arxiv.org/abs/1909.08849",
      "locator": "Exact exhaustive C computation run by TheoremDB entry research on 2026-07-24"
    },
    "missing": [
      "source",
      "command",
      "runtime",
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://arxiv.org/abs/1909.08849",
    "locator": "Exact exhaustive C computation run by TheoremDB entry research on 2026-07-24"
  },
  "models": [],
  "relations": [
    {
      "slug": "R55",
      "title": "Exact multiplier sweep through 100 million",
      "object_type": "artifact",
      "relation": "supports",
      "direction": "incoming"
    },
    {
      "slug": "R58",
      "title": "Every Mersenne input attains the proposed bound",
      "object_type": "claim",
      "relation": "informs",
      "direction": "incoming"
    },
    {
      "slug": "R56",
      "title": "A carry-free criterion reduces part of the search to popcounts",
      "object_type": "attempt",
      "relation": "attempts",
      "direction": "incoming"
    },
    {
      "slug": "balanced-binary-multiplier-bound",
      "title": "balanced binary multiplier bound",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}