\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}{\rm \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 Two Infinite Words with \\ \vskip .1in Cubic Subword Complexity } \vskip 1cm \large Luke Schaeffer\\ Institute for Quantum Computing\\ University of Waterloo\\ Waterloo, ON N2L 3G1\\ Canada\\ \href{mailto:lrschaeffer@gmail.com}{\tt lrschaeffer@gmail.com}\\ \ \\ Kaiyu Wu\\ School of Computer Science \\ University of Waterloo\\ Waterloo, ON N2L 3G1\\ Canada\\ \href{mailto:k29wu@uwaterloo.ca}{\tt k29wu@uwaterloo.ca} \end{center} \vskip .2 in \def\suchthat{\, : \,} \begin{abstract} We consider two natural infinite words whose subword complexity is cubic, and determine their exact subword complexity. As a consequence, it follows that neither word is morphic. \end{abstract} \section{Introduction} In this paper we are concerned with words over a finite alphabet $\Sigma$. We say a word $y$ is a {\it subword} of a word $w$ if there exist (possibly empty) words $x, z$ such that $w = xyz$. For example, {\tt bank} is a subword of {\tt embankment}. The {\it subword complexity} (also called {\it factor complexity} or just {\it complexity}) of an infinite word $\bf w$ is the function $\rho_{\bf w} (n)$ that maps $n$ to the number of distinct subwords of length $n$ in $\bf w$. Subword complexity is a natural measure of the complexity of a word, and has been extensively studied (see, e.g., \cite{Cassaigne:1996,Mignosi:1989,Ehrenfeucht&Rozenberg:1981c,DBLP:journals/dm/Ferenczi99,DBLP:journals/tcs/FerencziK99,allouche1994}). We say that a morphism $h: \Sigma^* \rightarrow \Sigma^*$ is {\it prolongable} on a letter $a$ if $h(a) = ax$ for some word $x$ such that $h^i(x) \not= \epsilon$ for all $i \geq 0$. In this case, it is meaningful to define $h^\omega(a) := a \, x \, h(x) \, h^2(x) \, \cdots $, which is an infinite word that is a fixed point of the extension of $h$ to infinite sequences. A word of the form $h^\omega(a)$ is called {\it pure morphic}. A {\it coding} is a particular type of morphism that maps every letter to a word of length $1$. An infinite word $\bf w$ is said to be {\it morphic\/} if it can be expressed as the image, under a coding, of a morphic word. The class of morphic words has been widely studied (see, e.g., \cite[Chap.~7]{Allouche&Shallit:2003}). Pansiot \cite{Pansiot:1984a,Pansiot:1984b} classified the subword complexity of morphic words. He showed that pure morphic words have subword complexity $O(n^2)$, and thus all morphic words have subword complexity $O(n^2)$. A random infinite word will almost surely have exponential subword complexity, and hence is not morphic. However, there are not that many explicit examples of non-morphic words that are easy to write down. Recently Tim Smith \cite{smith:2020} introduced a class of infinite words which he called {\it zigzag words}. In this note we determine the exact subword complexities of two natural zigzag words and show they are cubic. These, then, provide additional natural examples of non-morphic words. \section{Definitions of words} Let $${\bf w}_1 = \prod_{i \ge 1}\ \prod_{j=1}^i a^{i-j+1}b^{j} = (ab)(aab\cdot abb)(aaab\cdot aabb\cdot abbb)\cdots$$ and $${\bf w}_2 = \prod_{i \ge 1}\ \prod_{j=1}^i a^jb^{i-j+1} = (ab)(abb\cdot aab)(abbb\cdot aabb\cdot aaab)\cdots .$$ We will show that the exact subword complexities of ${\bf w}_1$ and ${\bf w}_2$ are as follows: \begin{align*} \rho_{{\bf w}_1}(n) &= \frac{n^3}{6} + \frac{n^2}{2} -\frac{5n}{3} + 3 \quad \text{for $n \geq 4$} ; \\[.1in] \rho_{{\bf w}_2}(n) &= \frac{n^3}{6} -\frac{2n}{3} + \frac{19 +(-1)^n}{4} \quad \text{for $n \geq 4$}. \end{align*} Call each factor $\prod_{j=1}^i a^{i-j+1}b^{j}$ of ${\bf w}_1$ and $\prod_{j=1}^i a^jb^{i-j+1}$ of ${\bf w}_2$ as a \emph{minute} (or more specifically the $(i+1)$-st minute), and call each natural division within a minute a \emph{second}. Note that seconds are unique; every word of the form $a^ib^j$ occurs infinitely many times in ${\bf w}_1$ and ${\bf w}_2$, but only the one in the $(i+j)$-th minute will be considered a second. Equivalently, $a^ib^j$ is a second if it is preceded by $b$ and followed by $a$. Finally, every occurrence of the subword $ba$ marks the boundaries between two seconds, since no second contains $ba$. \section{Subword complexity of ${\bf w}_1$} Using the above observation, whenever we can guarantee that a subword $s$ of ${\bf w}_1$ contains a second, we uniquely determine what $s$ must be. This is equivalent to $s$ containing two occurrences of $ba$, one at the start of the second, and one at the end. Thus if $s$ contains a factor of the form $a^ib^ja^kb^la$ with $j,k,l \ge 1$, we may identify $a^kb^l$ as a second occurring in the $(k+l)$th minute. Since we uniquely determine what $s$ must be, this gives us conditions on the values of $i$ and $j$. In the case that we cannot guarantee that $s$ contains a second ($s$ may appear in ${\bf w}_1$ many times; some of these occurrences will contain a second, but others will not), $s$ must be of the form $a^*b^*a^*b^*$. \begin{theorem} The subword complexity of ${\bf w}_1$ is \[\rho_{{\bf w}_1}(n) = \begin{cases}n^3/6 + n^2/2 -5n/3 + 3, & \text{for } n\ge 4;\\ 2^n, & \text{otherwise.}\end{cases} \] \end{theorem} \begin{proof} First consider the case when we cannot guarantee that a subword $s$ of $w$ contains a second. Then $s$ must be of the form $a^*b^*a^*b^*$. Note that for all $p,q \ge 1$, the word $a^{p+1}b^qa^pb^{q+1}$ is a subword in the $(p+q+1)$st minute. Thus by taking $p$ and $q$ sufficiently large, we can get any subword of the form $a^*b^*a^*$ or $b^*a^*b^*$. Hence all words in \[A := a^*b^*a^* \cup b^*a^*b^*\] are subwords of $w$. The remaining words in $a^*b^*a^*b^*\setminus A = a^+b^+a^+b^+$ are of the form $a^ib^ja^kb^l$ with $i,j,k,l \ge1$. Since $ba$ marks the boundary between two seconds and no second has a factor $ba$, $a^ib^j$ must be the suffix of one second and $a^kb^l$ the prefix of the next. There are two possibilities: \begin{itemize} \item If the seconds are in the same minute, then $a^ib^ja^kb^l$ is a subword of $a^{p+1}b^qa^pb^{q+1}$ for some $p,q \ge 1$. Thus $i \le k+1$ and $l \le j+1$. \item If the seconds are in different minutes, then $a^ib^ja^kb^l$ is a subword of $ab^pa^{p+1}b$. Thus, $i = l = 1, j+1 = k$. But note that in this case, we have $i \le k+1, l \le j+1$, so we have already counted these subwords in the first case. \end{itemize} Thus there is a subword $a^ib^ja^kb^l$ in ${\bf w}_1$ if and only if the tuple $(i,j,k,l)$ is in \[B = \{(i,j,k,l) \suchthat i,j,k,l \ge1, i \le k+1, l \le j+1\} .\] Now consider the case when we can guarantee that $s$ contains a second. By looking at the first second $s$ contains, we conclude that $s$ must be prefixed by a word of the form $a^ib^ja^kb^la$ with $j,k,l \ge 1$ and $i \ge 0$. The second contained is $a^kb^l$ and $a^ib^j$ is the suffix of the second preceding it. There are two possibilities: \begin{itemize} \item The second $a^kb^l$ is the first second in the minute, so $l = 1$. The preceding second is $ab^{k-1}$, so either $i = 1$ and $j = k-1$ or $i = 0$ and $j \le k-1$. Thus we obtain a unique subword for each tuple in \[C := \{(0,j,k,1) \suchthat k \ge 2, 1 \le j \le k-1 \} \cup \{(1,k-1,k,1) \suchthat k \ge 2\} .\] \item The second $a^kb^l$ is not the first second in the minute, so $l > 2$. The preceding second is $a^{k+1}b^{l-1}$, so either $i = 0$ and $j \le l-1$ or $1 \le 1 \le k+1$ and $j = l-1$. Thus we obtain a unique subword for each tuple in \begin{align*} D := & \{(i,l-1,k,l) \suchthat i,k,l-1\ge 1, i \le k+1 \}\\ &\cup \{(0,j,k,l)\suchthat j,k,l-1 \ge 1, j \le l-1 \} . \end{align*} \end{itemize} We will find generating functions $a,b,c,d$ such that $[x^n]a(x)$ is the number of subwords of length $n$ corresponding to $A$, etc. \begin{itemize} \item $A = \epsilon \cup a^+ \cup b^+ \cup a^+b^+ \cup b^+a^+ \cup a^+b^+a^+ \cup b^+a^+b^+$ is uniquely generated. This can be translated to \begin{align*} a(x) &= 1 + \frac{2x}{1-x} + \frac{2x^2}{(1-x)^2} + \frac{2x^3}{(1-x)^3}\\ &= \frac{1-x+x^2 + x^3}{(1-x)^3} . \end{align*} \item There is a length $i+j+k+l$ subword for each $(i,j,k,l) \in B$. Thus, \begin{align*} b(x) &= \sum_{(i,j,k,l) \in B} x^{i+j+k+l} = \sum_{k \ge 1, 1\le i \le k+1}\sum_{j \ge 1, 1 \le l \le j+1}x^{i+j+k+l}\\ &= \left(\sum_{k \ge 1, 1\le i \le k+1}x^{i+k} \right)^2\\ &= \left(\sum_{k \ge 1}\sum_{i=1}^{k+1}x^{i+k} \right)^2\\ &= \left(\frac{x^2+x^3-x^4}{(1-x)^2(1+x)} \right)^2 = \frac{x^4+2x^5-x^6-2x^7+x^8}{(1-x)^4(1+x)^2} . \end{align*} \item The tuples in $C,D$ corresponds to prefixes. For each tuple $(i,j,k,l) \in C,D$, there is exactly one subword with prefix $a^ib^jc^kd^la$. Thus we have \begin{align*} c(x) &= \sum_{(i,j,k,l) \in C} \frac{x^{i+j+k+l+1}}{1-x} = \sum_{k \ge 2}\sum_{j=1}^{k-1}\frac{x^{j+k+2}}{1-x} + \sum_{k \ge 2}\frac{x^{2k+2}}{1-x}\\ &=\frac{x^5}{(1-x)^3(1+x)} + \frac{x^6}{(1-x)^2(1+x)}\\[.1in] &= \frac{x^5+x^6-x^7}{(1-x)^3(1+x)}.\\[.1in] d(x) &= \sum_{l \ge 2,k\ge 1, 1\le u\le k+1}\frac{x^{i+k+2l}}{1-x} + \sum_{l\ge 2,k\ge 1,1\le j \le l-1}\frac{x^{j+k+l+1}}{1-x}\\[.1in] &= \frac{x^6+x^7 - x^8}{(1-x)^4(1+x)^2} + \frac{x^5+x^6}{(1-x)^4(1+x)^2} = \frac{x^5 + 2x^6 + x^7 - x^8}{(1-x)^4(1+x^2)} . \end{align*} \end{itemize} The sum of the generating functions $F(x) = a(x) + b(x) + c(x) + d(x)$ encodes the subword complexity as follows \[F(x) = \sum_{n\ge 0}\rho_{{\bf w}_1}(n)x^n.\] Thus we obtain \begin{align*} F(x) &= \frac{1-x+x^2 + x^3}{(1-x)^3} + \frac{x^4+2x^5-x^6-2x^7+x^8}{(1-x)^4(1+x)^2} \\ &\hspace{15pt}+ \frac{x^5+x^6-x^7}{(1-x)^3(1+x)} + \frac{x^5 + 2x^6 + x^7 - x^8}{(1-x)^4(1+x^2)}\\ &= \frac{1-2x + x^2 + 2x^5 - 3x^6 + x^7}{(1-x)^4}\\ &= \frac{1}{(1-x)^4}- \frac{1}{(1-x)^3} - \frac{2}{(1-x)^2} + \frac{5}{1-x} -2 +x^2 + x^3 . \end{align*} Thus $$\rho_{{\bf w}_1}(n) = {n+3\choose{3}} - {n+2\choose2} - 2{n+1\choose1} + 5 = \frac{n^3}{6} + \frac{n^2}{2} - \frac{5n}{3} + 3$$ for all $n \ge 0$, with the exception of $n =0,2,3$ due to the $-2 +x^2 + x^3$ terms. \end{proof} \section{Subword complexity of ${\bf w}_2$} The word ${\bf w}_2$ is very similar to ${\bf w}_1$, in that the seconds in each minute are concatenated in the reverse order. Thus, the technique used in the previous section will work here as well. We will give the classification of subwords $t$ of ${\bf w}_2$, but omit the details of the computations. \begin{theorem} The subword complexity of ${\bf w}_2$ is \[\rho_{{\bf w}_2}(n) = \begin{cases} n^3/6 - 2n/3 + (19 +(-1)^n)/4, &\text{for } n \ge 4;\\ 2^n, &\text{otherwise}. \end{cases}\] \end{theorem} \begin{proof} As before, if a subword $t$ contains $a^ib^ja^kb^la$, then it contains a second, and that second must be within the $(k+l)$th minute. Thus this uniquely determines $t$. We may choose this second to be the first second contained in $t$, so that $a^ib^ja^kb^la$ is the prefix of $t$. \begin{itemize} \item If $a^kb^l$ is the first second of a minute, so $k = 1$, then $a^ib^j$ is the suffix of $a^{l-1}b$. Thus $0 \le i \le l-1$ and $j =1$. Therefore, we obtain a prefix for each tuple in \[C:= \{(i,1,1,l) \suchthat 0\le i \le l-1 \text{ and } l \ge 2\} .\] \item If $a^kb^l$ is not the first second of a minute, so $k \ge 2$, then $a^ib^j$ is the suffix of $a^{k-1}b^{l+1}$. Thus either $i = 0$ and $1 \le j \le l+1$ or $1 \le i \le k-1$ and $j = l+1$. Thus we obtain a prefix for each tuple in \begin{align*} D := &\{ (i, l+1, k, l) \suchthat 1 \le i \le k-1, k\ge 2, l\ge 1\}\\ &\cup \{(0,j,k,l) \suchthat 1 \le j \le l+1, k \ge 2, l \ge 1\}. \end{align*} \end{itemize} Next, consider $t$ of the form $a^*b^*a^*b^*$. It must lie within two consecutive seconds, either $a^pb^{q+1}a^{p+1}b^q$ for $p,q \ge 1$ if they are within the same minute, or $a^pbab^q$ if they are not. Clearly, every word in $a^*b^* \cup b^*a^*$ is a valid subword, by taking $p,q$ large enough. We also get every word in $a^+bb^+a^+ \cup b^+aa^+b^+$. But every word appearing in $a^+ba^+$ must be a subword of $a^pbab^q$. Therefore, the second block of $a$s must have length $1$, and similarly for words in $b^+ab^+$. Therefore, every word in \[A := a^*b^*a^*\cup b^*a^*b^* \setminus\left(a^+baa^+\cup bb^+ab^+ \right) \] appears as a subword of ${\bf w}_2$. The remaining words of the form $a^*b^*a^*b^*$ are $a^ib^ja^kb^l$ with $i,j,k,l \ge 1$. For this to be a subword of $a^pb^{q+1}a^{p+1}b^q$, we must have $j,k\ge2, i \le k-1, l\le j-1$. For it to be a subword of $a^pbab^q$, we must have $j,k = 1$. Thus we obtain a subword for each tuple in \[B:= \{(i,j,k,l) \suchthat j,k \ge 2, 1 \le i \le k-1, 1 \le l \le j-1 \} \cup \{(i,1,1,l) \suchthat i,l \ge 1\}. \] As before, we construct generating functions for each of the sets, and add them. This gives a generating function $F(x)$ which encodes the subword complexity \[F(x) = a(x) + b(x) + c(x) + d(x) = \sum_{n\ge 0} \rho_{{\bf w}_2}(n)x^n. \] After the calculations, we obtain \[F(x) = \frac{5 - 11x + 3x^2 + 10x^3 - 5x^4}{(1-x)^4(1+x)} - 4 - 2x - x^2 + x^3, \] so that $\rho_{{\bf w}_2}(n) = \frac{n^3}{6} -\frac{2n}{3} + \frac{19 +(-1)^n}{4}$ for $n \ge 0$ with exceptions at $n = 0,1,2,3$ due to the $-4 - 2x - x^2 + x^3$ terms. \end{proof} \section{Acknowledgments} \noindent We would like to thank Tim Smith and Jeffrey Shallit for suggesting the problem. \begin{thebibliography}{10} \bibitem{Allouche&Shallit:2003} J.-P. Allouche and J.~O. Shallit, {\em Automatic Sequences: Theory, Applications, Generalizations}, Cambridge University Press, 2003. \bibitem{allouche1994} Jean-Paul Allouche, Sur la complexit\'e des suites infinies, {\em Bull. Belg. Math. Soc. Simon Stevin} {\bf 1} (1994), 133--143. \bibitem{Cassaigne:1996} J.~Cassaigne, Special factors of sequences with linear subword complexity. \newblock In J.~Dassow, G.~Rozenberg, and A.~Salomaa, editors, {\em Developments in Language Theory II}, pp.~25--34. World Scientific, 1996. \bibitem{Ehrenfeucht&Rozenberg:1981c} A.~Ehrenfeucht and G.~Rozenberg, On the subword complexity of square-free {D0L} languages, {\em Theoret. Comput. Sci.} {\bf 16} (1981), 25--32. \bibitem{DBLP:journals/dm/Ferenczi99} S{\'{e}}bastien Ferenczi, Complexity of sequences and dynamical systems, {\em Discrete Math.} {\bf 206} (1999), 145--154. \bibitem{DBLP:journals/tcs/FerencziK99} S{\'{e}}bastien Ferenczi and Zolt{\'{a}}n K{\'{a}}sa, Complexity for finite factors of infinite sequences, {\em Theoret. Comput. Sci.} {\bf 218} (1999), 177--195. \bibitem{Mignosi:1989} F.~Mignosi, Infinite words with linear subword complexity, {\em Theoret. Comput. Sci.} {\bf 65} (1989), 221--242. \bibitem{Pansiot:1984a} J.-J. Pansiot, {Complexit\'e} des facteurs des mots infinis {engendr\'es} par morphismes {it\'er\'es}. \newblock In J.~Paredaens, editor, {\em Proc. 11th Int'l Conf. on Automata, Languages, and Programming (ICALP)}, Vol.~172 of {\em Lecture Notes in Computer Science}, pp.~380--389. Springer-Verlag, 1984. \bibitem{Pansiot:1984b} J.-J. Pansiot, Bornes inf\'erieures sur la {complexit\'e} des facteurs des mots infinis {engendr\'es} par morphismes {it\'er\'es}. \newblock In M.~Fontet and K.~Mehlhorn, editors, {\em STACS 84, Proc.\ 1st Symp. Theoretical Aspects of Comp. Sci.}, Vol.~166 of {\em Lecture Notes in Computer Science}, pp.~230--240. Springer-Verlag, 1984. \bibitem{smith:2020} T.~Smith, {A characterization of morphic words with polynomial growth}, {\em {Discrete Mathematics \& Theoretical Computer Science}} {\bf 22} (2020), \href{https://dmtcs.episciences.org/6073/pdf}{Paper \#3}. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 68R15; Secondary 05A15. \noindent \emph{Keywords:} subword complexity, morphic word. \bigskip \hrule \bigskip \noindent (Concerned with sequence \seqnum{A338760}, \seqnum{A338761}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received September 10 2020; revised version received October 27 2020. Published in {\it Journal of Integer Sequences}, November 7 2020. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}