{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R540",
  "content_hash": null,
  "slug": "ms200-claim-certified-interval-71-145",
  "type": "claim",
  "title": "The certified interval is 71 through 145",
  "summary": "A displayed 71-set has 2,556 distinct unordered pair products; the complete collision-hypergraph LP gives the integer upper bound 145.",
  "relevance": "For Largest multiplicative Sidon subset of the first 200 integers, record ms200-claim-certified-interval-71-145 (“The certified interval is 71 through 145”) records a bound, answer, status fact, or structural consequence. The record states: A displayed 71-set has 2,556 distinct unordered pair products; the complete collision-hypergraph LP gives the integer upper bound 145.",
  "relevance_source": "recorded",
  "body": "Write \\(M(200)\\) for the largest size in the question. The present computation certifies\n\\[\n71\\le M(200)\\le145.\n\\]\nThe lower bound is attained by the displayed set in `ms200-claim-verified-71-set`. Its \\(\\binom{71+1}{2}=2556\\) unordered products, including all squares, are distinct.\n\nFor the upper bound, generate one forbidden hyperedge for every two distinct unordered pairs \\(\\{a,b\\}\\) and \\(\\{c,d\\}\\) with \\(ab=cd\\). After duplicate removal, the complete hypergraph has 20,111 edges: 248 triples and 19,863 four-sets. Every valid set is an independent set of this hypergraph. Relaxing its incidence vector to \\(0\\le x_i\\le1\\) and imposing\n\\[\n\\sum_{i\\in E}x_i\\le |E|-1\n\\]\nfor every collision edge \\(E\\) gives the exact rational optimum \\(291/2\\). An integral solution therefore has size at most 145.\n\nThis leaves a gap of 74. The exact finite value remains unresolved in this record. The upper calculation is a relaxation certificate, rather than a completed integer branch-and-bound proof.",
  "status": "reported",
  "evidence_grade": "reproduced",
  "scope": {
    "kind": "bounded",
    "statement": "multiplicative Sidon subsets of the positive integers 1 through 200, with squares included among the unordered pair products",
    "bounds": {
      "ground_set_minimum": {
        "min": 1,
        "max": 1
      },
      "ground_set_maximum": {
        "min": 200,
        "max": 200
      },
      "collision_hyperedges": {
        "min": 20111,
        "max": 20111
      }
    },
    "exhaustive": true
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "source_only",
    "kind": "claim",
    "citation": {
      "url": "https://arxiv.org/abs/1808.06182",
      "locator": "Self-contained exhaustive computation in ms200-artifact-construction-and-lp, executed 2026-07-25"
    },
    "missing": [
      "source",
      "command",
      "runtime",
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://arxiv.org/abs/1808.06182",
    "locator": "Self-contained exhaustive computation in ms200-artifact-construction-and-lp, executed 2026-07-25"
  },
  "models": [],
  "relations": [
    {
      "slug": "R541",
      "title": "A 71-element multiplicative Sidon set",
      "object_type": "claim",
      "relation": "supports",
      "direction": "incoming"
    },
    {
      "slug": "R538",
      "title": "Construction verifier and exact rational LP replay",
      "object_type": "artifact",
      "relation": "verifies",
      "direction": "incoming"
    },
    {
      "slug": "R539",
      "title": "The literature gives asymptotics; the finite exact search remains incomplete",
      "object_type": "attempt",
      "relation": "informs",
      "direction": "incoming"
    },
    {
      "slug": "multiplicative-sidon-200",
      "title": "multiplicative sidon 200",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}