%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-61/document.tex.
%%%%
%% Standard package list
\documentclass[letterpaper]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[english]{babel}
\usepackage[top=3cm, bottom=3cm, left=3.5cm, right=3.5cm]{geometry}
\usepackage[onehalfspacing]{setspace}
\usepackage{amsmath,amssymb,amsthm,wasysym}
\usepackage{nicefrac,booktabs}
\usepackage{mathptmx}
\usepackage{cite}
\usepackage[colorlinks=true]{hyperref}

%% Various helpers for Tom's papers
\newcommand{\gs}{\textnormal{gs}}
\newcommand{\ord}{\textnormal{ord}}
\newcommand{\Exp}{\textnormal{Exp}}
\newcommand{\Log}{\textnormal{Log}}
\newcommand{\lcm}{\textnormal{lcm}}
\newcommand{\range}{\textnormal{range}}
\newcommand{\NR}{\textnormal{NR}}
\newcommand{\Mod}[1]{\left(\textnormal{mod}~#1\right)}

\newcommand{\ap}[2]{\left\langle #1;#2 \right\rangle}
\newcommand{\summ}[1]{\sum_{k=1}^m{#1}}
\newcommand{\bt}[1]{{{#1}\mathbb{N}}}
\newcommand{\fp}[1]{{\left\lbrace{#1}\right\rbrace}}
\newcommand{\intv}[1]{{\left[1,{#1}\right]}}


%% Lifted from http://stackoverflow.com/questions/2767389/referencing-a-theorem-like-environment-by-its-name
%% This lets me do things like "Theorem A" and have the references work properly.
\makeatletter
\let\@old@begintheorem=\@begintheorem
\def\@begintheorem#1#2[#3]{%
  \gdef\@thm@name{#3}%
  \@old@begintheorem{#1}{#2}[#3]%
}
\def\namedthmlabel#1{\begingroup
   \edef\@currentlabel{\@thm@name}%
   \label{#1}\endgroup
}
\makeatother
% end lift

\newtheoremstyle{namedthrm}
  {}{}{}{}{}{}{ }  % This last space needs to be there
  {\bf\thmname{#1} \thmnote{#3}.}
%% End reference hack


%% Document start
\date{}
\begin{document}

%% Content start


\newtheorem{cor}{Corollary}
\newtheorem{lemma}{Lemma}
\newtheorem{thm}{Theorem}
\newtheorem{q}{Problem}
\theoremstyle{definition}
\newtheorem*{defn}{Definition}
\newtheorem*{ack}{Acknowledgements}

\title{Is There a Sequence on Four Symbols in Which No Two Adjacent Segments Are Permutations of One Another?}
\author{T. C. Brown}
\date{}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. {Brown}, \emph{Is there a sequence on four symbols in which no two adjacent
  segments are permutations of one other?}, American Math. Monthly \textbf{78}
  (1971), 886--888.}\bigskip\end{center}

It has long been known (see~\cite{hedlund1959,thue1906,thue1912,arshon1937,morse1938,morse+hedlund1944,hawkins+mientka1956,leech1957,braunholtz1963,dean1965}) that there exist sequences on $3$ symbols which contain no 2 identically equal consecutive segments, and sequences on 2 symbols which contain no 3 identically equal consecutive segments. Indeed, Axel Thue obtained these results around 1906. See~\cite{hedlund1959} for a brief account of the contexts of the various independent rediscoveries of these results, and see~\cite{robbins1937,hedlung+gottschalk1964} for an account of other properties of these sequences. 

Let $X$ be a set and let $s = x_1x_2x_3\cdots$ be a sequence on $X$. Then for $i+ 1 \leq k$, $s[i+1,k] = x_{i+1}x_{i+2}\cdots x_k$ is a \emph{segment} of $s$, and the segments $s[i+1,j],s[j+1,k]$ are \emph{consecutive}. The segments $s[i+1,j]$ and $s[p + 1, q]$ are \emph{identically equal} if $k-i = q - p$ and $x_{i + 1} = x_{p+1}, x_{i+ 2} = x_{p +2}, \dots, x_k = x_q$ or, in other words, if $s[i + 1,k] = s[p + 1, q]$ in $X^*$, the free semigroup generated by the set $X$.

An interesting situation arises when we allow the symbols \emph{within a segment} to commute with each other. It will be convenient to use the following terminology.

Given a set $X$ and a sequence $s$ on $X$, we regard segments of $s$ as elements of $X^*$. (Thus the results mentioned above say that there exist sequences on 3 symbols without 2nd powers as segments, and sequences on 2 symbols without 3rd powers.) Now let $X^+$ denote the free commutative semigroup generated by $X$, and let $\alpha: X^* \mapsto X^+$ be the natural homomorphism ($\alpha(x) = x$ for $x \in X$). If $s$ has $k$ consecutive segments $f_1,\dots, f_k$ such that $\alpha(f_1) = \cdots = \alpha(f_k)$, then we say that $s$ has a $k$th power mod $\alpha$. In this language, the question of the title is: Does there exist a sequence on four symbols without 2nd powers mod $\alpha$?

It is an easy matter to verify that every sequence on 3 symbols contains 2nd powers mod $\alpha$, and that every sequence on 2 symbols has 3rd powers mod $\alpha$. For example, if $X = \{x,y\}$, one can show by examining all cases that the longest elements of $X^*$ which do not contain a 3rd power mod $\alpha$ are $xxyyxyyxx, xxyyxyyxy,$ and a few others. Evdomikov~\cite{evdokimov1968} constructed a sequence on 25 symbols without 2nd powers mod $\alpha$, and conjectured that perhaps 5 symbols would suffice. Justin~\cite{justin1972-1}, with a remarkable half-page proof, constructed a sequence on 2 symbols without 5th powers mod $\alpha$. This sequence is obtained by successive iterations of the transformation $x \mapsto xxxxy$ and $y \mapsto xyyyy$, starting with $x$. Thus the first few iterations give $x, xxxxy, (xxxxy)^4xyyyy, [(xxxxy)^4 xyyyy]^4xxxxy(xyyyy)^4$. Then in 1970 a paper appeared~\cite{pleasants1970} in which P. A. B. Pleasants gave a construction of a sequence on 5 symbols without 2nd powers mod $\alpha$. Pleasants' sequence, which extends to infinity in both directions, is constructed by successive iterations of the transformation
\begin{align*} 
a &\mapsto bacaeacadaeadab \\
b &\mapsto cbdbabdbebabebc \\
c &\mapsto dcecbcecacbcacd \\
d &\mapsto edadcdadbdcdbde \\
e &\mapsto aebedebecedecea \\
\end{align*}
The reader has perhaps notice the ``duality" between the number of symbols and the power, according to which the ``dual" of each known result is also known. Indeed, it is conceivable that by inserting a third symbol into suitable places in Justin's sequence one could break up all the 4th powers mod $\alpha$ and so obtain a sequence on 3 symbols without 4th powers mod $\alpha$. Doing this twice more would give another sequence on 5 symbols without 2nd powers mod $\alpha$, and would tend to clarify the existence of the ``duality" in the first place. 

Little seems to be known about the $(2,4)$ case, that is, the existence of sequences on $2$ symbols without 4th powers mod $\alpha$ and on $4$ symbols without 2nd powers mod $\alpha$, beyond Justin's statement~\cite{justin1972-2} that one can construct on 4 symbols segments of length 7500 without 2nd powers mod $\alpha$. Pleasants~\cite{pleasants1970} states ``it seems certain" that there is a sequence on 4 symbols without 2nd powers mod $\alpha$, and gives several hints as to how one might manage to construct such a sequence. Even less appears to be known about the self-dual (3,3) case.

\begin{ack} The author is grateful to the referee for pointing out Thue's work and for references~\cite{hedlund1959,thue1906,thue1912}, and to V. L. Klee for drawing attention to the references in a draft by H. T. Croft and R. K. Guy of their forthcoming book \emph{Research Problems in Intuitive Mathematics}.
\end{ack}


\bibliographystyle{amsplain}
\bibliography{tom-all}
\end{document}