19.2 Exact top-coefficient extraction
On this page · Permalink · Source line 568
Lemma 19.2: Top coefficient as a Boolean-cube sum
Let \(G(w)\) be a multilinear polynomial over a characteristic-two field. Then
Proof
It is enough to check a monomial. A monomial of proper support is one on an even number \(2^{m-|S|}\) of Boolean inputs, so its cube sum is zero in characteristic two. The full-support monomial is one at exactly one input and has cube sum one. Linearity gives the identity.
Theorem 19.3: Weighted top-coefficient identity
Let \({\operatorname{Top}}_w\) extract the coefficient of \(w_1\cdots w_m\) after reduction in the Boolean \(w\) algebra. Then
Proof
At \(w_i=0\), the \(i\)th factor is one. At \(w_i=1\), it is \(z_i\). Lemma 19.2 therefore converts the right side to exactly the weighted sum defining \(P_R\).
The expression inside \({\operatorname{Top}}_w\) has a circuit with \(O(|R|+m)\) operations when the verifier has circuit size \(|R|\). The cost of applying \({\operatorname{Top}}_w\) to that succinct expression is not bounded by writing down the operator. The source evaluator explicitly stores \(2^m\) coefficients and remains exponential in witness length.