Problem 721

Let $W(3,k)$ be the van der Waerden number defined as the minimum $n$ such that in any red/blue colouring of $\{1,\ldots,n\}$ there exists either a red $3$ -term arithmetic progression or a blue $k$ -term arithmetic progression.

Give reasonable bounds for $W(3,k)$ . In particular, give any non-trivial lower bounds for $W(3,k)$ and prove that $W(3,k) < \exp(k^c)$ for some constant $c<1$ .

Source: erdosproblems.com/721

Number theory
Additive combinatorics
Ramsey theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

The site labels the problem SOLVED, its label for a problem resolved other than by a proof or disproof: the label attaches to the two explicit challenges, both met by refereed papers that the site's curator credits; the site's own commentary says that the growth of $W(3,k)$ is not fully understood but that both of Erdős's specific challenges have been met. The frontmatter lists the two challenges as the problem's parts, each settled by an accepted partial claim, so the derived standing is solved; the derived claim is proved, because both challenges are met by proved bounds. The open-ended sentence "Give reasonable bounds for $W(3,k)$ " is not listed as a part: it is the site's framing of Erdős's remarks, and every question Erdős himself put, quoted in

Gr22: B. Green, New lower bounds for van der Waerden numbers. Forum Math. Pi 10 (2022), e18, 1--51, DOI 10.1017/fmp.2022.12 (received 23 February 2021, accepted 8 March 2022). Theorem 1.1 on p. 2, Theorem 2.1 on p. 5 of the published article. Library home: Green 2022.
Hu22: Z. Hunter, Improved lower bounds for van der Waerden numbers. Combinatorica 42 (2022), suppl. 2, 1231--1252, DOI 10.1007/s00493-022-4925-2; arXiv:2111.01099v3 (21 August 2022), whose pages are the locators. Theorem 1 and Remark 1.1 on p. 2, footnote 1 on p. 1. Library home: Hunter 2022.
Sc21: T. Schoen, A subexponential upper bound for van der Waerden numbers $W(3,k)$ . Electron. J. Combin. 28 (2021), no. 2, P2.34, 10 pp., DOI 10.37236/9704 (published 4 June 2021). Theorem 1 and the remark after it on p. 2. Library home: Schoen 2021.
KeMe23: Z. Kelley and R. Meka, Strong bounds for 3-progressions. arXiv:2302.05537 (v6, 28 October 2024, the version cited); FOCS 2023, pp. 933--973, DOI 10.1109/FOCS57990.2023.00059 (not held). Theorems 1.1--1.2 on pp. 1--2. Library home: Kelley and Meka 2023.
BlSi23: T. F. Bloom and O. Sisask, An improvement to the Kelley–Meka bounds on three-term arithmetic progressions. arXiv:2309.02353v1 (5 September 2023). Theorem 1 on p. 1. Library home: Bloom and Sisask 2023.
Er80: P. Erdős, A survey of problems in combinatorial number theory. Ann. Discrete Math. 6 (1980), 89--115; printed p. 91. Library home: Erdos 1980.
Er81: P. Erdős, On the combinatorial problems which I would most like to see solved. Combinatorica 1 (1981), 25--42; the closing paragraph of Part V, p. 10 of the re-typeset copy (its own pagination). Library home: Erdős 1981. - Not held, second-hand: Y. Li and J. Shu, A lower bound for off-diagonal van der Waerden numbers, Adv. in Appl. Math. 44 (2010), 243--247 ( $W(3,k)\gg(k/\log k)^2$ , quoted from Schoen p. 2 and Green p. 2); T. C. Brown, B. M. Landman and A. Robertson, Bounds on some van der Waerden numbers, J. Combin. Theory Ser. A 115 (2008) ( $w(3,k)\gg k^{2-1/\log\log k}$ , from Green p. 2); K. Cwalina and T. Schoen, Tight bounds on additive Ramsey-type numbers, J. Lond. Math. Soc. 96 (2017) ( $W(3,k)\le\exp(O(k\log k))$ , from Schoen p. 2); T. Bloom and O. Sisask, Breaking the logarithmic barrier in Roth's theorem on arithmetic progressions, arXiv:2007.03528 (the 2020 Roth bound of Schoen's remark).

Problem 721

Status

Proof claims

Discussion