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

Improve this question
$\endgroup$
8
  • 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
    Commented Dec 20, 2018 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
    Commented Dec 20, 2018 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
    Commented Dec 20, 2018 at 15:45
  • 1
    $\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
    Commented Dec 20, 2018 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
    Commented Dec 20, 2018 at 19:01

1 Answer 1

Reset to default
6
$\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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .