{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R785",
  "content_hash": null,
  "slug": "threshold-six-three-claim-degree-lower-bound",
  "type": "claim",
  "title": "Algebraic degree forces at least three AND gates",
  "summary": "The function has degree four, so the standard degree lower bound is three.",
  "relevance": "For Multiplicative complexity of the six-bit threshold-at-least-three function, record threshold-six-three-claim-degree-lower-bound (“Algebraic degree forces at least three AND gates”) records a bound, answer, status fact, or structural consequence. The record states: The function has degree four, so the standard degree lower bound is three.",
  "relevance_source": "recorded",
  "body": "A Möbius transform of the 64-row truth table gives 35 nonzero algebraic-normal-form coefficients: all 20 squarefree monomials of degree 3 and all 15 squarefree monomials of degree 4. Thus\n\\[\nT=\\Sigma^6_3\\oplus\\Sigma^6_4\n\\]\nhas degree 4. The standard degree bound for multiplicative complexity states \\(C_\\wedge(f)\\geq\\deg(f)-1\\). Applying it here gives \\(C_\\wedge(T)\\geq3\\). The executable artifact independently reconstructs the algebraic normal form before checking this inference.",
  "status": "established",
  "evidence_grade": "sourced",
  "scope": {
    "kind": "bounded",
    "statement": "the six-input threshold-at-least-three function over the XOR, AND, and constant-one basis",
    "bounds": {
      "algebraic_degree": {
        "min": 4,
        "max": 4
      },
      "and_gates": {
        "min": 3,
        "max": 3
      }
    },
    "exhaustive": true
  },
  "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, preliminary degree bound; the same bound is attributed there to Schnorr"
    },
    "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, preliminary degree bound; the same bound is attributed there to Schnorr"
  },
  "relations": [
    {
      "slug": "R784",
      "title": "The certified multiplicative-complexity interval is 3 to 5",
      "object_type": "claim",
      "relation": "supports",
      "direction": "outgoing"
    },
    {
      "slug": "R782",
      "title": "Exhaustive verifier for the five-AND circuit",
      "object_type": "artifact",
      "relation": "supports",
      "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"
    }
  ]
}