# Injective map from $\{0,1\}^{n}$ to $\mathbb{N}$

Please help me to construct an example of an injective map $F: \{0,1\}^{n} \to \mathbb{N}$ such that $$|F(x_1,\ldots,x_n)-F(y_1,\ldots,y_n)| = \sum_{k=1}^{n} |x_k-y_k|$$ for all $x=(x_1,\ldots,x_n), \quad y=(y_1,\ldots,y_n) \quad (x_i, y_i =0 \,\,\text{or}\,\, 1)$.

Of course, there are $2^n$ such tuples and every such an $n$-tuple corresponds to a natural number.

• $\mathbb{N}_0$ or $\mathbb{N}_+$? – orlp Jun 12 '18 at 8:33
• $\mathbb{N}=\{0,1,2,\ldots\}$ or $\mathbb{N}=\{1,2,\ldots\}$ - it does not matter – monica_k Jun 12 '18 at 8:35
• I think maybe Gray codes can help here. – monica_k Jun 12 '18 at 8:38

This is impossible. Consider $x$ to be a $n$-tuple with $n-1$ zeroes and a single $1$ in the $k$th position and $y = (0, \dots, 0)$.

Then:

$$|F(x_1, \dots, x_n) - F(0, \dots, 0)| = 1$$

This means that there are only two possible values for $F(x_1, \dots, x_n)$, namely $F(0, \dots, 0) \pm 1$.

But there are $n$ possible $x$ with the conditions above, meaning for $n > 2$ the mapping can't be injective.

• Thank you very much! And what will be if one replace the above identity in the problem with the inequality $$|F(x_1,\ldots,x_n)-F(y_1,\ldots,y_n)| \leq C \sum_{k=1}^{n} |x_k-y_k|$$ for some $C>0$ ? – monica_k Jun 12 '18 at 8:42
• @monica_k Well by the same argument as above, $C$ can not be a constant irrespective of $n$, as it needs to be at least $n/2$. I don't know if that would be sufficient, but it would at least be necessary. – orlp Jun 12 '18 at 8:43
• @monica_k As there are $n$ choices for $\mathbf x$ (for given $\mathbf y$) that leadt to $\sum=1$, you'll need $C\ge n/2$. However, there are $n\choose 2$ possibilities with $\sum=2$, so you need to pack ${n\choose 2}+n+1$ values into $2C+1$ allowed values, i.e., $C$ must be ate least $\sim n^2/4$. We could continue, or note directly that to cover all vectros, we need $2^n\le 2nC+1$ – Hagen von Eitzen Jun 12 '18 at 8:47
• I'm sorry. Aren't there any positive examples for similar problems? I try the last attempt: What about an example of an injective map $F: B_{n,m} \to \mathbb{N}$ such that $$|F(x_1,\ldots,x_n)-F(y_1,\ldots,y_n)| \leq C \sum_{k=1}^{n} |x_k-y_k|$$ for all $x,y\in B_{n,m}$ (for some $C>0$) ? Here $$B_{n, m}=\{x=(x_1,\ldots,x_n)\in\{0,1\}^{n}: \,\, \sum_{k=1}^{n}x_k = m \}.$$ So, $B_{n, m}$ is the set of $n$-tuples of 0 and 1 with the fixed sum equal to $m$. ($m>1$ is the fixed natural number) – monica_k Jun 12 '18 at 8:59