Small sets which meet all the k(n)-term arithmetic progressions in the interval [1,n] (Q1119966)

Let \(n,k\in {\mathbb{N}}\) and define f(n,k) to be the minimum cardinality of any subset B of [1,n] which meets all of the k-term arithmetic progressions contained in [1,n]. Thus, for example, \(f(9,3)=4\) since the subset \(B=\{2,5,6,7\}\) of [1,9] meets every 3-term arithmetic progression contained in [1,9] and no smaller subset of [1,9] has this property. The authors show that for any function k(n), \[ f(n,k(n))\leq \frac{12n \log n}{k(n) \log k(n)} \] whenever k(n)\(\geq 4\). This result implies that \(f(n,n^{\epsilon})\leq Cn^{1-\epsilon}\) for some constant \(c=c(\epsilon)\) and that f(n,log n)\(=o(n)\), answering in the affirmative questions raised by Erdős. Bounds for \(f(p^ 2,p)\) when p is a prime are also proved as well as a lower bound for the function associated with Szemerédi's well-known theorem on this subject.