Rado's boundedness conjecture

Some linear equations, such as $x + y = 2z$, have a single-coloured solution however the positive integers are coloured with finitely many colours; others, such as $x + y = 3z$, can be dodged by a clever colouring. Rado conjectured in 1933 that when an equation can be dodged, the number of colours needed is bounded in terms of the number of variables alone. More than ninety years later this is known only for equations in three variables.

Problem

Let $a_1, \dots, a_k$ be nonzero integers and consider the equation

$$a_1 x_1 + a_2 x_2 + \cdots + a_k x_k = 0$$

in positive integers $x_1, \dots, x_k$ (not necessarily distinct). By Rado's theorem, every finite colouring of $\mathbb{N} = \{1, 2, 3, \dots\}$ admits a monochromatic solution if and only if $\sum_{i \in I} a_i = 0$ for some nonempty $I \subseteq \{1, \dots, k\}$.

When no nonempty subset of the coefficients sums to zero, let $c(a_1, \dots, a_k)$ be the least $r$ such that some colouring of $\mathbb{N}$ with $r$ colours has no monochromatic solution.

Conjecture (Rado). For every $k$ there is a number $K(k)$ such that $c(a_1, \dots, a_k) \le K(k)$ for all nonzero integers $a_1, \dots, a_k$ with no vanishing subset sum.

Equivalently: if an equation in $k$ variables has a monochromatic solution in every colouring with $K(k)$ colours, then it has one in every finite colouring.

Background

Rado's 1933 paper characterised the partition regular linear systems, extending Schur's theorem and van der Waerden's theorem, and raised this boundedness question. He also showed that the case of a single equation implies the analogous statement for systems of equations. The conjecture is one of the basic open questions of arithmetic Ramsey theory: it asks whether the qualitative dichotomy in Rado's theorem has a uniform quantitative form.

What is known

• The only non-trivial case that is known is $k = 3$: Fox and Kleitman (2006) proved that 24 colours always suffice, that is, $c(a_1, a_2, a_3) \le 24$.
• Whether 24 is the sharp constant for three variables is not known.
• The conjecture is open for every $k \ge 4$.
• Fox and Kleitman also proposed a modular analogue: colour the units of $\mathbb{Z}/p\mathbb{Z}$ with a number of colours depending only on $k$ so that there is no monochromatic solution whenever no subset sum of the coefficients vanishes modulo $p$. This is open even for $k = 3$, and Green suspects the answer may be negative.
• Milićević (2023) conjectured a 2-adic variant for colourings of $\mathbb{Z}/2^r\mathbb{Z}$ and noted that, by a compactness argument, it would imply Rado's conjecture in full.

What would count as progress

• A proof for four variables: an explicit $K$ with $c(a_1, a_2, a_3, a_4) \le K$ for every equation in four variables with no vanishing subset sum.
• The sharp constant for three variables. A lower-bound witness (an equation together with a SAT certificate that every colouring of $\{1, \dots, n\}$ with fewer colours contains a monochromatic solution) is checkable by computer.
• A proof or a counterexample for the modular analogue of Fox and Kleitman, or for Milićević's 2-adic conjecture, even when $k = 3$.
• A formal proof of the Lean statement green_21 in GreensOpenProblems/21.lean of google-deepmind/formal-conjectures, which also states the sharp-constant, modular and 2-adic variants.

References

1. R. Rado, Studien zur Kombinatorik, Math. Z. 36 (1933), 424–470.
2. J. Fox and D. J. Kleitman, On Rado's boundedness conjecture, J. Combin. Theory Ser. A 113 (2006), 84–100.
3. R. Baber et al., A collection of open problems in celebration of Imre Leader's 60th birthday, arXiv:2310.18163 (2023); Problem 11, by L. Milićević.

Source

Imported from Ben Green's 100 open problems 21, curated by Ben Green. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.