Polychromatic blocks and explicit lower bounds for multicolour van der Waerden numbers
Abstract
Let W(r,k) be the least N such that every r-colouring of {1,…,N} contains a monochromatic k-term arithmetic progression. Many of the best lower bounds for W(r,k) with r≥3 come from blow-up recurrences of Blankenship, Cummings and Taranchuk and of Xu, in which a known colouring is lengthened by a periodic block. Call an h-colouring of Zq k-polychromatic if every k-term progression with nonzero common difference meets each of the h colours. The argument behind these recurrences shows that such a colouring gives W(r,k)>q(W(r−⌈ r/h⌉,k)−1) for all r≥ h. We show that cubic, quartic, quintic and sextic residue colourings give k-polychromatic blocks with q much larger than k (e.g. q=1,376,317 for h=3 and k=28), and use them to get explicit lower bounds. For three colours and 9≤ k≤28 we improve on every published bound we know of, among them W(3,9)>4,002,705 and W(3,28)>159,594,201,561,100,726. For 3≤ r≤6 and 9≤ k≤28, $77$ of the $80$ cases improve on what the published bounds give under these recurrences and the other three tie. For r=5 and 12≤ k≤15 the best values come from palettes that are cyclic intervals of colours indexed by quintic residues. We checked every block by exhaustive enumeration and every base colouring by computer. We also prove that the block modulus is at most $(W(2,k)-1)/(k-1)$, so the method does not improve the asymptotics. For large k the largest cubic block modulus lies between k4−ε and k2 4k.
Related
BibTeX
@misc{kim2026polychromatic,
title = {{Polychromatic blocks and explicit lower bounds for multicolour van der Waerden numbers}},
author = {Seonbin Kim},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.32000},
eprint = {2610.32000},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.32000},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Polychromatic blocks and explicit lower bounds for multicolour van der Waerden numbers
AU - Seonbin Kim
PY - 2026
DA - 2026/10/22
PB - arXiv
DO - 10.48550/arxiv.2610.32000
UR - https://arxiv.org/abs/2610.32000
AB - Let W(r,k) be the least N such that every r-colouring of {1,…,N} contains a monochromatic k-term arithmetic progression. Many of the best lower bounds for W(r,k) with r≥3 come from blow-up recurrences of Blankenship, Cummings and Taranchuk and of Xu, in which a known colouring is lengthened by a periodic block. Call an h-colouring of Z_q k-polychromatic if every k-term progression with nonzero common difference meets each of the h colours. The argument behind these recurrences shows that such a colouring gives W(r,k)>q(W(r−⌈ r/h⌉,k)−1) for all r≥ h. We show that cubic, quartic, quintic and sextic residue colourings give k-polychromatic blocks with q much larger than k (e.g. q=1,376,317 for h=3 and k=28), and use them to get explicit lower bounds. For three colours and 9≤ k≤28 we improve on every published bound we know of, among them W(3,9)>4,002,705 and W(3,28)>159,594,201,561,100,726. For 3≤ r≤6 and 9≤ k≤28, $77$ of the $80$ cases improve on what the published bounds give under these recurrences and the other three tie. For r=5 and 12≤ k≤15 the best values come from palettes that are cyclic intervals of colours indexed by quintic residues. We checked every block by exhaustive enumeration and every base colouring by computer. We also prove that the block modulus is at most $(W(2,k)-1)/(k-1)$, so the method does not improve the asymptotics. For large k the largest cubic block modulus lies between k^4−ε and k^2 4^k.
ER -