Research · Papers · Adders, counters and the heap law · MF-117
Bounds on the strict width-nine cost E_9
18 ≤ E_9 ≤ 36
Published 2026-09-04
For everyone
Plain summary
In digital logic, XOR additions are effectively free, so circuit cost is measured by counting multiplication gates over GF(2). This entry establishes bounds on E_9, the strict width-nine multiplicative cost. Any valid circuit requires at least 18 multiplication gates, and a working implementation exists using 36. Both bounds are machine-verified, but the exact value between 18 and 36 is still an open question.
Result
Under the GF(2) XOR-and-inverter graph (XAG) multiplicative complexity model, the strict width-nine cost E_9 satisfies:
18 ≤ E_9 ≤ 36
Both bounds are proved. The exact value of E_9 within [18, 36] remains open.
Setting and definitions
Circuits are evaluated under the GF(2) XAG cost model, where linear XOR and inverter operations cost zero and the metric counts non-free AND gates. The parameter E_9 denotes the strict width-nine multiplicative cost. The register defines no additional sub-parameters.
Method
The two-sided bound rests on two verification artifacts:
- Lower bound 18 ≤ E_9: verified floor certificate in
zkgolf-decomp/sb-tax-scratch/n9_one_full_floor_receipt.json(SHA-2565a5237e61432a07345684ff252cb112ad2aeb2606ffda9bcfab3500ca009b25e), supplying evidence tier P + FC + FR. - Upper bound E_9 ≤ 36: verified by the cleanroom script
zkgolf-decomp/sb-tax-scratch/cleanroom_upper.py(SHA-256c03bb6312c08c9b35633cb3817c69e41ba3da401e3ad5957a594709adef51a00).
Supporting analyses and program states are recorded in zkgolf-decomp/reports/SB-TAX.md, zkgolf-decomp/reports/EXP-EQ-TAX.md, and zkgolf-decomp/reports/STATE-OF-PROGRAM-V2.md.
Discussion
The upper value 36 is a constructive ceiling rather than an exact minimum, leaving E_9 open within [18, 36]. The register records no external prior-art attribution for this parameter.
For everyone — the takeaway
What this means
Every width-nine binary circuit needs at least 18 multiplication gates, and 36 gates are always enough to build one. These bounds fix the search space for hardware designers, who now know the absolute best-case and worst-case costs for width-nine implementations.
Register references
- Register entry: MF-117
- Program reports:
zkgolf-decomp/reports/SB-TAX.mdzkgolf-decomp/reports/EXP-EQ-TAX.mdzkgolf-decomp/reports/STATE-OF-PROGRAM-V2.md- AX162 artifacts:
zkgolf-decomp/sb-tax-scratch/n9_one_full_floor_receipt.json(SHA-2565a5237e61432a07345684ff252cb112ad2aeb2606ffda9bcfab3500ca009b25e)zkgolf-decomp/sb-tax-scratch/cleanroom_upper.py(SHA-256c03bb6312c08c9b35633cb3817c69e41ba3da401e3ad5957a594709adef51a00)
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 (33 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.