Skip to main content
1 of 2
gowers
  • 29k
  • 29
  • 145
  • 182

Nonexistence of an approximately distance-preserving map between discrete cubes

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?

gowers
  • 29k
  • 29
  • 145
  • 182