Pages from year three of a mathematical blog Terence Tao
Yüklə 2,87 Mb. Pdf görüntüsü
|
- Bu səhifədəki naviqasiya:
- A M E R I C A N M A T H E M A T I C A L S O C I E T Y An Epsilon of Room, II
- A M E R I C A N M A T H E M A T I C A L S O C I E T Y
- MBK/77
| pages from year three of a mathematical blog Terence Tao A M E R I C A N M A T H E M A T I C A L S O C I E T Y An Epsilon of Room, II An Epsilon of Room, II pages from year three of a mathematical blog Terence Tao A M E R I C A N M A T H E M A T I C A L S O C I E T Y http://dx.doi.org/10.1090/mbk/077 2000 Mathematics Subject Classification. Primary 00A99. For additional information and updates on this book, visit www.ams.org/bookpages/mbk-77 Library of Congress Cataloging-in-Publication Data Tao, Terence, 1975– An epsilon of room, II: pages from year three of a mathematical blog / Terence Tao. p. cm. Includes bibliographical references and index. ISBN 978-0-8218-5280-4 (alk. paper) 1. Mathematics—Miscellanea. 2. General—General and miscellaneous specific topics— Miscellaneous topics. I. Title. QA99 .T36 2010 510—22
2010036471 Copying and reprinting. Individual readers of this publication, and nonprofit libraries acting for them, are permitted to make fair use of the material, such as to copy a chapter for use in teaching or research. Permission is granted to quote brief passages from this publication in reviews, provided the customary acknowledgment of the source is given. Republication, systematic copying, or multiple reproduction of any material in this publication is permitted only under license from the American Mathematical Society. Requests for such permission should be addressed to the Acquisitions Department, American Mathematical Society, 201 Charles Street, Providence, Rhode Island 02904-2294 USA. Requests can also be made by e-mail to reprint-permission@ams.org. c 2010 held by the author. All rights reserved. Printed in the United States of America. ∞ The paper used in this book is acid-free and falls within the guidelines established to ensure permanence and durability. Visit the AMS home page at http://www.ams.org/ 10 9 8 7 6 5 4 3 2 1 16 15 14 13 12 11 To Garth Gaudry, who set me on the road; To my family, for their constant support; And to the readers of my blog, for their feedback and contributions.
Contents Preface
vii A remark on notation viii Acknowledgments viii Chapter 1. Expository articles 1 §1.1. An explicitly solvable nonlinear wave equation 2 §1.2. Infinite fields, finite fields, and the Ax-Grothendieck theorem 7 §1.3. Sailing into the wind or faster than the wind 12 §1.4. The completeness and compactness theorems of first-order logic 20
35 §1.6. The Szemer´edi-Trotter theorem and the cell decomposition 42 §1.7. Benford’s law, Zipf’s law, and the Pareto distribution 48 §1.8. Selberg’s limit theorem for the Riemann zeta function on the critical line 59 §1.9. P = NP , relativisation, and multiple-choice exams 68 §1.10. Moser’s entropy compression argument 74 §1.11. The AKS primality test 82 §1.12. The prime number theorem in arithmetic progressions, and dueling conspiracies 87 §1.13. Mazur’s swindle 105 §1.14. Grothendieck’s definition of a group 108 §1.15. The “no self-defeating object” argument 116 v
vi Contents
§1.16. From Bose-Einstein condensates to the nonlinear Schr¨odinger equation
129 Chapter 2. Technical articles 141
§2.1. Polymath1 and three new proofs of the density Hales-Jewett theorem
142 §2.2. Szemer´edi’s regularity lemma via random partitions 154 §2.3. Szemer´edi’s regularity lemma via the correspondence principle162 §2.4. The two-ends reduction for the Kakeya maximal conjecture 171 §2.5. The least quadratic nonresidue, and the square root barrier 177 §2.6. Determinantal processes 188
§2.7. The Cohen-Lenstra distribution 200
§2.8. An entropy Pl¨unnecke-Ruzsa inequality 203
§2.9. An elementary noncommutative Freiman theorem 206
§2.10. Nonstandard analogues of energy and density increment arguments 209 §2.11. Approximate bases, sunflowers, and nonstandard analysis 212 §2.12. The double Duhamel trick and the in/out decomposition 230 §2.13. The free nilpotent group 233 Bibliography 241 Index
247 Preface In February of 2007, I converted my “What’s new” web page of research updates into a blog at terrytao.wordpress.com. This blog has since grown and evolved to cover a wide variety of mathematical topics, ranging from my own research updates, to lectures and guest posts by other mathematicians, to open problems, to class lecture notes, to expository articles at both basic and advanced levels. With the encouragement of my blog readers, and also of the American Mathematical Society, I published many of the mathematical articles from the first two years of the blog as [Ta2008] and [Ta2009], which will hence- forth be referred to as Structure and Randomness and Poincar´ e’s Legacies Vols. I, II throughout this book. This gave me the opportunity to improve and update these articles to a publishable (and citeable) standard, and also to record some of the substantive feedback I had received on these articles by the readers of the blog. The current text contains many (though not all) of the posts for the third year (2009) of the blog, focusing primarily on those posts of a mathematical nature which were not contributed primarily by other authors, and which are not published elsewhere. It has been split into two volumes. The first volume (referred to henceforth as Volume 1 ) consisted primarily of lecture notes from my graduate courses on real analysis that I taught at UCLA. The current volume consists instead of sundry articles on a variety of mathematical topics, which I have divided (somewhat arbitrarily) into expository articles (Chapter 1) which are introductory articles on topics of relatively broad interest, and more technical articles (Chapter 2) which are narrower in scope and often related to one of my current research interests. vii
viii Preface
These can be read in any order, although they often reference each other as well as articles from previous volumes in this series. A remark on notation For reasons of space, we will not be able to define every single mathematical term that we use in this book. If a term is italicised for reasons other than emphasis or for definition, then it denotes a standard mathematical object, result, or concept, which can be easily looked up in any number of references. (In the blog version of the book, many of these terms were linked to their Wikipedia pages, or other on-line reference pages.) I will however mention a few notational conventions that I will use throughout. The cardinality of a finite set E will be denoted |E|. We will use the asymptotic notation X = O(Y ), X Y , or Y X to denote the estimate |X| ≤ CY for some absolute constant C > 0. In some cases we will need this constant C to depend on a parameter (e.g., d), in which case we shall indicate this dependence by subscripts, e.g., X = O d (Y ) or
X d Y . We also sometimes use X ∼ Y as a synonym for X Y X. In many situations there will be a large parameter n that goes off to infinity. When that occurs, we also use the notation o n →∞
o(X) to denote any quantity bounded in magnitude by c(n)X, where c(n) is a function depending only on n that goes to zero as n goes to infinity. If we need c(n) to depend on another parameter, e.g., d, we indicate this by further subscripts, e.g., o n →∞;d
(X). We will occasionally use the averaging notation E x ∈X
:= 1 |X| x ∈X f (x) to denote the average value of a function f : X → C on a nonempty finite set X. Acknowledgments The author is supported by a grant from the MacArthur Foundation, by NSF grant DMS-0649473, and by the NSF Waterman Award. Thanks to Konrad Swanepoel, Blake Stacey, and anonymous commenters for global corrections to the text, and to Edward Dunne at the AMS for en- couragement and editing. Bibliography [AgKaSa2004] M. Agrawal, N. Kayal, N. Saxena, PRIMES is in P, Annals of Mathematics 160 (2004), no. 2, pp. 781–793. [AjSz1974] M. Ajtai, E. Szemer´ edi, Sets of lattice points that form no squares, Stud. Sci. Math. Hungar. 9 (1974), 9–11 (1975). [AlDuLeRoYu1994] N. Alon, R. Duke, H. Lefmann, Y. R¨ odl, R. Yuster, The algorithmic aspects of the regularity lemma, J. Algorithms 16 (1994), no. 1, 80–109. [AlSh2008] N. Alon, A. Shapira, Every monotone graph property is testable, SIAM J. Comput. 38 (2008), no. 2, 505–522. [AlSp2008] N. Alon, J. Spencer, The probabilistic method. Third edition. With an appen- dix on the life and work of Paul Erd˝ os. Wiley-Interscience Series in Discrete Mathe- matics and Optimization. John Wiley & Sons, Inc., Hoboken, NJ, 2008. [Au2008] T. Austin, On exchangeable random variables and the statistics of large graphs and hypergraphs, Probab. Surv. 5 (2008), 80–145. [Au2009] T. Austin, Deducing the multidimensional Szemer´ edi Theorem from an infinitary removal lemma, preprint. [Au2009b] T. Austin, Deducing the Density Hales-Jewett Theorem from an infinitary re- moval lemma, preprint. [AuTa2010] T. Austin, T. Tao, On the testability and repair of hereditary hypergraph properties, preprint. [Ax1968] J. Ax, The elementary theory of finite fields, Ann. of Math. 88 (1968) 239–271. [BaGiSo1975] T. Baker, J. Gill, R. Solovay, Relativizations of the P =?N P question, SIAM J. Comput. 4 (1975), no. 4, 431–442. [Be1975] W. Beckner, Inequalities in Fourier analysis, Ann. of Math. 102 (1975), no. 1, 159–182.
[BeTaZi2009] V. Bergelson, T. Tao, T. Ziegler, An inverse theorem for the uniformity seminorms associated with the action of F ω , preprint. [BeLo1976] J. Bergh, J. L¨ ofstr¨
om, Interpolation spaces. An introduction. Grundlehren der Mathematischen Wissenschaften, No. 223. Springer-Verlag, Berlin-New York, 1976. [BiRo1962] A. Bialynicki-Birula, M. Rosenlicht, Injective morphisms of real algebraic va- rieties, Proc. Amer. Math. Soc. 13 (1962) 200–203. 241
242 Bibliography [BoKe1996] E. Bogomolny, J. Keating, Random matrix theory and the Riemann zeros. II. n-point correlations, Nonlinearity 9 (1996), no. 4, 911–935. [Bo1969] A. Borel, Injective endomorphisms of algebraic varieties, Arch. Math. (Basel) 20 (1969), 531–537. [Bo1999] J. Bourgain, On the dimension of Kakeya sets and related maximal inequalities, Geom. Funct. Anal. 9 (1999), no. 2, 256–282. [BoBr2003] J. Bourgain, H. Brezis, On the equation div Y = f and application to control of phases, J. Amer. Math. Soc. 16 (2003), no. 2, 393–426. [BudePvaR2008] G. Buskes, B. de Pagter, A. van Rooij, The Loomis-Sikorski theorem revisited, Algebra Universalis 58 (2008), 413–426. [ChPa2009] T. Chen, N. Pavlovic, The quintic NLS as the mean field limit of a boson gas with three-body interactions, preprint. [ClEdGuShWe1990] K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, E. Welzl, Com- binatorial complexity bounds for arrangements of curves and spheres, Discrete Com- put. Geom. 5 (1990), no. 2, 99–160. [Co1989] J. B. Conrey, More than two fifths of the zeros of the Riemann zeta function are on the critical line, J. Reine Angew. Math. 399 (1989), 1–26. [Dy1970] F. Dyson, Correlations between eigenvalues of a random matrix, Comm. Math. Phys. 19 (1970), 235–250. [ElSz2008] G. Elek, B. Szegedy, A measure-theoretic approach to the theory of dense hy- pergraphs, preprint. [ElObTa2009] J. Ellenberg, R. Oberlin, T. Tao, The Kakeya set and maximal conjectures for algebraic varieties over finite fields, preprint. [ElVeWe2009] J. Ellenberg, A. Venkatesh, C. Westerland, Homological stability for Hur- witz spaces and the Cohen-Lenstra conjecture over function fields, preprint. [ErKa1940] P. Erd˝ os, M. Kac, The Gaussian Law of Errors in the Theory of Additive Number Theoretic Functions, Amer. J. Math., 62 (1940), no. 1/4, pages 738–742. [EsKePoVe2008] L. Escauriaza, C. E. Kenig, G. Ponce, L. Vega, Hardy’s uncertainty principle, convexity and Schr¨ odinger evolutions, J. Eur. Math. Soc. (JEMS) 10 (2008), no. 4, 883–907. [Fa2003] K. Falconer, Fractal geometry, Mathematical Foundations and Applications. Sec- ond edition. John Wiley & Sons, Inc., Hoboken, NJ, 2003. [FeSt1972] C. Fefferman, E. M. Stein, H p spaces of several variables, Acta Math. 129 (1972), no. 3-4, 137–193. [FiMaSh2007] E. Fischer, A. Matsliach, A. Shapira, Approximate Hypergraph Partitioning and Applications, Proc. of FOCS 2007, 579–589. [Fo2000] G. Folland, Real analysis, modern techniques and their applications. Second edi- tion. Pure and Applied Mathematics (New York). A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1999. [Fo1955] E. Følner, On groups with full Banach mean value, Math. Scand. 3 (1955), 243– 254.
[Fo1974] J. Fournier, Majorants and L p norms, Israel J. Math. 18 (1974), 157–166. [Fr1973] G. Freiman, Groups and the inverse problems of additive number theory, Number- theoretic studies in the Markov spectrum and in the structural theory of set addition, pp. 175-183. Kalinin. Gos. Univ., Moscow, 1973. [Fu1977] H. Furstenberg, Ergodic behavior of diagonal measures and a theorem of Sze- mer´ edi on arithmetic progressions, J. Analyse Math. 31 (1977), 204–256. Bibliography 243
[FuKa1989] H. Furstenberg, Y. Katznelson, A density version of the Hales-Jewett theorem for k = 3, Graph theory and combinatorics (Cambridge, 1988). Discrete Math. 75 (1989), no. 1–3, 227–241. [FuKa1991] H. Furstenberg, Y. Katznelson, A density version of the Hales-Jewett theorem, J. Anal. Math. 57 (1991), 64–119. [GiTr1998] D. Gilbarg, N. Trudinger, Elliptic partial differential equations of second order. Reprint of the 1998 edition. Classics in Mathematics. Springer-Verlag, Berlin, 2001. [GoMo1987] D. Goldston, H. Montgomery, Pair correlation of zeros and primes in short intervals, Analytic number theory and Diophantine problems (Stillwater, OK, 1984), 183–203, Progr. Math., 70, Birkh¨ auser Boston, Boston, MA, 1987. [Go1993] W. T. Gowers, B. Maurey, The unconditional basic sequence problem, J. Amer. Math. Soc. 6 (1993), no. 4, 851–874. [Gr1992] A. Granville, On elementary proofs of the prime number theorem for arithmetic progressions, without characters, Proceedings of the Amalfi Conference on Analytic Number Theory (Maiori, 1989), 157–194, Univ. Salerno, Salerno, 1992. [Gr2005] A. Granville, It is easy to determine whether a given integer is prime, Bull. Amer. Math. Soc. (N.S.) 42 (2005), no. 1, 3–38. [GrSo2007] A. Granville, K. Soundararajan, Large character sums: pretentious characters and the P´ olya-Vinogradov theorem, J. Amer. Math. Soc. 20 (2007), no. 2, 357–384. [GrTa2007] B. Green, T. Tao, The distribution of polynomials over finite fields, with ap- plications to the Gowers norms, preprint. [GrTaZi2009] B. Green, T. Tao, T. Ziegler, An inverse theorem for the Gowers U 4 norm,
preprint. [Gr1999] M. Gromov, Endomorphisms of symbolic algebraic varieties, J. Eur. Math. Soc. (JEMS) 1 (1999), no. 2, 109–197. [Gr1966] A. Grothendieck, ´ El´
ements de g´ eom´
etrie alg´ ebrique. IV. ´ Etude locale des sch´
emas et des morphismes de sch´ emas. III., Inst. Hautes ´ Etudes Sci. Publ. Math. No. 28, 1966, 255 pp. [GyMaRu2008] K. Gyarmati, M. Matolcsi, I. Ruzsa, Pl¨ unnecke’s inequality for different summands, Building Bridges, 309–320, Bolyai Soc. Math. Stud., 19, Springer, Berlin, 2008.
[Ho1990] L. H¨ ormander, The analysis of linear partial differential operators. I.-IV. Reprint of the second (1990) edition. Classics in Mathematics. Springer-Verlag, Berlin, 2003. [HoKrPeVi2006] J. Hough, M. Krishnapur, Y. Peres, B. Vir´ ag, Determinantal processes and independence, Probab. Surv. 3 (2006), 206–229. [Hr2009] E. Hrushovski, Stable group theory and approximate subgroups, preprint. [Hu1968] R. Hunt, On the convergence of Fourier series, 1968 Orthogonal Expansions and their Continuous Analogues (Proc. Conf., Edwardsville, Ill., 1967) pp. 235–255 Southern Illinois Univ. Press, Carbondale, Ill. [Is2006] Y. Ishigami, A Simple Regularization of Hypergraphs, preprint. [IwKo2004] H. Iwaniec, E. Kowalski, Analytic number theory, American Mathematical Society Colloquium Publications, 53. American Mathematical Society, Providence, RI, 2004. [Jo1986] D. Joyner, Distribution theorems of L-functions, Pitman Research Notes in Mathematics Series, 142. Longman Scientific & Technical, Harlow; John Wiley & Sons, Inc., New York, 1986.
244 Bibliography [KaVe1983] V. Kaimanovich, A. Vershik, Random walks on discrete groups: boundary and entropy, Ann. Probab. 11 (1983), no. 3, 457–490. [KiVi2009] R. Killip, M. Visan, Nonlinear Schr¨ odinger Equations at critical regularity, preprint. [KiScSt2008] K. Kirkpatrick, B. Schlein, G. Staffilani, Derivation of the two dimensional nonlinear Schrodinger equation from many body quantum dynamics, preprint. [KlMa2008] S. Klainerman, M. Machedon, On the uniqueness of solutions to the Gross- Pitaevskii hierarchy, Comm. Math. Phys. 279 (2008), no. 1, 169–185. [Ku1999] K. Kurdyka, Injective endomorphisms of real algebraic sets are surjective, Math. Ann. 313 (1999), no. 1, 69–82. [La2001] I. Laba, Fuglede’s conjecture for a union of two intervals, Proc. Amer. Math. Soc. 129 (2001), no. 10, 2965–2972. [LaTa2001] I. Laba, T. Tao, An x-ray transform estimate in R n , Rev. Mat. Iberoamericana 17 (2001), no. 2, 375–407. [La1996] A. Laurincikas, Limit theorems for the Riemann zeta-function. Mathematics and Its Applications, 352. Kluwer Academic Publishers Group, Dordrecht, 1996. [Le2009] A. Leibman, A canonical form and the distribution of values of generalised poly- nomials, preprint. [Le2000] V. Lev, Restricted Set Addition in Groups I: The Classical Setting, J. London Math. Soc. 62 (2000), no. 1, 27–40. [LiLo2000] E. Lieb, E. Loss, Analysis. Second edition. Graduate Studies in Mathematics, 14. American Mathematical Society, Providence, RI, 2001. [Li1853] J. Liouville, Sur l’equation aux differences partielles, J. Math. Pure et Appl. 18 (1853), 71–74. [LiTz1971] J. Lindenstrauss, L. Tzafriri, On the complemented subspaces problem, Israel J. Math. 9 (1971) 263–269. [Lo1946] L. H. Loomis, On the representation of σ-complete Boolean algebras, Bull. Amer. Math Soc. 53 (1947), 757–760. [LoSz2007] L. Lov´ asz, B. Szegedy, Szemer´ edi’s lemma for the analyst, Geom. Funct. Anal. 17 (2007), no. 1, 252–270. [Ly2003] R. Lyons, Determinantal probability measures, Publ. Math. Inst. Hautes ´ Etudes Sci. No. 98 (2003), 167–212. [Ma2008] M. Madiman, On the entropy of sums, preprint. [MaKaSo2004] W. Magnus, A. Karras, and D. Solitar, Presentations of Groups in Terms of Generators and Relations, Dover Publications, 2004. [Ma1999] R. Matthews, The power of one, New Scientist, 10 July 1999, p. 26. [Ma1995] P. Mattila, Geometry of sets and measures in Euclidean spaces. Fractals and rectifiability. Cambridge Studies in Advanced Mathematics, 44. Cambridge University Press, Cambridge, 1995. [Ma1959] B. Mazur, On embeddings of spheres, Bull. Amer. Math. Soc. 65 (1959), 59–65. [Mo2009] R. Moser, A constructive proof of the Lov´ asz local lemma, Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009, 343–350. [Na1964] I. Namioka, Følner’s conditions for amenable semi-groups, Math. Scand. 15 (1964), 18–28. [ON1963] R. O’Neil, Convolution operators and L(p, q) spaces, Duke Math. J. 30 (1963), 129–142.
Bibliography 245
[Po2009] D.H.J. Polymath, A new proof of the density Hales-Jewett theorem, preprint. [PCM] The Princeton Companion to Mathematics. Edited by Timothy Gowers, June Barrow-Green and Imre Leader. Princeton University Press, Princeton, NJ, 2008. [Ra1959] H. Rademacher, On the Phragm´ en-Lindel¨ of theorem and some applications, Math. Z. 72 (1959/1960), 192–204. [RaRu1997] A. Razborov, S. Rudich, Natural proofs, 26th Annual ACM Symposium on the Theory of Computing (STOC ’94) (Montreal, PQ, 1994). J. Comput. System Sci. 55 (1997), no. 1, part 1, 24–35. [Ro1982] J.-P. Rosay, Injective holomorphic mappings, Amer. Math. Monthly 89 (1982), no. 8, 587–588. [Ro1953] K. Roth, On certain sets of integers, I, J. London Math. Soc. 28 (1953), 104–109. [Ru1962] W. Rudin, Fourier Analysis on Groups. Reprint of the 1962 original. Wiley Classics Library. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1990. [Ru1995] W. Rudin, Injective polynomial maps are automorphisms, Amer. Math. Monthly 102 (1995), no. 6, 540–543. [Ru1989] I. Ruzsa, An application of graph theory to additive number theory, Sci. Ser. A Math. Sci. (N.S.) 3 (1989), 97–109. [RuSz1978] I. Ruzsa, E. Szemer´ edi, Triple systems with no six points carrying three tri- angles, Colloq. Math. Soc. J. Bolyai, 18 (1978), 939–945. [Sc2006] B. Schlein, Dynamics of Bose-Einstein Condensates, preprint. [Se2009] J. P. Serre, How to use finite fields for problems concerning infinite fields, preprint. [So2000] A. Soshnikov, Determinantal random point fields, Uspekhi Mat. Nauk 55 (2000), no. 5 (335), 107–160; translation in Russian Math. Surveys 55 (2000), no. 5, 923–975. [St1961] E. M. Stein, On limits of seqences of operators, Ann. of Math. 74 (1961) 140–170. [St1970] E. M. Stein, Singular integrals and differentiability properties of functions. Prince- ton Mathematical Series, No. 30 Princeton University Press, Princeton, N.J. 1970 [St1993] E. M. Stein, Harmonic analysis: real-variable methods, orthogonality, and oscil- latory integrals. With the assistance of Timothy S. Murphy. Princeton Mathematical Series, 43. Monographs in Harmonic Analysis, III. Princeton University Press, Prince- ton, NJ, 1993. [St1969] S. A. Stepanov, The number of points of a hyperelliptic curve over a finite prime field, Izv. Akad. Nauk SSSR Ser. Mat. 33 (1969) 1171–1181. [St1948] A. H. Stone, Paracompactness and product spaces, Bull. Amer. Math. Soc. 54, (1948), 977–982. [Sz2009] B. Szegedy, Higher order Fourier analysis as an algebraic theory I, preprint. [SzTr1983] E. Szemer´ edi, W. Trotter, Extremal problems in discrete geometry, Combina- torica 3 (1983), no. 3–4, 381–392. [Ta1996] M. Talagrand, Concentration of measure and isoperimetric inequalities in prod- uct spaces, Inst. Hautes ´ Etudes Sci. Publ. Math. No. 81 (1995), 73–205 [Ta2005] M. Talagrand, The Generic Chaining. Upper and Lower Bounds of Stochastic Processes. Springer Monographs in Mathematics. Springer-Verlag, Berlin, 2005. [Ta1951] A. Tarski, A Decision Method for Elementary Algebra and Geometry, 2nd ed. University of California Press, Berkeley and Los Angeles, Calif., 1951. [Ta] T. Tao, Summability of functions, unpublished preprint.
246 Bibliography [Ta2006] T. Tao, Nonlinear Dispersive Equations. Local and Global Analysis. CBMS Re- gional Conference Series in Mathematics, 106. Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 2006. [Ta2006b] T. Tao, A quantitative ergodic theory proof of Szemer´ edi’s theorem, Electron. J. Combin. 13 (2006), no. 1. [Ta2006c] T. Tao, Szemer´ edi’s regularity lemma revisited, Contrib. Discrete Math. 1 (2006), no. 1, 8–28. [Ta2007] T. Tao, A correspondence principle between (hyper)graph theory and probability theory, and the (hyper)graph removal lemma, J. Anal. Math. 103 (2007), 1–45. [Ta2007b] T. Tao, Structure and randomness in combinatorics, Proceedings of the 48th annual symposium on Foundations of Computer Science (FOCS) 2007, 3–18. [Ta2008] T. Tao, Structure and Randomness: pages from year one of a mathematical blog, American Mathematical Society, Providence RI, 2008. [Ta2009] T. Tao, Poincar´ e’s Legacies: pages from year two of a mathematical blog, Vols. I, II, American Mathematical Society, Providence RI, 2009. [Ta2010] T. Tao, The high exponent limit p → ∞ for the one-dimensional nonlinear wave equation, preprint. [Ta2010b] T. Tao, A remark on partial sums involving the M¨ obius function, preprint. [Ta2010c] T. Tao, Sumset and inverse sumset theorems for Shannon entropy, preprint. [TaVu2006] T. Tao, V. Vu, On random ±1 matrices: singularity and determinant, Ran- dom Structures Algorithms 28 (2006), no. 1, 1–23 [TaVu2006b] T. Tao, V. Vu, Additive Combinatorics. Cambridge Studies in Advanced Mathematics, 105. Cambridge University Press, Cambridge, 2006. [TaVu2007] T. Tao, V. Vu, On the singularity probability of random Bernoulli matrices, J. Amer. Math. Soc. 20 (2007), 603–628. [TaWr2003] T. Tao, J. Wright, L p improving bounds for averages along curves, J. Amer. Math. Soc. 16 (2003), no. 3, 605–638. [Th1994] W. Thurston, On proof and progress in mathematics, Bull. Amer. Math. Soc. (N.S.) 30 (1994), no. 2, 161–177. [To2005] C. Toth, The Szemer´ edi-Trotter Theorem in the Complex Plane, preprint. [Uc1982] A. Uchiyama, A constructive proof of the Fefferman-Stein decomposition of BMO (R n
[VuWoWo2010] V. Vu, M. Wood, P. Wood, Mapping incidences, preprint. [Wo1995] T. Wolff, An improved bound for Kakeya type maximal functions, Rev. Mat. Iberoamericana 11 (1995), no. 3, 651–674. [Wo1998] T. Wolff, A mixed norm estimate for the X-ray transform, Rev. Mat. Iberoamer- icana 14 (1998), no. 3, 561–600. [Wo2003] T. Wolff, Lectures on Harmonic Analysis. With a foreword by Charles Fefferman and preface by Izabella Laba. Edited by Laba and Carol Shubin. University Lecture Series, 29. American Mathematical Society, Providence, RI, 2003. Index P = N P , 69 Ajtai-Szemer´ edi theorem, 143 AKS primality test, 85 Ax-Grothendieck theorem, 8 BBGKY hierarchy, 138 Benford’s law, 48 Burgess estimate, 187 Busy Beaver function, 125 Cantor’s theorem, 119 Cantor-Bernstein-Schr¨ oder theorem, 107
Cell decomposition, 43 Cohen-Lenstra heuristic, 201 Compactness theorem, 21 Connection, 109 Corners theorem, 143 Density increment argument, 76, 144 Determinantal process, 191 Dirichlet character, 179 Duhamel formula, 230 Energy increment argument, 76 Entropy Pl¨ unnecke-Ruzsa inequality, 204 Euclid’s theorem, 117 Fatou-Bieberback domain, 8 Fermat’s little theorem, 83 First-order logic, 31 Flat connection, 110 Free nilpotent group, 238 G¨ odel completeness theorem, 20 G¨ odel’s incompleteness theorem, 123 Gaudin-Mehta formula, 198 Gaussian concentration inequality, 40 Ginibre formula, 198 Gram identity, 191 Graph correspondence principle, 165 Greedy algorithm, 155 Gross-Pitaevskii hierarchy, 139 Grothendieck’s axiom, 113 Hales-Jewett theorem, 142 Hall-Witt identity, 235 Hamilton’s equations of motion, 131 Hamiltonian mechanics, 130 Harmless move, 127 Heisenberg’s equation of motion, 135 Hilbert’s nullstellensatz, 9 Hyperelliptic curve, 184 Infinitary regularity lemma, 168 Jacobian conjecture, 8 Kakeya maximal function conjecture, 172
Large deviation inequality, 36 Liouville equation, 2 Lorentz transformation, 3 Lov´
asz local lemma, 78 M¨ obius function, 94 247 248 Index
M¨ obius inversion formula, 94 Mass increment argument, 76 Mazur’s swindle, 106 Mean field approximation, 139 Multidimensional Pythagorean theorem, 190 Nonstandard arithmetic regularity lemma, 211 Notation, viii Omnipotence paradox, 116 Oracle, 72 P´ olya-Vinogradov inequality, 181 Pareto distribution, 48 Pl¨
unnecke-Ruzsa inequality, 203 Point process, 188 Poisson bracket, 131 Poisson’s equations of motions, 131 Polycyclic group, 236 Prenex normal form, 33 Presheaf, 112 Prime number theorem, 87 Quining, 122 Rank (polynomial), 219 Rank reduction argument, 76, 213 Relativisation, 72 Riemann zeta function, 60 Roth’s theorem, 143 Russel’s paradox, 118 Saturation (model theory), 209 Sch¨ onflies problem, 106 Schr¨ odinger equation, 130 Schr¨ odinger’s equation of motion, 135 Second von Mangoldt function, 95 Selberg symmetric formula, 96 Sequential compactness theorem, 22 Sheaf, 112 Siegel’s theorem, 102 sine-Gordon equation, 2 Skolem’s paradox, 21 Skolemisation, 33 Stepanov’s method, 184 Strategy stealing argument, 127 Submodularity inequality, 204 Sunflower lemma, 222 Szemer´ edi regularity lemma, 154 Szemer´ edi-Trotter theorem, 42 Talagrand’s inequality, 37 Tautology, 24 Triangle removal lemma, 147 Turing halting theorem, 124 Two-ends condition, 173 Von Mangoldt function, 61, 87 Wronskian, 5 Zeroth-order logic, 27 Zipf’s law, 48
There are many bits and pieces of folklore in math- ematics that are passed down from advisor to stu- dent, or from collaborator to collaborator, but which are too fuzzy and nonrigorous to be discussed in the formal literature. Traditionally, it was a matter of luck and location as to who learned such “folklore mathematics”. But today, such bits and pieces can be communicated effectively and efficiently via the semiformal medium of research blogging. This book grew from such a blog. In 2007 Terry Tao began a mathematical blog to cover a variety of topics, rang- ing from his own research and other recent developments in mathematics, to lecture notes for his classes, to nontechnical puzzles and expository articles. The first two years of the blog have already been published by the American Mathematical Society. The posts from the third year are being published in two volumes. This second volume contains a broad selection of mathematical expositions and self-contained technical notes in many areas of mathematics, such as logic, mathematical physics, combinatorics, number theory, statistics, theoretical computer science, and group theory. Tao has an extraordinary ability to explain deep results to his audience, which has made his blog quite popular. Some examples of this facility in the present book are the tale of two students and a multiple-choice exam being used to explain the P
= N
con-
jecture and a discussion of “no self-defeating object” arguments that starts from a schoolyard number game and ends with results in logic, game theory, and theoretical physics. The first volume consists of a second course in real analysis, together with related material from the blog, and it can be read independently.
AMS on the Web www.ams.org For additional information and updates on this book, visit
Reed Hutchinson/UCLA Yüklə 2,87 Mb. Dostları ilə paylaş:
|