Maximize function over $n$-bit strings Consider
$$\max_{\phi:\left\{ 0,1\right\} ^{n}\to\left[-1,1\right]}\sum_{x,y\in\left\{ 0,1\right\} ^{n}}\phi\left(x\right)\phi\left(y\right)\left[1-\frac{2\left|x-y\right|}{n}\right]$$
where $\left|x-y\right|$ denotes the Hamming distance of the two $n$-bit strings $x,y\in\left\{ 0,1\right\} ^{n}$ and $\phi$  is a function on $n$-bit strings $x\in \left\{ 0,1\right\} ^{n}$. The sum is over the $4^n$ ordered pairs $(x,y)$.
I am looking for an (asymptotic) lower bound for this expression in terms of $n$ (or of course, if possible, for an exact expression).
A trivial lower bound is 1 by choosing $\phi(x)$ to be non-zero only on a single bitstring, for example
$$\phi\left(x\right)=\begin{cases}
1 & x=0\dots0\\
0 & else
\end{cases}
$$
 A: Let $\phi(x) = (-1)^{x_0}$; that is, $\phi(x) = 1$ if the first entry of $x$ is $0$ and $\phi(x) = -1$ if the first entry of $x$ is $1$.  The idea is that if $x$ and $y$ are close to each other in Hamming distance then they are more likely to have the first digit equal, and hence have the same sign assigned by $\phi$.
We have
\begin{align*}\sum_{x,y\in\left\{ 0,1\right\} ^{n}}\phi\left(x\right)\phi\left(y\right)\left[1-\frac{2\left|x-y\right|}{n}\right]&= \sum_{k=0}^n\left[1-\frac{2k}{n}\right]\sum_{x,y\in\left\{ 0,1\right\} ^{n}, |x-y| = k}\phi\left(x\right)\phi\left(y\right).\end{align*}
To find the inner sum, we note that if $|x-y| = k$ then we have a probability $k/n$ of having $x_0 \neq y_0$, in which case $\phi(x)\phi(y) = -1$, and a probability $1-k/n$ of having $\phi(x)\phi(y) = +1$.  Furthermore, the total number of pairs $x,y$ with $|x-y| = k$ is $${n \choose k}2^n$$ since to find pairs at Hamming distance $k$ we first choose a $k$-subset $S$ on which the pair differs and then choose any value for $x$; this information fully determines $y$.  Thus we get
\begin{align*}\sum_{x,y\in\left\{ 0,1\right\} ^{n}, |x-y| = k}\phi\left(x\right)\phi\left(y\right) &= \left(1 - \frac{k}{n}\right) {n \choose k} 2^n -  \frac{k}{n} {n \choose k} 2^n\\&= \left(1 - \frac{2k}{n}\right) {n \choose k} 2^n.\end{align*}
Thus we in total get the lower bound
\begin{align*}\sum_{k=0}^n \left(1 - \frac{2k}{n}\right)^2 {n \choose k} 2^n.\end{align*}
In particular, taking just $k=0$ and $k=n$ terms gives a lower bound of $2^{n+1}$.  (I have no idea how close this is to optimal.)
Edit: Inspired by RobPratt's observation in the comments, here's an easier way to see the lower bound $4^n/n$.
Dividing the whole sum by $4^n$ gives the expected value
$$E[\phi(x)\phi(y)(1-2k/n)]$$ where $k$ is the Hamming distance between $x,y$ are uniformly random bitstrings.
If we condition on $x_0 = y_0$, we get $\phi(x)\phi(y) = 1$, so computing the conditional expectation is equivalent to finding the expectation of $(1-2k/n)$ for $x,y$ two random $(n-1)$-length bitstrings. This is $0$. So, $$E\big[\phi(x)\phi(y)(1-2k/n)\big|x_0 = y_0\big] = 0.$$
Similarly, conditioning on $x_0 \neq y_0$ is equivalent to considering random $(n-1)$ bitstrings and adding $1$ to the Hamming distance.  Thus we get conditional expectation $$E[1-2(k+1)/n] = E[(1-2k/n)] - E[2/n] = -2/n.$$  So we have $$E\big[\phi(x)\phi(y)(1-2k/n)\big|x_0 \neq y_0\big] = 2/n.$$
Each of these events happen with probability $1/2$.  So in total the expectation is $1/n$.
