Corners theorem
Encyclopedia
In mathematics, the corners theorem is an important result, proved by Miklós Ajtai
and Endre Szemerédi
, of a statement in arithmetic combinatorics
. It states that for every ε > 0 there exists N such that given at least εN2 points in the N × N grid {1, ..., N} × {1, ..., N}, there exists a corner, i.e., three points in the form (x, y), (x + h, y), and (x, y + h). Later Solymosi gave a simpler proof, based on the triangle removal lemma. The corners theorem implies Roth's theorem
.
Miklós Ajtai
Miklós Ajtai is a computer scientist at the IBM Almaden Research Center. In 2003 he received the Knuth Prize for his numerous contributions to the field, including a classic sorting network algorithm Miklós Ajtai (born 2 July 1946, Budapest, Hungary) is a computer scientist at the IBM Almaden...
and Endre Szemerédi
Endre Szemerédi
Endre Szemerédi is a Hungarian mathematician, working in the field of combinatorics and theoretical computer science. He is the State of New Jersey Professor of computer science at Rutgers University since 1986...
, of a statement in arithmetic combinatorics
Arithmetic combinatorics
Arithmetic combinatorics arose out of the interplay between number theory, combinatorics, ergodic theory and harmonic analysis. It is about combinatorial estimates associated with arithmetic operations...
. It states that for every ε > 0 there exists N such that given at least εN2 points in the N × N grid {1, ..., N} × {1, ..., N}, there exists a corner, i.e., three points in the form (x, y), (x + h, y), and (x, y + h). Later Solymosi gave a simpler proof, based on the triangle removal lemma. The corners theorem implies Roth's theorem
Szemerédi's theorem
In number theory, Szemerédi's theorem is a result that was formerly the Erdős–Turán conjecture...
.
External link
- Proof of the corners theorem on polymath.