betaFeedback

Abstract

We prove a conjecture of Erdős: for every sufficiently large integer bb, every rational number a/ba/b with 1≤a<b1\le a\lt b is a sum of O(log⁡log⁡b)O(\log\log b) distinct positive unit fractions, with an absolute implied constant. This order is best possible when the numerator varies. We also show that both the number of expansions of 1 with exactly kk distinct terms and the least integer at least 2 that never occurs as a denominator in such an expansion grow doubly exponentially in kk: their double logarithms have order kk.

Introduction

An Egyptian-fraction expansion of a positive rational number is a finite sum of distinct reciprocals of positive integers. For integers 1≤a<b1 \le a < b, let N(a,b)N(a,b) be the least kk for which

ab=1n1+⋯+1nk,2≤n1<⋯<nk,ni∈Z,\frac{a}{b}=\frac{1}{n_1}+\cdots+\frac{1}{n_k},\qquad2\le n_1<\cdots<n_k,\qquad n_i\in\mathbb{Z},

and put N(b)=max⁡1≤a<bN(a,b)N(b) = \max_{1 \leq a < b} N(a,b). The fractions a/ba/b need not be in lowest terms, and the denominators nin_i have no prescribed upper bound. The greedy algorithm shows that such expansions exist. We determine the order of their maximum minimum length. Individual numerators can have much shorter expansions: for example, N(1,b)=1N(1,b) = 1 for every b≥2b \geq2.

Theorem 1.1. There are absolute constants c1,c2>0c_1,c_2 > 0 and b0b_0 such that, for every integer b≥b0b \geq b_0,

c1log⁡log⁡b≤N(b)≤c2log⁡log⁡b.c_1 \log\log b \leq N(b) \leq c_2 \log\log b.

In particular, the upper bound holds for every integer numerator 1≤a<b1 \leq a < b.

Nakayama’s study of N(a,b)N(a,b) emphasized arithmetic criteria for expansions with few terms [18 Section I]. The uniform problem asks how these minimum lengths behave as the numerator varies over a fixed denominator. In 1950, Erdős reported de Bruijn’s bound N(b)≪log⁡b/log⁡log⁡log⁡bN(b) \ll\log b/\log\log\log b and improved it to N(b)≪log⁡b/log⁡log⁡bN(b) \ll\log b/\log\log b [6 p. 195, Theorem 1]. He proposed the double-logarithmic upper bound and proved the matching lower order, already for the numerator b−1b-1 [6 p. 195, Theorem 2]. The question appears again in Erdős and Graham [8 pp. 37–38] and is recorded as Erdős Problem 304 [2]. Vose subsequently obtained N(b)≪log⁡bN(b) \ll\sqrt{\log b} [23]; an explicit modern statement of his uniform bound is given in [22 Lemma 2.2]. Theorem 1.1 proves Erdős’s conjecture affirmatively. The lower bound is classical; the issue is the uniform upper bound.

A related line of work controls the denominators as well as the length. Tenenbaum and Yokota proved that, for each fixed ε>0\varepsilon> 0 and every sufficiently large bb, every a/b∈(0,1)a/b \in(0,1) has a distinct expansion of length at most (1+ε)log⁡b/log⁡log⁡b(1+\varepsilon)\log b/\log\log b, with all denominators at most 4b(log⁡b)2log⁡log⁡b4b(\log b)^2\log\log b [21 Theorem, p. 151]. Their length estimate serves this simultaneous constraint. Here we optimize only the order of the length and leave the denominator sizes unrestricted.

The uniform theorem also determines the double-logarithmic order of the number of representations of one. For each positive integer kk, put

F(k)=#{(n1,…,nk):1≤n1<⋯<nk,ni∈Z,1n1+⋯+1nk=1}.F(k)=\#\left\{(n_1,\ldots,n_k): 1\leq n_1<\cdots<n_k,\quad n_i\in\mathbb{Z},\quad\frac{1}{n_1}+\cdots+\frac{1}{n_k}=1\right\}.

Here too there is no upper bound on the denominators.

Corollary 1.2. There are absolute constants c,C>0c,C > 0 and k0k_0 such that, for every integer k≥k0k \geq k_0,

ck≤log⁡log⁡F(k)≤Ck.ck \leq\log\log F(k) \leq Ck.

Erdős and Graham asked for good estimates for this counting function [8 p. 32]. Konyagin stated a lower bound with double logarithm of order k/log⁡kk/\log k [14 Theorem 1]; Elsholtz obtained this lower order even when every denominator is congruent to 11 or −1-1 modulo a fixed squarefree integer P>1P>1: the bound holds for every sufficiently large kk, with kk required to be odd when PP is even, and its constant may depend on PP [4 Theorem 1.1]. Elsholtz and Planitzer proved an upper bound with double logarithm O(k)O(k), allowing repetitions as well [5 Corollary 3(2)]. Corollary 1.2 determines the double-logarithmic order for unrestricted distinct denominators.

We can also ask which exact denominators occur among these expansions. For each integer k≥1k\geq1, let DkD_k be the set of integers m≥2m\geq2 for which there are positive integers n1<⋯<nkn_1<\cdots<n_k satisfying

1=∑i=1k1ni,m∈{n1,…,nk}.1=\sum_{i=1}^{k}\frac{1}{n_i},\qquad m\in\{n_1,\ldots,n_k\}.

Set

v(k)=min⁡({2,3,…}∖Dk).v(k)=\min\left(\{2,3,\ldots\}\setminus D_k\right).

The elementary denominator bound proved below makes DkD_k finite, so this minimum exists. Each m∈Dkm \in D_k may use a different expansion; membership requires the exact denominator mm and exactly kk distinct terms.

Corollary 1.3. For every sufficiently large integer kk,

exp⁡(exp⁡(k/600))≤v(k)≤1+k2k−1.\exp(\exp(k/600)) \leq v(k) \leq1 + k^{2^{k-1}}.

More precisely,

log⁡2257≤lim inf⁡k→∞log⁡log⁡v(k)k≤lim sup⁡k→∞log⁡log⁡v(k)k≤log⁡2.\frac{\log2}{257} \leq\liminf_{k \to\infty} \frac{\log\log v(k)}{k} \leq\limsup_{k \to\infty} \frac{\log\log v(k)}{k} \leq\log2.

Equivalently for the lower bound, every fixed c<log⁡2/257c < \log2/257 satisfies v(k)≥exp⁡(exp⁡(ck))v(k) \geq\exp(\exp(ck)) for every sufficiently large integer kk. In particular log⁡log⁡v(k)=Θ(k)\log\log v(k) = \Theta(k).

The prescribed-denominator question originates in Erdős and Graham [8 p. 35]; see also Problem 293 [1]. Van Doorn and Tang prove the lower bound v(k)≥exp⁡(ck2)v(k) \geq\exp(ck^2) for an absolute c>0c > 0 [22 Theorem 1.1]. They also show that an exact prescribed denominator can be retained while increasing the length of a distinct expansion [22 Lemma 2.1] and anticipate the connection between uniform short expansions and a double-exponential lower bound for v(k)v(k) [22 Section 3]. We give the required marker-avoidance argument below, thereby deriving the qualitative order from Theorem 1.1. A direct construction additionally gives the numerical lower slope in Corollary 1.3, without quantifying the constant c2c_2 in the uniform theorem. The elementary upper bound is convenient rather than best known: sharper public upper bounds follow from the counting estimates of Elsholtz and Planitzer [5 Corollary 3(2)].

The two consequences impose different requirements on a construction. To obtain many expansions, it suffices to retain a denominator divisible by an integer with many prime factors. To include a prescribed integer mm in DkD_k, the exact term 1/m1/m must survive. The latter requirement governs both the initial construction and the operation that increases its length.

The proof in outline

Put S=log⁡bS = \log b. After O(log⁡S)O(\log S) greedy steps, either the expansion is complete or its remainder has the form A/CA/C, where A≤bA \leq b and CC lies in a prescribed exponential range in SS. We then construct an auxiliary integer MM with eS<M=exp⁡(O(S))e^S < M = \exp(O(S)) and a large interval of numerators in which almost every fraction u/(MC)u/(MC) has an expansion of length O(log⁡S)O(\log S). This dense family suffices for the original numerator: a suitable integer multiple gAMgAM lies well inside the interval, and it is the sum of two numerators from that dense family. Adding their expansions and dividing by gg represents A/CA/C.

The dense family is obtained by descending through O(log⁡S)O(\log S) numerator ranges. At a range whose upper endpoint exceeds eSe^S, we represent fractions u/(MC)u/(MC); at lower ranges we represent u/Mu/M, which is still less than one. Write Q=CQ = C or Q=1Q = 1 for the denominator factor in the current range. A divisor tt of MM gives the identity

uMQ=1(M/t)z+1zhMQ,z=⌈Qtu⌉,h=uz−Qt.\frac{u}{MQ} = \frac{1}{(M/t)z} + \frac{1}{z}\frac{h}{MQ}, \qquad z = \left\lceil\frac{Qt}{u} \right\rceil, \qquad h = uz - Qt.

Thus one unit fraction reduces the problem to the residue of −Qt-Qt modulo uu. When the denominator factor changes from CC to 11, an expansion over MM can be transferred back over MCMC by multiplying every denominator by CC. We choose MM so that, for most numerators at each range, many of its divisors give small residues. Deterministic products of distinct primes provide the large-range estimate; independent random products provide the small-range estimate. At the bottom, the same construction gives a reduction for every remaining numerator, followed by a binary expansion.

The difficulty is to prevent the exceptional numerators from accumulating as these reductions are joined. For fixed tt and hh, a predecessor uu must divide Qt+hQt+h. A uniform moment estimate for the number of small divisors in a shifted interval controls the total number of predecessors of a small exceptional set. Hölder’s inequality then gives a recurrence for the exceptional proportions that remains small throughout the descent. This combination of residue distribution, uniform divisor moments, and the final passage from a dense family to every numerator is the main mechanism of the proof.

The use of a common auxiliary denominator connects the proof to the classical divisor method. Erdős’s construction writes suitable integers as sums of distinct divisors of a factorial and turns those sums into unit fractions [6 Section 1, pp. 199–203]. Tenenbaum and Yokota obtain a shorter divisor decomposition by choosing successive divisors close to the remaining numerator [21 Lemma 4 and Section 3]. The present descent instead selects divisors through the residues they produce. Modular control by finite Fourier methods also occurs in Croot’s work [3] and Martin’s development of it [17 Section 4, Lemmas 11–13], where subset sums of modular inverses remove large prime-power denominator factors. Here prime-product distributions supply many possible reductions, and a uniform divisor moment keeps their exceptional sets under control across all levels. The moment proof uses the prime-factor splitting method of Erdős [7 Section 3]; the truncation and shift uniformity needed here are established below.

Section 2 isolates the dense-family statement and deduces Theorem 1.1 from it. Section 3 proves the divisor estimate, Section 4 constructs the residue distributions, and Section 5 completes the dense-family argument. The construction constants are fixed first, then a moment order large enough for the descent, and finally a sufficiently large lower bound on SS. Section 6 then deduces Corollary 1.2. Theorem 1.1 supplies a short expansion containing a denominator with many prime factors. Splitting that denominator over its divisors gives many distinct expansions, and an injective padding operation gives every sufficiently large prescribed length. Divisor-rich denominators and divisor-indexed splitting appear in Konyagin and Elsholtz [14, 4]; Konyagin explicitly records the padding injection [14], p. 312.

For the prescribed-denominator consequence, Section 7 reserves 1/m1/m and uses a greedy prefix that skips denominator mm. The remaining sum is smaller than every reserved reciprocal, so any positive expansion of that remainder avoids all reserved denominators. Applying Theorem 1.1 gives a short marked expansion, and a separate padding lemma retains the exact marker at every later length. For an explicit length constant, Section 8 instead constructs the tail from a common supply of rational numbers whose numerators divide one auxiliary integer. Prime-product residue collisions and the quantitative three-prime theorem provide this supply. A divisor-density property of the unreduced greedy denominator then groups the remaining numerator into few pieces. The resulting length coefficient 257/log⁡2257/\log2 gives the lower slope after padding and absorbing the finitely many small markers.

Throughout, N={1,2,…}\mathbb{N}=\{1,2,\ldots\}, log⁡\log is the natural logarithm, log⁡2x=(log⁡x)/(log⁡2)\log_2 x=(\log x)/(\log2), e(x)=exp⁡(2πix)e(x)=\exp(2\pi i x), and sums over real intervals have integer indices. The notations O(⋅)O(\cdot) and ≪\ll have absolute implied constants unless a dependence is indicated. Intermediate unit-fraction lists may contain repetitions. Lemma 2.2 removes them when the total is below one; Section 6 supplies the argument at total one.

From a dense set to every numerator

The main construction produces short expansions for most numerators over a carefully chosen denominator. We first state exactly what is needed from that construction, and then show why it suffices for every numerator.

Proposition 2.1 (A dense set of short expansions). There are absolute constants DM>1D_M > 1, L>0L > 0, and S0>1S_0 > 1 with the following property. Put DX=DM+2D_X = D_M + 2 and DC=4DXD_C = 4D_X. For every real S≥S0S \ge S_0 and every integer CC satisfying

eDCS≤C≤e2DCS.e^{D_C S} \le C \le e^{2D_C S}.

there are an integer MM and a set G⊆{1,…,⌊X⌋}G \subseteq\{1,\ldots,\lfloor X\rfloor\}, where X=eDXSX=e^{D_X S}, such that

eS<M≤eDMS,∣{1,…,⌊X⌋}∖G∣≤X8.e^S < M \le e^{D_M S}, \qquad\left|\{1,\ldots,\lfloor X\rfloor\}\setminus G\right| \le\frac{X}{8}.

For each u∈Gu \in G, the fraction u/(MC)u/(MC) is a sum of at most Llog⁡SL\log S unit fractions with integer denominators at least 2. Repetitions are allowed.

Section 5 proves Proposition 2.1. Its constants and threshold are independent of CC; the integer MM and the set GG may depend on CC. The proof of Theorem 1.1 from this proposition is elementary. We record first how to remove repetitions and how to prepare a denominator in the required range.

Lemma 2.2 (Removing repetitions). Let k≥1k \ge1 be an integer. If 0<x<10 < x < 1 is a sum of kk positive unit fractions with integer denominators, then it is a sum of kk such fractions with distinct denominators, all at least 2.

Proof. We use Takenouchi’s argument [20 Sections II–III, pp. 79–80]. For fixed x>0x > 0 and kk, there are only finitely many nondecreasing lists of kk denominators with reciprocal sum xx. Indeed, the first denominator is at most k/xk/x. Once it is chosen, induction applies to the remaining positive sum and the remaining k−1k-1 terms; when no terms remain the sum must be zero.

If a denominator occurs twice, apply one of the identities

References

  1. [1]Thomas F. Bloom. Erdős Problem 293. https://www.erdosproblems.com/293.
  2. [2]Thomas F. Bloom. Erdős Problem 304. https://www.erdosproblems.com/304. Accessed 21 September 2026.
  3. [3]Ernest S. Croot, III. On some questions of Erdős and Graham about Egyptian fractions. Mathematika, 46(2):359–372, 1999. Publisher version.
  4. [4]Christian Elsholtz. Egyptian fractions with odd denominators. The Quarterly Journal of Mathematics, 67(3):425–430, 2016. Publisher version.
  5. [5]Christian Elsholtz and Stefan Planitzer. Sums of four and more unit fractions and approximate parametrizations. Bulletin of the London Mathematical Society, 53(3):695–709, 2021. Publisher version.
  6. [6]Paul Erdős. Az 1/x₁ + 1/x₂ + ⋯ + 1/xₙ = a/b egyenlet egész számú megoldásairól. Matematikai Lapok, 1:192–210, 1950. Public text.
  7. [7]Paul Erdős. On the sum ∑ₖ₌₁ˣ d(f(k)). Journal of the London Mathematical Society, 27(1):7–15, 1952. Publisher version.
  8. [8]Paul Erdős and Ronald L. Graham. Old and New Problems and Results in Combinatorial Number Theory, volume 28 of Monographies de L’Enseignement Mathématique. L’Enseignement Mathématique, Geneva, 1980. Public text.
  9. [9]Paul Erdős and Pál Turán. On a problem in the theory of uniform distribution. I, II. Proceedings of the Koninklijke Nederlandse Akademie van Wetenschappen, 51:1146–1154, 1262–1269, 1948. Part I; Part II.
  10. [10]P. X. Gallagher. A larger sieve. Acta Arithmetica, 18(1):77–81, 1971. Publisher version.DOI
  11. [11]A. A. Glibichuk and S. V. Konyagin. Additive properties of product sets in fields of prime order. In Additive Combinatorics, volume 43 of CRM Proceedings and Lecture Notes, pages 279–286. American Mathematical Society, 2007. Author version.
  12. [12]S. W. Graham and G. Kolesnik. Van der Corput’s Method of Exponential Sums, volume 126 of London Mathematical Society Lecture Note Series. Cambridge University Press, Cambridge, 1991. Publisher version.DOI
  13. [13]Adolf Hildebrand and Gérald Tenenbaum. Integers without large prime factors. Journal de Théorie des Nombres de Bordeaux, 5(2):411–484, 1993. Public text.DOI
  14. [14]S. V. Konyagin. Double exponential lower bound for the number of representations of unity by Egyptian fractions. Matematicheskie Zametki, 95(2):312–316, 2014. In Russian; Publisher version.
  15. [15]Angel Kumchev. On the Piatetski-Shapiro-Vinogradov theorem. Journal de Théorie des Nombres de Bordeaux, 9(1):11–23, 1997. Publisher version.DOI
  16. [16]Angel V. Kumchev and Dimitar I. Tolev. An invitation to additive prime number theory. Serdica Mathematical Journal, 31:1–74, 2005. Author version.
  17. [17]Greg Martin. Denser Egyptian fractions. Acta Arithmetica, 95(3):231–260, 2000. Author version.
  18. [18]Masayosi Nakayama. On the decomposition of a rational number into “Stammbrüche”. Tohoku Mathematical Journal, First Series, 46:1–21, 1940. Public text.
  19. [19]Atle Selberg. An elementary proof of the prime-number theorem. Annals of Mathematics. Second Series, 50(2):305–313, 1949. Publisher version.DOI
  20. [20]Tanzō Takenouchi. On an indeterminate equation. Proceedings of the Physico-Mathematical Society of Japan, Third Series, 3(6):78–92, 1921. Publisher version.DOI
  21. [21]Gérald Tenenbaum and Hisashi Yokota. Length and denominators of Egyptian fractions, III. Journal of Number Theory, 35(2):150–156, 1990. Publisher version.DOI
  22. [22]Wouter van Doorn and Quanyu Tang. The smallest denominator not contained in a unit fraction decomposition of 1 with fixed length. Mathematical Proceedings of the Cambridge Philosophical Society, pages 1–9, 2026. Published online 8 July 2026; arXiv:2512.22083v2; Publisher version.DOI
  23. [23]Michael D. Vose. Egyptian fractions. Bulletin of the London Mathematical Society, 17(1):21–24, 1985. Publisher version.DOI

Paper details

vlnc:W_83ugjxhd
Version
v1 · latest
Published
License
LicenseRef-OpenAI-public
Usage

views · 33

downloads · 1

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

unreleased internal OpenAI model

View statement
Looking for related papers…
Contents