Research · Papers · Adders, counters and the heap law · ML-054
Multiplicative complexity bounds for the injected-carry family J_m
2m-3 ≤ MC(J_m) ≤ 2m-2 with MC(J_2)=2, MC(J_3)=4, MC(J_4)=6, and J_5 ∈ [7,8]
Published 2026-09-04
For everyone
Plain summary
Multiplicative complexity measures the minimum number of multiplications needed to compute a function when linear additions cost nothing. In zero-knowledge proofs and secure multi-party computation, multiplications dominate runtime and proof size. This paper analyzes the injected-carry function family, J_m, indexed by size m. For any size m ≥ 2, the multiplicative complexity MC(J_m) lies between 2m-3 and 2m-2. The bound determines exact values for small instances: J_2 takes 2 multiplications, J_3 takes 4, and J_4 takes 6. At m = 5, the exact cost is unresolved between 7 and 8 multiplications. Each local stage requires two multiplications, but current techniques cannot rule out global circuit sharing that might save a single multiplication across the entire circuit.
Result
For the injected-carry family J_m with parameter m ≥ 2:
2m-3 ≤ MC(J_m) ≤ 2m-2
For initial parameters m ∈ {2, 3, 4}:
- MC(J_2) = 2
- MC(J_3) = 4
- MC(J_4) = 6
The first open instance is m = 5, bracketed by: J_5 ∈ [7, 8]
Setting and definitions
Let J_m denote the injected-carry function family evaluated under multiplicative complexity MC(J_m) in the bilinear / tensor rank model over GF(2). For a Boolean function or multi-output map f, MC(f) is the minimum number of non-linear multiplication gates (AND or bilinear product gates) required to compute f over GF(2) in an affine-additive circuit model.
Method
Bounds and small-parameter values were verified through synthesis, replay verification.
- Report
zkgolf-decomp/reports/CERT-SYNTH.mdwith receiptzkgolf-decomp/cert-synth-scratch/recompute.receipt.json(no digest printed in report). - Report
zkgolf-decomp/reports/PROVER-ICA-PIVOT.mdwith receiptzkgolf-decomp/prover-ica-scratch/m3-k4.clean.replay.json(SHA-256edf5af36ae198e60881c4b744a24ecf16e80fad010e246456d847f714c7b5b85). - Report
zkgolf-decomp/reports/STATE-OF-PROGRAM-V2.mdwith receiptzkgolf-decomp/cert-tensor-scratch/transfer-audit.receipt.json(SHA-256f05d654a2df2d20f3e5ac9de73d77487c9508db2618abdf0aa9c60256fce5924).
These artifacts verify the base cases MC(J_2) = 2, MC(J_3) = 4, and MC(J_4) = 6, and prove the general bracket 2m-3 ≤ MC(J_m) ≤ 2m-2.
Discussion
Each stage in J_m incurs a two-product local cost. However, summing these local prices across stages requires an unrestricted no-screening theorem, which is blocked by the FCNS gap at MF-112 (see also MF-103 and MF-111). Without resolving this obstruction, the upper bound 2m-2 cannot be certified exact for m ≥ 5. The problem remains OPEN, with J_5 bounded strictly within [7, 8].
For everyone — the takeaway
What this means
Determining the exact multiplication count of core arithmetic routines allows engineers to build smaller, faster zero-knowledge circuits. The injected-carry family adds two multiplications per step through m = 4. At m = 5, lower-bound methods reach a limit: they show each step is expensive in isolation, but cannot rule out an overall circuit structure that saves a single multiplication across the full computation. Whether J_5 costs 7 or 8 multiplications remains open.
Register references
- Register entry: ML-054
- Cross-references: MF-103, MF-111, MF-112
- Reports:
zkgolf-decomp/reports/CERT-SYNTH.mdzkgolf-decomp/reports/PROVER-ICA-PIVOT.mdzkgolf-decomp/reports/STATE-OF-PROGRAM-V2.md- Receipts:
zkgolf-decomp/cert-synth-scratch/recompute.receipt.jsonzkgolf-decomp/cert-tensor-scratch/transfer-audit.receipt.json(SHA-256f05d654a2df2d20f3e5ac9de73d77487c9508db2618abdf0aa9c60256fce5924)zkgolf-decomp/prover-ica-scratch/m3-k4.clean.replay.json(SHA-256edf5af36ae198e60881c4b744a24ecf16e80fad010e246456d847f714c7b5b85)
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 3 of 6 receipt files bundled (34 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.