\input amstex
\input amsppt.sty

\nologo

\magnification1200
\hsize13cm
\vsize19cm

\def\Z{\Bbb Z}
\def\N{\Bbb N}
\def\al{\alpha}
\def\be{\beta}
\def\Om{\Omega}
\def\om{\omega}
\def\ph{\varphi}
\def\F{\Cal F}
\def\Nr{\operatorname{Nr}}

\catcode`\@=11
\def\dddot#1{\vbox{\ialign{##\crcr
      .\hskip-.5pt.\hskip-.5pt.\crcr\noalign{\kern1.5\p@\nointerlineskip}
      $\hfil\displaystyle{#1}\hfil$\crcr}}}

\newif\iftab@\tab@false
\newif\ifvtab@\vtab@false
\def\tab{\bgroup\tab@true\vtab@false\vst@bfalse\Strich@false%
   \def\\{\global\hline@@false%
     \ifhline@\global\hline@false\global\hline@@true\fi\cr}
   \edef\l@{\the\leftskip}\ialign\bgroup\hskip\l@##\hfil&&##\hfil\cr}
\def\endtab{\cr\egroup\egroup}
\def\vtab{\vtop\bgroup\vst@bfalse\vtab@true\tab@true\Strich@false%
   \bgroup\def\\{\cr}\ialign\bgroup&##\hfil\cr}
\def\endvtab{\cr\egroup\egroup\egroup}
\def\stab{\D@cke0.5pt\null 
 \bgroup\tab@true\vtab@false\vst@bfalse\Strich@true\Let@@\vspace@
 \normalbaselines\offinterlineskip
  \openup\spreadmlines@
 \edef\l@{\the\leftskip}\ialign
 \bgroup\hskip\l@##\hfil&&##\hfil\crcr}
\def\endstab{\crcr\egroup
 \egroup}
\newif\ifvst@b\vst@bfalse
\def\vstab{\D@cke0.5pt\null
 \vtop\bgroup\tab@true\vtab@false\vst@btrue\Strich@true\bgroup\Let@@\vspace@
 \normalbaselines\offinterlineskip
  \openup\spreadmlines@\bgroup}
\def\endvstab{\crcr\egroup\egroup
 \egroup\tab@false\Strich@false}

\newdimen\htstrut@
\htstrut@8.5\p@
\newdimen\htStrut@
\htStrut@12\p@
\newdimen\dpstrut@
\dpstrut@3.5\p@
\newdimen\dpStrut@
\dpStrut@3.5\p@
\def\openup{\afterassignment\@penup\dimen@=}
\def\@penup{\advance\lineskip\dimen@
  \advance\baselineskip\dimen@
  \advance\lineskiplimit\dimen@
  \divide\dimen@ by2
  \advance\htstrut@\dimen@
  \advance\htStrut@\dimen@
  \advance\dpstrut@\dimen@
  \advance\dpStrut@\dimen@}
\def\Let@@{\relax\iffalse{\fi%
    \def\\{\global\hline@@false%
     \ifhline@\global\hline@false\global\hline@@true\fi\cr}%
    \iffalse}\fi}
\def\matrix{\null\,\vcenter\bgroup
 \tab@false\vtab@false\vst@bfalse\Strich@false\Let@@\vspace@
 \normalbaselines\openup\spreadmlines@\ialign
 \bgroup\hfil$\m@th##$\hfil&&\quad\hfil$\m@th##$\hfil\crcr
 \Mathstrut@\crcr\noalign{\kern-\baselineskip}}
\def\endmatrix{\crcr\Mathstrut@\crcr\noalign{\kern-\baselineskip}\egroup
 \egroup\,}
\def\smatrix{\D@cke0.5pt\null\,
 \vcenter\bgroup\tab@false\vtab@false\vst@bfalse\Strich@true\Let@@\vspace@
 \normalbaselines\offinterlineskip
  \openup\spreadmlines@\ialign
 \bgroup\hfil$\m@th##$\hfil&&\quad\hfil$\m@th##$\hfil\crcr}
\def\endsmatrix{\crcr\egroup
 \egroup\,\Strich@false}
\newdimen\D@cke
\def\Dicke#1{\global\D@cke#1}
\newtoks\tabs@\tabs@{&}
\newif\ifStrich@\Strich@false
\newif\iff@rst

\def\Stricherr@{\iftab@\ifvtab@\errmessage{\noexpand\s not allowed
     here. Use \noexpand\vstab!}%
  \else\errmessage{\noexpand\s not allowed here. Use \noexpand\stab!}%
  \fi\else\errmessage{\noexpand\s not allowed
     here. Use \noexpand\smatrix!}\fi}
\def\format{\ifvst@b\else\crcr\fi\egroup\iffalse{\fi\ifnum`}=0 \fi\format@}
\def\format@#1\\{\def\preamble@{#1}%
 \def\Str@chfehlt##1{\ifx##1\s\Stricherr@\fi\ifx##1\\\let\Next\relax%
   \else\let\Next\Str@chfehlt\fi\Next}%
 \def\c{\hfil\noexpand\ifhline@@\hbox{\vrule height\htStrut@%
   depth\dpstrut@ width\z@}\noexpand\fi%
   \ifStrich@\hbox{\vrule height\htstrut@ depth\dpstrut@ width\z@}%
   \fi\iftab@\else$\m@th\fi\the\hashtoks@\iftab@\else$\fi\hfil}%
 \def\r{\hfil\noexpand\ifhline@@\hbox{\vrule height\htStrut@%
   depth\dpstrut@ width\z@}\noexpand\fi%
   \ifStrich@\hbox{\vrule height\htstrut@ depth\dpstrut@ width\z@}%
   \fi\iftab@\else$\m@th\fi\the\hashtoks@\iftab@\else$\fi}%
 \def\l{\noexpand\ifhline@@\hbox{\vrule height\htStrut@%
   depth\dpstrut@ width\z@}\noexpand\fi%
   \ifStrich@\hbox{\vrule height\htstrut@ depth\dpstrut@ width\z@}%
   \fi\iftab@\else$\m@th\fi\the\hashtoks@\iftab@\else$\fi\hfil}%
 \def\s{\ifStrich@\ \the\tabs@\vrule width\D@cke\the\hashtoks@%
          \fi\the\tabs@\ }%
 \def\sa{\ifStrich@\vrule width\D@cke\the\hashtoks@%
            \the\tabs@\ %
            \fi}%
 \def\se{\ifStrich@\ \the\tabs@\vrule width\D@cke\the\hashtoks@\fi}%
 \def\cd{\hfil\noexpand\ifhline@@\hbox{\vrule height\htStrut@%
   depth\dpstrut@ width\z@}\noexpand\fi%
   \ifStrich@\hbox{\vrule height\htstrut@ depth\dpstrut@ width\z@}%
   \fi$\dsize\m@th\the\hashtoks@$\hfil}%
 \def\rd{\hfil\noexpand\ifhline@@\hbox{\vrule height\htStrut@%
   depth\dpstrut@ width\z@}\noexpand\fi%
   \ifStrich@\hbox{\vrule height\htstrut@ depth\dpstrut@ width\z@}%
   \fi$\dsize\m@th\the\hashtoks@$}%
 \def\ld{\noexpand\ifhline@@\hbox{\vrule height\htStrut@%
   depth\dpstrut@ width\z@}\noexpand\fi%
   \ifStrich@\hbox{\vrule height\htstrut@ depth\dpstrut@ width\z@}%
   \fi$\dsize\m@th\the\hashtoks@$\hfil}%
 \ifStrich@\else\Str@chfehlt#1\\\fi%
 \setbox\z@\hbox{\xdef\Preamble@{\preamble@}}\ifnum`{=0 \fi\iffalse}\fi
 \ialign\bgroup\span\Preamble@\crcr}
\newif\ifhline@\hline@false
\newif\ifhline@@\hline@@false
\def\hlinefor#1{\multispan@{\strip@#1 }\leaders\hrule height\D@cke\hfill%
    \global\hline@true\ignorespaces}
\def\Item "#1"{\par\noindent\hangindent2\parindent%
  \hangafter1\setbox0\hbox{\rm#1\enspace}\ifdim\wd0>2\parindent%
  \box0\else\hbox to 2\parindent{\rm#1\hfil}\fi\ignorespaces}
\def\ITEM #1"#2"{\par\noindent\hangafter1\hangindent#1%
  \setbox0\hbox{\rm#2\enspace}\ifdim\wd0>#1%
  \box0\else\hbox to 0pt{\rm#2\hss}\hskip#1\fi\ignorespaces}
\def\item"#1"{\par\noindent\hang%
  \setbox0=\hbox{\rm#1\enspace}\ifdim\wd0>\the\parindent%
  \box0\else\hbox to \parindent{\rm#1\hfil}\enspace\fi\ignorespaces}
\let\plainitem@\item
\catcode`\@=13

\topmatter 
\title On Hales--Jewett's Theorem
\endtitle 
\author Giuseppe Pirillo
\endauthor 
\address 
I.A.G.A.-I.A.M.I., Consiglo Nazionale Delle Recerche, viale Morgagni
67/A, I-50134 Firenze, Italy
\endaddress

\abstract\nofrills{\smc Summary}.
We prove that, for every finite semigroup $S$, there exist elements
$a_1,a_2,\dots,\mathbreak a_k,a_{k+1}$ of $S$ and integers $i_1,i_2,\dots,i_k$
such that
$$a_1\cdot x^{i_1}\cdot a_2\cdot x^{i_2}\cdot\dots\cdot
a_k\cdot x^{i_k}\cdot a_{k+1}=
a_1\cdot y^{i_1}\cdot a_2\cdot y^{i_2}\cdot\dots\cdot
a_k\cdot y^{i_k}\cdot a_{k+1}$$
for each $x,y$ of $S$.
\endabstract

\endtopmatter
\document

We refer to \cite{1} for the notion of (combinatorial) line as well as
for the other combinatorial concepts we use in the sequel.

The following theorem of Hales--Jewett is well-known.

\proclaim{Theorem \rm(\cite{2})} Given any finite set $A$ and any
integer $r$ there exists an integer $N=N(A,r)$ such that for each
$n\ge N(A,r)$ in any coloring of $A^n$ there is always a monochromatic
line.
\endproclaim

In \cite{1}, Graham presented an interesting algebraic application of
the theorem: for every finite commutative semigroup $S$, there exist
an element $a$ of $S$ and an integer $n$ such that
$$a\cdot x^n=a\cdot y^n$$
for each $x,y$ of $S$, i.e., $a\cdot x^n$ is independent of $x$
(shortly, we speak of the constant word $a\cdot x^n$ for $S$).

Trivially, there are finite non-commutative semigroups without
constant word of type $a\cdot x^n$, such as, for example, the
semigroup $D$ presented by the following Cayley table
$$\smatrix\format \c\s\c\s\c\se\\
&\omit&u&\omit&v\\
\omit&\hlinefor5\\
u&&u&&v&\\
\omit&\hlinefor5\\
v&&u&&v&\\
\omit&\hlinefor5
\endsmatrix$$

True, for this semigroup the word $x\cdot u$ is constant, i.e., for
this semigroup a particular case of the word $x^n\cdot b$ (``dual" of
$a\cdot x^n$) is constant. But the semigroup $D'$ presented by the
following Cayley table
$$\smatrix\format \c\s\c\s\c\se\\
&\omit&u&\omit&v\\
\omit&\hlinefor5\\
u&&u&&u&\\
\omit&\hlinefor5\\
v&&v&&v&\\
\omit&\hlinefor5
\endsmatrix$$
shows that $x^n\cdot b$ is not a constant word for each finite
semigroup.

Again, the direct product $D\times D'$, where $D$ and $D'$ are as
previously described, is a semigroup without constant word of type
$a\cdot x^n$ and without a constant word of type $x^n\cdot b$. 

After some other considerations like the previous ones, the following
question naturally arises: given any finite semigroup, does there
exist a sort of constant word for it?

The following proposition gives us the answer.

\proclaim{Proposition} For any finite semigroup $S$ there exist an
integer $k$, a $(k+1)$-tuple $a_1,a_2,\dots,a_k,a_{k+1}$ of elements
of $S$, and a $k$-tuple $i_1,i_2,\dots,i_k$ of integers such that
$$a_1\cdot x^{i_1}\cdot a_2\cdot x^{i_2}\cdot\dots\cdot
a_k\cdot x^{i_k}\cdot a_{k+1}$$
is independent of $x$, i.e., it is a constant word for $S$.
\endproclaim
\demo{Proof} Consider $S$ both as an alphabet and as a set of
colors. From Hales--Jewett's theorem there exists an integer
$N(S,\vert S\vert)$ such that for each integer $n\ge N(S,\vert
S\vert)$ and each $\vert S\vert$-coloring of $S^n$, a line of $S^n$ is
monochromatic.

This is true, in particular, when each element
$$(x_1,x_2,\dots,x_n)$$
of $S^n$ is colored by
$$x_1\cdot x_2\cdot\dots\cdot x_n,$$
i.e., the product in $S$ of $x_1,x_2,\dots,x_n$.

Now, if the monochromatic line is the diagonal, then the conclusion
follows immediately.

If the monochromatic line is not the diagonal, then the lengths of the
``lakes" of the non-fixed coordinates (there is always such a
coordinate) give us the integer $i_j$, and the elements $a_j$ are
easily obtained by looking at the fixed coordinates.
\enddemo





\Refs
\ref\no1\by R. L. Graham
\book Rudiments of Ramsey theory\publ CBMS Regional Conference Series
in Mathematics, vol.~45, 
American Mathematical Society,\publaddr Providence, R.I.\yr
1981\endref
\ref\no2\by A. W. Hales and R. I. Jewett
\paper Regularity and positional games\jour
Trans\. Amer\. Math\. Soc\.\vol 106\yr 1963\pages 222--229\endref

\endRefs





\enddocument
