Multidimensional Szemeredi’s theorem holds with an explicit bound

Combinatorics 1 Minute

You need to know: Set {\mathbb Z}^r of vectors with r integer components, notation a+dX for set \{y \in {\mathbb Z}^r\, : \, y=a+dx, \, x\in X\}, where a \in {\mathbb Z}^r, X \subset {\mathbb Z}^r, and d>0 is an integer.

Background: We say that number N=N(x_1, \dots, x_m) is explicitly computable if there is an algorithm which takes x_1, \dots x_m as an input and returns N as an output.

The Theorem: On 25th April 2005, Timothy Gowers submitted to the Annals of Mathematics a paper in which he proved that, for every \delta > 0, every positive integer r, and every finite subset X \subset {\mathbb Z}^r, there is an explicitly computable integer N=N(\delta, r, X)>0, such that every subset A of the grid \{1, 2, . . . , N\}^r of size at least \delta N^r has a subset of the form a+dX for some a \in {\mathbb Z}^r and integer d>0.

Short context: In 1975, Szemerédi proved that for any positive integer k and any \delta > 0, there exists a positive integer N = N(k, \delta) such that every subset of the set \{1, 2, \dots ,N\} of size at least \delta N contains an arithmetic progression of length k. In a paper submitted in 2000, Gowers proved that this statement holds with N=\exp(\exp(\delta^c)), where c=2^{-2^{k+9}}. The statement in the Theorem is a multidimensional version of Szemeredi’s theorem. The existence of N=N(\delta, r, X) required in the Theorem was first proved by Furstenberg and Katznelson in 1978, but without any explicit algorithm how to actually compute this N. The Theorem provides such an algorithm.

Links: Free arxiv version of the original paper is here, journal version is here. See also Section 7.10 of this book for an accessible description of the Theorem.

Go to the list of all theorems

Unknown's avatar

Published by Bogdan Grechuk

Published

Leave a comment