Why can't individual terms of a summation not cancel each other in the 2nd case?

89 Views Asked by At

Below is from a paper.

$F(.)$ is a low-degree multivariate polynomial over $\mathbb F$ in $s$ variables.

Checking if $\sum_{x \in \lbrace0,1\rbrace^s} F(x) = 0$ will not prove that that $F(x) = 0\space\forall x \in \lbrace 0,1\rbrace^s$ - This is because the $2^s$ terms in the sum might cancel each other making the final sum zero even when some of the individual terms are not zero. I understood this.

So the following procedure is used.

$Q(t) = \sum_{x \in \lbrace0,1\rbrace^s} F(x)\cdot eq(t,x)$

where

$eq(t,s) = 1$ when $t=x$ and

$eq(t,s) = 0$ when $t\ne x$

From this, $Q(t) = F(t) \forall t \in \lbrace 0, 1\rbrace^s$ - I understood this.

However, after this, the author writes

Thus, $Q(·)$ is a zero-polynomial (i.e., it evaluates to zero for all points in its domain) if and only if $F(·)$ evaluates to zero at all points in the s-dimensional Boolean hypercube.

I don't understand the above - why won't the point about the individual terms in the $\sum$ being non-zero but still cancelling each other to make the left hand side zero not hold here?

1

There are 1 best solutions below

0
On BEST ANSWER

You've proved that $Q(t) = F(t)$ for all $t$, which means $Q$ and $F$ evaluate the same for all $t$. So $F$ evaluates to 0 everywhere iff $Q$ evaluates to 0 everywhere.

You can't get cancellation in the summation for $Q$ because for any given $t$, all the terms in the sum for $x \ne t$ are already 0, since $eq(x,t)=0$. So there is only one term left, the term $x=t$, and it equals $F(t) eq(t,t) = F(t)$. Therefore if $Q(t)=0$, then $F(t) = 0$ as well. No cancellation of the type you are describing is possible. To have cancellation, you need at least 2 non-zero terms, like $1 + (-1) = 0$.