In
arithmetic combinatorics, Szemerédi's theorem is a result concerning
arithmetic progression
An arithmetic progression or arithmetic sequence () is a sequence of numbers such that the difference between the consecutive terms is constant. For instance, the sequence 5, 7, 9, 11, 13, 15, . . . is an arithmetic progression with a common differ ...
s in subsets of the integers. In 1936,
Erdős and
Turán conjectured
that every set of integers ''A'' with positive
natural density In number theory, natural density (also referred to as asymptotic density or arithmetic density) is one method to measure how "large" a subset of the set of natural numbers is. It relies chiefly on the probability of encountering members of the ...
contains a ''k''-term
arithmetic progression
An arithmetic progression or arithmetic sequence () is a sequence of numbers such that the difference between the consecutive terms is constant. For instance, the sequence 5, 7, 9, 11, 13, 15, . . . is an arithmetic progression with a common differ ...
for every ''k''.
Endre Szemerédi
Endre Szemerédi (; born August 21, 1940) is a Hungarian-American mathematician and computer scientist, working in the field of combinatorics and theoretical computer science. He has been the State of New Jersey Professor of computer science a ...
proved the conjecture in 1975.
Statement
A subset ''A'' of the
natural numbers
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called '' cardinal ...
is said to have positive upper density if
:
.
Szemerédi's theorem asserts that a subset of the natural numbers with positive upper density contains infinitely many arithmetic progressions of length ''k'' for all positive integers ''k''.
An often-used equivalent finitary version of the theorem states that for every positive integer ''k'' and real number
, there exists a positive integer
:
such that every subset of of size at least δ''N'' contains an arithmetic progression of length ''k''.
Another formulation uses the function ''r''
''k''(''N''), the size of the largest subset of without an arithmetic progression of length ''k''. Szemerédi's theorem is equivalent to the asymptotic bound
:
.
That is, ''r''
''k''(''N'') grows less than linearly with ''N''.
History
Van der Waerden's theorem, a precursor of Szemerédi's theorem, was proven in 1927.
The cases ''k'' = 1 and ''k'' = 2 of Szemerédi's theorem are trivial. The case ''k'' = 3, known as
Roth's theorem, was established in 1953 by
Klaus Roth via an adaptation of the
Hardy–Littlewood circle method.
Endre Szemerédi
Endre Szemerédi (; born August 21, 1940) is a Hungarian-American mathematician and computer scientist, working in the field of combinatorics and theoretical computer science. He has been the State of New Jersey Professor of computer science a ...
proved the case ''k'' = 4 through combinatorics. Using an approach similar to the one he used for the case ''k'' = 3, Roth gave a second proof for this in 1972.
The general case was settled in 1975, also by Szemerédi, who developed an ingenious and complicated extension of his previous combinatorial argument for ''k'' = 4 (called "a masterpiece of combinatorial reasoning" by
Erdős). Several other proofs are now known, the most important being those by
Hillel Furstenberg in 1977, using
ergodic theory, and by
Timothy Gowers in 2001, using both
Fourier analysis and
combinatorics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many a ...
.
Terence Tao has called the various proofs of Szemerédi's theorem a "
Rosetta stone
The Rosetta Stone is a stele composed of granodiorite inscribed with three versions of a decree issued in Memphis, Egypt, in 196 BC during the Ptolemaic dynasty on behalf of King Ptolemy V Epiphanes. The top and middle texts are in Ancient ...
" for connecting disparate fields of mathematics.
Quantitative bounds
It is an open problem to determine the exact growth rate of ''r''
''k''(''N''). The best known general bounds are
:
where
. The lower bound is due to O'Bryant
building on the work of
Behrend Behrend may refer to:
People
* Behrend (surname)
Places
* Penn State Erie (Behrend), Pennsylvania
* Penn State Behrend
* Arboretum at Penn State Behrend
Other
* Comcast Corp. v. Behrend, a United States Supreme Court case
See also
* Behrends
...
,
Rankin
Rankin may refer to:
Places Australia
*Division of Rankin, an electoral district in the Australian Federal House of Representatives, in Queensland Canada
*Rankin Inlet, Nunavut
*Rankin Inlet Airport, Nunavut
* Rankin River, Ontario
* Rankin Locat ...
, and Elkin. The upper bound is due to Gowers.
For small ''k'', there are tighter bounds than the general case. When ''k'' = 3,
Bourgain, Heath-Brown, Szemerédi, and
Sanders provided increasingly smaller upper bounds. The current best bounds are
:
due to O'Bryant
and Bloom respectively.
For ''k'' = 4, Green and Tao proved that
:
for some ''c'' > 0.
Extensions and generalizations
A multidimensional generalization of Szemerédi's theorem was first proven by
Hillel Furstenberg and
Yitzhak Katznelson
Yitzhak Katznelson ( he, יצחק כצנלסון; born 1934) is an Israeli mathematician.
Katznelson was born in Jerusalem. He received his doctoral degree from the University of Paris in 1956. He is a professor of mathematics at Stanford Uni ...
using ergodic theory.
Timothy Gowers, Vojtěch Rödl and Jozef Skokan with Brendan Nagle, Rödl, and
Mathias Schacht
Mathias Schacht (born 1977) is a German mathematician who specializes in graph theory..
Schacht earned a diploma in business mathematics in 1999 from the Technical University of Berlin. He did his graduate studies at Emory University, completing ...
, and
Terence Tao provided combinatorial proofs.
Alexander Leibman and
Vitaly Bergelson
Vitaly Bergelson (born 1950 in Kiev) is a mathematical researcher and professor at Ohio State University in Columbus, Ohio. His research focuses on ergodic theory and combinatorics.
Bergelson received his Ph.D in 1984 under Hillel Furstenberg a ...
generalized Szemerédi's to polynomial progressions: If
is a set with positive upper density and
are
integer-valued polynomials such that
, then there are infinitely many
such that
for all
. Leibman and Bergelson's result also holds in a multidimensional setting.
The finitary version of Szemerédi's theorem can be generalized to finite
additive group
An additive group is a group of which the group operation is to be thought of as ''addition'' in some sense. It is usually abelian, and typically written using the symbol + for its binary operation.
This terminology is widely used with structure ...
s including vector spaces over
finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subt ...
s. The finite field analog can be used as a model for understanding the theorem in the natural numbers. The problem of obtaining bounds in the k=3 case of Szemerédi's theorem in the vector space
is known as the
cap set problem.
The
Green–Tao theorem asserts the prime numbers contain arbitrary long arithmetic progressions. It is not implied by Szemerédi's theorem because the primes have density 0 in the natural numbers. As part of their proof,
Ben Green and Tao introduced a "relative" Szemerédi theorem which applies to subsets of the integers (even those with 0 density) satisfying certain pseudorandomness conditions. A more general relative Szemerédi theorem has since been given by
David Conlon
David Conlon (born 1982) is an Irish mathematician who is a Professor of Mathematics at California Institute of Technology. His research interests are in Hungarian-style combinatorics, particularly Ramsey theory, extremal graph theory, combinat ...
,
Jacob Fox, and Yufei Zhao.
The
Erdős conjecture on arithmetic progressions would imply both Szemerédi's theorem and the Green–Tao theorem.
See also
*
Problems involving arithmetic progressions
Problems involving arithmetic progressions are of interest in number theory,
combinatorics, and computer science, both from theoretical and applied points of view.
Largest progression-free subsets
Find the cardinality (denoted by ''A'k''(''m' ...
*
Ergodic Ramsey theory
*
Arithmetic combinatorics
*
Szemerédi regularity lemma
Notes
Further reading
*
External links
PlanetMath source for initial version of this page– the preprint is available a
math.NT/0404188* Ben Green and Terence Tao
Szemerédi's theoremon
Scholarpedia
*
*
{{DEFAULTSORT:Szemeredi's theorem
Additive combinatorics
Ramsey theory
Theorems in combinatorics
Theorems in number theory