Let $\mathbb{F}\_2=\{0,1\}$ be the field with two elements, and let
$u:\mathbb{F}\_2^n\rightarrow \mathbb{F}\_2$. *Suppose that $n$ is odd.*



> 
> Is it possible that
> $$
> \sum\_{x \in \mathbb{F}\_2^n}(-1)^{u(x)+u(x+a)}= 0,
> $$
> for every $a \neq 0$ in $\mathbb{F}\_2^n$?
> 
> 
> 


I treat the sum here as natural number, not as an element of $\mathbb{F}\_2$.




---


This question arose in the context of [this question](https://math.stackexchange.com/questions/4395191/every-boolean-function-is-multiplicative-with-probability-greater-than-1-2). (Trying to derive a lower bound on the approximate multiplicativity of a Boolean function). When $n$ is even [there are](https://math.stackexchange.com/a/4396116/104576) such functions; this is related to [Bent functions](https://en.wikipedia.org/wiki/Bent_function).



Are there functions $\mathbb{F}_2^n \to \mathbb{F}_2$ satisfying these special relations?
I think the answer is no. To see this, observe that
\begin{equation\*}
\left(\mathbb{E}\_{\mathbf{x}}[(-1)^{u(\mathbf{x})}]\right)^2=\mathbb{E}\_{\mathbf{x}}[(-1)^{u(\mathbf{x})}]\mathbb{E}\_{\mathbf{y}}[(-1)^{u(\mathbf{y})}]=\mathbb{E}\_{\mathbf{x},\mathbf{y}}[(-1)^{u(\mathbf{x})+u(\mathbf{y})}]=\mathbb{E}\_{\mathbf{x},\mathbf{a}}[(-1)^{u(\mathbf{x})+u(\mathbf{x}+\mathbf{a})}],
\end{equation\*}
where we use independence and then rewriting $\mathbf{y}=\mathbf{x}+\mathbf{a}$, and where all expectations are uniform over $\mathbb{F}\_2^n$. The assumption then is that for $\mathbf{a}=\mathbf{0}$, the expectation over $\mathbf{x}$ is clearly $1$, while for all other values of $\mathbf{a}$, the expectation over $\mathbf{x}$ is $0$. It follows that
\begin{equation\*}
\left(\mathbb{E}\_{\mathbf{x}}[(-1)^{u(\mathbf{x})}]\right)^2 = \frac{1}{2^n}\iff \mathbb{E}\_{\mathbf{x}}[(-1)^{u(\mathbf{x})}] = \frac{\pm 1}{2^{n/2}}
\end{equation\*}
However, it's not hard to see that this expectation must also be an integer multiple of $1/2^n$. But then this integer must be $\pm 2^{n/2}$, but this is integral if and only if $n$ is even.


