Research · Papers · The SHA-256 record and exact synthesis · ML-008
Exact multiplicative complexity of the schedule tile
The ten-input, four-output schedule tile requires a minimal r = 6 product gates in an acyclic XOR-AND circuit over GF(2)
Published 2026-08-29
For everyone
Plain summary
A small schedule tile maps ten on/off input bits to four on/off output bits across 1,024 truth-table rows. The outputs have degrees [1,2,4,6], measuring the highest-order interaction between inputs. An existing construction computes the tile with six product operations (AND gates operating on XOR sums). This result proves five products can't do it. A five-product circuit's degree-six top form must satisfy a specific algebraic Plücker identity over GF(2). The tile's actual degree-six output evaluates that identity to 1 instead of 0, yielding UNSAT across all 1,024 rows. The register records no prior-art comparison.
Result
For the recovered ten-input, four-output schedule tile, no acyclic XOR-AND circuit with r = 5 product gates realizes the target function. The output Möbius degrees are [1,2,4,6], placing the degree-six output at the extremal boundary 6 = r+1.
At this equality boundary, the degree-bound lemma forces the homogeneous degree-six component of the output to be decomposable. The target degree-six component is
e₄(x₀,x₂,x₄,x₆,x₈)·e₂(x₁,x₃,x₅,x₇,x₉)
across all 50 monomials. Its coefficient vector evaluates a concrete Plücker relation to 1 over GF(2), whereas decomposability requires 0. The five-product synthesis problem is therefore UNSAT. With an explicit six-product implementation on record, six products are minimal for this tile.
Setting and definitions
The schedule tile is the ten-input map
(x₀..x₉) ↦ bits(Σ_{i=0..4} x₂ᵢ + 2·x₂ᵢ₊₁).
It specifies four output bits over 1,024 truth-table rows with output degrees [1,2,4,6]. A product gate evaluates the AND of two affine forms over GF(2). For an output f, top₆(f) denotes its homogeneous degree-six part. A degree-six form is decomposable when it factors according to the extremal degree-bound induction for XOR-AND circuits.
The Plücker relation is the exterior-algebra relation vanishing on decomposable forms. The extremal lemma guarantees that any acyclic XOR-AND circuit with r product gates computing an output of degree r+1 has a decomposable degree-(r+1) top form: only the final product gate can contribute to that top degree, precluding cancellation between distinct gate outputs.
Method
The certificate in this paper's downloadable evidence pack was replayed on 2026-08-27, returning status=UNSAT for r = 5. The replay validated the output degrees [1,2,4,6], the 50-monomial support of
e₄(x₀,x₂,x₄,x₆,x₈)·e₂(x₁,x₃,x₅,x₇,x₉)
and the Plücker relation evaluation to 1. The generic 6×10 determinant identity vanishes identically over GF(2).
Soundness of the extremal induction step: replace the initial product L·R with an indeterminate z. The remaining r−1-product circuit computes F = F₀ + z·F₁. Specializing z := L·R to reach degree r+1 forces deg F₁ = r−1 and deg F = r. By induction, top(F₁) is decomposable. Contracting along z and taking exterior products with top(L) and top(R) yields a decomposable top component for the overall output. For r = 5, this applies directly to degree six.
A matching six-product upper bound is established by two verified three-product carry cells. Together with the five-product obstruction, this proves minimality.
Discussion
This lower bound is specific to the recovered schedule tile and its five-product topology. It does not generalize to arbitrary top-form tests: MF-094 exhibits an eight-product counterexample at non-extremal degree six (r = 8, 6 < r+1), where distinct degree-seven components cancel. Such cancellations are structurally impossible when 6 = r+1.
the flag was withdrawn the same day and ML-008 stands as PROVED. A separate full-domain exact-synthesis check at p = 5 remains in flight, independent of this certificate. The register records no prior-art comparison.
For everyone — the takeaway
What this means
You cannot build this ten-input schedule tile with five multiplication gates in the standard XOR-AND setup. Any five-product circuit reaching degree six must produce a top form with a rigid algebraic structure. The target tile's degree-six piece breaks that structure, failing an algebraic test on the 1,024-row table. Six products are both necessary and sufficient. This barrier holds because the degree equals the product count plus one; circuits with more products don't face the same restriction.
Register references
ML-008MF-001MF-094MF-097schedule-p5-alt\plucker_certificate.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 (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-27The certificate ruling out a five-product schedule topology (establishing 6 products minimal) remains unconfirmed until this experiment is completed.
- 2026-08-27A scope flag added on 2026-08-27 was withdrawn the same day after MF-097 showed the MF-001 flag was overly broad. Confirmed by a replay check, ML-008 stands as filed because its certificate at the extremal degree 6 = r+1 with r = 5 remains sound and unaffected by MF-094.
- 2026-08-29Published on this site.