Erdoes #304 - working report - Erdős Problem a Day

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

> that there exist integers \(1

> \[ > \frac{a}{b}=\frac{1}{n_1}+\cdots+\frac{1}{n_k}. > \]

> Estimate \(N(b)=\max_{1\leq a

> \(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

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*](https://www.renyi.hu/~p_erdos/1950-02.pdf),

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.

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

[*Old and New Problems and Results in Combinatorial Number

Theory*](https://mathweb.ucsd.edu/~ronspubs/80_11_number_theory.pdf),

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!\).

3. (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.

4. (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.

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

[*The smallest denominator not contained in a unit fraction decomposition

of 1 with fixed length*](https://arxiv.org/abs/2512.22083),

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

\[ \boxed{N(b)\leq 7\quad(2\leq b\leq1000),} \]

with equality exactly for

\[ \boxed{b\in\{733,739,787,839,863,898,907\}.} \]

The complete extremizer lists are:

| \(b\) | all \(a\) for which \(N(a,b)=N(b)=7\) |

|---:|:---|

| 733 | 732 |

| 739 | 728 |

| 787 | 786 |

| 839 | 827, 831, 834 |

| 863 | 859, 860 |

| 898 | 897 |

| 907 | 901, 906 |

Every lower bound in this table is an exhaustive rejection of lengths

1 through 6. Every upper bound has a separately checked exact certificate:

| fraction | increasing seven-term denominator tuple |

|:---|:---|

| \(732/733\) | \((2,3,7,45,4484,33397845,2305193137933140)\) |

| \(728/739\) | \((2,3,7,113,13336,632071254,2463670098522245928)\) |

| \(786/787\) | \((2,3,7,45,3159,10237019,137041642540530)\) |

| \(827/839\) | \((2,3,7,106,13733,346593826,143377721207882826)\) |

| \(831/839\) | \((2,3,7,71,5268,32786068,643036208984841)\) |

| \(834/839\) | \((2,3,7,57,3266,273332357,149421154493018541)\) |

| \(859/863\) | \((2,3,7,53,3262,22380093,1669561853248737)\) |

| \(860/863\) | \((2,3,7,50,3001,17890501,24325321960465575)\) |

| \(897/898\) | \((2,3,7,45,2111,149284643,44571809121990255)\) |

| \(901/907\) | \((2,3,7,59,4080,17172288,11158565008320)\) |

| \(906/907\) | \((2,3,7,45,2063,28751679,3765891177701730)\) |

The first occurrence of each new running maximum is:

| first \(b\) | new \(\max_{2\leq d\leq b}N(d)\) | extremizing \(a\) at that \(b\) |

|---:|---:|:---|

| 2 | 1 | 1 |

| 3 | 2 | 2 |

| 5 | 3 | 4 |

| 11 | 4 | 8, 9, 10 |

| 17 | 5 | 16 |

| 79 | 6 | 77 |

| 733 | 7 | 732 |

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

\[ \#\{N(b)=1,2,3,4,5,6,7\}=(1,3,10,37,326,615,7). \]

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

\[ N(b)=\max_{q\mid b}\max\{j:c_j(q)>0\}. \]

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

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

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

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

3. (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\),

\[ \frac ab=\frac1x+\frac1y \quad\Longleftrightarrow\quad (ax-b)(ay-b)=b^2. \]

For \(x

with \(d \[ x=\frac{d+b}{a},\qquad y=\frac{b^2/d+b}{a}. \]

The verifier factors \(b\), generates every divisor \(d

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

\[ L(M)=\max_{0\leq twith \(L(M)=\infty\) if some \(t\) has no such representation.

Common-denominator lemma

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

\[ N(a,b)\leq 2L(M)\qquad(1\leq aIndeed, write

\[ aM=bq+r,\qquad 0\leq rand choose distinct-divisor representations

\(q=\sum d_i\), \(r=\sum e_j\), each of length at most \(L(M)\). Then

\[ \frac ab =\frac qM+\frac r{bM} =\sum_i\frac1{M/d_i}+\sum_j\frac1{bM/e_j}. \]

Because \(q

Because each \(e_j\leq r

\(M\). Thus the two groups are disjoint and each is internally distinct.

Consequently, (a) the conjecture would follow from a sequence

\(M_1 \[ L(M_j)\ll\log\log M_j \quad\text{and}\quad \log\log M_j\ll\log\log M_{j-1}, \]

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

different sums require \(M\) different divisor subsets. Encoding a subset

of size at most \(L(M)\) by \(L(M)\) divisor-or-blank choices gives

\[ \boxed{M\leq(\tau(M)+1)^{L(M)}},\qquad L(M)\geq\frac{\log M}{\log(\tau(M)+1)}. \]

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.

2. (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

\(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

\(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,

\[ N(b-1,b)=7 \quad\Longleftrightarrow\quad b\in\{733,787,898,907\}, \]

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.