Erdős Problem #271

declared status 'open'. Formalized: no. For any $n$, let $A(n)=\{0<n<\cdots\}$ be the infinite sequence with $a_0=0$ and $a_1=n$, and for $k\geq 1$ we define $a_{k+1}$ as the least integer such that there is no three-term arithmetic progression in $\{a_0,\ldots,a_{k+1}\}$. Can the $a_k$ be explicitly determined? How fast do they grow? Current best: Odlyzko and Stanley [OdSt78] have found similar characterisations are known for $A(3^k)$ and $A(2\cdot 3^k)$ for any $k\geq 0$ and conjectured in general that such a sequence always eventually either satisfies$$a_k\asymp k^{\log_23}$$or$$a_k \asymp \frac{k^2}{\log k}.$$There is no known sequence which satisfies the second growth rate, but Lindhurst [Li90] gives data which suggests that $A(4)$ has such growth ($A(4)$ is given as A005487 in the OEIS). Moy [Mo11] has proved that, for all such sequences, for all $\epsilon>0$, $a_k\leq (\frac{1}{2}+\epsilon)k^2$ for all sufficiently large $k$. van Doorn and Sothanaphan have noted in the comment section that Moy's proof can be upgraded to give a fully explicit result of$$a_k\leq \frac{(k-1)(k+2)}{2}+n$$for all $k\geq 0$. Prize: no. OEIS: A005487. Tags: additive combinatorics, arithmetic progressions.

Notation is rendered from the stored source. The pinned checkout remains the exact record.