## Motivation:

Let's define a function computable on a $k$-ary tree as a function composed with simpler computable functions defined at each node such that a function of this kind defined on a binary tree of depth $N$ receives $2^{N-1}$ inputs:

While thinking about the expressiveness of functions $F_k^N$ computable on $k$-ary trees it occurred to me that the 'combinatorial power' of such functions must grow exponentially as a function of tree depth. This would be very nice because it's natural to execute parallel algorithms with $O(N)$ time complexity on $k$-ary trees with depth $N$.

Intuitively, if there are $k^n$ functions at the nth level the expressiveness for $F_k^N$ on a tree of depth $N$ should grow on the order of:

\begin{equation} \sim k^N \tag{1} \end{equation}

Might there be a theorem which expresses this idea using algorithmic information theory(i.e. Kolmogorov Complexity)?

## Probabilistic argument using Kolmogorov Complexity:

If $F_k^N$ is a composition of functions in $S$ where $\lvert S \rvert = \frac{k^{N}-1}{k-1}$ and $K(\cdot)$ denotes Kolmogorov Complexity then we may define:

\begin{equation} Q = \min_{f_i \in S} K(f_i) \tag{2} \end{equation}

and we may show that for almost all $F_k^N$ we must have:

\begin{equation} K(F_k^N) \geq \frac{Q}{2} \cdot k^{N-1} \tag{3} \end{equation}

**Proof:**

Let's suppose each $f_i \in S$ has an encoding as a binary string so $\forall i, f_i \in \{0,1\}^*$. If we compress each $f_i$ then $F_k^N$ is reduced to a program of length greater than:

\begin{equation} n= Qk^{N -1} \tag{4} \end{equation}

Now, the number of programs of length less than or equal to $\frac{n}{2}$ is given by:

\begin{equation} \sum_{l=1}^{\frac{n}{2}} 2^l \leq 2^{\frac{n}{2}+1}-1 \tag{5} \end{equation}

and so, using the principle of maximum entropy(i.e. uniform distribution) [4], we find that:

\begin{equation} \lim_{n \to \infty} P(K(F_k^N) \geq \frac{n}{2}) \geq \lim_{n \to \infty} 1 - \frac{2^{\frac{n}{2}}}{2^n} = 1 \tag{6} \end{equation}

## Question:

My question is whether this result (3) in the setting of algorithmic information theory may be significantly improved upon and whether there might be other interesting results of this kind.

## References:

- Vladimir I Arnold. Representation of continuous functions of three variables by the superposition of continuous functions of two variables. Collected Works: Representations of Functions, Celestial Mechanics and KAM Theory, 1957–1965, pages 47–133, 2009.
- Roozbeh Farhoodi, Khashayar Filom, Ilenna Simone Jones, Konrad Paul Kording. On functions computed on trees. Arxiv. 2019.
- M. Li and P. Vitányi. An Introduction to Kolmogorov Complexity and Its Applications. Graduate Texts in Computer Science. Springer, New York, second edition, 1997.
- Edwin Jaynes. Information Theory and Statistical Mechanics. The Physical Review. Vol. 106. No 4. 620-630. May 15, 1957.