\documentclass[11pt]{article}
\textwidth= 6.25in
\textheight= 9.0in
\topmargin = -10pt
\evensidemargin=10pt
\oddsidemargin=10pt
\headsep=25pt
\parskip=10pt
\font\smallit=cmti10
\font\smalltt=cmtt10
\font\smallrm=cmr9

\begin{document}

\begin{center}
{\bf AN APPLICATION OF VAN DER WAERDEN'S THEOREM\\ IN ADDITIVE NUMBER
THEORY} \vskip 20pt {\bf Lorenz Halbeisen\footnote{Supported by the
{\it Swiss National Science Foundation.}}}\\ {\smallit Department of
Mathematics, University of California at Berkeley, Berkeley, CA
94720, USA}\\ {\tt halbeis@math.berkeley.edu}\\ \vskip 10pt {\bf
Norbert Hungerb\"uhler}\\ {\smallit Department of Mathematics,
University of Alabama at Birmingham, Birmingham, AL 35294, USA}\\
{\tt buhler@math.uab.edu}\\
\end{center}
\vskip 30pt
\centerline{\smallit Received:  6/8/00, Revised:  6/28/00,
Accepted:  7/1/00, Published:  7/12/00 }
\vskip 30pt

\centerline{\bf Abstract}

\noindent A sequence on a finite set of symbols is called {\it
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 {\it strongly non-repetitive}.

\pagestyle{myheadings} \markright{\smalltt INTEGERS: \smallrm
ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 0 (2000),
\#A07\hfill}

\thispagestyle{empty} \baselineskip=15pt \vskip 30pt

\section*{\normalsize 0. Introduction}

A finite set of one or more consecutive terms in a sequence is called
a {\bf segment} of the sequence. A sequence on a finite set of
symbols is called {\bf 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\H{o}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
{\it permutations\/} of each other. Such a sequence is called {\bf
strongly non-repetitive}. Veikko Ker\"anen 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''. 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.
 \vskip 30pt

\section*{\normalsize 1. An application of van der Waerden's Theorem}

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

\noindent
 {\bf Van der Waerden's Theorem.} For any coloring of {\bf N} with
finitely many colors, and for each $l\in\mbox{\bf 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=\langle a_1,a_2,\ldots,a_i,\ldots\rangle$ be an infinite
sequence of {\bf Z}. By definition, a finite sequence of integers $s$
is a segment of $S$, if and only if there is a positive
$i\in\mbox{\bf N}$ such that $s=\langle a_i,a_{i+1},
\ldots,a_{i+k}\rangle$, for some $k\in \mbox{\bf N}$. A finite set
$s_1,s_2,\ldots,s_l$ of segments of $S$ is called a {\bf set of
adjacent segments}, if $s_j$ and $s_{j+1}$ are adjacent for each $j$
with $1\le j<l$. For a segment $s=\langle a_i,\ldots,a_{i+k}\rangle$
of $S$, let $\sum s:= \sum_{j=0}^{k}a_{i+j}$. A segment $s$ of $S$ of
the form $s =\langle a_1,\ldots,a_{k} \rangle$ is called the {\bf
initial segment of length $k$ of $S$}. Let $\sum (S)$ denote the
infinite integer sequence $\langle t_1,t_2,\ldots,t_k,\ldots\rangle$,
where $t_k:=\sum s_k$ and $s_k$ is the initial segment of length $k$
of $S$. We call $\sum (S)$ the {\bf series of $S$}.

The main result of this paper is the following:

\noindent
 {\bf Theorem.} If $S_M$ is an infinite sequence of some non-empty
finite set $M\subseteq\mbox{\bf N}$, then for each positive
$l\in\mbox{\bf N}$ there is a set $s_1,s_2,\ldots,s_l$ of adjacent
segments of $S_M$, such that
 $$ \sum s_1 = \sum s_2 =\ldots = \sum s_l\,.$$

\noindent{\it Proof.} Without loss of generality we may assume that
$0\notin M$. Thus, the series of $S_M$, $\sum (S_M)= \langle
t_1,t_2,\ldots,t_i,\ldots\rangle$, is strictly increasing and hence
an unbounded sequence of {\bf N}. Define the coloring $\pi$ of {\bf
N} as follows:
 $$\pi(n)\mbox{ 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 $\pi$ is a
well-defined finite coloring of {\bf N}. Now, by van~der~Waerden's
Theorem, for each $l\in\mbox{\bf N}$, there is a monochromatic
arithmetic progression of length $l$. Let $n_1<n_2<\ldots<n_{l+1}$ be
such a monochromatic arithmetic progression with increment $d$. Since
$n_1,n_2,\ldots, n_{l+1}$ is monochromatic, there is an $h$ such that
$\pi(n_i)=h$ (for $1\le i\le l+1$). This implies that for each $1\le
i\le 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\le i\le l$). Hence, for $S_M=\langle
a_1,a_2,\ldots,a_i,\ldots\rangle$, we get
 $$ \sum_{i=j_1+1}^{j_2}a_i \;= \sum_{i=j_2+1}^{j_3}a_i \;= \ldots
    \sum_{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:

\noindent
 {\bf Corollary.} If $S_M$ is an infinite sequence of some non-empty
finite set $M\subseteq\mbox{\bf Z}$, then for each positive
$l\in\mbox{\bf N}$ there is a set $s_1,s_2,\ldots,s_l$ of adjacent
segments of $S_M$, such that
 $$ \sum s_1 = \sum s_2 =\ldots = \sum s_l\,.$$

\noindent{\it Proof.} Let $S_M=\langle
a_1,a_2,\ldots,a_i,\ldots\rangle$. If the series of $S_M$ has a lower
and an upper bound, then we find an infinite set $J\subseteq\mbox{\bf
N}$ and an integer $c$, such that for each $j\in J$, $t_j=c$. Hence,
for any $j,j' \in J$ with $j<j'$ we get $\sum_{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}=\langle
-a_1,-a_2,\ldots,-a_i,\ldots\rangle$, 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 $\sum (S_M)=
\langle t_1,t_2,\ldots,t_i,\ldots\rangle$ does not have a maximal
element. Now, let $\langle \tau_1,\tau_2,\ldots,\tau_j,\ldots\rangle$
be the strictly increasing subsequence of $\sum (S_M)$ such that
$\tau_{j}=t_{\mu(j)}$, where $\mu(j)=\mbox{min}\{i:t_i >
\tau_{j-1}\}$ with $\tau_0:=-1$. Define the coloring $\pi$ of {\bf N}
by stipulating
 $$\pi(n)\mbox{ is the least non-negative integer $h$ such that $n+h=\tau_j$,
 for some $j$.}$$
Again by van~der~Waerden's Theorem, for each $l\in\mbox{\bf N}$ there
is a monochromatic arithmetic progression $n_1<n_2<\ldots<n_{l+1}$ of
length $l$. Let $j_i$ be such that $n_i+\pi(n_i) =
\tau_{j_i}=t_{\mu(j_i)}$, then, as in the proof of the Theorem, we
get
 $$ \sum_{i=\mu(j_1)+1}^{\mu(j_2)}a_i \;=
    \sum_{i=\mu(j_2)+1}^{\mu(j_3)}a_i \;= \ldots
    \sum_{i=\mu(j_l)+1}^{\mu(j_{l+1})}a_i\,,$$
which completes the proof of the ``unbounded'' case.
 \vskip 30pt

\section*{\normalsize 2. Stronger versions of ``strongly non-repetitive''}

One can strengthen the notion of {\it 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.

\subsection*{\normalsize 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
$\eta(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\"onig's Lemma, there is an infinite $(k;n,m)$-sequence and
we stipulate $\eta(k;n,m)=\infty$.

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\in
\mbox{\bf N}$. Michel Dekking showed in [Dek\,79] that $\eta(2;4,4)=
\eta(3;3,3)=\infty$, and, as mentioned above, Veikko Ker\"anen showed
in [Ker\,92] that $\eta(4;2,2)=\infty$. On the other hand, concerning
the non-trivial cases, it is not hard to check that $\eta(2;3,3)=9$,
$\eta(3;2,2)=7$ and $\eta(2;2,2)=3$. Thus, all the values of
$\eta(k;n,n)$ are determined.

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

\subsection*{\normalsize 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
{\bf 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
 $\langle${\it 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}$\rangle$.

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 {\bf separating} the
symbols $a$ and $b$, if neither $\langle a,b\rangle$ nor $\langle
b,a\rangle$ 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 {\it
same length\/} have the same sum?
 \vskip 30pt

\section*{\normalsize References}

 [Dek\,79] {\sc F.~Michel~Dekking:}
     {Strongly non-repetitive sequences and progression-free sets},
     {\it Journal of Combinatorial Theory (A)\/}
     {\bf 27}
     {(1979),}
     {181--185.}

\noindent
 [Erd\,61] {\sc Paul~Erd\H{o}s:}
     {Some unsolved problems},
     {\it Magyar Tudomanyos Akademia Matematikai Kutat\'o Intezetenek
      K\"ozlemenyei\/}
     {\bf 6}
     {(1961),}
     {221--254.}

 \noindent
 [Ker\,92] {\sc Veikko Ker\"anen:}
     {Abelian squares are avoidable on 4 letters},
     {\it Automata, languages and programming (Vienna, 1992)\/},
     {\tt Lecture Notes in Computer Science 623},
     {Springer-Ver\-lag},
     {Berlin\,$\cdot$\,New York},
     {1992},
     {pp.\,41--52.}

\noindent
 [Ple\,70] {\sc Peter~A.~B.~Pleasants:}
     {Non-repetitive sequences},
     {\it Proceedings of the Cambridge Philosophical Society\/}
     {\bf 68}
     {(1970),}
     {267--274.}

\noindent
 [vdW\,27] {\sc Bartel~L.~van\,der\,Waerden:}
     {Beweis einer Baudetschen Vermutung},
     {\it Nieuw Archief voor Wiskunde\/}
     {\bf 15}
     {(1927),}
     {212--216.}

\end{document}