Status
On this page
Status
Topics
Status
On this page
Status
Topics
Let be the smallest such that in any finite colouring of (into any number of colours) there is always either a monochromatic -term arithmetic progression or a rainbow arithmetic progression (i.e. all elements are different colours). Estimate . Is it true that
as ?
Let be the smallest such that in any finite colouring of (into any number of colours) there is always either a monochromatic -term arithmetic progression or a rainbow -term arithmetic progression (i.e. all elements are different colours). Estimate . Is it true that
as ?
Source: erdosproblems.com/190
An accepted solution exists. The statement is true.
The site shows SOLVED (page last edited 2 June 2026), a label that describes the precise Statement, and its commentary credits two independent 2026 preprints. The precise Statement is proved, by each of them: Bae proves , so (claim page (Bae, 2026)), and Fox and Hunter prove the stronger (claim page (Fox and Hunter, 2026)). The acceptance evidence is the site's curator's (T. F. Bloom), whose commentary credits both results; Fox and Hunter's preprint credits Bae's earlier independent resolution, and Bae acknowledged their stronger bound in a discussion-thread post of 2026-09-14. Neither is refereed, and no formal proof of the statement has been audited here; the community database lists the problem as solved (Lean) as of its last update of 2026-09-15, through Bae's repository (see Formalization). The request to estimate is open-ended, and no upper bound beyond the existence of is recorded.
The site's wording does not give the length of the rainbow progression. Any two integers form an arithmetic progression, so with progressions of two terms every coloring of has a monochromatic -term progression (one color) or a rainbow two-term one (two or more colors), while the one-color coloring of has neither; read so, and the displayed question has the answer no. A minimum of three terms would give yet another question, which no source states. The change inserts "-term" before the rainbow progression; nothing else changes. The evidence is the poser's own text: Erdős and Graham (1979), printed p. 333 (Old and new problems and results in combinatorial number theory: van der Waerden's theorem and related topics), define by requiring that "there is always an -term arithmetic progression all of whose terms either belong to one class or all different classes", and add that showing might be much harder; the site's wording renders that passage with for . Bae (Section 2.1) and Fox and Hunter (Section 1.1) define the same way. The omission is the site's. No result about the readings with a shorter rainbow progression is recorded.