Let be a positive integer and let . There exists a positive integer such that every subset of of size contains an arithmetic progression of length .

The case was first proved by Roth[4]. His method did not seem to extend to the case . Using completely different ideas Szemerédi proved the case [5], and the general case of an arbitrary [6].

The best known bounds for are

For a better upper bound was obtained by Bourgain

References

1

Felix A. Behrend.
On the sets of integers which contain no three in arithmetic progression.
Proc. Nat. Acad. Sci., 23:331-332, 1946.
Zbl 0060.10302.

2

Timothy Gowers.
A new proof of Szemerédi's theorem.
Geom. Funct. Anal., 11(3):465-588, 2001.
Preprint available at http://www.dpmms.cam.ac.uk/˜wtg10/papers.html.

3

Robert A. Rankin.
Sets of integers containing not more than a given number of terms in arithmetical progression.
Proc. Roy. Soc. Edinburgh Sect. A, 65:332-344, 1962.
Zbl 0104.03705.

4

Klaus Friedrich Roth.
On certain sets of integers.
J. London Math. Soc., 28:245-252, 1953.
Zbl 0050.04002.

5

Endre Szemerédi.
On sets of integers containing no four elements in arithmetic progression.
Acta Math. Acad. Sci. Hung., 20:89-104, 1969.
Zbl 0175.04301.

6

Endre Szemerédi.
On sets of integers containing no elements in arithmetic progression.
Acta. Arith., 27:299-345, 1975.
Zbl 0303.10056.