Erdős Problems

Tags Prizes

OPEN - $500

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\] or \[\sum_{\substack{x <n\\ x\in A}}\frac{1}{x}=o(\log n)?\]

#143: [Er61][Er73][Er77c][Er92c][Er97c]

primitive sets

Note that if $A$ is a set of integers then the condition implies that $A$ is a primitive set (that is, no element of $A$ is divisible by any other), for which the convergence of $\sum_{n\in A}\frac{1}{n\log n}$ was proved by Erdős [Er35], and the upper bound \[\sum_{n<x}\frac{1}{n}\ll \frac{\log x}{\sqrt{\log\log x}}\] was proved by Behrend [Be35]. This $O(\cdot)$ bound was improved to a $o(\cdot)$ bound by Erdős, Sárkőzy, and Szemerédi [ESS67].

In [Er73] and [Er77c] Erdős mentions an unpublished proof of Haight that \[\lim \frac{\lvert A\cap [1,x]\rvert}{x}=0\] holds if the elements of $A$ are independent over $\mathbb{Q}$.

Over the years Erdős asked for various different quantitative estimates, for example \[\liminf \frac{\lvert A\cap [1,x]\rvert}{x}=0\] or even (motivated by Behrend's bound) \[\sum_{\substack{x <n\\ x\in A}}\frac{1}{x}\ll \frac{\log x}{\sqrt{\log\log x}}.\] In [Er97c] he offers \$500 for resolving the questions in the main problem statement above.

This was partially resolved by Koukoulopoulos, Lamzouri, and Lichtman [KLL25], who proved that we must have \[\sum_{\substack{x <n\\ x\in A}}\frac{1}{x}=o(\log n).\]