{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R583",
  "content_hash": null,
  "slug": "pirw600-attempt-literature-audit",
  "type": "attempt",
  "title": "The fixed-degree tap objective is a syndrome-decoding instance",
  "summary": "Classical shift-register synthesis minimizes register length, while this candidate asks for minimum weight in one affine binary coset.",
  "relevance": "For Sparsest degree-600 recurrence for a prime-indicator prefix, record pirw600-attempt-literature-audit (“The fixed-degree tap objective is a syndrome-decoding instance”) documents a concrete method, search boundary, or failed route. The record states: Classical shift-register synthesis minimizes register length, while this candidate asks for minimum weight in one affine binary coset.",
  "relevance_source": "recorded",
  "body": "Massey's shift-register synthesis paper gives an iterative solution for the shortest linear feedback shift register generating a prescribed finite sequence. That is the standard finite linear-complexity problem. Its objective is register length. Here the degree is fixed at 600 and the number of nonzero connection coefficients is minimized.\n\nAfter the two endpoint coefficients are fixed, the present equations ask for a minimum-weight vector with a prescribed binary syndrome. Berlekamp, McEliece, and van Tilborg proved the general decoding and code-weight problems NP-complete. Their result explains why Gaussian elimination settles feasibility and dimension while leaving the minimum-weight search hard. It gives no instance-specific lower bound.\n\nWinterhof surveys linear complexity for several number-theoretic binary sequences, including Legendre, two-prime, Thue-Morse, and prime-omega sequences. The survey gives useful neighboring theory but does not treat the characteristic function of ordinary primes used here. A targeted title, abstract, and citation search on 2026-07-25 found no published computation for this exact 1024-bit prime-indicator prefix, fixed degree, endpoint convention, or tap-weight objective. The novelty claim therefore remains unverified.",
  "status": "completed",
  "evidence_grade": "sourced",
  "scope": {
    "kind": "bounded",
    "statement": "published work on finite linear complexity, sparse connection polynomials, syndrome decoding, and number-theoretic binary sequences relevant to the stated prime-indicator prefix"
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "source_only",
    "kind": "attempt",
    "citation": {
      "url": "https://doi.org/10.1109/TIT.1969.1054260",
      "locator": "James L. Massey, Shift-register synthesis and BCH decoding, IEEE Transactions on Information Theory 15(1), 1969, pages 122-127; Elwyn R. Berlekamp, Robert J. McEliece, and Henk C. A. van Tilborg, On the inherent intractability of certain coding problems, IEEE Transactions on Information Theory 24(3), 1978, pages 384-386; Arne Winterhof, Pseudorandom binary sequences: quality measures and number-theoretic constructions, IEICE Transactions on Fundamentals E106.A(12), 2023, pages 1452-1460"
    },
    "missing": [
      "source",
      "command",
      "runtime",
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://doi.org/10.1109/TIT.1969.1054260",
    "locator": "James L. Massey, Shift-register synthesis and BCH decoding, IEEE Transactions on Information Theory 15(1), 1969, pages 122-127; Elwyn R. Berlekamp, Robert J. McEliece, and Henk C. A. van Tilborg, On the inherent intractability of certain coding problems, IEEE Transactions on Information Theory 24(3), 1978, pages 384-386; Arne Winterhof, Pseudorandom binary sequences: quality measures and number-theoretic constructions, IEICE Transactions on Fundamentals E106.A(12), 2023, pages 1452-1460"
  },
  "relations": [
    {
      "slug": "R584",
      "title": "The minimum tap weight lies between 8 and 186",
      "object_type": "claim",
      "relation": "contextualizes",
      "direction": "outgoing"
    },
    {
      "slug": "prime-indicator-recurrence-weight-600",
      "title": "prime indicator recurrence weight 600",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}