15.4 Monotone specialization
On this page · Permalink · Source line 238
Theorem 15.6: Safe monomial ideal for a monotone function
If \(f\) is monotone, \(I_f\) has a monomial basis indexed by the positive supports of \(f\). For each positive \(v\),
Consequently, for nonzero \(f\),
Proof
For any Boolean polynomial \(h\), its coefficient on \(x^S\) is
over \({\mathbb F_2}\). If \(S\) is negative for monotone \(f\), every subset \(T\) is negative. A safe \(h\) vanishes at each \(1_T\), so its \(x^S\) coefficient is zero. Conversely, a monomial on a positive support is safe by monotonicity. This proves the basis assertion.
If a safe \(h\) satisfies \(h(v)=1\), at least one of its nonzero monomials is supported inside \({\operatorname{supp}}(v)\). That support is positive and has size at most \(\deg h\). Conversely, a smallest such positive-support monomial detects \(v\). This proves the pointwise formula. Taking the appropriate minima and maxima gives the minterm statements: a minimal positive support cannot contain a smaller positive one, and every positive input contains a minterm.
Corollary 15.7: Exact monomial oracle cost
For \(k\ge2\),
Proof
The unique positive input of the \(k\)-variable monomial needs a safe polynomial of degree \(k\). The complete-cover lower bound gives \(2k-3\). For the matching construction, successively compute \(x_1x_2\), then \(x_1x_2x_3\), and so on up to a \((k-1)\)-fold product on clean work wires. Toggle the output using that product and \(x_k\), then uncompute the \(k-2\) work products. The count is \((k-2)+1+(k-2)=2k-3\). For \(k=2\), a single Toffoli suffices.