For additional information and updates on this book, visit
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.
Includes bibliographical references and index.
2. General—General and miscellaneous speciﬁc topics—
Copying and reprinting.
Individual readers of this publication, and nonproﬁt 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 firstname.lastname@example.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
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 my family, for their constant support;
And to the readers of my blog, for their feedback and contributions.
A remark on notation
§1.1. An explicitly solvable nonlinear wave equation
§1.2. Inﬁnite ﬁelds, ﬁnite ﬁelds, and the Ax-Grothendieck theorem
§1.3. Sailing into the wind or faster than the wind
§1.4. The completeness and compactness theorems of ﬁrst-order
§1.5. Talagrand’s concentration inequality
§1.6. The Szemer´edi-Trotter theorem and the cell decomposition
§1.7. Benford’s law, Zipf’s law, and the Pareto distribution
§1.8. Selberg’s limit theorem for the Riemann zeta function on the
§1.9. P = NP , relativisation, and multiple-choice exams
§1.10. Moser’s entropy compression argument
§1.11. The AKS primality test
§1.12. The prime number theorem in arithmetic progressions, and
§1.13. Mazur’s swindle
§1.14. Grothendieck’s deﬁnition of a group
§1.15. The “no self-defeating object” argument
§2.2. Szemer´edi’s regularity lemma via random partitions
§2.3. Szemer´edi’s regularity lemma via the correspondence principle162
§2.5. The least quadratic nonresidue, and the square root barrier 177
§2.6. Determinantal processes
§2.11. Approximate bases, sunﬂowers, and nonstandard analysis
§2.12. The double Duhamel trick and the in/out decomposition
§2.13. The free nilpotent group
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 ﬁrst two years of the blog as [Ta2008] and [Ta2009], which will hence-
forth be referred to as Structure and Randomness and Poincar´
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 ﬁrst 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.
well as articles from previous volumes in this series.
A remark on notation
For reasons of space, we will not be able to deﬁne every single mathematical
term that we use in this book. If a term is italicised for reasons other than
emphasis or for deﬁnition, 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
The cardinality of a ﬁnite set E will be denoted
will use the asymptotic notation X = O(Y ), X
X to denote
|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
(Y ) or
Y . We also sometimes use X
inﬁnity. When that occurs, we also use the notation o
(X) or simply
is a function depending only on n that goes to zero as n goes to inﬁnity. If
we need c(n) to depend on another parameter, e.g., d, we indicate this by
further subscripts, e.g., o
We will occasionally use the averaging notation E
f (x) to denote the average value of a function f : X
a nonempty ﬁnite set X.
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.
[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 inﬁnitary
removal lemma, preprint.
[Au2009b] T. Austin, Deducing the Density Hales-Jewett Theorem from an inﬁnitary re-
moval lemma, preprint.
[AuTa2010] T. Austin, T. Tao, On the testability and repair of hereditary hypergraph
[Ax1968] J. Ax, The elementary theory of ﬁnite ﬁelds, 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,
seminorms associated with the action of F
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.
[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 ﬁeld 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 ﬁfths 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-
[ElObTa2009] J. Ellenberg, R. Oberlin, T. Tao, The Kakeya set and maximal conjectures
for algebraic varieties over ﬁnite ﬁelds, preprint.
[ElVeWe2009] J. Ellenberg, A. Venkatesh, C. Westerland, Homological stability for Hur-
witz spaces and the Cohen-Lenstra conjecture over function ﬁelds, 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. Feﬀerman, E. M. Stein, H
spaces of several variables, Acta Math. 129
[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–
norms, Israel J. Math. 18 (1974), 157–166.
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-
edi on arithmetic progressions, J. Analyse Math. 31 (1977), 204–256.
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 diﬀerential 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 Amalﬁ 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 ﬁnite ﬁelds, with ap-
plications to the Gowers norms, preprint.
[GrTaZi2009] B. Green, T. Tao, T. Ziegler, An inverse theorem for the Gowers U
[Gr1999] M. Gromov, Endomorphisms of symbolic algebraic varieties, J. Eur. Math. Soc.
(JEMS) 1 (1999), no. 2, 109–197.
[Gr1966] A. Grothendieck,
ebrique. IV. ´
Etude locale des
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 diﬀerent
summands, Building Bridges, 309–320, Bolyai Soc. Math. Stud., 19, Springer, Berlin,
ormander, The analysis of linear partial diﬀerential 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,
[Jo1986] D. Joyner, Distribution theorems of L-functions, Pitman Research Notes in
Mathematics Series, 142. Longman Scientiﬁc & Technical, Harlow; John Wiley &
Sons, Inc., New York, 1986.
[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,
[KiScSt2008] K. Kirkpatrick, B. Schlein, G. Staﬃlani, 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
, Rev. Mat. Iberoamericana
[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-
[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 diﬀerences partielles, J. Math. Pure et Appl. 18
[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 ´
Sci. No. 98 (2003), 167–212.
[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
rectiﬁability. 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
[ON1963] R. O’Neil, Convolution operators and L(p, q) spaces, Duke Math. J. 30 (1963),
[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´
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
[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 ﬁnite ﬁelds for problems concerning inﬁnite ﬁelds,
[So2000] A. Soshnikov, Determinantal random point ﬁelds, 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 diﬀerentiability 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 ﬁnite prime
ﬁeld, Izv. Akad. Nauk SSSR Ser. Mat. 33 (1969) 1171–1181.
[St1948] A. H. Stone, Paracompactness and product spaces, Bull. Amer. Math. Soc. 54,
[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.
[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
[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
improving bounds for averages along curves, J. Amer.
[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 Feﬀerman-Stein decomposition of BMO
), Acta Math. 148 (1982), 215–241.
[Wo1995] T. Wolﬀ, An improved bound for Kakeya type maximal functions, Rev. Mat.
Iberoamericana 11 (1995), no. 3, 651–674.
[Wo1998] T. Wolﬀ, A mixed norm estimate for the X-ray transform, Rev. Mat. Iberoamer-
icana 14 (1998), no. 3, 561–600.
[Wo2003] T. Wolﬀ, Lectures on Harmonic Analysis. With a foreword by Charles Feﬀerman
and preface by Izabella Laba. Edited by Laba and Carol Shubin. University Lecture
Series, 29. American Mathematical Society, Providence, RI, 2003.
P = N P , 69
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
Cohen-Lenstra heuristic, 201
Compactness theorem, 21
Corners theorem, 143
Density increment argument, 76, 144
Determinantal process, 191
Dirichlet character, 179
Duhamel formula, 230
Energy increment argument, 76
Euclid’s theorem, 117
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
Inﬁnitary regularity lemma, 168
Jacobian conjecture, 8
Kakeya maximal function conjecture,
Liouville equation, 2
Lorentz transformation, 3
obius function, 94
obius inversion formula, 94
Mass increment argument, 76
Mazur’s swindle, 106
Mean ﬁeld approximation, 139
Nonstandard arithmetic regularity
Omnipotence paradox, 116
olya-Vinogradov inequality, 181
Point process, 188
Poisson bracket, 131
Poisson’s equations of motions, 131
Polycyclic group, 236
Prenex normal form, 33
Prime number theorem, 87
Rank (polynomial), 219
Rank reduction argument, 76, 213
Riemann zeta function, 60
Roth’s theorem, 143
Russel’s paradox, 118
Saturation (model theory), 209
onﬂies problem, 106
odinger equation, 130
odinger’s equation of motion, 135
Selberg symmetric formula, 96
Sequential compactness theorem, 22
Siegel’s theorem, 102
sine-Gordon equation, 2
Skolem’s paradox, 21
Stepanov’s method, 184
Strategy stealing argument, 127
Submodularity inequality, 204
Sunﬂower lemma, 222
edi regularity lemma, 154
edi-Trotter theorem, 42
Talagrand’s inequality, 37
Triangle removal lemma, 147
Turing halting theorem, 124
Two-ends condition, 173
Von Mangoldt function, 61, 87
Zeroth-order logic, 27
Zipf’s law, 48
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
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
For additional information
and updates on this book, visit