Pages from year three of a mathematical blog Terence Tao



Yüklə 2,87 Mb.
Pdf görüntüsü
tarix01.08.2018
ölçüsü2,87 Mb.
#60241


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

§1.5. Talagrand’s concentration inequality



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

→∞

(X) or simply



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

f (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

), Acta Math. 148 (1982), 215–241.



[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

odel completeness theorem, 20



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

obius function, 94



247


248

Index


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

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

 

P

 

 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.

MBK/77

AMS on the Web  

www.ams.org

For additional information

and updates on this book, visit

www.ams.org/bookpages/mbk-77

Reed Hutchinson/UCLA




Yüklə 2,87 Mb.

Dostları ilə paylaş:




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©genderi.org 2023
rəhbərliyinə müraciət

    Ana səhifə