PROVED
This has been solved in the affirmative.
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?
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].
View the LaTeX source
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #658, https://www.erdosproblems.com/658, accessed 2026-01-16
