How dense can the sumset $A+B$ be if all its elements are pairwise coprime? (Erdős #432)
Statement
Let $A,B\subseteq\mathbb{N}$ be two infinite sets such that every two distinct elements of the sumset $A+B=\{a+b:a\in A,\ b\in B\}$ are relatively prime. How dense can $A+B$ be? Equivalently, determine the maximal possible order of growth of the counting function $\lvert(A+B)\cap[1,N]\rvert$ over all infinite pairs $A,B$ with $A+B$ pairwise coprime.
Acceptance. FULLY RESOLVES: determine the maximal order of growth of $\lvert(A+B)\cap[1,N]\rvert$ over all infinite $A,B$ with $A+B$ pairwise coprime, with matching upper and lower bounds — a construction attaining the order together with a proof that no such sumset does better; a complete proof. ADVANCES (each independently checkable): (a) an explicit construction of infinite $A,B$ with $A+B$ pairwise coprime whose counting function $\lvert(A+B)\cap[1,N]\rvert$ is provably larger, in order of magnitude, than any construction previously recorded, with proof; (b) a nontrivial upper bound $\lvert(A+B)\cap[1,N]\rvert=o(N/\log N)$ (or sharper), with proof, improving on the trivial pairwise-coprime bound. Deliver the construction plus its proof, or the upper-bound proof.
Background
Asked by Straus, inspired by a problem of Ostmann (compare Erdős #431, erdosproblems.com/431); recorded by Erdős–Graham [ErGr80, p.85]. Listed as open on erdosproblems.com/432 (fetched 2026-07-13, status 'open', tagged 'number theory'); the site records the origin but no partial results. Context (standard): any set of pairwise coprime integers in $[1,N]$ has at most $\pi(N)+1$ elements (each element $>1$ contributes a distinct smallest prime factor), so automatically $\lvert(A+B)\cap[1,N]\rvert\ll N/\log N$ and $A+B$ has density $0$; the open question is how close to this trivial ceiling the counting function of a genuine sumset (which carries additive structure, unlike an arbitrary pairwise-coprime set) can be pushed. This sits in the same Ostmann circle of ideas as the venue's questions on representing structured sets as sums of two sets. The attacker's tool: search for explicit constructions $A,B$ that maximise $\lvert(A+B)\cap[1,N]\rvert$ subject to pairwise coprimality of the sumset, paired with upper-bound arguments showing that additive structure limits how many pairwise-coprime values a sumset can realise.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #432 (T. F. Bloom) | website |
| REF-02 | Erdős Problem #431 (T. F. Bloom) — Ostmann-type source problem | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.