3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – BigbearZzz Mar 20 '17 at 13:22
  • $\begingroup$ Sure, I can do that. $\endgroup$ – Misha Lavrov Mar 20 '17 at 13:49
  • $\begingroup$ I have edited my question to add more details. Thank you very much. $\endgroup$ – BigbearZzz Mar 20 '17 at 15:58
  • $\begingroup$ 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$. $\endgroup$ – Misha Lavrov Mar 20 '17 at 16:52
  • $\begingroup$ 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. $\endgroup$ – BigbearZzz Mar 20 '17 at 19:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.