American Scientist

STRUCTURE AND RANDOMNESS: Pages from Year One of a Mathematical Blog. Terence Tao. xii + 298 pp. American Mathematical Society, 2008. $35.

Terence Tao is an almost ridiculously distinguished young mathematician, perhaps best known for his work in combinatorics and number theory, especially the theory of arithmetic progressions of prime numbers. In early 2007, he turned the “what’s new” section of his home page into a blog, and his new book, Structure and Randomness, collects some of the writings that first appeared there: expository notes on mathematical results that are or ought to be well-known, sketches of unusual proofs for classical theorems, the texts of three invited lectures, a selection of discussions of open problems, and a few curiosities, including a famous—or infamous—attempt to explain quantum mechanics in terms of the video game Tomb Raider. What should we make of this?

The first thing to say is that Tao is a mathematician writing for other mathematicians. The knowledge of modern mathematics needed to follow everything in this book, or on his blog, is very broad. The implied reader of the expository notes is familiar with abstract algebra, algebraic geometry, functional analysis, graph theory, harmonic analysis, Lie algebras, mathematical logic, measure theory, number theory, partial differential equations, real analysis and representation theory, among other topics; other fields (most notably ergodic theory) appear as background to the lectures and as open problems. Readers needn’t have very deep knowledge of any of these subjects, and no one chapter uses them all, but Tao is certainly not writing for neophytes. (Online, he usually links terms to their Wikipedia definitions, but that doesn’t work in a book, of course.) Given that background, however, Tao does a fine job of providing new insights into old ideas, building intuition about why results come out the way they do, exploring why certain problems are at once interesting and hard, and explaining tricks (of which more later).

Despite the range of subjects Tao covers, certain themes keep recurring. (It’s an interesting question whether this reflects the author’s preoccupations or is just inevitable given the quantity of material.) We can call these randomness, obstacles and tricks.

The first of these themes is the one announced by the title and treated most fully in chapter 2.1: the dichotomy between structure and randomness. The idea is to divide a mathematical domain into three parts: the highly structured or regular objects (knowing a little about one of them, or about one of its parts, enables broad inferences about the rest); the effectively random objects, which are in some sense uncorrelated with or orthogonal to all the structured objects; and the “hybrid” objects built from both structured and random components. Powerful theorems about the long-run or large-size behavior of objects are proved through decomposing the system into its structured and random parts and considering them separately.

A good illustration of this idea comes from ergodic theory. (What follows is simpler than, but related to, Tao’s examples.) Classical ergodic theory begins with a dynamical system or stochastic process x₁, x₂, . . . x_n, . . ., takes a function f of the state, and considers what happens to time averages of the function, (f(x₁) + f(x₂) + . . . + f(x_n))/n, when the time n goes to infinity. The ergodic theorems tell us when these time averages converge to deterministic limits and characterize those limits. The basic idea is that some functions are invariant under the dynamics, so thatf(x_n)=f(x_n+1). One then represents an arbitrary observable function as a sum of invariant functions and noninvariant parts, and shows that the former are left alone by time averaging but the contributions of the latter inevitably tend to cancel one another out. Similar ideas recur throughout probability theory (for instance, the central limit theorem), although oddly enough Tao says almost nothing about this connection, nor does he mention the information-theoretic account of randomness in terms of algorithmic complexity.

The second theme running through the book is that of obstacles to certain kinds of results or solutions, and the characterization and removal of obstacles. In particular, Tao is interested in results that say that the only obstacles to finding solutions are (in some appropriate sense) the obvious ones. If one is trying to solve a set of polynomial equations, for example, the obvious obstacle is that the equations are inconsistent with one another. The Nullstellensatz (“theory of zeros”) of David Hilbert (chapter 1.15) says, roughly, that this turns out to be the only obstacle, that any consistent set of equations has at least one solution. Tao’s remarkable work on “compressed sensing” (described here in chapters 1.2 and 2.2) combines this theme and the previous one: This is a family of techniques that allow one to reconstruct a function over some domain (such as a time series or image) from measurements of its values on a small fraction of the domain, provided that the locations where measurements are taken are sufficiently random. (This is closely related to the “lasso” method of selecting variables for linear regressions in statistics.) Whereas in ergodic theory one wants the nonrandom, invariant behavior to prevail, in compressed sensing the structured sets of observations are precisely the obstacles to be avoided.

Tao’s third theme is tricks: patterns of establishing results that replicate across many situations, but in which any one result is too small to be a theorem in its own right, while the general pattern is too vague. These are an important part of how math actually gets done, but by their nature they tend not to have a recognized place in the curriculum, getting passed down by oral tradition, or by being absorbed by those who are lucky enough not only to run across a paper using the trick, but also to guess that it will generalize. There are numerous tricks throughout the book, and one of the nicest chapters, 1.9, expounds a family of tricks for improving inequalities, which Tao calls amplification.

This brings us, finally, to the fact that this book began as a series of blog posts. The essential fact about blogs is that they are extremely cheap to produce, costing only Internet access and the writer’s time. This means that there is no minimum size for publications, and little or no role for the filters (peer review, editors) used in scholarly and commercial publishing to keep resources from being wasted on complete rubbish. Conceivably, Tao could have persuaded a math journal to publish a pedagogical note on the amplification trick, but maybe not, even with his considerable authority within the discipline. With a blog, valuable material that fails to make it past the filters of traditional media can nonetheless find an outlet. Moreover, that material finds a public outlet, one that makes the traditional “invisible colleges” of scientific disciplines visible to the wider world, including those who would like to join them and contribute to the disciplines. Here Tao’s blog has been exemplary, and the endnotes to these chapters record many improvements that are credited to online commenters and interactions.

Of course, filters exist for a reason, and blogs that lack them may, as a consequence, disseminate plenty of valueless material. In a well-functioning intellectual ecology, we would figure out a way to combine the advantages of the traditional filtering mechanisms with the advantages of nearly free online dissemination. Having the imprimatur of publication follow for blogs that have proved themselves might be a reasonable way forward.

But such suppositions are almost always overtaken by events, the future being stranger than anyone really expects. What’s important is that Tao has a book, and a blog, that mathematicians will definitely want to read, either on their screens or on dead trees, and it will be of interest to mathematically sophisticated readers coming from physics, statistics, economics, computer science and doubtless other disciplines. In Structure and Randomness we have a fascinating glimpse into the mind of one the best mathematicians working today.

Cosma Shalizi is an assistant professor in the statistics department at Carnegie Mellon University and an external professor at the Santa Fe Institute. He is writing a book on the statistical analysis of complex systems models. His blog, Three-Toed Sloth, can be found at http://bactra.org/weblog/.