Erdős–Graham problem

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

The Erdős–Graham problem asks a simple question in number theory. Take all integers greater than 1 (2, 3, 4, …) and split them into finitely many groups. Must one of these groups contain a finite subset whose reciprocals add up to 1? Such a subset is a finite Egyptian fraction representation of 1.

Erdős and Graham guessed that as the number of groups (colors) grows, the largest number you need to use in a suitable subset can be controlled. Formally, for sufficiently many colors r, the largest member of a monochromatic set whose reciprocals sum to 1 should be bounded by a fixed constant raised to the r-th power (b^r), where b is independent of r.

What is known
- A necessary baseline: the bound constant b cannot be smaller than Euler’s number e.
- Ernie Croot proved the conjecture. He showed that such a bound exists, and in fact the largest needed number can be taken as at most e^167000. That bound, while enormous, is finite and uniform in r.
- Croot’s result comes from a more general finding about Egyptian fractions for sets of “smooth” numbers. Roughly speaking, if you look at numbers with only small prime factors that lie in a short interval [X, X^(1+δ)], and if that set contains enough members so that the sum of their reciprocals is at least six, then you can form an Egyptian fraction for 1 from them.
- From this, the Erdős–Graham conjecture follows by a coloring argument. One can locate an interval of the form [X, X^(1+δ)] where the sum of the reciprocals of the smooth numbers inside is at least 6r. In an r-coloring, this guarantees a monochromatic set that meets the conditions of Croot’s theorem.

A stronger development
- In 2021, Thomas Bloom announced a stronger result: any set of integers with positive upper density contains denominators that form an Egyptian fraction for 1. In other words, you don’t even need a special interval or smoothness—just a sufficiently large, dense enough set of integers will contain the needed denominators.

In short, the Erdős–Graham problem connects coloring integers to finding finite, monochromatic subsets whose reciprocals sum to 1, and its resolution shows that such subsets exist with a largest element that grows at most like a fixed base to the r-th power. The ideas hinge on deep properties of smooth numbers and Egyptian fractions, with stronger density-based generalizations now available.