On Hilbert's thirteenth problem and related questions

A. G. Vitushkin

Trudy Matematicheskogo Instituta imeni V.A. Steklova, Tome 59 (2004) no. 1, pp. 11-25

Résumé

Hilbert's thirteenth problem involves the study of solutions of algebraic equations. The object is to obtain a complexity estimate for an algebraic function. As of now, the problem remains open. There are only a few partial algebraic results in this connection, but at the same time the problem has stimulated a series of studies in the theory of functions with their subsequent applications. The most brilliant result in this cycle is Kolmogorov's theorem on superpositions of continuous functions.

Bibliographie

[1] K. V. Kim, Yu. E. Nesterov, B. V. Cherkasskii, “O trudoemkosti vychisleniya gradienta”, Dokl. AN SSSR, 275:6 (1984), 1306–1309 | MR | Zbl

[2] D. Hilbert, “Mathematische Probleme”, Nachr. Akad. Wiss. Göttingen, 1900, 253–297 ; Gesammelte Abhandlungen, 3, Springer, Berlin, 1935, 290–329 | Zbl

[3] D. Hilbert, “Über die Gleichung neunten Grades”, Math. Ann., 97 (1927), 243–250 ; Gesammelte Abhandlungen, 2, Springer, Berlin, 1933, 393–400 | DOI | MR

[4] A. Wiman, “Über die Anwendung der Tschirnhausen-Transformation auf die Reduktion algebraischer Gleichungen”, Nova Acta Soc. Sci. Upsal., 1928, 3–8

[5] N. G. Chebotarëv, “Nekotorye voprosy v svyazi s problemoi rezolvent”, Sbornik statei po problemam rezolvent, 1, 1949, 255–340

[6] Kolmogorov. Yubileinoe izdanie. Kn. 2. “Etikh strok beguschikh tesma ...”. Izbrannye mesta iz perepiski A. N. Kolmogorova i P. S. Aleksandrova, red.-sost. A. N. Shiryaev, Fizmatlit, M., 2003

[7] A. N. Kolmogorov, “O predstavlenii nepreryvnykh funktsii neskolkikh peremennykh superpozitsiyami nepreryvnykh funktsii odnogo peremennogo i slozheniya”, Dokl. AN SSSR, 114:5 (1957), 953–956 | MR

[8] A. G. Vitushkin, “Dokazatelstvo suschestvovaniya analiticheskikh funktsii mnogikh peremennykh, ne predstavimykh lineinymi superpozitsiyami nepreryvno differentsiruemykh funktsii menshego chisla peremennykh”, Dokl. AN SSSR, 156:6 (1964), 1258–1261 | MR | Zbl

[9] N. G. Chebotarëv, “O probleme rezolvent”, Uchen. zap. Kazan. gos. un-ta, 114 (1954), 189–193 | MR

[10] V. V. Morozov, “Nekotorye voprosy v svyazi s problemoi rezolvent”, Uchen. zap. Kazan. gos. un-ta, 114 (1954), 173–187 | MR

[11] A. G. Khovanskii, “O superpozitsiyakh golomorfnykh funktsii s radikalami”, UMN, 26:3 (1971), 213–214 | MR | Zbl

[12] A. G. Khovanskii, “O predstavimosti funktsii v kvadraturakh”, UMN, 26:4 (1971), 251–252 | MR

[13] L. Bieberbach, “Bemerkung zum dreizehnten Hilbertschen Problem”, J. Reine Angew. Math., 165 (1931), 89–92 | Zbl

[14] A. Ostrowski, “Über Dirichletsche Reihen und algebraische Differentialgleichungen”, Math. Z., 8 (1920), 241–298 | DOI | MR | Zbl

[15] A. G. Vitushkin, “Polveka – kak odin den”, UMN, 57:1 (2002), 191–206 | MR

[16] A. G. Vitushkin, “K trinadtsatoi probleme Gilberta”, Dokl. AN SSSR, 96:4 (1954), 701–704 | MR

[17] A. G. Vitushkin, “Nekotorye otsenki dlya variatsii mnozhestv”, Dokl. AN SSSR, 95:3 (1954), 433–434 | MR | Zbl

[18] A. G. Vitushkin, “On representation of functions by means of superpositions and related topics”, Enseign. Math. (2), 23:3–4 (1977), 255–320 | MR | Zbl

[19] A. N. Kolmogorov, “O predstavlenii nepreryvnykh funktsii neskolkikh peremennykh superpozitsiyami nepreryvnykh funktsii menshego chisla peremennykh”, Dokl. AN SSSR, 108:2 (1956), 179–182 | MR

[20] A. S. Kronrod, “O funktsiyakh dvukh peremennykh”, UMN, 5:1 (1950), 24–134 | MR | Zbl

[21] V. I. Arnold, “O funktsiyakh trekh peremennykh”, Dokl. AN SSSR, 114:4 (1957), 679–681 | MR

[22] V. I. Arnold, “O predstavlenii funktsii neskolkikh peremennykh v vide superpozitsii funktsii menshego chisla peremennykh”, Matem. prosveschenie, 1958, no. 3, 41–61 | Zbl

[23] V. I. Arnold, “O predstavlenii nepreryvnykh funktsii trekh peremennykh superpozitsiyami funktsii dvukh peremennykh”, Matem. sb., 48:1 (1959), 3–74 | MR

[24] Yu. P. Ofman, “O nailuchshem priblizhenii funktsii dvukh peremennykh funktsiyami vida $\varphi(x)+\psi(y)$”, Izv. AN SSSR. Ser. matem., 25:2 (1961), 239–252 | MR | Zbl

[25] V. P. Motornyi, “K voprosu o nailuchshem priblizhenii funktsii dvukh peremennykh funktsiyami vida $\varphi(x)+\psi(y)$”, Izv. AN SSSR. Ser. matem., 27:6 (1963), 1211–1214 | MR | Zbl

[26] G. M. Khenkin, “O vlozhenii prostranstva $s$-gladkikh funktsii $n$ peremennykh v prostranstvo dostatochno gladkikh funktsii menshego chisla peremennykh”, Dokl. AN SSSR, 153:1 (1963), 57–60 | MR | Zbl

[27] R. Doss, “On the representation of the continuous functions of two variables by means of addition and continuous functions of one variable”, Colloq. Math., 10 (1963), 249–259 | MR | Zbl

[28] A. G. Vitushkin, “Nekotorye svoistva lineinykh superpozitsii gladkikh funktsii”, Dokl. AN SSSR, 156:5 (1964), 1003–1006 | MR | Zbl

[29] G. M. Khenkin, “O lineinykh superpozitsiyakh nepreryvno differentsiruemykh funktsii”, Dokl. AN SSSR, 157:2 (1964), 288–290 | MR | Zbl

[30] D. A. Sprecher, “On the structure of continuous functions of several variables”, Trans. Amer. Math. Soc., 115 (1965), 340–355 | DOI | MR | Zbl

[31] D. A. Sprecher, “On the structure of representation of continuous functions of several variables as finite sums of continuous functions of one variable”, Proc. Amer. Math. Soc., 17 (1966), 98–105 | DOI | MR | Zbl

[32] A. G. Vitushkin, “O vozmozhnosti predstavleniya funktsii superpozitsiyami funktsii menshego chisla peremennykh”, Trudy mezhdunarodnogo kongressa matematikov (Moskva, 1966), Nauka, M., 1968, 322–329

[33] L. A. Bassalygo, “O predstavlenii nepreryvnykh funktsii dvukh peremennykh pri pomoschi nepreryvnykh funktsii odnogo peremennogo”, Vestnik MGU. Ser. 1. Matem., mekh., 1966, no. 21, 58–63 | MR | Zbl

[34] B. L. Fridman, “Uluchshenie gladkosti funktsii v teoreme A. N. Kolmogorova o superpozitsiyakh”, Dokl. AN SSSR, 177:5 (1967), 1019–1022 | MR | Zbl

[35] A. G. Vitushkin, G. M. Khenkin, “Lineinye superpozitsii funktsii”, UMN, 22:1 (1967), 77–124 | MR | Zbl

[36] A. G. Vitushkin, “K trinadtsatoi probleme Gilberta”, Problemy Gilberta, Nauka, M., 1969, 163–170

[37] B. L. Fridman, “Nigde ne plotnost prostranstva lineinykh superpozitsii funktsii neskolkikh peremennykh”, Izv. AN SSSR. Ser. matem., 36:4 (1972), 814–846 | MR | Zbl

[38] J.-P. Kahane, “Sur le théorème de superposition de Kolmogorov”, J. Approx. Theory, 13:3 (1975), 229–234 | DOI | MR | Zbl

[39] G. G. Lorentz, “The 13th problem of Hilbert”, Proc. Sympos. Pure Math., 28 (1976), 419–430 | MR | Zbl

[40] V. Lin, “Superpozitsii algebraicheskikh funktsii”, Funkts. analiz i ego pril., 10:1 (1976), 37–45 | MR | Zbl

[41] A. A. Milyutin, “Izomorfnost prostranstv nepreryvnykh funktsii nad kompaktami kontinualnoi moschnosti”, Teoriya funktsii, funkts. analiz i ikh pril., 1966, no. 2, 150–156 | MR

[42] A. G. Vitushkin, “Variatsii funktsii mnogikh peremennykh i dostatochnye usloviya dlya ikh ogranichennosti”, Dokl. AN SSSR, 96:6 (1954), 1089–1091 | MR | Zbl

[43] A. G. Vitushkin, O mnogomernykh variatsiyakh, GITTL, M., 1955

[44] L. D. Ivanov, Variatsii mnozhestv i funktsii, Nauka, M., 1975 | MR

[45] I. G. Petrovskii, O. A. Oleinik, “O topologii deistvitelnykh algebraicheskikh poverkhnostei”, Izv. AN SSSR. Ser. matem., 13:5 (1949), 389–402 | MR | Zbl

[46] O. A. Oleinik, “Otsenki chisel Betti deistvitelnykh algebraicheskikh giperpoverkhnostei”, Matem. sb., 28:3 (1952), 635–640

[47] A. N. Kolmogorov, “Otsenki minimalnogo chisla elementov $\varepsilon$-setei v razlichnykh funktsionalnykh klassakh i ikh primenenie k voprosu o predstavimosti funktsii neskolkikh peremennykh superpozitsiyami funktsii menshego chisla peremennykh”, UMN, 10:1 (1955), 192–194 | Zbl

[48] A. N. Kolmogorov, “O nekotorykh asimptoticheskikh kharakteristikakh vpolne ogranichennykh metricheskikh prostranstv”, Dokl. AN SSSR, 108:3 (1956), 385–388 | MR | Zbl

[49] A. N. Kolmogorov, A. M. Yaglom, I. M. Gelfand, “Kolichestvo informatsii i entropiya dlya nepreryvnykh raspredelenii”, Trudy 3-go Vsesoyuznogo matematicheskogo s'ezda (Moskva, 1956), t. III: Obzornye doklady, Izd-vo AN SSSR, M., 1958, 300–320

[50] A. G. Vitushkin, “Absolyutnaya $\varepsilon$-entropiya metricheskikh prostranstv”, Dokl. AN SSSR, 117:2 (1957), 145–148

[51] V. M. Tikhomirov, “Ob $\varepsilon$-entropii nekotorykh klassov analiticheskikh funktsii”, Dokl. AN SSSR, 117:2 (1957), 191–194 | MR | Zbl

[52] A. Pełczyński, “On the approximation of $S$-spaces by finite dimentional spaces”, Bull. Acad. Polon. Sci. Cl. III, 5:9 (1957), 879–881 | MR

[53] A. N. Kolmogorov, “O lineinoi razmernosti topologicheskikh vektornykh prostranstv”, Dokl. AN SSSR, 120:2 (1958), 239–242 | MR

[54] K. I. Babenko, “Ob entropii odnogo klassa analiticheskikh funktsii”, Nauchn. dokl. vysshei shkoly. Ser. fiz.-matem. nauk., 1958, no. 2, 9–16 | Zbl

[55] V. D. Erokhin, “O konformnykh preobrazovaniyakh kolets i ob osnovnom bazise prostranstva funktsii, analiticheskikh v elementarnoi okrestnosti proizvolnogo kontinuuma”, Dokl. AN SSSR, 120:4 (1958), 689–692 | MR | Zbl

[56] V. D. Erokhin, “Ob asimptotike $\varepsilon$-entropii analiticheskikh funktsii”, Dokl. AN SSSR, 120:5 (1958), 949–952 | MR | Zbl

[57] V. D. Erokhin, “O nailuchshem priblizhenii analiticheskikh funktsii posredstvom ratsionalnykh drobei so svobodnymi polyusami”, Dokl. AN SSSR, 128:1 (1959), 29–32 | MR | Zbl

[58] A. N. Kolmogorov, V. M. Tikhomirov, “$\varepsilon$-entropiya i $\varepsilon$-emkost mnozhestv v funktsionalnykh prostranstvakh”, UMN, 14:2 (1959), 3–86 | MR

[59] Yu. A. Brudnyi, A. F. Timan, “Konstruktivnye kharakteristiki kompaktnykh mnozhestv v prostranstva Banakha i $\varepsilon$-entropiya”, Dokl. AN SSSR, 126:5 (1959), 927–930 | MR | Zbl

[60] N. S. Bakhvalov, “O priblizhennom vychislenii kratnykh integralov”, Vestnik MGU, 1959, no. 4, 3–18 | MR

[61] V. M. Tikhomirov, “Poperechniki mnozhestv v funktsionalnykh prostranstvakh i teoriya nailuchshikh priblizhenii”, UMN, 15:3 (1960), 81–120 | MR | Zbl

[62] S. A. Smolyak, “$\varepsilon$-entropiya klassov $E^{\alpha,k}_s(B)$ i $W^\alpha_s(B)$ v metrike $L_2$”, Dokl. AN SSSR, 131:1 (1960), 30–33 | MR

[63] B. S. Mityagin, “Svyaz mezhdu $\varepsilon$-entropiei, skorostyu approksimatsii i yadernostyu kompakta v lineinom prostranstve”, Dokl. AN SSSR, 134:4 (1960), 765–768 | MR | Zbl

[64] V. Ya. Pan, “Ob approksimatsii analiticheskikh funktsii ratsionalnymi”, UMN, 16:5 (1961), 159–197

[65] B. S. Mityagin, “Approksimativnaya razmernost i bazisy v yadernykh prostranstvakh”, UMN, 16:4 (1961), 63–132 | MR | Zbl

[66] C. Bessaga, A. Pełczyńcki, S. Rolewicz, “Approximative dimension of linear topological spaces and some of its applications. (Summary of a report)”, Studia Math. (Ser. Specjalna) Zeszyt., 1 (1963), 27–29 | MR | Zbl

[67] N. S. Bakhvalov, “Ob otsenke kolichestva vychislitelnoi raboty, neobkhodimoi pri priblizhennom reshenii zadach”, S. K. Godunov, V. S. Ryabenkii, Vvedenie v teoriyu raznostnykh skhem, Fizmatgiz, M., 1962, 316–329 | MR

[68] N. S. Bakhvalov, “O skorosti skhodimosti nedeterminirovannykh kvadraturnykh protsessov na klassakh funktsii $W^{(l)}_p$”, Teoriya veroyatn. i ee primen., 7:2 (1962), 238

[69] G. G. Lorentz, “Lower bounds for the degree of approximation”, Trans. Amer. Math. Soc., 97:1 (1960), 25–34 | DOI | MR | Zbl

[70] G. G. Lorentz, “Metric entropy, widths, and superpositions of functions”, Amer. Math. Monthly, 69 (1962), 469–485 | DOI | MR | Zbl

[71] V. M. Tikhomirov, “Raboty A. N. Kolmogorova po $\varepsilon$-entropii funktsionalnykh klassov i superpozitsiyam funktsii”, UMN, 18:5 (1963), 55–92 | MR | Zbl

[72] N. M. Korobov, Teoretiko-chislovye metody v priblizhennom analize, Fizmatgiz, M., 1963 | MR

[73] S. A. Smolyak, “Kvadraturnye interpolyatsionnye formuly na tenzornykh proizvedeniyakh nekotorykh klassov funktsii”, Dokl. AN SSSR, 148:5 (1963), 1042–1045 | MR | Zbl

[74] Yu. A. Brudnyi, B. D. Kotlyar, “O poryadke rosta $\varepsilon$-entropii na nekotorykh kompaktnykh klassakh funktsii”, Dokl. AN SSSR, 148:5 (1963), 1001–1004 | MR | Zbl

[75] Yu. P. Ofman, “O priblizhennoi realizatsii nepreryvnykh funktsii na avtomatakh”, Dokl. AN SSSR, 152:4 (1963), 823–826 | MR | Zbl

[76] H. S. Shapiro, “Some negative theorems of approximation theory”, Michigan Math. J., 11:3 (1964), 211–217 | DOI | MR | Zbl

[77] P. A. Ostrand, “Dimension of metric Spaces and Hilbert's problem 13”, Bull. Amer. Math. Soc., 71:4 (1965), 619–622 | DOI | MR | Zbl

[78] A. G. Vitushkin, V. I. Buslaev, “Otsenka dliny koda signalov s konechnym spektrom v svyazi s zadachami zvukozapisi”, Izv. AN SSSR. Ser. matem., 38:4 (1974), 867–895 | MR | Zbl

[79] V. V. Zmushko, “Entropiya klassa tselykh funktsii s chastotno-zavisimoi metrikoi”, Izv. AN SSSR. Ser. matem., 40:5 (1976), 1173–1186 | MR | Zbl

[80] A. G. Vitushkin, “Nekotorye otsenki iz teorii tabulirovaniya”, UMN, 12:2 (1957), 227–228

[81] A. G. Vitushkin, “Nekotorye otsenki iz teorii tabulirovaniya”, Dokl. AN SSSR, 114:5 (1957), 923–926 | MR | Zbl

[82] A. G. Vitushkin, “O nailuchshikh priblizheniyakh differentsiruemykh i analiticheskikh funktsii”, Dokl. AN SSSR, 119:3 (1958), 418–420 | MR | Zbl

[83] A. G. Vitushkin, Otsenka slozhnosti zadachi tabulirovaniya, Fizmatgiz, M., 1959

[84] V. A. Kotelnikov, “O propusknoi sposobnosti “efira” i provoloki v elektrosvyazi”, Materialy k 1-mu Vsesoyuznomu s'ezdu po voprosam rekonstruktsii dela svyazi i razvitiya slabotochnoi promyshlennosti, Upravlenie svyazi RKKA, M., 1933

[85] C. E. Shannon, “A mathematical theory of communication”, Bell. System Tech. J., 27 (1948), 379–423; 623–656 | MR

[86] A. N. Kolmogorov, “Teoriya peredachi informatsii”, Sessiya AN SSSR po nauchnym problemam avtomatizatsii proizvodstva. T. 1: Plenarnye zasedaniya, Izd-vo AN SSSR, M., 1957, 66–99

[87] A. G. Vitushkin, “Coding of signals with finite spectrum and sound recording problems”, Proceedings of the International Congress of Mathematicians (Vancouver, 1974), 1, Canad. Math. Congress, Montréal, 1975, 221–226 | MR