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
These four points form an axis-parallel square with side length \(d=2\). More generally, the required four corners have the form
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
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
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
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
- T. F. Bloom, Erdős Problem #658: maintained proved classification and orientation caveat.
- H. Furstenberg and Y. Katznelson, A density version of the Hales–Jewett theorem, J. Analyse Math. 57 (1991), 64–119. Bibliographic and theorem-context evidence; full original proof not replayed.
- J. Solymosi, A Note on a Question of Erdős and Graham, Combin. Probab. Comput. 13 (2004), 263–267. The publisher abstract was inspected and matches the exact four-corner assertion; the complete proof was not independently checked.
- Upstream Formal Conjectures #658 source: later, outside GCL's pinned provider snapshot and not a completed GCL proof.
- GCL authenticated source report #658: exact statements and evidence boundaries.
- P. Erdős, Some of my favourite unsolved problems (1997), pp. 527–537 [Er97e]: exact historical passage not independently inspected.
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.