Kolmogorov-Arnold theorem for (just-)functions

Question

There is famous Kolmogorov-Arnold theorem for continuous functions composition - continuous function of several variables can be composed of continuous functions of two variables.

Specialization of such theorem into smooth functions is false: there is no similar composition obeying smoothness - that is there are smooth functions of several variables that cannot be composed of smooth function of 2 variables.

Take a look here: Kolmogorov superposition for smooth functions

There is an obvious way around: generalization and even grand generalization.

Generalization: Is Kolmogorov-Arnold theorem true for just functions ( non-continuous)?

If above question is interesting we may ask for Grand Generalization: Let KA(f, X) means the following hypothesis: given object f of some class containing several variables ( function, relation, rules of inference etc), and characteristics X ( continuous, transitive etc) valid for such class of objects, is it possible to compose every object of class f as finite number of objects of the same class with 2 variables with the same characteristic X?

Is there something known for Grand Generalization K(f,X) for various f and X?

Answer 1

The answer is yes for functions $f:[0,1]^n\to\mathbb{R}$: Any such function can be written as $$ f(x_1,\dots,x_n) = g\Big(\sum_{i=1}^n h_i(x_i)\Big). $$ The proof is pretty simple: The $h_i$ should "spread out" the digits of the $x_i$ by $n$ places such that $\sum_{i=1}^n h_i(x_i)$ contains all the digits of all the $x_i$. Thus, the argument that is passed to $g$ contains the same information that the arguments of the function $f$ contain.

I've seen this proof in some lecture notes about deep learning - that's one field where Kolmogorov's Theorem was heavily discussed in the 1980s, see Girosi and Poggio's note

Representation properties of networks: Kolmogorov's theorem is irrelevant F Girosi, T Poggio - Neural Computation, 1989 - MIT Press

Edit: Here is more fleshed out version of the proof.

The $h_i$ should "spread out" the digits as follows: Let us denote the inputs by $x^1,\dots,x^n$ and their digits by $$ \begin{split} x^1 & = 0.x^1_1 x^1_2\dots\\ x^2 & = 0.x^2_1 x^2_2\dots\\ \vdots &\\ x^n & = x^n_1 x^n_2\dots \end{split}. $$ Then the $h_i$ work as follows $$ \begin{split} h_1(x^1) & = 0.x^1_1 0 \dots 0 x^1_2 0\dots 0 x^1_3 0\dots\\ h_2(x^2) & = 0.0 x^2_1 0\dots 0 x^2_2 0 \dots 0 x^2_3 0\dots\\ h_3(x^3) & = 0.0 0 x^3_1 0\dots 0 x^3_2 0 \dots 0 x^3_3 0\dots\\ \end{split} $$ with $n-1$ zeros between digits. Then $$ \sum_{i=1}^n h_i(x^i) = 0.x^1_1x^2_1\dots x^n_1 x^1_2 x^2_2\dots x^n_2\dots $$ i.e., this number contains all the digits of all the numbers $x^1,\dots,x^n$. Now define $g$ of this number as $f(x_1,\dots,x_2)$. Since the "interlacing map" $(x^1,\dots,x^n) \mapsto \sum_i h_i(x^i)$ is bijective, such a $g$ exists.