The sum of a polynomial over a boolean affine subcube

Question

Let $P:\mathbb{Z}_2^n\to\mathbb{Z}_2$ be a polynomial of degree $k$ over the boolean cube. An affine subcube inside $\mathbb{Z}_2^n$ is defined by a basis of $k+1$ linearly independent vectors and an offset in $\mathbb{Z}_2^n$.

[See "Testing Low-Degree Polynomials over GF(2)" by Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.9.1235 - for more details]

Why does taking such a subcube and evaluating the sum of $P$ on all $2^{k+1}$ elements of it, always results in zero ?

Answer 1

Let the coordinates be $z_1,z_2,\ldots,z_n$. It suffices to do the case, when $P$ is a monomial, say $P=z_{i_1}z_{i_2}\cdots z_{i_k}$. Let's use induction on $k$.

If $k=0$, then $P=1$, and the claim is clear.

In the general case let us consider the coordinates $z_{i_j},1\le j\le k$. If all these take only a single value on the affine subcube, then the restriction of $P$ to the subcube is a constant, and the claim holds. On the other hand, if one of these coordinates, say $z_{i_m}$, takes both values within the subcube, then $P$ obviously vanishes identically in the zero-set of $z_{i_m}=0$, so we need to worry about the restriction of $P$ to the affine hyperplane $H_m$ determined by the equation $z_{i_m}=1$. The intersection of the subcube and $H_m$ will be another affine subcube of dimension one less, i.e. at most $k$. Fortunately also the restriction of $P$ to that smaller cube coincides with that of the monomial $P/z_{i_m}$ of degree $k-1$. Therefore the induction hypothesis applies, and we are done.

[Edit:] The logic of the inductive step was a bit unclear in the first version. I think that it is clearer to first restrict to a smaller cube, and then observe that the degree also goes down. Not the other way around. [/Edit]

Remark: In coding theory this is a standard duality property of the so called Reed-Muller codes. The polynomial $P$, when evaluated at all the points of $\mathbf{Z}_2^n$, gives a word of the code $RM(k,n)$. The characteristic function of the affine hypercube is of degree $n-k-1$, and is thus a word of the dual code $RM(n-k-1,n)$ that is also known to be equal to the dual: $RM(n-k-1,n)=RM(k,n)^\perp$. The duality means that these two functions both take value $=1$ at an even number of points, and the claim follows.

Answer 2

The key idea in proving this is restricting a polynomial to an affine subcube. Let $S$ be the subcube $$ S := \{ z_1 \mathbf v_1 + z_2 \mathbf v_2 + \cdots + z_{k+1} \mathbf v_{k+1} + \mathbf v_0 \,:\, z_i \in \{ 0, 1 \} \text{ for } 1 \leq i \leq k+1 \} $$ for some fixed vectors $\mathbf v_1, \ldots, \mathbf v_{k+1}$ and $\mathbf v_0$. The restriction of $P$ to $S$ is then defined to be the polynomial $Q : \mathbb Z_2^{k+1} \to \mathbb Z_2$ obtained by formally plugging in $z_1 \mathbf v_1 + z_2 \mathbf v_2 + \cdots + z_{k+1} \mathbf v_{k+1} + \mathbf v_0$ for $\mathbf x$ in $P(\mathbf x)$. That is, $$ Q(\mathbf z) = P(z_1 \mathbf v_1 + z_2 \mathbf v_2 + \cdots + z_{k+1} \mathbf v_{k+1} + \mathbf v_0), \tag{1} $$ for all $\mathbf z = (z_1, z_2, \ldots, z_{k+1}) \in \mathbb Z_2^{k+1}$.

Restrictions are useful because they preserve the degree of the polynomial:

Proposition. If $P$ has degree at most $k$, then so does its restriction $Q$.

(The proof is simply to expand out $P$ in terms of the indeterminates $z_i$'s, keeping in mind that the $v_i$'s are fixed vectors. Complete the proof as an exercise!)

Now, the sum $\sum_{\mathbf x \in S} P(\mathbf x)$ is the same as the sum $\sum_{\mathbf z \in \mathbb Z_2^{k+1}} Q(\mathbf z)$ where $Q$ is defined as in $(1)$; so it is enough to prove that the latter sum is $0$.

Lemma. If $Q : \mathbb Z_2^{k+1} \to \mathbb Z_2$ is a polynomial of degree at most $k$, then $$\sum_{\mathbf z \in \mathbb Z_2^{k+1}} Q(\mathbf z) = 0 .$$

First of all, we can assume that the polynomial $Q$ is multilinear without loss of generality. Then since any multilinear polynomial is a linear combination of the basis polynomials $z_T := \prod\limits_{i \in T} z_i$ (where $T \subseteq [n]$), it suffices to prove the lemma for these basis polynomials. The proof is quite easy for the polynomials of the form $z_T$. I recommend that you try it; I will supply hints if you are stuck.

Answer 3

Let $f(x_1, \ldots, x_n)$ be a binary-valued polynomial in $n$ binary variables, and consider the $2^n$-bit vector $$[f(0,\ldots, 0, 0), f(0, \ldots, 0, 1), f(0, \ldots, 1, 0), \ldots, f(1, \ldots, 1)]$$ obtained by evaluating $f$ at the $2^n$ vertices of the hypercube. Does this vector (equivalently the function $f$) have even Hamming weight or odd Hamming weight? To answer this question, let us expand out $f$ into a sum of minterms by multiplying each monomial by $(x_i + \bar{x}_i)$ for each variable $x_i$ missing in the monomial. That is, with $n = 4$. say, $x_1x_3$ is expressed as $x_1(x_2+\bar{x}_2) x_3(x_4 + \bar{x}_4)$ and multiplied out to express it as the sum of $4$ minterms. Each monomial except $x_1x_2\cdots x_n$ will expand out into an even number of minterms, and thus we have that $f$ has odd Hamming weight if and only if it is of degree $n$ (and therefore contains $x_1x_2\cdots x_n$). Note that $f$ need not contain the minterm $x_1x_2\cdots x_n$:
$$f = \bar{x}_1x_2\cdots x_n = x_1\cdots x_n + x_2\cdots x_n$$ is of odd weight $1$, has only one minterm (which is not $x_1x_2\cdots x_n$) and is of degree $n$

So, if $f$ is a polynomial of degree $k$ in $n$ variables and $g$ is of degree at most $n-k-1$, then the polynomial $fg$ cannot contain $x_1x_2\cdots x_n$ and must have even weight. Equivalently, the corresponding $2^n$-bit vectors have inner product $0$, or $f$ and $g$ are orthogonal polynomials, which leads to the notion of duality of Reed-Muller codes. Finally, if $n = 4$, say, and $f$ is known to be of degree $2$ or less, how can one tell if $f$ contains the term $x_1x_3$? Well, we test the weight of $x_2x_4f$. If $x_2x_4f$ is of degree $n$, then the weight is odd. But if $x_2x_4f$ is of degree $n$ then $f$ must have the term $x_1x_3$ in it. On the other hand, if the weight of $x_2x_4f$ is even, then $f$ does not contain $x_1x_3$. Note that evaluating $x_2x_4f$ at $16$ points can be simplified to evaluating $f$ at the four points specified by $x_2 = 1, x_4 = 1$, i.e. an affine subcube. We could also evaluate $f$ at the four points specified by $x_2 = 1, x_4 = 0$ which corresponds to testing the Hamming weight of $x_2\bar{x}_4f$, and so on. Thus, if $f$ is of degree $k$ in $n$ variables, then it is orthogonal to all polynomials of degree at most $n-k-1$, and since a $n - (n - k - 1) = (k+1)$-dimensional affine subcube corresponds to a polynomial of degree $n-k-1$, $f$ has even weight on any $(k+1)$-dimensional affine subcube. that is, the sum of its values on the subcube is $0$.