I would like to know more about the relationship between the Kolmogorov complexity of a string and that of its substrings. The relation that up to an additive constant, $K(x,y) = K(x) + K(y\ |\ x, K(x))$ begins to address this issue, but I am hoping there are results on substring complexity as opposed to the complexity of pairs of strings. For example, suppose that it is possible to "cover" an infinite binary sequence $X$ with (possibly overlapping, possibly length-bounded) substrings $\sigma$ such that each $\sigma$ has $K(\sigma) < s|\sigma|$ (with $s$ being some fixed constant). What can be said, if anything, about $K(\sigma)$ for arbitrary substrings $\sigma$ of $X$? While an answer to that specific question is interesting if you have it, I am most hoping for pointers on where to learn about substring complexity more generally.

  • $\begingroup$ Dear Linda, please consider changing your title to include something about your specific question on substring complexity; your title sounds much too general as is. $\endgroup$ – François G. Dorais Nov 16 '13 at 14:09
  • $\begingroup$ Dear François, thank you for the suggestion. I have improved the title. $\endgroup$ – Linda Brown Westrick Nov 21 '13 at 2:51

Although I don't have the references you seek, I did notice that the following observation answers your specific question, in the case you don't impose any bound on the covering substrings.

Claim. There is an infinite binary string $X$, which is covered by non-overlapping substrings $\sigma$, with $K(\sigma)\lt \frac12|\sigma|$, or indeed less than $s|\sigma|$ for any fixed desired $s$, such that every finite string arises infinitely often as a substring of $X$.

The idea is simply to build $X$ as the concatenation of strings of the form $\sigma=\tau^\frown0000\cdots000$, where an arbitrary string $\tau$ is simply padded with an enormous number of $0$s so as to ensure $K(\sigma)$ is small in comparison with $|\sigma|$. Each such string has low complexity compared with its length. Consequently, if we construct $X$ as the concatenation of all such strings arising with all possible finite binary strings $\tau$, then $X$ will satisfy your covering property, but it will exhibit every possible finite string as a substring.

In particular, we cannot deduce anything special about $K(\sigma)$ for an arbitrary substring of $X$ under the circumstances you describe, since every finite string is a substring of $X$.

In this example, the covering strings get longer and longer, but a similar argument works even when you impose a bound on the lengths.

Claim. For any fixed even length $k$, there is an infinite binary string $X$ that is covered by non-overlapping finite strings $\sigma$ of length at most $k$, such that $K(\sigma)\leq\frac12|\sigma|+1$, such that every string of length $k$ arises as a substring of $X$.

Build $X$ as the concatenation of all possible strings $\sigma$ of the form $$\tau^\frown000\cdots000\qquad\text{ or }\qquad000\cdots000^\frown\tau,$$ where the string $\tau$ is half of the string and the rest is made of $0$s. Any such string has $K(\sigma)\leq \frac12|\sigma|+1$, since you can just specify $\tau$ and then indicate whether the $0$s come before or after. But now the point is that if you build $X$ by sometimes putting the zeros first and sometimes by putting them last, then you can arrange that every possible string $\eta$ of length $k$ arises as a substring of $X$, since if $\eta=\eta_0^\frown\eta_1$ is cut in half, then $000\cdots000^\frown\eta_0^\frown\eta_1^\frown000\cdots000$ arises as a substring of $X$, where $\eta_0$ appears as the end of the first half and $\eta_1$ arises as the beginning of the next part.

  • $\begingroup$ Good, so these examples confirm that to get non-trivial behavior, one should both bound the length of the covering strings, and consider the complexity of substrings of all lengths. We can also observe that if we assume both those restrictions, we must allow the covering strings to overlap to get interesting behavior. If they don't overlap, concatenating the (prefix-free) codes for the covering strings will give short codes of arbitrary strings. An example where s=1/3 but the best arbitrary compression is 1/2 is to alternate strings of zeros with random strings of the same length. $\endgroup$ – Linda Brown Westrick Dec 2 '13 at 21:11

I cannot answer your specific question, but will just mention that Ming Li and Paul Vitányi's great book is now it its 3rd edition (Springer link):
     Book Cover

  • 2
    $\begingroup$ My first thought was also Li and Vitanyi, but I leafed through it last night and didn't find anything on this question much beyond what the OP seems to already know. $\endgroup$ – Steven Landsburg Aug 31 '13 at 14:26
  • $\begingroup$ Thanks, Steven. I am temporarily separated from my copy of the book, so I couldn't scan through it. $\endgroup$ – Joseph O'Rourke Aug 31 '13 at 15:04

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.