New lower bounds for Van der Waerden numbers using distributed computing

1. Introduction

Van der Waerden’s Theorem [22] states that for any \(k\) and \(r\) there is an \(n\) for which any \(r\)-coloring of \([n]\) admits a monochromatic arithmetic progression of length \(k\), where \([n]\) is taken to denote \(\{1, 2, \ldots, n \}\). The van der Waerden number \(W(k, r)\) is the smallest such \(n\).

Only seven nontrivial van der Waerden numbers are known exactly. These are the entries in Table 1 without a >symbol. For other \(k\) and \(r\), only upper and lower bounds are available.

Van der Waerden’s original proof gave bounds that were not primitive recursive. Shelah [20] gave a proof of bounds that were primitive recursive; in particular, he showed that \(W(k,r)\) lies no higher than the fifth class of the Grzegorcyzk hierarchy.

The current best upper bound is due to Gowers [6], who proved that \[\label{eq1} \notag \begin{split} W(k,r)<2^{\scriptscriptstyle {2^{r^{2^{2^{k+9}}}}}}. \end{split}\]

There has also been work on upper bounds for \(k = 3\) and \(k = 4\). See Bloom and Sisack [4] for the latest result and a history in the former case and Green and Tao [7] for the latter; neither paper explicitly gives bounds but bounds can easily be derived from them, see also [10].

There has also been some work on lower bounds. The construction of Berlekamp [2] shows that if \(p\) is prime, \[\label{eq2} \notag \begin{split} W(p+1, 2)\ge p(2^p-1). \end{split}\]

Lower bounds generated using the probabilistic method have also undergone significant development. The naive method gives a lower bound of \(r^{k/2}\), which the Lovász Local Lemma improves to \(r^k/ek\). The best result of this type is due to Kuzik and Shabanov, who use a generalized Local Lemma with a recoloring algorithm in combination with a generalization of the Lovász Local Lemma to establish the following: \[\label{eq4} \notag \begin{split} W(k,r) \ge cr^k \text{ for some absolute constant } c. \end{split}\]

Determining exact van der Waerden numbers seems to be computationally difficult. The last two discovered, \(W(6,2)\) [12] and \(W(4,3)\) [11], were found using SAT solvers running on special purpose computers. Those authors stated that \(W(7,2)\) was not computable at this time, and perhaps never will be.

Our knowledge of growth rates of van der Waerden numbers in general is extremely limited, though it is notable that all colorings known to be maximal take the form of the constructions of Rabung [17] and Herwig et al. [8], which color based on the discrete logarithm modulo some prime, the latter being a structure-preserving transformation based on cyclic zippers. We provide numerical evidence on the growth rate of van der Waerden numbes based on such constructions and point to evidence that these are optimal.

Through distributed computing, we applied 2 teraflops of computing power over 12 months, or about 500 CPU years on a 2GHz core, to Rabung’s method. We checked the primes exhaustively up to 950 million, as compared to 27 million by Liang et al. [15]. Those authors focused only on the 2-color case. Our methods are no different from those of previous work; the sole difference was the scale of the computation, which was distributed among the computers of 500 volunteers. We also used cyclic zippers, the method of the latter paper, which double the size of a coloring produced with Rabung’s method, checking primes up to 40 million, without finding any new lower bounds superior to those of Rabung’s method.¹ It seems as though Rabung’s method overtakes cyclic zippers for large \(k\) as our computations would otherwise have shown a cyclic zipper generating a better lower bound for values of \(W(k,2)\) with \(k\) between 13 and 19 inclusive.

The paper is organized as follows. Section 2 presents the constructions utilized. Section 3 gives evidence that the bounds generated are tight. Section 4 explains our computational infrastructure. Section 5 describes our results. Section 6 discusses the structure of the der Waerden number and presents three conjectures based on our findings.

2. Constructions

We used the constructions of discrete logarithms [17] and cyclic zippers [8]) with larger primes and substantially greater computing power; the algorithm for zipping can be found in the latter paper. We also include in Tables 1-3 bounds which follow from the recursion formulas of Xu [23] and Blankenship et al. [3].

Rabung’s method colors \([p-1]\) so that the \(n\)th entry is assigned \(\log_\rho n \mod r\), where \(\rho\) is a fixed primitive root of \(p\) and \(\log_\rho n\) is the discrete logarithm. Notice that if \(a, a+d, \ldots, a+(k-1)d\) are colored identically, then \(ad^{-1}, ad^{-1}+1,\ldots, ad^{-1}+k-1\) with spacing 1 are as well. Therefore, modulo \(p\), one only needs to check for progressions of spacing 1. Rabung’s method can alternatively be seen as coloring with power residues.

The numbers above are the primes we used to find the lower bounds. Results with the Cyclic Zipper Method [8] are shown above. Z=zipped once, ZZ=zipped twice. Entries with two numbers separated by an “x” are the numbers used in Xu’s [23] method. Entries with a prime and van der Waerden number separated by a \(\cdot\) were produced with Blankenship et al’s [3] recurrence relation. The lower bounds that are bold are new or have been improved by this paper. For primes close to 1 billion, there may be better results that we did not check (as in the case of \(W(25,2)\)).

We \(r\)-color \(0,1, \ldots, (k-1)p\) so that position \(n\) is given color \(\log_\rho n \mod r\) for \(n\) not in the set \({0,p, \ldots, (k-1)p}\), then assign any colors to members of that set so that not all have the same color. Rabung showed that this coloring contains no monochromatic arithmetic progression of length \(k\) if and only if: (a) there is no monochromatic arithmetic progression of spacing 1 in \(1, \ldots, p-1\) and (b) if 1 and \(p-1\) have the same color then \([(k-1)/2]\) do not all have the same color, while if 1 and \(p-1\) have different colors then \([k-1]\) do not all have the same color [17]. Pseudocode is presented in Algorithm 1.

The Cyclic Zipper Method doubles the length of a coloring generated with the above method by interleaving it with itself. This was inspired by maximal colorings for \(W(6,2)\), which were computed in [12].² We checked \(k\) up to 18 and \(r\) up to 10 with cyclic zipping code shared by Rabung and Lotts [18]. It was terminated after having checked all primes through 40 million, given CPU constraints, and found that improved bounds were no longer being produced. This method did recreate already known lower bounds for smaller \(k\).

Tables 1-3 include bounds found through the method of Xu [23] of applying colorings recursively. He defines \(WR(k, r)\), or the ring van der Waerden number, as the van der Waerden number over \(\mathbb{Z}_p\) for some prime \(p\). This is taken to mean 1 larger than the largest prime \(p\) for which some \(r\)-coloring over \(\mathbb{Z}_p\) contains no monochromatic \(k\)-length arithmetic progression. He shows that if \(k\geq3, s\geq2, t\geq1, 5\leq n<WR(k, s)\), then \(W(k, st)>p(W(k,t)-1)+1\). The case \(t=1\) is particularly important; it lets one concatenate \(k-1\) copies of a coloring of \(\mathbb{Z}_p\). This is the concatenation which the power residue method uses, though it is able to add one color to the end. Note that throughout the rest of the paper the ring van der Waerden number will be taken to be that over \(\mathbb{F}_p\) rather than \(\mathbb{Z}_p\).

Finally, in Tables 1-3, we used the recursion formula of Blankenship et al. [3], who showed that \(W(k,r)>p\cdot(W(k,r-\lceil\frac{r}{p}\rceil)-1)\) whenever \(p\) is prime and less than or equal to \(k\). This generalizes Berlekamp’s [2] lower bound for \(r=2\).

The asterisks (*) represent our new bounds.

3. Evidence for optimality of constructions

Our bounds may shed light on the growth of the van der Waerden Numbers. Five of the seven known exact van der Waerden numbers (excluding \(W(3,2)\) and \(W(3,3)\)) have tight lower bounds based on the power residue method and Cyclic Zipping. These exceptions are likely due to a unique behavior among the van der Waerden numbers for \(k=3\); see Heule’s paper [10] for more details.

In particular, these two methods have been shown to produce all maximal colorings for all but the smallest known two-color van der Waerden numbers.

There is another reason to expect the power residue method to give good lower bounds. If \(\log_\rho n = \log_\rho (n + 1) = \log_\rho (n + 2) \mod r\), which is an arithmetic progression of spacing 1 and length 3, then for any \(c\), \(\log_\rho cn = \log_\rho (cn + c) = \log_\rho (cn + 2c) \mod r\), which is an arithmetic progression of spacing \(c\). Therefore, these sequences are saturated arithmetic progressions of length \(k-1\) of every possible spacing, which is a reason to think they are good lower bounds for \(W(k,r)\).

However, there are cases where SAT solvers have outperformed the Rabung’s method plus Cyclic Zipping; for \(W(5,3)\) a SAT solver [9] beat those two methods.

4. Computations

We used Berkeley Open Infrastructure For Network Computing (BOINC) to distribute the work among volunteers’ computers. Two teraflops of computing power were utilized over 12 months, or around 500 CPU years on a 2 GHz core. To validate the results, two computers applied the Rabung’s method to each prime. There were a total of 516 volunteers and 1760 computers in 53 countries. The program had Linux and Windows versions and was written in C++. Each computer was assigned as input a range of 250 integers (for instance, from 1,000 to 1,249), identified primes in this range, and applied the Rabuung’s method to them. They then, for each \(r\) recorded the longest progression \(k-1\) in that coloring, and on that basis reported a lower bound for \(W(k,r)\). The server received and amalgamated these reports to record the best lower bounds as shown in Table 1. There was no other pre- or post-processing by the server; the main computational work was done by the client. For primes up to 40 million, the volunteers’ computers also applied Cyclic Zipping to the generated colorings.

Both memory and CPU time were bottlenecks. For a given prime \(p\), to apply Rabung’s method, the program populates a one-dimensional array of length \(p-1\) with the powers of a primitive root. As an optimization of memory and CPU time, the same array is used for two to seven colors. To check a prime of nearly one billion, the array would have nearly one billion entries stored in RAM. The CPU time for to populate the array for each prime was 3-4 minutes on average, depending on the speed of the volunteer’s computer. It would be possible to store the array more compactly if the focus were on \(r=2\), i.e., with one bit per array entry, through bit stuffing, although we did not pursue that given the CPU constraint. There is no apparent way to improve on CPU time by populating the array more efficiently.

There are a number of reasons that a reader should have confidence in our results reported in Tables 1-3. First, two computers verified each computation in the BOINC project. Secondly, we reproduced all known lower bounds found using these methods. Thirdly, the reader can verify that the primes in Table 2 give the lower bounds in Table 1 using our source code, available at https://github.com/hmonroe/vdw with and without zipping. That site provides versions compiled for Windows, and sample input and output files. Verifying that the primes shown in Table 2 give the best possible lower bounds would require similar resources as our project, that is, around 500 CPU years on a 2 GHz core.

5. Current Bounds

We computed lower bounds for a wider range of \(k\) and \(r\) than did previous work, as can be seen in Tables 1-3. These new lower bounds are shown in bold. Bounds not in bold are the best known of previous work: Rabung and Lotts [18], Herwig et al. [8], Kouril and Paul [12], Landman et al. [13], Landman and Robertson [14], Rabung [17], and Liang et al. [15]. We checked the number of colors, \(r\), up to 10, and progression length, \(k\), up to 25, though we only present bounds for \(r\) at most 4 since for more colors our bounds were beaten by the recursions of Xu and Blankenship.

Our lower bounds on \(W(k,2)\) grow roughly exponentially in \(k\). Letting \(WR'(k,r)\) and \(W'(k,r)\) be this paper’s lower bounds on the ring van der Waerden (that being van der Waerden numbers on \(\mathbb{F}_p\) rather than \(\mathbb{Z}_p\)) and van der Waerden numbers, the ratio \(W'(k+1,2)/W'(k,2)\) seems to oscillate between 2 and 2.7 when \(k>14\), which is shown in Figure 1. The ratio \(W'(k+1,3)/W'(k,3)\) seems to hover around 3 or 4. There are several lower bound formulas with this growth rate. Berlekamp’s [2] bound states that \(W(p+1, 2)\ge p(2^p-1)\) for primes \(p\). Blankenship et al. [3] show that \(W(p+1,r)>p^{r-1}2^p\) for primes \(p\), which is a generalization of this bound. Landman and Robertson [14] generalized it in a different direction, showing that for primes \(q\), \(p\ge5\), \(W(p+1,q)\ge p(q^p-1)+1\).

The strength of power residue colorings manifests itself in smaller van der Waerden numbers which are known exactly. As can be seen in Table 2, Rabung’s method and cyclic zippers produce the largest possible colorings for 5 of the 7 currently known nontrivial van der Waerden numbers, that being Rabung’s method for \(W(4,2), W(4, 3), W(3, 4)\) and the cyclic zipper method for \(W(5, 2)\) and \(W(6, 2)\). In fact, for each of these, the respective method produces all maximal colorings.

6. The structure of van der Waerden numbers

The strength of Rabung’s method suggests an interplay between the van der Waerden number and the ring van der Waerden number. Xu’s method of concatenation can be applied to bound the former substantially above the latter. We present a simple argument that runs the other way.

We conjecture that the van der Waerden number for large \(k\) grows like \(r^{\text{O}(k^2)}\), and that it may even grow as slowly as \(r^k\) based on the following argument. If the following conjecture were shown, the structure of the van der Waerden number would be nearly completely determined, barring the case of large \(r\):

It was shown in [16] that if \(p > Ck2^k\) for some absolute constant \(C\), there are \(k\) consecutive quadratic residues modulo \(p\). Assuming the above conjecture, the two-color van der Waerden number would grow no more quickly than exponentially in the square of \(k\). Looking at Figure 2 gives strong intuition in the regard of arithmetic progressions of residues of squares and cubes; note that the low value at \(k=25\) for 2 colors suggests that the bound here can be improved. The dips for even \(k\) suggests that arithmetic progressions of quadratic residues tend to be of even length.

If colorings generated with quadratic residues are optimal for two colors for sufficiently large \(k\), \(W(2,k)\) would grow somewhat like \(k^2 2^k\). We do not believe, however, that the method is optimal for larger numbers of colors. The four-color van der Waerden number, for example, would grow at least as quickly as \(k^3 4^k\), as opposed to a \(k^2 4^k\) bound generated naively. The recursion of Xu would allow one to combine factors of \(k\) from the two-color van der Waerden number and the corresponding ring van der Waerden number.

We conjecture that the van der Waerden number grows roughly as follows:

Acknowledgments

We are indebted to John Rabung for providing us with advice while planning the work. We appreciate the guidance of Jay Cummings, Bill Gasarch, Ben Green, Stanislaw Radzizowski, Aaron Robertson, Vladislav Taranchuk, Xiadong Xu, and Daniel Zhu. Any remaining errors are our own. We would also like to thank the over 500 volunteers who contributed their computing resources, without whom it would not have been possible to carry out a computation of this magnitude.