# Kolmogorov-Arnold theorem for (just-)functions

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.

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?

• From Wikipedia, the Kolmogorov-Arnold theorem seems to say that .... multi-variate functions can be composed of single-variable functions. Is there a mistake in your description?
– YKY
Feb 2 at 4:35

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.

• What if some x_i is irrational or rational with periodic but infinite decimal representation? Idea to "spread digits" seems to be not so easy to solve this problem as we are looking for finite number of functions in composition.... Aug 16 '17 at 17:40
• That's no problem. "Spreading" shall mean that insert $n-1$ zeros in between digits. You also say that $\sum h_i(x_i)$ has all the digits of the $x_i$ interlaced.
– Dirk
Aug 16 '17 at 18:13
• In the link You provided there is no more information than in Your answer, and definitely there is no proof. In notes about deep learning proof is as follows: Proof: Any single real number contains an infinite amount of information. Select h_i to spread out the digits of its argument so that ∑ i h i ( x i ) contains all the digits of all the x_i. QED. Aug 17 '17 at 5:41
• Sorry but I do not understand even what "information" means in this sentence. In second reference there is Theorem of Vituskin cited but it is about smooth functions, and it do don't apply in general case. Aug 17 '17 at 5:45
• I added a longer explanation.
– Dirk
Aug 17 '17 at 10:16