{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R784",
  "content_hash": null,
  "slug": "threshold-six-three-claim-certified-three-to-five",
  "type": "claim",
  "title": "The certified multiplicative-complexity interval is 3 to 5",
  "summary": "The degree bound gives three AND gates, and a new five-AND circuit improves the candidate's twelve-gate construction.",
  "relevance": "For Multiplicative complexity of the six-bit threshold-at-least-three function, record threshold-six-three-claim-certified-three-to-five (“The certified multiplicative-complexity interval is 3 to 5”) records a bound, answer, status fact, or structural consequence. The record states: The degree bound gives three AND gates, and a new five-AND circuit improves the candidate's twelve-gate construction.",
  "relevance_source": "recorded",
  "body": "Let \\(T(x_1,\\ldots,x_6)\\) equal 1 when at least three inputs equal 1. Its algebraic normal form is\n\\[\nT=\\Sigma^6_3\\oplus\\Sigma^6_4,\n\\]\nso \\(T\\) has algebraic degree 4. Schnorr's degree bound, as stated and applied in the symmetric-function literature, gives \\(C_\\wedge(T)\\geq4-1=3\\).\n\nThe straight-line program in the companion artifact computes \\(T\\) with five two-input AND gates. It was checked on all 64 inputs and has truth-table word `fffefee8fee8e880` when row \\(x\\) occupies bit \\(x\\). Therefore\n\\[\n3\\leq C_\\wedge(T)\\leq5.\n\\]\nThe exact value is one of 3, 4, and 5. The published classification of all six-variable Boolean functions determines it in principle, while this fixture stops at the independently replayed interval.",
  "status": "established",
  "evidence_grade": "reproduced",
  "scope": {
    "kind": "bounded",
    "statement": "the multiplicative complexity of the six-variable Boolean function that is one exactly at Hamming weights at least three",
    "bounds": {
      "input_variables": {
        "min": 6,
        "max": 6
      },
      "certified_and_lower_bound": {
        "min": 3,
        "max": 3
      },
      "certified_and_upper_bound": {
        "min": 5,
        "max": 5
      }
    },
    "exhaustive": false
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "source_only",
    "kind": "claim",
    "citation": {
      "url": "https://doi.org/10.1016/j.tcs.2008.01.030",
      "locator": "Boyar and Peralta, Tight bounds for the multiplicative complexity of symmetric functions, degree bound and threshold-function discussion; upper endpoint reproduced by threshold-six-three-artifact-five-and-verifier"
    },
    "missing": [
      "source",
      "command",
      "runtime",
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://doi.org/10.1016/j.tcs.2008.01.030",
    "locator": "Boyar and Peralta, Tight bounds for the multiplicative complexity of symmetric functions, degree bound and threshold-function discussion; upper endpoint reproduced by threshold-six-three-artifact-five-and-verifier"
  },
  "relations": [
    {
      "slug": "R786",
      "title": "Five AND gates suffice",
      "object_type": "claim",
      "relation": "supports",
      "direction": "incoming"
    },
    {
      "slug": "R785",
      "title": "Algebraic degree forces at least three AND gates",
      "object_type": "claim",
      "relation": "supports",
      "direction": "incoming"
    },
    {
      "slug": "R783",
      "title": "The six-variable classification is the next exactness check",
      "object_type": "attempt",
      "relation": "informs",
      "direction": "incoming"
    },
    {
      "slug": "R1774",
      "title": "Direct answer and proof for Multiplicative complexity of the six-bit threshold-at-least-three function",
      "object_type": "claim",
      "relation": "supersedes",
      "direction": "incoming"
    },
    {
      "slug": "threshold-at-least-three-six-multiplicative-complexity",
      "title": "threshold at least three six multiplicative complexity",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}