This fascinating book “was conceived while the authors were teaching PhD students in theoretical computer science and discrete mathematics.” The preface conveys computing science as “one of the most mathematical fields besides mathematics itself,” a judgment with which we followers of C. A. R. Hoare, E. W. Dijkstra, J. McCarthy, D. E. Knuth, J.-R. Abrial ... “violently agree.”
Turing Award laureate Richard W. Hamming is quoted [1] as saying, “Does anyone believe that the difference between the Lebesgue and Riemann integrals can have physical significance?” This famous–perhaps notorious–quotation came immediately to mind upon my encounter with the first chapter of this charming, well-written book; that chapter touches on the foundations of probability and includes measure theory and the Lebesgue integral. There is another thought that my (admittedly imperfect) recollection attributes to Hamming; inexactly recalled, it is: “The only real numbers are the numbers that can be stored in computer memory.” Physics proper, hence Hamming’s above example, has a vaguely analogous “difficulty,” namely that the pervasiveness of numbers, the quintessential abstraction on which we should all agree (at least in the case of the natural numbers), may ultimately depend on the existence of a physical medium in which they, or their proxy, are “stored” [2]. (I speculate the latter “numbers” to be discrete.)
Be that as it may, this excellent book disturbed my peace (in a positive sense, I hasten to add). First, I thought that I had long ago, in physics, successfully walked away from the fight between mathematical rigor and sound application, that is, had found a largely reliable way to choose (in any given instance) between Dirac/Feynman [3,4]/Hamming on one side, and von Neumann [5]/Laurent Schwartz [6] on the other. Second, my computing-science slogan pertaining to safety and other critical software, namely, “The distance between theory and practice is zero,” is something I continue to proffer (with the help of homegrown and industrial-strength formal methods for mathematical proofs of a design’s or application’s correctness). The theory that the slogan/pronouncement refers to is, however, discrete mathematics, which the book under review goes considerably beyond. Third, there is the minor vindication regarding my getting caught and looked at askance, many decades ago, at leafing through Halmos’s Measure theory [7] during lunch hour in a software development venue.
The authors characterize their book’s six chapters as independent, self-contained, and not meant to be read sequentially. The chapters are: “Measure and Integral”; “High-Dimensional Geometry and Measure-Concentration”; “Fourier Analysis”; “Representations of Finite Groups”; “Polynomials”; and “Topology.”
It is safely non-falsifiable for me to say that Hamming would have enjoyed, and learned from, the authors’ exposition of Lebesgue integration’s essence. It is certainly the best brief treatment that I’ve seen, but a better description would use the terms “efficient” and “to the point.” The up-front characterization of the Lebesgue partition (set of approximating rectangles) under a curve as horizontal, versus Riemann’s vertical rectangles under a curve, is brilliant pedagogy. The connections to the foundations of probability theory (the theory that I dare say culminates in having actual physical or otherwise real-world significance) are clearly explicated. Chapter 2’s motivation of the relevance of very-high-dimensional geometric structures is highly convincing; Richard Hamming might be gratified by the use of his n-dimensional cube, {0,1}n, and Hamming measure between strings in that space.
Chapter 3’s treatment of Fourier analysis is in accordance with the “modern approach” to harmonic analysis: complex-valued functions on an abelian group G (such as the real numbers R under addition), and the vector-space basis provided for G. One unexpected application (close to my heart) is Blum, Luby, and Rubinfeld’s study of “testing the correctness of computer implementation of some function.”
As you probably know, a representation of a group is an ancillary set of matrices whose multiplication table is isomorphic to that of the abstract group’s operation. Chapter 4 candidly states that “applications of group representations in computer science ... are not (yet) too numerous. But they are usually beautiful and often yield results for which no alternative approach is known.” The application to complexity of digital communications is an interesting instance. In contrast, chapter 5 observes polynomials to be “among the most powerful and most often applied mathematical tools in computer science, and sometimes their use works like a magic wand.” I very much welcome the in-context treatment of Gröbner bases here. In chapter 6, “Topology,” that subject’s advocacy exceeds even that of polynomials: “Topology has spectacular applications in discrete mathematics and computer science.” Many of us would, however, agree with the authors that “the entrance barriers of topology are [unfortunately] high.” This hundred-odd page chapter does a superb job in lowering that barrier.
I recommend this exceptional book as a source of insight into important, advanced, and uncommon topics in computing science and computer applications.
