Distinct witness monomials prevent formal cancellation
On this page · Permalink · Source line 589
Over a characteristic-two field, define
The \(z_i\) are formal indeterminates, not Boolean variables. Different witnesses produce different monomials, so \(P_R=0\) exactly when there is no accepting witness.
Here
The ordinary unweighted characteristic-two sum of the four accepts is zero. The formal polynomial avoids this cancellation by retaining witness labels as monomial supports.
Nonzero as a formal polynomial does not mean nonzero at every field point. For instance, this example vanishes whenever \(z_1=z_2\) or \(z_3=1\). Random evaluation is governed by a root bound, not by the formal identity alone. Evaluating the polynomial efficiently remains a separate task.
Exact support fixture; general no-cancellation argument is written. The source finite evaluator retains \(2^m\) coefficients.