The fine art of crate digging

Alexeev and Mixon's resolution of Erdős problem 707 and the vastness of the library.

In the comments of Friday’s post, Will P sent me a delightful paper by Boris Alexeev and Dustin Mixon. They resolve a 50-year-old open Erdős problem by finding the solution in an 80-year-old paper. If you’re at all mathematically inclined, Alexeev and Mixon’s paper is super fun to read. The mathematics is accessible, the bemused tone adds suspense, and the long section about vibe-coding in Lean using ChatGPT is hilarious. However, I want to emphasize from the get-go that the AI is a complete sideshow here. Alexeev and Mixon tell a fascinating story about how even experts are incapable of fathoming their own fields.

As I wrote last time, Paul Erdős posed thousands of challenging math problems. He was fond of some more than others, and often offered prize bounties for solutions he most desired. According to Thomas Bloom’s Erdős problems database, 11 of those bounties were for a thousand dollars or more. Problem 707, resolved in Alexeev and Mixon’s paper, is one of these.

The fun part of number theory is that you can often explain its open problems to anyone. Problem 707 asks whether every finite Sidon set can be extended to a finite perfect difference set. A set is a Sidon set if all of its pairwise differences are distinct. An example is {1, 2, 4, 8, 13}. The pairwise differences are {1, 2, 3, 4, 5, 6, 7, 9, 11, 12}. We’re missing 8 and 10. Erdős wondered if you could add integers to this set to get a complete list of differences that doesn’t skip any numbers, at least in modular arithmetic. It’s an esoteric question, but not that much weirder than Fermat’s Last Theorem, and not much harder to state. The other fun part of number theory is that you never know when something simple to state is completely impossible to prove.

Problem 707 puzzled mathematicians for half a century. Or so it seemed. When Alexeev and Mixon were working on this problem, they tried applying some ideas from projective planes, a powerful tool in combinatorics developed by mathematician Marshall Hall. In a 1947 paper by Hall, they found the following sentence:

“From this theorem it immediately follows that there are many sets of integers satisfying the conditions of [Erdos’ problem] which cannot be extended to any finite [perfect] difference set. For example the set −8, −6, 0, 1, 4 may not be so extended.”

Hall had derived a counterexample of Erdős’ conjecture thirty years before Erdős had conjectured it.

Alexeev and Mixon write:

“Clearly, it appears that Erdős was not aware of this result. The authors of this paper were also unaware of this result, even though they performed a reasonably deep literature search prior to starting this project. (In fact, no large language model could find Hall’s result, even with substantial prompting that the result indeed exists.) Instead, the paper was discovered by accident when searching for support for Conjecture 14.”

Now, the more I look into it, the more amazed I am that this Erdős problem remained open. First, I slightly disagree with Alexeev and Mixon that Hall just casually wrote a throwaway sentence about perfect difference extensions. In the previous section of Hall’s paper, he proves that every Sidon set has an infinite extension. He then devotes a long paragraph to the question of whether finite extensions exist. Here are the first and last sentences of that paragraph:

“As an example of the application of the theorem, consider the set -8, -6, 0, 1, 4... There is no corresponding theorem for finite planes such as Theorem 3.1. In the next section it will be shown that there is no finite difference set including the numbers -8, -6, 0, 1, 4.”

It’s clear Hall thought the finite extension problem was an interesting question. He just didn’t flag the counterexample as a theorem or proposition.

Second, it’s not like this Hall paper is particularly esoteric. While the 1947 paper is not as famous as Hall’s 1943 paper on projective planes, it’s still been cited hundreds of times. Hall was a notable mathematician and had been a professor at Ohio State and Caltech. His paper appeared in the reputable Duke Mathematical Journal. And the paper is still regularly cited today. For example, Sarah Peluse cites it in her 2020 work on finite difference sets.

Now, Peluse perhaps wasn’t aware of Erdős’ not-so-open open problem. But many mathematicians were aware of both Hall’s paper and Erdős’s conjecture and failed to see the connection. Alexeev and Mixon note that in a 2004 book called Unsolved Problems in Number Theory, Richard Guy cites Hall’s paper two sentences before stating Erdős’ conjecture! Here’s Guy’s passage:

“Marshall Hall has shown that numerous non-prime powers cannot serve as values of k and Evans & Mann that there is no such k < 1600 that is not a prime power. It is conjectured that no perfect difference set exists unless k is a prime power. Can a given finite sequence, which contains no repeated differences, always be extended to form a perfect difference set?”

Guy actually refers to Hall’s paper twice in his book.

Anyway, this is an amazing story about the vastness of the literature. We have no idea what’s in our libraries, even when we restrict our attention to papers with hundreds of citations. To be fair to all of us, we all cite papers that we have not read in their entirety. This is to be expected. We don’t write academic papers to be read like novels. If the authors don’t explicitly state a claim as THEOREM or LEMMA or CONJECTURE, it’s easy to just skim past it.

Still, it’s surprising that Erdős didn’t know about this. He was going around offering a thousand dollars to solve his simply stated problem. How is it that no one he talked to knew about Hall’s example?

And how is it that ChatGPT, which we know is trained illegally on paywalled papers, couldn’t find Hall’s paper for Alexeev and Mixon? It was probably too busy coming up with bad pull-up programs. Get it together, ChatGPT.