# Stretching map of $n$ points from $\{0,1\}^n$ to $\{0,1\}^{n+1}$ with respect to their Hamming distance

Given a positive integer $$n$$, the Hamming distance $$d^H_n(x,y)$$ of $$x,y\in \{0,1\}^n$$ is defined by $$d^H_n(x,y) = |\{k\in\{0,\ldots,n-1\}: x(k)\neq y(k)\}|.$$

Given an integer $$n>0$$ and a set $$S\subseteq \{0,1\}^n$$ with $$|S| = n$$, is it possible to find a map $$f:S\to \{0,1\}^{n+1}$$ such that $$d^H_{n+1}(f(x), f(y)) = d^H_n(x,y) + 1 \text{ for all } x\neq y\in S$$?

• No when $n=3$, since $100$, $010$, $001$ are all at distance $2$, but there are no three words in $\{0,1\}^4$ all at distance $3$. Proof: we can suppose $0000$ and $0111$ are two of these words; the other words at distance $3$ from $0000$ are $1011, 1101, 1110$ , and all are distance two from $0111$. – Mark Wildon Dec 20 '18 at 15:22
• Thanks for this example! I am leaning towards deleting the question, but if you want to post this as answer, you are welcome – Dominic van der Zypen Dec 20 '18 at 15:34
• Up to you of course, but I think there is something of interest here. E.g. even if $n$ points are too many in general, then is the right number still $\Omega(n)$? – Mark Wildon Dec 20 '18 at 15:45
• Nice follow up question! I'll leave this question for the moment, and suggest you add your comment as an answer so we can close this thread – Dominic van der Zypen Dec 20 '18 at 16:07
• Yes - absolutely. (so this shows that there can never be an example of a map satisfying the desired property). – Anthony Quas Dec 20 '18 at 19:01

Here is an infinite family of counterexamples. Let $$n = 2^r$$. The $$2^r$$ distinct rows of a $$2^r \times 2^r$$ Hadamard matrix with entries from $$\{0,1\}$$ are all at distance $$2^{r-1}$$. However the maximum number of binary words all at distance $$2^{r-1} + 1$$ in $$\{0,1\}^{2^r+1}$$ is just $$2$$. Proof. We can suppose that $$0\ldots00 \ldots 0$$ and $$1\ldots 11\ldots 0$$ are two of these words. Flipping any $$2^{r-1} + 1$$ bits in the second word gives a binary word of even weight, so not at the odd distance $$2^{r-1}+1$$ from all-zeros.