Research · Papers · Adders, counters and the heap law · MF-183
Discard-tax principle for heap optimality with discarded top digits
MC(S⁻) = MC(S) − (heap ANDs exclusive to the dropped digits)
Published 2026-09-04
For everyone
Plain summary
Multiplicative complexity measures the number of logical AND gates needed to evaluate an operation when XOR and NOT gates are free. In arithmetic heaps, values build up across successive stages. When a circuit ignores the highest output bits—such as computing an operation modulo a power of two—we want to know how many AND gates can be dropped.
The discard-tax principle conjectures that dropping top digits saves only the AND gates dedicated exclusively to those digits. Truncation cannot produce surprise savings in the lower bits. This rule unifies four separate circuit bounds, including standard adder chains and counters. It is proved for quadratic functions and cases where the top digit is kept, but it remains open when top digits are dropped and the remaining output has high algebraic degree. SAT solver tests hit their target upper bounds, while lower-bound challenge runs reached time limits.
Result
The discard-tax conjecture asserts that for a heap output structure S with truncated top digit(s) S⁻:
MC(S⁻) = MC(S) − (heap ANDs exclusive to the dropped digits)
This unifies four related formulations:
- Flagship carry circuit bound: MC(J_m) = 2m−2 (giving J_32 = 62, F_32 = 61).
- Resolution tax relation from ML-089: τ_m = MC(K_m) − MC(J_{m+1}) = 1.
- Scalar top-digit bound: MC(TOP_m) = 2m−2, proved for m = 2, 3.
- Counter family form under modular truncation matching the Boyar–Peralta theorem on retained outputs: MC(H_n mod 8) = heap = 6, 6, 7 for n = 8, 9, 10 with algebraic degree floors 3, 3, 3.
Setting and definitions
Let MC(f) denote the multiplicative complexity of f over (XOR, AND, NOT) with free linear operations. For an arithmetic heap S, let S⁻ denote the specification obtained by discarding one or more top output bits. The heap AND count exclusive to the dropped digits counts canonical heap multiplicative gates that do not feed any retained lower-degree coordinates.
Status by parameter regime:
- Proved when the top digit is kept (degree tight).
- Proved for quadratic targets via symplectic rank arguments.
- Open when top digits are discarded and the highest retained output has algebraic degree ≥ 4.
Method
Automated SAT and synthesis runs in fivecent_discard.py and rref_discard.py tested the degree-gap counter instances starting 2026-09-03 07:50 CEST:
- H_8 mod 8 at multiplicative budget p = 5.
- H_9 mod 8 at multiplicative budget p = 5.
- H_10 mod 8 at multiplicative budget p = 6.
UNSAT certificates at these budgets confirm the lower bounds. A SAT certificate disproves the discard-tax principle and breaks the associated complexity route.
Execution benchmarks:
- Upper-bound control H_8 mod 8 at p = 6: SAT in 1,201 s; replay verified PASS.
- Upper-bound control H_9 mod 8 at p = 6: SAT in 216 s; replay verified PASS.
- Lower-bound payload runs (p = 5 for H_8, H_9; p = 6 for H_10): TIMEOUT at 3,600 s under tile_synth.
- RREF gauge calculation remains pending.
Discussion
The discard-tax principle remains conjectural. It unifies established linear carry bounds (J_m, K_m) and small scalar cases, but truncated counters with retained degree ≥ 4 currently exceed synthesis solver limits.
Positive controls confirmed valid implementations at the upper-bound heap counts (MC = 6 for H_8 and H_9 mod 8). Because the payload instances hit the 3,600 s limit without returning UNSAT certificates, the register lacks computational proofs for MC(H_8 mod 8) ≥ 6 or MC(H_9 mod 8) ≥ 6. The register records no prior-art position.
For everyone — the takeaway
What this means
When a circuit drops high-order output bits, you might hope for clever shortcuts in the remaining calculation. The discard-tax principle says those shortcuts do not exist: discarding top bits only saves the gates built solely to produce them. If the conjecture holds, optimizing truncated circuits cannot beat the baseline heap cost for the retained bits.
Register references
- Entry: MF-183
- Related entries cited: ML-089
- Scripts and encodings: fivecent_discard.py, rref_discard.py
- Receipts: council4_fivecent/discard_H*_mod8_p*.json
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 2 receipt files bundled (3 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-03Status remains conjecture: instances H_8 mod 8 p=5 (8 inputs, 256 rows), H_9 mod 8 p=5, and H_10 mod 8 p=6 timed out at 3,600 s and 7,200 s (controls H_8 p=6 and H_9 p=6 succeeded). The bottleneck is the degree 4 output against 5 gates rather than 13-wire width; a 24 h run on H_8 mod 8 p=5 is underway.
- 2026-09-04Published on this site.