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

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

1 Answer 1


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

  • 1
    $\begingroup$ Your last sum simplifies to $4^n/n$. $\endgroup$
    – RobPratt
    Jul 30, 2021 at 18:36
  • $\begingroup$ @RobPratt Ah very nice, thanks! $\endgroup$ Jul 30, 2021 at 18:37
  • $\begingroup$ @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? $\endgroup$
    – Marsl
    Jul 30, 2021 at 18:50
  • $\begingroup$ @Marsl Well, there is the trivial upper bound of $4^n$ since all the summands are $\leq 1$. $\endgroup$ Jul 30, 2021 at 18:55
  • $\begingroup$ @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 :) $\endgroup$
    – Marsl
    Jul 30, 2021 at 19:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .