# 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}$$

• Is the sum over ordered pairs $(x,y)$ or sets $\{x,y\}$? Jul 30, 2021 at 18:00
• It is meant to be over the $4^n$ ordered pairs $(x,y)$, so yeah every contribution is counted twice if you want Jul 30, 2021 at 18:03

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

• Your last sum simplifies to $4^n/n$. Jul 30, 2021 at 18:36
• @RobPratt Ah very nice, thanks! Jul 30, 2021 at 18:37
• @JairTaylor Thanks very much. and also RobPratt! This is actually already much larger than I would have hoped. Can you come up with an upper bound by any chance? Jul 30, 2021 at 18:50
• @Marsl Well, there is the trivial upper bound of $4^n$ since all the summands are $\leq 1$. Jul 30, 2021 at 18:55
• @JairTaylor Yeah, you re right. Would you mind editing your answer to reflect the fact that the sum simplifies to $4^n/n$ and that this optimal up to the linear factor of $1/n$ since $4^n$ is an upper bound. I will then accept your answer! Thank you very much again. Your help is much appreciated :) Jul 30, 2021 at 19:02