Some More Van der Waerden Numbers

Tanbir Ahmed Department of Computer Science and Software Engineering Concordia University Montréal, QC H3G1M8 Canada

                   ta ahmed@cs.concordia.ca

Abstract The van der Waerden number w(k; t_{0}, t_{1}, …, t_{k−1}) is the smallest positive integer n such that every k-coloring of the sequence 1, 2, …, n yields a monochromatic arithmetic progression of length t_{i} for some color i ∈ {0, 1, …, k − 1}. In this paper, we propose a problem-specific backtracking algorithm for computing van der Waerden numbers w(k; t_{0}, t_{1}, …, t_{k−1}) with t_{0} = t_{1} = ⋯ = t_{j−1} = 2, where k ⩾ j + 2, and t_{i} ⩾ 3 for i ⩾ j. We report some previously unknown van der Waerden numbers using this method. We also report the exact value of the previously unknown van der Waerden number w(2; 5, 7).

1 Introduction

The van der Waerden number w(k; t_{0}, t_{1}, …, t_{k−1}) is the smallest positive integer n such that every k-coloring of the sequence 1, 2, …, n yields a monochromatic arithmetic progression of length t_{i} for some color i ∈ {0, 1, …, k − 1}. For a list of all known values of w(k; t_{0}, t_{1}, …, t_{k−1}) and corresponding references, see Ahmed [1, 2, 3], Ahmed, Kullmann, and Snevily [4], and Kouril [7]. A good k-coloring of the set {1, 2, …, n} corresponding to w(k; t_{0}, t_{1}, …, t_{k−1}) contains no monochromatic arithmetic progression of length t_{i} for any i. We call such a good k-coloring of 1, 2, …, n a certificate of the lower bound w(k; t_{0}, t_{1}, …, t_{k−1}) > n. We denote colorings as strings; for example, 00110011 means the color partition {1, 2, 5, 6} ∪ {3, 4, 7, 8}.

In this paper, we propose a problem-specific backtracking algorithm for computing van der Waerden numbers w(k; t_{0}, t_{1}, …, t_{k−1}) with t_{0} = t_{1} = ⋯ = t_{j−1} = 2 where k ⩾ j + 2, and t_{i} ⩾ 3 for i ⩾ j. We report some previously unknown numbers using this method.

We also report the previously unknown value of w(2; 5, 7) to be 260. By far, only two values in the sequence w(2; 5, t) for t ⩾ 5 are known, namely w(2; 5, 5) = 178 (Stevens and Shantaram [8]) and w(2; 5, 6) = 206 (Kouril [6]).

2 Some new values of w(k; t_{0}, t_{1}, …, t_{k−1})

In this section, we discuss an idea to compute van der Waerden numbers with specific values of t_{0}, t_{1}, …, t_{k−1} taking symmetry into consideration.

2.1 On w(k; 2, 2, …, 2, t_{j}, t_{j+1} …, t_{k−1})

Suppose in w(k; t_{0}, …, t_{j−1}, t_{j}, …, t_{k−1}) where k − j ⩾ 2, we have t_{0} = t_{1} = ⋯ = t_{j−1} = 2, and t_{i} ⩾ 3 for i = j, j + 1, …, k − 1. Any certificate of a lower bound of this van der Waerden number will contain each of 0, 1, …, j − 1 exactly once. Hence the certificate will still remain valid after any in-place permutation of 0, 1, …, j − 1 in the certificate. For example, 898998879898031546989829988989 is a certificate of the lower bound

w(10; 2, 2, 2, 2, 2, 2, 2, 2, 3, 3) > 30,

which uses 10 colors. Keeping 8 and 9 in place, there are 8! certificates that prove the same lower bound.

In such a case, any certificate containing k colors can be transformed into an equivalent certificate replacing each of 0, 1, …, j − 1 with a symbol x, and keeping the remaining k − j colors. When we extend a certificate, we prohibit t_{i}-term arithmetic progressions for i = j, j + 1, …, k − 1 and check that the number of x does not exceed j. This observation greatly reduces the search space (the backtrack search-tree becomes (k −j +1)-ary instead of k-ary) of a trivial backtrack algorithm and makes way for computing new van der Waerden numbers.

From the above discussion, an equivalent certificate in our example is

8989988x9898xxxxxx9898x9988989,

which uses only two colors and a symbol x. For computational convenience, we can write this certificate as

121221102121000000212102211212,

with symbol x being replaced by integer color 0 and color c being replaced by integer color c − j + 1.

2.2 On w(k; 2, 2, …, 2, t, t …, t) with t ⩾ 3

Let t_{0} = t_{1} = ⋯ = t_{j−1} = 2 and t_{i} = t ⩾ 3 for i = j, j+1, …, k−1. We can further minimize the backtrack search-space by extending only one certificate from the set of isomorphic certificates under symmetry. Consider the 48 certificates of the lower bound w(3; 3, 3, 3) > 26 with the colors named 1, 2, and 3.

1: 11221123233131121223133232 2: 11223113132233223131132211
3: 11232113132233223131123211 4: 11323112123322332121132311
5: 11331132322121131332122323 6: 11332112123322332121123311
7: 12112123322332121123311313 8: 12122113223231133113232231
9: 12122113223231133113232232 10: 12122321131332322121331133
11: 12332321122112323321133131 12: 13113132233223131132211212
13: 13133112332321122112323321 14: 13133112332321122112323323
15: 13133231121223233131221122 16: 13223231133113232231122121
17: 21211223113132233223131131 18: 21211223113132233223131132
19: 21211312232331311212332233 20: 21221213311331212213322323
21: 21331312211221313312233232 22: 22112213133232212113233131
23: 22113223231133113232231122 24: 22131223231133113232213122
25: 22313221213311331212231322 26: 22331221213311331212213322
27: 22332231311212232331211313 28: 23113132233223131132211212
29: 23223231133113232231122121 30: 23233132212113133232112211
31: 23233221331312211221313312 32: 23233221331312211221313313
33: 31221213311331212213322323 34: 31311213323221211313223322
35: 31311332112123322332121121 36: 31311332112123322332121123
37: 31331312211221313312233232 38: 32112123322332121123311313
39: 32322123313112122323113311 40: 32322331221213311331212212
41: 32322331221213311331212213 42: 32332321122112323321133131
43: 33112332321122112323321133 44: 33113312122323313112322121
45: 33121332321122112323312133 46: 33212331312211221313321233
47: 33221331312211221313312233 48: 33223321211313323221311212

Table 1: All certificates of w(3; 3, 3, 3) > 26

Let a permutation π of 1, 2, …, k be a sequence π(1), π(2), …, π(k). Let S(k) denote the set of all permutations of 1, 2, …, k. We write the permutations in S(k) in parenthesized notation with respect to the indices 1, 2, …, k. For example,

S(3) = {(1)(2)(3), (1)(2, 3), (1, 2)(3), (1, 2, 3), (1, 3, 2), (1, 3)(2)} .

Let C = c_{1}c_{2} ⋯ c_{n} denote a certificate of the lower bound w(k; t, t, …, t) > n. Define T_{π}(C) and T_{S(k)}(C) by π(c_{1})π(c_{2}) … π(c_{n}) and {T_{π}(C) : π ∈ S(k)}, respectively.

For example, T_{S(3)}(11221123233131121223133232) equals the set with the following elements

\begin{matrix}11221123233131121223133232, & 11331132322121131332122323, \\ 22112213133232212113233131, & 22332231311212232331211313, \\ 33113312122323313112322121, & 33223321211313323221311212. \end{matrix}

Similarly, all 48 certificates can be generated from the following 8 certificates:

1: 11221123233131121223133232 2: 11223113132233223131132211
3: 11232113132233223131123211 7: 12112123322332121123311313
8: 12122113223231133113232231 9: 12122113223231133113232232
10: 12122321131332322121331133 11: 12332321122112323321133131

Table 2: Representative certificates of w(3; 3, 3, 3) > 26

So instead of generating and extending all certificates, we can consider only one from the 3! equivalent certificates. To do so, we can observe that, in a certificate c_{1}c_{2} ⋯ c_{n} of w(k; t, t, …, t) > n, if c_{i} is greater than c_{ℓ} for 1 ⩽ ℓ ⩽ i − 1, then we can ignore branching on c_{i} + 1, c_{i} + 2, …, k at position i.

2.3 The algorithm

We combine the ideas from Sections 2.1 and 2.2 to obtain the following algorithm for w(k; t_{0}, t_{1}, …, t_{k−1}), where t_{0} = t_{1} = ⋯ = t_{j−1} = 2 and k ⩾ j + 2.

Algorithm 1 Recursive algorithm Run(k, j, index, x) 1: function Run(k, j, index, x) 2: if zeroCount > j then return end if 3: if index > 0 and x > 0 then 4: if the indices of t_{x+j−1} x’s in c_{1}c_{2} ⋯ c_{index} form an AP then 5: return 6: end if 7: end if 8: if index > max then max = index end if 9: for i = 0 to k − j do 10: if i = 0 then zeroCount = zeroCount + 1 end if 11: c_{index+1} = i 12: Run(k, j, index + 1, i) 13: if i = 0 then zeroCount = zeroCount − 1 end if 14: if i > 0 and t_{j} = t_{j+1} = ⋯ = t_{k−1} = t then 15: if index ⩽ j + (i − 1)(t − 1) + 1 then 16: if c_{index+1} > c_{ℓ} for 1 ⩽ ℓ ⩽ index then 17: break 18: end if 19: end if 20: end if 21: end for 22: end function We can observe that function Run in Algorithm 1 returns with

max + 1 = w(k; 2, 2, …, 2, t_{j}, t_{j+1}, …, t_{k−1})

when called as Run(k,j,0,0) with zeroCount and max initialized to zero.

2.4 Experiment on some known van der Waerden numbers

In Table 3, we report test-results of Algorithm 1 with parameters corresponding to some known van der Waerden numbers. We consider numbers that are relevant to the algorithm and take less than half an hour of run-time.

(t_{j}, t_{j+1}, …, t_{k−1}) max + 1  time(s)
Run(2, 0, 0, 0) (3,3)  9 = w(2; 3, 3)  0.00
Run(2, 0, 0, 0) (4,4)  35 = w(2; 4, 4)  0.00
Run(3, 1, 0, 0) (3,3)  14 = w(3; 2, 3, 3)  0.00
Run(3, 1, 0, 0) (4,4)  40 = w(3; 2, 4, 4)  0.38
Run(3, 0, 0, 0) (3,3,3)  27 = w(3; 3, 3, 3)  0.12
Run(4, 2, 0, 0) (3,3)  17 = w(4; 2, 2, 3, 3)  0.00
Run(4, 2, 0, 0) (3,4)  25 = w(4; 2, 2, 3, 4)  0.07
Run(4, 2, 0, 0) (3,5)  43 = w(4; 2, 2, 3, 5)  2.20
Run(4, 2, 0, 0) (3,6)  48 = w(4; 2, 2, 3, 6)  42.93
Run(4, 2, 0, 0) (4,4)  53 = w(4; 2, 2, 4, 4)  10.25
Run(4, 1, 0, 0) (3,3,3)  40 = w(4; 2, 3, 3, 3)  4.97
Run(5, 3, 0, 0) (3,3)  20 = w(5; 2, 2, 2, 3, 3)  0.00
Run(5, 3, 0, 0) (3,4)  29 = w(5; 2, 2, 2, 3, 4)  0.84
Run(5, 3, 0, 0) (3,5)  44 = w(5; 2, 2, 2, 3, 5)  38.11
Run(5, 3, 0, 0) (4,4)  54 = w(5; 2, 2, 2, 4, 4)  208.74
Run(5, 2, 0, 0) (3,3,3)  41 = w(5; 2, 2, 3, 3, 3)  102.71
Run(6, 4, 0, 0) (3,3)  21 = w(6; 2, 2, 2, 2, 3, 3)  0.05
Run(6, 4, 0, 0) (3,4)  33 = w(6; 2, 2, 2, 2, 3, 4)  7.66
Run(6, 4, 0, 0) (3,5)  50 = w(6; 2, 2, 2, 2, 3, 5)  522.64
Run(6, 3, 0, 0) (3,3,3)  42 = w(6; 2, 2, 2, 3, 3, 3)  1615.73
Run(7, 5, 0, 0) (3,3)  24 = w(7; 2, 2, 2, 2, 2, 3, 3)  0.31
Run(7, 5, 0, 0) (3,4)  36 = w(7; 2, 2, 2, 2, 2, 3, 4)  59.64
Run(8, 6, 0, 0) (3,3)  25 = w(8; 2, 2, 2, 2, 2, 2, 3, 3)  1.38
Run(8, 6, 0, 0) (3,4)  40 = w(8; 2, 2, 2, 2, 2, 2, 3, 4)  434.12
Run(9, 7, 0, 0) (3,3)  28 = w(9; 2, 2, 2, 2, 2, 2, 2, 3, 3)  5.58

Table 3: Experiment on some known values

2.5 New values of w(k; t_{0}, t_{1}, …, t_{k−1})

We have computed the following new values of w(k; t_{0}, t_{1}, …, t_{k−1}) using Algorithm 1. w(k; t_{0}, t_{1}, …, t_{k−1})

w(7; 2, 2, 2, 2, 2, 3, 6)  = 65
w(7; 2, 2, 2, 2, 2, 4, 4)  = 66
w(7; 2, 2, 2, 2, 3, 3, 3)  = 45
w(8; 2, 2, 2, 2, 2, 2, 3, 5)  = 61
w(8; 2, 2, 2, 2, 2, 2, 3, 6)  = 71
w(8; 2, 2, 2, 2, 2, 2, 4, 4)  = 67
w(8; 2, 2, 2, 2, 2, 3, 3, 3)  = 49
w(9; 2, 2, 2, 2, 2, 2, 2, 3, 4)  = 42
w(9; 2, 2, 2, 2, 2, 2, 2, 3, 5)  = 65
w(9; 2, 2, 2, 2, 2, 2, 3, 3, 3)  = 52
w(10; 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)  = 31
w(10; 2, 2, 2, 2, 2, 2, 2, 2, 3, 4)  = 45
w(10; 2, 2, 2, 2, 2, 2, 2, 2, 3, 5)  = 70
w(11; 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)  = 33
w(11; 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4)  = 48
w(12; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)  = 35
w(12; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4)  = 52
w(13; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)  = 37
w(13; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4)  = 55
w(14; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)  = 39
w(15; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)  = 42
w(16; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)  = 44
w(17; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)  = 46
w(18; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)  = 48
w(19; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3) = 50
w(20; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3) = 51
Table 4: New values of w(k; t_{0}, t_{1}, …, t_{k−1})

Based on the results in Table 4, we have added and extended (as shown in bold fonts) the following entries in the OEIS:

1. \underline{A217005}: w(j + 2; t_{0}, t_{1}, …, t_{j−1}, 3, 3) for j ⩾ 0 with t_{i} = 2, 0 ⩽ i ⩽ j − 1. 9, 14, 17, 20, 21, 24, 25, 28, 31, 33, 35, 37, 39, 42, 44, 46, 48, 50, 51.

2. \underline{A217058}: w(j + 2; t_{0}, t_{1}, …, t_{j−1}, 3, 4) for j ⩾ 0 with t_{i} = 2, 0 ⩽ i ⩽ j − 1. 18, 21, 25, 29, 33, 36, 40, 42, 45, 48, 52, 55.

3. \underline{A217059}: w(j + 2; t_{0}, t_{1}, …, t_{j−1}, 3, 5) for j ⩾ 0 with t_{i} = 2, 0 ⩽ i ⩽ j − 1.

22, 32, 43, 44, 50, 55, 61, 65, 70.

4. \underline{A217060}: w(j + 2; t_{0}, t_{1}, …, t_{j−1}, 3, 6) for j ⩾ 0 with t_{i} = 2, 0 ⩽ i ⩽ j − 1.

32, 40, 48, 56, 60, 65, 71.

5. \underline{A217007}: w(j + 2; t_{0}, t_{1}, …, t_{j−1}, 4, 4) for j ⩾ 0 with t_{i} = 2, 0 ⩽ i ⩽ j − 1.

35, 40, 53, 54, 56, 66, 67.

6. \underline{A217008}: w(j + 3; t_{0}, t_{1}, …, t_{j−1}, 3, 3, 3) for j ⩾ 0 with t_{i} = 2, 0 ⩽ i ⩽ j − 1.

27, 40, 41, 42, 45, 49, 52.

3 Exact value of w(2; 5, 7) using SAT

In this section, we report the exact value of w(2; 5, 7) to be 260.

3.1 w(2; 5, 7) ⩾ 260

The following certificate (a good 2-coloring of 1, 2, …, 259) establishes the lower bound w(2; 5, 7) ⩾ 260 (Ahmed [3]):

11111101 11101111 10000111 10000100 01110111 10100111 11001011 11011100 01000010 11001001 10100001 00011101 11101001 11110010 11110111 00010000 10110010 01101000 01000111 01111010 01111100 10111101 11000100 00101100 10011010 a0010001 11011111 10011011 00101111 0111b011 00011011 01011110 111. (ab is arbitrary)

4 w(2; 5, 7) = 260

It remains to show that every 2-coloring of 1, 2, …, 260 either contains a 5-term arithmetic progression in color 0, or a 7-term arithmetic progression in color 1.

4.1 w(2; 5, 7) ⩽ 260

We construct an instance F of the satisfiability problem (or SAT for short) with 260 variables for the van der Waerden number w(2; 5, 7) such that F is satisfiable if and only if w(2; 5, 7) > 260. For a brief introduction to SAT and SAT-encoding of van der Waerden numbers, see Section 1 in Ahmed [2]. We use a distributed application of an efficient implementation of the DPLL [5] algorithm to show that the constructed instance is unsatisfiable. For a brief description of this implementation and its distributed application, see Sections 3 and 4, respectively, in Ahmed [2].

We have split the instance into 256 parts and then each of them into further parts to distribute them over the cluster machines at Concordia. It took 200 2.2 GHz AMD Opteron processors to run roughly for a year to conclude that there is no good 2-coloring of 1, 2, …, 260 corresponding to w(2; 5, 7).

In such a large computation where thousands of distributed branches of the search tree have run on hundreds of processors, we hope we have not fallen into the trap of an undetected hardware failure (an electricity failure is natural and every detected hardware-failure was rerun from the last state of the search), or a file-manipulation error on a particular branch which unfortunately could contain a good 2-coloring of 1, 2, …, 260. We welcome interested readers with proper resources to conduct another search to verify our result.

5 Acknowledgements

The author would like to thank Clement Lam for his continuous support, Donald Knuth for his time and valuable suggestions, and the anonymous referee for the helpful comments. The author would also like to thank Andalib Parvez for carefully reading the manuscript.

References

[1] T. Ahmed, Some new van der Waerden numbers and some van der Waerden-type numbers, Integers, 9 (2009), A06, 65–76.

[2] T. Ahmed, Two new van der Waerden numbers: w(2; 3, 17) and w(2; 3, 18), Integers, 10 (2010), A32, 369–377.

[3] T. Ahmed, On computation of exact van der Waerden numbers, Integers, 11 (2011), A71.

[4] T. Ahmed, O. Kullmann, and H. Snevily, On the van der Waerden numbers w(2; 3, t),

   preprint, http://arxiv.org/abs/1102.5433.

[5] M. Davis, G. Logemann, D. Loveland, A machine program for theorem-proving, Comm. ACM, 5 (1962), 394–397.

[6] M. Kouril, A backtracking framework for Beowulf clusters with an extension to multicluster computation and SAT benchmark problem implementation, Ph. D. Thesis, University of Cincinnati, Engineering : Computer Science and Engineering, 2006.

[7] M. Kouril, Computing the van der Waerden number W (3, 4) = 293, Integers, 12 (2012), A46.

[8] R. Stevens and R. Shantaram, Computer-generated van der Waerden partitions, Math. Comp., 32 (1978), 635–636.

[9] D. A. D. Tompkins and H. H. Hoos, UBCSAT: An implementation and experimentation environment for SLS algorithms for SAT and MAX-SAT. In Holger H. Hoos and David G. Mitchell, eds., Theory and Applications of Satisfiability Testing of 2004, Lecture Notes in Computer Science, Vol. 3542, Springer, 2005, pp. 306–320.

2010 Mathematics Subject Classification: Primary 11B25; Secondary 05D10. Keywords: van der Waerden number.

(Concerned with sequences \underline{A217005}, \underline{A217007}, \underline{A217008}, \underline{A217058}, \underline{A217059}, \underline{A217060}, and \underline{A217037}.)

Received September 28 2012; revised version received March 12 2013. Published in Journal of Integer Sequences, March 16 2013.

Return to Journal of Integer Sequences home page.