Ron Graham passed away, but he lives on…

 Cropped from tribute by Tom Leighton

Ron Graham just passed away Monday at the age of ${84}$ in La Jolla near UCSD.

Today Ken and I wish to say a few words about Ron.

Tributes are being written as we write, including this from the Simons Foundation. Here is the American Mathematical Society announcement, which we saw first:

Ron Graham, a leader in discrete mathematics and a former president of both the AMS (1993-1994) and the MAA (2003-2004), died on July 6. He was 84. Graham published more than 350 papers and books with many collaborators, including more than 90 with his wife, Fan Chung, and more than 30 with Paul Erdős. He was known for his infectious enthusiasm, his originality, and his accessibility to anyone who had a mathematics question.

A tribute by Brady Haran embeds several short videos of Ron and his work. Fan’s own page for Ron has much more. We have made a collage of images from his life:

Ron was special and will be greatly missed by all. We at GLL send our thoughts to his dear wife, Fan. Ken and I knew Ron for many years. Ken knew Ron since a visit to Bell Labs in the 1980s and meeting Fan too at STOC 1990. I knew Ron since I was at Yale in the 1970’s—a long time ago. I recall fondly meeting him for the first time when he was at Bell Labs.

## Some Stories

Ken and I thought we would give some personal stories about Graham.

${\bullet }$ Ken’s story is told here. In breaking a confidence by telling Erdős the secret about Bobby Fischer recounted there, Ken hoped that it would spread behind the scenes to enough people that Fischer would be less blamed for failing to play Anatoly Karpov in 1975. Since Erdős was staying with the Grahams, presumably it would have emerged there. The social excursion during STOC 1990 was a dinner cruise in Baltimore’s harbor. Ron and Fan and Ken found each other right away, and some questions to Ken about chess quickly went to the Fischer topic. At least Ken knows the secret was retold at least once.

${\bullet }$ Ron told me once that he was the accountant for Erdős. One of Ron’s jobs was to keep track of the prize money that Erdős owed. Ron would send out the checks to whoever solved the next problem. One of the brilliant insights of Erdős was to make the problems hard, but at least some where solvable. Ron told me that for years no one would actually cash the checks. They would frame them and proudly display them.

Ron said that he liked this for the obvious reason—less cash for Erdős to have to pay. But the advent of color xerox machines in the 1970’s changed this. He told me that people began cashing the checks and displaying the color copy. Bummer.

${\bullet }$ My first talk at Bell Labs was on my work on the planar separator theorem—joint work with Bob Tarjan. At the beginning of the talk I saw that Ron had a pile of papers on his desk. He was a manager and I guessed he had some paper work to do. I gave my talk. At the end I when up to Ron in the back and he said:

I did not get any work done.

I still fondly remember that as high praise.

${\bullet }$ Graham loved to do hand stands. I recall walking around Bell Labs one day when out of the blue Ron did a full handstand. He said that he liked to do these on the hand rail of the stairs. The trick he said was: “To not fall down.”

I searched for him doing handstands and found out he and Fan lived in a modern beautiful house.

When two mathematicians found a circular home designed by architect Kendrick Bangs Kellogg in La Jolla, they treasured their unique discovery.

## Fun and Games

Ron kept a simply organized page of all his papers. They are not sorted by subject or kind, but the titles are so descriptive that you can tell at a glance where the fun is. A number of them are expositions in the popular magazines of the AMS and MAA.

Among them, we’ll mention this note from 2016, titled “Inserting Plus Signs and Adding.” It is joint with Steve Butler, who penned his own reminiscence for Lance and Bill’s blog, and Richard Strong.

Say that a number ${w}$ is “reducible” to a number ${v}$ in one step (in base ${b}$) if there is a way to insert one or more ${+}$ signs into the base-${b}$ representation of ${w}$ so that the resulting numbers add up to ${v}$. For example, 1935 is reducible to 99 via ${1 + 93 + 5}$. The number 99 reduces only to 18 via ${9+9}$, and 18 reduces only to 9, which cannot be reduced further. Thus Ron’s birth year took ${3}$ reduction steps to become a single digit. However, doing ${1+9+3+5}$ gives 18 straightaway and thus saves a step. The paper gives cases where inserting ${+}$ everywhere is not a quickest way to reduce to a single digit.

Definition 1 For any base ${b}$ and number ${n \geq 1}$ denoting an input length, not magnitude, define ${f_b(n)}$ to be the least integer ${m}$ such that all base-${b}$ numbers of length ${n}$ can be reduced to a single digit within ${m}$ steps.

The question—of a complexity theoretic nature—is:

Given ${b}$, what is the growth rate of ${f_b(n)}$ as ${n \rightarrow \infty}$?

Here are some possible answers—which would you expect to be correct in the case where ${b}$ is base 10?

• ${f_{10}(n) = \Theta(\sqrt{n})}$.

• ${f_{10}(n) = \Theta(n^{1/10})}$.

• ${f_{10}(n) = O(\log n)}$.

• ${f_{10}(n) = O(\log\log n)}$.

• ${f_{10}(n) = O(\alpha(n))}$, where ${\alpha}$ is the inverse Ackermann function.

Your expectation might be wrong—see the paper for the answer and its nifty proof. For a warmup, if you want to answer without looking at the paper, prove that the final reduced digit is the same regardless of the sequence of reductions.

Ron is also known for very big integers, including one that held the record for largest to appear in a published mathematical proof. You can find it among the above tributes and also on a T-shirt. We could also mention his role in the largest proof known to date—at 200 terabytes it almost doubles the size of the tables for proving results of seven-piece chess endgames.

If you desire serious fun, look also to Ron’s books. He wrote several, including co-authoring the nonpareil textbook Concrete Mathematics with Don Knuth and Oren Patashnik.

## Some Prizes

Ron, in the tradition famously followed by Erdős, liked to put money on problems. A $10 dollar problem was much easier than a$100 one. A $1,000 one is extremely hard, and so on. In Ron’s paper on his favorite problems he stated this one: Let ${H_{n} = \sum_{j=1}^{n} \frac{1}{j}}$. Challenge: prove the inequality for all ${n \ge 1}$, $\displaystyle \sum_{d | n} d \le H_{n} + \exp(H_{n})\log(H_{n}).$ And he put the prize at$1,000,000. He added:

Why is this reward so outrageous? Because this conjecture is equivalent to the Riemann Hypothesis! A single ${n}$ violating would imply there are infinitely many zeroes of the Riemann zeta function off the critical line ${R(z) = 1}$. Of course, the \$1,000,000 prize is not from me but rather is offered by the Clay Mathematics Institute since the Riemann Hypothesis is one of their six remaining Millennium Prize Problems. We hope to live to see progress in the Challenges and Conjectures mentioned in this note, especially the last one!

Alas Ron did not get to see this resolved. Nor of course did Erdős, nor may any of us. But Ron is prominently mentioned on another Simons page where Erdős lives on, and so may Ron.

## Open Problems

Ron died at age ${84}$. Perhaps he liked that it is the sum of a twin prime ${41 + 43}$, and also three times a perfect number. We will always remember ${84}$ because of Ron. Added 7/10: ${84}$ is also his current h-index according to Google Scholar. HT in comment.

[some word changes, update about h-index]

July 10, 2020 1:59 pm

I wonder if there are other variants of the inequality being equivalent to the Riemannian hypothesis, but with other pairs of functions (f,g) instead of (exp,log).

2. July 10, 2020 8:00 pm

Hat-tip to Dan Fleetwood of Vanderbilt University for observing that 84 is also Ron Graham’s current h-index.

July 12, 2020 8:42 am

I didn’t know Ron Graham, but should have. His contributions to the juggling world were also major.

https://www.juggle.org/ron-graham-obituary/

I just got back into juggling after a long hiatus, and while I was gone, all sorts of new wonderful things appeared, among them siteswap (a mathematical notation for describing and analyzing juggling patterns that’s also a major tool for teaching juggling now) and Mills Mess, a seriously kewl pattern. Ron had a major role in both.

By the way, that obit mentions that he could juggle six balls well. That’s seriously impressive.