Embed Size (px)
Citation preview
Kolmogorov’s Heritage in Mathematics
Picture taken from the Kolmogorov Archive with kind permission of A.N. Shiryaev
Éric Charpentier · Annick LesneNikolaï K. Nikolski (Eds.)
Kolmogorov’s Heritagein Mathematics
With 22 Figures
���
Éric CharpentierInstitut de MathématiquesUniversité Bordeaux 1351 cours de la Libération33405 Talence [email protected]
Annick LesneLaboratoire de Physique Théoriquede la Matière CondenséeUniversité Pierre et Marie CurieCase 121, Tour 24-25 - 4ème étage, pièce 4074 Place Jussieu75252 ParisFrance
And
Institut des Hautes Études ScientifiquesLe Bois-Marie, 35 route de Chartres91440 [email protected]
Nikolaï K. NikolskiInstitut de MathématiquesUniversité Bordeaux 1351 cours de la Libération33405 Talence [email protected]
Édition originale: L’héritage de Kolmogorov en mathématiques c© Éditions Belin – 2004Ouvrage publié avec le concours du Ministère français chargé de la culture – Centre national du livreThis edition was supported by the French Ministry of Culture – Centre national du livre
Cover picture taken from the Kolmogorov Archive with kind permission of A. N. Shiryaev
Library of Congress Control Number: 2007923591
ISBN 978-3-540-36349-1 Springer Berlin Heidelberg New York
This work is subject to copyright. All rights are reserved, whether the whole or part of the material isconcerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting,reproduction on microfilm or in any other way, and storage in data banks. Duplication of this publicationor parts thereof is permitted only under the provisions of the German Copyright Law of September 9,1965, in its current version, and permission for use must always be obtained from Springer. Violationsare liable for prosecution under the German Copyright Law.
Springer is a part of Springer Science+Business Mediaspringer.comc© Springer-Verlag Berlin Heidelberg 2007
The use of general descriptive names, registered names, trademarks, etc. in this publication does not imply,even in the absence of a specific statement, that such names are exempt from the relevant protective lawsand regulations and therefore free for general use.
Typesetting: by the authors and Integra, India using a Springer LATEX macro packageCover design: WMX-Design, Heidelberg
Printed on acid-free paper SPIN: 11775072 5 4 3 2 1 0
Contents
IntroductionEric Charpentier, Annick Lesne, and Nikolaı Nikolski . . . . . . . . . . . . . . . . . 1
1 The youth of Andrei Nikolaevich and Fourier seriesJean-Pierre Kahane . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 Kolmogorov’s contribution to intuitionistic logicThierry Coquand . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3 Some aspects of the probabilistic workLoıc Chaumont, Laurent Mazliak, and Marc Yor . . . . . . . . . . . . . . . . . . . . . 41
4 Infinite-dimensional Kolmogorov equationsGiuseppe Da Prato . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5 From Kolmogorov’s theorem on empirical distribution tonumber theoryKevin Ford . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
6 Kolmogorov’s ε-entropy and the problem of statisticalestimationMikhail Nikouline and Valentin Solev . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
7 Kolmogorov and topologyVictor M. Buchstaber . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
8 Geometry and approximation theoryin A. N. Kolmogorov’s worksVladimir M. Tikhomirov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
9 Kolmogorov and population dynamicsKarl Sigmund . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
VI Contents
10 Resonances and small divisorsEtienne Ghys . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
11 The KAM TheoremJohn H. Hubbard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
12 From Kolmogorov’s work on entropy of dynamical systemsto non-uniformly hyperbolic dynamicsDenis V. Kosygin and Yakov G. Sinai . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
13 From Hilbert’s 13th Problem to the theory of neuralnetworks: constructive aspects of Kolmogorov’s SuperpositionTheoremVasco Brattka . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
14 Kolmogorov complexityBruno Durand and Alexander Zvonkin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
15 Algorithmic chaos and the incompressibility methodPaul Vitanyi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301
List of Contributors
Vasco BrattkaLaboratory of Foundational Aspectsof Computer ScienceDepartment of Mathematicsand Applied MathematicsUniversity of Cape TownSouth Africahttp://cca-net.de/vasco
Victor M. BuchstaberSteklov Mathematical Institute ofRussian Academy of Sciences, andMoscow State University, Russiahttp://www.mi.ras.ru/∼buchstab
and School of Mathematics, TheUniversity of Manchester, UK,[email protected]
Loıc ChaumontLaboratoire Angevin de Rechercheen Mathematiques (LAREMA)University of Angers, Francehttp://math.univ-angers.fr/∼chaumont
loic.chaumont@univ- angers.fr
Thierry CoquandDepartment of Computer Scienceand Engineering
Chalmers University of Technologyand Goteborg UniversitySwedenhttp://www.cs.chalmers.se/∼coquand
Giuseppe Da PratoScuola Normale SuperiorePisa, Italyhttp://www.sns.it/scienze/menunews/
docentiscienze/daprato
Bruno DurandLaboratoire d’informatique fonda-mentale de MarseilleUniversity of Provence (Aix-Marseille I), Francehttp://www.lif.univ-mrs.fr/∼bdurand
Kevin FordDepartment of MathematicsUniversity of Illinois at Urbana-Champaign, USAhttp://www.math.uiuc.edu/∼ford
Etienne GhysUnite de mathematiques pures etappliquees (UMPA)
VIII List of Contributors
CNRS and Ecole normale superieurede Lyon, Francehttp://www.umpa.ens-lyon.fr/∼ghys
John H. HubbardDepartment of MathematicsCornell University, Ithaca, NY, USAhttp://www.math.cornell.edu/People/
Faculty/hubbard.html
J.-P. KahaneDepartement de Mathematiquesd’OrsayUniversity Paris-sud, Orsay, Francehttp://www.academie-sciences.fr/
Membres/K/Kahane JP.htm
Denis V. KosyginCourant Institute of MathematicalSciencesNew York University, [email protected]
Laurent MazliakLaboratoire de Probabilites etModeles AleatoiresInstitut de mathematiques de JussieuUniversity Paris VI, Francehttp://www.proba.jussieu.fr/users/
lma/mazliak.html
Mikhaıl Nikouline (M. Nikulin)Statistique Mathematique et sesApplicationsUniversity Victor Segalen (Bor-deaux II), Francehttp://www.sm.u-bordeaux2.fr/stat
Karl SigmundFaculty for MathematicsUniversity of Vienna
and International Institute forApplied Systems Analysis, Austriahttp://homepage.univie.ac.at/
Karl.Sigmund
Yakov G. SinaiDepartment of MathematicsPrinceton University, [email protected]
Valentin SolevLaboratory of Statistical Methods,Steklov Institute of Mathematics,RAS, Saint Petersburg, Russiahttp://www.pdmi.ras.ru/staff/solev.html
Vladimir M. TikhomirovMoscow State University andIndependent University of Moscow,Russia
Paul VitanyiCentrum voor Wiskunde en Infor-matica (CWI), AmsterdamThe Netherlandshttp://www.cwi.nl/∼paulv
Marc YorLaboratoire de Probabilites etModeles AleatoiresInstitut de mathematiques de JussieuUniversity Paris VI, Francehttp://www.academie-sciences.fr/
Membres/Y/Yor Marc.htm
Alexander ZvonkinLaboratoire Bordelais de Rechercheen Informatique (LaBRI)University Bordeaux I, Francehttp://www.labri.fr/perso/zvonkin
Introduction
Eric Charpentier1, Annick Lesne2, and Nikolaı Nikolski3
1 Institut de Mathematiques de Bordeaux, University Bordeaux I, Francehttp://www.math.u-bordeaux1.fr/imb/
[email protected] Laboratoire de physique theorique de la matiere condensee, University Paris VI,
and Institut des Hautes Etudes Scientifiques, Bures-sur-Yvette, Francehttp://www.lptmc.jussieu.fr/users/lesne/
[email protected] Institut de Mathematiques de Bordeaux, University Bordeaux I, Francehttp://www.math.u-bordeaux1.fr/imb/
Translated from the French by Elizabeth Strouse
Andrei Nikolaevich Kolmogorov (Tambov 1903, Moscow 1987) was one ofthe most brilliant mathematicians that the world has ever known. Incrediblydeep and creative, he was able to approach each subject with a completelynew point of view: in a few magnificent pages, which are models of shrewdnessand imagination, and which astounded his contemporaries, he changed dras-tically the landscape of the subject. Most mathematicians prove what theycan, Kolmogorov was of those who prove what they want.
In this book we have asked several world experts to present (one part of4)the mathematical heritage left to us by Kolmogorov5. Each chapter treatsone of Kolmogorov’s research themes, or a subject that was invented as aconsequence of his discoveries. We present here his contributions, his methods,the perspectives he opened to us, the way in which this research has evolvedup to now, along with examples of recent applications and a presentation ofthe modern prospects.
We hope that this book can be read by anyone with a master’s (or evena bachelor’s) degree in mathematics, computer science or physics, or more4 In the book Kolmogorov in perspective (History of Mathematics, Vol. 20, Ameri-
can Mathematical Society, 2000) one can find a (more or less) complete bibliog-raphy of Kolmogorov’s work, which consists of about 500 publications. A lot ofthese are at the heart of very active research going on today
5 A book entitled The Kolmogorov Legacy in Physics has already appeared(Springer, 2004). It contains contributions to dynamical systems, complexity, tur-bulence and probability. We strongly recommend it to mathematicians
2 Eric Charpentier et al.
generally by anyone who likes mathematical ideas. Rather than presentingdetailed proofs, we give the main ideas, and a bibliography for those whowish to understand the technical details. One can see that sometimes verysimple reasoning (with the right interpretation and tools) can lead in a fewlines to very substantial results.Here is a quick summary of the themes that are treated here, with, for each,some significant examples of the “master’s touch”.
Fourier Series (Chap. 1). In 1922, at the age of 19, Kolmogorov managedto construct a Lebesgue integrable function on [0, 2π] whose Fourier seriesdiverges almost everywhere, that is, except on a set of Lebesgue measure 0.(Up to this point the Fourier series of all the functions that had been consid-ered converged almost everywhere.) Three years later, he found an exampleof a function whose Fourier series diverged everywhere! In the same time,Kolmogorov obtained important results on lacunary Fourier series, harmonicconjugates . . .
Logic (Chap. 2). In 1925, Kolmogorov became interested in intuitionis-tic logic. For Brouwer (the father of Intuitionism), Intuitionism and Formal-ism were antinomic approaches. Moreover, intuitionistic logic was generallyconsidered as a weakening of classical logic. But, baffling all expectations,Kolmogorov managed to formalize intuitionistic logic and to present it as anextension of classical logic. He then deduced that any “finitary” propositionwith a classical proof could be proved using intuitionistic logic. All this inonly two pages!
If intuitionistic logic is perceived as an extension of classical logic, ob-tained by adding connectors with no analogues in classical logic, one needsto find an interpretation of these connectors. This is what Kolmogorov did in1932 when he interpreted intuitionistic logic as a “calculus of problems”. Thisinterpretation later turned out to be relevant to computer science.
Probabilities (Chaps. 3 and 4). It was also around 1925 that Kolmogorovbegan working on probability theory. He began with a clever generalization ofthe Bienayme-Chebyshev inequality: this “Kolmogorov’s inequality” quicklyrevealed its usefulness. He used it, with Khinchin, to obtain a famous conver-gence rule for series of random variables.
In 1930 he used the inequality to deduce a version of the strong law oflarge numbers (“almost sure” convergence − i.e. convergence with probabilityequal to one − of the empirical mean towards the mathematical expectation)which contained all prior versions of this law (Borel, Cantelli, Khinchin) likea set of Russian dolls: this is the “L2 version” given in Chap. 3. A littlelater he obtained the “L1 version” which is in a certain sense optimal sinceit holds whenever the variables (independant and with the same law) have afinite expectation. Kolmogorov announced this result in his book Foundationsof probability theory, in 1933, without giving a proof; he explained the proofto Maurice Frechet and let him have the honor of being the first to publish
Introduction 3
it in the first book of his Recherches theoriques modernes sur le calcul desprobabilites (Gauthier-Villars, 1937).
In 1931, Kolmogorov began thinking about continuous time Markovprocesses. Instead of studying the trajectories of a process, he studied thetransition probability densities and determined the differential equations theysatisfied. These are, of course, the fundamental equations from which the mod-ern theory of diffusion has been constructed. Because of the applications tomodern physics, they have even been generalized to Hilbert spaces of infinitedimension: Chapter 4 describes this active area of research which has hadseveral recent applications.
Lomnicki, Steinhaus, Cantelli had sketched out axiomatizations of proba-bility theory, based on Borel’s idea to formulate it in the langage of measuretheory; but it is Kolmogorov, in 1933, who solved the problem: his axiomati-zation, both natural and powerful, is the one that is still used today.
Statistics (Chaps. 5 and 6). In 1933, Glivenko et Cantelli proved whatis sometimes called the fundamental theorem of statistics : almost surely, theempirical distribution function of a real random variable converges uniformlytowards the true distribution function when the size of the sample tends to-wards infinity. Soon afterwards, Kolmogorov gave the precise law for the con-vergence, in terms of a universal function (independant of the − sought after− law of the random variable) which leads to a very efficient goodness-of-fittest (a test for the unknown law).
The Chap. 5 retraces this discovery of Kolmogorov and presents certainimprovements with a surprising application to number theory: it gives theasymptotic behavior (when n tends to infinity) of the probability that aninteger chosen at random has at least one divisor between n and 2n, and ofthe probability that it has exactly r such divisors.
Epsilon-entropy, a quasi-universal tool introduced by Kolmogorov in the1950’s (see Chap. 8) has become a fundamental tool in statistics for measuringthe quality of estimators: the Chap. 6 gives a survey of the current state ofknowledge, intended for master’s degree students as well as for researchers.
Topology (Chap. 7). During the years 1934–1937, Kolmogorov was veryexcited about topology. From 1934 to 1935, at the same time as Alexander,he constructed the cohomology of topological spaces and discovered its ringstructure. In 1935, Samuel Eilenberg asked if an open mapping (one that takesopen sets to open sets) can increase the dimension of its domain; Kolmogorovanswered this question with a three page article, which appeared in 1937, inwhich he gave a very clever construction of an open mapping which transformsa topological space of dimension 1 into a topological space of dimension 2. Thisresult was later used to analyze groups’ actions on topological spaces.
Geometry (Chap. 8). One of Kolmogorov’s great gifts was his extraor-dinary geometrical intuition. This played an essential role in almost allhis work, as shown in the fascinating Chap. 8. This chapter describes the
4 Eric Charpentier et al.
contributions of Kolmogorov to geometry, approximation theory, the inventionof ε-entropy, etc.
Mathematical Ecology (Chap. 9). In 1936, Kolmogorov published a shortnote on the predator-prey model of Lotka and Volterra: they had (indepen-dently) expressed the rates of growth of populations by explicit functions,depending on a small number of parameters, and they solved the equationsexplicitely. Clearly such a method can only apply to highly simplified models.Kolmogorov, on the other hand, did not choose specific functions, but insteadconcentrated on monotonicity properties (which give robust conditions); thenhe applied the qualitative methods of Poincare to study the long-time behaviorof populations (equilibria, limit cycles). Of course, this qualitative approachis the only one that can be used in realistic models.
Dynamical Systems. KAM Theorem (Chaps. 10, 11) and entropy(Chap. 12). Around 1953, Kolmogorov became interested in dynamical sys-tems. He proved a fundamental theorem which explains why, when a systemstays close enough to a system in which numerous laws of conservation hold,most movements of the former remain close to the regular movements of thelatter, instead of capitalizing on the lack of laws to wander. Kolmogorov pre-sented his proof in talks, but did not publish it. Arnold and Moser laterpublished the first proofs of Kolmogorov’s theorem (with different hypothe-ses) and this is where the name of the KAM (Kolmogorov, Arnold, Moser)theorem comes from. For more than 30 years, all known proofs of this theo-rem were extremely complicated, but in 1984 a wonderfully simple proof waspublished. This proof was improved upon in 2002. When one of the authors ofthis improved proof explained it in Moscow in 2002, members of the audiencewho had heard Kolmogorov in 1957 said that the new proof was actually thesame as Kolmogorov’s original one! (Chap. 11, p. 215.) Chapter 10 gives a his-torical survey of the problem of stability of movements in Celestial mechanics,explains the role of resonance and small divisors and presents an analogue ofKAM theorem in a toy model where mathematical difficulties are weakened.Chapter 11 illustrates the KAM theorem in the cases of the solar system andof the forced pendulum; then, it gives a rigorous statement of the theoremand sketches the main ideas of the new proof.
In 1958, Kolmogorov introduced the idea of entropy of dynamical systems,a quantity which is invariant by metric isomorphisms. This turned out to be avery powerful tool which permits one to show that two dynamical systems arenot metrically isomorphic. At first, Kolmogorov thought that deterministicsystems determined by differential equations would necessarily have zero en-tropy (roughly: “no disorder”) unlike probabilistic systems. But Kolmogorovand Sinai noticed that there exist deterministic systems with nonzero entropy.This discovery is one of the starting points of the modern theory of determin-istic chaos.
The modern (and fundamental) notion of hyperbolicity of a dynamicalsystem was developed as a result of the investigation of these deterministic
Introduction 5
systems with nonzero entropy. Chapter 12 describes this discovery and thelatest results on the subject.
The superposition theorem (chaps. 8 and 13). The 13th Hilbert problem(Paris, 1900) was to determine if any continuous function of three variablescould be constructed in a finite number of steps, each one an application ofa continuous function of one or two variables. (This was an idealization of amethod of graphical resolution of equations.) Hilbert expected a negative an-swer. In 1956 Kolmogorov showed that any continuous function of n variableson [0, 1]n is constructible if one permits the use of continuous functions ofthree variables as auxiliaries, and in 1957 his student Arnold proved that anycontinuous function of three variables is constructible using functions of twovariables, thus resolving Hilbert’s 13th problem (with a different result thanthat expected by Hilbert). Soon after, Kolmogorov showed that any contin-uous function of n variables on [0, 1]n is constructible using only continuousfunctions of one variable and additions: this is the Kolmogorov’s SuperpositionTheorem.
In 1987, Hecht-Nielsen deduced that any continuous function could beimplemented by a certain type of neural network with continuous activationfunctions and real weights. Constructive versions of the superposition theo-rem have recently made possible the transposition of this result to computablefunctions, activation functions and weights, and may give a way to constructnetworks corresponding to given functions. This application of the superpo-sition theorem to neural networks would surely have pleased Kolmogorov: infact, according to Arnold, one of Kolmogorov’s last mathematical works wasmotivated by his curiosity about the structure of the brain (cf. chapitre 9,p. 177).
More recently other applications of the superposition theorem have ap-peared: Kolmogorov would surely have been happy to know that it applies tosubjects such as the Radon transform and topological groups.
Complexity of description (Chaps. 14 and 15). In 1965, Kolmogorovdefined the complexity of description of an object; this is, more or less, thelength of the shortest algorithm which can describe this object (the exactdefinition is given in Chap. 14). This is a wonderful tool. One of its applica-tions was a surprisingly simple and short proof by Gregory Chaitin of Godel’sincompleteness theorem (Chap. 14), which can be understood by everybody!Chaitin was very pleased to find this proof which, he explained, gives one theimpression that the incompleteness phenomenon discovered by Godel is nat-ural − unlike the traditional proof, based on the “liar paradox” which makesthe phenomenon seem rather pathological and uncommon.
Kolmogorov’s complexity theory also makes sense of propositions such as“the sequence is random”: for Kolmogorov this means more or less that thesequence has no regularity with which one can “summarize” it, it is “incom-pressible”.
6 Eric Charpentier et al.
The existence of such incompressible objects gives a simple way to provethings in all branches of mathematics: this is the “incompressibility method”.Two examples of this method are given in Chap. 15, one in number theory(how to show in a few lines, and almost without calculation, that the nthprime number has an order of magnitude less than n log2 n, for instance),and the other in graph theory (finding the maximum size of complete graphscontained in a random graph).
But the principal object of Chap. 15 is to propose a new approachto deterministic chaos: instead of studying the unpredictibility in termsof the probabilities of ensembles of trajectories, one uses the complexitytheory of Kolmogorov to express the fact that an individual trajectory is“unpredictable”.
Acknowledgements
We of course thank all our authors for the wonderful texts they contributed.Our gratitude also extends to the translators and to the colleagues whose
comments and suggestions made this book possible: Michel Balazard, PierreCasteran, Robert Deville, Etienne Matheron, Cyril Mauvillain, Michel MendesFrance, Vesselin Petkov, Elizabeth Strouse, Philippe Thieullen, John Trompand Alexander Zvonkin.
