# A question about a $2^n$-point metric space

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

• 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. – Ben Barber Jun 1 '18 at 19:00
• 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|$? – 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)$.