Skip to content

Erdős Problem #439

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: number theory, ramsey theory.

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

Color every positive integer using one of finitely many colors. Erdős Problem 439 asks whether there must be distinct positive integers \(x,y\) of the same color such that \(x+y\) is a perfect square. It also asks about other integer powers. The requirement is universal across all finite colorings: a single coloring containing a suitable pair is only an example, not a proof. The number of colors may be fixed but arbitrarily large.

A useful equivalent picture is an infinite graph whose vertices are the positive integers and whose edges connect distinct \(x,y\) whenever \(x+y\) is a square. A proper graph coloring has no edge whose endpoints share a color. Thus the question asks whether this graph has infinite chromatic number. Such a graph encodes Diophantine addition through the language of Ramsey theory and brings the structural difference between large sum-free sets and color partitions into focus.

A small example

For a very simple example, color every integer according to parity. The even vertices \(2\) and \(14\) share a color and satisfy \(2+14=16=4^2\). The witness is exact, and the integers are distinct. Yet another coloring may require a quite different witness, and even an exhaustive search through finitely many initial integers cannot certify a theorem about every coloring of the infinite domain.

There is also an immediate obstacle for certain polynomial analogues. If the target polynomial \(f(z)\) always takes even values, parity coloring cannot be defeated by a sum of an odd and even vertex, but it may still have monochromatic even-sum edges. The general theorem reported in the literature assumes that \(f\) attains an odd value somewhere. For powers \(f(z)=z^k\), choosing odd \(z\) meets this hypothesis. The condition is a theorem hypothesis, not a gratuitous decoration. When translating the theorem to positive-integer sumsets, one must also check that the chosen polynomial value is positive.

What is known

The historical question was raised by Roth, Erdős, Sárközy and Sós, with a reported conversation involving Silverman in 1977, and it appears in Erdős and Graham's 1980 collection. Erdős, Sárközy and Sós proved the conclusion for two and three colors in a 1989 paper. The remaining arbitrary-finite-color case was established by Khalfalah and Szemerédi (2006), as recorded in the maintained Erdős Problem #439 entry.

Their theorem is stronger than the square case: if \(f\in\mathbb Z[z]\) is a nonconstant integer polynomial that takes an odd value at some integer input, then any finite coloring gives distinct same-colored integers \(x,y\) with \(x+y=f(z)\) for an integer \(z\). Thus the positive integral powers question is also answered affirmatively, subject to matching the precise domain and positivity conventions. The theorem goes substantially beyond simply deducing the coloring question from density bounds.

Erdős #438 is related but logically different. It bounds the size of a single subset whose pairwise sums avoid squares. A finite coloring partitions an infinite set into several classes, and an extremal finite-set density inequality does not alone force a monochromatic edge for an arbitrary number of colors. The general chromatic theorem supplies the needed extra strength.

GCL's current state

The original GCL issue #1709 locks the teorth catalogue at commit 536408716724a2402bdfa7c1d764bf83d64a8c89, problems.yaml Git blob 4e60263a80af6207aca494d2e1388e44fa372889. Its status is proved and the maintained mathematical page agrees. The original issue records no #439 statement file in the admitted FormalConjectures provider revision 85f863718beeec7b58a3a1926ee92e3472bc2020, so no pinned Lean verification is asserted here.

The issue-bound authenticated source audit is https://github.com/grandchallenge/MATH-PROGRAMME/issues/1709#issuecomment-6158436004. This report describes published external results and an elementary exact witness. It is distinct from a GCL replay of the Khalfalah–Szemerédi proof, and it does not authorize mathematical certification, protected main publication or V2 editorial admission.

What remains

The next bounded task can encode finite square-sum graphs on vertex sets \(\{1,\ldots,N\}\), test graph-colorability and record the chromatic number for small \(N\). Use exact square testing by integer square roots, explicitly exclude loops, and compare two independent graph-coloring procedures. In parallel, inspect the 2006 primary theorem and verify whether the universal quantifiers apply to the positive integers or all integers and whether the polynomial parameter may be arbitrary.

Acceptance requires a correct finite graph fixture, a statement-to-theorem concordance and a clear distinction between a positive polynomial value and the odd-value hypothesis. Falsification includes allowing \(x=y\), treating a finite graph's chromatic number as the infinite graph's chromatic number, or claiming the theorem holds for every integer polynomial without the stated restrictions. Stop after the bounded computation and documentary review; the general mathematical answer is already published.

Sources and claim boundaries

Historical framing: Erdős–Graham (1980), Erdős–Sárközy–Sós (1989) and Khalfalah–Szemerédi (2006), summarized at Problem #439. See also the density problem #438. Frozen evidence: GCL issue #1709, teorth catalogue, and authenticated original-issue return.

The finite parity witness is exact and independently checkable. The universal coloring theorem is credited to external researchers. No new theorem, Lean proof replay or accepted editorial status is claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1709 — 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