Research · Papers · Adders, counters and the heap law · ML-049
An eight-product acyclic XAG for the low four bits of x₀+x₁+x₂+x₃
An acyclic XAG computes the low four bits of x₀+x₁+x₂+x₃ in 8 products (target 4op_w4_p8, p = 8 is SAT)
Published 2026-08-29
For everyone
Plain summary
We want to know how many multiplications are needed to add four 4-bit numbers and get the lowest four bits of x₀+x₁+x₂+x₃. An explicit eight-product circuit matches all 65,536 input combinations with zero errors. This settles p = 8 as SAT by direct construction, even though automated solvers never returned a verdict. The search now hinges on p = 7. If p = 7 is UNSAT (impossible), the minimal count is 8. If p = 7 is SAT (possible), it beats the standard eight-product carry-save baseline. The register records no prior-art position.
Result
An acyclic XAG computes the low four bits of x₀+x₁+x₂+x₃ for target 4op_w4_p8 in eight products. Each product multiplies two affine factors over {1, inputs, earlier products}, and each output is an affine readout, matching the MF-082 bound 3·4−4 = 8. The emitted witness evaluates across all 65,536 truth-table rows with zero mismatches, establishing p = 8 as SAT.
The open branch is p = 7. An UNSAT outcome establishes the acyclic complexity as 8, while SAT beats the carry-save baseline and provides the program's first multi-operand addition improvement.
Setting and definitions
The target consumes four 4-bit operands (16 input bits in operand-major little-endian order) and emits the four lowest sum bits. Circuits are acyclic XAGs where each counted product takes affine combinations of inputs and earlier products, outputs are affine readouts, and p denotes the product budget.
Method
The witness was generated under the discriminator model, and certificate replay checked all 65,536 truth-table rows. An independent verification routine parsed gate definitions, verified affinity and acyclicity, and evaluated plain-integer rows, confirming 8 gates, 65,536 points, and 0 mismatches.
Discussion
Because the explicit witness settles p = 8 without requiring solver completion, the entry status is NOT DECISIVE. The register logs three inconclusive p = 8 solver attempts, two of which hit memory limits. The p = 7 branch remains open; the register holds no p = 7 verdict and no prior-art position.
For everyone — the takeaway
What this means
The seven-product question remains open.
A verified circuit proves eight multiplications suffice to add four 4-bit numbers, bypassing solver timeouts. The remaining task is testing whether seven products can do the job. Proving seven impossible establishes eight as the exact minimum. Finding a seven-product circuit beats the standard baseline. Search effort shifts entirely from p = 8 to p = 7.
Register references
- ML-049
- MF-082
- MF-083
emit_4op_w4_p8_witness.py(SHA-256827a1fd6…77ee)4op_w4_p8_witness_certificate.json(SHA-256df675452…af5de)factory/discriminators/DISCRIMINATOR-4OP.mdindependent_witness_verifier.py(SHA-256cd5ac487…26bd)independent_witness_replay.json(SHA-25660d2565c…1179)4op_w4_p8.attempt{1,2,3}.statussbp_encoder.py verify- Prior-art position: 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 2 of 5 receipt files bundled (4 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.