Research · Papers · What rank-one constraints can express · MF-059
Complete witness-width classification of Boolean functions on F₂⁴
Every Boolean function `f: F₂⁴ → F₂` has a well-defined minimum witness width `ω(f)` in the finite arbitrary-affine-C rank-one model with an affine decoder and arbitrary nonempty f
Published 2026-08-29
For everyone
Plain summary
Take every rule that maps four yes-or-no inputs to one yes-or-no output. This result gives each rule a minimum witness width, meaning the smallest number of allowed witness pieces needed to represent it with an affine decoder, a final XOR-based rule with a constant, and arbitrary nonempty fibres, the model’s allowed sets of hidden values. An affine rule is one made from XORs of input bits and a constant. Every four-input rule has a well-defined minimum in this finite model, and the complete population falls into four width classes: 32 functions at width 0, 1,120 at width 1, 63,872 at width 2, and 512 at width 3. The width-three class has an especially simple description: its output list differs from an affine rule at exactly one input. The four-input AND function, AND₄, is in that class, so its minimum width is 3. A Python generator BFS and an independent second enumeration agree on the classification. The register records no prior-art position.
Result
Every Boolean function f: F₂⁴ → F₂ has a well-defined minimum witness width ω(f) in the finite arbitrary-affine-C rank-one model with an affine decoder and arbitrary nonempty fibres. The extended-affine orbit classification has eight orbits covering all 2,048 output-affine cosets. The function masses by minimum width are:
Minimum width ω(f) | Number of functions |
|---|---|
| 0 | 32 |
| 1 | 1,120 |
| 2 | 63,872 |
| 3 | 512 |
The width-three class is uniquely the 512 functions at Hamming distance one from affine. In particular, it contains AND₄, and therefore ω(AND₄)=3.
Setting and definitions
The domain is F₂⁴ and the codomain is F₂. The model is the finite arbitrary-affine-C rank-one model recorded in the register. It includes an affine decoder and permits arbitrary nonempty fibres. The witness width ω(f) is the minimum number of rank-one witnesses required for f in that model. The classification is also expressed through extended-affine orbits and output-affine cosets. Hamming distance one from affine means that the truth table of a function differs from the truth table of an affine function at exactly one input.
Method
The classification was established by two independent finite enumerations. A Python generator BFS generated the model’s functions and their minimum widths. An independent GL(4,2) enumeration used 20,160 matrices and 16 translations. The resulting orbit structure, width masses, and placement of AND₄ agree between the two procedures. The register names the CONT verification report and two package certificates as the receipts for this work. The agreement supplies an independent cross-check of the complete four-bit census.
Discussion
The theorem is complete for the stated four-input, one-output model. It gives a minimum width for every Boolean function in that finite setting, organizes the functions into eight extended-affine orbits, and accounts for all 2,048 output-affine cosets. The width distribution is sharply uneven: width 2 contains the largest recorded mass, while width 3 contains exactly the functions one truth-table change away from affine. AND₄ is therefore a member of a precisely characterized exceptional class within this model.
The width masses also separate two levels of the result. The eight-orbit statement describes the organization into extended-affine orbits, while the four mass counts describe individual functions. The width-three criterion gives a direct membership test for the largest-width class: one truth-table change from affine. Since the class contains AND₄, the value ω(AND₄)=3 follows from the complete classification. The register reports no unresolved width class within the stated four-bit census.
The result supports the exact statement ω(AND₄)=3 under the recorded model assumptions. Its scope ends with those assumptions and four input bits. The register supplies no claim about other input dimensions, other witness models, or a comparison with prior literature. The register does not record a prior-art position.
For everyone — the takeaway
What this means
The result is a complete map of a small but important design space. Instead of knowing only that AND₄ needs three witnesses, we now know where every four-input yes-or-no rule sits: width 0, 1, 2, or 3. Most of the functions occupy the middle class, and the hardest class has a clean visual description—one changed entry in an otherwise XOR-based output list. Two independent enumerations reach the same map. That makes the classification a reliable reference point for later ways of representing functions with witnesses. Its conclusion is exact inside the stated finite model, with no recorded claim beyond that setting.
Register references
MF-059
Receipts: CONT lens_r2a_catalyst_verification_report.md; package certificates/four_bit_ea_witness_width_census.json; package certificates/ea_witness_width_crosscheck.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 3 of 3 receipt files bundled (8 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.