A short expression inside a trace is not a computed trace
On this page · Permalink · Source line 616
Let \(\tau_w\) extract the top multilinear coefficient in the Boolean witness ring. For any \(G(w)\) over a characteristic-two field,
A proper-support monomial evaluates to one an even number of times; the full-support monomial does so once. This proves the identity directly.
Applying it to a weighted expression gives
At \(w_i=0\), a multiplier equals one. At \(w_i=1\), it equals \(z_i\). Summing evaluations therefore produces exactly the witness monomials. For the preceding verifier, the four surviving products are \(z_1,z_2,z_1z_3,z_2z_3\).
The circuit expression inside the trace adds only \(O(m)\) operations to the verifier. That observation bounds the expression's construction, not the cost of applying \(\tau_w\). The finite checker computes with a complete table of \(2^m\) witness coefficients.
| Established | Not supplied by the expression |
|---|---|
| Small weighted circuit inside \(\tau\) | A polynomial-time evaluator for the trace |
| Formal polynomial detects nonemptiness | A deterministic identity test from one evaluation |
| Exact finite table algorithm | Polynomial storage in the witness length |
At \(m=0\), the empty product is one, the top coefficient is the constant itself, and there is a single empty witness. The definitions remain valid.