\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage{tikz}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}
\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf
On Highly Repetitive and Power Free Words
}
\vskip 1cm
\large
Narad Rampersad\\
Department of Mathematics and Statistics\\
University of Winnipeg \\
Canada\\
\href{mailto:narad.rampersad@gmail.com}{\tt narad.rampersad@gmail.com}\\
\ \\
Elise Vaslet \\
Department of Mathematics\\
University of Turku \\
Finland\\
\end{center}
\vskip .2 in
\begin{abstract}
Answering a question of Richomme, Currie and Rampersad
proved that $7/3$ is the infimum of the real numbers $\alpha > 2$ such
that there exists an infinite binary word that avoids $\alpha$-powers
but is highly $2$-repetitive, i.e., contains arbitrarily large squares
beginning at every position. In this paper, we prove similar statements
about $\beta$-repetitive words, for some other $\beta$'s, over the binary
and the ternary alphabets.
\end{abstract}
\section{Introduction}
In this paper we study words that are non-repetitive, in the sense
that they avoid $\alpha$-powers for some $\alpha$, but yet are highly
repetitive, in the sense that for some $\beta$ close to $\alpha$, they
contain infinitely many $\beta$-powers starting at every position.
First we recall some basic definitions. A finite, non-empty word $v$
can be written as $v = p^ke$, where $k \geq 1$, the word $e$ is a
prefix of $p$, and the length of $p$ is minimal. We say that $v$ has
\emph{period} $p$, \emph{excess} $e$, and \emph{exponent}
$\mbox{expo}(v) = |v|/|p|$. A word with exponent $\alpha$ is called
an $\alpha$-power. An $\alpha^+$-\emph{power} is a word that is a
$\beta$-power for some $\beta > \alpha$. A $2$-power is called a
\emph{square}; a $2^+$-power is called an \emph{overlap}. A word is
$\alpha$-\emph{free} if none of its factors is a $\beta$-power for any
$\beta \geq \alpha$. A word is $\alpha^+$-\emph{free} if none of its
factors is an $\alpha^+$-power.
Thue \cite{th2} proved that there exist infinite overlap-free
binary words. Dekking \cite{dek} later showed that any infinite
overlap-free binary word must contain arbitrarily large squares.
Currie, Rampersad, and Shallit \cite{crs} constructed $7/3$-free words
containing infinitely many overlaps. Their motivation came from the
following result of Shur \cite{shu}: Any bi-infinite $7/3$-free binary
word is overlap-free. The analogue of this surprising result is not
true for one-sided infinite words: There are infinite $7/3$-free
binary words that are not overlap-free. The result of Currie et al.\
shows that in fact the infinite $7/3$-free binary words can be
significantly different from the infinite overlap-free binary words.
Currie and Rampersad \cite{cr} continued this line of study in order to
respond to the following question of Richomme \cite{ric}:
What is the infimum of the real numbers $\alpha > 2$ such that
there exists an infinite word that avoids $\alpha$-powers but
contains arbitrarily large squares beginning at every position?
They showed that over the binary alphabet the answer to Richomme's
question is $\alpha = 7/3$. In this paper we show that if instead of
requiring arbitrarily large squares at every position, we only
ask for arbitrarily large $\beta$-powers at every position for some fixed
$\beta < 2$, then the answer of $7/3$ for Richomme's question can be
replaced by $2$. We also answer the analogous question for the ternary
alphabet.
Specifically, we first define a \emph{highly $\alpha$-repetitive} word
to be a word that contains infinitely many $\alpha$-repetitions
beginning at every position. Our main results are:
\begin{enumerate}
\item On the binary alphabet, for any real number $\beta <2$, there
exists a $2^+$-free word that is highly $\beta$-repetitive.
\item On the ternary alphabet, for any real number $\beta <7/4$, there
exists a $7/4^+$-free word that is highly $\beta$-repetitive.
\end{enumerate}
We also mention here the related work of Saari \cite{saa}, who also
studied infinite words containing squares (not necessarily arbitrarily
large) beginning at every position. He called such words
\emph{squareful}, but he imposed the additional condition that the
word contain only finitely many distinct minimal squares.
\section{Preliminary definitions and results}\label{prelim}
Let $\alpha$ be a real number.
\begin{definition}
A finite word is an \emph{$\alpha$-repetition (resp.\ \emph{$\alpha^+$-repetition}) if it is a $\beta$-power for some $\beta \geq \alpha$ (resp.\ $\beta > \alpha$).}
\end{definition}
\begin{definition}
A word (finite or infinite) is \emph{highly $\alpha$-repetitive} (resp.\ \emph{highly $\alpha^+$-repetitive}) if it contains infinitely many $\alpha$-repetitions (resp.\ $\alpha^+$-repetitions) beginning at every position.
\end{definition}
\begin{definition}
A word (finite or infinite) is \emph{$\alpha$-free} (resp.\ \emph{$\alpha^+$-free}) if it contains no $\alpha$-repetition (resp.\ $\alpha^+$-repetition).
\end{definition}
\begin{definition}
A morphism $\mu : A^* \rightarrow B^*$ is \emph{$\alpha$-free} (resp.\ \emph{$\alpha^+$-free}) if for any word $w \in A^*$, the following equivalence holds:
\begin{center}
$w$ is $\alpha$-free (resp.\ $\alpha^+$-free) $\Leftrightarrow$
$\mu(w)$ is $\alpha$-free (resp.\ $\alpha^+$-free).
\end{center}
\end{definition}
\begin{definition}
The \emph{critical exponent} $E_c(w)$ of an infinite word $w$ is the supremum of all rational numbers $r$ such that $w$ contains an $r$-power.
\end{definition}
We now define some particular morphisms which we will use in the
paper because of their $\alpha$-freeness for certain $\alpha$.
The Thue-Morse morphism is defined by
\begin{eqnarray*}
\mu_{TM} : \begin{cases}
0 \mapsto 01 \\
1 \mapsto 10. \\
\end{cases}
\end{eqnarray*}
\begin{proposition}[\cite{th2}]
$\mu_{TM}$ is a $2^+$-free morphism.
\end{proposition}
Dejean's morphism is defined by
\begin{eqnarray*}
\mu_D : \begin{cases}
a \mapsto abc \; acb \; cab \; c \; bac \; bca \; cba \\
b \mapsto \pi (\mu_D (a) ) = bca \; bac \; abc \; a \; cba \; cab \; acb \\
c \mapsto \pi^2 (\mu_D (a)) = cab \; cba \; bca \; b \; acb \; abc \; bac, \\
\end{cases}
\end{eqnarray*}
where $\pi$ is the morphism that cyclically permutes the alphabet
$\{a,b,c\}$.
\begin{proposition}[\cite{dej}]
$\mu_{D}$ is a $7/4^+$-free morphism.
\end{proposition}
The following morphism was given by Brandenburg in \cite{bra}:
\begin{eqnarray*}
\mu_B : \begin{cases}
a \mapsto abacbabcbac \\
b \mapsto abacbcacbac \\
c \mapsto abcbabcacbc. \\
\end{cases}
\end{eqnarray*}
\begin{proposition}[\cite{bra}]
$\mu_{B}$ is a $2$-free morphism.
\end{proposition}
Finally, for any integers $s,t$ such that $0~~1;\\
t(t+1)+1+\frac{1}{t}, & \textup{ if } s =1. \end{cases}$$ These
morphisms were introduced by Krieger, who proved that:
\begin{proposition}[\cite{kri}]
The fixed point $\phi_{s,t}^{\omega}(0)$ of
$\phi_{s,t}$ has critical exponent $$E_c(\phi_{s,t}^{\omega}(0)) =
q_{s,t}. $$
\end{proposition}
In particular, the following remark will be useful:
\begin{remark}\label{freeness of the images}
For any factor $v$ of the fixed point $\phi_{s,t}^{\omega}(0)$, the word $\phi_{s,t}(v)$ is $q_{s,t}^+$-free.
\end{remark}
\section{Highly repetitive binary words}\label{binary}
The results of Currie and Rampersad \cite[Theorems 4 and 5]{cr}
state that for any $\alpha > 7/3$, there exists an infinite binary
word which is both $\alpha$-free and highly $2$-repetitive, and that such a word does not exist if $\alpha \leq 7/3$. The following proposition gives a similar result in the case of highly $\beta$-repetitive words, with $\beta < 2$: for any $\alpha>2 $ and any $\beta <2$, there exists an infinite binary word which is both $\alpha$-free and highly $\beta$-repetitive.
\begin{theorem}\label{high_rep_bin}
For any real number $\beta <2$, there exists an infinite binary word which is both $2^+$-free and highly $\beta$-repetitive.
\end{theorem}
\begin{proof}
Let $\beta <2$ be a real number. There exists an integer $m \geq 1$
such that $\beta \leq 2-\frac{1}{2^{m}} <2$. Let $r =
2-\frac{1}{2^{m}}$, and let us construct a binary infinite word with infinitely many $r$-powers at every position, and which is $2^+$-free. We recall that $\mu_{TM}$ is the Thue-Morse morphism.
We remark that $ \mu_{TM}^{m}(11)$ is a factor of $ \mu_{TM}^{m+3}(1)$. Indeed, $ \mu_{TM}^{3}(1) = 10010110$, and so
$ \mu_{TM}^{m+3}(1) = \mu_{TM}^{m}(10010110) = u \mu_{TM}^{m}(11) \mu_{TM}^{m}(0)$, where $u= \mu_{TM}^{m}(10010)$. Let us define $q = m+3$.
We define the following sequence of finite words: \begin{eqnarray*}
A_0 &=& \mu_{TM}^{m}(11)\\
A_1 & = & (u)^{-1} \mu_{TM}^{q}(A_0) \\
& \vdots & \\
A_n &= & (u)^{-1} \mu_{TM}^q(A_{n-1}),
\end{eqnarray*}
where we denote by $(x)^{-1} y$ the word obtained by removing the prefix $x$ from the word $y$ (here, the word $\mu_{TM}^q(A_{n})$ always has $u$ as a prefix, since $A_n$ always has $1$ as a prefix).
As $11$ and $\mu_{TM}$ are $2^+$-free, then for any $n\geq 0$, $A_n$ is $2^+$-free.
We show that for any $n\geq 0 $, $A_n$ is a prefix of $A_{n+1}$. This is clearly true for $n=0$. If $A_{n-1}$ is a prefix of $A_n$, then we can write $A_n = A_{n-1} S$, where $S$ is a binary word. Then, $A_{n+1}= (u)^{-1}\mu_{TM}^q(A_{n-1}S) = A_n\mu_{TM}^q(S)$. Thus, the sequence $A_n$ converges to an infinite limit word we denote by $w$, and this limit is $2^+$-free. We now prove that $w$ contains infinitely many $r$-powers beginning at every position. It can easily be seen that for any $n\geq 1 $,
$$A_n = (u)^{-1} [\mu_{TM}^q(u)]^{-1} \cdots [\mu_{TM}^{q(n-1)}(u)]^{-1} \mu_{TM}^{qn}(A_0).$$
(Here the sequence of deletions indicated by the terms appearing with exponent $-1$ should be understood as being applied from right to left.)
Let us denote by $p_n$ the word $$\mu_{TM}^{q(n-1)}(u) \cdots \mu_{TM}^q(u) u.$$ Then we have $A_n = (p_n)^{-1} \mu_{TM}^{qn}(A_0) $, since for any words $u$ and $v$, $(uv)^{-1} = (v)^{-1}(u)^{-1}$. Moreover, we can see that $p_n$ is a prefix of $\mu_{TM}^{qn}(1)$. Indeed,
\begin{eqnarray*}
|p_n| & = & |u| \sum_{i = 0}^{n-1} |\mu_{TM}(1)|^{qi}\\
& = & |u| \sum_{i = 0}^{n-1} 2^{qi}\\
& < & 2^{qn} = |\mu_{TM}^{qn}(1)|,
\end{eqnarray*}
since $|u| \leq 2^q -1$. So, we can write $\mu_{TM}^{qn}(1) = p_n s_n$, where $s_n$ is a binary word. For any $n \geq 1 $,
$A_n = (p_n)^{-1}\mu_{TM}^{qn}(A_0) = (p_n)^{-1} \mu_{TM}^{qn}(\mu_{TM}^{m}(11))$.
We know that $\mu_{TM}^{m}(1)$ begins with the letter $1$, and let us denote its last letter by $a\in \{0,1\}$. We can write $\mu_{TM}^{m}(1)= 1 x a$, where $x \in \{0,1\}^*$. We can also write $\mu_{TM}^{qn}(a) = \tilde{p_n} \tilde{ s_n}$, with $ \tilde{p_n}$ and $ \tilde{ s_n}$ two binary words such that $|\tilde{p_n}| = |p_n|$ and $|\tilde{ s_n}| = |s_n|$. Then,
$$A_n = s_n \mu_{TM}^{qn}(x) \tilde{p_n} \tilde{ s_n} p_ns_n \mu_{TM}^{qn}(x) \tilde{p_n} \tilde{ s_n}.$$
It follows that at all positions $0 \leq j \leq |s_n|$, there begins a repetition with period a conjugate of $s_n \mu_{TM}^{qn}(x) \tilde{p_n} \tilde{ s_n} p_n$, and of length
\begin{eqnarray*}
&&|s_n \mu_{TM}^{qn}(x) \tilde{p_n} \tilde{ s_n} p_n s_n
\mu_{TM}^{qn}(x) \tilde{p_n} | \\
& = & 2\cdot |x|\cdot 2^{qn}+ 3\cdot 2^{qn} \\
& = & 2^{qn}(2^{m+1}-1),
\end{eqnarray*}
since $|x|= |\mu_{TM}^{m}(1)|-2 = 2^m - 2$. These repetitions have exponents
$\frac{2^{qn}(2^{m+1}-1)}{2^{qn}|x|+2\cdot 2^{qn}} = \frac{2^{m+1}-1}{2^m} = r$. As $n$ can be taken arbitrarily large, the result follows.
\end{proof}
Moreover, this result is optimal. Indeed, on the one hand, it is easy
to see that for $\alpha \leq 2$, there is no infinite binary
$\alpha$-free word. On the other hand, Currie and Rampersad proved the
following result.
\begin{proposition}[\cite{cr}]
If $w$ is an infinite $2^+$-free binary word, then there is a position
$i$ such that $w$ does not contain a square beginning at position
$i$.
\end{proposition}
Our next result uses the morphisms $\phi_{s,t}$ defined in Section~\ref{prelim}.
We will first establish a few technical lemmas, which will be used to prove Proposition \ref{main proposition}.
For any integers $s,t$ and any integer $N$, we define
$$u_{s,t,N}=\begin{cases}\phi_{s,t}^{N-3}(0), & \textup{ if } s>1; \\
\phi_{s,t}^{N-3}(01^t), & \textup{ if } s=1, \end{cases}$$
and $$r_{s,t}= \begin{cases}1^t0, & \textup{ if } s>1; \\ 0^{t(t+1)+1}1,
& \textup{ if }s=1. \\ \end{cases}$$
\begin{lemma}\label{prefixes in the images}
For any $N \geq 3$, $\phi_{s,t}^N(0)$ begins with the prefix $u_{s,t,N} \phi_{s,t}^{N-3}(r_{s,t})$.
\end{lemma}
\begin{proof}
We prove this result by a simple induction. Suppose first that $s>1$. It is clear that $01^t0$ is a prefix of $\phi_{s,t}^3(0)$. Then, if we assume that $\phi_{s,t}^N(0)=u_{s,t,N} \phi_{s,t}^{N-3}(r_{s,t})s_{s,t,N}$, where $s_{s,t,N}$ denotes the corresponding suffix, then, we have: \begin{eqnarray*}
\phi_{s,t}^{N+1}(0)&=&\phi_{s,t}(\phi_{s,t}^{N-3}(01^t0)s_{s,t,N})\\
&=&u_{s,t,N+1} \phi_{s,t}^{N-2}(r_{s,t})\phi_{s,t}(s_{s,t,N}),
\end{eqnarray*}
which concludes the calculation. The case $s=1$ is proved similarly.
\end{proof}
We denote by $P_{s,t,N}$ the longest common prefix of
$\phi_{s,t}^{N}(0)$ and $\phi_{s,t}^{N}(1)$.
\begin{lemma}\label{commun prefix}
For any integer $N\geq 1$,
$$P_{s,t,N} = \phi_{s,t}^{N-1}(01^{s-1}) \phi_{s,t}^{N-2}(01^{s-1}) \cdots \phi_{s,t}(01^{s-1}) 01^{s-1}.$$
\end{lemma}
\begin{proof}
We prove the result by induction. We suppose first that $s > 1$. It is
clear that the longest common prefix of $\phi_{s,t}(0)$ and
$\phi_{s,t}(1)$ is $01^{s-1}$, since $s \leq t$. Now, assuming that $
P_{s,t,N} = \phi_{s,t}^{N-1}(01^{s-1}) \phi_{s,t}^{N-2}(01^{s-1})
\cdots \phi_{s,t}(01^{s-1}) 01^{s-1}$, the longest common prefix of
$\phi_{s,t}^{N+1}(0)$ and $\phi_{s,t}^{N+1}(1)$ is the longest common
prefix of $ \phi_{s,t}(P_{s,t,N}0)$ and $\phi_{s,t}(P_{s,t,N}1)$,
i.e., the longest common prefix of $$\phi_{s,t}^{N}(01^{s-1})
\phi_{s,t}^{N}(01^{s-1}) \cdots \phi_{s,t}(01^{s-1}) \phi_{s,t}(0) $$
and $$\phi_{s,t}^{N}(01^{s-1}) \phi_{s,t}^{N}(01^{s-1}) \cdots
\phi_{s,t}(01^{s-1}) \phi_{s,t}(1).$$ This prefix is obviously
$\phi_{s,t}^{N}(01^{s-1}) \phi_{s,t}^{N}(01^{s-1}) \cdots
\phi_{s,t}(01^{s-1})01^{s-1} $. The case $s=1$ is proved with similar
arguments.
\end{proof}
\begin{lemma}\label{repetitions in the images}
For any $N\geq 3$, $\phi_{s,t}^N(0)$ contains the repetition
$$R_{s,t,N} = \begin{cases}(\phi_{s,t}^{N-3}(1))^{t}P_{s,t,N-3}, & \textup{ if } s>1; \\ (\phi_{s,t}^{N-3}(0))^{t(t+1)+1}P_{s,t,N-3}, & \textup{ if }s=1,\end{cases}$$
which has exponent
$$E(R_{s,t,N})= \begin{cases}
t+\frac{s}{t}-\frac{s}{t(t+1)^{N-3}},& \textup{ if } s>1;\\
t(t+1)+1+\frac{1}{t}-\frac{1}{t(t+1)^{N-3}}, & \textup{ if } s=1.
\end{cases}$$
More precisely, $\phi_{s,t}^N(0)$ begins with the prefix $u_{s,t,N}R_{s,t,N}$.
\end{lemma}
\begin{proof}
The fact that $\phi_{s,t}^N(0)$ contains the repetition $R_{s,t,N}$ is
easily deduced from Lemmas \ref{prefixes in the images} and
\ref{commun prefix}. The exponent of this repetition is a simple
calculation. Indeed, $R_{s,t,N}$ has period $\phi_{s,t}^{N-3}(1)$ or
$\phi_{s,t}^{N-3}(0)$ (depending on the value of $s$), and excess
$P_{s,t,N-3}$. As we have $|P_{s,t,N-3}| =
\frac{s((t+1)^{N-3}-1)}{t}$, and $|\phi_{s,t}^{N-3}(1)|=
|\phi_{s,t}^{N-3}(0)|= (t+1)^{N-3}$, the result follows.
\end{proof}
\begin{proposition}\label{main proposition}
For any integers $s,t$, such that $0 < s \leq t$, and any real number $\beta1; \\ 0^{t(t+1)+1}1, & \textup{ if }s=1.\end{cases}$$
We can easily deduce from Lemma \ref{prefixes in the images} that $\phi_{s,t}^{p+N-3}(r_{s,t})$ is a factor of $\phi_{s,t}^{p+N}(0)$.
Indeed, by the Lemma, $\phi_{s,t}^{N}(0) = u_{s,t,N}\phi_{s,t}^{N-3}(r_{s,t})y $, with $y$ a binary word, so $$\phi_{s,t}^{p+N}(0) = \phi_{s,t}^{p}(u_{s,t,N})\phi_{s,t}^{p+N-3}(r_{s,t}) \phi_{s,t}^{p}(y).$$
Let us denote by $u$ the word $\phi_{s,t}^{p}(u_{s,t,N})$. Let us now set $q=p+N$, and define the following sequence of finite binary words:
\begin{eqnarray*}
A_0 &=& \phi_{s,t}^{p+N-3}(r_{s,t})\\
A_1& = & (u^{-1})\phi_{s,t}^q(A_0) \\
&\vdots & \\
A_M&=& (u^{-1})\phi_{s,t}^q(A_{M-1}).
\end{eqnarray*}
(Here, the word $\phi_{s,t}^q(A_M)$ always has $u$ as a prefix, since $A_M$ always has $0$ as a prefix.)
As $r_{s,t}$ is $q_{s,t}^+$-free and by Remark~\ref{freeness of the images}, we deduce that for any $M \geq 0$, $A_M$ is $q_{s,t}^+$-free. We now show that for any $M\geq 0$, $A_M$ is a prefix of $A_{M+1}$. This is clearly true for $M=0$, by definition of $u$. Then, if $A_{M-1}$ is a prefix of $A_M$, let us write $A_M = A_{M-1}S$, where $S \in \{0,1\}^*$. Then, $A_{M+1}=(u)^{-1}\phi_{s,t}^q(A_{M-1}S) = A_M\phi_{s,t}^q(S)$. Thus, the sequence of words $A_M$ converges to an infinite binary limit word we denote by $w$, and this limit is $q_{s,t}^+$-free. Let us now prove that $w$ contains infinitely many $r$-powers beginning at every position. It is easy to see that for any $M\geq 1$,
$$A_M = (u)^{-1}[\phi_{s,t}^q(u)]^{-1} \cdots [\phi_{s,t}^{q(M-1)}(u)]^{-1} \phi_{s,t}^{qM}(A_0).$$
We define $p_M = \phi_{s,t}^{q(M-1)}(u) \cdots \phi_{s,t}^q(u) u$, and then we have $A_M = (p_M)^{-1} \phi_{s,t}^{qM}(A_0)$, since for any words $x$, $y$, $(xy)^{-1} = y^{-1}x^{-1}$. Moreover, $p_M$ is a prefix of $\phi_{s,t}^{qM}(0)$. Indeed, since $\phi_{s,t}$ is $(t+1)$-uniform,
\begin{eqnarray*}
|p_M|&=& |u| \sum_{i=0}^{M-1} (t+1)^{qi} \\
&<& (t+1)^{qN} = |\phi_{s,t}^{qN}(0)|,\\
\end{eqnarray*}
since $|u| \leq |\phi_{s,t}^{p+N-3}(01^t)| =(t+1)^{p+N-2}\leq (t+1)^q -1$.
So, we can write $\phi_{s,t}^{qM}(0) = p_Ms_M$, where $s_M$ is the corresponding suffix.
Now, by Lemma \ref{commun prefix}, we can write $\phi_{s,t}^{N-3}(1)=P_{s,t,N-3}P_{s,t,N-3}^{(1)}$ and $\phi_{s,t}^{N-3}(0)=P_{s,t,N-3}P_{s,t,N-3}^{(0)}$, where we recall that $P_{s,t,N-3}$ is the longest common prefix of $\phi_{s,t}^{N-3}(1)$ and $\phi_{s,t}^{N-3}(0)$, and where $P_{s,t,N-3}^{(0)},P_{s,t,N-3}^{(1)}$ are the corresponding suffixes. Now, consider the word $\phi_{s,t}^p(P_{s,t,N-3})$. It begins with the letter $0$. We can then write $\phi_{s,t}^{p}(P_{s,t,N-3}) = 0 z$, with $z \in \{0,1\}^*$.
Now, let us suppose first that $s>1$. Then,
\begin{eqnarray*}
A_M & =& p_M^{-1} \phi_{s,t}^{qM}(A_0)\\
&=& p_M^{-1} \phi_{s,t}^{qM}(\phi_{s,t}^{p+N-3}(1^t0))\\
&=& p_M^{-1} \phi_{s,t}^{qM}([0z \phi_{s,t}^p(P_{s,t,N-3}^{(1)})]^{t}[0z\phi_{s,t}^p(P_{s,t,N-3}^{(0)})])\\
&=& p_M^{-1} [p_Ms_M \phi_{s,t}^{qM}(z)\phi_{s,t}^{p+qM}(P_{s,t,N-3}^{(1)})]^{t}[p_Ms_M\phi_{s,t}^{qM}(z) \phi_{s,t}^{p+qM}(P_{s,t,N-3}^{(0)})].
\end{eqnarray*}
We deduce that at every position $0 \leq j \leq |s_M|$, there begins a repetition with period a conjugate of $s_M \phi_{s,t}^{qM}(z) \phi_{s,t}^{p+qM}(P_{s,t,N-3}^{(1)})p_M$, and excess of length $\geq |(\phi_{s,t}^{qM}(z) | = |z|(t+1)^{qM}$. Thus, these repetitions have exponent at least
\begin{eqnarray*}
& & t+\frac{|z|(t+1)^{qM}}{(|z|+1)(t+1)^{qM}+|P_{s,t,N-3}^{(1)}|(t+1)^{p+qM}} \\
& =& t+\frac{|z|}{|z|+1+|P_{s,t,N-3}^{(1)}|(t+1)^p}\\
& = & t+\frac{|P_{s,t,N-3}|(t+1)^{p}-1}{(|P_{s,t,N-3}|+|P_{s,t,N-3}^{(1)}|)(t+1)^{p}} \textup{ (since } |z|=|\phi_{s,t}^p(P_{s,t,N-3})|-1) \\
&=& t+\frac{|P_{s,t,N-3}|(t+1)^{p}-1}{(t+1)^{N-3}(t+1)^{p}} \\
& =& t+ \frac{s}{t}-\frac{s}{t(t+1)^{N-3}}-\frac{1}{(t+1)^{p+N-3}} =r.
\end{eqnarray*}
As $N$ can be taken arbitrarily large, the result follows.
Finally, let us suppose that $s=1$. Then,
\begin{eqnarray*}
A_M & =& p_M^{-1} \phi_{s,t}^{qM}(A_0)\\
&=& p_M^{-1} \phi_{s,t}^{qM}(\phi_{s,t}^{p+N-3}(0^{t(t+1)+1}1))\\
&=& p_M^{-1} \phi_{s,t}^{qM}([0z \phi_{s,t}^p(P_{s,t,N-3}^{(0)})]^{t(t+1)+1}[0z\phi_{s,t}^p(P_{s,t,N-3}^{(1)})])\\
&=& p_M^{-1} [p_Ms_M \phi_{s,t}^{qM}(z) \phi_{s,t}^{p+qM}(P_{s,t,N-3}^{(0)})]^{t(t+1)+1}[p_Ms_M\phi_{s,t}^{qM}(z) \phi_{s,t}^{p+qM}(P_{s,t,N-3}^{(1)})].
\end{eqnarray*}
We deduce that at every position $0 \leq j \leq |s_M|$, there begins a repetition with period a conjugate of $s_M \phi_{s,t}^{qM}(z) \phi_{s,t}^{p+qM}(P_{s,t,N-3}^{(0)})p_M$, and excess of length $\geq |(\phi_{s,t}^{qM}(z)| = |z|(t+1)^{qM}$. Thus, these repetitions have exponent at least
\begin{eqnarray*}
& & t(t+1)+1+\frac{|z|(t+1)^{qM}}{(|z|+1)(t+1)^{qM}+|P_{s,t,N-3}^{(0)}|(t+1)^{p+qM}} \\
& =& t(t+1)+1+\frac{|z|}{|z|+1+|P_{s,t,N-3}^{(0)}|(t+1)^p}\\
& = & t(t+1)+1+\frac{|P_{s,t,N-3}|(t+1)^{p}-1}{(|P_{s,t,N-3}|+|P_{s,t,N-3}^{(0)}|)(t+1)^{p}} \textup{ (since } |z|=|\phi_{s,t}^p(P_{s,t,N-3})|-1) \\
&=& t(t+1)+1+\frac{|P_{s,t,N-3}|(t+1)^{p}-1}{(t+1)^{N-3}(t+1)^{p}}\\
& =& t(t+1)+1+ \frac{s}{t}-\frac{s}{t(t+1)^{N-3}}-\frac{1}{(t+1)^{p+N-3}} =r.
\end{eqnarray*}
As $N$ can be taken arbitrarily large, the result follows.
\end{proof}
The following proposition shows the optimality of the previous results.
\begin{proposition}\label{q+free_general}
Let $q \geq 2$ be a rational number. If an infinite word is $q^+$-free, then it is not highly $q$-repetitive.
\end{proposition}
\begin{proof}
The proof uses an idea of Richomme mentioned in the conclusion of \cite{cr}.
Suppose to the contrary that $x$ is an infinite $q^+$-free word that is highly $q$-repetitive. Consider two positions
$i$ and $i+1$ in $x$. Since $x$ is highly $q$-repetitive, it contains infinitely many $q$-powers starting at position $i+1$, so in particular, there is a square $ww$ at position $i+1$. Similarly, there are infinitely many squares starting at position $i$. We now apply the following result proved by Ilie \cite[Lemma~2]{ili}: In any word, if $vv$ and $uu$ are two squares at position $i$ and $ww$ is a square at position $i+1$, then either $|w| = |u|$ or $|w| = |v|$ or $|w| \geq 2|v|$. Since there are infinitely many squares starting at position $i$, this implies that $|w|$ equals $|v|$ for some square $vv$ occurring at position $i$. This means that the $q$-power $w^n$ starting at position $i+1$ can be extended to the left by one letter to create a $q^+$-power. This is a contradiction, since $x$ is $q^+$-free.
\end{proof}
\section{Highly repetitive ternary words}\label{ternary}
In this part, we will state some similar results in the case of the ternary alphabet. We recall that the repetition threshold of the ternary alphabet is $7/4$, so for any $\alpha \leq 7/4$, there is no infinite $\alpha$-free ternary word.
\begin{theorem}\label{high_rep_ter}
For any real number $\beta <7/4$, there exists an infinite ternary
word that is both $7/4^+$-free and highly $\beta$-repetitive.
\end{theorem}
\begin{proof}
For any real number $\beta <7/4$, there exists an integer $m \geq 1$ such that $\beta \leq 7/4-\frac{1}{19^{m+2}} <7/4$. Let $r = 7/4-\frac{1}{19^{m+2}}$, and let us construct a $7/4^+$-free word which contains infinitely many $r$-powers at every position. We recall that $\mu_{D}$ is Dejean's morphism.
We remark that $ \mu_{D}^{m}(abcbabc)$ is a factor of $ \mu_{D}^{m+2}(a)$. Indeed,
$$ \mu_{D}^{2}(a) = \mu_{D}(a) \mu_{D}(b) cab cba bca b acb abc bac \mu_{D}(acb cab c bac bca cba), $$ and so
$$
\mu_{D}^{m+2}(a) = u \mu_{D}^{m}(abcbabc) \mu_{D}^m(a b acb abc bac) \mu_{D}^{m+1}(acb cab c bac bca cba),
$$
where $u= \mu_{D}^{m+1}(ab)\mu_{D}^m(c)$.
Let us define $q = m+2$.
We define the following sequence of finite words: \begin{eqnarray*}
A_0 &=& \mu_{D}^{m}(abcbabc)\\
A_1 & = & (u)^{-1} \mu_{D}^{q}(A_0) \\
& \vdots & \\
A_n &= & (u)^{-1} \mu_{D}^q(A_{n-1}).
\end{eqnarray*}
(Here, the word $\mu_{D}^q(A_{n})$ always has $u$ as a prefix, since $A_n$ always has $a$ as a prefix).
As $abcbabc$ and $\mu_{D}$ are $7/4^+$-free, then for any $n\geq 0$, $A_n$ is $7/4^+$-free.
Similar arguments as in the proof of Theorem~\ref{high_rep_bin} prove that the sequence $A_n$ converges to an infinite limit word we denote by $w$, and this limit is $7/4^+$-free. We now prove that $w$ contains infinitely many $\alpha$-powers beginning at every position.
Again with similar arguments as in the proof of Theorem~\ref{high_rep_bin}, we can see that for any $n\geq 1 $,
$$A_n = (p_n)^{-1} \mu_{D}^{qn}(A_0),$$
where $p_n$ is the word $\mu_{D}^{q(n-1)}(u) \cdots \mu_{D}^q(u) u$. Moreover, we can see that $p_n$ is a prefix of $\mu_D^{qn}(a)$. Indeed,
\begin{eqnarray*}
|p_n| & = & |u| \sum_{i = 0}^{n-1} |\mu_{D}(a)|^{qi}\\
& = & |u| \sum_{i = 0}^{n-1} 19^{qi}\\
& < & 19^{qn} = |\mu_{D}^{qn}(a)|.
\end{eqnarray*}
So, we can write $\mu_D^{qn}(a) = p_n s_n$, where $s_n$ is a ternary word. For any $n \geq 1 $,
$A_n = (p_n)^{-1}\mu_{D}^{qn}(A_0) = (p_n)^{-1} \mu_{D}^{qn}(\mu_{D}^{m}(abcbabc))$.
We know that $\mu_{D}^{m}(a)$ begins with the letter $a$, and let us denote its last letter by $x\in \{a,b,c\}$. We can write $\mu_{D}^{m}(a)= a X x$, where $X \in \{a,b,c\}^*$. Similarly, let us write $\mu_{D}^{m}(c)= c Y y$, where $Y \in \{a,b,c\}^*$, and $y\in \{a,b,c\}$. We can also write $\mu_D^{qn}(y) = \tilde{p_n} \tilde{ s_n}$, with $ \tilde{p_n}$ and $ \tilde{ s_n}$ two ternary words such that $|\tilde{p_n}| = |p_n|$ and $|\tilde{ s_n}| = |s_n|$. Then,
$$A_n = s_n \mu_{D}^{qn}(X x \mu_D^m(b) c Y) \tilde{p_n} \tilde{ s_n}\mu_{D}^{qn+m}(b) p_n s_n \mu_{D}^{qn}(X x \mu_D^m(b) c Y) \tilde{p_n} \tilde{ s_n}.$$
It follows that at all positions $0 \leq j \leq |s_n|$, there begins a repetition with period a conjugate of $s_n \mu_{D}^{qn}(X x \mu_D^m(b) c Y) \tilde{p_n} \tilde{ s_n}\mu_{D}^{qn+m}(b) p_n $, and of length \begin{eqnarray*}
l & = & | s_n \mu_{D}^{qn}(X x \mu_D^m(b) c Y) \tilde{p_n} \tilde{ s_n}\mu_{D}^{qn+m}(b) p_n s_n \mu_{D}^{qn}(X x \mu_D^m(b) c Y) \tilde{p_n}| \\
&=& 2\cdot |X x \mu_D^m(b) c Y|\cdot 19^{qn}+19^{qn+m} +3\cdot 19^{qn} \\
&= &19^{qn}\cdot (7\cdot 19^m -1),
\end{eqnarray*}
since $|X| = |Y|= |\mu_{D}^{m}(a)|-2 = 19^m - 2$. These repetitions have exponent
$$\frac{19^{qn}(7\cdot 19^{m}-1)}{19^{qn}|X x \mu_D^m(b) c
Y|+19^{qn+m}+2\cdot 19^{qn}} = \frac{7\cdot 19^{m}-1}{4\cdot 19^{m}} = \alpha.$$ As $n$ can be taken arbitrarily large, the result follows.
\end{proof}
Now, we will consider the problem for highly $7/4$-repetitive
words. This would be Richomme's question for the ternary alphabet:
what is the infimum of the real numbers $\alpha$ such that there
exists an infinite ternary word which is both $\alpha$-free and highly $7/4$-repetitive?
\begin{proposition}
Let $q \geq 7/4$ be a rational number. There is no $q^+$-free ternary word which is highly $q$-repetitive.
\end{proposition}
\begin{proof}
For $q \geq 2$, the result follows from Proposition~\ref{q+free_general}, so
let us suppose that $q < 2$. Suppose there exists a word $w$ over
$\{a,b,c\}$ that is $q^+$-free and highly $q$-repetitive. Then, any factor of $w$
is \emph{left-special} (i.e., has two left extensions). Indeed, let $u$ be a
factor of $w$, and let $i$ denote its position in $w$. $w$ is
\emph{recurrent} (every factor occurs infinitely often) because it is highly repetitive, so we can suppose $i \geq 1$. There is a long enough $q$-repetition $v$ beginning at position $i$. We denote its period by $p$. Then, $u$ is repeated in the excess of $v$: $pu$ is a factor of $v$. Now, let $x_1 = w_{i-1}$ and $x_2=p_{|p|}$. It is clear that $x_1 \neq x_2$, since otherwise, $x_1v$ would be a $q^+$-repetition, which is impossible since $w$ is $q^+$-free. So $u$ has two left extensions. Moreover, as the factors $aa$, $bb$ and $cc$ are clearly forbidden, we can see that $w$ contains the factor $abab$ (by extending $b$ on the left). But $abab$ is a square, which contradicts the fact that $w$ is $q^+$-free.
\end{proof}
\begin {theorem}
There exists an infinite ternary word which is both $2$-free and highly $7/4$-repetitive.
\end{theorem}
\begin {proof}
We use the morphism of Brandenburg, which is a square-free morphism:
\begin{eqnarray*}
\mu_B : \begin{cases}
a \mapsto abacbabcbac \\
b \mapsto abacbcacbac \\
c \mapsto abcbabcacbc. \\
\end{cases}
\end{eqnarray*}
We use it to give a similar construction as in the proofs of Theorems \ref{high_rep_bin} and \ref{high_rep_ter}. We consider the sequence:
\begin{eqnarray*}
A_0& =& cbac \mu_B(cbc)abac = cbacabcbabcacbcabacbcacbacabcbabcacbcabac\\
A_1& =& (u)^{-1}\mu_B^3(A_0) \\
&\vdots& \\
A_n&=& (u)^{-1}\mu_B^3(A_{n-1}) ,\\
\end{eqnarray*}
where $u=\mu_B^2(a)\mu_B (ab)abacbab$.
The sequence $A_n$ converges to a limit we denote by $w$, which is a
square-free word because $\mu_B$ is square-free. For any $n\geq 1$,
if we denote by $p_n$ the word $\mu_{B}^{3(n-1)}(u) \cdots \mu_{B}^3(u) u$, we can see that $A_n = (p_n)^{-1}\mu_B^{3n}(A_0)$. But $p_n$ is a prefix of $\mu_B^{3n}(c)$, since
\begin{eqnarray*}
|p_n| & = & |u| \sum_{i = 0}^{n-1} |\mu_{B}(a)|^{3i}\\
& = & |u|\sum_{i = 0}^{n-1} 11^{3i}\\
& < & 11^{3n} = |\mu_B^{3n}(c)|.
\end{eqnarray*}
So, we can write $\mu_B^{3n}(c) = p_n s_n$, where $s_n$ is a ternary word.
Then, for any $n \geq 1 $,
\begin{eqnarray*}
A_n &=&(p_n)^{-1} \mu_{B}^{3n}(A_0)\\
& = &s_n \mu_{B}^{3n}(bac abc bab cac bca ba) p_n s_n \mu_{B}^{3n}(bca) p_n s_n \mu_{B}^{3n}(bac abc bab cac bca ba) p_n s_n .
\end{eqnarray*}
It follows that at all positions $0 \leq j \leq |s_n|$, there begins a repetition with period a conjugate of $s_n \mu_{B}^{3n}(bac abc bab cac bca ba) p_n s_n \mu_{B}^{3n}(bca) p_n$, and of length
\begin{eqnarray*}
l & = & |s_n \mu_{B}^{3n}(bac abc bab cac bca ba) p_n s_n \mu_{B}^{3n}(bca) p_n s_n\mu_{B}^{3n}(bac abc bab cac bca ba) p_n | \\
& = & 40\cdot 11^{3n} .
\end{eqnarray*}
These repetitions have exponents $40/22=20/11 \geq 7/4$. As $n$ can be taken arbitrarily large, the result follows.
\end{proof}
\begin{remark}
In fact, with this proof, we have the result: There exists an infinite $2$-free ternary word which is highly $20/11$-repetitive.
\end{remark}
So the problem of finding the infimum of the real numbers $\alpha$ such that there exists an infinite ternary $\alpha^+$-free word which is highly $7/4$-repetitive is open. We proved that this infimum is between $7/4$ and $2$.
\section{Weaker results on ternary words}\label{weak ternary}
In the following section, we will prove some weaker results for words over the ternary alphabet. First, instead of considering highly repetitive words, we consider words with powers at every position. Then, we will discuss words containing infinitely many powers, but not necessary at every position. These questions were asked at the end of \cite{cr} by Currie and Rampersad.
The following results concern Dejean's morphism $\mu_D$ and its behaviour
regarding repetitions and synchronizing properties, and were proved in
\cite{vas}. If $v$ is a word, we denote by $\delta$ the application
that removes the first letter of $v$ (and so, $\delta^t(v)$ removes
the first $t$ letters of $v$). Moreover, we denote by $\mathfrak{F}_D$
the set $\textup{Fact}(\mu_D(\{a,b,c\}^*))$ of factors of $\mu_D(\{a,b,c\}^*)$.
\begin{lemma}[\cite{vas}]\label{evite}
Let $\alpha \in ]7/4,2[$ be given. Let $s$, $t$ be natural numbers
such that $\mu_D^s(b)=xabcbabcy$, with $|x|=t$. Let $\beta = 2-
\frac{t}{4\cdot 19^s}$. Suppose that $7/4 < \beta < \alpha$, and that $abcbabcv \in \mathfrak{F}_D$ is $\alpha$-free. Consider the word $w=\delta^t \mu_D^s (babcbabcv)$. Then, we have:
\begin{enumerate}
\item[1.] $w$ has a prefix with exponent $\beta$.
\item[2.] If $abcbabcv$ has a factor with exponent $\gamma$ and period $p$, then, $w$ has a factor with exponent $\gamma$ and a period of length $19^s|p|$.
\item[3.] $w$ is $\alpha$-free.
\end{enumerate}
\end{lemma}
\begin{definition}[\cite{vas}]\label{obtainable}
A real number $\beta < \alpha$ is said to be \emph{obtainable} if $\beta$
can be written as $\beta=2-\frac{t}{4\cdot 19^s}$, where the natural numbers $s$ and $t$ satisfy:\begin{enumerate}
\item[*] $s \geq 3$
\item[*] the word $\delta^t(\mu_D^s(b))$ begins with $abcbabc$.
\end{enumerate}
\end{definition}
We note that for any given $s \geq 3$, it is possible to choose $t$ such that
\begin{enumerate}
\item[*] $7/4 < \beta = 2-\frac{t}{4\cdot 19^s}< \alpha$
\item[*] $|\alpha - \beta| \leq \frac{19^2}{4\cdot 19^s}$.
\end{enumerate}
Indeed, $\mu_D^2(a)$, $\mu_D^2(b)$, and $\mu_D^2(c)$ have length $19^2$, and each has $abcbabc$ as a factor. Therefore, choosing a large enough $s$, we can always find some obtainable real numbers $\beta$ arbitrarily close to $\alpha$.
\begin{theorem}\label{every position}
For every real number $\alpha > 7/4$, there exists an infinite $\alpha$-free ternary word that contains $7/4$-powers beginning at every position.
\end{theorem}
\begin{proof}
Theorem 3.4 in \cite{cr} established the result for any $\alpha > 2$. Let us consider $7/4 < \alpha \leq 2$. Let $\beta $ be an obtainable number (see Definition~\ref{obtainable}), that is, it can be written as:
$$\beta = 2 - \frac{t}{4\cdot 19^s}, $$
where $s \geq 3$, and $\delta^t \mu_D^s (b)$ begins with $abcbabc$.
For any word $v$ in $ \mathfrak{F}_D$, we denote by $\Phi(v)$ the word $\delta^t \mu_D^s (bv)$ (we recall that $\delta(u)$, for some word $u$, removes the first letter of $u$) and we consider the sequence:
\begin{eqnarray*}
v_1 &=& \Phi(abcbabc) = \delta^t \mu_D^s (babcbabc)\\
v_2 &=& \Phi(v_1) = \delta^t \mu_D^s (b\delta^t\mu_D^s(babcbabc))\\
&\vdots&\\
v_n &=& \Phi(v_{n-1}) \\
&\vdots&
\end{eqnarray*}
Let $w = \lim v_n$ (possible because each $v_i$ is clearly a prefix of $v_{i+1}$). By iteration of Lemma~\ref{evite}, as $abcbabc$ is $\alpha$-free, each $v_i$ is $\alpha$-free, and then $w$ is $\alpha$-free.
For any $n\geq 0$, $w$ begins with a prefix of the form
$$\delta^t\mu_D^s(b) \mu_D^s(\delta^t\mu_D^s(b)) \cdots \mu_D^{ns}(\delta^t\mu_D^s(b)) \mu_D^{(n+1)s}(abcbabc) .$$
Thus, $w$ contains the word $\mu_D^{ns}(\delta^t(\mu_D^s(b)) \mu_D^{(n+1)s}(abcbabc)$ at position
\begin{eqnarray*}
p_n& = &|\delta^t\mu_D^s(b) \mu_D^s(\delta^t\mu_D^s(b)) \cdots \mu_D^{(n-1)s}(\delta^t\mu_D^s(b))|\\
&=& \sum_{i=1}^{n} |\mu_D^{is}(b)| - \sum_{i=0}^{n-1} t\cdot 19^{is}\\
&=& (19^s -t) \sum_{i=0}^{n-1} 19^{is}\\
&=&(19^s -t) \frac{19^{ns}-1}{19^s -1}
\end{eqnarray*}
Moreover, the word $\mu_D^{ns}(\delta^t\mu_D^s(b))
\mu_D^{(n+1)s}(abcbabc)$ contains $7/4$-powers at every position
between $1$ and $q_n =|\mu_D^{ns}(\delta^t \mu_D^s(b))| = (19^s
-t)\cdot 19^{ns}$. So, in $w$, there is a $7/4$-repetition starting at every position $j$, for every $j \in [ p_n, p_n + q_n -1 ]$. Since $p_{n+1} = p_n + q_n$, every position $j$ in $\mathbb{N}$ is reached.
\end{proof}
\begin{theorem}
For every real number $\alpha \geq 7/4$ there exists a real number $\beta$, with $7/4 \leq \beta < \alpha$, arbitrarily close to $\alpha$, such that there is an infinite $\beta ^+$-free ternary word containing infinitely many $\beta$-powers.
\end{theorem}
\begin{proof}
Theorem 3.4 in \cite{cr} established the result for any $\alpha > 2$. Let us consider $7/4 < \alpha \leq 2$. Let $\beta $ be an obtainable number, that is, it can be written as:
$$\beta = 2 - \frac{t}{4\cdot 19^s}, $$
where $s \geq 3$, and $\delta^t \mu_D^s (b)$ begins with $abcbabc$.
Similarly to the proof of Theorem~\ref{every position}, we consider the sequence:
\begin{eqnarray*}
v_1 &=& \Phi(abcbabc) = \delta^t \mu_D^s (babcbabc)\\
v_2 &=& \Phi(v_1) = \delta^t \mu_D^s (b\delta^t\mu_D^s(babcbabc))\\
&\vdots&\\
v_n &=& \Phi(v_{n-1}) \\
&\vdots&
\end{eqnarray*}
Let $w = \lim v_n$. The word $w$ is $\alpha$-free, and it is $\beta^+$-free,
since $\beta < \alpha$. Moreover, for any $n\geq 1$, $w$ contains
the word $\mu_D^{ns}(\delta^t\mu_D^s(babcbabc))$, which has length
$19^{ns}(8\cdot 19^s - t)$ and exponent $\beta$.
\end{proof}
\section{Conclusion}
We propose the following definition. For an integer $k$, consider the set
\begin{eqnarray*}
\mathfrak{S}_k & = &\{(\alpha, \beta) \in \mathbb{R}^2 : \textup{there
exists a word in }\{0,1,\ldots,k-1\}^{\omega}\textup{ which is }\alpha\textup{-free
and} \\
& & \textup{highly }\beta\textup{-repetitive}\} .
\end{eqnarray*}
The combined results of Currie and Rampersad \cite{cr}, and of Sections \ref{binary} and \ref{ternary} of this paper, give a partial desciption of $\mathfrak{S}_k$ for $k=2$ and $k=3$. We believe it is reasonable to expect the sets $\mathfrak{S}_k$, for $k=2$ and $k\geq 3$, to be as described respectively in Figure \ref{fig_bin} and \ref{fig_tern}. Proving this would be an interesting continuation of this work, as it is obviously related to important open problems about critical exponents of morphic words.
\begin{figure}[hb]
\begin{center}
\begin{tikzpicture}[scale=1.7]
\filldraw[black!20] (2,0) rectangle (4,2) ;
\filldraw[black!20] (7/3,7/3)--(4,7/3)--(4,4) ;
\filldraw[black!20] (7/3,2) rectangle (4,7/3) ;
\draw[->] (0,0) -- node [very near end,xshift=-0.2cm] {$\beta$} (0,4);
\draw[->] (0,0) -- node [very near end,yshift=-0.2cm] {$\alpha$} (4,0);
\node[pin=below:$2$, yshift=+0.35cm] at (2,0) {};
\node[pin=below:$\frac{7}{3}$, yshift=+0.35cm] at (7/3,0) {};
\node[pin=left:$2$, xshift=+0.35cm] at (0,2) {};
\node[pin=left:$\frac{7}{3}$, xshift=+0.35cm] at (0,7/3) {};
\draw[dashed] (2,0) -- (2,2);
\draw[dashed] (7/3,7/3) -- (4,4);
\draw[dashed] (2,2) -- (7/3,2);
\draw[dashed] (7/3,2) -- (7/3,7/3);
\end{tikzpicture}
\caption{Conjecture for $k=2$ ($\mathfrak{S}_2$ in grey.)}
\label{fig_bin}
\end{center}
\end{figure}
\begin{figure}
\begin{center}
\begin{tikzpicture}[scale=1.7]
\filldraw[black!20] (7/5,0) rectangle (4,7/5) ;
\filldraw[black!20] (7/5,7/5)--(4,7/5)--(4,4) ;
\draw[->] (0,0) -- node [very near end,xshift=-0.2cm] {$\beta$} (0,4);
\draw[->] (0,0) -- node [very near end,yshift=-0.2cm] {$\alpha$} (4,0);
\node[pin=below:$2$, yshift=+0.35cm] at (2,0) {};
\node[pin=below:$RT(k)$, yshift=+0.35cm] at (7/5,0) {};
\node[pin=left:$RT(k)$, xshift=+0.35cm] at (0,7/5) {};
\draw[dashed] (7/5,0) -- (7/5,7/5);
\draw[dashed] (7/5,7/5) -- (4,4);
\end{tikzpicture}
\caption{Conjecture for $k\geq 3$ ($\mathfrak{S}_k$ in grey.)}
\label{fig_tern}
\end{center}
\end{figure}
\newpage
\begin{thebibliography}{11}
\bibitem[BRA]{bra} F. J. Brandenburg, Uniformly growing $k$-th powerfree
homomorphisms, \textit{Theoret. Comput. Sci.} {\bf 23} (1983), 69--82.
\bibitem[CR]{cr} J. Currie and N. Rampersad, Infinite words containing
squares at every position, \textit{Theor. Inform. Appl.} {\bf 44}
(2010), 113--124.
\bibitem[CRS]{crs} J. Currie, N. Rampersad, and J. Shallit, Binary words containing infinitely many overlaps, \textit{Electron. J. Combinatorics} {\bf 13} (2006), \#R82.
\bibitem[DEJ]{dej} F. Dejean, Sur un th\'eor\`eme de Thue, \textit{J. Combin. Theory Ser. A } {\bf 13} (1972), 90--99.
\bibitem[DEK]{dek} F. M. Dekking, On repetitions in binary sequences,
\textit{J. Comb. Theory Ser. A} {\bf 20} (1976), 292--299.
\bibitem[ILI]{ili} L. Ilie, A note on the number of squares in a word,
\textit{Theoret. Comput. Sci.} {\bf 380} (2007), 373--376.
\bibitem[KRI]{kri} D. Krieger, Critical exponents and stabilizers of
infinite words. Ph.D.\ thesis, University of Waterloo, 2008.
\bibitem[RIC]{ric} G. Richomme. Personal communication, 2005.
\bibitem[SAA]{saa} K. Saari, Everywhere $\alpha$-repetitive
sequences and Sturmian words, \textit{Europ. J. Combin.} {\bf 31} (2010), 177--192.
\bibitem[SHU]{shu} A. M. Shur, The structure of the set of cube-free
$\mathbb{Z}$-words in a two-letter alphabet (Russian),
\emph{Izv. Ross. Akad. Nauk Ser. Mat.}
\textbf{64} (2000), 201--224. English translation in \emph{Izv. Math.}
\textbf{64} (2000), 847--871.
\bibitem[TH2]{th2} A. Thue, \"Uber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, \textit{Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiana No.10} (1912), 1--67.
\bibitem[VAS]{vas} E. Vaslet, Critical exponents of words over $3$
letters, \textit{Electron. J. Combinatorics} {\bf 18} (2011), P125.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}: Primary
68R15.
\noindent \emph{Keywords:} repetition, Thue-Morse word, critical exponent.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequence \seqnum{A010060}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received June 28 2012;
revised version received November 12 2012.
Published in {\it Journal of Integer Sequences}, March 2 2013.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}
~~