Best-possible upper bound for $\sum_{n\in A}1/n$ under an at-most-$r$ prime-representation cap (Erdős #538)
Statement
Let $r\geq 2$ and $N\geq 1$. Suppose $A\subseteq\{1,\ldots,N\}$ has the property that for every integer $m$ there are at most $r$ solutions to $m=pa$ with $p$ prime and $a\in A$ — that is, each integer $m$ is a prime multiple of an element of $A$ in at most $r$ ways. Determine the best-possible upper bound, as a function of $r$ and $N$, for $$\sum_{n\in A}\frac{1}{n}.$$
Acceptance. FULLY RESOLVES: determine the best-possible order of $\max_A\sum_{n\in A}1/n$ as a function of $r$ and $N$ — a complete proof giving both an upper bound and a construction achieving it up to constants, thereby settling whether Erdős's $\ll r\log N/\log\log N$ is tight. ADVANCES: either (a) improve the upper bound strictly below the best stated in the background, $r\log N/\log\log N$, with a full proof; or (b) exhibit an explicit family $A\subseteq\{1,\ldots,N\}$ satisfying the at-most-$r$-representations hypothesis whose reciprocal sum is provably $\gg r\,\phi(N)$ for a function $\phi$ larger than any previously certified lower bound, together with a proof of both the hypothesis and the sum. Deliver the proof and/or the explicit construction with verification. State in words the bound you improve on.
Background
Posed by Erdős [Er73]; listed as open on erdosproblems.com/538 (fetched 2026-07-21, status 'open'). Erdős gave the standard upper bound by a counting argument: since each product $pa\leq N^2$ arises at most $r$ times, $$\Big(\sum_{n\in A}\frac{1}{n}\Big)\Big(\sum_{p\leq N}\frac1p\Big)\leq r\sum_{m\leq N^2}\frac1m\ll r\log N,$$ and because $\sum_{p\leq N}1/p=\log\log N+O(1)$ this gives $\sum_{n\in A}1/n\ll r\,\frac{\log N}{\log\log N}$. Whether this is the true order — whether a set $A$ can be constructed whose reciprocal sum matches $r\log N/\log\log N$, or whether the upper bound can be lowered — is open. The question sits alongside the closely related restricted-representation problems Erdős #536 and #537 (erdosproblems.com/536, erdosproblems.com/537). One unverified proof claim has been posted in the site's proof-claims thread, but it is not reflected in Bloom's remarks and the problem remains listed open. The attacker's tool: multiplicative/analytic number theory to sharpen the upper bound, paired with an explicit extremal construction (for instance built from primes or smooth numbers) certifying a matching lower bound.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #538 (T. F. Bloom) | website |
| REF-02 | Erdős Problem #537 (T. F. Bloom) — related restricted-representation problem | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.