Research · Papers · The quadratic hull and its defects · MF-090
Exact quadratic cover number of an OR-chain lift of a width-k clause over F2
For the lifted relation of a positive width-k clause (k ≥ 3), κ2,cover = k − 1
Published 2026-08-29
For everyone
Plain summary
A positive width-k clause is a logical rule on k variables that forbids a single assignment: setting every variable to false. We can represent this rule by breaking it into a chain of two-input OR operations using helper variables, then expressing each step as a degree-2 equation over binary values. Exactly k−1 quadratic equations are needed to define this lifted solution set. That count is sharp: k−1 equations suffice, and k−2 cannot define the set. The lower bound follows from the Chevalley-Warning theorem, which governs solution counts of low-degree polynomial systems over finite fields. The count was verified directly for widths 3 through 6, with independent brute-force checks at widths 3 and 4. The underlying techniques are standard, and the register records no novelty claim without a literature search on this exact encoding.
Result
Let x1, ..., xk be the variables of a positive width-k clause, with k ≥ 3. Introduce k−2 deterministic auxiliaries
u2 = x1 ∨ x2, uj = uj-1 ∨ xj (3 ≤ j ≤ k−1),
and encode each OR step by the quadric
u + a + b + ab = 0.
Add the final binary-clause equation
1 + a + b + ab = 0.
For this lifted relation, the exact quadratic cover number is
κ2,cover = k − 1.
The k−1 quadrics comprise the k−2 chain equations and the terminal binary-clause equation. Conversely, the lifted relation has n = 2k−2 variables and exactly 2^k − 1 common zeros. A cover by at most k−2 quadrics would have degree sum at most 2k−4 < n. By Chevalley-Warning over F2, any such system must have an even number of common zeros. Because 2^k − 1 is odd, no system of k−2 quadrics can define the relation.
Setting and definitions
All polynomials are over F2. The lifted relation comprises the k original clause variables and the k−2 chain variables. A quadric is a polynomial equation of degree at most two. The cover number κ2,cover is the minimum number of quadrics whose common zero set equals the lifted relation. The auxiliaries are deterministic: each is fixed by the previous accumulator value and the incoming clause variable.
Method
The upper bound is constructive: the k−2 OR-chain quadrics and the final binary-clause quadric form an explicit cover of size k−1. For the lower bound, the lifted system has n = 2k−2 variables and 2^k − 1 satisfying assignments. Because 2(k−2) = 2k−4 < 2k−2 = n, Chevalley-Warning over F2 requires any system of at most k−2 quadrics to have an even solution count mod 2. The odd zero count 2^k − 1 rules out all covers of size at most k−2.
The construction and proof were checked for k = 3, 4, 5, 6. An independent brute-force search over critical numbers confirms the result for k = 3, 4. The full derivations and verification artifacts are provided in this paper's downloadable evidence pack.
Discussion
The result characterizes the sequential OR-chain lift of a positive width-k clause over F2. Direct computation validates the formula through k = 6, with independent critical-number verification through k = 4; the Chevalley-Warning argument proves the claim for all k ≥ 3.
The components are classical, and the report makes no novelty claim absent a targeted prior-art search. The register does not record prior-art citations, nor does it record whether the cover number changes under non-sequential lift topologies or over larger fields. Because the auxiliaries are deterministic, the exact cover number applies specifically to this lifted representation.
For everyone — the takeaway
What this means
This result fixes the exact cost of translating a wide logical clause into degree-2 polynomial equations via an OR chain. Each intermediate variable holds a running OR, and the final equation enforces clause satisfaction. The count is tight: k−1 equations are enough, and k−2 equations cannot work. Proof-system designers can rely on k−1 as the exact quadratic budget for this encoding.
Attribution and prior art
Prior art: This result uses well-established, classical techniques, and no claim of novelty is made without a targeted literature search for this encoding theorem.
Register references
- Entry: MF-090.
- Receipt artifacts: 07-quadratic-hull-proof-complexity/REPORT.md §7.3 (Theorem 7.2); quadratic_hull_preprocessor.py; examples/.
- Prior-art works: 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 (22 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.