# An inequality related to the number of binary strings with no fixed substring

This is basically a repost of this math.se question. At the time I was writing this I thought it has to have a straightforward solution so I posted it there. Now I am not so sure about it being so easy. The problem is as follows.

Let $f \in \{0,1\}^k$ and let $S_n(f)$ be the number of strings of $\{0,1\}^n$ that do not contain $f$ as a substring. Is it true that $$|f| > |f'| \implies S_n(f) > S_n(f')$$

I am aware that the transfer-matrix method could be used to compute $S_n(f)$ given a concrete $f.$ I don't know though if it offers a solution to this problem or perhaps if there's any other obvious reason why this is true.

• What do you mean by $|f|$? – Mariano Suárez-Álvarez Dec 2 '13 at 8:12
• @Mariano: I think $|f|$ denotes the length of the string $f$ . – Pietro Majer Dec 2 '13 at 9:38

Your conjecture is true. Here is a proof.

Define $\operatorname{Av}_n(w)$ to be the number of binary words of length $n$ which avoid the pattern $w$.

Let $u$ and $v$ be binary words with $|u| = k$ and $|v|=m$ with $k < m$. We will show that $\operatorname{Av}_n(u) < \operatorname{Av}_n(v)$ for all $n$.

Define the special words $$M_n = \overbrace{00\cdots00}^n\qquad\text{and}\qquad L_n = \overbrace{00\cdots01}^n.$$

We can show fairly easily using the cluster method of Goulden and Jackson (and other ways as well, though the cluster method works easily for any pattern) that words avoiding $M_n$ and words avoiding $L_n$ have the generating functions $$m_n(x) = \sum_{r \geq 0}\operatorname{Av}_r(M_n)x^r = \frac{1-x^n}{1-2x+x^{n+1}}$$ and $$\ell_n(x) = \sum_{r\geq 0} \operatorname{Av}_r(L_n)x^r = \frac{1}{1-2x+x^n}.$$

Moreover, of all words $w$ with $|w|=n$, $M_n$ is the most avoided word and $L_n$ is the least avoided word. Formally, for $w$ with $|w|=n$ and all $r$ $$\operatorname{Av}_r(L_n) \leq \operatorname{Av}_r(w) \leq \operatorname{Av}_r(M_n).$$

This can be seen probabilistically by observing that the number of occurrences of a pattern of length $n$ in all words of length $r$ is independent of what the pattern is. Since $M_n$ "packs" the most easily (i.e., has a lot of overlaps) and $L_n$ does not "pack" at all (i.e., cannot overlap itself), it follows that $M_n$ appears as a pattern in less words overall than any other pattern and $L_n$ appears as a pattern in more words overall than any other pattern.

It should also be obvious that $\operatorname{Av}_r(L_n) \leq \operatorname{Av}_r(L_{n+1})$ for all $r$.

We need to prove one more fact: $\operatorname{Av}_r(M_{s-1}) < \operatorname{Av}_r(L_s)$ for all $r \geq s-1$.

Edit: As @DavidSpeyer pointed out in a comment, this is easily proved by observing that $M_{s-1}$ is a subword of $L_s$. I've removed my lengthier argument, but left the generating functions $m_n(x)$ and $\ell_n(x)$ defined above.

We now combine all of our results: for $r \geq k$ $$\operatorname{Av}_r(u) \leq \operatorname{Av}_r(M_k) < \operatorname{Av}_r(L_{k+1}) \leq \operatorname{Av}_r(L_m) \leq \operatorname{Av}_r(v).\;\;\square$$

• Quicker proof that $Av_r(M_{s-1}) \leq Av_r(L_s)$: The string $M_{s-1}$ is a substring of $L_s$. Nice answer! – David E Speyer Dec 2 '13 at 21:16
• I have to admit though, I don't find it completely obvious that increasing the self overlaps always makes a word harder to avoid. – David E Speyer Dec 2 '13 at 21:29
• @DavidSpeyer Thanks for pointing that out. As for the overlaps, if we define the overlap set $\mathcal{O}(w)$ of a word $w$ of length $n$ to be the set of indices $k$ such that $w_i = w_{n-i+1}$ for all $1 \leq i \leq k$, then it follows from the cluster method that if $\mathcal{O}(w) \subseteq \mathcal{O}(w')$, then $\operatorname{Av}_r(w) \leq \operatorname{Av}_r(w')$. (In fact, the generating function for $\operatorname{Av}_r(w)$ can be directly computed from $\mathcal{O}(w)$.) Since $\mathcal{O}(M_n) = \{1,\ldots,n-1\}$ and $\mathcal{O}(L_n) = \emptyset$, my claim follows. – Jay Pantone Dec 2 '13 at 23:02
• The formula that I get (Concrete Mathematics, Section 8.4) is $\sum_r Av_r(w) z^r = 1/(1-2z+z^{|w|}/(1+\sum_{i \in \mathcal{O}(w)} z^i))$. It is easy to see that increasing the set $\mathcal{O}(w)$ makes this generating function larger as a function of $z$, but it isn't obvious to me that it makes each individual term larger. – David E Speyer Dec 2 '13 at 23:14
• @DavidSpeyer I think you can see it by subtracting the generating function for words avoiding $w$ from the generating function for words avoiding $w'$, and with a little algebra get a power series with positive coefficients. This result also appears in "String Overlaps, Pattern Matching, and Nontransitive Games", by Guibas and Odlyzko (see Section 7). – Jay Pantone Dec 6 '13 at 1:35

This is not quite a proof yet, but might be enough for you to finish it off.

In a random string of length $n$, the expected number of substrings equal to $f$ depends only on the length of $f$. So the number of strings containing $f$ depends on how much we lose from the expectation by having multiple copies of $f$ in each string. But the easiest substring to pack is a constant substring; and any substring that cannot overlap with itself under any circumstances is equally hard to pack. So take $f'$ to be $k$ $0$'s and $f$ to be a $1$ followed by $k$ $0's$: this should be a worst case. But in this case it is clear that $|S_n(f)| > |S_n(f')|$.

You may always assume that $f$ starts with a zero. For each $i = 1,\ldots, n-k+1$, let $S_i$ be the set of strings whose the substring from position $i$ to position $i+k-1$ is equal to $f$. It is trivial that $|S_i| = 2^{n-k}$. The set of strings whose have a substring equal to $f$ is the union of these sets. Therefore, one has the inequality $$M_n(k) \le (n-k+1)\cdot 2^{n-k}$$ where $M_n(k) = \max Q_n(f)$, and $Q_n(f)$ denotes the number of strings whose have a substring equal to $f$.

Moreover, note that $S_{ij} = S_i \cap S_j$ has the same cardinality $2^{n-2k}$ when $|i - j| \ge k$, and is empty for all $i, j$ such that $|i-j| < k$ if and only if $f$ is not invariant under any translations. (A string is invariant under some translation if any only if it is decomposable (i.e., $f = g \ldots g$ for some string $g$.) Therefore, one can see that $Q_n(f)$ is maximum when $f$ is not invariant under any translations, e.g. $f = 0\ldots 01$. The formula for $M_n(k)$ is possible given that one write $n = k d + r$, and then find out exactly how many $S_I = \cap_{i\in I} S_i$ is non-empty. But for the purpose of proving the inequality the question ask the rough bound above is enough.

Now, $S_{ij}$ has maximum cardinality (the same as being non-empty) for all $|i-j| < k$ if and only if $f$ is invariant under any translations. In other words, $f = 0\ldots 0$. Note that if $S_{ij}$ is empty for some $|i-j| < k$, then it is non-empty for quite a few more, and the $S_{ijk}$ cannot recover much, thus the minimum value of $Q_n(f)$ is obtained at $m_n(k) = Q_n(0\ldots 0).$

Now the $m_n(k)$ follows the following recursive formulas: For $n = k + i$, with $1\le i \le k-1$, we have $$m_{k+i}(k) = m_{k+i-1}(k) + \cdots + m_k(k) + 2^{n-k}.$$ The reason for this recursive formula is that if the last entry of your string is $1$, then you have $m_{k+i-1}$ of the strings, if then the last two entries of your string is $10$, then you have $m_{k+i-1}$, etc, until if the last $i$ entries is $0\cdots 0$, then its last $k$ entries must all be zero, thus the factor of $2^{n-k}$ at the end. From this recursive formula one deduces that $$m_{k+i} = i\cdot 2^{i-1} + 2^i$$ for $i= 0, \ldots, k-1$. For $i \ge k$, similarly one has the formula $$m_{k+i} = m_{k+i-1} + \cdots + m_{i+1} + 2^i.$$ In particular, $m_{2k} = k\cdot 2^{k-1} + 2^k - 1$ and $m_{k +i} > i\cdot 2^{i-1}$. (Each of the term in the recursive formula for $m_{k+i}$ is larger than $2^i$ (it is actually much larger).

To prove your inequality, obviously from the explicit formula, it is true when $n \le 2k$. And for $i > k$, it follows from the previous inequality $i\cdot 2^{i-1} < m_{k+i}.$