Research · Papers · The SHA-256 record and exact synthesis · MF-001
Exact multiplicative complexity of a ten-input schedule tile
MC(f) = 6 in the XOR-AND circuit model for the ten-input schedule tile f
Published 2026-08-29
For everyone
Plain summary
MF-001 establishes the exact multiplication count for a ten-input binary schedule block. In this circuit model, each product multiplies two binary expressions. The result provides a working six-product circuit and an algebraic certificate proving that no five-product circuit can compute the block. The certificate checks the block's degree-six top form against a Plücker identity, an algebraic condition that any five-product implementation must meet at this boundary. The test covers all 1,024 input assignments and runs in under a second. A separate brute-force synthesis search at five products is still running, so the page carries a caveat. The register records no prior-art or novelty claims.
Result
Let f denote the ten-input schedule tile. In the stated XOR-AND circuit model,
MC(f) = 6.
More explicitly:
fhas a six-product realization.- No five-product realization of
fexists.
The lower bound follows from the degree-six Plücker obstruction at the extremal boundary r = 5, deg(f) = 6 = r + 1. The recorded output degrees are [1,2,4,6] on the 1,024-row domain. This is an exact determination for the assigned tile and circuit model.
Setting and definitions
The tile is a Boolean function with ten inputs and the four outputs specified for the schedule interface. An r-product XOR-AND realization is an acyclic circuit with r AND gates, where each gate multiplies two affine combinations of inputs and previous products, and each output is an affine readout.
For a polynomial output, top_d(f) denotes its homogeneous degree-d component. A degree-six form is decomposable if it factors as the exterior product of lower-degree forms. Plücker identities are the polynomial relations satisfied by every decomposable form.
When an r-product XOR-AND circuit produces an output of degree exactly r + 1, its degree-(r + 1) component must be decomposable. MF-001 applies this equality case with r = 5 and target degree 6.
Method
The verified six-product upper bound is provided in this paper's downloadable evidence pack. The lower bound derives from the Plücker certificate replayed under MF-097.
The replay returned status=UNSAT. It confirmed output degrees [1,2,4,6] and the degree-six support e₄(x₀,x₂,x₄,x₆,x₈)·e₂(x₁,x₃,x₅,x₇,x₉) across all 50 monomials. A concrete Plücker relation evaluates to 1, whereas a decomposable form must evaluate to 0. The generic 6×10 determinant identity vanishes over GF(2). Consequently, the degree-six top component cannot be generated by a five-product circuit under the extremal equality condition.
The certificate script and verification artifacts are provided in this paper's downloadable evidence pack and were replayed under MF-097. The register records an exact recheck across all 1,024 inputs in under one second.
Discussion
MF-094 showed that top-form arguments fail in general XAGs when gate cancellations below degree r + 1 expose lower-degree top forms.
MF-097 demonstrated that this cancellation failure does not apply at degree r + 1. At this maximum degree, the top component can only originate from the final product, leaving no parallel equal-degree term to cancel it. Because MF-001 sits at the extremal case 6 = 5 + 1—unlike the non-extremal degree-six instance in MF-094—the certificate is valid.
This result is scoped strictly to the specified ten-input schedule tile and XOR-AND model; it does not generalize Plücker tests to unrestricted XAGs. Independent full-domain exact synthesis at p = 5 remains in flight. The p = 6 control solved as SAT in 1,139 seconds. The page verdict is CAVEAT. The register records no prior-art position or novelty claim.
For everyone — the takeaway
What this means
This tile requires six multiplications. A six-product design works, and the certificate proves five multiplications can't compute the function. This gives an exact hardware cost for the block rather than an estimate.
The proof holds because at five multiplications, the highest-degree terms cannot cancel out. A brute-force search for a five-multiplication circuit is still running as a cross-check, so the page retains its caveat. The register claims no novelty over prior work.
Register references
- MF-001; receipt: HANDOFF §2.5.
- MF-097; receipts:
zkgolf-pro-corpus-three-pack-2026-08-14\staging\01-attack-frontier\zkgolf-sha256\scratch\schedule-p5-alt\plucker_certificate.py,README.md,plucker-certificate.json. - MF-094; receipt:
04-andcount-optimization/audit_topform_counterexample.py. - 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 1 of 1 receipt files bundled (10 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-27On 2026-08-27, a scope flag on MF-001 was withdrawn after a replay check confirmed it correctly applies the equality lemma at degree 6 = r+1 with r = 5 (validated in MF-097), unlike the non-extremal cases refuted in MF-094. MF-001 stands as proved.
- 2026-08-29Published on this site.