Nonexistence of an approximately distance-preserving map between discrete cubes

Question

Let $n>m$. Can there exist a map $\phi:\{0,1\}^n\to\{0,1\}^m$ that approximately preserves Hamming distance? I'm defining Hamming distance slightly nonstandardly by dividing by the dimension, so that the maximum distance between two sequences is 1, whatever the dimension. By "approximately preserves" I mean that for every $x,y\in\{0,1\}^n$, $d(\phi(x),\phi(y))$ should be within $\delta$ of $d(x,y)$, where $\delta$ is some small constant like $1/100$.

It seems to me that the answer ought to be no, for the following reason. The fact that distances are approximately preserved implies a kind of continuity of $\phi$ (because in particular small distances go to small distances). But then the Borsuk-Ulam theorem would suggest that there will probably be two antipodal points in $\{0,1\}^n$ that map very close together in $\{0,1\}^m$, contradicting the approximate distance-preserving property.

My question is, is that thought the basis for a well-known argument? Or does the assertion follow easily from a known result?

Edit. As asked the question is not a great one, since, as Felipe points out below, if $m=n-1$ then one can just ignore the last coordinate. There are also arguments based on the pigeonhole principle if $n$ is a fair amount bigger than $m$: then there must be large sets of points in $\{0,1\}^n$ that have the same image, or, more generally, images in the same not too large Hamming ball. Amongst such sets there must be (if the sets are reasonably large) almost antipodal points (see Eoin's comment).

I'm actually interested in the case $m=n/2$. It's not clear to me (but I need to do some proper calculations) that that can be proved by pigeonhole type arguments. However, what is clear is that a topological proof of the kind I speculated about is unlikely to exist.

Answer 1

The existence of good error correcting codes implies that, given your $\delta$, there exists $\epsilon > 0$ and a subset $C$ of $\{0,1\}^n$ of size at least $2^{\epsilon n}$ for which any two distinct elements of $C$ are of at least distance (normalized as you did) $\delta$ apart. So $\phi$ is injective on $C$ and thus $m > \epsilon n$. I think for $m$ close to $n$ there should be such maps. Doesn't projection on the first $n-1$ coordinates work for $m=n-1$?

Answer 2

I guess the answer would be no if $n$ is only slightly bigger than $m$, as Felipe mentioned in his post (just by projecting onto subcubes). However, you're probably more interested in what happens when $n$ is reasonably separated from $m$. I think here you can prove what you would like using concentration of measure.

We must have that the preimage of some $x\in \{0,1\}^m$ under $f$ has size at least $2^{n-m}$. Now find some $\alpha \in [0,1/2]$ such that $2^{n-m} \approx \sum _{i= 0}^{\alpha n} \binom {n}{i}$. By an old result of Kleitman, any subset of $\{0,1\}^n$ of this size must contain two points at Hamming distance about $2\alpha n$ (this can be proved pretty easily using compressions). It's easy to see that for say $n/m \to \infty $ we have $ \alpha \to 1/2 $, and so two points which were almost antipodal get mapped to the same point.

In case you're interested in a better dependence between $n$ and $m$, I think that taking `preimage of a dense Hamming ball' of an appropriate radius in $\{0,1\}^m$ in place of $x$ in the above argument should create a worse distortion in this case.