Structure and Randomness: pages from year one of a mathematical blog

Terence Tao

American Mathematical Society, 2008

298 pages

ISBN-10: 0-8218-4695-7

ISBN-13: 978-0-8218-4695-7

mbk-tao-cov_0001

Last updated Nov 25, 2022

This is a book version of my blog, covering many (though not all) of my articles in 2007, reworked into a publishable format (and in particular, with formal and updated references).

A draft copy of the book is available here. Note that the formatting for this internet version is significantly different from that in the final print version, in particular the page numbering does not correspond at all.

Here is a (2MB) PDF file containing the front cover of the book.

The official AMS web page for this book is here.

A review of the book for the American Scientist is here.

Here is a review for the MAA.

— Errata —

  • Page 21: In Proposition 1.8, k/\varepsilon+1 should be k/\varepsilon+k.
  • Page 22: In Proposition 1.10, 2^{1/\varepsilon}+1 should be 2^{1/\varepsilon+1}.Page 51: In Lemma 1.34(2), hf'(x) should be hL.
  • Page ???: In the start of Section 1.9, the requirement a_d \neq 0 should be added to the definition of a linear recurrence sequence.
  • Page 54: The phrase “nonstandard ultrafilter on {*} {\Bbb N}” requires some clarification.  It should be “ultrafilter on {*}{\Bbb N} that extends an ultraproduct of nonprincipal ultrafilters on {\Bbb N}“.
  • Section 2.2, page ???: “need thus need” should be “thus need”.
  • Page ???: In the proof of Lemma 2.28, in the final two displays, the left absolute value and integral signs should be interchanged.
  • Page 86: In the final display, the exponent of p on the LHS should be deleted. Similarly on the first display of page 87.
  • Page 95, Figure 1: The graph of K_{3,3} is missing two edges (namely, the long diagonal edges between opposite corners of the graph).
  • Page 96: The inequality |E| \leq 3|V| - 6 is only valid for connected graphs with at least one cycle.  In general, one only has |E| \leq 3|V|.  One must then delete all terms involving the number 6 in the rest of the section.  One can then replace “To solve the optimisation problem exactly, one needs to solve a cubic; but we can perform a much cheaper computation” by “One can solve the optimisation problem exactly, but we can perform a cheaper computation”.
  • Page 101: Footnote 67 is incorrect and should be deleted.
  • Page 102: (A+A) \times (A \cdot A) should be (A \cdot A) \times (A + A).
  • Page 103: The sentence “More generally, any Riemannian manifold…” is incorrect and should be deleted, replaced instead with the sentence “Similarly, the hy0erbolic plane {\bf H} is isomorphic to SL(2,{\bf R})/SO(2)“.
  • Page 104: In first paragraph: the modular curve should be SO(2,{\mathbf R}) \backslash SL(2,{\mathbf R}) / SL(2,{\mathbf Z}).  In the footnote, add “and an obvious left action of SO(2,{\mathbf R}),” after the final comma.
  • Page 128: In the second and third displays, \frac{1}{t^{p(1-p)}} should be t^{p(1-p)}.
  • Page 129: “decaying faster” should be “decaying faster or having smaller amplitude”.
  • Page 143: The proof that 1/\alpha \leq \hbox{maxflow} is not correct as stated (the perturbations indicated do not preserve the property of being an \alpha-flow).  A correct argument is as follows.  Call an edge of an \alpha-flow unsaturated if it has weight strictly between 0 and \alpha, and similarly call a vertex unsaturated if its net inflow or outflow is strictly less than \alpha.  Observe that if e is an unsaturated edge, then the final vertex u of e will either have an unsaturated edge leading out of it (if u is unsaturated) or another unsaturated edge leading into it (if u is saturated).  Similarly, the initial vertex u’ of e will either have an unsaturated edge leading into it (if u is unsaturated) or another unsaturated edge leading out of it (if u is saturated).  Thus, if there is at least one unsaturated edge, then by iterating the above observations, one can find an oriented cycle along unsaturated edges with the property that at any saturated vertex u, the number of edges flowing along the cycle into u equals the number of edges flowing against the cycle into u, and the number of edges flowing along the cycle out of u equals the number of edges flowing against the cycle out of u. For this cycle, one can modify the flow as indicated in the text to reduce the number of edges in the \alpha-flow.
  • Page 137: In the last line of Case 1, “multiply (1.47) by…” should be “raise (1.47) to the power r' and then multiply by…”, and r+r' should be (r+1)r'.
  • Page 148: In the first line, \overline{F_v} = \overline{F_{-v}} should read F_v = \overline{F_{-v}}.
  • Page 180: In the second display, x/\xi should be x \xi.
  • Page 257: When selecting the large prime p, it is necessary that p is larger than 2.  This is needed in order for the binomial expansion of (1+pB)^n to be expressible in the desired form \sum_{j=0}^\infty p^j P_j(n) where the polynomials P_j have coefficients in the p-adic integers, because the number of times p divides p^k / k! can be bounded below by k - k/(p-1), which goes to infinity as k \to \infty provided that p is larger than 2.
  • Page 267: In the third display, \sum_{d \leq 2N} \frac{\mu(d)}{d} \log^2 d should be \sum_{d \leq N} \frac{\mu(d)}{d} \log^2 \frac{N}{d}.
  • Section 2.9.4: The application of the tensor power trick to the Riesz-Thorin theorem is only valid in the regime q \geq p.
  • Section 2.10?: In (2.8), \sum_d |\lambda_d| should be \sum_d |c_d|.

Thanks to Ravindra Bapat, Alan Chang, Dion,  Norman Hardy, Matthew Kahle, Chris Kimmel, JamesL, Avi Levy, Russ Lyons, Arturo Magadin, Kirane Mokhtar, David P. Moulton, Kamil Rychlewicz , David Speyer, Caleb Stanford, Nikodem Szpak, Tobias and Tony, Chao Weng, Sheng-Peng Wu, and Yuncheng  for corrections.