Timeline for An inequality related to the number of binary strings with no fixed substring
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 6, 2013 at 1:35 | comment | added | Jay Pantone | @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). | |
| Dec 3, 2013 at 1:28 | vote | accept | Jernej | ||
| Dec 2, 2013 at 23:14 | comment | added | David E Speyer | 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. | |
| Dec 2, 2013 at 23:02 | comment | added | Jay Pantone | @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. | |
| Dec 2, 2013 at 22:51 | history | edited | Jay Pantone | CC BY-SA 3.0 |
Shortened the argument.
|
| Dec 2, 2013 at 21:29 | comment | added | David E Speyer | I have to admit though, I don't find it completely obvious that increasing the self overlaps always makes a word harder to avoid. | |
| Dec 2, 2013 at 21:16 | comment | added | David E Speyer | 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! | |
| Dec 2, 2013 at 21:12 | review | First posts | |||
| Dec 2, 2013 at 21:15 | |||||
| Dec 2, 2013 at 20:54 | history | answered | Jay Pantone | CC BY-SA 3.0 |