Arithmetic progressions in sequences with bounded gaps
A celebrated theorem of van der Waerden states that for every pair of positive integers \(k\) and \(r\) there exists \(W(k,r)\) such that for the least integer \(w\geq W(k,r)\), any partition of \([1,w]\) into \(r\) parts has a part that contains a \(k\)-term arithmetic progression. Let \(G(k,r)\) denote the smallest positive integer \(g\) such that if \(A= \{1= a_1,a_2,\dots,a_g\}\) is a strictly increasing sequence of integers with \(a_{j+1}- a_j\leq r\), \(1\leq j\leq r-1\), then \(A\) contains a \(k\)-term arithmetic progression. An interesting (and easy) consequence of the theorem of van der Waerden implies the existence of \(G(k,r)\). M. Nathanson gave a quantitative connection between \(W(k,r)\) and \(G(k,r)\). He proved \(G(k,r)\leq W(k,r)\leq G((k-1)r+1,2r-1)\). In the present paper, the authors prove: For every \(k\geq 3\), \[ G(k,2)> \sqrt{(k-1)/2}\cdot (4/3)^{(k-1)/2}. \] Furthermore, they prove that for every \(k\geq 3\), \(r\geq 2\), \[ G(k,2r-1)>(1+ o(1)){r^{k-2}\over ek}. \] Both proofs are probabilistic; in the second one the regular form of the Lovász local lemma is used. Nathanson's inequalities show that it will require hard work to find a reasonable upper bound for \(G(k,3)\).
- Progressions in sequences of nearly consecutive integers
- A pseudo upper bound for the van der Waerden function
- Arithmetic progressions, quasi progressions, and Gallai-Ramsey colorings
- Limitations to equidistribution in arithmetic progressions
- Riesz sequences and arithmetic progressions
- Monochromatic sequences whose gaps belong to {d, 2d, …, md}
- scientific article; zbMATH DE number 7640029 (Why is no real title available?)
This page was built for publication: Arithmetic progressions in sequences with bounded gaps
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1352863)
