1
$\begingroup$

For any positive integer $n$, let $X_n$ be the family of all subsets of $\{1,2,\cdots,n\}$.

Let $(X_n,d)$ be the metric space such that $$d(A,B)=|\,A\triangle B\,|,\ \forall A,B\in X_n$$ where $A\triangle B$ is the symmetric difference of $A$ and $B$.

Let real $k>0$ (be fixed), and let $\ S_n\subseteq X_n\ $ satisfy:

      for every $F\in X_n$, there exists $E\in S_n$ such that $d(E,F)<k\sqrt{n}$.

Is

$$ \liminf_{n\rightarrow\infty}\frac{\mid S_n\mid}{\mid X_n\mid}>0\,? $$

Now I know the answer is no! I want to know more about quotients $\ \frac{|S_n|}{2^n}\ $ as $\ n\rightarrow\infty\, ?$

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ Your space is $\mathbb F_2^n$ with the Hamming metric, and your $S_n$ is an $a_n$-covering code. You might like to consider the case where $S_n$ is all sets of even size. $\endgroup$
    – Ben Barber
    Commented Jun 1, 2018 at 19:00
  • $\begingroup$ Ben Barber: Thanks for your reminding. I should think carefully before posting my question! I have revised my question, but the answer is also no! Is there any relationship between $a_n$ and $|S_n|/|X_n|$? $\endgroup$
    – user173856
    Commented Jun 1, 2018 at 19:37

1 Answer 1

Reset to default
3
$\begingroup$

No: let $S_n$ be the collection of subsets of $\{1,\ldots,n\}$ whose size is a multiple of $\lfloor k\sqrt n\rfloor$. Then every subset of $\{1,\ldots,n\}$ may be approximated by an element of $S_n$ with error at most $\frac 12\lfloor k\sqrt n\rfloor$. The ratio $|S_n|/|X_n|$ is approximately $1/(k\sqrt n)$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Anthony Quas: Yes, you are right! Thanks for your answer! Do you know any relationship between $a_n$ and $|S_n|/|X_n|$? $\endgroup$
    – user173856
    Commented Jun 1, 2018 at 19:40
  • 3
    $\begingroup$ This is exactly the question of the densest code. See the Hamming Bound (en.wikipedia.org/wiki/Hamming_bound) and the Gilbert Varshamov bound (en.wikipedia.org/wiki/Gilbert%E2%80%93Varshamov_bound) for more details. $\endgroup$
    – Anthony Quas
    Commented Jun 1, 2018 at 20:07
  • $\begingroup$ Anthony Quas: Thank you very much for your help! $\endgroup$
    – user173856
    Commented Jun 3, 2018 at 15:29

You must log in to answer this question.

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