A Second Order Density Version of the Gallai-Witt Theorem

Abstract

Szemerédi’s density theorem extends van der Waerden’s theorem by saying that for any $k$ and $c$, $0<c<1$, there exists an integer $n_0=n_0(k,c)$ such that if $n>n_0$ and $S$ is a subset of $\{1,2,\dots ,n\}$ of size at least $cn$ then $S$ contains an arithmetic progression of length $k$. A “second order density” result of Frankl, Graham, and Rödl guarantees that $S$ contains a positive fraction of all $k$-term arithmetic progressions. In this paper, we prove the analogous result for the Gallai-Witt theorem, a multi-dimensional version of van der Waerden’s theorem.