Corners theorem

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 (xy), (x + hy), and (xy + h). Later Solymosi gave a simpler proof, based on the triangle removal lemma. The corners theorem implies Roth's theorem.

References[edit]

  • M. Ajtai, E. Szemerédi: Sets of lattice points that form no squares, Studia Sci. Math. Hungar., 9(1974), 9–11.
  • J. Solymosi: Note on a generalization of Roth's theorem, Algorithms Combin., 25, 2003,Springer, Berlin, 825–827,

External links[edit]