Research · Papers · The quadratic hull and its defects · MF-088
Exact multilinear separator degree of the Boolean AND graph
For R_r = Graph(w = x₁...x_r) and a_r = (1^r, 0), σ_{R_r}(a_r) = r, and a_r ∈ H_d(R_r) if and only if d < r
Published 2026-08-29
For everyone
Plain summary
Take an AND rule with r inputs. The rule outputs 1 only when every input bit is 1. Its honest graph lists all valid input-output combinations. The point with all 1s on input and 0 on output is wrong because those inputs require an output of 1. A separator is a polynomial test that evaluates to 0 on every honest point and 1 at this wrong point.
The minimum degree of a multilinear separator for this point is exactly r. This result generalizes MF-012. It carries a CAVEAT tag because separating points algebraically in fixed coordinates is a semantic property, not an automatic proof-system lower bound. Under a purely quadratic presentation, the wrong point is an actual model, so no refutation exists at any degree. Under the direct graph equation, both Polynomial Calculus and Nullstellensatz require degree r. Under the standard multiplication chain, both systems refute the point at degree 2.
Result
For the Boolean AND graph R_r = Graph(w = x_1...x_r) and the positive wrong point a_r = (1^r, 0), the exact multilinear separator degree is σ_{R_r}(a_r) = r.
Writing any multilinear separator as q(x, w) = q_0(x) + w q_1(x) with q vanishing on R_r and q(a_r) = 1, the honest points force q_0(x) = 0 for every x ≠ 1^r because w = 0 on those points. At x = 1^r, the condition q(a_r) = 1 forces q_0(1^r) = 1. The component q_0 is therefore the singleton indicator of 1^r. Its unique algebraic normal form is the monomial x_1...x_r of degree r, which matches the upper bound given by the product itself.
Thus, a_r ∈ H_d(R_r) if and only if d < r. The AND_3 positive-pinning result is the instance r = 3, d = 2.
Proof-complexity bounds do not follow directly from this semantic obstruction. Under a sound quadratic-only presentation, a_r satisfies all constraints and no refutation exists at any degree. With the direct pinned graph axiom, the exact refutation degree in both Polynomial Calculus and Nullstellensatz is r. With the standard multiplication-chain extension, both proof systems have exact refutation degree 2.
Setting and definitions
Variables x_1, ..., x_r, w take values in F_2. The relation R_r is the graph of the r-bit Boolean AND function. The point a_r has input coordinates 1^r and output coordinate 0.
A multilinear separator for a_r against R_r is a multilinear polynomial that vanishes on R_r and evaluates to 1 at a_r. The minimum degree of such a polynomial is σ_{R_r}(a_r). The degree-d hull H_d(R_r) contains all points that cannot be eliminated by any multilinear separator of degree at most d.
Positive pinning sets the input coordinates to 1 and the output to 0. The direct pinned graph axiom and the standard multiplication-chain extension represent two distinct algebraic encodings of this relation. The proof systems evaluated are Polynomial Calculus and Nullstellensatz.
Method
The separator degree was proved by decomposing an arbitrary multilinear separator into q(x, w) = q_0(x) + w q_1(x). Vanishing on R_r together with evaluation at a_r forces q_0 to match the singleton indicator for 1^r, whose algebraic normal form has degree r.
The proof-complexity degrees were verified against exact-degree certificates, whose full derivations and computational verification are provided in this paper's downloadable evidence pack.
Discussion
MF-088 is PROVED and generalises MF-012. The CAVEAT tag marks the boundary between coordinate-fixed semantic separators and proof-complexity lower bounds: σ_{R_r}(a_r) = r characterizes low-degree separating polynomials in fixed coordinates, but does not yield degree-2 lower bounds for Polynomial Calculus or Nullstellensatz.
Proof complexity depends on the algebraic encoding:
- In the quadratic-only presentation, a_r is a satisfying assignment, so no refutation exists at any degree.
- In the direct pinned graph presentation, the exact refutation degree is r.
- In the standard multiplication-chain presentation, intermediate variables allow refutations at degree 2.
These distinct behaviors cannot be collapsed into a single proof-system degree claim. The register records this entry as a generalization of MF-012 without external prior-art comparisons.
For everyone — the takeaway
What this means
When an r-input AND gate receives all 1s, outputting 0 is an error. Distinguishing this error from all correct input-output pairs with a single multilinear equation requires multiplying all r inputs together.
Proving that this bad point cannot occur is a different problem whose difficulty depends on how the gate is written down. If written as a single high-degree equation, the proof needs degree r. If broken into a chain of two-input multiplications, the proof needs only degree 2. The semantic separator degree does not dictate the proof degree.
Attribution and prior art
Prior art: This result generalizes MF-012; no external prior-art comparison is stated.
Register references
MF-088.
Receipt artifacts: 07-quadratic-hull-proof-complexity/REPORT.md §4–§5 (Theorems 4.1, 4.2, 5.1), PC_exact_certificate.py, PC_exact_certificate.json, NOTES-PC.md.
Prior-art position: generalises MF-012. No external prior-art comparison is recorded in the register.
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 4 of 4 receipt files bundled (27 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.