Ronald L. Graham (1935-2020)

Mathematician Ronald L. Graham died on July 6, 2020, at the age of 84. He was one of the principal architects of the field of discrete mathematics and made important contributions to computational geometry, Ramsey theory, notions of randomness, and other topics. He also served as president of the American Mathematical Society (1993-1994) and the Mathematical Association of America (2003-2004).

Ron Graham in August 1990 at the 75th anniversary of the Mathematical Association of America, held in Columbus, Ohio.

For more than 20 years while I was a reporter and writer at Science News, I relied on Ron Graham for advice, comments, and news tips. He was especially helpful in pinpointing significant developments in mathematics and patiently explaining their relevance and importance.

Graham's remarks on the difficulties of establishing mathematical certainty inspired the title of my second book: Islands of Truth: A Mathematical Mystery Cruise (W.H. Freeman, 1990).

I wrote about Graham's own research on a number of occasions.

Inside Averages

What can you deduce when you know certain averages but the original data from which the averages were computed are missing?

Considering that question in the 1980s, Ron Graham wondered, for example, to what extent secret data contained in confidential files can be uncovered if the right questions are asked. Such considerations led him to collaborate with Persi Diaconis to explore the discrete Radon transform and its inverse, an important mathematical tool in tomography.

Cracking a confidential database can be likened to the old parlor game of twenty questions. A player receiving only yes-or-no answers yet asking the right sequence of pertinent questions can often deduce the identity of some hidden object or person.

In the same way, the answers to a series of general questions addressed to a particular database could add up to a revealing portrait of something that is supposed to be secret.

A simple example shows how such a scheme might work. Suppose someone wants to find out Alice's salary. The inquisitor has access to information revealing that the average of Alice's and Bob's salaries is $30,000; the average of Alice's and Charlie's salaries is $32,000; and the average of Bob's and Charlie's salaries is $22,000. This provides enough information to deduce that Alice's salary is $40,000.

Researchers often face a situation in which certain averages are known but the original data are missing. If eight data points happen to be identified with the eight vertices of a cube and each of the eight numbers is the average of its three nearest neighbors, then it's possible to deduce the actual but currently hidden value associated with each vertex.

The actual value of vertex A is the sum of the averages shown at B, D, and E minus twice the average at G: (3 + 5 + 5) − 2(5) = 3. The values of the other vertices are 6, 3, 6, 9, 3, 12, and 9.

In this situation, the actual value at each vertex is equal to the sum of the nearest-neighbor averages minus double the average at the corner farthest from the point of interest. Curiously, the point that makes the biggest contribution to the answer is the one that's farthest away.

Diaconis and Graham developed a mathematical theory, based on the idea of discrete Radon transforms, that helps to decide how many and which averages are needed to crack a database or to analyze statistical data. Their results appear in the article "The Radon Transform on Z₂^k," published in the Pacific Journal of Mathematics.

At the root of their exercise is the mathematical concept of how completely a bunch of averages captures the mathematical relationship underlying a data set.

See also "Pennies in a Tray."