{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R1774",
  "content_hash": null,
  "slug": "threshold-at-least-three-six-multiplicative-complexity-resolution-packet-quality-20260801",
  "type": "claim",
  "title": "Direct answer and proof for Multiplicative complexity of the six-bit threshold-at-least-three function",
  "summary": "The threshold-at-least-three function on six bits has multiplicative complexity exactly 4.",
  "relevance": "For Multiplicative complexity of the six-bit threshold-at-least-three function, this successor supplies the direct answer and complete human-readable proof required by the Resolution presentation.",
  "relevance_source": "recorded",
  "body": "Here is a direct upper-bound certificate. Work over GF(2), so every sum below is XOR. Define\n\\[\n\\begin{aligned}\na_0&=(1+x_3)x_4,\\\\\na_1&=(1+x_2+x_3+x_4)(x_3+x_4+x_5),\\\\\na_2&=(1+x_1+x_2+x_3+x_4+x_5)(1+x_1+x_6),\\\\\na_3&=(1+x_2+x_4+x_5+a_0+a_2)(1+x_3+x_4+x_5+a_1+a_2),\\\\\nT&=1+x_2+x_3+x_4+x_5+a_2+a_3.\n\\end{aligned}\n\\]\nEach displayed product is one two-input AND gate. Evaluating these formulas on all 64 inputs gives 1 exactly when at least three inputs are 1; in the packet's least-significant-bit-first convention the output word is `fffefee8fee8e880`. Hence four AND gates suffice.\n\nFor the lower bound, Çalık, Sönmez Turan, and Peralta exhaustively classified all 150,357 affine-equivalence classes of six-variable Boolean functions. Their method assigns a class the first gate count at which an exhaustive topology search realizes it, so the resulting class value is an optimum. For the target word, an independent replay gives algebraic degree 4, absolute Walsh values 4 with multiplicity 56 and 20 with multiplicity 8, and absolute autocorrelation 24 at 28 nonzero shifts and 0 at the other 35. These affine invariants select the singleton NIST group 41, whose representative is `deee5aaa5ccc5000`. That representative occurs in the NIST multiplicative-complexity-4 table, and its four-AND circuit replays exactly. Therefore the target cannot use three AND gates. Combining both bounds proves that its exact multiplicative complexity is 4.\n\nThe replay pins NIST Circuits commit `c553c0f5e7b8b93acc6f3c557de327f79cb904c3`. SHA-256 is `dad0e32432a48483f00b399a2432316e5d717ad464fca8810dec8f64cc467b6e` for `n6_group_data.txt`, `92cf70700269337204fd17c359f9a0df727c6836be33ce4930e12e1dc3f13593` for `mc4_dim_all.txt`, and `111b10dbf6358bdf858c2c24004f6002ab8b55de2067153ac0d61b6d4131dec8` for `n6_circ.txt`.",
  "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
      },
      "multiplicative_complexity": {
        "min": 4,
        "max": 4
      }
    },
    "exhaustive": true
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "source_only",
    "kind": "claim",
    "citation": {
      "url": "https://doi.org/10.1007/s12095-018-0297-2",
      "locator": "Algorithm 4 and the complete 150,357-class distribution; NIST Circuits commit c553c0f5e7b8b93acc6f3c557de327f79cb904c3, singleton group 41, mc4_dim_all.txt line 516, and the four-AND representative circuit"
    },
    "missing": [
      "source",
      "command",
      "runtime",
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://doi.org/10.1007/s12095-018-0297-2",
    "locator": "Algorithm 4 and the complete 150,357-class distribution; NIST Circuits commit c553c0f5e7b8b93acc6f3c557de327f79cb904c3, singleton group 41, mc4_dim_all.txt line 516, and the four-AND representative circuit"
  },
  "relations": [
    {
      "slug": "R784",
      "title": "The certified multiplicative-complexity interval is 3 to 5",
      "object_type": "claim",
      "relation": "supersedes",
      "direction": "outgoing"
    },
    {
      "slug": "threshold-at-least-three-six-multiplicative-complexity",
      "title": "threshold at least three six multiplicative complexity",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}