3
$\begingroup$

This is inspired by an older, as of yet unanswered question.

If $X$ is a set and $A,B\subseteq X$, we let the Hamming distance of $A, B$ be defined as $d_H:=\text{card}\big((A\setminus B)\cup (B\setminus A)\big)$.

Given $n\in\mathbb{N}$, we say that a collection ${\cal S}\subseteq {\cal P}(\mathbb{N})$ is $n$-equidistant if distinct members of ${\cal S}$ have Hamming distance $n$. For $n\in\mathbb{N}$ we let $M_n$ be the maximal cardinality that an $n$-equidistant collection can have.

It is not hard to prove that if ${\cal S}\subseteq {\cal P}(\mathbb{N})$ is uncountable, then ${\cal S}$ contains two members of infinite Hamming distance. So $M_n\leq \aleph_0$ for all $n\in \mathbb{N}$.

If $n$ is even, say $n=2k$, then we have $M_n = \aleph_0$: Partition $\mathbb{N}$ into sets of cardinality $k$ each.

We have $M_1=2$.

What are the values of $M_{2k+1}$ for integers $k\ge1$

$\endgroup$

1 Answer 1

8
$\begingroup$

Suppose we have sets $A,B,C$ which are $n$-equidistant. Then $$n=|A\triangle C|=|(A\triangle B)\triangle (B\triangle C)| = 2(n-|(A\triangle B)\cap (B\triangle C)|),$$ so $n$ is even. Thus $M_n=2$ whenever $n$ is odd.

$\endgroup$

You must log in to answer this question.

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