On sets without k-term arithmetic progression

For positive integers n and k  , let rk(n)rk(n) be the size of the largest subset of {1,2,…,n}{1,2,…,n} without arithmetic progressions of length k  . The van der Waerden number W(k1,k2,…,kr)W(k1,k2,…,kr) is the smallest integer w such that every r  -coloring of {1,2,…,w}{1,2,…,w} contains a monochromatic kiki-term arithmetic progression with color i for some i  . In this note, an algorithm is proposed to search exact values of rk(n)rk(n) for some k and n  , and some new exact values of rk(n)rk(n) for k=4,5,6,7,8k=4,5,6,7,8 are obtained. The results extend the previous ones significantly. It is also shown that rk+1(2k2+1)⩾2k2−3k+3rk+1(2k2+1)⩾2k2−3k+3 for prime k⩾3k⩾3, and three lower bounds for van der Waerden numbers are given: W(3,4,5)⩾124W(3,4,5)⩾124, W(5,8)⩾248W(5,8)⩾248, W(5,9)⩾320W(5,9)⩾320.

► Dynamic programming technique is used to test k  -term arithmetic progressions. ► A construction for lower bounds of rk+1(2k2+1)⩾2k2−3k+3rk+1(2k2+1)⩾2k2−3k+3 is provided. ► Many exact values of rk(n)rk(n) are obtained by computing. ► Three lower bounds for van der Waerden numbers are given.