Skip to content

Erdős Problem #658

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: additive combinatorics.

Read this status correctly

The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.

The question in plain language

Imagine coloring a fixed positive proportion of the points in an enormous square integer grid. Can the colored points avoid containing the four corners of a smaller square?

Erdős Problem #658 asks whether, for every fixed density \(\delta>0\), there is a sufficiently large side length \(N\) beyond which every \(A\subseteq\{1,\ldots,N\}^2\) with at least \(\delta N^2\) points contains four vertices of a square.

The answer is yes. Mathematics proves something stronger: one can insist that the square's sides be parallel to the coordinate axes. Jozsef Solymosi gave a quantitative proof in 2004; an earlier qualitative result follows from Furstenberg and Katznelson's density Hales–Jewett theorem.

The historical question attributed to Erdős may have left the square's orientation unspecified. Proving the axis-parallel version removes that ambiguity for the existence claim without resolving exactly what Erdős wrote.

A small example

In the \(3\times3\) integer grid, take

\[ A=\{(1,1),(1,3),(3,1),(3,3)\}. \]

These four points form an axis-parallel square with side length \(d=2\). More generally, the required four corners have the form

\[ (a,b),\qquad(a+d,b),\qquad (a,b+d),\qquad(a+d,b+d),\qquad d\geq1. \]

The four distances around the boundary are all \(d\), and the two diagonals are both \(d\sqrt2\).

The phrase sufficiently large is essential. In the \(2\times2\) grid, choose just the three points

\[ A_0=\{(1,1),(2,1),(1,2)\}. \]

This already has density \(3/4\), but three points cannot contain all four distinct vertices of any square. This does not contradict the theorem: for fixed \(\delta\), the asserted conclusion holds only once \(N\) passes a threshold \(N_0(\delta)\).

A thin diagonal or a single row can also be square-free, but its density tends to zero as the grid grows. Such examples do not refute a fixed-positive-density theorem.

What is known

The logical form of the result is

\[ \forall\delta>0\quad\exists N_0(\delta)\quad \forall N\geq N_0(\delta)\quad \forall A\subseteq[N]^2, \]
\[ |A|\geq\delta N^2 \ \Longrightarrow\ \exists a,b,d\in\mathbb N,\ d>0: \{(a,b),(a+d,b),(a,b+d),(a+d,b+d)\}\subseteq A. \]

Because every displayed collection forms a Euclidean square, this is strictly stronger in its conclusion than merely asserting the existence of a square in an unspecified orientation.

The 1991 article of Hillel Furstenberg and Yitzhak Katznelson, A density version of the Hales–Jewett theorem, Journal d'Analyse Mathématique 57, 64–119, supplies a broader combinatorial density theorem. Its relevant geometric corollary says that positive-density grids contain homothetic copies of finite rectangular patterns, including the four corners of a square. Here a homothetic copy of an axis-aligned pattern means every coordinate is rescaled by the same positive factor and translated.

Jozsef Solymosi's A Note on a Question of Erdős and Graham, Combinatorics, Probability and Computing 13 (2004), 263–267, gave a quantitative proof for exactly these four corners. The Cambridge University Press abstract explicitly states that every sufficiently dense grid contains

\[ \{(a,b),(a+d,b),(a,b+d),(a+d,b+d)\}. \]

The word quantitative means that the proof supplies an effective (though very large) dependence on \(\delta\), not that a modest finite grid necessarily contains a square at a given density. This draft does not assert a specific numerical value for \(N_0(\delta)\).

The formalization boundary. GCL's frozen formal-provider snapshot does not contain a protected file for #658. A later upstream 658.lean file has been inspected separately; it formalizes the axis-parallel conclusion with a positive integer side length and an eventual-in \(N\) density hypothesis. It references an external Lean proof, but the upstream wrapper itself ends in a sorry. Neither the reference nor its metadata constitutes independent GCL compilation, dependency checking or proof certification.

GCL's current state

The original authenticated RESULT/1 source return records BOUNDED_TASK_DESIGNED and retains the original mathematical qualifications. This is an editorially reviewed explanatory article in the EC-BULK-005-R9 protected batch, effective only when that exact-hash transaction merges. The corresponding maintained Erdős statement and its bibliography were inspected. This editorial decision does not certify any full original theorem proof, independent external formalization, or Lean kernel check.

Preserved source-review qualifications: axis aligned theorem stronger than general square; upstream 658 lean not in protected provider; external lean wrapper sorry. See the immutable 128-case critical review record for the complete source-return caveats.

What remains

The immediate verification package has three bounded components. First, inspect the exact original Erdős 1997 text and Solymosi's full theorem/proof pages to lock the historical assumption, theorem number and quantitative dependencies. Second, compare every quantifier in the external formal statement with the axis-parallel theorem: \(\delta>0\), all sufficiently large \(N\), all dense subsets, four distinct corners and positive \(d\). A witness with \(d=0\) is invalid.

Third, if independent formal certification is actually required, obtain the exact proof environment and verify the externally linked Lean source, its imports, theorem target, transitive axioms and absence of unintended holes. This is a task-dependent use of Lean; it is not a prerequisite for writing a sourced mathematical explanation.

The eventual editorial cohort still needs critical source review, consolidated protected publication, browser inspection of real rendered mathematical notation, and a separate exact-source-hash V2 admission.

Sources and claim boundaries

Authority boundary: a published solution to the stated existence problem, elementary illustrative examples and a carefully distinguished external formal reference. No new GCL theorem, original-source completion, internal Lean certification, protected production merge, browser readback is a protected publication verification gateor editorial admission.

Editorial source decision: R9 critical review, REVIEWED as a source-grounded explanation only. All open mathematical questions, primary-proof fidelity obligations, and external formalization caveats remain separate.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1929 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
  • Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction