AN APPLICATION OF VAN DER WAERDEN’S THEOREM IN ADDITIVE NUMBER THEORY

Lorenz Halbeisen^{1}

Department of Mathematics, University of California at Berkeley, Berkeley, CA 94720, USA

                           halbeis@math.berkeley.edu

Norbert Hungerbühler

Department of Mathematics, University of Alabama at Birmingham, Birmingham, AL 35294, USA

                              buhler@math.uab.edu

Received: 6/8/00, Revised: 6/28/00, Accepted: 7/1/00, Published: 7/12/00

Abstract

A sequence on a finite set of symbols is called strongly non-repetitive if no two adjacent (finite) segments are permutations of each other. Replacing the finite set of symbols of a strongly non-repetitive sequence by different prime numbers, one gets an infinite sequence on a finite set of integers such that no two adjacent segments have the same product. It is known that there are infinite strongly non-repetitive sequences on just four symbols. The aim of this paper is to show that there is no infinite sequence on a finite set of integers such that no two adjacent segments have the same sum. Thus, in the statement above, one cannot replace “product” by “sum”. Further we suggest some strengthened versions of the notion of strongly non-repetitive.

0. Introduction

A finite set of one or more consecutive terms in a sequence is called a segment of the sequence. A sequence on a finite set of symbols is called non-repetitive if no two adjacent segments are identical, where adjacent means abutting but not overlapping. It is known that there are infinite non-repetitive sequences on three symbols (see [Ple 70]), and on the other hand, it is obvious that a non-repetitive sequence on two symbols is at most of length 3. Paul Erdős has raised in [Erd 61] the question of the maximum length of a sequence on k symbols, such that no two adjacent segments are permutations of each other. Such a sequence is called strongly non-repetitive. Veikko Keränen has shown that four symbols are enough to construct an infinite strongly non-repetitive sequence (see [Ker 92]). Replacing the finite set of symbols of an infinite strongly non-repetitive sequence by different prime numbers, one gets an infinite sequence on a finite set of integers such that no two adjacent segments have the same product.

It is natural to ask whether one can replace in the statement above “product” by “sum”.

1Supported by the Swiss National Science Foundation.

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 0 (2000), #A07 2

This leads to the following question: Is it possible to construct an infinite sequence on a finite set of integers such that no two adjacent segments have the same sum?

In the next section we will see that such a sequence does not exist. Moreover, in any infinite sequence on a finite set of integers we always find arbitrary large finite sets of adjacent segments, such that all these segments have the same sum.

1. An application of van der Waerden’s Theorem

Let Z denote the set of integers and let N denote the set of non-negative integers. The theorem of van der Waerden states as follows (cf. [vdW 27]):

Van der Waerden’s Theorem. For any coloring of N with finitely many colors, and for each l ∈ N, there is a monochromatic arithmetic progression of length l.

Before we state the main result of this paper, we introduce some notation.

Let S = ⟨a_{1}, a_{2}, …, a_{i}, …⟩ be an infinite sequence of Z. By definition, a finite sequence of integers s is a segment of S, if and only if there is a positive i ∈ N such that s = ⟨a_{i}, a_{i+1}, …, a_{i+k}⟩, for some k ∈ N. A finite set s_{1}, s_{2}, …, s_{l} of segments of S is called a set of adjacent segments, if s_{j} and s_{j+1} are adjacent for each j with 1 ≤ j < l. For a segment s = ⟨a_{i}, …, a_{i+k}⟩ of S, let ∑ s := ∑_{j=0}^{k} a_{i+j}. A segment s of S of the form s = ⟨a_{1}, …, a_{k}⟩ is called the initial segment of length k of S. Let ∑(S) denote the infinite integer sequence ⟨t_{1}, t_{2}, …, t_{k}, …⟩, where t_{k} := ∑ s_{k} and s_{k} is the initial segment of length k of S. We call ∑(S) the series of S.

The main result of this paper is the following:

Theorem. If S_{M} is an infinite sequence of some non-empty finite set M ⊆ N, then for each positive l ∈ N there is a set s_{1}, s_{2}, …, s_{l} of adjacent segments of S_{M}, such that

∑ s_{1} = ∑ s_{2} = … = ∑ s_{l} .

Proof. Without loss of generality we may assume that 0 ∉ M. Thus, the series of S_{M}, ∑(S_{M}) = ⟨t_{1}, t_{2}, …, t_{i}, …⟩, is strictly increasing and hence an unbounded sequence of N. Define the coloring π of N as follows:

π(n) is the least non-negative integer h such that n + h = t_{j}, for some j.

Because M is finite, it has a biggest element, and therefore, since the series of S_{M} is unbounded, the coloring π is a well-defined finite coloring of N. Now, by van der Waerden’s Theorem, for each l ∈ N, there is a monochromatic arithmetic progression of length l. Let n_{1} < n_{2} < … < n_{l+1} be such a monochromatic arithmetic progression with increment d. Since n_{1}, n_{2}, …, n_{l+1} is monochromatic, there is an h such that π(n_{i}) = h (for 1 ≤ i ≤ l + 1). This implies that for each 1 ≤ i ≤ l + 1 there is a j_{i} such that n_{i} + h = t_{j_{i}}, and since the series of S_{M} is strictly increasing, we have j_{i} < j_{i+1} (for 1 ≤ i ≤ l). Hence, for S_{M} = ⟨a_{1}, a_{2}, …, a_{i}, …⟩, we get

∑_{i=j_{1}+1}^{j_{2}} a_{i} = ∑_{i=j_{2}+1}^{j_{3}} a_{i} = … ∑_{i=j_{l}+1}^{j_{l+1}} a_{i} = d .

Thus, we find a set of size l of adjacent segments of S_{M} such that all these segments have the same sum, which completes the proof of the Theorem.

Using a modification of the arguments above we can prove the following:

Corollary. If S_{M} is an infinite sequence of some non-empty finite set M ⊆ Z, then for each positive l ∈ N there is a set s_{1}, s_{2}, …, s_{l} of adjacent segments of S_{M}, such that

∑ s_{1} = ∑ s_{2} = … = ∑ s_{l} .

Proof. Let S_{M} = ⟨a_{1}, a_{2}, …, a_{i}, …⟩. If the series of S_{M} has a lower and an upper bound, then we find an infinite set J ⊆ N and an integer c, such that for each j ∈ J, t_{j} = c. Hence, for any j, j′ ∈ J with j < j′ we get ∑_{i=j+1}^{j′} a_{i} = 0, which completes the proof of the “bounded” case. On the other hand, if the series of S_{M} does not have a lower bound, then the series of −S_{M}, where −S_{M} = ⟨−a_{1}, −a_{2}, …, −a_{i}, …⟩, does not have an upper bound. Thus, without loss of generality, we may assume that the series of S_{M} does not have an upper bound, which implies that ∑(S_{M}) = ⟨t_{1}, t_{2}, …, t_{i}, …⟩ does not have a maximal element. Now, let ⟨τ_{1}, τ_{2}, …, τ_{j}, …⟩ be the strictly increasing subsequence of ∑(S_{M}) such that τ_{j} = t_{μ(j)}, where μ(j) = min{i : t_{i} > τ_{j−1}} with τ_{0} := −1. Define the coloring π of N by stipulating

π(n) is the least non-negative integer h such that n + h = τ_{j}, for some j.

Again by van der Waerden’s Theorem, for each l ∈ N there is a monochromatic arithmetic progression n_{1} < n_{2} < … < n_{l+1} of length l. Let j_{i} be such that n_{i} + π(n_{i}) = τ_{j_{i}} = t_{μ(j_{i})}, then, as in the proof of the Theorem, we get

∑_{i=μ(j_{1})+1}^{μ(j_{2})} a_{i} = ∑_{i=μ(j_{2})+1}^{μ(j_{3})} a_{i} = … ∑_{i=μ(j_{l})+1}^{μ(j_{l+1})} a_{i} ,

which completes the proof of the “unbounded” case.

2. Stronger versions of “strongly non-repetitive”

One can strengthen the notion of strongly non-repetitive in different directions. For example, one can consider more than two adjacent segments, or one can restrict the set of patterns which may appear in the sequence.

2.1. More than two adjacent segments

A sequence on k symbols is called a (k; n, m)-sequence if, and only if, in any set of n adjacent segments of the same length we find no m segments which are permutations of each other. Further, let η(k; n, m) denote the maximum length of a (k; n, m)-sequence. If there are (k; n, m)- sequences of any length (for fixed k, n, m), then, by König’s Lemma, there is an infinite (k; n, m)- sequence and we stipulate η(k; n, m) = ∞.

First we consider the case when n = m. It is easy to see that each (k; n, n)-sequence is also a (k + r; n − s, n − s)-sequence, where r, s ∈ N. Michel Dekking showed in [Dek 79] that η(2; 4, 4) = η(3; 3, 3) = ∞, and, as mentioned above, Veikko Keränen showed in [Ker 92] that η(4; 2, 2) = ∞. On the other hand, concerning the non-trivial cases, it is not hard to check that η(2; 3, 3) = 9, η(3; 2, 2) = 7 and η(2; 2, 2) = 3. Thus, all the values of η(k; n, n) are determined.

With the help of PROLOG, we investigated some of the cases where n > m. For example we know that η(5; 5, 2) = 24, η(3; 5, 3) = 38, η(2; 5, 4) = 49, η(5; 4, 2) = 16 and η(4; 3, 2) = 13. Further, with the results for n = m, it is easy to see that η(4; 5, 4) = η(4; 4, 3) = ∞. On the other hand, we found long (3; 4, 3) and (4; 5, 3)-sequences, respectively. So, also η(3; 4, 3) and η(4; 5, 3) might be infinite.

2.2. Restricted versions

Let us now restrict the set of patterns which may appear in the non-repetitive sequence.

If a symbol appears in a sequence twice in a row, then we call it a simple repetition. A sequence on k symbols is called a (k; n, m)^{∗}-sequence if it is a (k; n, m)-sequence without simple repetitions. Again with the help of PROLOG, we know that the maximum length of a (3; 4, 3)^{∗}-sequence is 55. An example of a (3; 4, 3)^{∗}-sequence of length 55 is given by ⟨a, b, a, b, a, c, a, c, a, b, a, b, c, b, c, b, a, b, a, c, a, c, a, b, a, b, c, b, c, b, a, b, a, c, a, c, a, b, a, b, c, b, c, b, a, b, a, c, a, c, a, b, a, b, a⟩.

Another restriction on the set of patterns which may appear in the sequence is given by the following example. Let S be a sequence on four symbols, say a, b, c, d. We say that S is separating the symbols a and b, if neither ⟨a, b⟩ nor ⟨b, a⟩ appears as a segment of S. Surprisingly, we found quite long abcd-sequences separating a and b, which are even (4; 2, 2)- sequences.

Finally, concerning the Theorem, we like to ask the following question: Is it possible to construct an infinite sequence on a finite set of integers such that no two adjacent segments of the same length have the same sum?

References

[Dek 79] F. Michel Dekking: Strongly non-repetitive sequences and progression-free sets, Journal of Combinatorial Theory (A) 27 (1979), 181–185.

[Erd 61] Paul Erdős: Some unsolved problems, Magyar Tudomanyos Akademia Matematikai Kutató Intezetenek Közlemenyei 6 (1961), 221–254.

[Ker 92] Veikko Keränen: Abelian squares are avoidable on 4 letters, Automata, languages and programming (Vienna, 1992), Lecture Notes in Computer Science 623, Springer-Ver-lag, Berlin · New York, 1992, pp. 41–52.

[Ple 70] Peter A. B. Pleasants: Non-repetitive sequences, Proceedings of the Cambridge Philosophical Society 68 (1970), 267–274.

[vdW 27] Bartel L. van der Waerden: Beweis einer Baudetschen Vermutung, Nieuw Archief voor Wiskunde 15 (1927), 212–216.