Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Claim. Let n(N)n(N) be the largest integer such that every integer 1≤n≤n(N)1\le n\le n(N) is a sum of distinct unit fractions with denominators at most NN, and HN=∑n≤N1/nH_N=\sum_{n\le N}1/n. Then, for all large NN,

⌊HN−92(1+o(1))(log⁡log⁡N)2log⁡N⌋≤n(N)≤⌊HN−12(1+o(1))(log⁡log⁡N)2log⁡N⌋.\Bigl\lfloor H_N-\tfrac92(1+o(1))\tfrac{(\log\log N)^2}{\log N}\Bigr\rfloor \le n(N)\le \Bigl\lfloor H_N-\tfrac12(1+o(1))\tfrac{(\log\log N)^2}{\log N}\Bigr\rfloor.

This is the Main Theorem of Croot's paper, on the library's result page. In the notation of Problem 308, with N(N)N(N) the set of representable positive integers, f(N)f(N) the smallest positive integer not in it and mN=⌊HN⌋m_N=\lfloor H_N\rfloor: every element of N(N)N(N) is at most HNH_N, so N(N)⊆{1,…,mN}N(N)\subseteq\{1,\ldots,m_N\}; the lower floor gives {1,…,mN−1}⊆N(N)\{1,\ldots,m_N-1\}\subseteq N(N) for large NN; and writing HN=mN+δNH_N=m_N+\delta_N, the theorem puts mNm_N in N(N)N(N) when δN>(92+o(1))(log⁡log⁡N)2/log⁡N\delta_N>(\frac92+o(1))(\log\log N)^2/\log N and outside it when δN<(12+o(1))(log⁡log⁡N)2/log⁡N\delta_N<(\frac12+o(1))(\log\log N)^2/\log N (the paper's p. 2, on the conjecture page). Hence for all large NN the set N(N)N(N) is {1,…,mN−1}\{1,\ldots,m_N-1\} or {1,…,mN}\{1,\ldots,m_N\} and f(N)=n(N)+1∈{mN,mN+1}f(N)=n(N)+1\in\{m_N,m_N+1\}.

Covers. Both questions of the problem's corrected Statement, for all sufficiently large NN: the smallest missing integer f(N)f(N) is mNm_N or mN+1m_N+1, and the representable integers form an initial segment {1,…,m}\{1,\ldots,m\}, with m∈{mN−1,mN}m\in\{m_N-1,m_N\}. The case is decided by the fractional part δN\delta_N of HNH_N whenever δN\delta_N lies outside the window between (12+o(1))(log⁡log⁡N)2/log⁡N(\frac12+o(1))(\log\log N)^2/\log N and (92+o(1))(log⁡log⁡N)2/log⁡N(\frac92+o(1))(\log\log N)^2/\log N. Not covered: the exact value of f(N)f(N) inside that window, which Croot's conjecture that the upper floor is the truth would decide, and the initial-segment property for NN below the theorem's range; the problem page records both as the problem's variants.

Depends on. Yokota's 1997 theorem supplies, in the proof of the lower bound, the representability of the integers below a fixed bound (the paper's references [5] and [6]).

Route. Lower bound: starting from the full harmonic sum, remove as few terms as possible to leave an integer, prime power by prime power from the top, with the removed reciprocal mass controlled by a quantity built from prime powers (Propositions 1 and 3); every integer between the value so reached for a fixed N0N_0 and the value for NN is reached at some intermediate denominator bound, and the integers below the fixed value are representable by Yokota's 1997 theorem (the library's Theorem 1, recorded at statement depth; its 1998 Corrigendum is not held). Upper bound: a pp-adic argument shows that no denominator in an integer reciprocal sum has a prime factor above Nlog⁡log⁡N/log⁡NN\log\log N/\log N, and the reciprocal mass of the integers with such a factor exceeds 12(1+o(1))(log⁡log⁡N)2/log⁡N\frac12(1+o(1))(\log\log N)^2/\log N.

Acceptance. Refereed: Croot, III, Ernest S., On some questions of Erdős and Graham about Egyptian fractions, Mathematika 46 (1999), no. 2, 359--372. The publisher's record dates the issue December 1999 and gives no day; the day in this page's name is the first of that month. Reviewed: the site's curator, Thomas Bloom, marks Problem 308 proved and credits Croot's theorem as essentially solving it in the problem's commentary; the site's displays attach the two floors to f(N)f(N) where the theorem bounds n(N)=f(N)−1n(N)=f(N)-1, as the problem page records. The locators are pages of the author's fourteen-page typescript, posted on the author's papers page (the second link); the journal text has not been compared, the proof is recorded in outline only, and no independent review of it is recorded in this corpus.

Formalization. The file src/latest/ErdosProblems/Erdos308.lean in Boris Alexeev's lean-proofs collection at the pinned commit (the third link) declares itself a Lean formalization of a solution to Problem 308, with Croot and Yokota as informal authors and Codex, GPT-5.6 Sol (OpenAI Codex) as formal authors. Its theorem erdos_308 states that for all large NN the represented positive integers are exactly {1,…,mN−1}\{1,\ldots,m_N-1\} with first missing integer mNm_N, or exactly {1,…,mN}\{1,\ldots,m_N\} with first missing integer mN+1m_N+1; its eventually_represented_shape is the two-set alternative and its eventually_interval_coverage the lower floor's consequence that every positive integer up to mN−1m_N-1 is representable. These are the statements of the Covers paragraph, the two questions of the problem's corrected Statement; the final theorem does not decide between the two cases, and the two floors appear in the file as definitions (CrootIntervalStatement, CrootCardinalityBounds) rather than as its theorem, the proof resting on a companion module's construction that the top file calls Croot's. The corpus did not build the file, and only its top file is recorded, so no formalized evidence is listed; the formal-conjectures statement file for the problem points at this file.