\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
\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_1m$. 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}