On generalized Stanley sequences (Q1747975)

A strictly increasing sequence \(A\) of non-negative integers is called an AP\({}_k\)-covering sequence, if there exists an \(n_0\), such that for all \(n>n_0\), number \(n\) and some \((k-1)\) terms of the sequence, each less then \(n\), make a \(k\)-term arithmetic progression. Let \(A(n)\) enumerate the number of terms of the sequence \(A\) up to \(n\). The paper proves that there exists an AP\({}_3\)-covering sequence \(A\) such that \(\liminf \frac{A(n)}{\sqrt{n}}\leq 2\) and that there exists an AP\({}_3\)-covering sequence \(A\) such that \(\limsup \frac{A(n)}{\sqrt{n}}\leq 36\). More general, they prove that there exists an AP\({}_k\)-covering sequence \(A\) such that \(A(n)=O((\log n)^{\frac{1}{k-1}} n^{\frac{k-2}{k-1}})\), where the constant in the big-Oh term may depend on \(k\). The paper poses the following conjectures: for any integer \(k \geq 3\), there exists an AP\({}_k\)-covering sequence \(A\) such that \(\limsup \frac{A(n)}{n^{{(k-2)}/{(k-1)}}}<\infty\), and for any integer \(k \geq 3\) there exists a positive constant \(c_k\), such that for any AP\({}_k\)-covering sequence \(A\), \(\liminf \frac{A(n)}{n^{{(k-2)}/{(k-1)}}}>c_k\).