1
$\begingroup$

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}$?

$\endgroup$
  • 2
    $\begingroup$ Just a guess: Perhaps $x \cdot y$ is even just as often as it is odd. $\endgroup$ – Ethan Bolker May 21 at 16:49
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ So call these pairs $x, x'$. Then one of $x \cdot y, x' \cdot y$ is even and the other is odd. Where do I go from here? I can intuitively see now that the sum is zero, but how do I show it rigorously? $\endgroup$ – the man May 21 at 16:57
  • $\begingroup$ @theman There are $2^{n-1}$ pairs, so the sum consists of $2^{n-1}$ many $+1$'s and $2^{n-1}$ many $-1$'s. Alternatively, if you (pretend to) write out the sum explicitly, then swapping every $x$ with its pair-mate changes the sign of each term. So the entire sum has changed sign. But exactly the same terms are included, so the sum must at the same time be unchanged. $\endgroup$ – Arthur May 21 at 18:59
1
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.