A degree-one dual certificate for two-input AND
On this page · Permalink · Source line 328
Let \(f(a,b)=ab\), with unique positive point \((1,1)\). For degree at most one, the evaluation vector is \(v_1(a,b)=(1,a,b)\). The three negative points already span the positive vector.
Any affine polynomial is a coefficient covector \(c=(c_0,c_a,c_b)\). Safety means that it pairs to zero with each negative row. The displayed dependence therefore forces its value at \((1,1)\) to be zero. No safe affine packet detects the positive point.
The degree-two polynomial \(ab\) does detect it, so \(\beta_{11}(f)=\beta(f)=2\). Since \(\beta^*\le n=2\) and \(\beta^*\ge\beta\), \(\beta^*=2\). The complete bound gives \(T\ge1\), attained by one direct Toffoli to the target.
The constant coordinate also checks parity: this dependence uses three negative rows, an odd number. Without the constant coordinate, that parity conclusion would not follow.
Exact finite dependence plus written duality. Lean proves the corresponding AND2 degree and beta exclusions by four-corner parity, without formalizing the general evaluation-span dual.