Largest subset of $\{1,\ldots,N\}$ with no two elements whose sum divides their product (Erdős #327)
Statement
Call a set $A\subseteq\{1,\ldots,N\}$ product-avoiding if for every pair of distinct $a,b\in A$ one has $a+b\nmid ab$ (the sum never divides the product). The odd numbers are product-avoiding — if $a,b$ are both odd then $a+b$ is even while $ab$ is odd, so $a+b\nmid ab$ — giving density $1/2$. Can a product-avoiding set be 'substantially more' than the odd numbers, i.e. can $\lvert A\rvert$ exceed $(1/2+c)N$ for some fixed $c>0$, or even reach $(1-o(1))N$? In the relaxed variant where the requirement is instead $a+b\nmid 2ab$ for all distinct $a,b\in A$, must every such set satisfy $\lvert A\rvert=o(N)$?
Acceptance. FULLY RESOLVES: determine, with proof, the supremum of $\lvert A\rvert/N$ over product-avoiding $A$ as $N\to\infty$ — e.g. prove no product-avoiding set has density above $1/2+o(1)$ (answering 'no, not substantially more'), or exhibit a construction of density $\geq 1/2+c$ with proof; and for the second variant, prove $\lvert A\rvert=o(N)$ (with $a+b\nmid 2ab$) or exhibit a positive-density example. ADVANCES: (a) improve van Doorn's upper bound of $(25/28+o(1))N$ (the bound stated in background) to a strictly smaller constant with proof; (b) construct, for infinitely many $N$, a product-avoiding set of density strictly above $1/2$, beating the odd numbers, with a verifiable construction; or (c) compute the exact maximum-size product-avoiding subset of $\{1,\ldots,N\}$ for a new range of $N$ via a reproducible search with an optimality certificate. Deliver the proof / construction or the search code plus certified optima.
Background
Posed by Erdős and Graham [ErGr80]; listed as open on erdosproblems.com/327 (fetched 2026-07-21, status 'open'), no cash prize. The link to unit fractions is that $\tfrac1a+\tfrac1b$ is itself a unit fraction exactly when $a+b\mid ab$, so a product-avoiding set is one in which no two reciprocals sum to a unit fraction. The best known upper bound on the density is due to Wouter van Doorn, whose elementary argument shows that any $A\subseteq\{1,\ldots,N\}$ with $\lvert A\rvert\geq(25/28+o(1))N$ must contain distinct $a,b$ with $a+b\mid ab$ (discussed on erdosproblems.com/301); thus the extremal density lies between $1/2$ (the odd numbers) and $25/28\approx 0.893$, and it is not even known whether one can beat $1/2$. See also erdosproblems.com/302 and OEIS A384927. Attacker's tool: ILP / exhaustive search for the densest product-avoiding subset of $\{1,\ldots,N\}$ at small $N$ to test whether the density can exceed $1/2$, together with structural or sieve arguments to push van Doorn's $25/28$ bound down.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #327 (T. F. Bloom) | website |
| REF-02 | OEIS A384927 (related to Erdős #327) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.