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
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
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
Dostları ilə paylaş: |