|
Let $k$ be a positive integer and let $\delta>0$ . There exists a positive integer $N=N(k,\delta)$ such that every subset of
 of size $\delta N$ contains an arithmetic progression of length $k$ .
The case $k=3$ was first proved by Roth[4]. His method did not seem to extend to the case $k>3$ . Using completely different ideas Szemerédi proved the case $k=4$ [5], and the general case of an arbitrary $k$ [6].
The best known bounds for $N(k,\delta)$ are \begin{equation*} e^{c (\log \frac{1}{\delta})^{k-1}}\leq N(k,\delta)\leq 2^{2^{\delta^{-2^{2^{k+9}}}}}, \end{equation*}where the lower bound is due to Behrend[1] (for $k=3$ ) and Rankin[3], and the upper bound is due to Gowers[2].
For $k=3$ a better upper bound was obtained by Bourgain \begin{equation*} N(3,\delta)\leq c \delta^{-2} e^{2^{56} \delta^{-2}}. \end{equation*}
- 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 $k$ elements in arithmetic progression.
Acta. Arith., 27:299-345, 1975.
Zbl 0303.10056.
|
