Sum over the field $\mathbb{F}_{2}^{n}$

Question

Consider the binary field $\mathbb{F}_2$ and then consider $n$ direct products of this: $\mathbb{F}_2 \times \mathbb{F}_2 \times \cdots \times \mathbb{F}_{2}$.

Hence, $\mathbb{F}_{2}^{n} = {\{x = (x_1,\ldots,x_n) : x_i \in \mathbb{F}_{2}}\}$, so it's just the set of vectors with entries $0$ and $1$.

Define $x \cdot y = x_1 y_1 + \ldots + x_n y_n$.

Now, let $y \in \mathbb{F}_{2}^{n}$.

I am trying to find out what the following sum is: $$\sum_{x \in \mathbb{F}_{2}^{n}} (-1)^{x \cdot y}.$$

When $y$ is the zero vector, the sum is equal to $2^n$ clearly. But, what about an arbitrary vector $y \in \mathbb{F}_{2}^{n}$?

Answer 1

Hint: Let $y\neq 0$ have a non-zero entry at index $k$. Now divide $\Bbb F_2^n$ into pairs of vectors which only differ at index $k$.

Answer 2

Since $y$ is nonzero, the operation $x \mapsto x \cdot y$ defines a nonzero linear functional, which we will call $f$. These always have a kernel of codimension 1. That is, there is a linear subspace $\ker f \subset \mathbb F^n_2$, and a vector $b \in \mathbb F^n_2$ with $f(b) \neq 0$, such that every vector $x \in \mathbb F^n_2$ can be uniquely represented as $a + \lambda b$, for some $a \in \ker f$ and $\lambda \in \mathbb F_2$.

Now, in our case $\lambda$ can be $0$ or $1$, so the space $\mathbb F^n_2$ decomposes into a union of $\ker f$ and $\ker f + b$. For $x \in \ker f$ we have $(-1)^{x\cdot y} = (-1)^f(x) = (-1)^0 = 1$, while for $x \in \ker f + b$ we have $(-1)^{x \cdot y} = (-1)^1 = -1$.

Answer 3

Let there be $k$ ones in $y$. Each assignment of zeros and ones to the corresponding $k$ entries in $x$ can be completed into $2^{n-k}$ vectors in $\mathbb F_2^n$, so the sum becomes $2^{n-k}\sum_{x\in\mathbb F_2^k}(-1)^{\operatorname{HW}(x)}$, where $\operatorname{HW}(x)$ is the Hamming weight. This second sigma is easily shown by the binomial theorem to be $0^k$, which is $0$ for $k>0$ but $1$ for $k=0$. Therefore the original sum is $0$ whenever $y$ is non-zero.