Erdős Problem #439

Erdős Problem #439: monochromatic square sums

Partial reconstruction, 24 September 2026.

1) Statement and scope

Must every finite colouring of the positive integers contain distinct integers $x,y$ of the same colour with $x+y$ a square? Does the corresponding assertion hold for every fixed positive integer exponent $k$?

The problem is known to have an affirmative answer, by Khalfalah and Szemerédi. This attempt gives elementary proofs for two colours in the square case and for every eventually periodic colouring in every exponent. It does not reproduce their theorem for arbitrary finite colourings. In particular, a solution with $x=y$ would not answer the question, and distinctness is checked throughout.

2) Two colours: an explicit triangle

The three positive integers $6,19,30$ satisfy \[ 6+19=25=5^2,\qquad 6+30=36=6^2,\qquad19+30=49=7^2. \] In any two-colouring, two of these three integers have the same colour. Their sum is a square and they are distinct. Thus the graph joining distinct positive integers whose sum is a square is not bipartite.

There are in fact infinitely many distinct monochromatic pairs in every two-colouring. For each positive integer $h$, the triple $\{6h^2,19h^2,30h^2\}$ has the same property. Choose recursively $h_{j+1}$ with $6h_{j+1}^2>30h_j^2$. These triples are disjoint, so the pairs supplied by the pigeonhole principle are different. This argument does not extend to an arbitrary number of colours merely by producing more disjoint triangles.

3) Every exponent for eventually periodic colourings

Suppose a colouring $\chi$ has period $q\ge1$ beyond some threshold: $\chi(n+q)=\chi(n)$ for every sufficiently large $n$. Fix $k\ge2$ and choose $t$ so large that \[ x=(qt)^k,\qquad y=(2^k-1)(qt)^k \] are beyond the threshold. Both are multiples of $q$, so repeated application of periodicity gives $\chi(x)=\chi(y)$. They are distinct because $2^k-1>1$, and \[x+y=2^k(qt)^k=(2qt)^k.\] Increasing $t$ gives infinitely many such pairs. For $k=1$, any two distinct members of an infinite colour class suffice, since every positive integer is a first power.

4) Why an arithmetic obstruction matters

For the more general equation $x+y=f(z)$ with $f\in\mathbb Z[z]$, an even value of $f$ is necessary for a universal colouring theorem: if $f(z)$ is odd for every integer $z$, colouring integers by parity prevents a monochromatic pair from having sum $f(z)$. The published theorem in particular handles every power polynomial $f(z)=z^k$; its general polynomial formulation must respect the domain of the variables. The constructions above establish only the stated special cases; periodicity cannot be assumed for an arbitrary finite colouring.

5) Outcome, gap, and attribution

UNRESOLVED in this attempt. PARTIAL PROGRESS. The two-colour square case and all eventually periodic colourings are proved in full. The unbounded chromatic number of the square-sum graph, and the general $k$th-power assertion for arbitrary finite colourings, remain unproved in this document. No inference from the graph being non-bipartite to its having infinite chromatic number is made.

Sources: https://www.erdosproblems.com/439, checked 24 September 2026; A. Khalfalah and E. Szemerédi, "On the number of monochromatic solutions of $x+y=z^2$", https://doi.org/10.1017/S0963548305007169. The historical resolution is attributed to that work; it is not presented as a proof supplied here. No formal verification or novelty is claimed.

The percentage is a subjective estimate of how much of the full proof task is supplied, not a probability that the known theorem is true.

6) COMPLETION ESTIMATE

COMPLETION: 30%