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?

  • $\begingroup$ 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? $\endgroup$
    – 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.

  • $\begingroup$ 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.... $\endgroup$
    – kakaz
    Aug 16 '17 at 17:40
  • 1
    $\begingroup$ 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. $\endgroup$
    – Dirk
    Aug 16 '17 at 18:13
  • $\begingroup$ 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. $\endgroup$
    – kakaz
    Aug 17 '17 at 5:41
  • $\begingroup$ 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. $\endgroup$
    – kakaz
    Aug 17 '17 at 5:45
  • 2
    $\begingroup$ I added a longer explanation. $\endgroup$
    – Dirk
    Aug 17 '17 at 10:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.