New lower bounds for van der Waerden numbers

2021/02/02 by Ben Green, Green, Ben
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Number Theory (math.NT)

paper · pdf · doi:10.48550/arxiv.2102.01543

openalex publication_date 2021/02/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We show that there is a red-blue colouring of [N] with no blue 3-term arithmetic progression and no red arithmetic progression of length e^C(log N)^3/4(log log N)^1/4. Consequently, the two-colour van der Waerden number w(3,k) is bounded below by k^b(k), where b(k) = c ( (log k)/(loglog k) )^1/3. Previously it had been speculated, supported by data, that w(3,k) = O(k²).

Related

• Improved lower bounds for van der Waerden numbers
• A short proof that w(3,k) ≥ (1-o(1))k²
• Lower bounds for multicolor van der Waerden numbers
• A Radix Representation for each van der Waerden number W(r, k) with r colors: Why log_rW(r, k) < k² is true whenever k is the number of terms in the arithmetic progression
• Bounds on Van der Waerden Numbers and Some Related Functions