Research · Papers · Symmetry, state encodings and search gauges · ML-079
Open Status of the NIST 21-vs-22 Question for Degree-22 Symmetric Functions
NIST 21-vs-22 question for deg-22 symmetric functions remains open; t = 5 two-phase route yields 22, while t = 6, 7 remain open.
Published 2026-09-04
For everyone
Plain summary
Symmetric Boolean functions produce outputs based only on how many inputs are true, not their positions. A standing question from NIST asks whether certain symmetric functions of algebraic degree 22 can be computed with 21 multiplication operations (AND gates), or if they strictly need 22.
Recent work showed that a specific five-step construction cannot beat 22 multiplications across 2.9 million candidate functions, because a parity-based shortcut runs out of power at five steps. This does not settle the wider question. Six- or seven-step schedules, degree-based algebraic encodings, and circuits that skip the two-phase layout entirely are still unexamined. Determining whether 21 multiplications suffice remains open, blocked by broader unsolved problems in circuit complexity.
Result
The NIST 21-vs-22 conjecture for degree-22 symmetric Boolean functions remains open. MF-170 closed only the specific t = 5 two-phase construction route, which yields multiplicative complexity 22 across all 2.9M candidate carriers.
Whether any of the 2.9M carriers admits a 21-AND circuit is unsettled. Three structural spaces remain unconstrained:
- Heap schedules for t = 6 and t = 7, with schedule costs of 17 and 16.
- Degree-based (non-weight) encodings.
- General circuit topologies outside two-phase decomposition.
Setting and definitions
Let f be an n-variable symmetric Boolean function depending only on input Hamming weight. The multiplicative complexity MC(f) is the minimum number of AND gates (multiplications over GF(2)) needed to evaluate f over the gate set {AND, XOR, NOT}.
In a two-phase synthesis architecture parameterized by t:
- Phase 1 builds an intermediate weight representation or base heap at schedule cost C(t), providing free-entry parity access.
- Phase 2 synthesizes the remaining target logic on the resulting sub-functions.
- The carrier set contains 2.9M functions of degree 22.
- Λ(k) denotes the exact multiplicative complexity lookup table over k-variable Boolean functions, with maximum complexity bounded by B_k.
Method
Auditing the proof bounds of MF-170 against general upper and lower bound techniques establishes the open status:
- Exhaustive analysis of the t = 5 two-phase route showed that the free-entry parity device terminates at t = 5, fixing the cost at 22 multiplications across all 2.9M carriers.
- Evaluating higher parameters yields schedule costs of 17 for t = 6 and 16 for t = 7, which provide additional free entries.
- Phase-2 evaluations for t = 6 require exact bounds over 6-variable Boolean functions (the Λ(6) exact-table gap). Because the maximum multiplicative complexity over 6 variables is the open B_6 problem, table lookups cannot evaluate or rule out t = 6.
- Verification artifacts and structural cost tables are in
wave1-symmetric/REPORT.md§4 andout/unit_g_parity.json.
Discussion
Eliminating the t = 5 two-phase route does not establish MC(f) = 22 for degree-22 symmetric functions.
Refuting the NIST 22 conjecture requires finding a valid 21-AND realization for at least one of the 2.9M carriers; none is known. Proving the conjecture requires establishing MC(f) ≥ 22 across all unconstrained routes: alternative two-phase parameterizations (t = 6, 7), non-weight algebraic degree encodings, and single-phase or non-standard topologies.
The main obstacle to exhaustive classification at t = 6 is the open B_6 question—the exact maximum multiplicative complexity of 6-variable functions. Until B_6 or the alternate search spaces are solved, the NIST 21-vs-22 question remains open.
For everyone — the takeaway
What this means
Ruling out one specific synthesis technique does not prove a problem cannot be solved faster another way. While five-step two-phase designs need 22 multiplication gates for these degree-22 symmetric functions, other strategies might still reach 21. Finding out whether 21 multiplications suffice depends directly on classic open problems in circuit complexity, such as finding the exact maximum multiplication cost for arbitrary six-variable Boolean functions.
Register references
- Register entry: ML-079
- Related register entry: MF-170
- Artifacts:
wave1-symmetric/REPORT.md§4,out/unit_g_parity.json
Every artifact named above is bundled in, or hashed by, this paper's evidence pack below.
Evidence pack
Everything needed to check this entry against its receipts: the register text, a manifest with a SHA-256 hash for every named receipt, and 2 of 2 receipt files bundled (10 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.
Changelog
Last reviewed 2026-09-04
- 2026-09-04Published on this site.