HOME

TheInfoList



OR:

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 :\limsup_\frac > 0. 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 \delta \in (0, 1], there exists a positive integer :N = N(k,\delta) 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 :r_k(N) = o(N). 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 :CN\exp\left(-n2^\sqrt + \frac\log \log N\right) \leq r_k(N) \leq \frac, where n = \lceil \log k\rceil. 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 :N2^ \leq r_3(N) \leq C\fracN due to O'Bryant and Bloom respectively. For ''k'' = 4, Green and Tao proved that :r_4(N) \leq C\frac 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 A \subset \mathbb is a set with positive upper density and p_1(n),p_2(n),\dotsc,p_k(n) are integer-valued polynomials such that p_i(0) = 0, then there are infinitely many u, n \in \mathbb such that u + p_i(n) \in A for all 1 \leq i \leq k. 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 \mathbb_3^n 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 theorem
on Scholarpedia * * {{DEFAULTSORT:Szemeredi's theorem Additive combinatorics Ramsey theory Theorems in combinatorics Theorems in number theory