Let $g(N)$ denote the size of the largest such $A$. The construction mentioned proves that\[g(N) \geq \left(\tfrac{9}{8}n\right)^{1/2}+O(1).\]Erdős [Er51b] proved $g(N) \leq (4n)^{1/2}+O(1)$, which was improved by Choi [Ch72b]. Chen [Ch98] established the asymptotic\[g(N) \sim \left(\tfrac{9}{8}n\right)^{1/2}.\]Chen and Dai [DaCh06] proved that\[g(N)\leq \left(\tfrac{9}{8}n\right)^{1/2}+O\left(\left(\frac{N}{\log N}\right)^{1/2}\log\log N\right).\]In [ChDa07] the same authors prove that, infinitely often, Erdős' construction is not optimal: if $B$ is that construction and $A$ is such that $\lvert A\rvert=g(N)$ then, for infinitely many $N$,\[\lvert A\rvert\geq \lvert B\rvert+t,\]where $t\geq 0$ is defined such that the $t$-fold iterated logarithm of $N$ is in $[0,1)$.

This is discussed in problems B26 and E2 of Guy's collection [Gu04].

View the LaTeX source

This page was last edited 27 December 2025. View history