Can we explicitly compute this "shift"-quantity over Boolean functions $u:\mathbb{F}_2^n\rightarrow \mathbb{F}_2$? 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$?
 A: 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$.
