3
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ There are better bounds, like Elias - Bassalygo, based on considering slightly large balls that may intersect but not by many balls at once: en.m.wikipedia.org/wiki/Elias_Bassalygo_bound $\endgroup$
    – Fedor Petrov
    Commented Apr 11, 2023 at 20:20
  • 1
    $\begingroup$ fixed the link in the answer $\endgroup$
    – kodlu
    Commented Apr 13, 2023 at 18:31

1 Answer 1

Reset to default
4
$\begingroup$

The best upper bound will depend on $\alpha.$ and also whether you are interested in asymptotics.

There is a nice short chapter describing some of what is known https://algo.epfl.ch/_media/en/courses/2008-2009/mct_l03.pdf. The quantity $\alpha_2(x)$ is what you are interested in. In general unless $\alpha$ is very small the best upper bound is the so-called MRRW (4 Americans) bound of McEliece-Rudemich-Rumsey-Welch obtained by linear programming.

The lower bound given is Gilbert-Varshamov, and all the others are upper bounds. There have been some limited improvements on it, see Jiang and Vardy which I believe has since appeared in the IEEE Transactions on Information Theory after Alex Vardy unexpectedly passed away.

enter image description here

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thanks! By the way, I think the first "here" from your answer point to the wrong link? $\endgroup$
    – Saúl RM
    Commented Apr 13, 2023 at 18:12

You must log in to answer this question.

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