Research · Papers · Adders, counters and the heap law · ML-060
Symmetry and exact small-width complexity of constant-addition shears
MC(F_{n,K}) = MC(F_{n,K+2^{n-2}}), with MC(F_{2,K}) = 2 and MC(F_{3,K}) = 5 for every constant K
Published 2026-09-04
For everyone
Plain summary
Multiplicative complexity counts the logical AND gates needed to build a circuit over binary values when XOR gates are free. This paper studies constant-addition shears, which combine fixed-constant addition with shearing steps. Adding 2^(n-2) to the constant K does not change the multiplicative complexity of an n-bit shear F_{n,K}. For small bit-widths, the cost is constant across all choices of K: every 2-bit shear takes 2 multiplications, and every 3-bit shear takes 5 multiplications. For larger bit-widths, the formula H_n(K) = 4n - 6 - λ_n(K) gives an upper bound rather than an exact equality.
Result
Under the XOR-free GF(2) XOR-AND graph (XAG) model, constant-addition shears F_{n,K} obey the shift symmetry:
MC(F_{n,K}) = MC(F_{n,K+2^{n-2}})
for any bit-width n and constant K.
For bit-widths n = 2 and n = 3, multiplicative complexity is independent of K:
MC(F_{2,K}) = 2 for every constant K of width 2, MC(F_{3,K}) = 5 for every constant K of width 3.
Setting and definitions
Multiplicative complexity MC(f) counts non-linear AND gates over the GF(2) basis {AND, XOR, NOT}, with XOR and NOT gates assigned zero cost. The map F_{n,K} denotes an n-bit constant-addition shear parameterized by integer constant K. The heap complexity function H_n(K) = 4n - 6 - λ_n(K) measures the multiplicative cost of the canonical full-/half-adder heap construction.
Method
Results carry evidence tier P + FC + FR through automated certificate verification, lower-bound grid replay, and derivations recorded in zkgolf-decomp/reports/CONST-THEORY.md, zkgolf-decomp/reports/CONST-BUILD.md, and zkgolf-decomp/reports/STATE-OF-PROGRAM-V2.md.
Verification receipts:
zkgolf-decomp/const-theory-scratch/heap-and-width32.receipt.json(SHA-25697495ea7cb13222225e45598ceef9956d61e9684d0c2001e96613a41f83a4da0)zkgolf-decomp/const-theory-scratch/small-grid-lower.receipt.json(SHA-256af5365a96feb27fcfecab8c9d8f1fc291b4aedb280e7f999958abc52a0c28a89)
Discussion
The shift symmetry MC(F_{n,K}) = MC(F_{n,K+2^{n-2}}) and small-width values MC(F_{2,K}) = 2 and MC(F_{3,K}) = 5 are exact.
For larger n, the closed form H_n(K) = 4n - 6 - λ_n(K) belongs specifically to the canonical full-/half-adder heap family. It provides an upper bound across all circuits, not an exact lower bound, and does not yield a 92-product SHA component. Entries MF-118 and MF-119 treat related bounds.
For everyone — the takeaway
What this means
Non-linear multiplications determine proof generation time in zero-knowledge systems. Because shifting K by 2^(n-2) leaves the multiplication count unchanged, circuit synthesis tools can prune the parameter search space. The exact costs of 2 multiplications for 2-bit shears and 5 multiplications for 3-bit shears give tight targets for small components, while closed-form formulas for wider circuits remain upper bounds.
Register references
- Entry ID: ML-060
- Cross-references: MF-118, MF-119
- Reports:
zkgolf-decomp/reports/CONST-THEORY.mdzkgolf-decomp/reports/CONST-BUILD.mdzkgolf-decomp/reports/STATE-OF-PROGRAM-V2.md- Receipts:
zkgolf-decomp/const-theory-scratch/heap-and-width32.receipt.json(SHA-25697495ea7cb13222225e45598ceef9956d61e9684d0c2001e96613a41f83a4da0)zkgolf-decomp/const-theory-scratch/small-grid-lower.receipt.json(SHA-256af5365a96feb27fcfecab8c9d8f1fc291b4aedb280e7f999958abc52a0c28a89)
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 5 receipt files bundled (36 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.