Characterising functions $\mathbb{F}_2^n \to \mathbb{F}_2$ satisfying special equations

Question

Let $\mathbb{F}_2=\{0,1\}$ be the field with two elements, and let $u:\mathbb{F}_2^n\rightarrow \mathbb{F}_2$ be a function.

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

If so, can we characterise the functions satisfying property?

Comment: I treat the sum here as natural (or real) 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).

---

If $u$ is linear, i.e. $u(x+y)=u(x)+u(y)$, then the sum above is never zero.

---

Edit:

Jyrki Lahtonen gave a nice example for all even $n$. It turns out that there are no such functions for odd $n$.

Answer 1

I think the following idea I borrowed from the theory of so called bent functions (that Claude Carlet's group is actively researching) gives a construction of an example of such a function $u$. Assuming that $n$ is an even number.

---

Write $n=2k$, $V=\Bbb{F}_2^k$, and $\langle\ ,\ \rangle:V\times V\to \Bbb{F}_2$ the usual inner product. We identify $\Bbb{F}_2^n$ with $V\times V$ and use $u=\langle\ ,\ \rangle$. Let $(a,b)$ be a non.zero vector of $V\times V$. Let $(x,y)$ be an arbitrary vector. Bilinearity means that $$ \begin{aligned} u((x,y))+u((x,y)+(a,b))&=\langle x,y\rangle+\langle x+a,y+b\rangle\\ &=\langle a,y\rangle+\langle x,b\rangle+\langle a,b\rangle. \end{aligned} $$

Therefore the sum $$ \begin{aligned} \sum_{(x,y)\in\Bbb{F}_2^n}(-1)^{u((x,y))+u((x,y)+(a,b))}&= \sum_{x\in V}\sum_{y\in V}(-1)^{\langle a,y\rangle+\langle x,b\rangle+\langle a,b\rangle}\\ &=(-1)^{\langle a,b\rangle}\sum_{y\in V}(-1)^{\langle a,y\rangle}\sum_{x\in V}(-1)^{\langle x,b\rangle}. \end{aligned} $$ The assumption is that at least one of $a,b$ is non-zero. Therefore at least one of the sums that appear as factors in the final formula vanishes by the usual orthogonality of characters (see below). Hence so does the entire sum.

---

In other words, if $n=2$, use $u(x_1,x_2)=x_1x_2$. If $n=4$, use $u(x_1,x_2,x_3,x_4)=x_1x_3+x_2x_4$ et cetera.

---

Orthogonality. Assume that $a\in V$ is non-zero. Then there exists an element $\epsilon\in V$ such that $\langle a,\epsilon\rangle=1$. We fix one such. Therefore $$ \begin{aligned} S(a)&:=\sum_{x\in V}(-1)^{\langle x,a\rangle}\\ &=\sum_{x+\epsilon\in V}(-1)^{\langle x+\epsilon,a\rangle}\\ &=\sum_{x\in V}(-1)^{\langle x+\epsilon,a\rangle}&\text{because $x$ ranges over $V$ while $x+\epsilon$ does}\\ &=(-1)^{\langle\epsilon,a\rangle}\left(\sum_{x\in V}(-1)^{\langle x,a\rangle}\right)\\ &=-S(a). \end{aligned} $$ Hence $S(a)=0$ as claimed.

Answer 2

This is an area of still active research, as far as I know (errored claim regarding linear functions removed, shouldn't post after midnight).

See the fantastic survey on Boolean functions by Claude Carlet available here.

Specifically (p. 59) a function $f$ is said to satisfy the propagation criterion with respect to a set $E\subset \mathbb{F}_2^n$ if the directional derivative $$ D_a f(x)=f(x)-f(x+a) $$ is balanced for all $a\in E.$

Your question corresponds to the case $E=\mathbb{F}_2^n\setminus \{0\}.$

Update:

I am not an expert in this field but know about some of the results.

If we consider a function $$ f:\mathbb{F}_{2^n} \rightarrow \mathbb{F}_{2^n} \quad(1) $$ instead of a boolean function, such a function is called a planar function if $$ D_a f(x)=f(x)-f(x+a) $$ is a permutation of $\mathbb{F}_{2^n}$ for all nonzero $a$ in $\mathbb{F}_{2^n}.$ Note that by choosing a basis you can view $\mathbb{F}_{2^n}$ as $\mathbb{F}_2^n$ but some technical issues arise with respect to equivalence of functions.

If you have a planar function, you can compose it with, say, the trace map $$ tr:\mathbb{F}_{2^n}\rightarrow \mathbb{F}_2 $$ which is $2^{n-1}$ to $1$ and obtain a function satisfying the propagation criterion for all $a \in \mathbb{F}_{2^n}\setminus \{0\}.$ The planar functions $f$ in $(1)$ are also known as perfect nonlinear functions in cryptography which may help you find related results.

Some families of such functions exist but there is no full characterisation as far as I know. See page 79 of the Carlet chapter regarding this topic.

A relatively recent result in this topic, exhibiting monomial planar functions was given in

Schmidt and Zhou, Planar functions over fields of characteristic two Journal of Algebraic Combinatorics 40:503-526, 2014.