Research · Papers · Adders, counters and the heap law · MF-118
Exact shear symmetry of multiplicative complexity in constant addition
MC(F_{n,K}) = MC(F_{n,K+2^{n-2}}), with MC(F_{2,K}) = 2 and MC(F_{3,K}) = 5 for all constant offsets K
Published 2026-09-04
For everyone
Plain summary
Adding a fixed constant number to an unknown binary value is a core operation in processors and zero-knowledge cryptography. In cryptographic circuits, linear steps like XOR additions cost nothing, while non-linear multiplications (AND gates over bits) are computationally expensive. Multiplicative complexity measures the minimum number of multiplications needed to compute a function.
This paper proves that shifting an added constant by 2^(n-2) leaves the multiplicative complexity of an n-bit modular addition unchanged. This symmetry collapses costs across constant choices: every 2-bit constant addition requires exactly 2 multiplications, and every 3-bit constant addition requires exactly 5, regardless of the offset.
Result
Let F_n,K : GF(2)^n -> GF(2)^n compute (x + K) mod 2^n for an n-bit input x and constant offset K ∈ {0, 1, ..., 2^n - 1}. In the GF(2) XOR-and-inverter graph (XAG) model with free XOR and NOT gates, the multiplicative complexity MC(F_n,K) satisfies the exact shear symmetry:
MC(F_n,K) = MC(F_n, K + 2^(n-2))
for all n ≥ 2, where addition on K is modulo 2^n.
Evaluating this symmetry on small bit-widths yields uniform values across all offsets:
- Width n = 2: MC(F_2,K) = 2 for all K ∈ {0, 1, 2, 3}.
- Width n = 3: MC(F_3,K) = 5 for all K ∈ {0, 1, ..., 7}.
Setting and definitions
Computations are over GF(2). An input x = (x_0, x_1, ..., x_(n-1)) ∈ GF(2)^n encodes an unsigned integer with least significant bit x_0. For offset K ∈ {0, ..., 2^n - 1}, the map F_n,K : GF(2)^n -> GF(2)^n outputs the n-bit encoding of (x + K) mod 2^n.
The multiplicative complexity MC(f) of a Boolean function f : GF(2)^n -> GF(2)^m is the minimum number of two-input AND gates required by an XAG computing f, with XOR gates, NOT gates, and constants available at zero cost. The shear step delta = 2^(n-2) defines an additive perturbation on K that preserves MC(F_n,K).
Method
The result combines structural reductions, constructive synthesis, and exhaustive automated verification.
Theoretical derivations and upper-bound synthesis:
- zkgolf-decomp/reports/CONST-THEORY.md derives the shear invariance MC(F_n,K) = MC(F_n, K + 2^(n-2)).
- zkgolf-decomp/reports/CONST-BUILD.md constructs optimal XAG topologies matching upper bounds.
- zkgolf-decomp/reports/STATE-OF-PROGRAM-V2.md tracks integration and global proof status.
Verification artifacts executed on AX162:
- zkgolf-decomp/const-theory-scratch/heap-and-width32.receipt.json (SHA-256 97495ea7cb13222225e45598ceef9956d61e9684d0c2001e96613a41f83a4da0) validates circuit upper bounds and heap structures.
- zkgolf-decomp/const-theory-scratch/small-grid-lower.receipt.json (SHA-256 af5365a96feb27fcfecab8c9d8f1fc291b4aedb280e7f999958abc52a0c28a89) validates exhaustive SAT lower-bound certificates establishing MC(F_2,K) ≥ 2 and MC(F_3,K) ≥ 5 across the grid.
Evidence tier: P + FC + FR (Proved with Formal Certificate and Full Replay).
Discussion
Shear symmetry establishes that constant addition costs do not depend arbitrarily on K. Shifting K by 2^(n-2) cuts the space of distinct complexity classes by half.
For small bit-widths, the symmetry forces complete uniformity:
- At n = 2, the shift delta = 2^(2-2) = 1 links all K ∈ {0, 1, 2, 3} into a single orbit of length 4, fixing MC(F_2,K) = 2.
- At n = 3, the shift delta = 2^(3-2) = 2 partitions the 8 offsets into two orbits under step size 2. Combined with complementation symmetries and certified lower bounds, MC(F_3,K) = 5 for every K ∈ {0, 1, ..., 7}.
Scope and limits: The entry establishes the structural shear symmetry for F_n,K and exact evaluations for n = 2 and n = 3. It does not provide closed-form formulas for arbitrary n > 3. The audit row records status PROVED with verdict CONFIRMED under the GF(2) XAG cost model.
For everyone — the takeaway
What this means
Zero-knowledge proof systems treat XOR additions as free but charge heavily for binary multiplications (AND gates). Circuit designers previously had to search for optimal implementations of constant addition on a case-by-case basis.
This result proves an underlying mathematical symmetry: adding 2^(n-2) to the constant never changes the required number of multiplications. For 2-bit and 3-bit numbers, every constant costs the exact same amount: 2 multiplications for any 2-bit constant, and 5 multiplications for any 3-bit constant. Cryptographic compilers can use these numbers as exact, minimal baseline costs.
Register references
- Register ID: MF-118
- Reports:
- zkgolf-decomp/reports/CONST-THEORY.md
- zkgolf-decomp/reports/CONST-BUILD.md
- zkgolf-decomp/reports/STATE-OF-PROGRAM-V2.md
- Receipts:
- zkgolf-decomp/const-theory-scratch/heap-and-width32.receipt.json (SHA-256: 97495ea7cb13222225e45598ceef9956d61e9684d0c2001e96613a41f83a4da0)
- zkgolf-decomp/const-theory-scratch/small-grid-lower.receipt.json (SHA-256: af5365a96feb27fcfecab8c9d8f1fc291b4aedb280e7f999958abc52a0c28a89)
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 (35 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.