Can we explicitly compute this "shift"-quantity over Boolean functions $u:\mathbb{F}_2^n\rightarrow \mathbb{F}_2$?

Question

This question is a follow-up of this question.

Let $\mathbb{F}_2=\{0,1\}$ be the field with two elements, and suppose that $n$ is odd.

Question: Can we compute the exact minimum $$A:= \min_{u:\mathbb{F}_2^n\rightarrow \mathbb{F}_2} \sum_{a\neq 0}\left(\sum_{x}(-1)^{u(x)+u(x+a)}\right)^2 \, \,? $$

Here is a lower bound, which I don't know if can attained (see derivation below):

$$ A \ge \max\{1,\frac{f^2(n)}{2^n-1}\}, $$ where $$ f(n):=\min \{\,\, |k| \,\,\, | \,\,\, k+2^n \,\,\,\text{is a square of an integer}\}. $$

Motivation: This question arose while I was trying to derive a lower bound on the approximate multiplicativity of Boolean functions.

---

Lower bound derivation:

Set $s(x,a)=(-1)^{u(x)+u(x+a)}$, $g(a):=\sum_xs(x,a)$, $r=\sum_{a \neq 0} g(a)$.

Since $g(0)=2^n$, $$ \tag{1} \mathbb{E}_{\mathbf{x},\mathbf{a}}[s(x,a)]=\frac{1}{2^{2n}}\sum_a g(a)=\frac{2^n+r}{2^{2n}}. $$

Now, we also have \begin{equation*} \tag{2} \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})}]=\mathbb{E}_{\mathbf{x},\mathbf{a}}[s(x,a)], \end{equation*}

$\mathbb{E}_{\mathbf{x}}[(-1)^{u(\mathbf{x})}]$ is an integer multiple of $1/2^n$, so we may write $\mathbb{E}_{\mathbf{x}}[(-1)^{u(\mathbf{x})}]=\frac{m}{2^n}$.

Combining this with equations $(1),(2)$, we get $$ \frac{2^n+r}{2^{2n}}=\frac{m^2}{2^{2n}}, $$ or $$ 2^n+r=m^2. $$ Thus $|r| \ge f(n)$, by the definition of $f$.

Now using Cauchy-Schwartz: $$ f(n) \le |r| = |\sum_{a \neq 0} g(a)| \le \sum_{a \neq 0} |g(a)| \le \sqrt{\sum_{a \neq 0} g^2(a)}\sqrt{2^n-1}. $$

---

Equality happens when all the $g(a)=t \in \mathbb{Z}$, and so $$ f(n)=|r|=|\sum_{a \neq 0} g(a)|=(2^n-1)|t|$$

Since $f(n) \le 2^n$, this implies $$ (2^n-1)|t| \le 2^n, $$ so $|t|=1$. Is it possible that indeed $|g(a)|=1$ for every $a \neq 0$?

Answer 1

Too long for a comment:

A function $u:\mathbb{F}_q^n\rightarrow \mathbb{F}_q^n$ is perfect nonlinear if the derivative $$ D_au(x)=u(x+a)-u(x) $$ takes on each value in $\mathbb{F}_q^m$ equally often for any $a\neq 0,$ as $x$ ranges over the domain. Note that here $n$ is odd, $q=2,$ and $m=1.$ In which case we have $$ D_au(x)=u(x+a)+u(x) $$

Fix $a,$ and note that for each $x,$ $D_a(x)=D_a(x+a)$ in even characteristic. So we cannot have PN (Perfect Nonlinear) mappings here, but only so called almost PN (APN) mappings [which are 2-to-1].

A natural technique to obtain a function $u:\mathbb{F}_q^n\rightarrow \mathbb{F}_q$ is to use the absolute trace.

Under this approach, a number of monomial power permutations have been shown to be APN and their composition with the absolute trace have also been used.

For example, for $q=2,$ the Gold exponent over $\mathbb{F}_{2^n}$ is defined as $$ x\mapsto x^{2^k+1} $$ with $\gcd(2^k+1,n)=1,$ and $n$ odd. So take $u=tr(x^{2^k+1})$ and fix some basis to view $\mathbb{F}_{2^n}$ as $\mathbb{F}_2^n,$ then it turns out that $$ u(x+a)+u(x) $$ is balanced for all $a \in \mathbb{F}_2^n\setminus \mathbb{F}_2.$ this will yield $$ \sum_{a\neq 0}\left(\sum_{x}(-1)^{u(x)+u(x+a)}\right)^2= \left(\sum_{x}(-1)^{u(x)+u(x+1)}\right)^2=2^{2n}. $$ So your minimum is upperbounded by this quantity. I don't know of any other examples which give a lower minimum. Perhaps you can do a search and see for small $n$.