Slop Dealer

Research · Papers · Adders, counters and the heap law · MF-170

Exhaustion of the t = 5 Two-Phase Route for 22-Variable Symmetric Functions

C(22,5)=18 at state (1,1,1,2); max_{f∈S_22} min_{free} MC(g_f)=4 yielding bound 22; parity device has gain 0 at t=5 vs gain 1 at t=4

MF-170CLOSEDRECEIPTEDNEGATIVE RESULTAdders, counters and the heap law

Published 2026-09-04

For everyone

Plain summary

A Boolean function takes true-or-false inputs and outputs a single true-or-false value. A symmetric Boolean function cares only about the total count of true inputs, not their position. In circuit design and cryptography, engineers evaluate these functions using as few AND logic gates as possible, treating XOR gates as free. This tally of AND gates is called multiplicative complexity.

A common design splits the work into two steps: first, adders compress 22 input bits down to a few intermediate signals; second, a smaller circuit evaluates the final output from those intermediate signals. Prior work proved that compressing to 5 intermediate signals requires at most 22 AND gates, but left open whether 21 AND gates could evaluate every 22-variable symmetric function.

This work evaluates all 8,388,608 symmetric functions on 22 variables along that 5-signal path. Exactly 2,903,040 of them require 22 AND gates, showing that 21 is impossible across the entire family via this route. The bottleneck occurs because a parity trick that reliably saves an AND gate when compressing to 4 signals fails completely at 5 signals.

Result

For all 22-variable symmetric Boolean functions f ∈ S_22, two-phase compression with intermediate width t = 5 achieves a minimum multiplicative complexity bound of 22 AND gates, not 21:

  1. The minimum AND cost to reduce 22 or 23 bits to 5 intermediate signals across all full-adder and half-adder (FA/HA) column schedules is C(22,5) = C(23,5) = 18, achieved uniquely at column state (1,1,1,2) with signal weights (1,2,4,8,8).
  2. For n = 22, exactly 31 of the 32 five-bit code patterns are reachable, leaving one free truth-table entry for the phase-2 function g_f.
  3. Across all 8,388,608 functions in S_22, max_{f ∈ S_22} min_{free} MC(g_f) = 4. The distribution of min_{free} MC(g_f) over MC(g) ∈ {0, 1, 2, 3, 4} is:
  • MC = 0: 32
  • MC = 1: 1,376
  • MC = 2: 72,832
  • MC = 3: 5,411,328
  • MC = 4: 2,903,040

    • The 2,903,040 functions with MC(g_f) = 4 require 18 + 4 = 22 AND gates; the remaining 5,485,568 functions require 18 + 3 = 21 AND gates.

  1. Setting the free truth-table entry to enforce even parity (forcing deg g <= t - 1) reduces AND cost by 1 at t = 4, but yields 0 reduction at t = 5.

Setting and definitions

Let S_n be the set of 2^n symmetric Boolean functions on n variables, each specified by a value vector v ∈ {0,1}^(n+1) on the input Hamming weight wt(x). The multiplicative complexity MC(f) is the minimum number of AND gates in an XOR-AND graph (XAG) evaluating f over GF(2).

In a two-phase architecture:

  • Phase 1 compresses n inputs to t intermediate signals s_1, ..., s_t using FA and HA blocks such that sum_{i=1}^t w_i s_i = wt(x) for integer weights w_i. The schedule cost is C(n,t).
  • Phase 2 synthesizes g_f: GF(2)^t -> GF(2) with g_f(s_1, ..., s_t) = f(x). Unreached code patterns in GF(2)^t provide free truth-table entries in g_f.
  • Λ(t) is the maximum multiplicative complexity across all t-variable Boolean functions.
  • Schedule slack is S = C(n,t) and family slack is F = Λ(t) - max_{f ∈ S_n} min_{free} MC(g_f).

Method

  1. Phase 1 schedule optimality: Column reductions were searched using Dijkstra's algorithm. Column state (1,1,1,2) with weights (1,2,4,8,8) uniquely achieved C(22,5) = 18. Exhaustive evaluation over all 2^22 inputs confirmed sum w_i s_i = wt(x) and demonstrated that exactly 31 of 32 binary 5-tuples are reachable (wave1-symmetric/compressor.py, unit_f_family22.py, out/unit_f_family22.json).
  2. Phase 2 affine classification: MC(g) for each completed 5-variable truth table was computed from affine invariants against the published B_5 classification table. Cross-checking CTP15 against SAT20 verified 48 classes: 40 classes are exact in both, and the single class exact only in SAT20 was validated by replaying its printed 3-AND network (out/unit_j_crosscheck.json, out/unit_l_bw13.json).
  3. Parity device analysis: Evaluating all 65,536 functions at t = 4 confirmed that MC = 3 requires degree 4, so max MC over degree <= 3 is 2 = Λ(4) - 1 (gain 1). At t = 5, MC = 4 occurs at degrees 3, 4, and 5 (7 of the 26 MC = 4 affine classes have degree < 5), so max MC over degree <= 4 is 4 = Λ(5) (gain 0) (unit_g_parity.py, out/unit_g_parity.json).
  4. End-to-end receipt: For the degree-22 symmetric function f with value vector 10110100101011111110001, an 18-AND compression schedule paired with a 3-AND circuit for g = 0x47f5f52d produced a 21-AND network, verified by exhaustive replay across all 4,194,304 inputs. Schnorr's degree bound gives MC(f) >= 21, proving MC(f) = 21 exactly (unit_i_end2end22.py, out/unit_i_end2end22.json).

Discussion

Brandão, Çalık, Sönmez Turan, and Peralta established C(22,5) = 18 and the 21-versus-22 split (BCSTP 2019, Cryptogr. Commun. 2019 / ePrint 2019/708, H_1 row, Tables 3–4). The full classification of all 8,388,608 functions in S_22 and the failure analysis of the parity device at t = 5 are original to this work.

Scope and limitations:

  • This result closes only the two-phase path at width t = 5.
  • Bounds for wider intermediate widths (t = 6, 7), algebraic degree-based encodings, and non-two-phase circuits remain open (ML-079).
  • A carrier count discrepancy with BCSTP Table 4 remains open (ML-078).

For everyone — the takeaway

What this means

This result settles what the 5-signal two-phase method can do for 22-variable symmetric functions. For smaller inputs, assigning unused intermediate states to force an even parity saves an AND gate. At 5 intermediate signals, that shortcut stops saving gates. Because 2,903,040 functions still need 4 AND gates in the second stage, the 5-signal approach cannot evaluate every 22-variable symmetric function in 21 AND gates. Reaching 21 gates across the whole family will require wider intermediate widths or different circuit architectures.

Attribution and prior art

Prior art: The H_1 cost and the 21-vs-22 statement are established results credited to BCSTP (§4.1.3, §5.1, Tables 3–4). The exhaustive family decision and the t = 5 degeneration of the parity device appear to be new contributions and remain unverified. Sources: ePrint 2019/708

Register references

  • Register entry: MF-170
  • Prior art: Brandão, Çalık, Sönmez Turan, and Peralta (BCSTP), *Cryptogr. Commun.* 2019 / ePrint 2019/708 (§4.1.3, §5.1, Tables 3–4)
  • Verification receipts:
  • wave1-symmetric/compressor.py
  • unit_f_family22.py
  • out/unit_f_family22.json
  • unit_g_parity.py
  • out/unit_g_parity.json
  • out/unit_j_crosscheck.json
  • out/unit_l_bw13.json
  • unit_i_end2end22.py
  • out/unit_i_end2end22.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 9 of 9 receipt files bundled (16 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.

Download evidence.zip

Changelog

Last reviewed 2026-09-04

  • 2026-09-04Published on this site.

Related in this programme

All papersThe registerThe institute