2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – Mark Wildon Dec 20 '18 at 15:22
  • $\begingroup$ Thanks for this example! I am leaning towards deleting the question, but if you want to post this as answer, you are welcome $\endgroup$ – Dominic van der Zypen Dec 20 '18 at 15:34
  • $\begingroup$ 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)$? $\endgroup$ – Mark Wildon Dec 20 '18 at 15:45
  • $\begingroup$ 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 $\endgroup$ – Dominic van der Zypen Dec 20 '18 at 16:07
  • 1
    $\begingroup$ Yes - absolutely. (so this shows that there can never be an example of a map satisfying the desired property). $\endgroup$ – Anthony Quas Dec 20 '18 at 19:01
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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