In arithmetic combinatorics, Szemerédi's theorem is a result concerning arithmetic progressions in subsets of the integers. In 1936, Erdős and Turán conjectured that every set of integers A with positive natural density contains a k-term arithmetic progression for every k. Endre Szemerédi proved the conjecture in 1975.
A subset A of the natural numbers 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 {1, 2, ..., N} of size at least δN contains an arithmetic progression of length k.
Another formulation uses the function rk(N), the size of the largest subset of {1, 2, ..., N} without an arithmetic progression of length k. Szemerédi's theorem is equivalent to the asymptotic bound
That is, rk(N) grows less than linearly with N.
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 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. Terence Tao has called the various proofs of Szemerédi's theorem a "Rosetta stone" for connecting disparate fields of mathematics.
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Terence Chi-Shen Tao (; born 17 July 1975) is an Australian mathematician. He is a professor of mathematics at the University of California, Los Angeles (UCLA), where he holds the James and Carol Collins chair. His research includes topics in harmonic analysis, partial differential equations, algebraic combinatorics, arithmetic combinatorics, geometric combinatorics, probability theory, compressed sensing and analytic number theory. Tao was born to ethnic Chinese immigrant parents and raised in Adelaide.
In mathematics, arithmetic combinatorics is a field in the intersection of number theory, combinatorics, ergodic theory and harmonic analysis. Arithmetic combinatorics is about combinatorial estimates associated with arithmetic operations (addition, subtraction, multiplication, and division). Additive combinatorics is the special case when only the operations of addition and subtraction are involved. Ben Green explains arithmetic combinatorics in his review of "Additive Combinatorics" by Tao and Vu.
We consider a divergence-form elliptic difference operator on the lattice Zd, with a coefficient matrix that is an i.i.d. perturbation of the identity matrix. Recently, Bourgain introduced novel techniques from harmonic analysis to prove the convergence of ...
A decomposition of multicorrelation sequences for commuting transformations along primes, Discrete Analysis 2021:4, 27 pp. Szemerédi's theorem asserts that for every positive integer k and every δ>0 there exists n such that every subset of ${1, ...
2021
In a recent work, Bourgain gave a fine description of the expectation of solutions of discrete linear elliptic equations on Zd with random coefficients in a perturbative regime using tools from harmonic analysis. This result is surprising for it goes beyon ...