Fibonacci word

Description through a straight line with a slope

1/\varphi

{\ displaystyle 1 / \ varphi}

{\ displaystyle 1 / \ varphi}

or

\varphi -1

{\ displaystyle \ varphi -1}

{\ displaystyle \ varphi -1}

where

\varphi

{\ displaystyle \ varphi}

\ varphi

- golden ratio .

A Fibonacci word is a sequence of binary digits (or characters from any two-letter alphabet ). The Fibonacci word is formed by repeating concatenation in the same way that Fibonacci numbers are formed by repeated additions.

The Fibonacci word is a textbook example of the .

The name “Fibonacci word” is also used to refer to the members of the formal language L , which contains strings of zeros and ones without units adjacent. Any part of a particular Fibonacci word belongs to L , but the language has many other lines. In L, the number of lines of each possible length is the Fibonacci number.

Definition

Let be $S_{0}$ ${\ displaystyle S_ {0}}$ $S_{0}$ equal to "0", and $S_{1}$ ${\ displaystyle S_ {1}}$ $S_{1}$ equal to "01". Now $S_{n}=S_{n-1}S_{n-2}$ ${\ displaystyle S_ {n} = S_ {n-1} S_ {n-2}}$ $S_{n}=S_{n-1}S_{n-2}$ (concatenation of the previous member and the member before it).

The infinite Fibonacci word is the limit $S_{\infty }$ ${\ displaystyle S _ {\ infty}}$ $S_{\infty }$ .

Enumeration of the sequence members from the definition above gives:

$S_{0}$ ${\ displaystyle S_ {0}}$ $S_{0}$ 0

$S_{1}$ ${\ displaystyle S_ {1}}$ $S_{1}$ 01

$S_{2}$ ${\ displaystyle S_ {2}}$ $S_{2}$ 010

$S_{3}$ ${\ displaystyle S_ {3}}$ $S_{3}$ 01001

$S_{4}$ ${\ displaystyle S_ {4}}$ $S_4$ 01001010

$S_{5}$ ${\ displaystyle S_ {5}}$ $S_5$ 0100101001001

...

The first few elements of the infinite Fibonacci word:

0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, ... ( sequence A003849 in OEIS )

Closed expression for specific numbers

The number n of the word is $2+\left\lfloor {{n}\,\varphi }\right\rfloor -\left\lfloor {\left({n+1}\right)\,\varphi }\right\rfloor$ ${\ displaystyle 2+ \ left \ lfloor {{n} \, \ varphi} \ right \ rfloor - \ left \ lfloor {\ left ({n + 1} \ right) \, \ varphi} \ right \ rfloor}$ where $\varphi$ ${\ displaystyle \ varphi}$ - the golden ratio , and $\left\lfloor x\right\rfloor$ ${\ displaystyle \ left \ lfloor x \ right \ rfloor}$ - function "floor" ("floor").

Substitution Rules

Another way to go from S _n to S _{n + 1} is to replace each character 0 in S _{n with a} pair of characters 0, 1 and replace each 1 with 0.

Alternatively, one can imagine generating the entire infinite Fibonacci word using the following process. We start with the character 0, set the cursor on it. At each step, if the cursor points to 0, add 1 and 0 to the end of the word, and if the cursor points to 1, add 0 to the end of the word. In any case, the step ends with moving one position to the right.

A similar infinite word is sometimes called a golden string or a rabbit sequence ; it is formed by a similar endless process, but the replacement rule is different - if the cursor points to 0, add 1, and if it points to 1, add 0, 1. The resulting sequence begins with

0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, ...

However, this sequence differs trivially from the Fibonacci word - zeros are replaced by ones and the whole sequence is shifted by one.

Closed expression for a gold string:

The number n of the word is $\left\lfloor {{n}\,\varphi }\right\rfloor -\left\lfloor {\left({n-1}\right)\,\varphi }\right\rfloor -1$ ${\ displaystyle \ left \ lfloor {{n} \, \ varphi} \ right \ rfloor - \ left \ lfloor {\ left ({n-1} \ right) \, \ varphi} \ right \ rfloor -1}$ where $\varphi$ ${\ displaystyle \ varphi}$ - the golden ratio , and $\left\lfloor x\right\rfloor$ ${\ displaystyle \ left \ lfloor x \ right \ rfloor}$ - function "floor" .

Discussion

The word is associated with a famous sequence of the same name ( Fibonacci sequence ) in the sense that the addition of integers in an inductive definition is replaced by the concatenation of strings. This leads to the fact that the length S _n is equal to F _{n + 2} , ( n + 2) -th Fibonacci number. Also, the number of units in S _n is equal to F _n , and the number of zeros in S _n is equal to F _{n + 1} .

Other properties

The infinite Fibonacci word is not periodic and is not final periodic ^[1] .
The last two digits of the Fibonacci word are either “01” or “10”.
Removing the last two letters of the Fibonacci word or adding the last two letters to the beginning of the addition creates a palindrome . Example: 01 $S_{4}$ ${\ displaystyle S_ {4}}$ = 0101001010 is a palindrome. The palindromic density of the infinite Fibonacci word is 1 / φ, where φ is the golden ratio . This is the largest possible value for non-periodic words ^[2] .
In the infinite Fibonacci word, the ratio (number of digits) / (number of zeros) is equal to φ, as is the ratio of the number of zeros to the number of ones.
The infinite Fibonacci word is a . Take two substrings of the same length somewhere in the Fibonacci word. The difference between their (number of units) never exceeds 1 ^[3] .
Subwords 11 and 000 never occur.
infinite Fibonacci word is n +1 - it contains n +1 different subwords of length n . Example: There are 4 different subwords of length 3: “001”, “010”, “100” and “101”. Being a non-periodic sequence, the word has "minimal complexity", and therefore is the ^[4] with a slope $1/\phi ^{2}$ ${\ displaystyle 1 / \ phi ^ {2}}$ . The infinite Fibonacci word is a formed by the (1,1,1, ....).
The infinite Fibonacci word is recursive. That is, any subword occurs infinitely often.
If a $u$ ${\ displaystyle u}$ is a subword of the infinite Fibonacci word, then the subword is its inverse, denoted $u^{R}$ ${\ displaystyle u ^ {R}}$ .
If a $u$ ${\ displaystyle u}$ is a subword of the infinite Fibonacci word, then the smallest period $u$ ${\ displaystyle u}$ is the Fibonacci number.
The concatenation of two sequences of Fibonacci words is “almost commutative”. $S_{n+1}=S_{n}S_{n-1}$ ${\ displaystyle S_ {n + 1} = S_ {n} S_ {n-1}}$ and $S_{n-1}S_{n}$ ${\ displaystyle S_ {n-1} S_ {n}}$ differ only in the last two letters.
As a result, an infinite Fibonacci number can be described by a sequence of sections of a straight line with an inclination $\phi$ ${\ displaystyle \ phi}$ or $\phi -1$ ${\ displaystyle \ phi -1}$ . See picture above.
The number 0,010010100 ..., whose decimal digits are the digits of the infinite Fibonacci word, is transcendental .
The letters "1" can be found in the positions specified by the sequential values of the upper Withoff sequence (OEIS A001950): $\lfloor n\phi ^{2}\rfloor$ ${\ displaystyle \ lfloor n \ phi ^ {2} \ rfloor}$
The letters "0" can be found in the positions specified by the sequential values of the lower Withoff sequence (OEIS A000201): $\lfloor n\phi \rfloor$ ${\ displaystyle \ lfloor n \ phi \ rfloor}$
Distribution $n=F_{k}$ ${\ displaystyle n = F_ {k}}$ points on a unit circle placed sequentially clockwise at a golden angle ${\frac {2\pi }{\phi ^{2}}}$ ${\ displaystyle {\ frac {2 \ pi} {\ phi ^ {2}}}}$ forms a pattern of two lengths ${\frac {2\pi }{\phi ^{k-1}}},{\frac {2\pi }{\phi ^{k}}}$ ${\ displaystyle {\ frac {2 \ pi} {\ phi ^ {k-1}}}, {\ frac {2 \ pi} {\ phi ^ {k}}}}$ on the unit circle. Although the process of generating the Fibonacci word described above does not correspond directly to the sequential division of segments of a circle, this pattern is $S_{k-1}$ ${\ displaystyle S_ {k-1}}$ if you start from the point closest to the clockwise direction, while 0 corresponds to a long distance, and 1 corresponds to a short distance.
An infinite Fibonacci word can contain a repetition of 3 consecutive identical subwords, but never contains 4 such subwords. for an infinite Fibonacci word is $2+\phi =3,618$ ${\ displaystyle 2+ \ phi = 3,618}$ repetitions ^[5] . This is the smallest index (or critical index) among all the words of Sturm.
The infinite Fibonacci word is often referred to as the for string repetition algorithms.
The infinite Fibonacci word is a , formed from {0,1} * by means of endomorphism 0 → 01, 1 → 0 ^[6] .

Applications

The construction of Fibonacci words is used to model physical systems with a nonperiodic order, such as quasicrystals , and to study the light scattering properties of crystals with Fibonacci layers ^[7] .

Notes

↑ sequence $v=(v_{0},v_{1},\ldots )$ ${\ displaystyle v = (v_ {0}, v_ {1}, \ ldots)}$ called finally periodic with parameters $(T,\tau )$ ${\ displaystyle (T, \ tau)}$ if the condition is satisfied $v_{k+T}=v_{k}$ ${\ displaystyle v_ {k + T} = v_ {k}}$ for $k\geqslant \tau$ ${\ displaystyle k \ geqslant \ tau}$ where $T$ ${\ displaystyle T}$ and $\tau$ ${\ displaystyle \ tau}$ whole $T>0$ ${\ displaystyle T> 0}$ , $\tau >0$ ${\ displaystyle \ tau> 0}$ . Smallest such number $T$ ${\ displaystyle T}$ called the period of the sequence. Sequence called $T$ ${\ displaystyle T}$ -periodic if $\tau =0$ ${\ displaystyle \ tau = 0}$ ( Lipnitsky, Chesalin, 2008 , p. 27).
↑ Adamczewski, Bugeaud, 2010 , p. 443.
↑ Lothaire, 2011 , p. 47.
↑ de Luca (1995) .
↑ Allouche, Shallit, 2003 , p. 37.
↑ Lothaire, 2011 , p. eleven.
↑ Dharma-wardana, MacDonald, Lockwood, Baribeau, Houghton, 1987 .

Literature

Jean-Paul Allouche, Jeffrey Shallit. Automatic Sequences: Theory, Applications, Generalizations. - Cambridge University Press , 2003. - ISBN 978-0-521-82332-6 .
Dharma-wardana MWC, MacDonald AH, Lockwood DJ, Baribeau J.-M., Houghton DC Raman scattering in Fibonacci superlattices // Physical Review Letters . - 1987.- T. 58 . - S. 1761-1765 . - DOI : 10.1103 / physrevlett . 58.1761 .
Lothaire M. Combinatorics on Words. - 2nd. - Cambridge University Press , 1997. - T. 17. - (Encyclopedia of Mathematics and Its Applications). - ISBN 0-521-59924-5 .
Lothaire M. Algebraic Combinatorics on Words. - Cambridge University Press , 2011.- T. 90. - (Encyclopedia of Mathematics and Its Applications). . Reprint of the 2002 hardback.
Aldo de Luca. A division property of the Fibonacci word // Information Processing Letters . - 1995. - T. 54 , no. 6 . - S. 307-312 . - DOI : 10.1016 / 0020-0190 (95) 00067-M .
Mignosi F., Pirillo G. Repetitions in the Fibonacci infinite word // Informatique théorique et application. - 1992. - T. 26 , no. 3 . - S. 199–204 .
Boris Adamczewski, Yann Bugeaud. Chapter 8. Transcendence and diophantine approximation // Combinatorics, automata, and number theory / Valérie Berthé, Michael Rigo. - Cambridge: Cambridge University Press , 2010. - T. 135. - S. 443. - (Encyclopedia of Mathematics and its Applications). - ISBN 978-0-521-51597-9 .
Lipnitsky V. A., Chesalin N. V. Linear codes and code sequences: textbook. Method. Allowance for students fur. Fak. BSU . - Minsk: BSU, 2008.

Links

A detailed and accessible description, on Ron Knott's site
Weisstein, Eric W. Rabbit Sequence on Wolfram MathWorld .
YouTube video

[1] sequence $v=(v_{0},v_{1},\ldots )$ ${\ displaystyle v = (v_ {0}, v_ {1}, \ ldots)}$ called finally periodic with parameters $(T,\tau )$ ${\ displaystyle (T, \ tau)}$ if the condition is satisfied $v_{k+T}=v_{k}$ ${\ displaystyle v_ {k + T} = v_ {k}}$ for $k\geqslant \tau$ ${\ displaystyle k \ geqslant \ tau}$ where $T$ ${\ displaystyle T}$ and $\tau$ ${\ displaystyle \ tau}$ whole $T>0$ ${\ displaystyle T> 0}$ , $\tau >0$ ${\ displaystyle \ tau> 0}$ . Smallest such number $T$ ${\ displaystyle T}$ called the period of the sequence. Sequence called $T$ ${\ displaystyle T}$ -periodic if $\tau =0$ ${\ displaystyle \ tau = 0}$ ( Lipnitsky, Chesalin, 2008 , p. 27).

[_a536b7ea553dc163-2] Adamczewski, Bugeaud, 2010 , p. 443.

[_bc15f7e28f87325c-3] Lothaire, 2011 , p. 47.

[FOOTNOTEde_Luca1995-4] Luca (1995) .

[_dbdbbc4129695982-5] Allouche, Shallit, 2003 , p. 37.

[_bc15fae28f8737b5-6] Lothaire, 2011 , p. eleven.

[_f9fadc5a572c5a1a-7] Dharma-wardana, MacDonald, Lockwood, Baribeau, Houghton, 1987 .