Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
I'm slightly baffled: how does Borsuk-Ulam apply to $\{0,1\}^n$? In particular, continuous functions $\{0,1\}^n \to \{0,1\}^m$ are rather different from restrictions of continuous functions $[0,1]^n \to [0,1]^m$, are they not? –  Vidit Nanda Jul 8 '13 at 17:59
    
I think my answer applies to $m=n/2$ by using asymptotically good codes of rate $1/2$ and it shows that $\phi$ does not exist for small enough $\delta$. –  Felipe Voloch Jul 8 '13 at 20:52
add comment

2 Answers 2

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$?

share|improve this answer
    
You're right about projection on to the first $n-1$ coordinates. Actually, the case that I'm really interested in is $n/2$ dimensions. In an hour or so I'll modify the question accordingly. –  gowers Jul 8 '13 at 18:22
add comment

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.

share|improve this answer
1  
Hi Eoin, welcome to MO! (That is, assuming you're the Eoin I think you are. (Or rather, welcome no matter which Eoin you are, though you might find my welcome confusing if you're not the Eoin I think you are.)) –  Artie Prendergast-Smith Jul 8 '13 at 21:14
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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