Research · Papers · What rank-one constraints can express · MF-051
Impossibility of realizing AND4 with three witnesses and three product rows
The finite search space for an identity-C, affine-decoder, nonempty-even-fibre realization of AND4 with four public inputs, three witnesses, and three rank-one product rows contain
Published 2026-08-29
For everyone
Plain summary
AND4 outputs 1 only when all four of its inputs are 1. MF-051 tests whether AND4 can be realized with four public inputs, three hidden helper bits called witnesses, three rank-one product rows, and an affine decoder whose C component is fixed to the identity map. A rank-one product row multiplies two XOR-based affine terms. The model also requires every input to have a nonempty even fibre, meaning a positive even number of valid witness assignments.
A SAT solver searched this parameter space and showed that no valid configuration exists (UNSAT). CaDiCaL produced the result, which was verified by an independently checked DRAT proof certificate, with matching UNSAT runs from Glucose and CryptoMiniSat. This impossibility result applies strictly to this parameter setting. Nonidentity C, four witnesses, and other relational models remain UNKNOWN.
Result
The finite search space for an identity-C, affine-decoder, nonempty-even-fibre realization of AND4 with four public inputs, three witnesses, and three rank-one product rows contains no valid assignment. Encoded as a Boolean CNF formula with 4,038 variables and 15,836 clauses, the system is unsatisfiable (UNSAT). This refutes the existence of any realization under these exact parameters.
Setting and definitions
The formulation imposes four simultaneous structural constraints:
- Public inputs: 4 Boolean variables computing AND4.
- Witnesses: 3 hidden Boolean variables.
- Decoder: affine decoding with component C fixed to identity.
- Constraints: 3 rank-one product rows, each constraining the product of two affine expressions.
- Fibre condition: for each public input assignment, the set of satisfying witness tuples (its fibre) must have non-zero even cardinality.
A valid realization must satisfy the decoder, row, and fibre constraints while correctly evaluating AND4.
Method
The formulation was compiled into a CNF formula with 4,038 variables and 15,836 clauses. CaDiCal 2.1.3 determined the formula to be UNSAT. An independently checked DRAT certificate verifies the refutation across 46,011,844 bytes, 232,707 core lemmas, and 8,979,915 resolution steps. Glucose and CryptoMiniSat independently confirmed the UNSAT result on the same CNF instance.
Discussion
The impossibility boundary is narrow and defined strictly by the formulation:
- Setting C to a nonidentity map remains UNKNOWN.
- Expanding the witness budget to four remains UNKNOWN.
- Other row counts and relational models remain UNKNOWN.
The DRAT certificate closes only this exact parameter tuple. The register records no errata for MF-051 and no prior-art position.
For everyone — the takeaway
What this means
You cannot build an AND4 gate using three helper bits, three product constraints, and an identity-C affine decoder if every input must have an even, non-zero number of valid helper settings. A computer searched every possible assignment in this design and proved none work, confirmed by an independently verified mathematical proof certificate. Changing any parameter—such as adding a fourth witness bit or using a nonidentity C decoder—creates a different problem that this result does not cover.
Register references
MF-051
Receipt: CONT fleet-c-return7/phantom_and4_3w3r_verified_unsat_receipt.json (SHA-256 e0755dce91200d847bebdbd20ff937b0183bc81ed74fb35575625d4c184c81fc).
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 (2 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.