# Are there functions $\mathbb{F}_2^n \to \mathbb{F}_2$ satisfying these special relations?

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. (Trying to derive a lower bound on the approximate multiplicativity of a Boolean function). When $$n$$ is even there are such functions; this is related to Bent functions.

• @PeterMueller The OP reask their question with the additional condition that $n$ is odd. Mar 5, 2022 at 18:53

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.