Skip to main content
1 of 2
Saúl RM
  • 10.6k
  • 2
  • 28
  • 48

Maximum cardinality of separated sets in the Hamming distance

This question is motivated by section 15.1 (Codes) of Alon and Spencer's The probabilistic method.

Fix $\alpha<\frac{1}{2}$ and for each $n\in\mathbb{N}$ let $\{0,1\}^n$ be the length $n$ binary strings with the Hamming distance.

Let $N_n$ be the maximal cardinality of a $\alpha n$-separated set (that is, the points of the set are pairwise at distance $\alpha n$) in $\{0,1\}^n$. What do we know about the growth rate of $N_n$?

It has to grow slower than $\frac{2^n}{\#B(0,\frac{n\alpha}{2})}$. So, as $\#B(0,\frac{n\alpha}{2})=2^{n(H(\frac{\alpha}{2})+o(1))}$ (where $H(x)=-x\log_2(x)-(1-x)\log_2(1-x)$), as proved in the section mentioned above of Alon and Spencer's book, this gives an upper bound of $2^{n(1-H(\frac{\alpha}{2})+o(1))}$. I don't think I have any decent lower bounds.

Saúl RM
  • 10.6k
  • 2
  • 28
  • 48