The Bactra Review: Occasional and eclectic book reviews by Cosma Shalizi   140

Structure and Randomness

Pages from Year One of a Mathematical Blog

by Terence Tao

Obstacles and Tricks

[This review appeared in the March-April 2009 issue of American Scientist.]

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 homepage into a weblog, and this book collects some of the writings which first appeared there: expository notes on mathematical results which are our 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, like 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 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 here.) 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 just an inevitable consequence of writing enough 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 about 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 x1, x2, ... xt, ..., takes a function f of the state, and considers what happens to time-averages of the function, (f(x1) + f(x2) + ... + f(xn))/n, when the time n goes to infinity. The ergodic theorems say 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 that f(xt) = f(xt+1). One then represents an arbitrary observable function as a sum of invariant functions and non-invariant part, and shows that the former are left alone by time-averaging but the contributions of the latter inevitably tend to cancel each other out. Similar ideas recur throughout probability theory (for instance, the central limit theorem), though oddly enough Tao says almost nothing about this connection, nor does he mention the information-theoretic account of randomness in terms of algorithmic complexity.

This brings us to the second theme running through the book, that of obstacles to certain kinds of results or solutions, and characterizing and removing obstacles. In particular, Tao is interested in results which 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 "Nullstellenansatz" 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 which allow one to reconstruct a function over some domain (such as a time series or image) from measuring its values on a small fraction of the domain, provided 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.) While in ergodic theory one wants the non-random, 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 which replicate across many situations, but where 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 lucky enough not only to run across a paper using the trick, but also guessing that it will generalize. One of the nicest chapters in this book is 1.9, expounding a family of tricks for improving inequalities which Tao calls "amplification", but there is a lot of this throughout the book.

This brings us, finally, to the fact that this book began as a series of weblog 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 on the one hand there is no minimum size for publications, and little or no role for the filters (peer review, editors) used in traditional scholarly and commercial publishing to keep from wasting too many resources 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 disciplinary authority. With a blog, valuable material which is rejected by the traditional filters can nonetheless find an outlet. Moreover, it finds a public outlet, one which 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 after-notes to these chapters record many improvements due to on-line commenters and interactions. Of course, the filters of traditional publishing exist for a reason — plenty of value-less material gets disseminated through blogs. 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 on-line dissemination. The present case, where the imprimatur of publication follows on blogs which have proved themselves, might be a reasonable way forward.

Guesses like that are almost always overtaken by events, the future being stranger than anyone really expects. What's more important is that this is a book, and a blog, which mathematicians will definitely want to read, either on their screens or on dead trees, and it will be of interest to mathematically mature 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.

xii+298 pp.


Currently in print as a paperback, ISBN 978-0-8218-4695-7 [buy from Powell's], US$35
14 January 2009