Affine output adjustment is an actual circuit
On this page · Permalink · Source line 156
THE OPTIMIZATION DOES NOT ASSUME A CLEAN NORMAL FORM For every degree-one Boolean function \(g\), the source constructs a restored implementation with zero Toffolis.
A constant is computed by the empty circuit or target NOT. An input variable uses a legal input-to-target CNOT. XOR is implemented by concatenating restored circuits. Induction on a degree-one certificate gives the general construction.
If \(c\) restores \(f\) and \(d\) restores \(g\), their concatenation restores \(f{\mathbin{\oplus}} g\). For the affine implementation,
The unoptimized bound applies to every affine \(g\) at the same \(T\). Define \(\beta^*(f)\) as the least upper bound of those \(\beta(f{\mathbin{\oplus}} g)\) values. Existence follows from their common upper bound \(n\).
Therefore
The final output at initial target zero is exactly \(f\), so the forward coordinate theorem also gives \({\operatorname{DegreeLE}}(T+1,f)\). The joint endpoint combines these two proved conclusions.
Nonvacuity: two-input AND
On this page · Permalink · Source line 173
Every degree-one function on two inputs has zero XOR over the four corners of the input square. AND has corner XOR one. Thus AND has no degree-one certificate.
A degree-one complete safe cover for AND would include a detector of its sole accepting input. Safety forces that detector to be AND itself, contradicting the corner-parity lemma. The degree-two monomial is a valid detector. The source proves
and therefore every restored implementation of AND\(_2\) uses at least one Toffoli.
This is a theorem about all implementations in the model, not an exhaustive search through circuits. It does not formalize the general \(k\)-input monomial optimum.