pith. sign in

arxiv: 2606.02541 · v1 · pith:ZPYZGG6Fnew · submitted 2026-06-01 · 🧮 math.CO · math.NT

Three-color van der Waerden numbers grow super-exponentially

Jacob Fox , Zach Hunter This is my paper

Pith reviewed 2026-06-28 13:40 UTC · model grok-4.3

classification 🧮 math.CO math.NT
keywords van der Waerden numbersarithmetic progressionsthree-coloringslower boundssuper-exponential growthcanonical van der Waerden numbersRamsey theoryErdős-Graham problem
0
0 comments X

The pith

For large k the three-color van der Waerden number w(k;3) exceeds 2 raised to k times log-star k divided by 4.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that for all sufficiently large k there exists a three-coloring of the integers 1 through 2 to the power of k times the iterated logarithm of k over 4 with no monochromatic arithmetic progression of length k. This shows that w(k;3) grows faster than any exponential function of k. A reader would care because earlier lower bounds were only exponential while this one is super-exponential. The work also supplies a new lower bound for multicolor van der Waerden numbers that settles a question of Erdős and Graham on canonical versions.

Core claim

For k sufficiently large there is a three-coloring of the first 2^{k (log^* k)/4} positive integers without any monochromatic k-term arithmetic progressions, so w(k;3) grows faster than any exponential in k. The paper further proves a new lower bound on multicolor van der Waerden numbers which resolves a problem of Erdős and Graham on canonical van der Waerden numbers.

What carries the argument

A three-coloring of an initial segment of length 2^{k (log^* k)/4} that avoids monochromatic k-term arithmetic progressions.

If this is right

  • w(k;3) is at least 2^{k (log^* k)/4} for large k.
  • The three-color van der Waerden number grows faster than any fixed exponential function of k.
  • Multicolor van der Waerden numbers satisfy improved lower bounds.
  • The canonical van der Waerden numbers problem of Erdős and Graham is resolved by the new multicolor bound.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same style of coloring construction may produce super-exponential lower bounds when the number of colors is allowed to grow with k.
  • The result indicates that the gap between upper and lower bounds on w(k;r) for fixed r>3 may also be super-exponential.
  • The technique could be tested on related Ramsey numbers such as Schur or Rado numbers to check for analogous growth.

Load-bearing premise

Such a three-coloring without monochromatic k-term arithmetic progressions exists for every sufficiently large k.

What would settle it

A proof that every three-coloring of the integers from 1 to 2^{k (log^* k)/4} contains a monochromatic k-term arithmetic progression, for some explicit large k.

read the original abstract

For $k$ sufficiently large, we show that there is a three-coloring of the first $2^{k (\log^* k)/4}$ positive integers without any monochromatic $k$-term arithmetic progressions. Thus, the three-color van der Waerden number $w(k;3)$ grows faster than any exponential in $k$. We further prove a new lower bound on multicolor van der Waerden numbers which resolves a problem of Erd\H{o}s and Graham on canonical van der Waerden numbers.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper proves that for all sufficiently large k, there exists a 3-coloring of {1, ..., 2^{k (log^* k)/4}} with no monochromatic k-term arithmetic progression. This implies that the 3-color van der Waerden number w(k;3) grows faster than any exponential function of k. The manuscript also establishes a new lower bound for multicolor van der Waerden numbers that resolves a problem of Erdős and Graham on canonical van der Waerden numbers.

Significance. If the claimed recursive construction holds, the result is a significant advance: it supplies the first super-exponential lower bound for w(k;3) and resolves the Erdős-Graham question on canonical numbers. The explicit inductive construction together with the size calculation reaching 2^{k (log^* k)/4} is a concrete strength that makes the quantitative claim falsifiable and checkable in principle.

major comments (2)
  1. [§3] §3, inductive step (displayed recurrence for the coloring length): the claimed size multiplier of roughly 2^{k/4} per iteration appears to accumulate the log^* factor, but the precise accounting of how many iterations are needed to reach the full exponent k (log^* k)/4 is not cross-checked against the base-case length; a short calculation verifying the total exponent after log^* k steps would strengthen the central claim.
  2. [§4] §4, proof of the canonical lower bound: the reduction from the 3-color construction to the multicolor canonical statement relies on an auxiliary coloring whose monochromatic-AP-free property is asserted but whose parameter dependence on the original k is not made fully explicit; this step is load-bearing for the Erdős-Graham resolution.
minor comments (2)
  1. [§2] The definition of log^* k is used without a parenthetical reminder of the precise iterated-logarithm convention (number of iterations until below 1 or 2); adding this once in §2 would remove ambiguity.
  2. [Figure 1] Figure 1 (schematic of the recursive coloring blocks) uses shading that is difficult to distinguish in black-and-white print; a pattern or label change would improve clarity.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive evaluation and the constructive comments, which help clarify the presentation of the inductive construction and the canonical reduction. We address each major comment below and will incorporate the suggested clarifications in a revised manuscript.

read point-by-point responses

  1. Referee: [§3] §3, inductive step (displayed recurrence for the coloring length): the claimed size multiplier of roughly 2^{k/4} per iteration appears to accumulate the log^* factor, but the precise accounting of how many iterations are needed to reach the full exponent k (log^* k)/4 is not cross-checked against the base-case length; a short calculation verifying the total exponent after log^* k steps would strengthen the central claim.

    Authors: We agree that an explicit cross-check strengthens the central claim. In the revision we will add, immediately after the recurrence in §3, a short calculation verifying the total exponent: starting from the base-case length and applying the multiplier 2^{k/4} for log^* k iterations yields a length of at least 2^{k (log^* k)/4}, with the base case chosen so that the inequality holds for all sufficiently large k. revision: yes

  2. Referee: [§4] §4, proof of the canonical lower bound: the reduction from the 3-color construction to the multicolor canonical statement relies on an auxiliary coloring whose monochromatic-AP-free property is asserted but whose parameter dependence on the original k is not made fully explicit; this step is load-bearing for the Erdős-Graham resolution.

    Authors: We accept that the parameter dependence must be stated explicitly for the reduction to be fully transparent. The revised §4 will include an explicit statement of the auxiliary coloring's parameters (number of colors, progression length, and interval size) as functions of the original k, together with a short verification that the monochromatic-AP-free property carries over with the required quantitative bounds. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper asserts an explicit combinatorial construction of a 3-coloring on an interval of length 2^{k (log^* k)/4} with no monochromatic k-term AP. The claimed lower bound on w(k;3) follows directly from the size of this interval and the absence of monochromatic progressions in the constructed coloring. No parameter is fitted to data and then re-used as a prediction, no self-citation supplies a uniqueness theorem that forces the result, and no ansatz or renaming reduces the central existence claim to its own inputs by definition. The derivation chain is therefore self-contained against external combinatorial benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The abstract presents a pure existence proof and introduces no fitted constants, new entities, or non-standard axioms.

axioms (1)
  • standard math Standard axioms of finite combinatorics and arithmetic progressions
    The result is an existence claim in Ramsey theory relying on ordinary set-theoretic and combinatorial reasoning.

pith-pipeline@v0.9.1-grok · 5600 in / 1228 out tokens · 39140 ms · 2026-06-28T13:40:02.094876+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

34 extracted references · 5 canonical work pages · 1 internal anchor

  1. [1]

    J. H. Bae, A resolution of Erd˝ os Problem #190 via Erd˝ os-Lov´ asz, BCT, and Baker-Harman- Pintz, (April 2026), 10 pp.https://arxiv.org/abs/2604.20588

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  2. [2]

    F. A. Behrend, On sets of integers which contain no three terms in arithmetical progression, Proc. Nat. Acad. Sci. U.S.A.32(1946), 331–332

    1946

  3. [3]

    Berlekamp, A construction for partitions which avoid long arithmetic progressions,Canad

    E. Berlekamp, A construction for partitions which avoid long arithmetic progressions,Canad. Math. Bull.11(1968), 409–414

    1968

  4. [4]

    Bergelson and F

    V. Bergelson and F. K. Richter, Van der Waerden’s theorem on arithmetic progressions – a survey of some historical and modern developments, (March 2026), 49 pp.https://arxiv.org/ abs/2603.25922

    work page arXiv 2026

  5. [5]

    Blankenship, J

    M. Blankenship, J. Cummings, and V. Taranchuk, A new lower bound for van der Waerden numbers,European J. Combin.69(2018), 163–168

    2018

  6. [6]

    T. F. Bloom, Erd˝ os Problem #176, https://www.erdosproblems.com/176, accessed 2026-02-22

    2026

  7. [7]

    Brown, B

    T. Brown, B. Landman, and A. Robertson, Bounds on some van der Waerden numbers,J. Combin. Theory Ser. A115(2008), 1304–1309

    2008

  8. [8]

    Elsholtz, Z

    C. Elsholtz, Z. Hunter, L. Proske, and L. Sauermann, Improving Behrend’s construction: Sets without arithmetic progressions in integers and over finite fields, preprint (June 2024), 15 pp. https://arxiv.org/abs/2406.12290

    work page arXiv 2024

  9. [9]

    Erd˝ os, Problems and results in combinatorial number theory

    P. Erd˝ os, Problems and results in combinatorial number theory. Journ´ ees Arithm´ etiques de Bordeaux (Conf., Univ. Bordeaux, Bordeaux, 1974) (1975), 295–310

    1974

  10. [10]

    Erd˝ os, A survey of problems in combinatorial number theory,Ann

    P. Erd˝ os, A survey of problems in combinatorial number theory,Ann. Discrete Math.(1980), 89–115

    1980

  11. [11]

    Erd˝ os, On some problems in number theory, S´ eminaire Delange-Pisot-Poitou, Paris, 1979– 80,Prog

    P. Erd˝ os, On some problems in number theory, S´ eminaire Delange-Pisot-Poitou, Paris, 1979– 80,Prog. Math.12(1981), 71–75. 17

    1979

  12. [12]

    Erd˝ os, On the combinatorial problems which I would most like to see solved,Combinatorica (1981), 25–42

    P. Erd˝ os, On the combinatorial problems which I would most like to see solved,Combinatorica (1981), 25–42

    1981

  13. [13]

    Erd˝ os and R

    P. Erd˝ os and R. Graham, Old and new problems and results in combinatorial number theory: van der Waerden’s theorem and related topics,Enseign. Math.25(1979), 325–344

    1979

  14. [14]

    Erd˝ os and L

    P. Erd˝ os and L. Lov´ asz,Problems and results on 3 chromatic hypergraphs and some related questions,inColloq. Math. Soc. J´ anos Bolyai10(1975), 609–627

    1975

  15. [15]

    Erd˝ os and R

    P. Erd˝ os and R. Rado, Combinatorial theorems on classifications of subsets of a given set, Proc. London Math. Soc.2(1952), 417–439

    1952

  16. [16]

    Erd˝ os and P

    P. Erd˝ os and P. Tur´ an, On some sequences of integers,J. London Math. Soc.11(1936), 261–264

    1936

  17. [17]

    Fox and Z

    J. Fox and Z. Hunter, Lower bounds for arithmetic Ramsey numbers, in preparation

  18. [18]

    W. T. Gowers, A new proof of Szemer´ edi’s theorem,Geom. Funct. Anal.11(2001), 465–588

    2001

  19. [19]

    R. L. Graham, B. L. Rothschild and J. H. Spencer, Ramsey theory, 2nd ed., Wiley, New York, 1990

    1990

  20. [20]

    Hunter, Lower bounds for multicolor van der Waerden numbers,Israel J

    Z. Hunter, Lower bounds for multicolor van der Waerden numbers,Israel J. Math.267(2025), 783–795

    2025

  21. [21]

    Kelley and R

    Z. Kelley and R. Meka, Strong bounds for 3-progressions, 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), 2023, 933–973

    2023

  22. [22]

    Kozik and D

    J. Kozik and D. Shabanov, Improved algorithms for colorings of simple hypergraphs and applications,J. Combin. Theory Ser. B116(2016), 312–332

    2016

  23. [23]

    J. Leng, A. Sah, and M. Sawhney, Improved bounds for Szemer´ edi’s Theorem, preprint (Febru- ary 2024), 13 pp.https://arxiv.org/abs/2402.17995

    work page arXiv 2024

  24. [24]

    J. Leng, A. Sah, and M. Sawhney, Quasipolynomial bounds on the inverse theorem for the GowersU s+1[N]-norm, preprint (February 2024), 100 pp.https://arxiv.org/abs/2402.17994

    work page arXiv 2024

  25. [25]

    Monroe, New lower bounds for van der Waerden numbers using distributed computing,J

    D. Monroe, New lower bounds for van der Waerden numbers using distributed computing,J. Combin. Math. Combin. Comput.128(2026) 305–315

    2026

  26. [26]

    R. A. Rankin, Sets of integers containing not more than a given number of terms in arithmetical progression,Proc. Roy. Soc. Edinburgh Sect. A65(1960/61), 332–344

    1960

  27. [27]

    Shelah, Primitive recursive bounds for van der Waerden numbers,J

    S. Shelah, Primitive recursive bounds for van der Waerden numbers,J. Amer. Math. Soc.1 (1988), 683–697

    1988

  28. [28]

    Soifer, The new mathematical coloring book—mathematics of coloring and the colorful life of its creators, Springer, 2024

    A. Soifer, The new mathematical coloring book—mathematics of coloring and the colorful life of its creators, Springer, 2024

    2024

  29. [29]

    Spencer, Asymptotic lower bounds for Ramsey functions.Discrete Math.20(1977), 69–76

    J. Spencer, Asymptotic lower bounds for Ramsey functions.Discrete Math.20(1977), 69–76

    1977

  30. [30]

    B. L. van der Waerden, Beweis einer Baudetschen Vermutung,Nieuw Arch. Wisk.15(1927), 212–216. 18

    1927

  31. [31]

    Szab´ o, An application of Lov´ asz’ local lemma — A new lower bound for the van der Waerden number,Random Structures Algorithms1(1990), 343–360

    Z. Szab´ o, An application of Lov´ asz’ local lemma — A new lower bound for the van der Waerden number,Random Structures Algorithms1(1990), 343–360

    1990

  32. [32]

    Szemer´ edi, On sets of integers containing nokelements in arithmetic progression,Acta Arith.27(1975), 299–345

    E. Szemer´ edi, On sets of integers containing nokelements in arithmetic progression,Acta Arith.27(1975), 299–345

    1975

  33. [33]

    In Wikipedia,https://en.wikipedia.org/wiki/Van_der_ Waerden_number, accessed March 19, 2026

    Van der Waerden numbers. In Wikipedia,https://en.wikipedia.org/wiki/Van_der_ Waerden_number, accessed March 19, 2026

    2026

  34. [34]

    X. Xu, M. Liang, and H. Luo, Ramsey theory: Unsolved problems and results, De Gruyter, Berlin; 2018. 19

    2018