Erdős Problem #658

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]. The square is taken to be axis-aligned (Graham's version), which implies the version allowing arbitrary squares.