Problem 143

Let $A\subset (1,\infty)$ be a countably infinite set such that for all $x\neq y\in A$ and integers $k\geq 1$ we have

\lvert kx -y\rvert \geq 1.

Does this imply that $A$ is sparse? In particular, does this imply that

\sum_{x\in A}\frac{1}{x\log x}<\infty

\sum_{\substack{x <n\\ x\in A}}\frac{1}{x}=o(\log n)?

Source: erdosproblems.com/143

Primitive sets

Wiki page

Status

ClaimedAnswered

A full solution has been claimed but not yet accepted. Settled in another form, for example when its parts resolve differently or the question is open-ended.

OPEN on the site (page last edited 24 April 2026; its proof-claims tab carries one claim, listed there as full).

Be35: Behrend, F., On sequences of numbers not divisible by another. London Math. Soc. Journal (1935), 42-45.
ESS67: Erdős, P. and Sárközy, A. and Szemerédi, E., On a theorem of Behrend. J. Austral. Math. Soc. (1967), 9-16.
Er35: Erdős, Paul, Note on Sequences of Integers No One of Which is Divisible By Any Other. J. London Math. Soc. (1935), 126-128.
Er73: Erdős, P., Problems and results on combinatorial number theory. A survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971) (1973), 117-138.
Er77c: Erdős, Paul, Problems and results on combinatorial number theory. III. Number theory day (Proc. Conf., Rockefeller Univ., New York, 1976) (1977), 43-72.
Er97c: Erdős, Paul, Some of my favorite problems and results. The mathematics of Paul Erdős, I, Algorithms Combin. 13, Springer (1997), 47--67; display (2.20) and its question, printed pp. 57--58, with the prize offer; the printed question asks whether (2.20) forces the two sums to diverge, the reverse of the statement's signs, recorded on the result page. Library home: Erdős 1997; paged at Erdős 1997, Display (2.20).
KLL25: D. Koukoulopoulos, Y. Lamzouri, and J. D. Lichtman, Erdős's integer dilation approximation problem and GCD graphs. arXiv:2502.09539 (2025).

Problem 143

Status

Proof claims

Discussion