login
Fixed point of the mapping 00->0010, 1->011, starting with 00.
5

%I #23 Sep 28 2019 10:01:23

%S 0,0,1,0,0,1,1,0,0,1,0,0,1,1,0,1,1,0,0,1,0,0,1,1,0,0,1,0,0,1,1,0,1,1,

%T 0,0,1,1,0,1,1,0,0,1,0,0,1,1,0,0,1,0,0,1,1,0,1,1,0,0,1,0,0,1,1,0,0,1,

%U 0,0,1,1,0,1,1,0,0,1,1,0,1,1,0,0,1,0

%N Fixed point of the mapping 00->0010, 1->011, starting with 00.

%C From _Michel Dekking_, Sep 27 2019: (Start)

%C This sequence is a morphic sequence, i.e, the letter-to-letter image of a fixed point of a morphism.

%C Proof: We note first that the mapping SR: 00->0010, 10->011, is an algorithmic procedure given by StringReplace in Mathematica. This makes it hard to describe iterates of it. However, in this particular case one can deal with this.

%C There are three types of 0's occurring in (a(n)). The first 0 in a pair 00, which we code by the letter F, the second 0 in a pair 00 which we code by the letter G, and the single 0 occurring between two 1's, coded by G. The 1 at the end of the iterates SR^n, we code by D ('dead'). The other 1's we code by A ('active').

%C So, if we denote this code by psi, then for example,

%C psi(SR(00)) = psi(0010) = FGAD,

%C psi(SR^2(00)) = psi(00100110) = FGAFGAAD.

%C Now consider the morphism sigma on the alphabet {F,G,D,A} given by

%C sigma(F) = FGA, sigma(G) = F, sigma(D) = D, sigma(A) = GAA.

%C Let pi be the inverse of psi: pi(F) = pi(G) = pi(D) = 0, pi(A) = 1.

%C Any word with prefix 00 and without occurrences of 000, is a concatenation of the three words u=00, v=1 and w=101. The SR-procedure acts context-free on such concatenations. One has

%C SR(u) = 0010, SR(v) = 011, SR(w) = 0110011.

%C The psi-images are

%C psi(u) = FG, psi(v) = A, psi(w) = AGA.

%C The sigma-images of these are

%C sigma(FG) = FGAF, sigma(A) = GAA, sigma(AGA) = GAAFGAA.

%C The pi-images of these are

%C pi sigma psi(u) = 0010, pi sigma psi(v) = 011, pi sigma psi(w) = 0110011.

%C We see that pi sigma psi acts exactly in the same way as SR.

%C It follows that (a(n)) = pi(x), where x = FGAFGAA... is the unique fixed point of sigma. QED

%C (End)

%C From _Michel Dekking_, Sep 27 2019: (Start)

%C Now that we know that this sequence is a morphic sequence, we may prove Kimberling's conjecture that the lengths of the words SR^n(00) are given by A182780.

%C Here b:=A182780 has b(0) = 2, b(1) = 4, and satisfies the linear recurrence b(n) = 3*b(n-1) - b(n-2) - b(n-3) for n>2.

%C The number of letters (F's, G's, D's and A's) in the word psi(SR^n(00)) is equal to the vector/matrix/vector product

%C (1,1,1,1) M^n (1,0,1,0)^T,

%C where (1,0,1,0)^T is the transpose of (1,0,1,0), and M is the incidence matrix of the morphism sigma, i.e., M equals

%C |1 1 0 0|

%C |1 0 0 1|

%C |0 0 1 0|

%C |1 0 0 2|.

%C The characteristic polynomial of M is equal to

%C chi(u) = u^4 - 4u^3 + 4u^2 - 1 = (u^3 - 3u^2 + u + 1)(u - 1).

%C Thus the conjecture is proved by an application of the Cayley-Hamilton theorem: M^3 = 3M^2 - M - Id.

%C (End)

%C From _Michel Dekking_, Sep 28 2019: (Start)

%C The application of Cayley-Hamilton is more subtle than suggested above. In fact chi(u) has a second factor u-1: chi(u) = (u^2-2u-1)(u-1)^2, but b=A182780 does not satisfy the Pell recurrence a(n) = 2*a(n-1) + a(n-2).

%C Removing the letter D from {F,G,D,A} gives a morphism tau defined by

%C tau(F) = FGA, tau(G) = F, tau(A) = GAA.

%C The iterates tau^n(F) are equal to the iterates sigma^n(FD), with the suffix D removed. So

%C |SR^n(00)|= |sigma^n(FD)|=|tau^n(F)|+1,

%C where |.| denotes length.

%C The characteristic polynomial of the incidence matrix of tau is equal to u^3-3u^2+u+1.

%C So, by the Cayley-Hamilton theorem, the sequence

%C (|tau^n(F)|) = 1,3,7,17,41,99,... = A078057=:c

%C satisfies the recurrence c(n) = 3c(n-1)-c(n-2)-c(n-3). This implies that the sequence (|SR^n(00)|) = (c(n)+1) satisfies the recurrence

%C b(n) = 3b(n-1) - b(n-2) - b(n-3). QED

%C (End)

%H Clark Kimberling, <a href="/A288213/b288213.txt">Table of n, a(n) for n = 1..10000</a>

%F a(n) = A001953(n-1) mod 2 (conjectured). - _Jon Maiga_, Sep 27 2019

%e Iterates, starting with 00:

%e 00

%e 0010

%e 00100110

%e 001001100100110110

%e 001001100100110110010011001001101100110110

%t s = {0, 0}; w[0] = StringJoin[Map[ToString, s]];

%t w[n_] := StringReplace[w[n - 1], {"00" -> "0010", "1" -> "011"}]

%t Table[w[n], {n, 0, 8}]

%t st = ToCharacterCode[w[11]] - 48 (* A288213 *)

%t Flatten[Position[st, 0]] (* A288214 *)

%t Flatten[Position[st, 1]] (* A288215 *)

%t Table[StringLength[w[n]], {n, 1, 35}] (* A182780 conjectured *)

%Y Cf. A001953, A288214, A288215, A182780.

%K nonn,easy

%O 1

%A _Clark Kimberling_, Jun 07 2017