# Inferring the Kolmogorov complexity of a string from its substrings' complexity

I know that the Kolmogorov complexity of a substring $$v$$ of an incompressible string $$x$$ has $$C(v)\geq |v|-O(\log{|x|})$$ , but I'm wondering if it is also possible to infer the complexity of a string given its substrings' complexity:

Specifically, If $$x$$ is a string of length $$n$$ and every substring $$v$$ of $$x$$ having length $$m$$ has complexity $$C(v)\geq k$$, is it possible to infer any general lower bound for $$C(x)$$ in terms of $$n$$, $$m$$, and $$k$$? I'm thinking that $$C(x)$$ cannot be much smaller than $$k$$ or else the $$C(v)$$ would not have $$k$$ as a lower bound. On the other hand, since $$n$$ can be much larger than $$m$$ this might balance things out.

A simple bound is that we could use a program generating $$x$$, a starting index $$1 \leq i \leq n$$ and length $$m$$ to get a program generating any choice of $$v$$, and thus $$C(v)$$ is bounded as

$$\forall v: k \leq C(v) \leq C(x) + \log(n) + \log(m) + c,$$

where $$c$$ is some constant overhead independent from $$x,v$$ that represents the steps necessary to take a Turing machine, a starting index and length and return the requested substring.

This in turn gives us a lower bound for $$C(x)$$,

$$C(x) \geq k - \log(n) - \log(m) - c.$$

• Thanks. I thought though that a string always has a kolmogorov complexity at least as high as any of its substrings'. (In this case $C(x)\geq k$ without a need to subtract any more). Is that not necessarily true?
– Ari
Dec 28, 2020 at 14:04
• @Ari No. Consider a program that generates all strings up to length $n$ concatenated.
– orlp
Dec 28, 2020 at 19:51
• Thanks for the clarification. I also thought about it more and realized that without knowing any more about $x$, yours is about the best bound we can hope for. That is, if $x$ is $\frac{n}{m}$ copies of $v$ concatenated, we get $C(x)\leq k+O(\log(\frac{n}{m}))$.
– Ari
Dec 29, 2020 at 23:26
• @Ari I didn't claim my bound was the best possible, and your original question was more generic than copies of $v$ concatenated (the substrings could overlap in your original question). So I wouldn't be so quick with your conclusion.
– orlp
Dec 29, 2020 at 23:40