Problem Statement
Let $F(N)$ be the maximal size of $A\subseteq\{1,\ldots,N\}$ such that no $a\in A$ divides the sum of any distinct elements of $A\backslash\{a\}$. Estimate $F(N)$. In particular, is it true that\[F(N) > N^{1/2-o(1)}?\]
Categories:
Number Theory
Progress
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].
Source: erdosproblems.com/131 | Last verified: January 13, 2026