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

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.
• I think you meant to write $\log 2$ in many places instead of $2$. – Noah Stephens-Davidowitz Aug 20 '18 at 21:07
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$.
• Sorry, I wanted to ask about $\lim \frac{\log X_n}{n}$ – Alexey Milovanov Aug 13 '18 at 11:08