Research · Papers · Adders, counters and the heap law · MF-040
An upper bound on the multiplicative complexity of the natural (S,S+R) component
MC(component) ≤ 8 for the 13-input, 7-output natural (S,S+R) component
Published 2026-08-29
For everyone
Plain summary
This entry records a verified circuit for an exact carry component. The block takes 13 input bits and outputs 7 bits. Multiplicative complexity counts the number of multiplication-like product steps. The recorded circuit uses eight product gates: five compute products directly from the raw inputs, and three chain into earlier products. All 8,192 possible input rows were tested across a direct scalar script, a NumPy array pass, a decoded-formula runner, and an independent Return 6 replay. Every replay matched the target table with zero errors. This proves eight products suffice. It does not prove eight is minimal. Two disjoint copies give the known 16-product period baseline, while a combined 14-product construction and an unrestricted six-product component remain open. The register records no prior art.
Result
For the exact 13-input, 7-output natural (S,S+R) component, the register establishes the constructive upper bound
MC(component) <= 8
The witness circuit pairs five input-only wedges with three chained products. Scalar execution, a NumPy recheck, and a fresh decoded-formula implementation each reproduce the complete 8,192-row truth table with zero mismatches. The resulting output table matches SHA-256 digest 7a61888ba56729e373c5d706e6554c0de74ce32b1b881b892ae82e7405d91965.
The result establishes sufficiency. It does not claim MC(component) = 8.
Setting and definitions
The component realizes the exact natural (S,S+R) law on 13 Boolean inputs and 7 Boolean outputs, defining a full domain of 2^13 = 8,192 assignments.
Multiplicative complexity counts product gates in a pN circuit. The eight-product witness consists of five input-only products (wedges whose arguments derive strictly from primary inputs) and three chained products that read intermediate product signals. The bound certifies this component law over its entire domain; it implies neither minimality nor an automatic reduction for the combined period-two tile.
Method
The circuit specification and numerical confirmation define the witness circuit. The scalar harness, NumPy runner, and decoded-formula implementation executed exhaustive evaluations over all 8,192 domain rows against the SHA-256 truth table digest.
An independent verification pass re-verified the full truth table, with raw verification scripts and receipts provided in this paper's downloadable evidence pack. The verification confirms the upper-bound witness but contains no lower-bound optimality certificate.
Discussion
The status is PROVED (constructive), certifying MC(component) <= 8. Instantiating two disjoint component copies yields the baseline p16 period tile. The construction delivers no p14 combined result and updates no zkGolf rows.
Optimality remains open: the register neither provides nor excludes an unrestricted p6 component. Further compression and the joint period-two target remain separate problems. The INDEX records no corrections, retractions, or addenda for MF-040 (curation note NONE). The register records no prior art.
For everyone — the takeaway
What this means
A 13-input, 7-output carry block can be computed in eight multiplication steps. All 8,192 possible input combinations were tested, and every output bit matched. Two separate copies take sixteen steps when run side by side. Eight is a ceiling: the circuit proves eight steps work, but does not settle whether six or seven steps are possible. Combining the steps into a fourteen-product two-column block remains an open challenge.
Register references
- Entry:
MF-040. - Receipts: Return D
period_two_component_p8_report.json; Return Dperiod_two_component_p8_numpy_recheck.json; CONTreturn6_d_component_p8_independent_replay.py; CONTreturn6_d_component_p8_independent_replay.json; CONTreturn6_d_verification_receipt.json. - Prior art: The register does not record this.
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 5 of 5 receipt files bundled (6 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.
Changelog
Last reviewed 2026-08-29
- 2026-08-29Published on this site.