Kolmogorov-Arnold theorem

The Kolmogorov – Arnold theorem — a theorem from the analysis of a real variable and the theory of approximations , states that each multidimensional continuous function can be represented as a superposition of continuous functions of one variable. It solves in a more general form the thirteenth problem of Hubert . ^[1] ^[2]

The works of Andrei Kolmogorov and Arnold established that if f is a multidimensional continuous function, then f can be written as a finite composition of continuous functions of one variable and a binary addition operation . ^[3] Namely,

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).

{\ displaystyle 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).}

{\ displaystyle 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).}

The construction of evidence, and even more concrete constructions, can be found in the work of Brown and Griebel ^[4] .

In a sense, Kolmogorov and Arnold showed that the only true function of many variables is addition, since all other functions can be written using functions of one variable and addition. ^[five]

Content

History

The Kolmogorov-Arnold theorem is closely related to the 13th Hubert problem . In his Paris lecture at the International Congress of Mathematicians in 1900, David Gilbert formulated 23 problems that, in his opinion, were important for the further development of mathematics. ^[6] In the 13th of these problems, the task was to solve the general equations of higher degrees. It is known that for algebraic equations of degree 4, the solution can be calculated using formulas that contain only radicals and arithmetic operations. For higher orders , the Galois theory shows that solutions of algebraic equations cannot be expressed in terms of basic algebraic operations. It follows from the Chirngauz transformations that the general algebraic equation

x^{n}+a_{n-1}x^{n-1}+\dots +a_{0}=0

{\ displaystyle x ^ {n} + a_ {n-1} x ^ {n-1} + \ dots + a_ {0} = 0}

can be converted into a form $y^{n}+b_{n-4}y^{n-4}+\dots +b_{1}y+1=0$ ${\ displaystyle y ^ {n} + b_ {n-4} y ^ {n-4} + \ dots + b_ {1} y + 1 = 0}$ . The Chirngauz transformation is determined by a formula containing only radicals and arithmetic operations and transformations. Thus, the solution of an algebraic equation of degree $n$ ${\ displaystyle n}$ can be represented as a superposition of functions of two variables if $n<7$ ${\ displaystyle n <7}$ , and as a superposition of functions $n-4$ ${\ displaystyle n-4}$ variables if $n\geqslant 7$ ${\ displaystyle n \ geqslant 7}$ . For $n=7$ ${\ displaystyle n = 7}$ the solution is a superposition of arithmetic operations, radicals, and solutions of the equation $y^{7}+b_{3}y^{3}+b_{2}y^{2}+b_{1}y+1=0$ ${\ displaystyle y ^ {7} + b_ {3} y ^ {3} + b_ {2} y ^ {2} + b_ {1} y + 1 = 0}$ .

A further simplification of algebraic transformations seems to be impossible, which led to Hilbert's hypothesis that “the solution of a general equation of degree 7 cannot be represented as a superposition of continuous functions of two variables”. This explains the relation of the thirteenth Hilbert problem to the representation of multidimensional functions as a superposition of low-dimensional functions. In this context, it has stimulated numerous studies in the field of the theory of functions and other related problems by different authors. ^[7]

Variants of the Kolmogorov-Arnold theorem

A variant of the Kolmogorov theorem, which reduces the number of external functions $\Phi _{q}$ ${\ displaystyle \ Phi _ {q}}$ owned by George Lorenz. ^[8] He showed in 1962 that external functions $\Phi _{q}$ ${\ displaystyle \ Phi _ {q}}$ can be replaced by one function $\Phi$ ${\ displaystyle \ Phi}$ . More precisely, Lorentz proved the existence of functions. $\phi _{q,p}$ ${\ displaystyle \ phi _ {q, p}}$ , $q=0,1,\ldots ,2n$ ${\ displaystyle q = 0,1, \ ldots, 2n}$ , $p=1,\ldots ,n,$ ${\ displaystyle p = 1, \ ldots, n,}$ such that

f(\mathbf {x} )=\sum _{q=0}^{2n}\Phi \left(\sum _{p=1}^{n}\phi _{q,p}(x_{p})\right).

{\ displaystyle f (\ mathbf {x}) = \ sum _ {q = 0} ^ {2n} \ Phi \ left (\ sum _ {p = 1} ^ {n} \ phi _ {q, p} ( x_ {p}) \ right).}

Sprecher ^[9] replaced internal functions $\phi _{q,p}$ ${\ displaystyle \ phi _ {q, p}}$ by one internal function with a corresponding shift in its arguments. He proved that there are real values. $\eta ,\lambda _{1},\ldots ,\lambda _{n}$ ${\ displaystyle \ eta, \ lambda _ {1}, \ ldots, \ lambda _ {n}}$ continuous function $\Phi \colon \mathbb {R} \to \mathbb {R}$ ${\ displaystyle \ Phi \ colon \ mathbb {R} \ to \ mathbb {R}}$ and real increasing continuous function $\phi \colon [0,1]\to [0,1]$ ${\ displaystyle \ phi \ colon [0,1] \ to [0,1]}$ with $\phi \in \operatorname {Lip} {\big (}\ln 2/\ln(2N+2){\big )}$ ${\ displaystyle \ phi \ in \ operatorname {Lip} {\ big (} \ ln 2 / \ ln (2N + 2) {\ big)}}$ for $N\geqslant n\geqslant 2$ ${\ displaystyle N \ geqslant n \ geqslant 2}$ such that

f(\mathbf {x} )=\sum _{q=0}^{2n}\Phi \left(\sum _{p=1}^{n}\lambda _{p}\phi (x_{p}+\eta q)+q\right).

{\ displaystyle f (\ mathbf {x}) = \ sum _ {q = 0} ^ {2n} \ Phi \ left (\ sum _ {p = 1} ^ {n} \ lambda _ {p} \ phi ( x_ {p} + \ eta q) + q \ right).}

Phillip A. Ostrand ^[10] generalized Kolmogorov's theorem to compact metric spaces. For $p=1,\ldots ,m$ ${\ displaystyle p = 1, \ ldots, m}$ let be $X_{p}$ ${\ displaystyle X_ {p}}$ - compact metric spaces of finite dimension $n_{p}$ ${\ displaystyle n_ {p}}$ , let it go $n=\sum _{p=1}^{m}n_{p}$ ${\ displaystyle n = \ sum _ {p = 1} ^ {m} n_ {p}}$ . Then there is a continuous function. $\phi _{q,p}\colon X_{p}\to [0,1],\ q=0,\ldots ,2n,\ p=1,\ldots ,m$ ${\ displaystyle \ phi _ {q, p} \ colon X_ {p} \ to [0,1], \ q = 0, \ ldots, 2n, \ p = 1, \ ldots, m}$ and continuous functions $G_{q}\colon [0,1]\to \mathbb {R} ,\ q=0,\ldots ,2n$ ${\ displaystyle G_ {q} \ colon [0,1] \ to \ mathbb {R}, \ q = 0, \ ldots, 2n}$ such that any continuous function $f\colon X_{1}\times \dots \times X_{m}\to \mathbb {R}$ ${\ displaystyle f \ colon X_ {1} \ times \ dots \ times X_ {m} \ to \ mathbb {R}}$ representable as

f(x_{1},\ldots ,x_{m})=\sum _{q=0}^{2n}G_{q}\left(\sum _{p=1}^{m}\phi _{q,p}(x_{p})\right).

{\ displaystyle f (x_ {1}, \ ldots, x_ {m}) = \ sum _ {q = 0} ^ {2n} G_ {q} \ left (\ sum _ {p = 1} ^ {m} \ phi _ {q, p} (x_ {p}) \ right).}

Original links

Andrei Kolmogorov , “On the representation of continuous functions of several variables by superpositions of continuous functions of a smaller number of variables”, Izvestiya AS USSR , 108 (1956), p. 179-182; English translation: Amer. Math Soc. Transl., 17 (1961), p. 369-373.
Vladimir Arnold , “On the function of three variables,” Proceedings of the Academy of Sciences of the USSR , 114 (1957), p. 679-681; English translation: Amer. Math Soc. Transl. 28 (1963), p. 51–54.

Links

↑ Arnold: Swimming Against the Tide : [ eng ] . - American Mathematical Society , 2014. - P. 165. - ISBN 978-1-4704-1699-7 .
↑ Shigeo Akashi. Application of ent-entropy theory to Kolmogorov — Arnold representation theorem (Eng.) // Reports on Mathematical Physics : journal. - 2001. - Vol. 48 . - P. 19—26 . - DOI : 10.1016 / S0034-4877 (01) 80060-4 .
↑ Bar-Natan. Dessert: Hilbert's 13th Problem, in Full Color (Eng.) .
↑ Jürgen Braun, Michael Griebel. On a constructive proof of Kolmogorov's superposition theorem (Eng.) // Constructive Approximation : journal. - 2009. - Vol. 30 - P. 653 . - DOI : 10.1007 / s00365-009-9054-2 .
↑ Persi Diaconis, Mehrdad Shahshahani. On Linear Functions of Linear Combinations (English) // SIAM J. Sci. Stat. Comput. : journal. - 1984. - Vol. 5 - P. 180 . - DOI : 10.1137 / 0905013 .
↑ David . Mathematical problems (English) // Bulletin of the American Mathematical Society : journal. - 1902. - Vol. 8 - P. 461-462 .
↑ Jürgen Braun. On Kolmogorov's Superposition Theorem and Its Applications. - SVH Verlag, 2010. - 192 p.
↑ George; Lorentz. Metric entropy, widths, and superpositions of functions (English) // American Mathematical Monthly : journal. - 1962. - Vol. 69 - P. 469-485 .
↑ David A. Sprecher. On the structure of continuous functions of several variables (Eng.) // Transactions of the American Mathematical Society : journal. - 1965. - Vol. 115 - P. 340—355 .
↑ Phillip A. Ostrand. Dimension of metric spaces and Hilbert's problem 13 (Eng.) // Bulletin of the American Mathematical Society : journal. - 1965. - Vol. 71 - P. 619-622 .

[1] Arnold: Swimming Against the Tide : [ eng ] . - American Mathematical Society , 2014. - P. 165. - ISBN 978-1-4704-1699-7 .

[2] Shigeo Akashi. Application of ent-entropy theory to Kolmogorov — Arnold representation theorem (Eng.) // Reports on Mathematical Physics : journal. - 2001. - Vol. 48 . - P. 19—26 . - DOI : 10.1016 / S0034-4877 (01) 80060-4 .

[h13-3] Bar-Natan. Dessert: Hilbert's 13th Problem, in Full Color (Eng.) .

[4] Jürgen Braun, Michael Griebel. On a constructive proof of Kolmogorov's superposition theorem (Eng.) // Constructive Approximation : journal. - 2009. - Vol. 30 - P. 653 . - DOI : 10.1007 / s00365-009-9054-2 .

[dia-5] Persi Diaconis, Mehrdad Shahshahani. On Linear Functions of Linear Combinations (English) // SIAM J. Sci. Stat. Comput. : journal. - 1984. - Vol. 5 - P. 180 . - DOI : 10.1137 / 0905013 .

[6] David . Mathematical problems (English) // Bulletin of the American Mathematical Society : journal. - 1902. - Vol. 8 - P. 461-462 .

[7] Jürgen Braun. On Kolmogorov's Superposition Theorem and Its Applications. - SVH Verlag, 2010. - 192 p.

[8] George; Lorentz. Metric entropy, widths, and superpositions of functions (English) // American Mathematical Monthly : journal. - 1962. - Vol. 69 - P. 469-485 .

[9] David A. Sprecher. On the structure of continuous functions of several variables (Eng.) // Transactions of the American Mathematical Society : journal. - 1965. - Vol. 115 - P. 340—355 .

[10] Phillip A. Ostrand. Dimension of metric spaces and Hilbert's problem 13 (Eng.) // Bulletin of the American Mathematical Society : journal. - 1965. - Vol. 71 - P. 619-622 .