Erdős problem 304 — live audit, exact finite certificate, and the method barrier

Access date: 2026-07-26 (UTC).

Claim labels used throughout:

• (a) elementary-rigorous: a complete argument is supplied here.
• (b) rigorous-modulo-named-theorem: the stated published theorem is used.
• (c) plausible/structural-unverified: a heuristic or a literature-search

miss, not a theorem.

• (d) computational-only: established by the accompanying exact program,

but not asserted beyond its finite range.

0. Mandatory live-page gate

I fetched the live page and its discussion thread through the Bright Data browser path, not datacenter curl.

The live page says OPEN, 0 claimed proofs, and Currently working on this problem: None. It lists Woett and Quanyu_Tang under both “Likes this problem” and “Interested in collaborating”; those are not current-worker markers. “This problem looks difficult,” “This problem looks tractable,” “The results on this problem could be formalisable,” and “I am working on formalising the results” all say None. The external-data box says the statement has been formalised, and the page says it was last edited 2025-12-29. Thus no requested stop condition is present.

Verbatim live statement

For integers \(1\leq a<b\) let \(N(a,b)\) denote the minimal \(k\) such that there exist integers \(1<n_1<\cdots<n_k\) with \[ > \frac{a}{b}=\frac{1}{n_1}+\cdots+\frac{1}{n_k}. > \] Estimate \(N(b)=\max_{1\leq a<b}N(a,b)\). Is it true that \(N(b)\ll\log\log b\)?

Everything else currently listed on the page

• (b) The page attributes

\[ \log\log b\ll N(b)\ll\frac{\log b}{\log\log b} \] to Erdős [Er50c], and the improved upper bound \(N(b)\ll\sqrt{\log b}\) to Vose [Vo85].

• (b) It also records

\[ \frac1b\sum_{1\leq a<b}N(a,b)\gg\log\log b, \] says the problem is related to problem 18, and notes the particularly close connection between \(N(b-1,b)\) and problem 293 explained by van Doorn and Tang [vDTa25b].

• It links OEIS A097847 and A097849 and says the statement is formalised in

Lean as part of Google DeepMind's Formal Conjectures project.

• There is exactly one comment. Alfaiz, 2026-02-06, writes:

“This paper by H. Yokota ([Yo92]) seems related.” The link is to Yokota's On a Sum of Divisors. The site warns that comments are unverified; this comment is therefore not itself used as evidence.

1. Primary-source literature audit

1. (b) Erdős's original 1950 paper,

Az \(1/x_1+\cdots+1/x_n=A/B\) egyenlet egész számú megoldásairól, exists as the 19-page Mat. Lapok paper at pages 192--210. Its Theorem 1 states the \(\log b/\log\log b\) upper bound. Its Theorem 2 gives the stronger explicit lower statements \(N(b-1,b)>\log\log b-1\) and an average lower bound of that order. The English summary at the end also states the conjectural \(O(\log\log b)\) upper bound.

1. (b) The cited 1980 Erdős--Graham monograph,

Old and New Problems and Results in Combinatorial Number Theory, contains this problem on printed page 37. It gives the same definition and bounds and says that even an \(o(\log b/\log\log b)\) bound would be interesting. It explicitly derives the old upper bound from the lemma that every integer below \(n!\) is a sum of fewer than \(n\) distinct divisors of \(n!\).

1. (b) Vose's article

Egyptian Fractions is Bulletin of the London Mathematical Society 17 (1985), 21--24, DOI 10.1112/blms/17.1.21. The journal landing page verifies the bibliographic data. More importantly for its mathematical content, the primary 2026 paper below restates the needed Vose lemma: every \(a/b\in(0,1)\) has such a decomposition with at most \(C\sqrt{\log b}\) terms.

1. (b) The comment's paper is real:

H. Yokota, On a Sum of Divisors, Canadian Mathematical Bulletin 35 (1992), 423--430. Yokota defines \(l(M,r)\) as the minimum number of distinct divisors of \(M\) summing to \(r\), and \(l(M)\) as the worst case. His corollary proves \[ l(M_k)\asymp\sqrt{\log M_k} \] for Vose's particular sequence \(M_k\). Thus the paper is relevant, but it does not improve the uniform Egyptian-fraction bound; it proves that the divisor-subset step on Vose's sequence is already of the displayed order.

1. (b) W. van Doorn and Q. Tang,

The smallest denominator not contained in a unit fraction decomposition of 1 with fixed length, is arXiv 2512.22083v2, revised 2026-05-24 and published online in 2026. Theorem 1.1 proves \(v(k)\geq\exp(c k^2)\). Its concluding remarks explicitly identify Vose's \(N(b)\ll\sqrt{\log b}\) as the current best uniform bound, state the \(O(\log\log b)\) conjecture, and prove that a lower bound for \(v(k)\) gives an upper bound for \(N(b-1,b)\).

The searches included the exact problem notation, title/author searches, and 2025--2026 Egyptian-fraction papers. (c) I found no primary source claiming a better uniform upper bound or a solution. This is a search miss, not a proof that no unindexed source exists.

2. Exact finite result

Sharp result through denominator 1000

(d) The standalone verifier exhausts all 304,191 reduced fractions with denominator at most 1000 and proves

with equality exactly for

The complete extremizer lists are:

Every lower bound in this table is an exhaustive rejection of lengths 1 through 6. Every upper bound has a separately checked exact certificate:

The first occurrence of each new running maximum is:

For a compact exact extension of the OEIS A097849 table, here are all values from 106 through 200. Each row labels consecutive \(b\)'s:

106--115: 5 6 5 6 5 5 5 6 5 5
116--125: 5 5 6 5 4 5 5 5 5 5
126--135: 4 6 5 5 5 6 5 5 6 5
136--145: 5 6 5 6 4 5 5 5 5 5
146--155: 5 5 5 6 5 6 5 5 5 5
156--165: 5 6 6 5 5 5 5 6 5 5
166--175: 6 6 4 5 5 5 5 6 5 5
176--185: 5 5 5 6 4 5 5 5 5 5
186--195: 5 5 5 5 5 6 5 6 6 5
196--200: 5 6 5 6 5

Over \(2\leq b\leq1000\), the counts of denominators having each value are

Independent data cross-check and honesty about novelty

Hugo van der Sanden's public least_eg/results file contains, for each reduced denominator through 27539, a vector counting fractions of each minimum length. It is an independent computation and is not treated as a theorem.

Let \(c_j(q)\) count reduced \(a/q\) with minimum length \(j\). (a) Reduction of fractions gives

The verifier's complete vectors \(c_j(q)\) for \(2\leq q\leq1000\) match van der Sanden's prefix exactly. In the canonical serialization q:c1,c2,...\n, both give SHA-256

aa8a2c6b3278cc4765e499c041dac7b869aa22140ccae0afeb9a19f957e2e939.

The downloaded public results file itself had SHA-256

09b3055b6f4315d6f2f0887df05129614074288a4acfc35282353bca744c157a

on the access date. The OEIS A097849 displayed table stops at \(b=105\); the longer public count file means the finite values above are not claimed as novel. The contribution of this run is a short, from-scratch exact reconstruction with explicit witnesses, a proof of its rejection bounds, and an independent full-prefix match.

3. Why the finite search is exhaustive

Reduction to reduced denominators

(a) If \(a/b=c/q\) in lowest terms, then \(q\mid b\) and \(N(a,b)=N(c,q)\). Conversely, every reduced \(c/q\) with \(q\mid b\) appears among the fractions with displayed denominator \(b\). This proves the divisor aggregation formula above and avoids recomputing duplicates.

The recursion bounds

Suppose the remaining target is \(a/b>0\) in lowest terms, the previous chosen denominator is \(p\), and \(t>2\) terms remain. If the next denominator is \(x\), then:

1. (a) Positivity of the nonempty tail gives \(1/x<a/b\), hence

\[ x\geq\max\!\left(p+1,\left\lfloor b/a\right\rfloor+1\right). \]

1. (a) All \(t\) remaining unit fractions are at most \(1/x\), hence

\[ a/b\leq t/x,\qquad x\leq\lfloor tb/a\rfloor. \]

1. (a) After choosing \(x\), the largest possible distinct increasing

tail uses \(x+1,\ldots,x+t-1\). Therefore a branch is impossible if \[ \frac ab-\frac1x> \sum_{i=1}^{t-1}\frac1{x+i}. \]

The program tries every integer in the resulting finite interval, performs the subtraction and gcd reduction with integers, and applies only the necessary pruning in item 3.

Exact two-term leaves

(a) For reduced \(a/b\),

For \(x<y\), put \(d=ax-b\). Then \(d\) is a positive divisor of \(b^2\) with \(d<b\), and

The verifier factors \(b\), generates every divisor \(d<b\) of \(b^2\), checks both congruences and the ordering, and therefore neither misses nor invents a two-term completion. A one-term leaf is possible exactly when the remaining reduced numerator is 1 and its denominator exceeds \(p\). Induction on \(t\) proves completeness of the whole search.

The Fibonacci--Sylvester greedy expansion supplies a finite upper bound. Every returned tuple is then checked independently using fractions.Fraction, including strict order, denominators \(>1\), and exact sum. For each fraction the search rejects every smaller length before accepting its witness.

As a separate implementation check, the script compares the factorized two-term solver with a direct denominator loop for every reduced target through denominator 80 and five different previous-denominator bounds. An unrelated subset dynamic program also reconstructs divisor bases for 13 small practical numbers and checks the common-denominator construction below for every eligible \(a/b\). Both checks run before the main search.

The deterministic full-table serialization has SHA-256

f3bdbfd7c0547098e3821a5907486efb1ac8c5291161ff8099e53d2201caa0f1,

and the stream of all reduced targets, minimum lengths, and first witnesses has SHA-256

b5e07954dc79190e63f85c585938f3e201cb1411c3d01afe923294744d6bb97c.

Reproduction:

python3 runs/erdos304_wave5s_verify.py

Use --full-table to print all 999 values and every extremizer list. The final run used one core for 38 seconds, peaked at about 289 MB RSS, and ended with ALL CHECKS PASSED.

4. A clean sufficient reduction—and why the standard instances stall

For a positive integer \(M\), let \(\lambda_M(t)\) be the fewest distinct divisors of \(M\) whose sum is \(t\), and put

with \(L(M)=\infty\) if some \(t\) has no such representation.

Common-denominator lemma

(a) If \(b\leq M\) and \(L(M)<\infty\), then

Indeed, write

and choose distinct-divisor representations \(q=\sum d_i\), \(r=\sum e_j\), each of length at most \(L(M)\). Then

Because \(q<M\), every first-group denominator is between 2 and \(M\). Because each \(e_j\leq r<b\), every second-group denominator is greater than \(M\). Thus the two groups are disjoint and each is internally distinct.

Consequently, (a) the conjecture would follow from a sequence \(M_1<M_2<\cdots\) satisfying

because one chooses the first \(M_j\geq b\). This is an exact sufficient lemma, not a claimed known construction.

The information-theoretic obstruction

Let \(\tau(M)\) be the number of divisors of \(M\). (a) If all \(0\leq t<M\) have supports of size at most \(L(M)\), then the \(M\) different sums require \(M\) different divisor subsets. Encoding a subset of size at most \(L(M)\) by \(L(M)\) divisor-or-blank choices gives

Thus any successful common-denominator sequence must be extremely divisor-rich as well as having uniformly efficient subset sums.

There are two precise failures of the standard choices.

1. (b) For \(M=n!\), the Chebyshev prime-counting bound gives

\(\log\tau(n!)=O(n/\log n)\), while elementary factorial estimates give \(\log(n!)=\Theta(n\log n)\). The boxed inequality therefore forces \[ L(n!)=\Omega((\log n)^2). \] But choosing the least \(n\) with \(b\leq n!\) gives \(\log\log b=\Theta(\log n)\). Hence the original one-\(n!\) divisor-subset route cannot deliver \(O(\log\log b)\); it is short by at least a factor of order \(\log n\) at its own worst cases.

1. (b) Vose replaces \(n!\) by a much more carefully chosen sequence,

but Yokota's 1992 corollary proves \(L(M_j)\asymp\sqrt{\log M_j}\) for that very sequence. Therefore merely optimizing the subset selection inside Vose's existing common denominators cannot improve its order.

This isolates the missing input: either construct a dense-enough sequence of very divisor-rich \(M_j\) for which every \(t<M_j\) has an \(O(\log\log M_j)\)-term divisor support, or introduce a genuinely multi-scale/adaptive expansion that is not captured by one common \(M\). The first alternative is a concrete lemma; the second is only a structural direction (c).

5. What the connection to problem 293 does and does not cover

(b) Van Doorn--Tang prove that \(b<v(k)\) implies \(N(b-1,b)\leq k-1\): take a \(k\)-term decomposition of 1 containing \(1/b\), then remove that term. Their \(v(k)\geq\exp(c k^2)\) therefore recovers only a \(O(\sqrt{\log b})\) bound for this special fraction. A double-exponential lower bound \(v(k)\geq\exp(\exp(c k))\) would be needed to obtain \(O(\log\log b)\) by this direction.

(d) The exact computation also shows that the special fraction is not always the maximizer. Up to 1000,

whereas \(N(b)=7\) at the seven denominators listed earlier. In particular, the hard cases at \(b=739,839,863\) come from other numerators. Over the 999 tested denominators, \(N(b)=N(b-1,b)\) in 840 cases and exceeds it by exactly 1 in 159 cases. Thus even a complete resolution of the special family would not by itself supply the missing uniformity in \(a\).

6. Remaining wall and compute cost

The finite computation does not imply any asymptotic bound. The precise analytic wall is the absent short-support lemma above (or a replacement for the common-denominator framework), not another thousand small cases.

The public computational data continue to 27539, but independently rerunning that whole range with this transparent Python verifier would exceed the allowed budget. Scaling the measured 6.2 seconds at 500 and 38 seconds at 1000 gives a crude 70--150 single-core-hour estimate at 27539, with the length-8 boundary and cache memory likely making it worse. I did not run that computation. More importantly, no finite extension can establish the uniform \(b\to\infty\) statement.

PARTIAL: exact exhaustive search proves N(b) <= 7 for b <= 1000, with equality exactly at 733, 739, 787, 839, 863, 898, and 907; the uniform O(log log b) question remains open, and the precise common-denominator bottleneck is isolated.