# 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

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