Problem Statement
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}]$?
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}]$?
Categories:
Number Theory
Progress
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].
Source: erdosproblems.com/441 | Last verified: January 15, 2026