Problem Statement
Let $\delta>0$ and $N$ be sufficiently large depending on $\delta$. Is it true that if $A\subseteq \{1,\ldots,N\}^2$ has $\lvert A\rvert \geq \delta N^2$ then $A$ must contain the vertices of a square?
Categories:
Additive Combinatorics
Progress
A problem of Graham, if the square is restricted to be axis-aligned. (It is unclear whether in [Er97e] had this restriction in mind.)This qualitative statement follows from the density Hales-Jewett theorem proved by Furstenberg and Katznelson [FuKa91]. A quantitative proof (yet with very poor bounds) was given by Solymosi [So04].
Source: erdosproblems.com/658 | Last verified: January 16, 2026