A Second Order Density Version of the Gallai-Witt Theorem

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, \ldots, 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.