Skip to main content
added 3575 characters in body
Source Link
Peter Taylor
  • 7.2k
  • 1
  • 21
  • 29

ThisI construct some parallel families of finite sequences in "generations", where the full sequence is conjecture based on observing a patternobtained by concatenating all of the generations in order.

Let $W$ denote the infinite Fibonacci word.

Let $P_0 = [w_0]$, but it feels so natural$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 it inspires some confidence even based onthe 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 relatively small sampleprefix of $w_{n+2}$).

DefineLet $r_k = \textrm{reverse}(w_k)$; equivalently $r_0 = 0$, $r_1 = 10$, $r_{k+2} = r_k r_{k+1}$. (Note that the sequencefirst symbol of words $r_i = \textrm{reverse}(w_i)$$r_i$ is $i \bmod 2$). InitialiseThen the family $i = 0$$R_k$ is defined inductively as $R_0 = [r_0]$, $s = \textrm{reverse}(W[1..n])$$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 $n$$i$th splitter. Whileword in $s$$P_k$, and therefore $R = R_0 + R_1 + R_2 + \cdots$ is nonthe sequence of the (non-empty, if) splitters.

A point of interest is that the last word in $r_i$$R_k$ is $r_0 r_1 \cdots r_k$, and this is a prefix of $s$ emit$W$ $A$, remove(see e.g. proposition 17 of $r_i$ fromFactorizations of the Fibonacci Infinite Word, Fici, J. Int. Seq. article 15.9.3). But it's also the startreverse of $s$a prefix, and incrementtherefore is a palindrome. Then we can work backwards along the generation and say that the $i$; otherwise emitth 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, remove $r_{i+1}$ from$G_k$ contains precisely the startcomposites of weight $s$$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 increment $B$ exactly index the splitters (which I don't know how to prove), we can show that the $i$ twiceth element of $G_k$ exactly indexes the $i$th element of $R_k$, so that $G$ is the desired sequence.

Worked example:Observe that since $A$ and $B$ partition the 26th splitter isdomain of a Wythoff composite $10010010100101001001010010$$S$, $SA$ and $SB$ partition its range. It doesn't start withIf the longest word indexed by $r_0 = 0$$S$ is the splitter $s \in R_k$, so we emitthen the construction of the generations of $B$$R$ tells us that $sr_{k+1}$ and skip $r_1 = 10$ leaving$sr_{k+2}$ are both splitters whose common prefix is precisely $010010100101001001010010$$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 does startcan 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 $r_2 = 010$$S \in G_{n-1}$, so we emitthe splitter $A$$sr_n$ is indexed by $SA$, and reducethe splitter $s$ to$sr_{n+1}$ must therefore be indexed by $010100101001001010010$$SBT$ for some $T$. This doesn't start withBut $r_3 = 10010$$T$ must be empty as otherwise there is no splitter indexed by $SB$, socontradicting our assumption.

Now, for the $i$th last $s' \in R_n$ with corresponding composite $S' \in G_n$ we emitnote that $B$$s'r_{n+1} \in R_{n+1}$ and skipoccurs at position $r_4 = 01010010$ leaving$i$ in $1001001010010$$W$. ThisOur inductive hypothesis suffices to show that $s'$ does start withnot occur at any position $r_5 = 1001001010010$$j < i$ in $W$, so we emitsince otherwise it would be indexed by multiple composites in $A$ and$R_n$, requiring one to be a prefix of another, which is incompatible with the empty string remainsobservation about their weights. The Wythoff composite forTherefore $i$ is the 26th splitterfirst 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 $BABA$$S'A$, contradicting our assumption.

 

For practical implementationAs a by-product, it maywe 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 noted thatthe subword of interest, and initialise $r_i$'s$i = 0$. While $s$ is non-empty, if its first symbol is $i \bmod 2$ andthen emit $A$, delete (up to) $f_{i+2}$ symbols from the lengthsstart of $s$, obviouslyand increment $i$; otherwise emit $B$, followdelete (up to) $f_{i+3}$ symbols from the Fibonaccistart 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.

This is conjecture based on observing a pattern, but it feels so natural that it inspires some confidence even based on a relatively small sample.

Define the sequence of words $r_i = \textrm{reverse}(w_i)$. Initialise $i = 0$, $s = \textrm{reverse}(W[1..n])$ is the $n$th splitter. While $s$ is non-empty, if $r_i$ is a prefix of $s$ emit $A$, remove $r_i$ from the start of $s$, and increment $i$; otherwise emit $B$, remove $r_{i+1}$ from the start of $s$, and increment $i$ twice.

Worked example: the 26th splitter is $10010010100101001001010010$. It doesn't start with $r_0 = 0$, so we emit $B$ and skip $r_1 = 10$ leaving $010010100101001001010010$. This does start with $r_2 = 010$, so we emit $A$ and reduce $s$ to $010100101001001010010$. This doesn't start with $r_3 = 10010$, so we emit $B$ and skip $r_4 = 01010010$ leaving $1001001010010$. This does start with $r_5 = 1001001010010$, so we emit $A$ and the empty string remains. The Wythoff composite for the 26th splitter is $BABA$.

For practical implementation, it may be noted that $r_i$'s first symbol is $i \bmod 2$ and the lengths, obviously, follow the Fibonacci sequence.

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.

Source Link
Peter Taylor
  • 7.2k
  • 1
  • 21
  • 29

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.

This is conjecture based on observing a pattern, but it feels so natural that it inspires some confidence even based on a relatively small sample.

Define the sequence of words $r_i = \textrm{reverse}(w_i)$. Initialise $i = 0$, $s = \textrm{reverse}(W[1..n])$ is the $n$th splitter. While $s$ is non-empty, if $r_i$ is a prefix of $s$ emit $A$, remove $r_i$ from the start of $s$, and increment $i$; otherwise emit $B$, remove $r_{i+1}$ from the start of $s$, and increment $i$ twice.

Worked example: the 26th splitter is $10010010100101001001010010$. It doesn't start with $r_0 = 0$, so we emit $B$ and skip $r_1 = 10$ leaving $010010100101001001010010$. This does start with $r_2 = 010$, so we emit $A$ and reduce $s$ to $010100101001001010010$. This doesn't start with $r_3 = 10010$, so we emit $B$ and skip $r_4 = 01010010$ leaving $1001001010010$. This does start with $r_5 = 1001001010010$, so we emit $A$ and the empty string remains. The Wythoff composite for the 26th splitter is $BABA$.

For practical implementation, it may be noted that $r_i$'s first symbol is $i \bmod 2$ and the lengths, obviously, follow the Fibonacci sequence.