Polychromatic blocks and explicit lower bounds for multicolour van der Waerden numbers

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 all 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, for instance q=1,376,317 for h=3 and k=28, and we use them to obtain explicit lower bounds. For three colours and 9≤ k≤28 every bound known to us is improved, for example 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 are equal; for r=5 and 12≤ k≤15 the best values come from palettes that are cyclic intervals of colours indexed by quintic residues. Every block was checked by exhaustive enumeration and every base colouring by computer. We also show that the block modulus is at most (W(2,k)-1)/(k-1), so the method gives no asymptotic improvement, and that for large k the largest cubic block modulus lies between k4-ε and k^2 4^k.