8
$\begingroup$

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.

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

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

$\endgroup$
  • 3
    $\begingroup$ 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! $\endgroup$ – David E Speyer Dec 2 '13 at 21:16
  • $\begingroup$ I have to admit though, I don't find it completely obvious that increasing the self overlaps always makes a word harder to avoid. $\endgroup$ – David E Speyer Dec 2 '13 at 21:29
  • 1
    $\begingroup$ @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. $\endgroup$ – Jay Pantone Dec 2 '13 at 23:02
  • $\begingroup$ 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. $\endgroup$ – David E Speyer Dec 2 '13 at 23:14
  • 2
    $\begingroup$ @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). $\endgroup$ – Jay Pantone Dec 6 '13 at 1:35
2
$\begingroup$

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')|$.

$\endgroup$
0
$\begingroup$

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}.$

$\endgroup$

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.