# Kolmogorov complexity of string concatenation

If $K(s)$ is the Kolmogorov complexity of the string $s \in \{0,1\}^*$,

Can we prove (or disprove) the following statement:

"Every string $s$ is a prefix of an incompressible string; i.e. for every string $s$ there exists a string $r$ such that $K(sr) \geq |sr|$" ?

In a very informal (and perhaps not too meaningful) way: we know that $K(r) \leq |r| + O(1)$; if we pick a large enough incompressible string $r$, can we "use" the $O(1)$ to "mask" the compressibility of the given string $s$ ?

A similar (but different) result is that for any $c$, we can find $s$ and $r$ such that: $K(sr) > K(s) + K(r) + c$

• Does incompressible mean that the length of the string $s$ is a lower bound on its shortest description $K(s)$? – mrk Sep 16 '12 at 13:50
• @saadtaame: it means that $K(s) \geq |s|$ – Vor Sep 16 '12 at 15:41

Your conjecture is wrong. For some constants $C,D$, it holds that $K(sr) \leq 2K(s) + K(r) + C \leq 2K(s) + |r| + D$ (proof: use a universal Turing machine to generate $s$ and then $r$; you need somewhat more than $K(s)+K(r)$ to store both programs, though $2K(s)+K(r)$ is an overkill). Therefore if $2K(s) + D < |s|$, your conjecture doesn't hold. Such easy strings $s$ certainly exist, for example $K(0^n) = O(\log n)$.

• it seems ok. I thought that $D$ depends on $r$, but once fixed the UTM it is a constant. Another consideration: in concatenating the two strings one must add $\log |s|$ bits (to delimit the program for $s$ from the program for $r$), so your proof doesn't work if we modify the "conjecture" into: "every incompressible string $s$ is a prefix of an incompressible string $r$"? Can you see how to (dis)prove it easily? – Vor Sep 17 '12 at 8:55
• The latter conjecture is less interesting since $s$ is already incompressible. Formally, you could choose $r = s$, though this solution is easy to disallow. – Yuval Filmus Sep 17 '12 at 14:55
• @Yuval Filmus, do you have any ideas on how to prove the second statement, i.e., for any $c$, we can find $s$ and $r$ such that: $$K(sr)>K(s)+K(r)+c$$ This is stated in Sipser's book and left as an exercise problem, but I was not able to prove it, and I am very curious to know what kind of proof technique should be used to show this result. Thanks! – Han Zhao Feb 21 '18 at 0:45
• I suggest you post this as a new question with the 'Ask Question' button. When you do that, it might help if you told us what approaches you tried. It definitely doesn't belong as an answer here. – D.W. Feb 21 '18 at 1:06