Decomposing functions of many variables to functions of one variable
Suppose you have a computer that can evaluate and compose continuous functions of one real variable and can do addition. What kinds of functions could you compute with it? You could compute functions of one variable by definition, but could you bootstrap it to compute functions of two variables?
Here's an example that shows this computer might be more useful than it seems at first glance. We said it can do addition, but can it multiply? Indeed it can [1].
We can decompose the function
into
where
So multiplication of two variables can be decomposed into the addition and composition of functions of one variable. What other functions of two variables can be decomposed this way? What about functions of three or more variables?
The Kolmogorov-Arnol'd theorem says that all continuous functions, of however many variables you like, can be decomposed this way.
Here is the original version of the Kolmogorov-Arnol'd theorem from 1957:
Let f : [0,1]n R be an arbitrary multivariate continuous function. Then it has the representation
where the univariate functions q and q,p are continuous and defined on the real line. Furthermore the q,p can be chosen independent of f.
Later refinements showed that it is possible to get by with a single outer function depending on f , but independent of q [1].
The original theorem was not constructive, but later Jurgen Braun and Michael Griebel gave a constructive proof [2].
References- Sidney A. Morris. Hilbert 13: Are there any genuine continuous multivariate real-valued functions?" Journal: Bull. Amer. Math. Soc. DOI: https://doi.org/10.1090/bull/1698. Posted online July 6, 2020
- Jurgen Braun, Michael Griebel. On a Constructive Proof of Kolmogorov's Superposition Theorem. Constructive Approximation 30, 653 (2009). https://doi.org/10.1007/s00365-009-9054-2