# Subwords of the infinite Fibonacci word

Let $$W = 01001010010010 \ldots$$ be the infinite Fibonacci word, A003849 in the OEIS. Let $$B(m)$$ be the set of $$m+1$$ subwords of $$W$$ that have length $$m$$, and for each such subword $$u$$, let $$p(u)$$ be the sequence of positions in $$W$$ where $$u$$ begins. Then $$p(u)$$ is a composite of the famous Wythoff sequences $$A=$$A000201 and $$B=$$A001950. Can someone figure out (or cite a reference) exactly which composites represent the subwords in $$B(m)$$?

Here's how it looks for $$m=4$$:

$$\begin{array}{|c|c|c|c|} \text{subword, } u & \text{positions, } p(u) & \text{composite} & \text{OEIS} \\ 0100 & 1,6,9,14,\ldots & AAA & A134859 \\ 1001 & 2,7,10,15,\ldots & BA & A035336 \\ 0010 & 3,8,11,16,\ldots & AB & A003623 \\ 0101 & 4,12,17,25,\ldots & AAB & A134860 \\ 1010 & 5,13,18,26,\ldots & BB & A101864 \end{array}$$

(Links: A134859, A035336, A003623, A134860, A101864)

(Note that for every $$m$$, the difference sequence of every $$p(u)$$ consists of Fibonacci numbers.)

Following Sam Hopkins's note, here's a definition. Start with $$0$$ and apply the substitutions $$0 \rightarrow 01$$ and $$1 \rightarrow 0$$ repeatedly, like this: $$0,01,010,01001,01001010,0100101001001,\ldots.$$ The limiting word is A003849, one of several called the infinite Fibonacci word, but this one is regarded as the standard form, according to the Crossrefs section of A014675.

Writing those words as $$w_0,w_1,w_2,\ldots$$, respectively, note that $$w_n$$ is, for $$n \geq 2$$, the concatenation indicated by $$w_n=w_{n-1}w_{n-2}$$, so that the length of $$w_n$$ is a Fibonacci number.

Some more background: suppose that $$w$$ is a word in $$B(m)$$. Then at least one of the words $$w0$$ and $$w1$$ must be in $$B(m+1)$$. However, there is only one $$w$$ in $$B(m)$$ such that both $$w0$$ and $$w1$$ are in $$B(m+1)$$. Such a "splitter" turns out to be simply a reversal of an initial word of $$W$$, so that the first few splitters are $$,0,10,010,0010,10010,\ldots$$. The corresponding Wythoff composites are $$A,B,AA,AB,BA,AAA,BB,AAB,ABA,BAA,AAAA,ABB,\ldots$$ So, if someone can tell specifically how to generate this sequence, the problem will be solved.

• It'd be helpful if you defined the Fibonacci word (rather than just cite an OEIS entry). Commented Jan 16, 2021 at 20:10
• The word you obtain over $\{A, B\}$ is determined by the choices you had to make to get that particular subword. When you do have a choice while adding a new letter to the right, $A$ stands for the choice that occurs first, and $B$ for the other one. Example: $00100\mapsto ABB$ since in the Fibonacci word $0$ occurs before $1$, $00$ after $01$, and $00100$ after $00101$. (This is mostly guessing, I'll let someone else prove it – or disprove it if I'm wrong.) Commented Jan 17, 2021 at 9:20
• It would be nice (and good practice) if you replace each oeis reference by the corresponding hyperlink. Commented Jan 17, 2021 at 12:37
• Since I don't believe you get automatic notifications of edits to answers, this is a manual notification that I've heavily overhauled my answer, elevating it from conjecture to theorem conditional on statements made in the question. Commented Jun 5, 2021 at 10:21

Such a "splitter" turns out to be simply a reversal of an initial word of $$W$$, so that the first few splitters are $$,0,10,010,0010,10010,\ldots$$. The corresponding Wythoff composites are $$A,B,AA,AB,BA,AAA,BB,AAB,ABA,BAA,AAAA,ABB,\ldots$$ So, if someone can tell specifically how to generate this sequence, the problem will be solved.

I construct some parallel families of finite sequences in "generations", where the full sequence is obtained by concatenating all of the generations in order.

Let $$W$$ denote the infinite Fibonacci word.

Let $$P_0 = [w_0]$$, $$P_1 = [w_1, w_1 w_0]$$, $$P_{k+2} = w_{k+2} P_k + w_{k+2} P_{k+1}$$. It's easy to show by induction that the lengths of the words in $$P = P_0 + P_1 + P_2 + \cdots$$ are $$1, 2, 3, \ldots$$ and that the words themselves are all prefixes of $$W$$. (A useful lemma to show the latter is that $$w_n w_{n-1} \cdots w_0$$ is a prefix of $$w_{n+2}$$).

Let $$r_k = \textrm{reverse}(w_k)$$; equivalently $$r_0 = 0$$, $$r_1 = 10$$, $$r_{k+2} = r_k r_{k+1}$$. (Note that the first symbol of $$r_i$$ is $$i \bmod 2$$). Then the family $$R_k$$ is defined inductively as $$R_0 = [r_0]$$, $$R_1 = [r_1, r_0 r_1]$$, $$R_{k+2} = R_k r_{k+2} + R_{k+1} r_{k+2}$$. By construction, the $$i$$th word in $$R_k$$ is the reverse of the $$i$$th word in $$P_k$$, and therefore $$R = R_0 + R_1 + R_2 + \cdots$$ is the sequence of the (non-empty) splitters.

A point of interest is that the last word in $$R_k$$ is $$r_0 r_1 \cdots r_k$$, and this is a prefix of $$W$$ (see e.g. proposition 17 of Factorizations of the Fibonacci Infinite Word, Fici, J. Int. Seq. article 15.9.3). But it's also the reverse of a prefix, and therefore is a palindrome. Then we can work backwards along the generation and say that the $$i$$th last word in $$R_k$$ can be found at position $$i$$ in $$W$$.

The main sequence is $$G_0 = [A]$$, $$G_1 = [B, AA]$$, $$G_{k+2} = G_k B + G_{k+1} A$$. Clearly every (non-empty) Wythoff composite occurs exactly once in the sequence $$G = G_0 + G_1 + G_2 + \cdots$$. It will be useful to note that if $$A$$ has weight $$1$$ and $$B$$ has weight $$2$$ then every composite in $$G_k$$ has weight $$k+1$$. (In fact, $$G_k$$ contains precisely the composites of weight $$k+1$$ in lexicographic order of their reversals, but we won't use this).

Assuming the claim made in the question that compositions of $$A$$ and $$B$$ exactly index the splitters (which I don't know how to prove), we can show that the $$i$$th element of $$G_k$$ exactly indexes the $$i$$th element of $$R_k$$, so that $$G$$ is the desired sequence.

Observe that since $$A$$ and $$B$$ partition the domain of a Wythoff composite $$S$$, $$SA$$ and $$SB$$ partition its range. If the longest word indexed by $$S$$ is the splitter $$s \in R_k$$, then the construction of the generations of $$R$$ tells us that $$sr_{k+1}$$ and $$sr_{k+2}$$ are both splitters whose common prefix is precisely $$s$$.

Take the inductive hypothesis:

The elements of $$G_k$$ exactly index the corresponding elements of $$R_k$$ for every $$0 \le k \le n$$.

This can be checked for $$n = 1$$. Suppose it holds for a given $$n \ge 1$$. Then for any given splitter $$s \in R_{n-1}$$ with corresponding composite $$S \in G_{n-1}$$, the splitter $$sr_n$$ is indexed by $$SA$$, and the splitter $$sr_{n+1}$$ must therefore be indexed by $$SBT$$ for some $$T$$. But $$T$$ must be empty as otherwise there is no splitter indexed by $$SB$$, contradicting our assumption.

Now, for the $$i$$th last $$s' \in R_n$$ with corresponding composite $$S' \in G_n$$ we note that $$s'r_{n+1} \in R_{n+1}$$ and occurs at position $$i$$ in $$W$$. Our inductive hypothesis suffices to show that $$s'$$ does not occur at any position $$j < i$$ in $$W$$, since otherwise it would be indexed by multiple composites in $$R_n$$, requiring one to be a prefix of another, which is incompatible with the observation about their weights. Therefore $$i$$ is the first occurrence of both $$s'$$ and $$s'r_{n+1}$$, and $$s'r_{n+1}$$ must be indexed by $$S'A^m$$ for some $$m > 0$$. But in fact $$m = 1$$ since otherwise there is no splitter indexed by $$S'A$$, contradicting our assumption.

As a by-product, we obtain an effective algorithm to determine the composite which corresponds to any subword of $$W$$ without explicitly calculating anything more than Fibonacci numbers.

Let $$s$$ be the subword of interest, and initialise $$i = 0$$. While $$s$$ is non-empty, if its first symbol is $$i \bmod 2$$ then emit $$A$$, delete (up to) $$f_{i+2}$$ symbols from the start of $$s$$, and increment $$i$$; otherwise emit $$B$$, delete (up to) $$f_{i+3}$$ symbols from the start of $$s$$, and increment $$i$$ twice.

And as a side-note, I observe that A341258 describes a sequence of words beginning $$0$$, $$1$$, $$00$$, $$01$$, $$10$$, $$000$$, $$11$$, $$001$$, $$010$$, $$100$$, $$000$$, $$011$$, $$101$$, $$0001$$, $$110$$, $$0010$$, $$0100$$, $$1000$$, $$00000$$, $$111$$ which appears to correspond to $$G$$ under the substitution $$0 \to A, 1 \to B$$ and was submitted by Clark Kimberling in March. I assume that this is no coincidence and that you have already solved the problem by a different route.