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



Intuition for inequality involving permutation and Hamming Cube
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.


