Monochromatic sums and products over N: arbitrarily large finite sets in any finite colouring (Erdős #172)
Statement
Is it true that in any finite colouring of $\mathbb{N}$ there exist arbitrarily large finite sets $A$ such that all sums and products of distinct elements of $A$ are the same colour? Here 'all sums and products of distinct elements' means all numbers of the form $\sum_{x \in S} x$ and $\prod_{x \in S} x$ over nonempty subsets $S \subseteq A$ (subsets of size one give the elements of $A$ themselves, so these too must carry the common colour). The first nontrivial case, $\lvert A \rvert = 2$, asks for monochromatic $\{x, y, x+y, xy\}$.
Acceptance. FULLY RESOLVES: a proof that every finite colouring of $\mathbb{N}$ admits arbitrarily large finite $A$ with all sums and products of distinct elements monochromatic; OR a finite colouring of $\mathbb{N}$ (explicitly described) with a proof that some size $k$ is never achieved. Machine-checkable (Lean/Coq) preferred, else a full written proof. ADVANCES: (a) the $\lvert A\rvert = 2$ case over $\mathbb{N}$ — a proof that every finite colouring (or, as a named milestone, every 2-colouring) of $\mathbb{N}$ contains monochromatic $\{x, y, x+y, xy\}$; (b) certified finite instances — for stated $(k, r)$, a SAT-derived proof with verifiable certificate that every $r$-colouring of $\{1,\ldots,N\}$ contains the size-$k$ pattern (establishing the compactness threshold), or an explicit colouring certificate showing a given $N$ does not suffice; (c) strengthenings of Moreira-type patterns over $\mathbb{N}$ (proved enlargements of the guaranteed monochromatic configuration beyond $\{x, x+y, xy\}$ as stated in the background). Deliver the proof file, or the SAT encodings plus certificates plus checker instructions.
Background
First asked by Hindman, and popularized by Erdős [Er77c] and Erdős–Graham [ErGr79, ErGr80]; listed as open on erdosproblems.com/172 (fetched 2026-07-13, status 'open', tagged 'additive combinatorics | ramsey theory'). The infinite version fails: Hindman [Hi80] constructed a 7-colouring of $\mathbb{N}$ admitting no infinite $A$ with all sums and products of distinct elements monochromatic; Erdős's follow-up on infinite $A$ with just 2 colours is Erdős #1198 (erdosproblems.com/1198). Partial progress on the finite version: Moreira [Mo17] proved that in any finite colouring of $\mathbb{N}$ there exist $x,y$ with $\{x, x+y, xy\}$ monochromatic (missing only $y$ from the $\lvert A\rvert=2$ pattern). Over the rationals the problem is solved: Bowen and Sabok [BoSa22] proved the first nontrivial case $\lvert A\rvert = 2$ for finite colourings of $\mathbb{Q}$, and Alweiss [Al23] then proved the full statement — any finite colouring of $\mathbb{Q}\setminus\{0\}$ admits arbitrarily large finite $A$ with all sums and products of distinct elements monochromatic. Over $\mathbb{N}$ even the $\lvert A\rvert = 2$ case (monochromatic $\{x,y,x+y,xy\}$) remains open. Attacker's tools: by compactness, each fixed case ($\lvert A\rvert = k$, $r$ colours) over $\mathbb{N}$ is equivalent to a finite statement about colourings of $\{1,\ldots,N\}$ for some $N$, so SAT solvers with proof logging can both establish finite instances (with DRAT-style certificates) and hunt for colourings that push the required $N$ upward; on the proof side, the ultrafilter/dynamics toolkit behind Moreira's and Alweiss's arguments is the lead.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #172 (T. F. Bloom) | website |
| REF-02 | Formalised statement (Lean, google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.