Research · Papers · Cipher S-boxes, χ, and quantum gate counts · MF-174
Refutation of five candidate multiplicative complexity lower-bound conjectures
Five refutations: MC ≱ dim V + μ₁ + μ₂ - 2, plane parity bound fails, Lemma X fails at (4,3), linear catalysis fails, MC(χ,χ²,χ³) ≠ 3n
Published 2026-09-04
For everyone
Plain summary
Multiplicative complexity measures the minimum number of nonlinear AND gates needed to evaluate a system of Boolean functions using only AND and XOR operations. Because computing exact multiplicative complexity is notoriously difficult, researchers often propose general formulas, lower bounds, or structural lemmas to simplify the analysis.
This record collects explicit counterexamples that disprove five distinct conjectures and proposed lemmas. First, it refutes a formula predicting that the joint complexity of two classes is bounded below by the sum of their individual costs minus two. Second, it disproves a general-model plane parity counting bound. Third, it breaks a proposed gate-local growth lemma (Lemma X) that attempted to bound step-by-step quadratic space generation. Fourth, it refutes a linear catalysis hypothesis for bridge-slack collapse, showing that internal signals provide zero linear surplus for symmetric functions. Fifth, it disproves a joint power law predicting that the complexity of the first three powers of the chi mapping equals three times the input length. These explicit witnesses prevent future proofs from relying on false structural assumptions.
Result
Five candidate lower-bound inequalities, structural induction steps, and complexity attributions are false:
- Two-class cost sum: The inequality MC >= dim V + mu_1 + mu_2 - 2 does not hold in general. There exist 16 register-backed counterexamples; the minimal witness is GF(4) multiplication, which evaluates to a true multiplicative complexity of 3 against the predicted bound of 4. The correct second-order term is m_2(V), not the sum of two individual class costs.
- General-model plane parity bound: The general-model plane parity counting bound fails. For n = 3, with gates g1 = x0 x1 and g2 = g1 x2, the space W = span{x0x1, x0x1x2} achieves cost 2 against the counting bound 3. In a chained circuit, a class cost is bounded by its largest gate index rather than its support cardinality.
- Gate-local growth (Lemma X): The structural assertion that whenever Quad(S_t) = Quad(S_{t-1}) + <w>, there exists some v ∈ Quad(S_{t-1}) satisfying mc(w + v) <= 1, fails. A counterexample occurs at n = 4, k = 3 (1 occurrence in 36,038 growth events) with witness gates [34952, 28800, 6720] and w = x0x3 + x1x2, where mc(w) = mc(w + x0x1) = 2.
- Linear catalysis for bridge-slack collapse: The CS-08 attribution of m = 4 bridge-slack collapse to free lookup from heap-internal signals fails in its linear interpretation. For all m = 2..10, the affine span of all heap signals contains exactly as many symmetric functions as the span of the weight bits alone (surplus 0). The collapse at n = 4 is settled by the schedule alone (C(4,3) = 1 plus Λ(3) = 2), operating via BCSTP's H_FA redundant weight encoding.
- Three-power joint law: The joint complexity equality MC(chi, chi^2, chi^3) = 3n fails at n = 4 and n = 5.
Setting and definitions
Let MC(f) denote the multiplicative complexity of a Boolean map or function over GF(2). For a linear subspace of quadratic forms V, dim V is its vector space dimension, and mu_i denote individual class costs, with m_2(V) representing the true second-order structural cost.
For a sequence of gates S_t in an XAG, Quad(S_t) denotes the space of quadratic forms spanned by the outputs and products of affine combinations available at step t. The quantity mc(w) denotes the multiplicative complexity of an isolated form w.
The map chi denotes the standard non-linear permutation mapping on n bits, with powers chi^2 and chi^3 defined under composition or joint power evaluations over GF(2)^n.
Method
Each refutation was established by generating explicit counterexample certificates, exhaustive space replays.
- The failure of MC >= dim V + mu_1 + mu_2 - 2 and the general-model plane parity bound were extracted from explicit witness exceedances recorded in
geometry/sweep_results.json(under keyplane_refuter). - Lemma X was tested across 36,038 quadratic space growth events using
wave1-ms3/lemx.py, with logs and verification replays recorded inPROGRESS.log(lines 86–87, 04:09:31Z replay). - The linear catalysis hypothesis was evaluated by checking the affine closure of heap-internal signals across symmetric function spaces for m = 2..10, recorded in
wave1-symmetric/out/unit_c_catalysis.jsonandout/unit_d_obstruction.json. - The joint power law MC(chi, chi^2, chi^3) = 3n was evaluated at n = 4 and n = 5 via joint synthesis sweeps recorded in
chi/out_s02_powers_joint.json.
All five results satisfy the fully checked (FC) and fully reproduced (FR) evidence tiers.
Discussion
These refutations establish structural boundaries across several lower-bound programs:
- The failure of the plane parity counting bound explains why the Mirwald–Schnorr <= 2-form import boundary is strictly load-bearing and why Theorem A at j >= 2 cannot currently be used. This failure matches the open-problem formulation given by Boyar and Find.
- The failure of Lemma X at n = 4, k = 3 demonstrates that quadratic space complexity does not grow via step-by-step local increments of cost at most 1. Had Lemma X held, induction would have established MC = qMC across every quadratic space for all n, closing the 3-form gap. Any valid inductive proof must account for non-local amortization where a later gate pays for an earlier over-jump.
- Regarding catalysis, the refutation applies strictly to the linear reading (affine span of internal signals yielding symmetric functions). The productive reading, where heap-internal signals are reused nonlinearly as AND inputs in phase 2, remains untested and is not refuted.
- The joint power law MC(chi, chi^2, chi^3) = 3n cannot be extended to arbitrary n due to failures at n = 4 and n = 5.
For everyone — the takeaway
What this means
Lower bounds in circuit complexity are hard to prove, and natural-looking assumptions often fail in subtle ways. By constructing explicit counterexamples to these five candidate bounds and lemmas, this entry closes off several flawed proof strategies.
Specifically, it demonstrates that circuit optimization can exploit gate chaining, global amortization, and redundant encodings to beat naive counting arguments and local induction steps. Researchers cannot assume that gate costs add together cleanly or that intermediate circuit states evolve one simple step at a time.
Attribution and prior art
Prior art: This result is supported by prior work, including the Mirwald–Schnorr <= 2-form import boundary, Boyar–Find’s open-problem statement, and the BCSTP redundant weight encoding.
Register references
- Register entry: MF-174 (related entries: MF-140, MF-156)
- Artifacts:
geometry/sweep_results.json(fieldexceedances, keyplane_refuter)wave1-ms3/lemx.pyPROGRESS.log86–87 and 04:09:31Z replaywave1-symmetric/out/unit_c_catalysis.jsonout/unit_d_obstruction.jsonchi/out_s02_powers_joint.json- Prior art:
- Mirwald–Schnorr <= 2-form import boundary
- Boyar–Find open-problem statement
- BCSTP H_FA redundant weight encoding
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 6 of 6 receipt files bundled (9 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.