Research · Papers · The quadratic hull and its defects · MF-089
The degree-(d) hull of Boolean relations with few forbidden points
If R ⊆ 𝔽_2^n, F = 𝔽_2^n \ R, 0 ≤ d ≤ n, and |F| < 2^{n-d}, then I_{≤d}(R) = {0} and H_d(R) = 𝔽_2^n
Published 2026-08-29
For everyone
Plain summary
Take allowed yes/no assignments and call the rest forbidden. This result gives a sharp cutoff for when equations with limited degree can notice omissions. Degree counts the maximum number of variables multiplied in one term. If fewer than (2^{n-d}) of the (2^n) assignments are forbidden, then no nonzero equation of degree at most (d) can vanish on all allowed assignments. The degree-(d) hull, the set of points surviving these tests, is therefore the entire Boolean cube. A width-(k) clause is a logical condition on (k) variables that excludes one assignment. For (k\ge 3), every quadratic test misses it, even though step-by-step clause reasoning can force a last variable in the familiar partial-assignment case. Widths 1 and 2 differ because their one-point exclusions have degree at most 2. The register marks MF-089 PROVED with a SHOW page verdict. The cutoff uses a classical Reed–Muller fact: a nonzero Boolean truth table of degree at most (d) has at least (2^{n-d}) entries equal to 1. Reed–Muller is a named family of such truth tables, and no novelty claim is recorded.
Result
Let (R\subseteq\mathbb F_2^n), let [ F=\mathbb F_2^n\setminus R, ] and let (0\le d\le n). If [ |F|<2^{n-d}, ] then [ I_{\le d}(R)=\{0\} qquad\text{and}\qquad H_d(R)=\mathbb F_2^n. ]
The threshold is tight. Minimum-weight words of (RM(d,n)) are indicators of affine subspaces of codimension (d), and they attain weight (2^{n-d}).
For the clause corollary, a width-(k) clause relation (R_k) has exactly one forbidden point. Therefore, for every (k\ge 3), [ I_{\le 2}(R_k)=\{0\} qquad\text{and}\qquad H_2(R_k)=\mathbb F_2^k. ] Every quadratic is blind to the clause’s sole false tuple. For (k=1,2), the unique-falsifier indicator has degree at most 2 and closes the hull.
The register states the structural warning precisely: a global static quadratic hull and root unit propagation are incomparable. The hull result does not turn into a general statement about SAT propagation.
Setting and definitions
The ambient cube is (\mathbb F_2^n). The relation (R) is the set of honest points, and (F) is its forbidden complement. (I_{\le d}(R)) denotes the space of degree-at-most-(d) Boolean polynomials that vanish on (R). (H_d(R)) is the degree-(d) hull determined by those vanishing polynomials.
The Reed–Muller code (RM(d,n)) is the collection of truth tables of Boolean polynomials of degree at most (d). Hamming weight counts the points at which a truth table is 1. A width-(k) clause relation has one forbidden tuple among its (k)-variable assignments. Root unit propagation is the local clause operation applied at a partial assignment.
Method
The proof uses the minimum-distance property of (RM(d,n)): every nonzero word has Hamming weight at least (2^{n-d}). A polynomial in (I_{\le d}(R)) vanishes on every point of (R), so its support is contained in (F). When (|F|<2^{n-d}), that support is too small for a nonzero Reed–Muller word. Hence the vanishing space is zero, and the degree-(d) hull is the whole cube.
Tightness is supplied by the minimum-weight Reed–Muller words, which are indicators of affine subspaces of codimension (d). The clause cases were checked exhaustively for widths 1–8, with verification scripts and output certificates available in this paper's downloadable evidence pack.
Discussion
MF-089 is PROVED, and its page verdict is SHOW. The theorem applies under the strict inequality (|F|<2^{n-d}). The threshold is tight, so the register does not support extending the same conclusion across the equality case without further information.
The clause consequence is intentionally limited. A single false tuple is invisible to the static quadratic hull for every width (k\ge 3), while widths 1 and 2 are closed by their degree-at-most-2 falsifier indicators. The global semantic hull answers whether low-degree equations separate points from the full relation. Root unit propagation answers what a local clause rule can force after a partial assignment. The register states that these operations are incomparable.
The minimum-distance ingredient is classical Reed–Muller theory. The register records no novelty claim for that ingredient. The exhaustive width-1–8 checker is a confirmation of the listed clause cases; the general sparse-forbidden statement comes from the Reed–Muller argument.
For everyone — the takeaway
What this means
Equations whose terms multiply at most (d) variables have limited reach. If a Boolean system leaves only a small number of forbidden assignments, every such test can miss all of them. The system then looks like the full cube to that family of tests. A clause with three or more variables is the clearest example: one assignment is forbidden, yet the static quadratic hull, the set of assignments surviving every two-variable test, cannot see it. A SAT solver, a program that searches for satisfying assignments, can still force a final variable when the other literals are fixed. MF-089 explains why those two observations do not conflict. One is a global algebraic view of all assignments; the other is a local rule applied during solving. The result marks the exact point where the static test loses information.
Attribution and prior art
Prior art: This step relies on standard minimum-distance properties of classical Reed-Muller codes; no original contribution or novelty is claimed.
Register references
MF-089.
Receipt artifacts: 07-quadratic-hull-proof-complexity/REPORT.md §7.1, §7.4, quadratic_hull_preprocessor.py, SAT-HULL-CERTIFICATE.json, SAT_preprocessor_certificate.json, NOTES-SAT.md.
Prior-art position: the register records the Reed–Muller minimum-distance ingredient as classical. The register does not record a novelty claim or a separate prior-art work.
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 5 of 5 receipt files bundled (41 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.