# Intuition for inequality involving permutation and Hamming Cube

Let $C^n=\{0,1\}^n$ be a metric space (Hamming Cube). The distance on $C^n$ is defined by $$d(\varepsilon,\varepsilon'):=|\{j:\varepsilon_j\ne\varepsilon'_j\}|,$$ $\varepsilon=(\varepsilon_1,\dots,\varepsilon_n)$.

Let $s,k$ be integers such that $sk=n$. We divide each $\varepsilon$ into $k$ blocks, each of lenght $s$ i.e. $$\underbrace{ \underbrace{\varepsilon_1, \varepsilon_2,\dots,\varepsilon_s}_{s\text{ times}}, \underbrace{\varepsilon_{s+1}, \varepsilon_{s+2},\dots,\varepsilon_{2s}}_{s\text{ times}},\dots, \underbrace{\varepsilon_{(k-1)s+1}, \varepsilon_{(k-1)s+2},\dots,\varepsilon_{n}}_{s\text{ times}} }_{k\text{ times}}$$ Denote the $i^{\text{th}}$ block by $I_i:=\{(i-1)s+1,(i-1)s+2,\dots,is \}$.

Define $\varepsilon_{I_i}$ by

$$(\varepsilon_{I_i})_j:= \begin{cases}1-\varepsilon_j &;\ j\in I_i \\ \varepsilon_j &;\ j\ne I_i \end{cases}$$ to be the swap of the $i^{\text{th}}$ block of $\varepsilon$. For example let $n=6,k=3,s=2$, then \begin{align} (000000)_{I_1}&=(110000)\\ (000000)_{I_2}&=(001100)\\ (011001)_{I_1}&=(101001). \end{align}

Any permutation $\sigma\in S_n$ induces a transformation on $\varepsilon$ in an obvious way: $$(\sigma\varepsilon)_j := \varepsilon_{\sigma(j)}.$$

Let $f:C^n \to X$, where $X$ is another metric space. Denote the diagonal map $\delta$ defined by $$\delta(\varepsilon):=d(f(\varepsilon),f(1-\varepsilon))$$ and a another map $\phi_i(\varepsilon,\sigma)$ defined by $$\phi_i(\varepsilon,\sigma):=d(f(\sigma\varepsilon),f(\sigma\varepsilon_{I_i})).$$

There are two claims \begin{align} \sum_{\sigma,\varepsilon}\phi_i(\varepsilon,\sigma) &= \sum_{\sigma,\varepsilon}\phi_j(\varepsilon,\sigma)\quad\text{for all}\ i,j\quad\text{and} \\ \sum_{\varepsilon}\delta(\varepsilon) &\le \frac 1{n!}\sum_{i=1}^k \sum_{\sigma,\varepsilon}\phi_i(\varepsilon,\sigma). \end{align}

The first one is not so hard, but I cannot wrap my head around the second one yet. I believe a prove would go along the line of using triangle inequality repeatedly, but right now I am confused by $\phi_i(\varepsilon,\sigma)$.

Is there a nice way to look at $\phi_i(\varepsilon,\sigma)$? What is it intuitively?

EDIT: To generalize the inequality, we can write $$E_1 := \frac 1{n!}\sum_{\sigma,\varepsilon}\phi_i(\varepsilon,\sigma)$$ and, since $E_1$ does not depend on the choice of $i$, the previous inequality become $$\sum_{\varepsilon}\delta(\varepsilon) \le k E_1 = \frac ns E_1.$$ Now define $\phi_{i,j}:=d(f(\sigma\varepsilon),f(\sigma\varepsilon_{I_i\cup I_j}))$, where $\varepsilon_{I_i\cup I_j}$ is the swapping of both $i^{\text{th}}$ and $j^{\text{th}}$ block, $$E_2 := \frac 1{n!}\sum_{\sigma,\varepsilon}\phi_{i,j}(\varepsilon,\sigma)$$ for $i\ne j$. How do we prove $$\sum_{\varepsilon}\delta(\varepsilon) \le \frac n{2s} E_2$$ and, even more generally, $$\sum_{\varepsilon}\delta(\varepsilon) \le \frac n{ts} E_t$$ where $E_t$, $1\le t\le k$, is defined using $\varepsilon_{I_{i_1}\cup I_{i_2}\cup\cdots\cup I_{i_t}}$ with $i_1<i_2<\dots<i_t$?

This is not hard when $ts|n$ but for general $t$ I cannot see it.

If we took $\phi_i(\varepsilon, (1))$, where $(1)$ is the identity permutation, we'd have $d(f(\varepsilon), f(\varepsilon_{I_i}))$: the distance we go when we change the $i$-th block of $\varepsilon$.

But there's nothing special about the order of the coordinates of $\varepsilon$, nor about the way we partition them into blocks. So we introduce the permutation $\sigma$ to average out over all of these. In fact, if we consider the values of $\phi_i(\sigma^{-1}\varepsilon, \sigma)$ as $\sigma$ ranges over all of $S_n$, we'd see every possible way to change $s$ coordinates of $\varepsilon$ a total of $n!/\binom{n}{s}$ times.

But there's a reason that we keep blocks around, rather than just permuting over sets of $s$ coordinates. We can use blocks to define the sequence $\varepsilon^{(0)}, \varepsilon^{(1)}, \dots, \varepsilon^{(k)}$, where:

• we start with an $\varepsilon^{(0)} = \varepsilon$,
• then flip the blocks one at a time by taking $\varepsilon^{(i)} = \varepsilon^{(i-1)}_{I_i}$,
• and as a result end up at $\varepsilon^{(k)} = 1 - \varepsilon$.

This is a particular choice of $k$-step path from $\varepsilon$ to $1 - \varepsilon$, and $$\phi_1(\varepsilon^{(0)}, (1)) + \phi_2(\varepsilon^{(1)}, (1)) + \dots + \phi_k(\varepsilon^{(k-1)}, (1))$$ will tell us the length of that path in the embedding $C^n \to X$. If we now let $\varepsilon$ and $\sigma$ vary, then $$\phi_1(\varepsilon^{(0)}, \sigma) + \phi_2(\varepsilon^{(1)}, \sigma) + \dots + \phi_k(\varepsilon^{(k-1)}, \sigma)$$ will vary over the lengths of all possible $k$-step paths, where we can start at any $\varepsilon$ and flip the coordinates in any possible groups of $s$ at a time, until we end up at $1-\varepsilon$.

By the triangle inequality, $$\delta(\varepsilon) \le \phi_1(\varepsilon^{(0)}, \sigma) + \dots + \phi_k(\varepsilon^{(k-1)}, \sigma)$$ since the $k$-step path can be no shorter than a direct path from $\varepsilon$ to $1-\varepsilon$. So if we average over all the paths, then we must have $$\frac1{2^n} \sum_{\varepsilon} \delta(\varepsilon) \le \frac1{2^n\,n!}\sum_{\sigma,\varepsilon} \left(\phi_1(\varepsilon^{(0)}, \sigma) + \dots + \phi_k(\varepsilon^{(k-1)}, \sigma)\right).$$ The rest of the work is just rearranging the sum on the right-hand side to "forget" about the existence of $k$-step paths.

• Thank you very much for your time! I have also managed to solved it 2 days after posting it here and the reasoning was almost parallel to what you did here. Anyway, if you would be so kind, I have another very related problem that I still cannot solve and wonder if you'd like to have a try at it? It's a generalization of this problem but I found it to be a whole lot harder. – BigbearZzz Mar 20 '17 at 13:22
• Sure, I can do that. – Misha Lavrov Mar 20 '17 at 13:49
• I have edited my question to add more details. Thank you very much. – BigbearZzz Mar 20 '17 at 15:58
• After a discussion with my officemate, we determined that the generalized inequality is false. Let $s=1$ and $n=3$; for the map $f : C^n \to X$, choose $x_0, x_1 \in X$ and map $\varepsilon$ to $x_0$ or $x_1$ according to whether $\varepsilon_1 + \cdots + \varepsilon_n$ is even or odd. Then $\delta(\varepsilon) = d(x_0, x_1)$ for any $\varepsilon$, but $E_2=0$, since $f(\varepsilon) = f(\varepsilon_{I_i \cup I_j})$ for any $\varepsilon, i, j$. – Misha Lavrov Mar 20 '17 at 16:52
• Thank you for confirming my suspicion. I am already convinced that the generalization is wrong but it seems to be used in a well-known paper (the paper is extremely sketchy in many parts so I am not 100% sure). It is implicit that $n$ is supposed to be very large (astronomically large) but I think an issue will arise anyway when $t$ gets near $k$. Now I'm very lost. – BigbearZzz Mar 20 '17 at 19:43