Research · Papers · Adders, counters and the heap law · MF-111
Bounds on the multiplicative complexity of the injected-carry family
2m-3 ≤ MC(J_m) ≤ 2m-2 for m ≥ 2; MC(J_2)=2, MC(J_3)=4, MC(J_4)=6, J_5 ∈ [7, 8]
Published 2026-09-04
For everyone
Plain summary
This work determines how many multiplication steps are needed to compute the injected-carry family of Boolean functions, written J_m, where m is the input size. Multiplicative complexity counts the minimum number of logical AND gates (multiplications over GF(2)) needed in a circuit when XOR gates are free.
For every input size m ≥ 2, the exact multiplicative complexity MC(J_m) falls within a two-value window: either 2m-3 or 2m-2. For the smallest three sizes (m = 2, 3, and 4), the exact values are resolved as 2, 4, and 6. The smallest undecided case is J_5, whose complexity is either 7 or 8.
Result
For all m ≥ 2, the multiplicative complexity MC(J_m) of the injected-carry family satisfies:
2m-3 ≤ MC(J_m) ≤ 2m-2
The exact values for the first three non-trivial instances are:
- MC(J_2) = 2
- MC(J_3) = 4
- MC(J_4) = 6
The first unresolved case is J_5, which satisfies J_5 ∈ [7, 8].
Setting and definitions
Let J_m denote the m-bit injected-carry family evaluated over GF(2). Multiplicative complexity MC(f) is the minimum number of bilinear multiplication (AND) operations required to synthesize f in a straight-line program over GF(2) with free affine XOR operations. Under the bilinear and tensor rank cost model, the identity at MF-103 provides the structural reduction parameterizing the family across general m.
Method
The general bounds 2m-3 ≤ MC(J_m) ≤ 2m-2 are established by formal reduction via MF-103. The base instances m = 2, 3, and 4 are established by separate synthesis certifications and replay certificates.
Evidence tiers:
- Tier P for 2m-3 ≤ MC(J_m) ≤ 2m-2.
- Tier FC and FR for m = 2, 3, 4.
Verification reports:
- zkgolf-decomp/reports/CERT-SYNTH.md
- zkgolf-decomp/reports/PROVER-ICA-PIVOT.md
- zkgolf-decomp/reports/STATE-OF-PROGRAM-V2.md
Receipts:
- zkgolf-decomp/cert-synth-scratch/recompute.receipt.json (no receipt digest recorded in report)
- zkgolf-decomp/cert-tensor-scratch/transfer-audit.receipt.json (SHA-256 f05d654a2df2d20f3e5ac9de73d77487c9508db2618abdf0aa9c60256fce5924)
- zkgolf-decomp/prover-ica-scratch/m3-k4.clean.replay.json (SHA-256 edf5af36ae198e60881c4b744a24ecf16e80fad010e246456d847f714c7b5b85)
Discussion
The register status is PROVED.
The bracket leaves an uncertainty of at most one multiplication gate for all m ≥ 5. The upper bound 2m-2 is sharp for m = 2, 3, and 4 (yielding 2, 4, and 6), whereas for m ≥ 5, deciding whether MC(J_m) equals 2m-3 or 2m-2 remains open. The register records no prior-art position.
For everyone — the takeaway
What this means
In zero-knowledge cryptography and secure computation, non-linear multiplication gates account for almost all proof-generation time and overhead, while additions and XORs are essentially free. Knowing exact multiplication counts for standard components like injected-carry functions sets hard limits on circuit efficiency. This result pins down the cost of the entire injected-carry family to at most two values for any size, and resolves the smallest cases completely.
Register references
- Entry: MF-111
- Related identity: MF-103
- Reports:
- zkgolf-decomp/reports/CERT-SYNTH.md
- zkgolf-decomp/reports/PROVER-ICA-PIVOT.md
- zkgolf-decomp/reports/STATE-OF-PROGRAM-V2.md
- Receipts:
- zkgolf-decomp/cert-synth-scratch/recompute.receipt.json
- zkgolf-decomp/cert-tensor-scratch/transfer-audit.receipt.json (SHA-256 f05d654a2df2d20f3e5ac9de73d77487c9508db2618abdf0aa9c60256fce5924)
- zkgolf-decomp/prover-ica-scratch/m3-k4.clean.replay.json (SHA-256 edf5af36ae198e60881c4b744a24ecf16e80fad010e246456d847f714c7b5b85)
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.