Semi-progressions (Q1924239)

There are several ways to generalize property ``\(AP\)'' of a set of positive integers to contain arbitrarily long arithmetic progressions [cf. \textit{T. C. Brown}, \textit{P. Erdös}, and the second author, J. Comb. Theory, Ser. A 53, No. 1, 81-95 (1990; Zbl 0699.10069)] or \textit{B. M. Landman} and \textit{R. N. Greenwell} [J. Comb. Math. Comb. Comput. 8, 103-106 (1990; Zbl 0749.05007)]. The paper under review presupposes a familiarity with the above mentioned paper by Brown, Erdös, and Freedman, where it was proved that \(AP \Rightarrow QP \Rightarrow CP \Rightarrow C \Rightarrow DW\), and that none of these implications is reversible. The authors introduce a further property \(SP(g)\) with \(g(n)\) a real function defined over nonnegative integers, which requires that a set of integers contains a \(k\)-term semi-progression for \(g(n)\) for infinitely many \(k\). Here, a sequence of \(k\) positive integers \(a_1< a_2< \cdots < a_k\) is called a \(k\)-term semi-progression for \(g(n)\) if the diameter of the set of differences \(\{a_{j+1} - a_j; j=1, \dots, k-1\}\) does not exceed \(g(k)\). If \(g(n)\) is bounded we get a property similar to \(QP\), i.e. containing arbitrarily long quasi-progressions of diameter \(d\). Thus it suffices to consider only the case when \(g\) is unbounded. Then \(QP\Rightarrow SP(g)\). The authors further show that, under suitable conditions, \(SP(g)\) lies between \(QP\) and \(DW\), but it is incomparable with \(CP\) and \(C\). More precisely, if \(g(n) \leq p(n)\) with \(p(n)\) a polynomial, then \(SP(g) \Rightarrow DW\) and this implication is not reversible. Further, for every \(g\) we have \(CP \nRightarrow SP(g)\) and if \(g(n) \geq n\) then \(SP(g) \nRightarrow C\).