A van der Waerden Variant

Kevin J. Compton

BRICS Research Centre, University of Aarhus, Denmark and EECS Department, University of Michigan Ann Arbor, MI 48109-2122

                           kjc@umich.edu

Abstract

The classical van der Waerden Theorem says that for every every finite set S of natural numbers and every k-coloring of the natural numbers, there is a monochromatic set of the form aS +b for some a > 0 and b ≥ 0. I.e., monochromatism is obtained by a dilation followed by a translation. We investigate the effect of reversing the order of dilation and translation. S has the variant van der Waerden property for k colors if for every k-coloring there is a monochromatic set of the form a(S + b) for some a > 0 and b ≥ 0. On the positive side it is shown that every two-element set has the variant van der Waerden property for every k. Also, for every finite S and k there is an n such that nS has the variant van der Waerden property for k colors. This extends the classical van der Waerden Theorem. On the negative side it is shown that if S has at least three elements, the variant van der Waerden property fails for a sufficiently large k. The counterexamples to the variant van der Waerden property are constructed by specifying colorings as Thue-Morse sequences.

Submitted July 17, 1997; Accepted April 2, 1999.

AMS Subject Classification. Primary: 05D10. Secondary: 11B85, 68R15.

1 Introduction.

Van der Waerden’s theorem on arithmetic progressions is over seventy years old [26], but it continues to reveal new facets and inspire new results. It has many generalizations, such as the Hales-Jewett Theorem [6] and multidimensional versions [21]. It has had unexpected connections with other parts of mathematics, such as topological dynamics [5]. The numerical bounds from van der Waerden’s original proof, long thought to be the best attainable, have been dramatically reduced in recent years [23].

In its most familiar formulation, van der Waerden’s Theorem says that if ℕ = {0, 1, 2, …} is partitioned into a finite number of classes, one of the classes contains arbitrarily long arithmetic progressions. To distinguish this theorem from the variant we will introduce, we refer to it as the classical van der Waerden Theorem. Another way of stating the theorem is to say that for every k-coloring of ℕ (or mapping α : ℕ → {0, …, k − 1}) and every finite S ⊆ ℕ, there are integers a > 0 and b ≥ 0 such that aS + b = {as + b | s ∈ S} is monochromatic. That is, α maps all elements in some set aS + b to the same color. Thus, we can find a monochromatic set by dilating S (multiplying every element by a) and then translating (adding b to every element).

The question we will consider involves another, apparently unexplored, variation: what happens when the order of dilation and translation is reversed? Is it the case that if ℕ is k-colored and S is a finite subset of ℕ, there are a > 0 and b ≥ 0 such that a(S + b) is monochromatic? The answer, interestingly enough, depends on S and k. For some values of S and k this property (which we call the variant van der Waerden property) holds; for others it does not. We do not yet have a characterization of the cases where it holds, but this paper makes some initial progress in that direction.

For a nonempty set S ⊆ ℕ and k > 0, VW (S, k) holds if for every k-coloring of ℕ there are integers a > 0 and b ≥ 0 such that a(S + b) is monochromatic. (When we speak of a set of the form a(S + b), we will assume that a > 0 and b ≥ 0.) Clearly, if VW (S, k) holds, T ⊆ S and l < k, then VW (T, l) holds. Also, if c ≥ 0 and VW (S + c, k) holds, then VW (S, k) holds.

In Section 2 we will examine the positive instances of the variant van der Waerden property and in Section 3 we will examine negative instances. Proofs of the negative results make use of Thue-Morse sequences which have been studied both in formal language theory and topological dynamics. We conclude with some open questions in Section 4. Many of the results in this paper were originally conjectured on the basis of computer experiments. We will describe how the experiments led to the results proved in this paper. The C program vw.c used in these experiments may be downloaded from the EJC site.

The computer program we used computed some values of M(S, k), which is defined to be the least M such that every k-coloring of {0, 1, 2, …, M} has a monochromatic subset of the form a(S + b). If we define M′(S, k) to be the least M′ such that every k-coloring of {0, 1, 2, …, M′} has a monochromatic subset of the form aS + b, it is clear that M′(S, k) ≤ M(S, k) whenever M(S, k) is defined. Brown, et al. [4] give a nearly complete account of the values of M′(S, k) when |S| = 3.

In general, one may formulate many different variants of van der Waerden’s Theorem by asking, for a given set A of finite sets of integers and a given k > 1, whether every k-coloring of ℕ will make at least one element of A monochromatic. Researchers have investigated this question for various choices of A (see, e.g. [3, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]), but not for the one considered here.

We will require a few definitions in the sections that follow. Besides k-colorings of ℕ, we will also consider k-colorings of initial intervals of ℕ. It is useful to identify a kcoloring α : {0, 1, …, i−1} → {0, …, k−1} with a word of length i over the k-symbol alphabet, viz., the word α_{0}α_{1} ⋯ α_{i−1}, where α_{i} = α(i). Similarly, we identify a kcoloring of ℕ with an infinite word over the k symbol alphabet. Thus, we may speak of k-coloring α : I → {0, …, k − 1} being a prefix of k-coloring β : J → {0, …, k − 1} if I is an initial interval of J and α is the restriction of β to I; if, in addition, I is properly contained in J, we say α is a proper prefix of β. When α is a prefix of β, we will also say that β is an extension of α.

2 Positive Instances

Instances where the variant van der Waerden property holds satisfy the usual compactness property of Ramsey-type theorems (see [6]). That is, if VW (S, k) holds, there is an M such that for every k-coloring of {0, 1, …, M}, there is a monochromatic set of the form a(S + b) is contained in {0, 1, …, M}. For each S and k such that VW (S, k) holds, let M(S, k) be the least such M.

The compactness property allows us to verify through a computer search that VW (S, k) holds. Suppose S and k are given. We may systematically list k-colorings of sets {0, 1, ..., i} until we find an i such that all k-colorings contain a monochromatic set of the form a(S +b). This approach may be improved by applying standard search techniques.

The table in Figure 1 below shows the result of running a search program for various values of k and various two-element sets S. For the empty entries the program did not return a value because it exceeded a time limit. In the classical Van der Waerden Theorem, the case where S has two elements is not interesting. For the variant van der Waerden property, the situation is not completely trivial, as we shall see.

k
2 3 4 5
{0,1} 2 4 12 32
{0,2} 4 6 12
{1,2} 4 12 32
{0,3} 6 12 24
{1,3} 6 12 24
{2,3} 6 12 48
{0,4} 8 12 24
S {1,4} 8 24
{2,4} 8 12 24
{3,4} 8 16
{0,5} 10 20
{1,5} 10 18
{2,5} 10 24
{3,5} 10 18
{4,5} 10 24

Figure 1: Some values of M(S, k)

When S has precisely two elements it is useful to regard the problem of whether VW (S, k) holds as a graph coloring problem. Let S = {c, d} with c < d and let 𝔊(S) be the graph whose vertex set is ℕ and edge set is {{a(c+b), a(d+b)} | a > 0, b ≥ 0}. Then VW (S, k) holds if and only if 𝔊(S) is not k-colorable. If 𝔊(S) is not k-colorable, then M(S, k) is the least integer M such that 𝔊(S) restricted to {0, 1, …, M} is not k-colorable.

The following proposition, conjectured after a cursory examination of the table, is quite easy to show.

Proposition 2.1 Let c < d be nonnegative integers. Then M({c, d}, 2) = 2d.

Proof. 𝔊(S) restricted to {0, 1, …, 2d} is not 2-colorable because it contains a triangle consisting of the edges {c, d} + c, {c, d} + d and 2{c, d}.

On the other hand, 𝔊(S) restricted to {0, 1, …, 2d − 1} is 2-colorable. The only edges in this graph are of the form {c, d} + b, where 0 ≤ b ≤ d − 1. Let l = d − c. Color a vertex i with color 0 if ⌊i/l⌋ is even, and with color 1 otherwise. Since the only vertices that i might possibly be adjacent to are i − l and i + l, no two adjacent vertices have the same color. □

We now show that the variant van der Waerden property holds for two-element sets.

Theorem 2.2 Let |S| = 2. Then VW (S, k) holds for all k > 0.

Proof. By the remarks above, it is enough to show that 𝔊(S) is not k-colorable. It is easier to show something a little stronger. Let 𝔊_{n}(S) be the graph whose vertex set is ℕ and edge set is {{a(c + b), a(d + b)} | n ≥ a > 0, b ≥ 0}. Clearly, the edge set of 𝔊(S) is the union of the edge sets of the graphs 𝔊_{n}(S). We will show that for every S and k, there is an n = n(S, k) such that 𝔊_{n}(S) contains a (k + 1)-clique. Thus, 𝔊(S) contains a (k + 1)-clique and therefore is not k-colorable.

First, we show by induction on k that for each k there is an n such that 𝔊_{n}({0, 1}) contains a k-clique whose vertices are all less than or equal to n. The case k = 1 is trivial. If k = 2 then we may take n = 1. Observe that for each n, 𝔊_{n}({0, 1}) is periodic in the following sense. Let p(n) = lcm{1, 2, …, n}. Consider any edge a({0, 1} + b) in 𝔊_{n}({0, 1}). Since a ≤ n, p is a multiple of a, say p = aq. Then a({0, 1} + b) + p = a({0, 1} + b + q) is also an edge in 𝔊_{n}({0, 1}). Thus, if 𝔊_{n}({0, 1}) contains a k-clique whose vertices are all ≤ n, then by periodicity, it also contains a k-clique whose vertices are all ≥ p(n) and ≤ n + p(n). Let n′ = n + p(n). Then 𝔊_{n′}({0, 1}) contains a k-clique whose vertices are all ≥ p(n) and ≤ n + p(n) and, furthermore, contains an edge from 0 to each one of the vertices in this k-clique. That is, 𝔊_{n′}({0, 1}) contains a (k + 1)-clique all of whose vertices are ≤ n′.

Now we consider the case where S is an arbitrary two-element set. Let S = {c, d} where c < d. We have seen that for a given k there is an n such that 𝔊_{n}({0, 1}) contains a k-clique. We will show that 𝔊_{n}(S) also contains a k-clique by describing an embedding of 𝔊_{n}({0, 1}) into 𝔊_{n}(S). Let l = d − c and define h : ℕ → ℕ by h(x) = lx + cp(n) (where p(n) is as above). Consider any edge a({0, 1} + b) in 𝔊_{n}({0, 1}). As before, p = p(n) is a multiple of a so we may write p = aq. Thus, h maps a({0, 1} + b) to la({0, 1} + b) + acq = a{cq + lb, cq + lb + l}. We know that q ≥ 1 so setting b′ = cq + lb − c, we see that b′ ≥ 0, cq + lb = c + b′ and cq + lb + l = d + b′. The image of the edge a({0, 1} + b) under h is therefore a(S + b′), an edge in 𝔊_{n}(S). □

S  M(S, 2)  S  M(S, 2)
{0,1,2}  {2,4,5}  20
{0,1,3}  12  {3,4,5}
{0,2,3}  12  {0,1,6}  36
{1,2,3}  {0,2,6}  24
{0,1,4}  22  {1,2,6}
{0,2,4}  {0,3,6}  24
{1,2,4}  18  {1,3,6}  28
{0,3,4}  20  {2,3,6}  30
{1,3,4}  20  {0,4,6}  24
{2,3,4}  {1,4,6}  32
{0,1,5}  {2,4,6}
{0,2,5}  24  {3,4,6}  24
{1,2,5}  22  {0,5,6}  32
{0,3,5}  24  {1.5.6}
{1,3,5}  {2,5,6}  30
{2,3,5}  24  {3,5,6}  24
{0,4,5}  {4,5,6}
{1,4,5}  22

Figure 2: Some values of M(S, 2)

The results in Figure 2 give the values of M(S, 2) for some three-element sets S. The program ran out of space on all the entries where no value of M(S, 2) is given. Notice that in all these cases, the elements of S represent three distinct congruence classes modulo 3. We give a partial explanation for this in the next section.

Theorem 2.3 For every finite S ⊆ ℕ and k, there is an n = n(S, k) such that VW (nS, k) holds.

Proof. By the compactness property of the classical van der Waerden Theorem, for every S and k, there is an m such that for any k-coloring of {0, 1, …, m}, there are a > 0 and b ≥ 0 with aS + b monochromatic; in particular, a ≤ m and b ≤ m. Let n = lcm{1, 2, …, m}. Consider any k-coloring α of {0, 1, …, mn}. Define a kcoloring β on {0, 1, …, m} by β(i) = α(ni). Thus, there are a and b, with 0 < a ≤ m and 0 ≤ b ≤ m, such that aS + b is monochromatic with respect to β. Therefore, anS + bn is monochromatic with respect to α. But n is divisible by a, say n = ac, so a(nS + bc) is monochromatic with respect to α. □

3 Negative Instances and Thue-Morse Sequences

As we noted, the sets for the empty entries in Figure 2 consist of integers representing three distinct congruence classes modulo 3. We can show that VW (S, 2) does not hold when elements of S represent three distinct congruence classes modulo 3. (We do not know if the converse holds.) The proof of this result will serve as a model for proofs of more general results.

Suppose we run the program described in the previous section with S = {0, 1, 2} and k = 2. The program does not verify that VW (S, k) holds; instead, when it exhausts the space that has been allocated to it (160 integers) it outputs the first 81 colors of the last coloring in its search:

001001101001001101101001101 001001101001001101101001101 101001101001001101101001101

There is a pattern here! Let σ_{i} be the i-th color in this sequence (beginning with σ_{0} and ending with σ_{80}). If i ≡ 1(mod 3), then σ_{i} = 0. If i ≡ 2(mod 3), then σ_{i} = 1. For all i < 27, σ_{i} = σ_{3i}. These rules together with the initial value σ_{0} = 0 determine the sequence uniquely and allow us to continue it indefinitely. There is a more succinct way to express this sequence as a Thue-Morse sequence.

We will consider a simple mathematical system (sometimes called a D0L system [22]) consisting of a finite alphabet Σ, a mapping T : Σ → Σ^{∗}, and a word w ∈ Σ^{∗}. Here Σ^{∗} is the set of words over Σ. We assume, for simplicity, that Σ is a set of integers {0, 1, …, k − 1}; the natural order on Σ gives a lexicographic order on Σ^{∗}. Rather than T (i) = α, we usually state a rewrite rule i → α.

We may extend T to a mapping T : Σ^{∗} → Σ^{∗} by taking

T (α_{0}α_{1} ⋯ α_{l−1}) = T (α_{0})T (α_{1}) ⋯ T (α_{l−1}).

for symbols α_{0}, …, α_{l−1} ∈ Σ. Similarly, we can extend T to a mapping on infinite words over Σ. The study of L systems concerns iterations of T applied to w. If w is a single symbol, say 0, and each i ∈ Σ is the initial symbol of T (i), then T^{n}(0) is a prefix of T^{n+1}(0) and each of the words 0, T (0), T^{2}(0), T^{3}(0), … is a prefix of some (possibly infinite) limit word σ, called the Thue-Morse sequence for (Σ, T, 0). This is the least word in lexicographic order such that T (σ) = σ. To specify a Thue-Morse word, it suffices to list the rewrite rules for T, since we take w = 0.

The famous sequence of Thue [25, 24] and Morse [19, 20] is generated by the rewrite rules 0 → 01 and 1 → 10. It begins

01101001100101101001100101100110 ⋯

and has many interesting combinatorial properties [2].

The sequence at the beginning of this section is generated by the rewrite rules 0 → 001 and 1 → 101. This sequence is indeed a counterexample to VW ({0, 1, 2}, 2), as can be seen from the proof of the following theorem.

Theorem 3.1 Let p be a prime and k ≥ 2. Take r = ⌈(p−1)/k⌉+2. If S is a subset of ℕ whose elements represent at least r distinct congruence classes modulo p, then VW (S, k) does not hold.

Proof. Let s = r − 2 = ⌈(p − 1)/k⌉, t = ⌊(p − 1)/k⌋, and j be the remainder when p − 1 is divided by k. Thus, p − 1 = js + (k − j)t. Consider the rewrite rules

i → i 0^{s} 1^{s} ⋯ (j − 1)^{s} j^{t} (j + 1)^{t} ⋯ (k − 1)^{t}

for i = 0, 1, …, k − 1. Let σ = σ_{0}σ_{1}σ_{2} ⋯ be the associated Thue-Morse sequence.We show that no set of the form a(S + b) is monochromatic with respect to σ.

The value of σ_{i} is determined by its congruence class modulo p, unless i ≡ 0(mod p). No set representing at least r = s + 2 distinct congruence classes can be monochromatic because at most one of its elements is congruent to 0 modulo p, and its other elements represent at least s + 1 congruence classes.

Proceed by contradiction, taking a(S +b) to be a minimal monochromatic set (i.e., its largest element is minimal). If a is divisible by p, (a/p)(S + b) would be a smaller monochromatic set, a contradiction. If a is not divisible by p, then the elements of a(S + b) represent at least r distinct congruence classes modulo p, and hence a(S + b) is not monochromatic. Once more we arrive at a contradiction. □

We will improve this result presently. However, it is already strong enough to show an important result concerning the variant van der Waerden property.

Corollary 3.2 If |S| ≥ 3, there is a k such that VW (S, k) fails.

Proof. Let p be a prime larger than the greatest element of S. Thus, every element of S represents a distinct congruence class modulo p. Take k large enough that |S| ≥ ⌈(p − 1)/k⌉ + 2. □

When k is reasonably large compared to p, Theorem 3.1 gives very good results with respect to the Thue-Morse sequence. When p is large compared to k, we can obtain better bounds using the probabilistic method (see Alon and Spencer [1]).

Theorem 3.3 Let p be a prime and k ≥ 2. Take r = ⌈log_{k}(p^{2} − p)⌉ + 2. If S is a subset of ℕ whose elements represent at least r distinct congruence classes modulo p, then VW (S, k) does not hold.

Proof. In the proof of Theorem 3.1, the rewrite rules are of the form i → i α, where α is a particular word of length p − 1. The only property of α used in the proof can be stated as follows.

If α is regarded as a k-coloring of {1, 2, …, p − 1}, then no set of the form a(S + b)(mod p) with a ≢ 0 (mod p) is monochromatic.

Here T (mod p) indicates the set formed by replacing every t ∈ T with an integer t′ ≡ t (mod p), where 0 ≤ t′ < p. (If a(S + b)(mod p) happens to contain 0, it is considered monochromatic if all its nonzero elements have the same color.) If we can show under the hypotheses of the present theorem that such an α exists, we are done.

Consider a probability space consisting of all k-colorings α of the set {1, 2, …, p− 1} with the uniform probability measure. Define the random variable X(α) on this space to be the number of pairs (a, b) such that 1 ≤ a < p, 0 ≤ b < p, and a(S + b)(mod p) is monochromatic with respect to α. Now let us estimate E[X], the expectation of X. We may write X as a sum X = ∑_{a,b} X_{a,b} where

X_{a,b}(α) = \{ \begin{matrix}1, & if a(S + b)(mod p) is monochromatic with respect to α; \\ 0, & otherwise. \end{matrix}

This sum is taken over the range 1 ≤ a < p, 0 ≤ b < p. By linearity of expectation we have that E[X] = ∑_{a,b} E[X_{a,b}]. Now for fixed values of a and b, a(S + b)(mod p) contains at least r − 1 nonzero elements. There are k ways to color them monochromatically, so E[X_{a,b}] ≤ k/k^{r−1} = 1/k^{r−2}. Thus, E[X] ≤ p(p − 1)/k^{r−2}. Since r > log_{k}(p^{2}−p)+2, we have E[X] < 1. We see that X is a nonnegative integer-valued random variable with expectation less than 1. Therefore, for some α, X(α) = 0. This is the coloring we seek. □

4 Final Questions

Many questions remain. Here are a few questions suggested by the results of this paper.

1. Is it the case that VW (S, k) holds if and only if for every prime p, every kcoloring of {1, 2, …, p − 1}, every a > 0, and every b ≥ 0, a(S + b)(mod p) is monochromatic?

2. Is it true that whenever VW (S, k) fails, there is a Thue-Morse sequence α over the k-symbol alphabet such that no set of the form a(S + b) is monochromatic with respect to α?

3. Is there a reason that the 2-coloring turned up by our computer search on S = {0, 1, 2} and k = 2 happens to be the initial part of a simple Thue-Morse sequence? In particular, if the program continued (with additional space added as needed), would it continue to generate the Thue-Morse sequence? The computer generated 2-coloring is the first counterexample (under lexicographic ordering) to the variant van der Waerden property. We conjecture that for all S and k where the variant van der Waerden property fails, the first counterexample coloring is a Thue-Morse sequence. Readers interested in doing computer experiments to gain insight into this problem might first check to see how long it takes for the color of the integer 17 to stabilize during the search for a counterexample when S = {0, 1, 2} and k = 2. This will give some idea of the subtleties of the problem.

4. We see from Corollary 3.2 and Theorem 2.3 that the variant van der Waerden property is affected both by dilation of S and number of colors. For a given S with at least three elements, define F_{S}(n) to be the least k ≥ 1 such that VW (nS, k) fails. It follows that F_{S}(n) is unbounded. However, it is not monotone in general. What can we say about the behavior of the function F_{S}(n)?

5. Fix k ≥ 2. Is there an infinite set T_{k} such that for each finite S ⊆ T_{k}, VW (S, k) holds? A possibility for T_{2} might be {2, 2·3, 2·3·5, 2·3·5·7, 2·3·5·7·11, …}.

6. Characterize the S and k for which VW (S, k) holds.

References

[1] N. Alon and J. H. Spencer. The Probabilistic Method. Wiley, New York, 1991.

[2] J. Berstel and C. Reutenauer. Square-free words and idempotent semigroups. In M. Lothaire, editor, Combinatorics on Words, pages 18–38. Addison-Wesley, Reading, MA, 1983.

[3] T. C. Brown and B. M. Landman. The Ramsey property for collections of sequences not containing all arithmetic progressions. Graphs Combin., 12(2):149– 161, 1996.

[4] T. C. Brown, B. M. Landman, and M. Mishna. Monochromatic homothetic copies of {1, 1 + s, 1 + s + t}. Canad. Math. Bull., 40(2):149–157, 1997.

[5] H. Furstenberg. Recurrence in Ergodic Theory and Combinatorial Number Theory. Princeton University Press, Princeton, 1981.

[6] R. L. Graham, B. L. Rothschild, and J. H. Spencer. Ramsey Theory. Addison-Wesley, Reading, MA, second edition, 1990.

[7] R. N. Greenwell and B. M. Landman. On the existence of a reasonable upper bound for the van der Waerden numbers. J. Combin. Theory Ser. A, 50(1):82–86, 1989.

[8] B. M. Landman. Generalized van der Waerden numbers. Graphs Combin., 2(4):351–356, 1986.

[9] B. M. Landman. Ramsey functions related to the van der Waerden numbers. Discrete Math., 102(3):265–278, 1992.

[10] B. M. Landman. An upper bound for van der Waerden-like numbers using k colors. Graphs Combin., 9(2):177–184, 1993.

[11] B. M. Landman. Ramsey functions associated with second order recurrences. J. Combin. Math. Combin. Comput., 15:119–127, 1994.

[12] B. M. Landman. Avoiding arithmetic progressions (mod m) and arithmetic progressions. Util. Math., 52:173–182, 1997.

[13] B. M. Landman. Monochromatic sequences whose gaps belong to {d, 2d, ⋯, md}. Bull. Austral. Math. Soc., 58(1):93–101, 1998.

[14] B. M. Landman. Ramsey functions for quasi-progressions. Graphs Combin., 14(2):131–142, 1998.

[15] B. M. Landman and R. N. Greenwell. Values and bounds for Ramsey numbers associated with polynomial iteration. Discrete Math., 68(1):77–83, 1988.

[16] B. M. Landman and R. N. Greenwell. Some new bounds and values for van der Waerden-like numbers. Graphs Combin., 6(3):287–291, 1990.

[17] B. M. Landman and A. F. Long. Ramsey functions for sequences with adjacent differences in a specified congruence class. In Proceedings of the Twenty-fifth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1994), volume 103, pages 3–20, 1994.

[18] B. M. Landman and B. Wysocka. Collections of sequences having the Ramsey property only for few colours. Bull. Austral. Math. Soc., 55(1):19–28, 1997.

[19] M. Morse. Recurrent geodesics on a surface of negative curvature. Trans. Amer. Math. Soc., 22:84–100, 1921.

[20] M. Morse. A solution of the problem of infinite play in chess. Bull. Amer. Math. Soc., 44:632, 1938.

[21] J.-E. Pin. Van der Waerden’s theorem. In M. Lothaire, editor, Combinatorics on Words, pages 39–54. Addison-Wesley, Reading, MA, 1983.

[22] A. Salomaa. Computation and automata. Cambridge University Press, Cambridge, 1985. With a foreword by Grzegorz Rozenberg.

[23] S. Shelah. Primitive recursive bounds for van der Waerden numbers. J. Amer. Math. Soc., 1:683–697, 1988.

[24] A. Thue. Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. In T. Nagell, A. Selberg, S. Selberg, and K. Thalberg, editors, Selected Mathematical Papers of Axel Thue, pages 413–477. Universitetsforlaget, Oslo, 1977.

[25] A. Thue. Über unendliche Zeichenreihen. In T. Nagell, A. Selberg, S. Selberg, and K. Thalberg, editors, Selected Mathematical Papers of Axel Thue, pages 139–158. Universitetsforlaget, Oslo, 1977.

[26] B. L. van der Waerden. Beweis einer Baudet’schen Vermutung. Nieuw Arch. Wisk., 15:212–216, 1927.