Erdős Problem #441

Let \(N\geq 1\). What is the size of the largest \(A\subset \{1,\ldots,N\}\) such that \([a,b]\leq N\) for all \(a,b\in A\), where \([a,b]\) is the least common multiple of \(a\) and \(b\)? Is it attained by choosing all integers in \([1,(N/2)^{1/2}]\) together with all even integers in \([(N/2)^{1/2},(2N)^{1/2}]\)? 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-2\), where \(t\geq 0\) is defined such that the \(t\)-fold iterated logarithm of \(N\) is in \([0,1)\). (erdosproblems.com omits the \(-2\); [ChDa07] proves the bound with it.) This is discussed in problems B26 and E2 of G