Largest subset of {1,…,N} with no 1/a = 1/b + 1/c: estimate f(N) (Erdős #302)
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}+\frac{1}{c}$$ with $a,b,c$ distinct elements of $A$. Estimate $f(N)$. In particular, is $f(N)=(\tfrac{1}{2}+o(1))N$?
Acceptance. FULLY RESOLVES: a complete proof determining $\lim f(N)/N$ (or a proof that no such limit exists); machine-checkable (Lean/Coq) preferred, else a full written proof. ADVANCES (each independently checkable): (a) improve the upper bound strictly below the best stated in the background, $(9/10+o(1))N$, with proof or a reproducible extremal argument; (b) improve the lower bound strictly above $(5/8+o(1))N$ by an explicit solution-free family plus a verification that it is solution-free; (c) extend the exact values $f(N)$ (A390395) to a new record $N$ with the search code and an optimality certificate. Deliver the proof, or the construction + verification, or the code + attained values.
Background
Posed by Erdős and Graham [ErGr80]; listed as open on erdosproblems.com/302 (fetched 2026-07-21, status 'open'). This is the three-variable case of #301 (erdosproblems.com/301); the associated colouring problem #303 (erdosproblems.com/303) was resolved by Brown and Rödl [BrRo91]. Lower bound $f(N)\ge(1/2+o(1))N$ from taking all odd integers in $[1,N]$ — an equation $1/a=1/b+1/c$ with $a,b,c$ all odd is impossible, since $bc=a(b+c)$ has odd left side and even right side — or all of $[N/2,N]$. Stijn Cambie improved this to $f(N)\ge(5/8+o(1))N$ by taking the odd integers up to $N/4$ together with all of $[N/2,N]$; note this already refutes the guess $f(N)=(1/2+o(1))N$, so the open task is to pin the true constant. Wouter van Doorn proved the upper bound $f(N)\le(9/10+o(1))N$. Cambie further observed that if $b=c$ is permitted, a solution appears once $\lvert A\rvert\ge(2/3+o(1))N$ (there must then exist $n,2n\in A$). OEIS A390395 tabulates $f(N)$. The site's forum records one claimed proof that has not been incorporated into the remarks; treat it as unverified. Attacker's tool: exact computation of $f(N)$ for small $N$ via integer programming / exhaustive search (extending A390395), plus sharper constructions and covering arguments to narrow the constant within $[5/8,\,9/10]$.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #302 (T. F. Bloom) | website |
| REF-02 | OEIS A390395 — f(N) for Erdős problem #302 | website |
| REF-03 | W. van Doorn, note deriving f(N) ≤ (9/10+o(1))N | paper |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.