This was studied by Erdős, Lev, Rauzy, Sándor, and Sárközy [ELRSS99], where they call such a property 'non-dividing', and prove the explicit bound\[F(N)<3N^{1/2}+1.\]In [Er97b] Erdős credits Csaba with a construction that proves $F(N) \gg N^{1/5}$. Such a construction was also given in [ELRSS99], where it is linked to the problem of non-averaging sets (see [186]).

Indeed, every such set is non-averaging, and hence the result of Pham and Zakharov [PhZa24] implies\[F(N) \leq N^{1/4+o(1)}.\]This shows the answer to the original question is no, but the general question of the correct growth of $F(N)$ remains open.

In [Er75b] Erdős writes that he originally thought $F(N) <(\log N)^{O(1)}$, but that Straus proved that\[F(N) > \exp((\sqrt{\tfrac{2}{\log 2}}+o(1))\sqrt{\log N}).\]See also [13].

This is discussed in problem C16 of Guy's collection [Gu04].

View the LaTeX source

This page was last edited 30 September 2025.