<p>Your bound is correct, for exactly the reasons you give. It is also unimprovable in general. Suppose that each function is multiplication by a large constant, where both constants are subwords of some infinite incomprehensible sequence. If you could compress the composition, you would be able to compress at least one of the constants—a contradiction. </p>

<p>Edit: You might need to pay additional bits for the composition, as for ordered pairings -- as observed by  Emil Jeřábek in the comments.</p>

CC BY-SA 4.0
2020-01-08T19:00:27.227Z
There is a related question I am interested in which I shared on the MathOverflow: https://mathoverflow.net/questions/350014/the-expressiveness-of-functions-computable-on-trees
Aidan Rocke
CC BY-SA 4.0
2020-01-08T19:01:40.003Z
I am not sure whether I should have shared it on the Theoretical Computer Science stackexchange instead because I felt that it could be of interest to many mathematicians.
Aidan Rocke
CC BY-SA 4.0
2020-01-09T08:09:37.620Z
Wouldn't there be a logarithmic overhead to separate the descriptions of $f$ and $g$? Or is this prefix-free Kolmogorov complexity?
Emil Jeřábek
CC BY-SA 4.0
2020-01-09T08:23:03.597Z
You may be right -- I was focusing more on the lower bound. In my example (with the two integers), it seems one can get away without the log overhead?..
Aryeh
CC BY-SA 4.0
2020-01-09T08:46:53.233Z
There are certainly examples where you need much less. For example, if $g$ is addition of a large constant, and $f$ is subtraction of the same constant, then $f\circ g$ is just the identity. The question is what is true for general $f$ and $g$, not for a particular example.
Emil Jeřábek
CC BY-SA 4.0
2020-01-09T09:29:18.337Z
Yes. I'd be interested to know the answer.
Aryeh
CC BY-SA 4.0
2020-01-09T09:34:54.837Z
Actually, I don’t see why you’d get away without overhead even in the multiplication example. While it may be less in particular cases, I don’t see in general how to encode the product of two integers shorter than by supplying a (constant-size) description of a multiplication algorithm together with the pair of the numbers. The overhead is needed to encode pairs.
Emil Jeřábek
CC BY-SA 4.0
2020-01-09T09:41:43.127Z
Function composition should be no easier than ordered pairs. Given functions $f(x)$ and $g(x)$, let $f'$ and $g'$ be the functions $f'(x)=(f(x),x)$ and $g'((x,y))=(x,g(y))$. Then $K(f')=K(f)+O(1)$, $K(g')=K(g)+O(1)$, and $K((f,g))\le K(g'\circ f')+O(1)$.
Emil Jeřábek
CC BY-SA 4.0
2020-01-08T15:29:17.977Z
2020-01-09T10:18:57.730Z
2020-01-09T10:18:57.730Z
Aryeh
<p>Let's suppose we encode two computable functions <span class="math-container">$f$</span> and <span class="math-container">$g$</span> as binary strings so <span class="math-container">$f,g \in \{0,1\}^*$</span>. What I am curious about is whether we can find good upper and lower bounds for: </p>

<p><span class="math-container">\begin{equation}
K(f \circ g) \tag{1}
\end{equation}</span></p>

<p>where <span class="math-container">$K(\cdot)$</span> denotes Kolmogorov Complexity. </p>

<p>My intuition suggests that we can compress each function separately and therefore: </p>

<p><span class="math-container">\begin{equation}
K(f \circ g) \leq K(f) + K(g) \tag{2}
\end{equation}</span></p>

<p>and in general I think we can demonstrate that: </p>

<p><span class="math-container">\begin{equation}
K(f_n \circ f_{n-1} \circ ... \circ f_1) \leq \sum_{i=1}^n K(f_i) \tag{3}
\end{equation}</span></p>

<p>However, my intuition also suggests that this is probably not the best upper bound and I am also curious about tight lower bounds. </p>

<p>Might there be a general theorem that gives the best possible upper and lower bounds? </p>

<reference-request><kolmogorov-complexity>
Kolmogorov Complexity of the composition of two computable functions
Aidan Rocke
# Kolmogorov Complexity of the composition of two computable functions

(Asked by: username_0 on 2020-01-08)

Let's suppose we encode two computable functions $f$ and $g$ as binary strings so $f,g \in \{0,1\}^\*$. What I am curious about is whether we can find good upper and lower bounds for:

\begin{equation}
K(f \circ g) \tag{1}
\end{equation}

where $K(\cdot)$ denotes Kolmogorov Complexity.

My intuition suggests that we can compress each function separately and therefore:

\begin{equation}
K(f \circ g) \leq K(f) + K(g) \tag{2}
\end{equation}

and in general I think we can demonstrate that:

\begin{equation}
K(f\_n \circ f\_{n-1} \circ ... \circ f\_1) \leq \sum\_{i=1}^n K(f\_i) \tag{3}
\end{equation}

However, my intuition also suggests that this is probably not the best upper bound and I am also curious about tight lower bounds.

Might there be a general theorem that gives the best possible upper and lower bounds?

**Tags:** reference-request, kolmogorov-complexity

---

## 1 answers

### Answer by username_1 on 2020-01-08. Score: 2 | Accepted answer

Your bound is correct, for exactly the reasons you give. It is also unimprovable in general. Suppose that each function is multiplication by a large constant, where both constants are subwords of some infinite incomprehensible sequence. If you could compress the composition, you would be able to compress at least one of the constants—a contradiction.

Edit: You might need to pay additional bits for the composition, as for ordered pairings -- as observed by Emil Jeřábek in the comments.

> **Comments:**
> **username_0**: There is a related question I am interested in which I shared on the MathOverflow: https://mathoverflow.net/questions/350014/the-expressiveness-of-functions-computable-on-trees  
> **username_0**: I am not sure whether I should have shared it on the Theoretical Computer Science stackexchange instead because I felt that it could be of interest to many mathematicians.  
> **username_2**: Wouldn't there be a logarithmic overhead to separate the descriptions of $f$ and $g$? Or is this prefix-free Kolmogorov complexity?  
> **username_1**: You may be right -- I was focusing more on the lower bound. In my example (with the two integers), it seems one can get away without the log overhead?..  
> **username_2**: There are certainly examples where you need much less. For example, if $g$ is addition of a large constant, and $f$ is subtraction of the same constant, then $f\circ g$ is just the identity. The question is what is true for general $f$ and $g$, not for a particular example.  
> **username_1**: Yes. I'd be interested to know the answer.  
> **username_2**: Actually, I don’t see why you’d get away without overhead even in the multiplication example. While it may be less in particular cases, I don’t see in general how to encode the product of two integers shorter than by supplying a (constant-size) description of a multiplication algorithm together with the pair of the numbers. The overhead is needed to encode pairs.  
> **username_2**: Function composition should be no easier than ordered pairs. Given functions $f(x)$ and $g(x)$, let $f'$ and $g'$ be the functions $f'(x)=(f(x),x)$ and $g'((x,y))=(x,g(y))$. Then $K(f')=K(f)+O(1)$, $K(g')=K(g)+O(1)$, and $K((f,g))\le K(g'\circ f')+O(1)$.  

---

