# Expressing any f(x,y) using only addition and unary functions?

Suppose we have a continuous function $f:R^2\rightarrow R$. I was told of the following remarkable theorem: $f$ can be expressed as the composition of continuous unary functions (that is, functions from $R\rightarrow R$) and addition.

Could anyone give me a reference (or name) for this theorem?

-

## 3 Answers

This is "due in successively more exact forms to Kolmogorov, Arnol'd and a succession of mathematicians ending with Kahane", to quote T.W. Korner on the subject.

I am informed that the proof I met is prepared using:

J.-P. Kahane Sur le treizieme probleme de Hilbert, le theoreme de superposition de Kolmogorov et les sommes algebriques d'arcs croissants in the conference proceedings Harmonic analysis, Iraklion 1978 Springer 1980

G. G. Lorenz, Approximation of functions Chelsea Publishing Co. 1986 (First Ed. 1966)

A. G. Vituskin On the representation of functions by superpositions and related topics in L'Enseignement Mathématique, 1977, Vol 23, pages 255-320

[This is all from these skeleton notes (no proofs) here (Links to pdf; See Chapter 1 and Chapter 11 for references)]

-
Thanks for the link! –  Andres Caicedo Sep 1 '10 at 15:11

I think this was proven by Kolmogorov. See the following reference: A. N. Kolmogorov, “On the representation of continuous functions of several variables by superpositions of continuous functions of one variable and addition”, Dokl. Akad. Nauk SSSR 114 (1957), 953–956; English transl., Amer. Math. Soc. Transl. (2) 28 (1963), 55–59.

-

I find it interesting that this theorem is used as a theoretical basis for neural networks. I had never heard this before.

Věra Kůrková, Kolmogorov's theorem and multilayer neural networks 1992

-
There seems to be some debate on the relevance of Kolmogorov's theorem to learning theory. A rebuttal can be found in "Representation Properties of Networks: Kolmogorov's Theorem is Irrelevant" by Girosi and Poggio, 1989. A PDF copy is online here: cbcl.mit.edu/projects/cbcl/people/poggio/journals/… –  Bill Bradley Sep 7 '10 at 13:03
I was thinking along the same lines. It would guess that the functions postulated by Kolmogorov's theorem would be smooth only in simple cases. Thanks. –  dls Sep 8 '10 at 15:29