Research · Papers · What rank-one constraints can express · MF-012
An impossibility theorem for pinning the three-input AND under quadratic systems
No quadratic system in (x1,x2,x3,w) can pin w=1 at x=(1,1,1) for R=Graph(w=x1x2x3)={(x1,x2,x3,w)∈F2^4:w=x1x2x3}
Published 2026-08-29
For everyone
Plain summary
This result studies the three-input AND function, whose output is 1 only when three input bits are all 1. It gives the function an extra recorded value \(w\), required to equal the correct answer \(x_1x_2x_3\). A quadratic rule is a constraint containing products of at most two quantities. The theorem says that, when this extra value is kept explicitly, quadratic rules cannot force \(w\) to take its positive value \(1\) at the positive input \((1,1,1)\). This is an impossibility statement about one small input-output table. It does not establish the same obstruction for the carry calculations used in binary addition; that broader extension remains conjectural in the register. Batches A and B independently prove the graph statement, and the Batch B checker tests all 256 Boolean functions of three inputs as well as the certificate for the three-input AND result. The register records no prior-art comparison and makes no novelty claim.
Result
Let \[ R=\operatorname{Graph}(w=x_1x_2x_3) =\{(x_1,x_2,x_3,w)\in\mathbb F_2^4:w=x_1x_2x_3\}. \] In the fixed graph coordinates \(x_1,x_2,x_3,w\), the positive input is \(x=(1,1,1)\), whose graph value is \(w=1\). The positive-pin obstruction states that no quadratic system can pin \(w\) to this value at that input. Equivalently, the graph cannot be protected from its positive-input wrong value using only quadratic relations in these fixed coordinates.
The theorem is proved for the graph coordinate presentation. The register leaves the carry-wide mechanism conditional: applying the same obstruction to carry systems remains conjectural.
Setting and definitions
The base field is \(\mathbb F_2\), with coordinates \(x_1,x_2,x_3,w\). The graph relation contains the four-tuples satisfying \(w=x_1x_2x_3\). A quadratic system is a collection of Boolean relations of degree at most two in these coordinates. “Pinning” \(w\) at an input means excluding the alternative value of \(w\) while retaining the graph value. “Fixed graph coordinates” keeps \(w\) as the explicit output coordinate rather than replacing it by an auxiliary representation.
Method
Batches A and B independently proved the stated obstruction. The Batch B checker exhaustively verifies all 256 three-input Boolean functions and verifies the AND3 certificate. The register records the replay receipts batch_a_replay_receipt.json and batch_b_replay_receipt.json under CONT, with the underlying brief cited as BRIEF B.3.
The proof and replays establish the fixed-coordinate graph obstruction. No carry-wide application was inferred from the abstract result. The register says that applying the theorem to each observed carry rank wall still requires each live relation export.
Discussion
The fixed-coordinate qualifier controls the claim. The result proves the obstruction for the graph of \(w=x_1x_2x_3\) and the positive input \((1,1,1)\). It supplies a conditional explanation for carry systems: if the same mechanism governs them, every observed rank-\((n-1)\) wall would be covered by one theorem, and witness-basis changes could never remove the obstruction; only catalyst coordinates could. That implication depends on the carry relations exporting the relevant fixed-coordinate graph, and the register says the abstract theorem alone does not establish it.
The carry-wide mechanism therefore remains CONJECTURAL. The entry is an impossibility theorem for a fixed graph presentation, with no stated prior-art comparison or novelty position. The register records no prior-art work or search.
For everyone — the takeaway
What this means
The theorem identifies a precise limitation in a tiny calculation. A three-input AND can be written as an ordinary table, with \(w\) recording its answer. At the all-ones input, the answer is positive, yet rules involving at most two quantities cannot force that answer when \(w\) is kept as the direct output value. This helps explain why some constrained binary-addition designs hit a wall. The explanation transfers to those larger designs only after their individual relations are checked. Changing how hidden values are represented cannot solve the obstruction under the stated conditional mechanism; adding suitable extra recorded values may. The broader claim about carry calculations remains open.
Register references
Entry: MF-012.
Receipts: BRIEF B.3; CONT batch_a_replay_receipt.json; CONT batch_b_replay_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 2 of 2 receipt files bundled (7 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.