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}$.


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

  • 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 Jun 1 '18 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 Jun 1 '18 at 19:37

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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.