Largest subset of {1,…,N} with no 1/a equal to a sum of distinct 1/b_i: estimate f(N) (Erdős #301)
Statement
Let $f(N)$ denote the size of the largest set $A\subseteq\{1,\ldots,N\}$ that contains no solution to $$\frac{1}{a}=\frac{1}{b_1}+\cdots+\frac{1}{b_k}$$ with $a,b_1,\ldots,b_k$ distinct elements of $A$ (and $k\ge 1$ arbitrary). Estimate $f(N)$. In particular, is it true that $f(N)=(\tfrac{1}{2}+o(1))N$?
Acceptance. FULLY RESOLVES: a complete proof (machine-checkable in Lean/Coq preferred, else a full written proof) determining the asymptotics of $f(N)$ — either establishing $f(N)=(\tfrac12+o(1))N$, or determining the correct leading constant $\lim f(N)/N$, or proving that no such limit exists. ADVANCES (each independently checkable): (a) improve the upper bound strictly below the best stated in the background, $(25/28+o(1))N$, via a proof or a reproducible extremal-set argument; (b) improve the lower bound strictly above $(1/2+o(1))N$ by exhibiting an explicit family of solution-free sets of density exceeding $1/2$ together with a verification that they are solution-free; (c) extend the sequence of exact values $f(N)$ (A390394) to a new record $N$ with the search program and a certificate of optimality. Deliver the proof, or the construction + verification, or the search code + attained values.
Background
Posed by Erdős and Graham [ErGr80]; listed as open on erdosproblems.com/301 (fetched 2026-07-21, status 'open'). Lower bound: taking $A=(N/2,N]\cap\mathbb{N}$ is solution-free, since each reciprocal there lies in $[1/N,2/N)$ so no two or more of them can sum to a third; this gives $f(N)\ge N/2$. Upper bound: Wouter van Doorn gave an elementary argument proving $f(N)\le(25/28+o(1))N$, using the disjoint sets $S_a=\{2a,3a,4a,6a,12a\}\cap[1,N]$ over $a$ of the form $8^b 9^c d$ with $\gcd(d,6)=1$: a solution-free $A$ must omit at least two elements of each $S_a$ with $a\le N/12$ and at least one with $N/12<a\le N/6$, and an elementary count concludes. Stijn Cambie and van Doorn also noted that if the $b_i$ are allowed to repeat, the maximal set has size at most $N/2$ (the classical divisibility threshold forcing some $a\mid b$). This is the multi-term generalisation of the three-variable problem #302 (erdosproblems.com/302); see also #327 (erdosproblems.com/327). OEIS A390394 tabulates $f(N)$. Attacker's tool: exact computation of $f(N)$ for small $N$ by integer programming / exhaustive search over subsets (extending A390394), plus structured constructions and a sharpened disjoint-block argument to squeeze the constant between $1/2$ and $25/28$.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #301 (T. F. Bloom) | website |
| REF-02 | OEIS A390394 — f(N) for Erdős problem #301 | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.