A question of Erdős and Graham on Egyptian fractions

A question of Erdős and Graham on Egyptian fractions, Discrete Analysis 2025:28, 13 pp.

An Egyptian fraction is a way of writing a rational number as a sum of reciprocals of positive integers with distinct denominators. It is a nice exercise to show that every rational number can be written in this way. For example, to write $3/7$ one can observe that $1/n=1/(n+1)+1/n(n+1)$ for every $n$ and thus write $3/7$ as $1/7+1/8+1/56+1/7$. The second $1/7$ can then be rewritten as $1/8+1/56=1/9+1/72+1/57+1/3912$. Egyptian fractions are so called because (to oversimplify the history somewhat) the ancient Egyptians had a preference for reciprocals over “vulgar fractions” of the form $m/n$ with $m>1$.

Egyptian fractions have also led to some interesting modern mathematical problems. For example, a well-known conjecture of Erdős and Graham (not the one addressed in this paper) asked whether if the positive integers are coloured with finitely many colours there exists a finite set $A\subset\mathbb N$ not containing 1 such that $\sum_{a\in A}a^{-1}=1$. The answer is yes, as was proved by Ernie Croot in 2003. In 2021, Thomas Bloom obtained the density version of this theorem: that is, he showed that if $X\subset\mathbb N$ is a subset of positive upper density, then $X$ has a finite subset $A$ such that $\sum_{a\in A}a^{-1}=1$.

The question of Erdős and Graham that is addressed in this paper concerns the number of ways that 1 can be expressed as an Egyptian fraction using numbers with denominator at most $n$. A trivial upper bound for this is $2^n$, so they asked whether that could be matched by a lower bound of $2^{n-o(n)}$. A negative answer was given to this question in 2017 by various people in response to a MathOverflow post (details can be found in the paper). That is, an upper bound of $2^{cn+o(n)}$ was obtained for some $c<1$. The particular $c$ can be defined as follows. First, let $\lambda$ be the unique real number such that $\int_0^1\frac{\mathrm dy}{y(1+\mathrm e^{\lambda/y})}=1$. Then let $c=\int_0^1 h(1/(1+\mathrm e^{\lambda/y}))\mathrm dy\approx 0.91117$, where $h$ is the binary entropy function $h(x)=-\log_2(x)-\log_2(1-x)$.

We can make slightly more sense of this constant by approximating the second integral by $\sum_{m=1}^n h(1/(1+e^{\lambda n/m}))$. This is the entropy of a sum of $n$ independent Bernoulli random variables $X_1+\dots+X_n$, where $X_m=1$ with probability $1/(1+e^{\lambda n/m})$. Thus, the number of ways of writing 1 as an Egyptian fraction with denominators at most $n$ is in some sense at most the number of “typical” sequences $(X_1,\dots,X_n)$ one obtains when they are drawn from this distribution.

This paper provides a matching lower bound: that is, it shows that 1 can be written in at least that number of ways as an Egyptian fraction with denominators at most $n$. In fact, the proof works just as well for any rational number $x$ – one simply has to replace $\lambda$ by $\lambda(x)$, which is the unique real number such that $\int_0^1\frac{\mathrm dy}{y(1+\mathrm e^{\lambda/y})}=x$.

The rough idea of how they prove this is to start by letting $U$ be the set of integers in $[n]$ after removing (i) those with a prime power factor greater than $n^{1-\epsilon} / 2$, (ii) those divisible by the lcm of prime powers up to $L$ (for some parameter $L$), and (iii) numbers of the form $qm$ where $q$ is a prime power power at most $n^{1-\epsilon}/2$ and $m$ is an integer in $[q^\epsilon, 2 q^\epsilon]$. Although it might seem that a lot is removed, we in fact have that $|U|=n(1 - O(\epsilon))$ for sufficiently large $L$ big enough. Next, they count the number of subsets of $U$ whose sum of reciprocals is a little smaller than $x$, of size less than $x (1 - \eta)$, say. In fact, most of the subsets will have sum of reciprocals near to that. Note that if $S$ is one of these subsets and $s = a/b$ is equal to $\sum_{n\in S}\frac 1n$, then the highest prime-power divisor of $b$ will be less than $n^{1-\epsilon} / 2$.

The idea now is to try to “clean up” this number $s$, by adding some more elements to $S$, until the associated sum is exactly $x$. And one needs to keep track of how adding these elements affects the count of the subsets for which the initial sum of reciprocals lands near $x$. This cleaning up is achieved by setting aside a small subset of $[n]$ that the authors call a “reservoir”. Using numbers from the reservoir, they first reduce the denominator of $a/b$ to something manageably small, and then they make up the remaining difference to their target number $x$. As they point out, this process is somewhat reminiscent of the absorption method. Crucial use is made in the argument of a recent result of Conlon, Fox and Pham that shows that any reasonably large subset $A$ of $[n]$ contains a not too large subset $A'$ such that the set $\Sigma(A')$ of subset sums of $A'$ contains a homogeneous generalized arithmetic progression with a homgeneous translate that contains many elements of $A$.

The main result of the paper was obtained independently with a different proof by Yang P. Liu and Mehtaab Sawhney.