The Narayana Morphism and Related Words

Jeffrey Shallit · 2025

Read The Narayana Morphism and Related Words by Jeffrey Shallit (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-01026.txt.

Introduction

Jeffrey Shallit studies a number word built by a fixed rewriting rule, in a solo paper from 2025. The rule, called the Narayana morphism, sends each of three symbols to a short string: zero becomes zero one, one becomes two, and two becomes zero. Repeating the rule forever yields one endless word that starts with a known pattern.

Shallit uses automata theory, the study of simple state machines, to prove traits of that endless word and of kin words built by like rules. Such words serve as clean test cases in combinatorics on words, where patterns, repeats, and avoided blocks are the core questions. Machine based proofs can settle claims about these words that hand arguments handle only with effort. The paper adds a worked example of that method.

Catalog record

CREATORJeffrey Shallit
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE55 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-01026

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The Narayana Morphism and Related Words Jeffrey Shallit Abstract The Narayana morphism ν \nu maps 0 → 01 0\rightarrow 01 , 1 → 2 1\rightarrow 2 , 2 → 0 2\rightarrow 0 and has a fixed point 𝐧 = n 0 n 1 n 2 ⋯ = 𝟶𝟷𝟸𝟶𝟶𝟷𝟶𝟷𝟸𝟶𝟷𝟸𝟶 ⋯ {\bf n}=n_{0}n_{1}n_{2}\cdots={\tt 0120010120120}\cdots . In this paper we study the properties of this word and related words using automata theory. 1 Introduction Consider the morphism \nu:0\rightarrow 01 , 1\rightarrow 2 , 2\rightarrow 0 , which we call the Narayana morphism for reasons that will become clear in a moment. Its fixed point is {\bf n}=n_{0}n_{1}n_{2}\cdots={\tt 012001012012001200101200101201200101201200120010120120012001}\cdots, the infinite Narayana word . Up to renaming the letters, the word \bf n is sequence A105083 in the On-Line Encyclopedia of Integer Sequences (OEIS) [ 43 ] . We can view \nu as a higher-dimensional generalization of the well-studied Fibonacci morphism [ 24 , 7 , 20 ] 0\rightarrow 01 , 1\rightarrow 0 , and \bf n as a higher-dimensional generalization of the Fibonacci word {\bf f}={\tt 01001010010010100101001}\cdots [ 36 , 27 ] . (See Section 8 for more about this.) Nevertheless, the morphism \nu and the word \bf n have received very little study. The morphism \nu was mentioned briefly by Sirvent and Wang [ 42 ] , and \bf n appears (implicitly) in [ 18 , 2 ] as an infinite word associated with a Parry number (with finite Rényi expansion) that is a real root of the equation X^{j}=\sum_{0\leq i<j}t_{i}X^{i} . In their notation, it corresponds to t_{1}t_{2}t_{3}=101 . In this paper we study properties of the word \bf n , and related words, using Walnut , a free software tool for proving first-order properties of sequences that can be generated with automata. Although some of the results proved here were already known (and indeed, some in much greater generality), the virtue of the method we present here is its extreme simplicity. Often one only has to state the desired theorem and Walnut can prove it in a few seconds. The techniques involving automata are mostly familiar now, and detailed explanations of the technique can be found in the author’s book [ 40 ] . However, there are a few novelties. Along the way we prove two conjectures, one due to Kimberling and Moses [ 26 ] and one due to Cloitre. 2 The Narayana numbers and the Narayana numeration system It is natural to study the integer sequence (N_{i})_{i\geq 0} defined by N_{i}=|\nu^{i}(0)| . Table 1 gives the first few values of this sequence. If we also define N_{-1}=N_{-2}=1 , then a simple induction shows N_{i}=N_{i-1}+N_{i-3} for i\geq 1 , and further that |\nu^{i}(1)|=N_{i-2} and |\nu^{i}(2)|=N_{i-1} for i\geq 0 . i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 N_{i} 1 2 3 4 6 9 13 19 28 41 60 88 129 189 277 406 595 Table 1: The first few Narayana numbers. The integer sequence (N_{i}) (in contrast to \nu and \bf n ) has been well-studied under the slightly awkward name of Narayana’s cows sequence . See, for example, [ 1 , 31 , 10 ] . We call (N_{i}) the Narayana numbers; they form sequence A000930 in the OEIS. The Narayana numbers can be extended to negative indices using the recurrence N_{i}=N_{i-1}+N_{i-3} . We can build a numeration system from (N_{i})_{i\geq 0} , where we write every non-negative integer as a sum of distinct Narayana numbers N_{i} . We can write such a representation for m as a binary string e_{1}\cdots e_{t} , where m=\sum_{1\leq i\leq t}e_{i}N_{t-i}. (1) The sum ( 1 ) is denoted [e_{1}e_{2}\cdots e_{t}]_{N} . In other words, the representations we study here are written most-significant-digit first. For example, 27=N_{7}+N_{4}+N_{1}=19+6+2=[10010010]_{N} . Theorem 1 . Every positive integer m has a unique representation e_{1}\cdots e_{t} , provided the leading digit e_{1} is nonzero, and there are no occurrences of the block 11 or 101 in e_{1}\cdots e_{t} . Proof. This result can be found as Theorem 7.1 of [ 22 ] , but it also follows from the more general results of Fraenkel [ 16 ] . ∎ The unique (canonical) Narayana representation of m is written (m)_{N}=e_{1}e_{2}\cdots e_{t} . The representation of 0 is \epsilon , the empty string. The first few Narayana representations are given in Table 2 . i (i)_{N} i (i)_{N} i (i)_{N} 0 \epsilon 7 10001 14 1000001 1 1 8 10010 15 1000010 2 10 9 100000 16 1000100 3 100 10 100001 17 1001000 4 1000 11 100010 18 1001001 5 1001 12 100100 19 10000000 6 10000 13 1000000 20 10000001 Table 2: Narayana representations. Define p_{i} to be the prefix of length i of \bf n and let q_{i} be p_{N_{i}}=\nu^{i}(0) . The Narayana representation of i also gives a simple description for p_{i} , as follows. Theorem 2 . Write the Narayana representation of i in the form N_{d_{1}}+N_{d_{2}}+\cdots+N_{d_{t}} , where d_{1}>d_{2}>\cdots>d_{t} . Then p_{i}=q_{d_{1}}q_{d_{2}}\cdots q_{d_{t}} . Proof. A simple proof by induction, omitted. ∎ Recall that |x|_{a} denotes the number of occurrences of the symbol a in the string x . Proposition 3 . For i\geq 0 we have \displaystyle|q_{i}|_{0} \displaystyle=N_{i-2} \displaystyle|q_{i}|_{1} \displaystyle=N_{i-3} \displaystyle|q_{i}|_{2} \displaystyle=N_{i-4}. Proof. A simple proof by induction, omitted. ∎ Corollary 4 . Let the representation of i be e_{1}e_{2}\cdots e_{j} . Then \displaystyle|p_{i}|_{0} \displaystyle=[e_{1}\cdots e_{j-2}]_{N}+e_{j-1}+e_{j} \displaystyle|p_{i}|_{1} \displaystyle=[e_{1}\cdots e_{j-3}]_{N}+e_{j-2}+e_{j-1} \displaystyle|p_{i}|_{2} \displaystyle=[e_{1}\cdots e_{j-4}]_{N}+e_{j-3}+e_{j-2}. 3 Closed form and estimates for the Narayana numbers As is well-known from the theory of linear recurrences, there is a closed form for the Narayana numbers of the form N_{i}=c_{1}\alpha^{i}+c_{2}\beta^{i}+c_{3}\gamma^{i}, (2) where \alpha and c_{1} are real, and (\beta,\gamma) and (c_{2},c_{3}) are complex conjugates pairs. Here \alpha,\beta,\gamma are the zeroes of the polynomial X^{3}-X^{2}-1 . We therefore get, using the triangle inequality and ( 2 ), that |N_{i}-c_{1}\alpha^{i}|\leq|c_{2}\beta^{i}+c_{3}\gamma^{i}|\leq|c_{2}\beta^{i}|+|c_{3}\gamma^{i}|=|c_{2}||\beta|^{i}+|c_{3}||\gamma|^{i}=2|c_{2}||\beta|^{i}. (3) We now obtain some explicit estimates for the quantities N_{i+j}-\alpha^{j}N_{i} . These will be useful later in Section 5.9 , Theorem 26 . For k\geq 0 we have N_{i+k}-\alpha^{k}N_{i}=(N_{i+k}-c_{1}\alpha^{i+k})-\alpha^{k}(N_{i}-c_{1}\alpha^{i}), and so by the triangle inequality and ( 3 ) we get \displaystyle|N_{i+k}-\alpha^{k}N_{i}| \displaystyle\leq|N_{i+k}-c_{1}\alpha^{i+k}|+\alpha^{k}|N_{i}-c_{1}\alpha^{i}| \displaystyle\leq 2|c_{2}|(|\beta|^{k}+\alpha^{k})|\beta|^{i}. (4) Closed forms for \alpha,\beta,\gamma,c_{1},c_{2},c_{3} were given by Lin [ 31 ] , and from these we can easily compute approximations to their values, as follows: \displaystyle\alpha \displaystyle\doteq 1.46557123187676802665673 \displaystyle\beta \displaystyle\doteq-0.2327856159383840133283656+0.7925519925154478483258983i \displaystyle\gamma \displaystyle\doteq-0.2327856159383840133283656-0.7925519925154478483258983i \displaystyle|\beta| \displaystyle=|\gamma|\doteq 0.826031357654186955968987 \displaystyle c_{1} \displaystyle=\alpha^{5}/(\alpha^{3}+2)\doteq 1.313423059852349798783263 \displaystyle c_{2} \displaystyle=\beta^{5}/(\beta^{3}+2)\doteq-0.15671152992617489939163-0.001340333618411808095189i \displaystyle c_{3} \displaystyle=\gamma^{5}/(\beta^{3}+2)\doteq-0.15671152992617489939163+0.001340333618411808095189i \displaystyle|c_{2}| \displaystyle=|c_{3}|\doteq 0.15671726167213060374568596. Now for k=1,2,3 , using ( 4 ) and the numerical approximations above, we get \displaystyle|N_{i+1}-\alpha N_{i}| \displaystyle<0.71826736534411(0.8260313576542)^{i} (5) \displaystyle|N_{i+2}-\alpha^{2}N_{i}| \displaystyle<0.887090800406(0.8260313576542)^{i} (6) \displaystyle|N_{i+3}-\alpha^{3}N_{i}| \displaystyle<1.16331950440432(0.8260313576542)^{i}. (7) We now prove a useful lemma. Lemma 5 . For i\geq 0 we have the bounds \displaystyle-0.79752082381 \displaystyle<[(i)_{N}0]_{N}-\alpha i<1.04861494527 (8) \displaystyle-1.09505816541 \displaystyle<[(i)_{N}00]_{N}-\alpha^{2}i<1.684304571609 (9) \displaystyle-1.10019497962 \displaystyle<[(i)_{N}000]_{N}-\alpha^{3}i<1.70593793584. (10) Proof. To prove Eq. ( 8 ), we start by writing i in its Narayana representation: i=N_{f_{1}}+\cdots+N_{f_{s}} for some integers 0\leq f_{1}<f_{2}<\cdots<f_{s} . Then [(i)_{N}0]_{N}=N_{f_{1}+1}+\cdots+N_{f_{s}+1}, and hence [(i)_{N}0]_{N}-\alpha i=\sum_{1\leq j\leq s}(N_{f_{j}+1}-\alpha N_{f_{j}}). Now we split the sum on the right-hand side into two pieces: one where f_{j}<30 , and one where f_{j}\geq 30 : [(i)_{N}0]_{N}-\alpha i=\sum_{0\leq f_{j}<30}(N_{f_{j}+1}-\alpha N_{f_{j}})+\sum_{f_{j}\geq 30}(N_{f_{j}+1}-\alpha N_{f_{j}}), and hence, by using Eq. ( 5 ), we get \displaystyle|[(i)_{N}0]_{N}-\alpha i-\sum_{0\leq f_{j}<30}(N_{f_{j}+1}-\alpha N_{f_{j}})| \displaystyle\leq\sum_{k\geq 30}|N_{k+1}-\alpha N_{k}| \displaystyle<\sum_{k\geq 30}0.71826736534411(0.8260313576542)^{k} \displaystyle<0.01335706955. (11) We now compute

Read the complete text