Calibration families and exact small oracles

Proof

The minterms have supports \(\{a,b\}\) and \(\{z_1,\ldots,z_k\}\). The first two assertions follow from Theorem 15.6. The monomial \(abB\) has degree \(k+2\) and does not cancel with either lower-degree term in the displayed polynomial.

Back to statement · Permalink · Source line 286

Proof

First restrict to the face \(z_1=0\). There \(F_k+\ell\) becomes \(ab+\ell|_{z_1=0}\), a nonzero quadratic. If the restricted affine term contains a remaining \(z\) variable, set \(a=0\) and set the remaining affine form to one. This gives an accepting affine subspace of codimension at most two inside the face. If it contains no remaining \(z\) variable, fix \(a,b\) to an accepting pair instead. The indicator of the resulting affine subspace in the full input space has degree at most three and is safe. Thus every affine adjustment has a nonzero safe polynomial of degree at most three.

For equality, take \(\ell=a\). The degree-three polynomial

is safe for \(G_k\). Suppose a safe \(h\) of degree at most two existed. On \(a=0\), acceptance requires \(B=1\). For \(k\ge3\), the monotone-ideal argument forces \(h|_{a=0}=0\), hence \(h=aL\) with \(L\) affine in the remaining variables. The negative face \(a=b=1\) forces \(L(1,z)=0\), so \(L=c(1+b)\). The negative point \(a=1,b=0,z=(1,\ldots,1)\) then forces \(c=0\).

When \(k=2\), the restriction can initially be \(h|_{a=0}=cB\). Write \(h=cB+aL\). On the same negative face \(a=b=1\), the quadratic term \(cB\) cannot be cancelled by affine \(L\), so \(c=0\). The previous argument then applies. There is no nonzero safe polynomial of degree at most two, proving equality.

Back to statement · Permalink · Source line 296

Proof

Restrict \(G_k=F_k+a\) to \(b=1\). Then

This is the indicator of one point on \(k+1\) variables. At the positive input \(a=0,b=1,z=(1,\ldots,1)\), a safe detecting polynomial must restrict to that singleton indicator and therefore have degree at least \(k+1\). Thus \(\beta(G_k)\ge k+1\).

For the upper bound, Theorem 16.2 shows that no \(F_k+\ell\) is a singleton indicator: a singleton would have one-packet degree \(n=k+2>3\). These functions are also nonzero because \(F_k\) is not affine. Each has at least two positive inputs, so Proposition 15.1 gives \(\beta(F_k+\ell)\le n-1=k+1\).

Back to statement · Permalink · Source line 314

Proof

The lower bound follows from Theorems 15.3 and 16.3. For the upper bound, compute \(A=ab\) with one multiplication and \(B\) using \(k-1\) multiplications. Toggle the output by \(A+B+AB\), requiring one output Toffoli and affine additions. Uncompute \(A\) and \(B\). The total Toffoli count is \(k+1+k=2k+1=2n-3\).

Back to statement · Permalink · Source line 330