# Kolmogorov Complexity of ​String Concatenation

For all bit strings $$x$$, $$y$$ and Kolmogorov complexity $$K$$, is $$K(xy) > K(x)$$?

• (Expect any example having a shortish description in natural language or any formalism of choice to have a short program. That said, how about x the binary representation of Ackermann-Péter(4, 2) sans last bit, y 1?) – greybeard Nov 24 '19 at 7:04
• I don’t think that always holds. For example $xy$ could have very low complexity. Of course given $xy$ you could extract $x$ given its length, so your inequality holds with the corresponding error term. – Yuval Filmus Nov 24 '19 at 7:13

## 2 Answers

Let $$w = 0^{2^n}$$, so that $$K(w) = O(\log n)$$. The string $$w$$ has $$2^n+1$$ prefixes, and so some prefix $$x$$ satisfies $$K(x) \geq n$$. This example strongly violates your inequality.

On the other hand, given $$xy$$ and $$|x|$$, we can easily extract $$x$$. This shows that $$K(x) \leq K(xy) + O(K(|x|))$$. In particular, if $$|x| = n$$ then $$K(xy) \geq K(x) - O(\log n)$$.

While this example might have to be tweaked a little, consider a bitstring of 8192 zeroes followed by 273 ones. Let's call this string x. Now let's have y equal to 7919 ones.

Now concatenate: The string xy is 2^13 zeroes followed by 2^13 ones. It has a shorter description than x or y, and one can probably write a shorter algorithm to generate it that to generate either x or y alone.

Following an approach like this, for any given constant c, I think one could make an example where K(xy) < K(x) - c and K(xy) < K (y) - c.