Problem Statement
Let $A=\{a_1<a_2<\cdots\}\subseteq \mathbb{N}$ be infinite and let $A(x)$ count the number of indices for which $\mathrm{lcm}(a_i,a_{i+1})\leq x$. Is it true that $A(x) \ll x^{1/2}$?
How large can\[\liminf \frac{A(x)}{x^{1/2}}\]be?
How large can\[\liminf \frac{A(x)}{x^{1/2}}\]be?
Categories:
Number Theory
Progress
Taking $A=\mathbb{N}$ shows that\[\liminf \frac{A(x)}{x^{1/2}}=1\]is possible. Erdős and Szemerédi [ErSz80] proved that it is always $\leq 1$.Tao in the comments has given a simple proof that $A(x) \ll x^{1/2}$. van Doorn has proved that $A(x) \leq (c+o(1))x^{1/2}$ where\[c=\sum_{n\geq 1}\frac{1}{n^{1/2}(n+1)}\approx 1.86.\]This was already proved by Erdős and Szemerédi [ErSz80], who showed that this constant is the best possible.
There are more related results (particularly for the more general case of $\mathrm{lcm}(a_i,a_{i+1},\ldots,a_{i+k})$) in [ErSz80].
Source: erdosproblems.com/440 | Last verified: January 15, 2026