Logo
All Random Solved Random Open
OPEN
Let $t\geq 1$ and $A\subseteq \{1,\ldots,N\}$ be such that whenever $a,b\in A$ with $b-a\geq t$ we have $b-a\nmid b$. How large can $\lvert A\rvert$ be? Is it true that \[\lvert A\rvert \leq \left(\frac{1}{2}+o_t(1)\right)N?\]
Asked by Erdős in a letter to Ruzsa in around 1980. Erdős observes that when $t=1$ the maximum possible is \[\lvert A\rvert=\left\lfloor\frac{N+1}{2}\right\rfloor,\] achieved by taking $A$ to be all odd numbers in $\{1,\ldots,N\}$. He also observes that when $t=2$ there exists such an $A$ with \[\lvert A\rvert \geq \frac{N}{2}+c\log N\] for some constant $c>0$: take $A$ to be the union of all odd numbers together with numbers of the shape $2^k$ with $k$ odd.