Set of strings $S$ such that no string from $S$ is a substring of another one Let $X$ be a subset of $\{0,1\}^*$ with the following property: for every pair of distinct strings $x_1$, $x_2$ from $X$
$x_1$ is not a substring of $x_2$ and  $x_2$ is not a substring of $x_1$.
How much can be the log-density of $X$, 
i.e. $\lim \frac{ \log X_n}{n}$, where $X_n$ is the cardinality of all strings of length $n$ in $X$? 
 A: I'm going to use $\log_2$ instead of $\log$ throughout; this only results in constant factor change (and the largest possible answer becomes $1$, which is convenient).
Fedor Petrov's answer implies that $\lim \frac{\log_2 X_n}{n} < 1$ for any $X$. We can, however, construct a family $X$ with $\lim \frac{\log_2 X_n}{n} > 1 - \varepsilon$ for any $\varepsilon > 0$. To do that, choose $k \in \mathbb{N}$, and let $Y_k \subset \{0, 1\}^*$ consist of all strings without $k$ consecutive zeroes. Finally, let $X = \{0^k1s10^k | s \in Y_k\}$. $X$ is substring-free since $0^k$ can only occur as a prefix or as a suffix, and $x, y \in X$ with $x$ containing $y$ would imply that $x$ contains $0^k$ in the middle.
For this particular $X$, we have $X_n = \Theta(\alpha_k^n)$, where $\alpha_k$ is the largest root of $x^k = x^{k - 1} + \ldots + 1$. It is straightforward that $\lim_{k \to \infty} \alpha_k = 2$, hence for a given $\varepsilon > 0$ choosing $k$ such that $\alpha_k > 2^{1 - \varepsilon}$ does the job.
A: Even if we forbid one substring $a$, the density becomes 0: if $m$ is a length of $a$, then there exist at most $(2^m-1)^{\lceil n/m\rceil}$ strings of length $n$ without substring $a$. 
