The sum of a polynomial over a boolean affine subcube 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 ?

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.
