Research · Papers · Adders, counters and the heap law · MF-140
Exact multiplicative complexity of A_{4,3} and constant-added addition F_{3,K}
MC(A_{4,3}) = 5 = MC(F_{3,K}) for every K mod 8; MC(F_{2,K}) = 2 = MC(A_{4,2})
Published 2026-09-04
For everyone
Plain summary
Adding four numbers modulo 8 takes five AND gates. Adding any fixed constant integer K modulo 8 to that sum still takes five AND gates. At width 2, adding four inputs modulo 4 takes two AND gates, with or without an added constant.
This zero-cost constant addition does not hold at larger bit-widths. At widths 2 and 3, the constant comes for free because intermediate products already computed by the addition circuit happen to cover the threshold carry check. At width 32, real cryptographic constants, including those in SHA-256, fall outside the zero-cost orbit of zero.
Result
For four-input addition at bit-widths 3 and 2:
MC(A_{4,3}) = 5 = MC(F_{3,K}) for every K mod 8
MC(A_{4,2}) = 2 = MC(F_{2,K}) for every K mod 4
The cost difference between constant-free four-input addition and addition with a fixed constant K is zero across all proved symmetry orbits at bit-widths 4 and 5.
This constant-freeness does not extend to arbitrary bit-widths n. The inductive step is:
MC(F_{n+1,K}) = MC(F_{n,k}, C^k_{4,n})
where the inductive object is the joint lower output and next-stage carry. The carry function decomposes as:
C^k_{4,n} = C^0_{4,n} XOR [A_{4,n} >= 2^n - k]
The threshold predicate [A_{4,n} >= 2^n - k] is nonlinear in general. The exact equality MC(F_{n,K}) = MC(A_{4,n}) at small widths holds because existing intermediate product terms catalyze this nonlinear threshold, not through universal structural equivalence.
Setting and definitions
Let A_{4,n} denote the addition of four n-bit unsigned integers modulo 2^n. Let F_{n,K} denote the addition of four n-bit unsigned integers plus a fixed constant K modulo 2^n.
Multiplicative complexity MC(f) is the minimum number of two-input AND gates (multiplications over GF(2)) required to evaluate the multi-output Boolean function f with straight-line programs over the standard basis (XOR, AND, NOT).
C^k_{4,n} is the carry-out generated by adding four n-bit inputs with a constant k. C^0_{4,n} is the carry-out of the zero-constant addition. The predicate [A_{4,n} >= 2^n - k] evaluates to 1 when the sum of the four n-bit inputs reaches or exceeds 2^n - k.
Method
The exact values MC(A_{4,3}) = 5, MC(F_{3,K}) = 5 for all K mod 8, MC(A_{4,2}) = 2, and MC(F_{2,K}) = 2 for all K mod 4 were established under cost model AGL(n, 2) Orbits / Encodings.
The verification carries evidence tier FC+FR at the settled widths, archived in receipts RECORD-CONSTFREE.md and RECORD-CONSTLIFT.md.
Discussion
The complexity match MC(F_{n,K}) = MC(A_{4,n}) holds at widths 2 and 3, and the difference is zero on proved symmetry orbits at widths 4 and 5.
Width scaling fails because evaluating the joint low output and carry requires computing C^k_{4,n} = C^0_{4,n} XOR [A_{4,n} >= 2^n - k]. At widths 2 and 3, products generated during the evaluation of A_{4,n} fully catalyze this threshold predicate. At higher widths, this catalysis fails in general; no round constant in SHA-256 lies within the width-32 symmetry orbit of the zero constant.
For everyone — the takeaway
What this means
Adding a fixed constant to a four-operand sum of 2-bit or 3-bit numbers requires no extra multiplication gates. The circuit computes the constant carry entirely from intermediate values already present in the addition.
This zero-cost behavior stops at larger word sizes. For 32-bit addition, such as in SHA-256, constants do not belong to the small-width symmetry orbits. Constant additions cannot be assumed free in wide arithmetic datapaths.
Register references
- Entry: MF-140
- Receipts: RECORD-CONSTFREE.md, RECORD-CONSTLIFT.md
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 0 of 2 receipt files bundled (1 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.