<p>A simple bound is that we could use a program generating <span class="math-container">$x$</span>, a starting index <span class="math-container">$1 \leq i \leq n$</span> and length <span class="math-container">$m$</span> to get a program generating any choice of <span class="math-container">$v$</span>, and thus <span class="math-container">$C(v)$</span> is bounded as</p>
<p><span class="math-container">$$\forall v: k \leq C(v) \leq C(x) + \log(n) + \log(m) + c,$$</span></p>
<p>where <span class="math-container">$c$</span> is some constant overhead independent from <span class="math-container">$x,v$</span> that represents the steps necessary to take a Turing machine, a starting index and length and return the requested substring.</p>
<p>This in turn gives us a lower bound for <span class="math-container">$C(x)$</span>,</p>
<p><span class="math-container">$$C(x)  \geq k - \log(n) - \log(m) - c.$$</span></p>

CC BY-SA 4.0
2020-12-28T14:04:03.627Z
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
CC BY-SA 4.0
2020-12-28T19:51:40.127Z
@Ari No. Consider a program that generates all strings up to length $n$ concatenated.
orlp
CC BY-SA 4.0
2020-12-29T23:26:55.170Z
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
CC BY-SA 4.0
2020-12-29T23:40:12.770Z
@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
CC BY-SA 4.0
2020-12-27T10:46:24.143Z
2020-12-27T10:59:40.040Z
2020-12-27T10:59:40.040Z
orlp
<p>I know that the Kolmogorov complexity of a substring <span class="math-container">$v$</span> of an incompressible string <span class="math-container">$x$</span> has <span class="math-container">$C(v)\geq |v|-O(\log{|x|})$</span> , but I'm wondering if it is also possible to infer the complexity of a string given its substrings' complexity:</p>
<p>Specifically, If <span class="math-container">$x$</span> is a string of length <span class="math-container">$n$</span> and every substring <span class="math-container">$v$</span> of <span class="math-container">$x$</span> having length <span class="math-container">$m$</span> has complexity <span class="math-container">$C(v)\geq k$</span>, is it possible to infer any general lower bound for <span class="math-container">$C(x)$</span> in terms of <span class="math-container">$n$</span>, <span class="math-container">$m$</span>, and <span class="math-container">$k$</span>? I'm thinking that <span class="math-container">$C(x)$</span> cannot be much smaller than <span class="math-container">$k$</span> or else the <span class="math-container">$C(v)$</span> would not have <span class="math-container">$k$</span> as a lower bound. On the other hand, since <span class="math-container">$n$</span> can be much larger than <span class="math-container">$m$</span> this might balance things out.</p>

<co.combinatorics><kolmogorov-complexity>
Inferring the Kolmogorov complexity of a string from its substrings' complexity
Ari
# Inferring the Kolmogorov complexity of a string from its substrings' complexity

(Asked by: username_0 on 2020-12-16)

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.

**Tags:** co.combinatorics, kolmogorov-complexity


---

## 1 answers

### Answer by username_1 on 2020-12-27. Score: 1 | Accepted answer

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

> **Comments:**
> **username_0**: 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?  
> **username_1**: @username_0 No. Consider a program that generates all strings up to length $n$ concatenated.  
> **username_0**: 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}))$.  
> **username_1**: @username_0 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.  

---

