At the 1900 International Congress of Mathematicians, David Hilbert presented a list of 23 problems that would shape the century to come. His thirteenth asked, in essence, a deceptively simple question : are there functions of several variables that cannot be built from functions of fewer variables ? Half a century later, in a two-page note, Andrey Kolmogorov gave a breathtaking answer : every continuous function of many variables is a superposition of continuous functions of a single variable and addition. Nothing more than univariate functions and $+$ is ever needed. This post tells that story, unpacks the structure of the theorem, and follows the surprising thread that ties it to modern neural networks.

1. Hilbert’s thirteenth problem

Some functions of two variables are obviously reducible. The product $xy$, for instance, hides a univariate skeleton :

\[\begin{equation} xy = \exp\big( \ln x + \ln y \big), \qquad x, y > 0, \label{eq:product} \end{equation}\]

so multiplication is really just addition of logarithms wrapped inside an exponential, i.e. a superposition of the univariate functions $\ln$ and $\exp$. Hilbert asked whether this kind of reduction is always possible. Concretely, he conjectured that the solution of the general seventh-degree equation, viewed as a function of three of its coefficients, could not be written using only continuous functions of two variables. He expected an impossibility result.

Mathematics rarely obliges our intuitions. In 1957 Kolmogorov (Kolmogorov, 1957), building on and then dramatically simplifying work with his student Vladimir Arnold (Arnold, 1957) ¹, proved the opposite of what Hilbert anticipated : not only are two variables enough, a single variable is enough, provided we are allowed to add.

2. The theorem

For every integer $n \geq 2$ there exist continuous functions $\phi_{q,p} : [0,1] \rightarrow \Bbb{R}$, for $q = 0, \dots, 2n$ and $p = 1, \dots, n$, such that every continuous function $ƒ : [0,1]^{n} \rightarrow \Bbb{R}$ can be represented in the form $$ \begin{equation} ƒ(x_{1}, \dots, x_{n}) = \sum_{q=0}^{2n} \Phi_{q}\!\left( \sum_{p=1}^{n} \phi_{q,p}(x_{p}) \right), \label{eq:kolmogorov} \end{equation} $$ where the outer functions $\Phi_{q} : \Bbb{R} \rightarrow \Bbb{R}$ are continuous and depend on $ƒ$.

Read this slowly, because every symbol is carrying weight. The inner functions $\phi_{q,p}$ act on a single coordinate $x_{p}$ at a time. Their outputs are summed, coordinate by coordinate, into $2n+1$ scalars $z_{q} = \sum_{p} \phi_{q,p}(x_{p})$. Each scalar is then reshaped by a single outer function $\Phi_{q}$, and the $2n+1$ results are added. The entire multivariate complexity of $ƒ$ has been squeezed into univariate maps and two rounds of addition.

In plain words : no matter how complicated a recipe is, Kolmogorov says you can cook it using only single-ingredient preparations and the act of piling things together. Each $\phi_{q,p}$ processes one “ingredient” (one coordinate) on its own ; you add up the results, run them through the $\Phi_q$, and add again. Nothing ever has to combine two inputs in a genuinely two-dimensional way.

The structure is easiest to see as a graph. The following diagram traces the flow for $n = 2$ : two inputs, $2n + 1 = 5$ inner units, five outer units, one sum.

Figure 1 - Kolmogorov's representation for $n=2$. Each input passes through inner univariate maps $\phi_{q,p}$ (green), the coordinate contributions are summed into $z_q$, reshaped by outer maps $\Phi_q$ (orange), and finally added. The animated dashes suggest the direction of the computation.

If this picture reminds you of something, that is not an accident, and we will return to it in the last section.

3. What makes it remarkable

Three features of $\eqref{eq:kolmogorov}$ deserve to be highlighted, because each one defies a natural expectation.

We call the $\phi_{q,p}$ the inner (or universal) functions and the $\Phi_{q}$ the outer functions. A representation is said to be universal when the inner functions can be chosen once and for all, independently of the target $ƒ$, so that only the outer functions have to adapt.

• A fixed number of terms. The outer sum always has exactly $2n + 1$ terms, no matter how wild $ƒ$ is. The complexity of $ƒ$ is absorbed entirely by the shape of the univariate functions, never by their number.

• Universality of the inner functions. In the sharper forms due to Lorentz, Sprecher and others (Sprecher, 1965), the inner functions $\phi_{q,p}$ (and even a single monotone $\phi$ with rational shifts) can be fixed before $ƒ$ is known. They form a kind of universal coordinate system into which any continuous function can be poured ; only the $\Phi_{q}$ then encode $ƒ$.

• Continuity without smoothness. The functions produced by the theorem are continuous but, in general, extremely irregular : they are typically nowhere differentiable, fractal-like objects. Vitushkin later showed that if one insists on smoothness (continuous derivatives), the reduction genuinely fails, which is why Hilbert’s intuition was not entirely misplaced, it was merely aimed at the wrong regularity class.

The exponential trick $\eqref{eq:product}$ is a baby version of the phenomenon : the two-variable function $xy$ is expressed through the univariate $\ln$ and $\exp$ and one addition. Kolmogorov's theorem asserts that a decomposition of this flavour, though far less explicit, exists for every continuous $ƒ$ on the cube, not just for the analytically lucky ones.

4. A non-constructive miracle

It is tempting to ask for the functions. Here the theorem turns coy : its original proof is an existence argument. It guarantees that suitable $\phi_{q,p}$ and $\Phi_{q}$ exist, but the classical constructions produce functions of formidable irregularity, defined as limits of carefully nested approximations. Explicit and numerically usable constructions of the inner functions were only obtained much later, notably by Sprecher and, more recently, through the algorithm of Braun and Griebel (Braun & Griebel, 2009), which finally made the decomposition computable to a prescribed accuracy.

So the theorem is best read as a statement about what is possible in principle. It tells us that the barrier Hilbert imagined, dimensionality as an irreducible source of complexity, simply is not there for continuous functions. Whether that possibility can be exploited is a separate, and much harder, story, a tension we already met with the Universal Approximation Theorem.

5. The neural-network connection

Look again at Figure 1. Inputs feed a first layer of univariate transformations, the results are summed, a second layer of univariate transformations is applied, and everything is added. That is precisely the shape of a two-layer feedforward network : the inner functions play the role of the first hidden layer, the outer functions the role of the second.

This resemblance was made explicit by Hecht-Nielsen (Hecht-Nielsen, 1987), who observed that Kolmogorov’s theorem can be phrased as the existence of an exact four-layer “Kolmogorov network” computing any continuous $ƒ$. For a while this was advertised as a theoretical foundation for neural networks : here, it seemed, was a proof that networks can represent anything, and with a fixed, tiny width of $2n+1$ units.

The enthusiasm needed tempering. Girosi and Poggio (Girosi & Poggio, 1989) pointed out the catch : the outer functions $\Phi_{q}$ depend on $ƒ$ in a wholly non-constructive and highly non-smooth way, so they are nothing like the fixed, simple activation functions (a sigmoid, a ReLU) used in real networks. Kolmogorov’s theorem hands you an exact representation but with pathological building blocks ; the Universal Approximation Theorem hands you an approximation with benign, tunable building blocks. They are complementary lenses on the same question, how much can univariate non-linearities and addition achieve, and neither one, on its own, explains why deep learning works in practice.

6. Conclusion

Kolmogorov’s superposition theorem is one of those results that quietly rearranges your sense of what is possible. A question that Hilbert framed as a search for irreducible multivariate complexity turned out to have the most economical answer imaginable : univariate functions and addition suffice, always, for continuous functions on a cube. The price is regularity, the ingredients are fractal, non-constructive, and unfriendly to computation, which is exactly why the theorem informs, but does not by itself explain, the practical success of the layered architectures it so eerily prefigures. It is a bridge between a 1900 problem list and a 21st-century machine, built entirely out of one-dimensional pieces.

References

1. Arnold, V. I. (1957). On Functions of Three Variables. Doklady Akademii Nauk SSSR, 114, 679–681.
   @article{Arnold1957,
     author = {Arnold, Vladimir I.},
     title = {On Functions of Three Variables},
     journal = {Doklady Akademii Nauk SSSR},
     volume = {114},
     pages = {679--681},
     year = {1957}
   }
   

2. Braun, J., & Griebel, M. (2009). On a Constructive Proof of Kolmogorov’s Superposition Theorem. Constructive Approximation, 30(3), 653–675.
   @article{Braun2009,
     author = {Braun, J{\"u}rgen and Griebel, Michael},
     title = {On a Constructive Proof of Kolmogorov's Superposition Theorem},
     journal = {Constructive Approximation},
     volume = {30},
     number = {3},
     pages = {653--675},
     year = {2009},
     publisher = {Springer}
   }
   

3. Girosi, F., & Poggio, T. (1989). Representation Properties of Networks: Kolmogorov’s Theorem Is Irrelevant. Neural Computation, 1(4), 465–469.
   @article{Girosi1989,
     author = {Girosi, Federico and Poggio, Tomaso},
     title = {Representation Properties of Networks: Kolmogorov's Theorem Is Irrelevant},
     journal = {Neural Computation},
     volume = {1},
     number = {4},
     pages = {465--469},
     year = {1989},
     publisher = {MIT Press}
   }
   

4. Hecht-Nielsen, R. (1987). Kolmogorov’s Mapping Neural Network Existence Theorem. Proceedings of the IEEE International Conference on Neural Networks, 3, 11–14.
   @inproceedings{HechtNielsen1987,
     author = {Hecht-Nielsen, Robert},
     title = {Kolmogorov's Mapping Neural Network Existence Theorem},
     booktitle = {Proceedings of the IEEE International Conference on Neural Networks},
     volume = {3},
     pages = {11--14},
     year = {1987}
   }
   

5. Kolmogorov, A. N. (1957). On the Representation of Continuous Functions of Many Variables by Superposition of Continuous Functions of One Variable and Addition. Doklady Akademii Nauk SSSR, 114, 953–956.
   @article{Kolmogorov1957,
     author = {Kolmogorov, Andrey N.},
     title = {On the Representation of Continuous Functions of Many Variables by Superposition of Continuous Functions of One Variable and Addition},
     journal = {Doklady Akademii Nauk SSSR},
     volume = {114},
     pages = {953--956},
     year = {1957}
   }
   

6. Sprecher, D. A. (1965). On the Structure of Continuous Functions of Several Variables. Transactions of the American Mathematical Society, 115, 340–355.
   @article{Sprecher1965,
     author = {Sprecher, David A.},
     title = {On the Structure of Continuous Functions of Several Variables},
     journal = {Transactions of the American Mathematical Society},
     volume = {115},
     pages = {340--355},
     year = {1965},
     publisher = {American Mathematical Society}
   }
   

1. Arnold first settled the three-variable case of Hilbert’s problem in 1957 ; Kolmogorov’s general superposition theorem, of which this post treats, appeared the same year and subsumed it. ↩