# P2602: Multiplicative complexity of the six-bit threshold-at-least-three function

- ID: `P2602`
- Reference: `threshold-at-least-three-six-multiplicative-complexity`
- Page: https://theoremdb.org/statements/P2602
- Record maturity: Reviewed problem with recorded work

## Problem

Over the Boolean basis with \(\mathsf{XOR}\) and constants free and two-input \(\mathsf{AND}\) gates counted, what is the minimum number of \(\mathsf{AND}\) gates needed to compute the six-input threshold function that equals \(1\) exactly at Hamming weights at least \(3\)?

### Remarks

- **Remark.** Circuits compute over F_2 with x^2=x on Boolean inputs.
- **Remark.** Multiplicative complexity counts AND gates and permits unrestricted fan-out and any number of XOR gates.

### What counts as a solution

- Give an XOR-AND circuit and a matching lower certificate establishing the minimum.

## The answer

The threshold-at-least-three function on six bits has multiplicative complexity exactly 4. [1](#reference-1) [3](#reference-3)

**Review status:** Reproduced.

**Lean verification:** not Lean-verified.

### Verification

Here is a direct upper-bound certificate. Work over GF(2), so every sum below is XOR. Define
\[
\begin{aligned}
a_0&=(1+x_3)x_4,\\
a_1&=(1+x_2+x_3+x_4)(x_3+x_4+x_5),\\
a_2&=(1+x_1+x_2+x_3+x_4+x_5)(1+x_1+x_6),\\
a_3&=(1+x_2+x_4+x_5+a_0+a_2)(1+x_3+x_4+x_5+a_1+a_2),\\
T&=1+x_2+x_3+x_4+x_5+a_2+a_3.
\end{aligned}
\]
Each 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.

For 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.

The 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`.

## Work

### Proof and evidence for the resolution

**Computation 1 (Direct answer and proof for Multiplicative complexity of the six-bit threshold-at-least-three function).** The threshold-at-least-three function on six bits has multiplicative complexity exactly 4.

Here is a direct upper-bound certificate. Work over GF(2), so every sum below is XOR. Define
\[
\begin{aligned}
a_0&=(1+x_3)x_4,\\
a_1&=(1+x_2+x_3+x_4)(x_3+x_4+x_5),\\
a_2&=(1+x_1+x_2+x_3+x_4+x_5)(1+x_1+x_6),\\
a_3&=(1+x_2+x_4+x_5+a_0+a_2)(1+x_3+x_4+x_5+a_1+a_2),\\
T&=1+x_2+x_3+x_4+x_5+a_2+a_3.
\end{aligned}
\]
Each 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.

For 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.

The 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`.

### Background and intake notes

Current rigorous bounds are 3 <= M <= 12 AND gates. The upper circuit updates e_j by e_j xor x_i e_(j-1) for j=2,3,4 as each input arrives and outputs e_3 xor e_4.

- Original intake status: Status unknown. Multiplicative complexities of small symmetric functions may be tabulated.
- The algebraic normal form is e_3 xor e_4. Sequential elementary-symmetric updates give a fully specified 12-AND circuit.
- A lower-bound search should canonicalize the affine span available before each AND gate. Algebraic degree four supplies the initial two-AND lower bound, while exhaustive span states can raise it.

- Recorded example: The updates use 1, 2, 3, 3, and 3 AND gates when x_2 through x_6 are added, for a total of 12.

### Supporting results

- **Computation 2** (reproduced): Two three-bit counters and a short carry calculation give a five-AND threshold circuit.
- **Proposition 1** (supported): The function has degree four, so the standard degree lower bound is three. [2](#reference-2)

### Prior approaches

- **Route 1** (supported): Primary sources give the degree bound, general symmetric-function circuits, and an exact classification of all affine classes on six variables. [1](#reference-1)

### Runnable artifacts

- **Artifact 1** (reproduced): The standard-library program checks every input, the truth-table word, and the degree-three plus degree-four algebraic normal form.

### Computational notes

- A complete 64-input truth-table check verified that the threshold-at-least-three function has algebraic normal form e_3 xor e_4. The displayed recurrence was symbolically expanded and reproduced that form using 12 AND gates. Any degree-four monomial needs at least three binary multiplications, giving the three-AND lower bound.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `threshold-at-least-three-six-multiplicative-complexity`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## Lean verification

An informal proof is recorded. A Lean formalization still needs to be attached.

[Prepare and check a Lean proof with TheoremDB Researcher](https://chatgpt.com/g/g-6a6c206c5acc8191b184bb55fb72c5b3-theoremdb-researcher?prompt=Prepare%20and%20submit%20a%20Lean%20proof%20for%20this%20TheoremDB%20result.%0A%0AExact%20problem_ref%3A%20threshold-at-least-three-six-multiplicative-complexity%0A%0AExact%20title%3A%20Multiplicative%20complexity%20of%20the%20six-bit%20threshold-at-least-three%20function%0A%0ACanonical%20packet%3A%20https%3A%2F%2Ftheoremdb.org%2Fstatements%2Fthreshold-at-least-three-six-multiplicative-complexity%2F%23lean-verification%0A%0AStart%20with%20prepareLeanProof%20for%20this%20exact%20problem_ref.%20Use%20its%20proof%20bundle%2C%20declaration%2C%20statement%2C%20and%20pinned%20world.%20If%20the%20target%20is%20not%20ready%2C%20follow%20the%20returned%20next%20step%20to%20record%20the%20exact%20formal%20target%2C%20then%20retry%20prepareLeanProof.%0A%0ACheck%20each%20private%20draft%20with%20checkLeanDraft%20and%20poll%20getLeanDraftRun%20until%20the%20check%20finishes.%20Repair%20any%20reported%20proof-line%20diagnostics%20before%20continuing.%0A%0ASubmit%20an%20accepted%20draft%20with%20submitLeanProof%2C%20then%20poll%20getLeanProofRun%20until%20verification%20finishes.%20Report%20whether%20the%20proof%20was%20published%20to%20the%20packet%20or%20needs%20the%20returned%20relation-review%20handoff.).

## References

1. <a id="reference-1"></a>Çağdaş Çalık, Meltem Sönmez Turan, and René Peralta, “The Multiplicative Complexity of 6-variable Boolean Functions,” Cryptography and Communications 11(1) (2019), 93-107. DOI 10.1007/s12095-018-0297-2. Algorithm 4, the class distribution, and the affine-signature method https://doi.org/10.1007/s12095-018-0297-2
   - Also cited at Çalık, Sönmez Turan, and Peralta, The Multiplicative Complexity of 6-variable Boolean Functions, especially Algorithm 4 and Table 4; data repository https://github.com/usnistgov/Circuits
   - journal_article; primary source; checked 2026-08-01
   - Source use: original_summary
   - Proves the exhaustive optimum classification used for the four-AND lower bound.
2. <a id="reference-2"></a>Joan Boyar and René Peralta, “Tight Bounds for the Multiplicative Complexity of Symmetric Functions,” Theoretical Computer Science 396(1-3) (2008), 223-246. DOI 10.1016/j.tcs.2008.01.030. degree lower bound and the symmetric-function multiplicative-complexity framework https://doi.org/10.1016/j.tcs.2008.01.030
   - Also cited at Boyar and Peralta, Tight bounds for the multiplicative complexity of symmetric functions, preliminary degree bound; the same bound is attributed there to Schnorr
   - journal_article; primary source; checked 2026-08-01
   - Source use: original_summary
   - For Multiplicative complexity of the six-bit threshold-at-least-three function, this source supplies the degree bound and symmetric-function framework used in the packet.
   - Source named by the research packet.
3. <a id="reference-3"></a>National Institute of Standards and Technology, Circuits, commit c553c0f5e7b8b93acc6f3c557de327f79cb904c3, January 31, 2024. data/n6_group_data.txt group 41; data/mc_dim/mc4_dim_all.txt line 516; data/circuits/n6_circ.txt representative deee5aaa5ccc5000 https://github.com/usnistgov/Circuits/tree/c553c0f5e7b8b93acc6f3c557de327f79cb904c3
   - dataset; primary source; Git commit c553c0f5e7b8b93acc6f3c557de327f79cb904c3; checked 2026-08-01
   - Source use: data_used
   - Reused material: data/n6_group_data.txt group 41; data/mc_dim/mc4_dim_all.txt line 516; data/circuits/n6_circ.txt representative deee5aaa5ccc5000
   - Reuse basis: fair_use_reviewed; rights holder: National Institute of Standards and Technology; checked 2026-08-01; by Philip Weiss, TheoremDB staff
   - Required attribution: National Institute of Standards and Technology, Circuits, commit c553c0f5e7b8b93acc6f3c557de327f79cb904c3, January 31, 2024.
   - Supplies the pinned affine-class record and AND-optimal circuit replay.