\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}