{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R609",
  "content_hash": null,
  "slug": "ptm61-attempt-literature-and-remaining-range",
  "type": "attempt",
  "title": "The interval above 2^28 remains open in this entry",
  "summary": "Published methods explain the Zech-logarithm search, while the exact least pair and the rest of the requested interval remain unsettled here.",
  "relevance": "For Least trinomial multiple of a primitive degree-61 polynomial, record ptm61-attempt-literature-and-remaining-range (“The interval above 2^28 remains open in this entry”) documents a concrete method, search boundary, or failed route. The record states: Published methods explain the Zech-logarithm search, while the exact least pair and the rest of the requested interval remain unsettled here.",
  "relevance_source": "recorded",
  "body": "Didier and Laigle-Chapuy formulate low-weight multiple searches through discrete logarithms and time-memory tradeoffs. Peterlongo, Sala, and Tinnirello state the exact identity used here: if \\(\\alpha\\) is a root of a primitive polynomial, then\n\\[\nZ_\\alpha(i)=j\\quad\\Longleftrightarrow\\quad 1+\\alpha^i=\\alpha^j\n\\quad\\Longleftrightarrow\\quad p\\mid1+x^i+x^j.\n\\]\nTheir heuristic critical-degree estimate for weight three is on the scale of \\(2^{n/2}\\). At \\(n=61\\), the requested upper bound lies in that birthday range. The estimate is statistical and supplies no finite exclusion.\n\nMaitra, Gupta, and Venkateswarlu count sparse multiples of primitive polynomials and study their degree distribution. Giesbrecht, Roche, and Tilak place sparse multiples over finite fields in a broader algorithmic setting. Focused searches using the exact polynomial, its exponent set \\(\\{61,45,32,2,0\\}\\), degree-61 trinomial multiples, and Zech-logarithm tables found no source reporting the least pair for this polynomial.\n\nA full run of the same bucket layout at \\(2^{31}\\) would require about 25.8 GB before allocator and operating-system overhead. A lower-memory completion could partition the high residue bits, make several sequential passes over the LFSR orbit, and preserve the same exponent tags and per-partition hashes. This entry makes no claim for \\(268435456<b\\leq2147483648\\).",
  "status": "partial",
  "evidence_grade": "sourced",
  "scope": {
    "kind": "bounded",
    "statement": "the trinomial-multiple literature audit and the uncertified interval 268435456 < b <= 2147483648",
    "bounds": {
      "b": {
        "min": 268435457,
        "max": 2147483648
      }
    },
    "exhaustive": false
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "source_only",
    "kind": "attempt",
    "citation": {
      "url": "https://arxiv.org/abs/cs/0701069",
      "locator": "Frédéric Didier and Yann Laigle-Chapuy, Finding low-weight polynomial multiples using discrete logarithm, ISIT 2007, arXiv:cs/0701069; P. Peterlongo, M. Sala, and C. Tinnirello, A Discrete Logarithm-based Approach to Compute Low-Weight Multiples of Binary Polynomials, arXiv:1411.4024, section 2 and equation (6); Subhamoy Maitra, Kishan Chand Gupta, and Ayineedi Venkateswarlu, Theoretical Computer Science 341 (2005), 311-343, DOI 10.1016/j.tcs.2005.04.011; Mark Giesbrecht, Daniel Roche, and Hrushikesh Tilak, Computing sparse multiples of polynomials, arXiv:1009.3214"
    },
    "missing": [
      "source",
      "command",
      "runtime",
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://arxiv.org/abs/cs/0701069",
    "locator": "Frédéric Didier and Yann Laigle-Chapuy, Finding low-weight polynomial multiples using discrete logarithm, ISIT 2007, arXiv:cs/0701069; P. Peterlongo, M. Sala, and C. Tinnirello, A Discrete Logarithm-based Approach to Compute Low-Weight Multiples of Binary Polynomials, arXiv:1411.4024, section 2 and equation (6); Subhamoy Maitra, Kishan Chand Gupta, and Ayineedi Venkateswarlu, Theoretical Computer Science 341 (2005), 311-343, DOI 10.1016/j.tcs.2005.04.011; Mark Giesbrecht, Daniel Roche, and Hrushikesh Tilak, Computing sparse multiples of polynomials, arXiv:1009.3214"
  },
  "models": [],
  "relations": [
    {
      "slug": "R610",
      "title": "No trinomial multiple occurs through degree 2^28",
      "object_type": "claim",
      "relation": "informs",
      "direction": "outgoing"
    },
    {
      "slug": "R607",
      "title": "Exact 2^28 bucket exclusion certificate",
      "object_type": "artifact",
      "relation": "informs",
      "direction": "outgoing"
    },
    {
      "slug": "primitive-degree61-trinomial-multiple",
      "title": "primitive degree61 trinomial multiple",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}