PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: High Entry average rating: No information on entry rating
Szemerédi's theorem (Theorem)

Let $ k$ be a positive integer and let $ \delta>0$. There exists a positive integer $ N=N(k,\delta)$ such that every subset of $ \{1,2,\dotsc,N\}$ 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

$\displaystyle e^{c (\log \frac{1}{\delta})^{k-1}}\leq N(k,\delta)\leq 2^{2^{\delta^{-2^{2^{k+9}}}}},$    

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

$\displaystyle N(3,\delta)\leq c \delta^{-2} e^{2^{56} \delta^{-2}}.$    

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 $ k$ elements in arithmetic progression.
Acta. Arith., 27:299-345, 1975.
Zbl 0303.10056.



"Szemerédi's theorem" is owned by bbukh.
(view preamble | get metadata)

View style:


Attachments:
Behrend's construction (Result) by bbukh
Log in to rate this entry.
(view current ratings)

Cross-references: upper bound, lower bound, bounds, length, arithmetic progression, contains, subset, integer, positive

This is version 14 of Szemerédi's theorem, born on 2002-12-26, modified 2004-01-20.
Object id is 3839, canonical name is SzemeredisTheorem.
Accessed 5807 times total.

Classification:
AMS MSC11B25 (Number theory :: Sequences and sets :: Arithmetic progressions)
 05D10 (Combinatorics :: Extremal combinatorics :: Ramsey theory)

Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | prove | add result | add corollary | add example | add (any)