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.

  • $\begingroup$ I think you meant to write $\log 2$ in many places instead of $2$. $\endgroup$ – 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$.

  • $\begingroup$ Sorry, I wanted to ask about $\lim \frac{\log X_n}{n}$ $\endgroup$ – Alexey Milovanov Aug 13 '18 at 11:08

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.