View source for Kolmogorov–Arnold representation theorem

{{short description|Multivariate functions can be written using univariate functions and summing}}
In [[real analysis]] and [[approximation theory]], the '''Kolmogorov–Arnold representation theorem''' (or '''superposition theorem''') states that every [[Multivariable calculus|multivariate]] [[Continuity (mathematics)|continuous]] [[Function (mathematics)|function]] <math>f\colon[0,1]^n\to \R</math> can be represented as a [[superposition]] of continuous single-variable functions.

The works of [[Vladimir Arnold]] and [[Andrey Kolmogorov]] established that if ''f'' is a multivariate continuous function, then ''f'' can be written as a finite [[Function composition|composition]] of continuous functions of a single variable and the [[binary operation]] of [[addition]].<ref name="h13">{{cite web|last=Bar-Natan|first=Dror|authorlink=Dror Bar-Natan|title=Dessert: Hilbert's 13th Problem, in Full Colour|url=http://www.math.toronto.edu/drorbn/Talks/Fields-0911/}}</ref> More specifically,

:{{nowrap|<math> f(\mathbf x) = f(x_1,\ldots ,x_n) = \sum_{q=0}^{2n} \Phi_{q}\!\left(\sum_{p=1}^{n} \phi_{q,p}(x_{p})\right),</math>}}

where <math>\phi_{q,p}\colon[0,1]\to \R</math> and <math>\Phi_{q}\colon \R \to \R</math>.

There are proofs with specific constructions.<ref>{{Cite journal |last1=Braun |first1=Jürgen |last2=Griebel |first2=Michael |year=2009 |title=On a constructive proof of Kolmogorov's superposition theorem |journal=[[Constructive Approximation]] |language=en |volume=30 |issue=3 |pages=653–675 |doi=10.1007/s00365-009-9054-2}}</ref>

It solved a more constrained form of [[Hilbert's thirteenth problem]], so the original Hilbert's thirteenth problem is a corollary.<ref>{{cite book|first1=Boris A.|last1= Khesin|author2-link=Sergei Tabachnikov|first2=Serge L. |last2=Tabachnikov|title=Arnold: Swimming Against the Tide|url=https://books.google.com/books?id=aBWHBAAAQBAJ&pg=PA165|year=2014|publisher=[[American Mathematical Society]]|isbn=978-1-4704-1699-7|page=165|author1-link=Boris Khesin}}</ref><ref name="Akashi">{{Cite journal |last=Akashi |first=Shigeo |year=2001|title=Application of ϵ-entropy theory to Kolmogorov—Arnold representation theorem |journal=[[Reports on Mathematical Physics]] |language=en |volume=48 |issue=1–2 |pages=19–26 |doi=10.1016/S0034-4877(01)80060-4}}</ref><ref name=":0">{{Cite journal|last=Morris|first=Sidney A.|date=2020-07-06|title=Hilbert 13: Are there any genuine continuous multivariate real-valued functions?|url=https://www.ams.org/bull/2021-58-01/S0273-0979-2020-01698-8/|journal=[[Bulletin of the American Mathematical Society]]|language=en|volume=58|issue=1|pages=107–118|doi=10.1090/bull/1698|issn=0273-0979|doi-access=free}}</ref> In a sense, they showed that the only true continuous multivariate function is the sum, since every other continuous function can be written using [[univariate]] continuous functions and summing.<ref name="dia">{{cite journal|first1=Persi |last1=Diaconis|author1-link=Persi Diaconis|first2= Mehrdad |last2=Shahshahani|title=On nonlinear functions of linear combinations|journal=[[SIAM Journal on Scientific Computing]]|year= 1984|volume=5|issue=1|pages=175&ndash;191|doi=10.1137/0905013 |url=http://statweb.stanford.edu/~cgates/PERSI/papers/nonlin_func.pdf|archive-url=https://web.archive.org/web/20170808221733/http://statweb.stanford.edu/~cgates/PERSI/papers/nonlin_func.pdf |archive-date=2017-08-08 }}</ref>{{rp|180}}

==History==
The Kolmogorov–Arnold representation theorem is closely related to [[Hilbert's 13th problem]]. In his [[Paris]] lecture at the [[International Congress of Mathematicians]] in 1900, [[David Hilbert]] formulated [[Hilbert's problems|23 problems]] which in his opinion were important for the further development of mathematics.<ref>{{cite journal|first=David|last=Hilbert|authorlink=David Hilbert|title= Mathematical problems|journal=Bulletin of the American Mathematical Society|volume=8|issue=10|year=1902|pages=461–462|doi=10.1090/S0002-9904-1902-00923-3|doi-access=free}}</ref> The 13th of these problems dealt with the solution of general equations of higher degrees. It is known that for algebraic equations of degree 4 the solution can be computed by formulae that only contain radicals and arithmetic operations. For higher orders, [[Galois theory]] shows us that the solutions of algebraic equations cannot be expressed in terms of basic algebraic operations. It follows from the so called [[Tschirnhaus transformation]] that the general algebraic equation 
:<math>x^{n}+a_{n-1}x^{n-1}+\cdots +a_{0}=0</math>
can be translated to the form <math> y^{n}+b_{n-4}y^{n-4}+\cdots +b_{1}y+1=0</math>. The Tschirnhaus transformation is given by a formula containing only radicals and arithmetic operations and transforms. Therefore, the solution of an algebraic equation of degree <math>n</math>  can be represented as a superposition of functions of two variables if <math>n<7</math> and as a superposition of functions of <math>n-4</math> variables if <math>n\geq 7</math>. For <math>n=7</math>  the solution is a superposition of arithmetic operations, radicals, and the solution of the equation {{nowrap|<math>y^{7}+b_{3}y^{3}+b_{2}y^{2}+b_{1}y+1=0</math>.}}

A further simplification with algebraic transformations seems to be impossible which led to Hilbert's conjecture that "A solution of the general equation of degree 7 cannot be represented as a superposition of continuous functions of two variables". This explains the relation of [[Hilbert's thirteenth problem]] to the representation of a higher-dimensional function as superposition of lower-dimensional functions. In this context, it has stimulated many studies in the theory of functions and other related problems by different authors.<ref>Jürgen Braun, On Kolmogorov's Superposition Theorem and Its Applications, SVH Verlag, 2010, 192 pp.</ref>

==Variants==
A variant of Kolmogorov's theorem that reduces the number of
outer functions <math>\Phi_{q}</math> is due to [[George G. Lorentz|George Lorentz]].<ref>{{cite journal|first=G. G.|last=Lorentz|title=Metric entropy, widths, and superpositions of functions|journal=[[American Mathematical Monthly]]|volume=69 |issue=6|year=1962|pages=469–485 |doi=10.1080/00029890.1962.11989915}}</ref> He showed in 1962  that the outer functions <math>\Phi_{q}</math> can be replaced by a single function <math>\Phi</math>. More precisely, Lorentz proved the existence of functions <math>\phi _{q,p}</math>, <math>q=0,1,\ldots, 2n</math>, <math>p=1,\ldots,n,</math> such that 

:<math> f(\mathbf x) = \sum_{q=0}^{2n} \Phi\!\left(\sum_{p=1}^{n} \phi_{q,p}(x_{p})\right).</math>

David Sprecher <ref>{{cite journal | doi=10.2307/1994273 | jstor=1994273 | title=On the Structure of Continuous Functions of Several Variables | last1=Sprecher | first1=David A. | journal=Transactions of the American Mathematical Society | date=1965 | volume=115 | pages=340–355 }}</ref> replaced the inner functions <math>\phi_{q,p}</math> by one single inner function with an appropriate shift in its argument. He proved that there exist real values <math>\eta, \lambda_1,\ldots,\lambda_n</math>, a continuous function <math>\Phi\colon \mathbb{R} \rightarrow \R</math>, and a real increasing continuous function <math>\phi\colon [0,1] \rightarrow [0,1]</math> with <math>\phi \in \operatorname{Lip}(\ln 2/\ln (2N+2))</math>, for <math>N \geq n \geq 2</math>, such that

:<math> f(\mathbf x) = \sum_{q=0}^{2n} \Phi\!\left(\sum_{p=1}^{n} \lambda_p \phi(x_{p}+\eta q)+q \right).</math>

Phillip A. Ostrand <ref>{{cite journal|first=Phillip A.|last= Ostrand|title=Dimension of metric spaces and Hilbert's problem 13|journal= [[Bulletin of the American Mathematical Society]]|volume= 71 |issue= 4|year=1965|pages= 619–622|doi=10.1090/s0002-9904-1965-11363-5|doi-access= free}}</ref> generalized the Kolmogorov superposition theorem to compact metric spaces. For <math>p=1,\ldots,m</math> let <math>X_p</math> be compact metric spaces of finite dimension <math>n_p</math> and let <math>n = \sum_{p=1}^{m} n_p</math>. Then there exists continuous functions <math>\phi_{q,p}\colon X_p \rightarrow [0,1], q=0,\ldots,2n, p=1,\ldots,m</math> and continuous functions <math>G_q\colon [0,1] \rightarrow \R, q=0,\ldots,2n</math> such that any continuous function <math>f\colon X_1 \times \dots \times X_m \rightarrow \mathbb{R}</math> is representable in the form 

:<math> f(x_1,\ldots,x_m) = \sum_{q=0}^{2n} G_{q}\!\left(\sum_{p=1}^{m} \phi_{q,p}(x_{p})\right).</math>

Kolmogorov-Arnold representation theorem and its aforementioned variants also hold for discontinuous multivariate functions.<ref name="Ismailov">{{Cite journal |last=Ismailov |first=Vugar |year=2008|title=On the representation by linear superpositions |journal=[[Journal of Approximation Theory]] |language=en |volume=151 |issue=2 |pages=113–125 |doi=10.1016/j.jat.2007.09.003|arxiv=1501.05268 }}</ref>

==Continuous form==

In its classic form Kolmogorov-Arnold representation has two layers, where the first, called inner layer, is vector to vector mapping 

:<math> s_q = \sum_{p=1}^{n} \phi_{q,p}(x_{p}), \quad q=0,1,..,2n </math>

and the second, outer layer, is vector to scalar mapping

:<math> f(x_1, ... , x_m) = \sum_{q=0}^{2n} \Phi_q\left(s_q\right).</math>

The transition from discrete to continuous form for inner layer gives equation of Urysohn with 3D kernel

:<math> s(q) = \int_{p_1}^{p_2} F[x(p),p,q]dp, \quad q \in [q_1, q_2], </math>

same transition for the outer layer gives its particular case

:<math> f = \int_{q_1}^{q_2} G[s(q),q]dq. </math>

The generalization of Kolmogorov-Arnold representation known as Kolmogorov-Arnold network in continuous form 
is a chain of Urysohn equations, where outer equation also may return function or a vector as multiple related targets.

Urysohn equation was introduced in 1924 for a different purpose, as function to function mapping with the problem 
of finding function <math>x(p)</math>, provided <math>s(q)</math> and <math>F[x(p),p,q]</math>. 

==Limitations==

The theorem does not hold in general for complex multi-variate functions, as discussed here.<ref name="Akashi"/> Furthermore, the non-smoothness of the inner functions and their "wild behavior" has limited the practical use of the representation,<ref>{{cite journal | doi=10.1162/neco.1989.1.4.465 | title=Representation Properties of Networks: Kolmogorov's Theorem is Irrelevant | date=1989 | last1=Girosi | first1=Federico | last2=Poggio | first2=Tomaso | journal=Neural Computation | volume=1 | issue=4 | pages=465–469 }}</ref> although there is some debate on this.<ref>{{cite journal | doi=10.1162/neco.1991.3.4.617 | title=Kolmogorov's Theorem is Relevant | date=1991 | last1=Kůrková | first1=Věra | journal=Neural Computation | volume=3 | issue=4 | pages=617–622 | pmid=31167327 }}</ref>

== Applications ==
In the field of [[machine learning]], there have been various attempts to use [[neural networks]] modeled on the Kolmogorov–Arnold representation.<ref>{{cite journal |last1=Lin |first1=Ji-Nan |last2=Unbehauen |first2=Rolf |date=January 1993 |title=On the Realization of a Kolmogorov Network |journal=Neural Computation |volume=5 |pages=18–20 |doi=10.1162/neco.1993.5.1.18 |number=1}}</ref><ref>{{cite book |last=Köppen |first=Mario |title=Artificial Neural Networks — ICANN 2002 |date=2022 |isbn=978-3-540-44074-1 |series=Lecture Notes in Computer Science |volume=2415 |pages=474–479 |chapter=On the Training of a Kolmogorov Network |doi=10.1007/3-540-46084-5_77 |chapter-url=https://link.springer.com/chapter/10.1007/3-540-46084-5_77}}</ref><ref>[[arxiv:2404.19756|KAN: Kolmogorov-Arnold Networks.]] (Ziming Liu et al.)</ref><ref>{{Cite news |author=Manon Bischoff |date=May 28, 2024 |title=An Alternative to Conventional Neural Networks Could Help Reveal What AI Is Doing behind the Scenes |url=https://www.scientificamerican.com/article/an-alternative-to-conventional-neural-networks-could-help-reveal-what-ai-is/ |archive-url=https://archive.today/20240529122452/https://www.scientificamerican.com/article/an-alternative-to-conventional-neural-networks-could-help-reveal-what-ai-is/ |archive-date=May 29, 2024 |access-date=May 29, 2024 |newspaper=[[Scientific American]]}}</ref><ref>{{cite journal |last1=Ismayilova |first1=Aysu |last2=Ismailov |first2=Vugar |date=August 2024 |title=On the Kolmogorov Neural Networks |journal=Neural Networks |volume=176 | number=Article 106333 |doi=10.1016/j.neunet.2024.106333|pmid=38688072 |arxiv=2311.00049 }}</ref><ref>{{Cite news |author=Steve Nadis |date=September 11, 2024 |title=Novel Architecture Makes Neural Networks More Understandable |url=https://www.quantamagazine.org/novel-architecture-makes-neural-networks-more-understandable-20240911/ |newspaper=[[Quanta Magazine]]}}</ref><ref>{{cite journal |last1=Polar |first1=Andrew |last2=Poluektov |first2=Michael |date=March 2021 |title=A deep machine learning algorithm for construction of the Kolmogorov–Arnold representation |journal=Engineering Applications of Artificial Intelligence |volume=99 |doi=10.1016/j.engappai.2020.104137 |arxiv=2001.04652 }}</ref> In these works, the Kolmogorov–Arnold theorem plays a role analogous to that of the [[universal approximation theorem]] in the study of [[multilayer perceptron]]s.

== Proof ==

Here one example is proved. This proof closely follows.<ref>{{Cite journal |last=Morris |first=Sidney |date=January 2021 |title=Hilbert 13: Are there any genuine continuous multivariate real-valued functions? |url=https://www.ams.org/journals/bull/2021-58-01/S0273-0979-2020-01698-8/ |journal=Bulletin of the American Mathematical Society |language=English |volume=58 |issue=1 |pages=107–118 |doi=10.1090/bull/1698 |issn=0273-0979|doi-access=free }}</ref> A proof for the case of functions depending on two variables is given, as the generalization is immediate.

=== Setup ===

* Let <math display="inline">I</math> be the unit interval <math display="inline">[0, 1]</math>.
* Let <math display="inline">C[I]</math> be the set of continuous functions of type <math display="inline">[0, 1] \to \R</math>. It is a [[function space]] with [[Uniform norm|supremum norm]] (it is a [[Banach space]]).
* Let <math display="inline">f</math> be a continuous function of type <math display="inline">[0, 1]^2 \to \R</math>, and let <math display="inline">\|f\|</math> be the supremum of it on <math display="inline">[0, 1]^2</math>.
* Let <math display="inline">t</math> be a positive irrational number. Its exact value is irrelevant.

We say that a 5-tuple <math display="inline">(\phi_1, \dots, \phi_5) \in C[I]^5</math> is a Kolmogorov-Arnold tuple [[if and only if]] any <math display="inline">f \in C[I^2]</math> there exists a continuous function <math display="inline">g: \R \to \R</math>, such that <math display="block">
      f(x,y) = \sum_{i=1}^5 g(\phi_i(x) + t \phi_i(y))
      </math>In the notation, we have the following:

{{Math theorem|name=Theorem|note=|math_statement= 
The Kolmogorov–Arnold tuples make up an open and dense subset of <math display="inline">C[I]^5</math>.
}}

=== Proof ===

Fix a <math display="inline">f \in C[I^2]</math>. We show that a certain subset <math display="inline">U_f \subset C[I]^5</math> is open and dense: There exists continuous <math display="inline">g</math> such that <math display="inline">\|g\| < \frac{1.01}{7} \|f\|</math>, and <math display="block">
          \Big\| f(x,y) - \sum_{i=1}^5 g(\phi_i(x) + t \phi_i(y)) \Big\| < \frac{6.01}{7}  \|f\|
          </math>We can assume that <math display="inline">\|f\| = 1</math> with no loss of generality.

By continuity, the set of such 5-tuples is open in <math display="inline">C[I]^5</math>. It remains to prove that they are dense.

The key idea is to divide <math display="inline">[0, 1]^2</math> into an overlapping system of small squares, each with a unique address, and define <math display="inline">g</math> to have the appropriate value at each address.

==== Grid system ====
Let <math display="inline">\psi_1 \in C[I]</math>. For any <math display="inline">\epsilon > 0</math>, for all large <math display="inline">N</math>, we can discretize <math display="inline">\psi_1</math> into a continuous function <math display="inline">\phi_1</math> satisfying the following properties:

* <math display="inline">\phi_1</math> is constant on each of the intervals <math display="inline">[0/5N, 4/5N], [5/5N, 9/5N], \dots, [1-5/5N, 1-1/5N]</math>.

* These values are different rational numbers.
* <math display="inline">\|\psi_1 - \phi_1\| < \epsilon</math>.

This function <math display="inline">\phi_1</math> creates a grid address system on <math display="inline">[0, 1]^2</math>, divided into streets and blocks. The blocks are of form <math display="inline">[0/5N, 4/5N] \times [0/5N, 4/5N], [0/5N, 4/5N] \times [5/5N, 9/5N], \dots</math>.
[[File:Kolmogorov-Arnold grid.svg|thumb|304x304px|An example construction of <math>\phi</math> and the corresponding grid system.]]
Since <math display="inline">f</math> is continuous on <math display="inline">[0, 1]^2</math>, it is uniformly continuous. Thus, we can take <math display="inline">N</math> large enough, so that <math display="inline">f</math> varies by less than <math display="inline">1/7</math> on any block.

On each block, <math display="inline">\phi_1(x) + t \phi_1(y)</math> has a constant value. The key property is that, because <math display="inline">t</math> is irrational, and <math display="inline">\phi_1</math> is rational on the blocks, each block has a different value of <math display="inline">\phi_1(x) + t \phi_1(y)</math>. 

So, given any 5-tuple <math display="inline">(\psi_1, \dots, \psi_5)</math>, we construct such a 5-tuple <math display="inline">(\phi_1, \dots, \phi_5)</math>. These create 5 overlapping grid systems. 

Enumerate the blocks as <math display="inline">R_{i, r}</math>, where <math display="inline">R_{i,r}</math> is the <math display="inline">r</math> -th block of the grid system created by <math display="inline">\phi_i</math>. The address of this block is <math display="inline">a_{i, r} := \phi_i(x) + t \phi_i(y)</math>, for any <math display="inline">(x, y) \in R_{i, r}</math>. By adding a small and linearly independent irrational number (the construction is similar to that of the [[Hamel basis]]) to each of <math display="inline">(\phi_1, \dots, \phi_5)</math>, we can ensure that every block has a unique address.

By plotting out the entire grid system, one can see that every point in <math display="inline">[0, 1]^2</math> is contained in 3 to 5 blocks, and 2 to 0 streets.

==== Construction of ''g'' ====
For each block <math display="inline">R_{i, r}</math>, if <math display="inline">f > 0</math> on all of <math display="inline">R_{i, r}</math> then define <math display="inline">g(a_{i, r}) = +1/7</math>; if <math display="inline">f < 0</math> on all of <math display="inline">R_{i, r}</math> then define <math display="inline">g(a_{i, r}) = -1/7</math>. Now, linearly interpolate <math display="inline">g</math> between these defined values. It remains to show this construction has the desired properties.

For any <math display="inline">(x, y) \in I^2</math>, we consider three cases.

If <math display="inline">f(x, y) \in [1/7, 7/7]</math>, then by uniform continuity, <math display="inline">f > 0</math> on every block <math display="inline">R_{i, r}</math> that contains the point <math display="inline">(x, y)</math>. This means that <math display="inline">g = 1/7</math> on 3 to 5 of the blocks, and have an unknown value on 2 to 0 of the streets. Thus, we have <math display="block">
              \sum_{i=1}^5 g(\phi_i(x) + t \phi_i(y)) \in [1/7, 5/7]
              </math> giving<math display="block">
              \Big| f(x,y) - \sum_{i=1}^5 g(\phi_i(x) + t \phi_i(y)) \Big| \in [0, 6/7]
              </math>Similarly for <math display="inline">f(x, y) \in [-7/7, -1/7]</math>.

If <math display="inline">f(x, y) \in [-1/7, 1/7]</math>, then since <math display="inline">\|g\| \leq 1/7</math>, we still have <math display="block">
              \Big| f(x,y) - \sum_{i=1}^5 g(\phi_i(x) + t \phi_i(y)) \Big| \in [0, 6/7]
              </math>

==== Baire category theorem ====
Iterating the above construction, then applying the [[Baire category theorem]], we find that the following kind of 5-tuples are open and dense in <math>
           C[I]^5
          </math>: There exists a sequence of <math display="inline">g_1, g_2, \dots</math> such that <math display="inline">\|g_1\| < \frac{1.01}{7} \|f\|</math>, <math display="inline">\|g_2\| < \frac{1.01}7 \frac{6.01}7 \|f\|</math>, etc. This allows their sum to be defined: <math display="inline">g := \sum_n g_n</math>, which is still continuous and bounded, and it satisfies <math display="block">
           f(x,y) = \sum_{i=1}^5 g(\phi_i(x) + t \phi_i(y)) 
          </math>Since <math display="inline">C[I^2]</math> [[Separable space|has a countable dense subset]], we can apply the Baire category theorem again to obtain the full theorem.

=== Extensions ===
The above proof generalizes for <math display="inline">n</math>-dimensions: Divide the cube <math display="inline">[0, 1]^n</math> into <math display="inline">(2n+1)</math> interlocking grid systems, such that each point in the cube is on <math display="inline">(n+1)</math> to <math display="inline">(2n + 1)</math> blocks, and <math display="inline">0</math> to <math display="inline">n</math> streets. Now, since <math display="inline">(n+1) > n</math>, the above construction works.

Indeed, this is the best possible value.

{{Math theorem|name=Theorem|note=Sternfeld, 1985 <ref>{{Cite journal |last=Sternfeld |first=Y. |date=1985-03-01 |title=Dimension, superposition of functions and separation of points, in compact metric spaces |url=https://link.springer.com/article/10.1007/BF02761117 |journal=Israel Journal of Mathematics |language=en |volume=50 |issue=1 |pages=13–53 |doi=10.1007/BF02761117 |issn=1565-8511}}</ref>
|math_statement= 
Let <math display="inline">X</math> be a compact metric space with <math display="inline">\operatorname{dim} X \geq 2</math>, and let <math display="inline">X \subset \R^m</math> be an embedding such that every <math display="inline">f \in C[X]</math> can be represented as

<math display="block">
f\left(x_1, x_2, \ldots, x_m\right)=\sum_{i=1}^m g_i\left(x_i\right), \quad\left(x_1, x_2, \ldots, x_m\right) \in X, \quad g_i \in C[\R].
</math>

Then <math display="inline">m \geq 2 \operatorname{dim} X+1</math>.
}}

A relatively short proof is given in <ref>{{Cite journal |last=Levin |first=Michael |date=1990-06-01 |title=Dimension and superposition of continuous functions |url=https://link.springer.com/article/10.1007/BF02807868 |journal=Israel Journal of Mathematics |language=en |volume=70 |issue=2 |pages=205–218 |doi=10.1007/BF02807868 |issn=1565-8511}}</ref> via [[dimension theory]].

In another direction of generality, more conditions can be imposed on the Kolmogorov–Arnold tuples.

{{Math theorem|name=Theorem|note=
|math_statement= 
There exists a Kolmogorov–Arnold tuple where each function is strictly monotonically increasing.
}}

The proof is given in.<ref>{{cite book |first=Torbjörn |last=Hedberg |chapter=Appendix 2: The Kolmogorov superposition theorem |title=Topics in Approximation Theory |editor-last=Shapiro |editor-first=Harold S. |series=Lecture Notes in Mathematics |publisher=Springer |volume=187 |orig-year=1971 |pages=267–275, (33– of PDF) |isbn=978-3-540-36497-9 |doi=10.1007/BFb0058976 |date=2006 |chapter-url=https://link.springer.com/content/pdf/bbm:978-3-540-36497-9/1}}</ref>

(Vituškin, 1954)<ref>{{cite journal |first=A.G. |last=Vituškin |title=On Hilbert's Thirteenth Problem |language=ru |journal=Doklady Akad. Nauk SSSR (N.S.) |volume=95 |issue=4 |year=1954 |pages=701–4}}</ref> showed that the theorem is false if we require all functions <math>f, g,\phi_i</math> to be continuously differentiable. The theorem remains true if we require all <math>\phi_i</math> to be 1-[[Lipschitz continuous]].<ref name=":0" />

==References==
{{reflist}}

==Sources==
*[[Andrey Kolmogorov]], "On the representation of continuous functions of several variables by superpositions of continuous functions of a smaller number of variables", ''[[Proceedings of the USSR Academy of Sciences]]'', 108 (1956), pp.&nbsp;179–182; English translation: [https://bookstore.ams.org/view?ProductCode=TRANS2/17 ''Amer. Math. Soc. Transl.'', "17: Twelve Papers on Algebra and Real Functions" (1961)], pp.&nbsp;369–373. 
*[[Vladimir Arnold]], "On functions of three variables", ''[[Proceedings of the USSR Academy of Sciences]]'', 114 (1957), pp.&nbsp;679–681; English translation: [https://bookstore.ams.org/view?ProductCode=TRANS2/28 ''Amer. Math. Soc. Transl.'', "28: Sixteen Papers on Analysis" (1963)], pp.&nbsp;51–54. [https://link.springer.com/chapter/10.1007/978-3-642-01742-1_2 SpringerLink]
*Vladimir Arnold, "On the representation of continuous functions of three variables as superpositions of continuous functions of two variables", ''Dokl. Akad. Nauk. SSSR'' 114:4 (1957), pp. 679–681 (in Russian) [https://link.springer.com/chapter/10.1007/978-3-642-01742-1_6 SpringerLink]
*Andrey Kolmogorov, "On the representation of continuous functions of several variables as superpositions of continuous functions of one variable and addition", (1957); English translation: [https://bookstore.ams.org/view?ProductCode=TRANS2/28 ''Amer. Math. Soc. Transl.'', "28: Sixteen Papers on Analysis" (1963)], [https://cs.uwaterloo.ca/~y328yu/classics/Kolmogorov57.pdf PDF]

==Further reading==
*S. Ya. Khavinson, ''Best Approximation by Linear Superpositions (Approximate Nomography)'', AMS Translations of Mathematical Monographs (1997)

{{DEFAULTSORT:Kolmogorov-Arnold representation theorem}}
[[Category:Theorems in real analysis]]
[[Category:Functions and mappings]]
[[Category:Theorems in approximation theory]]