Prefixes of the Fibonacci word that end with a cube

Narad Rampersad

doi:10.5802/crmath.408

Combinatorics

Prefixes of the Fibonacci word that end with a cube

Narad Rampersad ¹

¹ Department of Mathematics and Statistics, University of Winnipeg, 515 Portage Ave., Winnipeg, MB, R3B 2E9, Canada

Comptes Rendus. Mathématique, Volume 361 (2023), pp. 323-330.

Abstract

The Fibonacci word $f = 010010100100101 \dots$ is one of the most well-studied words in the area of combinatorics on words. It is not periodic, but nevertheless contains many highly periodic factors (contiguous subwords). For example, it contains many cubes (i.e., non-empty words of the form $x x x$ ). We study the prefixes of the Fibonacci word that end with a cube. Using the computer prover Walnut, we obtain an exact description of the positions of the Fibonacci word at which a cube ends. This gives a certain measure of how close the Fibonacci word is to being periodic.

Received: 2021-11-29
Revised: 2022-07-13
Accepted: 2022-07-20
Published online: 2023-01-12

DOI: 10.5802/crmath.408

Classification: 68R15

Author's affiliations:

Narad Rampersad ¹

¹ Department of Mathematics and Statistics, University of Winnipeg, 515 Portage Ave., Winnipeg, MB, R3B 2E9, Canada

License:

CC-BY 4.0

Copyrights: The authors retain unrestricted copyrights and publishing rights

@article{CRMATH_2023__361_G1_323_0,
     author = {Narad Rampersad},
     title = {Prefixes of the {Fibonacci} word that end with a cube},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {323--330},
     publisher = {Acad\'emie des sciences, Paris},
     volume = {361},
     year = {2023},
     doi = {10.5802/crmath.408},
     language = {en},
}

TY  - JOUR
AU  - Narad Rampersad
TI  - Prefixes of the Fibonacci word that end with a cube
JO  - Comptes Rendus. Mathématique
PY  - 2023
SP  - 323
EP  - 330
VL  - 361
PB  - Académie des sciences, Paris
DO  - 10.5802/crmath.408
LA  - en
ID  - CRMATH_2023__361_G1_323_0
ER  -

%0 Journal Article
%A Narad Rampersad
%T Prefixes of the Fibonacci word that end with a cube
%J Comptes Rendus. Mathématique
%D 2023
%P 323-330
%V 361
%I Académie des sciences, Paris
%R 10.5802/crmath.408
%G en
%F CRMATH_2023__361_G1_323_0

Narad Rampersad. Prefixes of the Fibonacci word that end with a cube. Comptes Rendus. Mathématique, Volume 361 (2023), pp. 323-330. doi : 10.5802/crmath.408. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.5802/crmath.408/

References
Cited by

[1] Jean-Paul Allouche; Jeffrey Shallit Automatic Sequences: Theory, Applications Generalizations, Cambridge University Press, 2003 | DOI | Zbl

[2] Paweł Gawrychowski; Dalia Krieger; Narad Rampersad; Jeffrey Shallit Finding the growth rate of a regular or context-free language in polynomial time, Developments in Language, Theory. 12^th International Conference, DLT 2008, Kyoto, Japan, September 16–19, 2008. Proceedings (Lecture Notes in Computer Science), Volume 5257, Springer, 2008, pp. 339-358 | MR | Zbl

[3] John E. Hopcroft; Jeffrey D. Ullman Introduction to Automata Theory, Languages and Computation, Addison-Wesley Series in Computer Science, Addison-Wesley Publishing Group, 1979 | Zbl

[4] Dalia Krieger Critical Exponents and Stabilizers of Infinite Words, Ph. D. Thesis, University of Waterloo, Waterloo, Ontario, Canada (2008) (http://uwspace.uwaterloo.ca/handle/10012/3599) | MR

[5] Cornelis G. Lekkerkerker Voorstelling van natuurlijke getallen door een som van getallen van Fibonacci [Representation of natural numbers as a sum of Fibonacci numbers], Simon Stevin, Volume 29 (1952), pp. 190-195 | Zbl

[6] Filippo Mignosi; Giuseppe Pirillo Repetitions in the Fibonacci infinite word, RAIRO, Inform. Théor. Appl., Volume 26 (1992), pp. 199-204 | DOI | Numdam | MR | Zbl

[7] Filippo Mignosi; Antonio Restivo; Sergio Salemi Periodicity and the golden ratio, Theor. Comput. Sci., Volume 204 (1998), pp. 153-167 | DOI | MR | Zbl

[8] Marston Morse; Gustav A. Hedlund Symbolic dynamics, Am. J. Math., Volume 60 (1938), pp. 815-866 | DOI | MR | Zbl

[9] Hamoon Mousavi Automatic theorem proving in Walnut (2021) Documentation (2016–2021) available at https://arxiv.org/abs/1603.06017

[10] Hamoon Mousavi; Luke Schaeffer; Jeffrey Shallit Decision algorithms for Fibonacci-automatic words I: Basic results, RAIRO, Theor. Inform. Appl., Volume 50 (2016) no. 1, pp. 39-66 | DOI | Numdam | MR | Zbl

[11] Alexander Ostrowski Bemerkungen zur Theorie der Diophantischen Approximationen, Abh. Math. Semin. Univ. Hamb., Volume 1 (1922), p. 77-98, 250–251 (reprinted in Collected Mathematical Papers, Vol. 3, pp. 57–80) | DOI | MR | Zbl

[12] Édouard Zeckendorf Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas, Bull. Soc. Roy. Liège, Volume 41 (1972), pp. 179-182 | Zbl

Cited by Sources:

Comments - Policy