\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\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}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\underline{#1}}}
\usepackage{cite}
\usepackage[multiple]{footmisc}
\usepackage{enumitem}
\setlist[enumerate]{label={\textnormal{(\roman*)}}}
\renewcommand{\tt}[1]{\texttt{#1}}
\DeclareMathOperator{\Fact}{Fact}
\DeclareMathOperator{\Stab}{Stab}
\DeclareMathOperator{\RT}{RT}
\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
The Number of Threshold Words on $n$ \\
\vskip .1in
Letters Grows Exponentially for Every $n\geq 27$
}
\vskip 1cm
\large
James~D.~Currie\footnote{The work of James D. Currie is supported by the Natural Sciences and Engineering Research Council of Canada (NSERC), [funding reference number 2017-03901].}, Lucas~Mol, and Narad~Rampersad\footnote{The work of Narad Rampersad is supported by the Natural Sciences and Engineering Research Council of Canada (NSERC), [funding reference number 2019-04111].} \\
Department of Mathematics and Statistics\\
University of Winnipeg\\
515 Portage Avenue\\
Winnipeg, MB R3B 2E9\\
Canada\\
\href{mailto:j.currie@uwinnipeg.ca}{\tt j.currie@uwinnipeg.ca} \\
\href{mailto:l.mol@uwinnipeg.ca}{\tt l.mol@uwinnipeg.ca} \\
\href{mailto:n.rampersad@uwinnipeg.ca}{\tt n.rampersad@uwinnipeg.ca}
\end{center}
\begin{abstract}
For every $n\geq 27$, we show that the number of $n/(n-1)^+$-free words (i.e., threshold words) of length $k$ on $n$ letters grows exponentially in $k$. This settles all but finitely many cases of a conjecture of Ochem.
\end{abstract}
\section{Introduction}
Throughout, we use standard definitions and notations from combinatorics on words (see~\cite{LothaireAlgebraic}). A \emph{square} is a word of the form $xx$, where $x$ is a nonempty word. A \emph{cube} is a word of the form $xxx$, where $x$ is a nonempty word. An \emph{overlap} is a word of the form $axaxa$, where $a$ is a letter and $x$ is a (possibly empty) word. The study of words goes back to Thue, who demonstrated the existence of an infinite overlap-free word over a binary alphabet, and an infinite square-free word over a ternary alphabet (see~\cite{Berstel1995}).
A language is a set of finite words over some alphabet $A$. The \emph{combinatorial complexity} of a language $L$ is the sequence $C_L:\mathbb{N}\rightarrow\mathbb{N}$, where $C_L(k)$ is defined as the number of words in $L$ of length $k$. We say that a language $L$ \emph{grows} exactly as the sequence $C_L(k)$ grows, be it exponentially, polynomially, etc.
Since the work of Brandenburg~\cite{Brandenburg1983}, the study of the growth of languages has been a central theme in combinatorics on words. Given a language $L$, a key question is whether it grows exponentially (fast), or subexponentially (slow). Brandenburg~\cite{Brandenburg1983} demonstrated that both the language of cube-free words over a binary alphabet, and the language of square-free words over a ternary alphabet, grow exponentially. On the other hand, Restivo and Salemi~\cite{RestivoSalemi1985} demonstrated that the language of overlap-free binary words grows only polynomially.
Squares, cubes, and overlaps are all examples of \emph{repetitions} in words, and can be considered in the same general framework. Let $w=w_1w_2\cdots w_k$ be a finite word, where the $w_i$'s are letters. A positive integer $p$ is a \emph{period} of $w$ if $w_{i+p}=w_i$ for all $1\leq i\leq k-p$. In this case, we say that $|w|/p$ is an \emph{exponent} of $w$, and the largest such number is called \emph{the} exponent of $w$. For a real number $r>1$, a finite or infinite word $w$ is called $r$-free ($r^+$-free) if $w$ contains no finite factors of exponent greater than or equal to $r$ (strictly greater than $r$, respectively).
Throughout, for every positive integer $n$, let $A_n$ denote the $n$-letter alphabet $\{\tt{1},\tt{2},\dots,\tt{n}\}$. For every $n\geq 2$, the \emph{repetition threshold} for $n$ letters, denoted $\RT(n)$, is defined by
\[
\RT(n)=\inf\{r>1\colon\ \text{there is an infinite $r^+$-free word over $A_n$}\}.
\]
Essentially, the repetition threshold describes the border between avoidable and unavoidable repetitions in words over an alphabet of $n$ letters. The repetition threshold was first defined by Dejean~\cite{Dejean1972}. Her 1972 conjecture on the values of $\RT(n)$ has now been confirmed through the work of many authors~\cite{Dejean1972,Pansiot1984,MoulinOllagnier1992,MohammadNooriCurrie2007,Carpi2007,CurrieRampersad2009,CurrieRampersad2009Again,CurrieRampersad2011,Rao2011}:
\[
\RT(n)=\begin{cases}
2, &\text{ if $n=2$};\\
7/4, & \text{ if $n=3$};\\
7/5, & \text{ if $n=4$};\\
n/(n-1), & \text{ if $n\geq 5$.}
\end{cases}
\]
The last cases of Dejean's conjecture were confirmed in 2011 by the first and third authors~\cite{CurrieRampersad2011}, and independently by Rao~\cite{Rao2011}. However, probably the most important contribution was made by Carpi~\cite{Carpi2007}, who confirmed the conjecture in all but finitely many cases.
In this short note, we are concerned with the growth rate of the language of \emph{threshold words} over $A_n$. For every $n\geq 2$, let $T_n$ denote the language of all $\RT(n)^+$-free words over $A_n$. We call $T_n$ the \emph{threshold language} of order $n$, and we call its members \emph{threshold words} of order $n$. Threshold words are also called \emph{Dejean words} by some authors. For every $n\geq 2$, the threshold language $T_n$ is the minimally repetitive infinite language over $A_n$.
The threshold language $T_2$ is exactly the language of overlap-free words over $A_2$, which is known to grow only polynomially~\cite{RestivoSalemi1985}.\footnote{Currently the best known bounds on $C_{T_2}(k)$ are due to Jungers et al.~\cite{JungersProtasovBlondel2009}.}\footnote{The threshold between polynomial and exponential growth for repetition-free binary words is known to be $7/3$~\cite{KarhumakiShallit2004}. That is, the language of $7/3$-free words over $A_2$ grows polynomially, while the language of $7/3^+$-free words over $A_2$ grows exponentially.} However, Ochem made the following conjecture about the growth of threshold languages of all other orders.
\begin{conjecture}[Ochem~\cite{Ochem2006}]
\label{OchemConjecture}
For every $n\geq 3$, the language $T_n$ of threshold words of order $n$ grows exponentially.
\end{conjecture}
Conjecture~\ref{OchemConjecture} has been confirmed for $n\in\{3,4\}$ by Ochem~\cite{Ochem2006}, for $n\in\{5,6,\dots,10\}$ by Kolpakov and Rao~\cite{KolpakovRao2011}, and for all odd $n$ less than or equal to $101$ by Tunev and Shur~\cite{TunevShur2012}. In this note, we confirm Conjecture~\ref{OchemConjecture} for every $n\geq 27$.
\begin{theorem}\label{main}
For every $n\geq 27$, the language $T_n$ of threshold words of order $n$ grows exponentially.
\end{theorem}
The layout of the remainder of the note is as follows. In Section~\ref{Review}, we summarize the work of Carpi~\cite{Carpi2007} in confirming all but finitely many cases of Dejean's conjecture. In Section~\ref{Construction}, we establish Theorem~\ref{main} with constructions that rely heavily on the work of Carpi.
We conclude with a discussion of problems related to the rate of growth of threshold languages.
\section{Carpi's reduction to \boldmath{$\psi_n$}-kernel repetitions}\label{Review}
In this section, let $n\geq 2$ be a fixed integer. Pansiot~\cite{Pansiot1984} was first to observe that if a word over the alphabet $A_n$ is $(n-1)/(n-2)$-free, then it can be encoded by a word over the binary alphabet $B=\{\tt{0},\tt{1}\}$. For consistency, we use the notation of Carpi~\cite{Carpi2007} to describe this encoding. Let $\mathbb{S}_n$ denote the symmetric group on $A_n$, and define the morphism $\varphi_n:B^*\rightarrow \mathbb{S}_n$ by
\begin{align*}
\varphi_n(\tt{0})&=\begin{pmatrix}
\tt{1} & \tt{2} & \cdots & \tt{n-1}
\end{pmatrix}; \text{ and}\\
\varphi_n(\tt{1})&=\begin{pmatrix}
\tt{1} & \tt{2} & \cdots & \tt{n}
\end{pmatrix}.
\end{align*}
Now define the map $\gamma_n:B^*\rightarrow A_n^*$ by
\[
\gamma_n(b_1b_2\cdots b_k)=a_1a_2\cdots a_k,
\]
where
\[
a_i\varphi_n(b_1b_2\cdots b_i)=\tt{1}
\]
for all $1\leq i\leq k$. To be precise, Pansiot proved that if a word $\alpha\in A_n^*$ is $(n-1)/(n-2)$-free, then $\alpha$ can be obtained from a word of the form $\gamma_n(u)$, where $u\in B^*$, by renaming the letters.
Let $u\in B^*$, and let $\alpha=\gamma_n(u)$. Pansiot showed that if $\alpha$ has a factor of exponent greater than $n/(n-1)$, then either the word $\alpha$ itself contains a \emph{short repetition}, or the binary word $u$ contains a \emph{kernel repetition} (see~\cite{Pansiot1984} for details). Carpi reformulated this statement so that both types of forbidden factors appear in the binary word $u$. Let $k\in\{1,2,\dots,n-1\}$, and let $v\in B^+$. Then $v$ is called a \emph{$k$-stabilizing word} (of order $n$) if $\varphi_n(v)$ fixes the points $\tt{1},\tt{2},\dots,\tt{k}$. Let $\Stab_n(k)$ denote the set of $k$-stabilizing words of order $n$. The word $v$ is called a \emph{kernel repetition} (of order $n$) if it has period $p$ and a factor $v'$ of length $p$ such that $v'\in \ker(\varphi_n)$ and $|v|>\frac{np}{n-1}-(n-1)$.
Carpi's reformulation of Pansiot's result is the following.
\begin{proposition}[Carpi~{\cite[Proposition~3.2]{Carpi2007}}]
\label{CarpiReform}
Let $u\in B^*$. If a factor of $\gamma_n(u)$ has exponent larger than $n/(n-1)$, then $u$ has a factor $v$ satisfying one of the following conditions:
\begin{enumerate}
\item $v\in \Stab_n(k)$ and $0<|v|0$. Set $|v|=4^bc$, where $4^b$ is the maximal power of $4$ dividing $|v|$. Suppose, towards a contradiction, that $b\leq m-2$. Since $v\in\ker(\psi_n)$, by Lemma~\ref{Carpi4}, we see that $4$ divides $|v|$, meaning $b\geq 1$.
Write $z=z_1z_2\cdots z_{|z|}$. Then we have $v=z_iz_{i+1}\cdots z_{i+4^bc-1}$ for some $i\geq 1$. By definition, for any $j\geq 1$, we have $z_j\geq b+2$ if and only if $4^b$ divides $j$. (Since $b\geq 1$, we have $b+2\geq 3$, and hence $z_j\geq b+2$ implies $j\equiv 0$ (mod $4$).) Thus, we have that the sum $\sum_{a=b+2}^{m}|v|_a$ is exactly the number of integers in the set $\{i,i+1,\dots,i+4^bc-1\}$ that are divisible by $4^b$, which is exactly $c$. Since $v\in \ker(\psi_n)$, by Lemma~\ref{Carpi4}, we conclude that $4$ divides $c$, contradicting the maximality of $b$.
\end{proof}
Now, using Lemma~\ref{Analogous} in place of~\cite[Lemma~9.3]{Carpi2007}, a proof strictly analogous to that of~\cite[Proposition~9.4]{Carpi2007} gives the following. The only tool in the proof that we have not covered here is~\cite[Lemma~9.2]{Carpi2007}, which is a short technical lemma about the repetitions in the word $\beta$, and which can be used without any modification.
\begin{proposition}\label{zeta}
Suppose that $n\geq 33$. Then no word $z\in Z_m$ contains a $\psi_n$-kernel repetition.
\end{proposition}
\subsection{Case II: $27\leq n\leq 32$}
In this case, we have $m=4$. For any set $X$, we let $2^X$ denote the power set of $X$. So in particular, the set $2^{A_4^*}$ consists of all sets of finite words over $A_4$. For alphabets $\Sigma$ and $\Delta$, a \emph{substitution} is a map $s:\Sigma^*\rightarrow 2^{\Delta^*}$ such that $s(xy)=s(x)s(y)$ for all $x,y\in \Sigma^*$ and $s(\varepsilon)=\{\varepsilon\}$.
Define a substitution $g:A_4^*\rightarrow 2^{A_4^*}$ by
\begin{align*}
g(\tt{1})&=\{\tt{112}\}\\
g(\tt{2})&=\{\tt{114}\}\\
g(\tt{3})&=\{\tt{113}\}\\
g(\tt{4})&=\{\tt{123},\tt{213}\}.
\end{align*}
We extend $g$ to $2^{A_4^*}$ by $g(W)=\bigcup_{w\in W}g(w)$, which allows us to iteratively apply $g$ to an initial word in $A_4^*$. Let $Z_4=\Fact\{v\colon\ \text{$v\in g^n(\tt{1})$ for some $n\geq 1$}\}$, i.e., we have that $Z_4$ is the set of factors of all words obtained by iteratively applying $g$ to the initial word $\tt{1}$.
For a word $w\in A_4^*$, let $\pi(w)$ denote the \emph{Parikh vector} of $w$, defined by
\[
\pi(w)=\begin{bmatrix}
|w|_\tt{1} & |w|_\tt{2} & |w|_\tt{3} & |w|_\tt{4}
\end{bmatrix}^T
\]
Note that for every $a\in A_4$ and every $x,y\in g(a)$, we have $\pi(x)=\pi(y)$. Thus, we may let $\pi_g(a)$ denote the common Parikh vector of every word in $g(a)$. The \emph{frequency matrix} $M_g$ of $g$ is then the $4\times 4$ matrix defined by
\[
(M_g)_{ij}=(\pi_g(j))_{i}
\]
i.e., the $j$th column of $M_g$ is the Parikh vector of every word in $g(j)$. Explicitly, we have
\[
M_g=\begin{bmatrix}
2 & 2 & 2 & 1\\
1 & 0 & 0 & 1\\
0 & 0 & 1 & 1\\
0 & 1 & 0 & 0
\end{bmatrix}.
\]
Evidently, if $v\in g(u)$, then we have $\pi(v)=M_g\pi(u)$. Note also that $M_g$ is invertible modulo $4$, with
\[
M_g^{-1}=\begin{bmatrix}
3 & 3 & 2 & 2\\
0 & 0 & 0 & 1\\
3 & 2 & 3 & 2\\
1 & 2 & 2 & 2
\end{bmatrix}.
\]
This fact is the key to the proof of the following lemma.
\begin{lemma}\label{Invertible}
Let $u\in A_4^*$ be a word, and let $v\in g(u)$. If $v\in \ker(\psi_n)$, then $u\in \ker(\psi_n)$.
\end{lemma}
\begin{proof}
By Lemma~\ref{Carpi4}, for every word $w\in A_4^*$, we have $w\in \ker(\psi_n)$ if and only if $\pi(w)\equiv \mathbf{0}$ (mod $4$).
Now suppose that $v\in \ker(\psi_n)$. Then $\pi(v)\equiv \mathbf{0}$ (mod $4$). Since $v\in g(u)$, we have $\pi(v)=M_g\pi(u)$. It follows that $\pi(u)\equiv M_g^{-1}\pi(v)\equiv \mathbf{0}$ (mod $4$) as well, and thus we have $u\in\ker(\psi_n)$.
\end{proof}
If a word $w\in A_4^*$ has period $p$ and the length $p$ prefix of $w$ is in $\ker(\psi_n)$, then we say that $p$ is a \emph{kernel period} of $w$.
\begin{proposition}\label{m4}
Suppose that $27\leq n\leq 32$. Then no word in $Z_4$ contains a $\psi_n$-kernel repetition.
\end{proposition}
\begin{proof}
Suppose otherwise that the word $v_0\in Z_4$ is a $\psi_n$-kernel repetition. Write $v_0=x_0y_0$, where $v_0$ has kernel period $|x_0|$. From the definition of $\psi_n$-kernel repetition, we must have
\[
(n-1)(|v_0|+1)\geq n|x_0|-3,
\]
or equivalently,
\[
|x_0|\leq (n-1)|y_0|+n+2.
\]
Since $n\leq 32$, we certainly have
\begin{align}\label{psikernelcondition}
|x_0|\leq 31|y_0|+34.
\end{align}
If $|y_0|\leq 3$, then we have $|x_0|\leq 127$, and hence $|v_0|\leq 130$. We eliminate this possibility by exhaustive search, so we may assume that $|y_0|\geq 4$.
Let $z$ be the length $3$ prefix of $y_0$. By inspection of all words in $Z_4$ of length $3$, there is a unique factorization $z=z'z''$, where $z'$ is a nonempty suffix of some word in $g(A_4)$, and $z''$ is a (possibly empty) prefix of some word in $g(A_4)$. Since $y_0$ is a prefix of $x_0y_0$, it must be the case that $z$ is a prefix of $x_0$. Write $x_0z=z'z''x_0'z'z''$. Then we must have $z''x_0'z'\in g(A_4^*)$, and hence $|x_0|=|z''x_0'z'|$ is a multiple of $3$.
Now write $v_0=s_0v'_0p_0$ for some suffix $s_0$ of a word in $g(A_4)$, some prefix $p_0$ of a word in $g(A_4)$, and some word $v'_0\in g(v_1)$, where $v_1\in Z_4$. Since $|s_0|\leq 2$ and $|p_0|\leq 2$, we have $|v'_0|\geq|v_0|-4\geq |x_0|$, and hence $v'_0$ has kernel period $|x_0|$. Now write $v_1=x_1y_1$, where $3|x_1|=|x_0|$. Evidently, we have $3|y_1|+4\geq |y_0|$. Note that $v_1$ has period $|x_1|$. Further, by Lemma~\ref{Invertible}, we have $x_1\in \ker(\psi_n)$, and hence $|x_1|$ is a kernel period of $v_1$.
We may now repeat the process described above. Eventually, for some $r\geq 1$, we reach a word $v_r\in Z_4$ that can be written $v_r=x_ry_r$, where $|x_r|$ is a kernel period of $v_r$, and $|y_r|\leq 3$. For all $1\leq i\leq r$, one proves by induction that $|x_0|=3^i|x_i|$ and $|y_0|\leq 3^i|y_i|+4\sum_{j=0}^{i-1}3^j=3^i|y_i|+2(3^i-1)$.
Thus, from (\ref{psikernelcondition}), we obtain
\begin{align*}
3^i|x_i|\leq 31\left[3^i|y_i|+2(3^i-1)\right]+34
\end{align*}
for all $1\leq i\leq r$.
Dividing through by $3^i$, and then simplifying, we obtain
\begin{align}\label{Bound}
|x_i|\leq 31\left[|y_i|+2\right]-\frac{28}{3^i}\leq 31\left[|y_i|+2\right]
\end{align}
for all $1\leq i\leq r$.
Since $|y_r|\leq 3$, we obtain $|x_r|\leq 155$ from (\ref{Bound}). By Lemma~\ref{Carpi4}, the kernel period $|x_r|$ of $v_r$ is a multiple of $4$, so in fact we have $|x_r|\leq 152$, and in turn $|v_r|\leq 155$. By exhaustive search of all words in $Z_4$ of length at most $155$, we find that $v_r\in W$, where $W$ is a set containing exactly $200$ words. Indeed, the set $W$ contains
\begin{itemize}
\item 160 words with kernel period 76 and length 77,
\item 36 words with kernel period 92 and length 93, and
\item 4 words with kernel period 112 and length 114.
\end{itemize}
For every $w\in W$, let
\[
E_w=\Fact\left(\{g(awb)\colon\ \text{$a,b\in A_4$, $awb\in Z_4$}\}\right).
\]
Evidently, we have $v_{r-1}\in E_{v_r}$. For every word $w\in W$, let $p_w$ denote the kernel period of $w$, and let $q_w$ denote the maximum length of a repetition with kernel period $3p_w$ across all words in $E_w$. By exhaustive check, for every $w\in W$, we find $3p_w> 31\left[q_w-3p_w+2\right]$. However, the word $v_{r-1}=x_{r-1}y_{r-1}$ must be in $E_{v_r}$, and by (\ref{Bound}), we have
\[
3p_{v_r}=|x_{r-1}|\leq 31\left[|y_{r-1}|+2\right]\leq 31\left[q_{v_r}-3p_{v_r}+2\right].
\]
This is a contradiction. We conclude that the set $Z_4$ contains no $\psi_n$-kernel repetitions.
\end{proof}
We now proceed with the proof of our main result.
\begin{proof}[Proof of Theorem~\ref{main}]
First suppose that $n\geq 33$. By Proposition~\ref{zeta}, no word $z\in Z_m$ contains a $\psi_n$-kernel repetition. From the definition of $Z_m$, one easily proves that
\[
C_{Z_m}(k)=\Omega\left(2^{k/4}\right).
\]
By Theorem~\ref{CarpiMain}, for every word $z\in Z_m$, the word $\gamma_n(f_n(z))$ is in the threshold language $T_n$ of order $n$. Moreover, the maps $\gamma_n$ and $f_n$ are injective, and $|\gamma_n(f_n(z))|/|z|=(n-1)(\ell+1)$, since $f_n$ is $(n-1)(\ell+1)$-uniform and $\gamma_n$ preserves length. It follows that
\[
C_{T_n}(k)=\Omega\left(2^{k/4(n-1)(\ell+1)}\right).
\]
Since $n$, and hence $\ell$, are fixed, the quantity $(n-1)(\ell+1)$ is a constant, and we conclude that the language $T_n$ grows exponentially.
Suppose now that $27\leq n\leq 32$. By Proposition~\ref{m4}, no word $z\in Z_4$ contains a $\psi_n$-kernel repetition. Since $|g^4(a)|\geq 4$ for all $a\in A_4$, we have
\[
C_{Z_4}(k)=\Omega\left(4^{k/81}\right).
\]
By the same argument as above, we see that
\[
C_{T_n}(k)=\Omega\left(4^{k/81(n-1)(\ell+1)}\right),
\]
and we conclude that the language $T_n$ grows exponentially.
\end{proof}
As pointed out by one of the anonymous referees, the constructions given in this section can also be used to demonstrate the existence of uncountably many infinite threshold words over $A_n$ for every $n\geq 27$.
\section{Conclusion}
Conjecture~\ref{OchemConjecture} has now been established for all $n\not\in\{12,14,\dots,26\}$. We remark that different techniques than those presented here will be needed to establish Conjecture~\ref{OchemConjecture} in all but one of these remaining cases. (It appears that the techniques presented here could potentially be used for $n=22$, but we do not pursue this isolated case.) For example, let $n=26$. Then we have $m=3$. By computer search, for every letter $a\in A_m$, the word $f_n(a\tt{3})$ contains a $15$-stabilizing word of length $350$, which is less than $15(n-1)=375$. By another computer search, the longest word on $\{\tt{1},\tt{2}\}$ avoiding $\psi_{n}$-kernel repetitions has length $15$. So there are only finitely many words in $A_m^*$ that avoid both $\psi_n$-kernel repetitions and the forbidden stabilizing words. Similar arguments lead to the same conclusion for all $n\in\{12,14,16,18,20,24\}$.
For a language $L$, the value
$\rho(L)=\limsup_{k\rightarrow\infty}(C_L(k))^{1/k}$
is called the \emph{growth rate} of $L$. If $L$ is factorial (i.e., closed under taking factors), then by an application of Fekete's lemma, we can safely replace $\limsup$ by $\lim$ in this definition. If $\rho(L)>1$, then the language $L$ grows exponentially, and in this case, $\rho(L)$ is a good description of how quickly the language grows.
For all $n\geq 33$, we have established that $\rho(T_n)\geq 2^{1/4(n-1)\left(\ell+1\right)}$. However, this lower bound tends to $1$ as $n$ tends to infinity, and this seems far from best possible. Indeed, Shur and Gorbunova proposed the following conjecture concerning the asymptotic behaviour of $\rho(T_n)$.
\begin{conjecture}[Shur and Gorbunova~\cite{ShurGorbunova2010}]
The sequence $\{\rho(T_n)\}$ of the growth rates of threshold languages converges to a limit $\hat{\rho}\approx 1.242$ as $n$ tends to infinity.
\end{conjecture}
A wide variety of evidence supports this conjecture -- we refer the reader to~\cite{ShurGorbunova2010,GorbunovaShur2011,Shur2014,Shur2012} for details. For a fixed $n$, there are efficient methods for determining upper bounds on $\rho(T_n)$ which appear to be rather sharp, even for relatively large values of $n$ (see~\cite{ShurGorbunova2010}, for example). Establishing a sharp lower bound on $\rho(T_n)$ appears to be a more difficult problem. We note that a good lower bound on $\rho(T_3)$ is given by Kolpakov~\cite{Kolpakov2007} using a method that requires some significant computation. For all $n\in\{5,6,\dots,10\}$, Kolpakov and Rao~\cite{KolpakovRao2011} give lower bounds for $\rho(T_n)$ using a similar method. They were then able to estimate the value of $\rho(T_n)$ with precision 0.005 using upper bounds obtained by the method of Shur and Gorbunova~\cite{ShurGorbunova2010}.
Thus, in addition to resolving the finitely many remaining cases of Conjecture~\ref{OchemConjecture}, improving our lower bound for $\rho(T_n)$ when $n\geq 27$ remains a significant open problem.
\section{Acknowledgments}
We thank the anonymous referees, whose comments and suggestions helped to improve the paper.
\begin{thebibliography}{10}
\bibitem{Berstel1995}
J.~Berstel, {Axel Thue's papers on repetitions in words: a translation}, in
{\em Publications du LaCIM}, Vol.~20, Universit{\'{e}} du Qu{\'{e}}bec
{\`{a}} Montr{\'{e}}al, 1995.
\bibitem{Brandenburg1983}
F.~J. Brandenburg, {Uniformly growing $k$-th power-free homomorphisms}, {\em
Theoret. Comput. Sci.} {\bf 23} (1983), 69--82.
\bibitem{Carpi2007}
A.~Carpi, {On Dejean's conjecture over large alphabets}, {\em Theoret. Comput.
Sci.} {\bf 385} (2007), 137--151.
\bibitem{CurrieRampersad2009Again}
J.~D. Currie and N.~Rampersad, {Dejean's conjecture holds for $n\geq 27$}, {\em
RAIRO---Theor. Inform. Appl.} {\bf 43} (2009), 775--778.
\bibitem{CurrieRampersad2009}
J.~D. Currie and N.~Rampersad, {Dejean's conjecture holds for $n\geq 30$}, {\em
Theoret. Comput. Sci.} {\bf 410} (2009), 2885--2888.
\bibitem{CurrieRampersad2011}
J.~D. Currie and N.~Rampersad, {A proof of Dejean's conjecture}, {\em Math.
Comp.} {\bf 80} (2011), 1063--1070.
\bibitem{Dejean1972}
F.~Dejean, {Sur un th{\'{e}}or{\`{e}}me de Thue}, {\em J. Combin. Theory Ser.
A} {\bf 13} (1972), 90--99.
\bibitem{GorbunovaShur2011}
I.~A. Gorbunova and A.~M. Shur, {On {P}ansiot words avoiding
3-repetitions}, in
{\em Proc. 8th Internat. Conf. Words 2011 (WORDS 2011)},
Electron. Proc. Theor. Comput. Sci., Vol.~63, 2012, pp.~138--146.
\bibitem{JungersProtasovBlondel2009}
R.~M. Jungers, V.~Y. Protasov, and V.~D. Blondel, {Overlap-free words and
spectra of matrices}, {\em Theoret. Comput. Sci.} {\bf 410} (2009),
3670--3684.
\bibitem{KarhumakiShallit2004}
J.~Karhum\"aki and J.~Shallit, {Polynomial versus exponential growth in
repetition-free binary words}, {\em J. Combin. Theory Ser. A} {\bf 105}
(2004), 335--347.
\bibitem{Kolpakov2007}
R.~Kolpakov, {Efficient lower bounds on the number of repetition-free words},
{\em J. Integer Sequences} {\bf 10} (2007), 1--16.
\bibitem{KolpakovRao2011}
R.~Kolpakov and M.~Rao, {On the number of Dejean words over alphabets of 5, 6,
7, 8, 9 and 10 letters}, {\em Theoret. Comput. Sci.} {\bf 412} (2011),
6507--6516.
\bibitem{LothaireAlgebraic}
M~Lothaire, {\em {Algebraic Combinatorics on Words}}, Cambridge University
Press, 2002.
\bibitem{MohammadNooriCurrie2007}
M.~Mohammad-Noori and J.~D. Currie, {Dejean's conjecture and Sturmian words},
{\em European J. Combin.} {\bf 28} (2007), 876--890.
\bibitem{MoulinOllagnier1992}
J.~Moulin-Ollagnier, {Proof of Dejean's conjecture for alphabets with 5, 6, 7,
8, 9, 10, and 11 letters}, {\em Theoret. Comput. Sci.} {\bf 95} (1992),
187--205.
\bibitem{Ochem2006}
P.~Ochem, {A generator of morphisms for infinite words}, {\em RAIRO---Theor.
Inform. Appl.} {\bf 40} (2006), 427--441.
\bibitem{Pansiot1984}
J.~J. Pansiot, {A propos d'une conjecture de F. Dejean sur les
r{\'{e}}p{\'{e}}titions dans les mots}, {\em Discrete Appl. Math.} {\bf 7}
(1984), 297--311.
\bibitem{Rao2011}
M.~Rao, {Last cases of Dejean's conjecture}, {\em Theoret. Comput. Sci.} {\bf
412} (2011), 3010--3018.
\bibitem{RestivoSalemi1985}
A.~Restivo and S.~Salemi, {Overlap free words on two symbols}, in M.~Nivat and
D.~Perrin, eds., {\em Automata on Infinite Words}, Lect. Notes in
Comput. Sci., Vol.~192, Springer-Verlag, 1985, pp.~198--206.
\bibitem{Shur2012}
A.~M. Shur, {Growth properties of power-free languages}, {\em Comput. Sci.
Rev.} {\bf 6} (2012), 187--208.
\bibitem{Shur2014}
A.~M. Shur, {Growth of power-free languages over large alphabets}, {\em Theory
Comput. Syst.} {\bf 54} (2014), 224--243.
\bibitem{ShurGorbunova2010}
A.~M. Shur and I.~A. Gorbunova, {On the growth rates of complexity of threshold
languages}, {\em RAIRO---Theor. Inform. Appl.} {\bf 44} (2010), 175--192.
\bibitem{TunevShur2012}
I.~N. Tunev and A.~M. Shur, {On two stronger versions of Dejean's conjecture},
in {\em Proc. 37th Internat. Conf. on Mathematical Foundations of Computer
Science (MFCS 2012)}, Lect. Notes in Comput. Sci., Vol.~7464, Springer, 2012, pp.~800--812.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}:
Primary 68R15.
\noindent \emph{Keywords: }
threshold word, repetition threshold, Dejean word, exponential growth,
Dejean's conjecture, Dejean's theorem.
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received November 13 2019;
revised version received February 21 2020.
Published in {\it Journal of Integer Sequences}, February 22 2020.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}