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



Set of strings $S$ such that no string from $S$ is a substring of another one
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.


