no. G1
Combinatoire
Prefixes of the Fibonacci word that end with a cube
Rampersad, Narad1
1 Department of Mathematics and Statistics, University of Winnipeg, 515 Portage Ave., Winnipeg, MB, R3B 2E9, Canada
Comptes Rendus. Mathématique, Tome 361 (2023) no. G1, pp. 323-330

The Fibonacci word f=010010100100101⋯ 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 xxx). 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.

Reçu le :
Révisé le :
Accepté le :
Publié le :
DOI : 10.5802/crmath.408
Classification : 68R15

Rampersad, Narad 1

1 Department of Mathematics and Statistics, University of Winnipeg, 515 Portage Ave., Winnipeg, MB, R3B 2E9, Canada
Licence : CC-BY 4.0
Droits d'auteur : Les auteurs conservent leurs droits 
@article{CRMATH_2023__361_G1_323_0,
     author = {Rampersad, Narad},
     title = {Prefixes of the {Fibonacci} word that end with a cube},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {323--330},
     year = {2023},
     publisher = {Acad\'emie des sciences, Paris},
     volume = {361},
     number = {G1},
     doi = {10.5802/crmath.408},
     language = {en},
     url = {https://www.numdam.org/articles/10.5802/crmath.408/}
}
TY  - JOUR
AU  - Rampersad, Narad
TI  - Prefixes of the Fibonacci word that end with a cube
JO  - Comptes Rendus. Mathématique
PY  - 2023
SP  - 323
EP  - 330
VL  - 361
IS  - G1
PB  - Académie des sciences, Paris
UR  - https://www.numdam.org/articles/10.5802/crmath.408/
DO  - 10.5802/crmath.408
LA  - en
ID  - CRMATH_2023__361_G1_323_0
ER  - 
%0 Journal Article
%A Rampersad, Narad
%T Prefixes of the Fibonacci word that end with a cube
%J Comptes Rendus. Mathématique
%D 2023
%P 323-330
%V 361
%N G1
%I Académie des sciences, Paris
%U https://www.numdam.org/articles/10.5802/crmath.408/
%R 10.5802/crmath.408
%G en
%F CRMATH_2023__361_G1_323_0
Rampersad, Narad. Prefixes of the Fibonacci word that end with a cube. Comptes Rendus. Mathématique, Tome 361 (2023) no. G1, pp. 323-330. doi: 10.5802/crmath.408

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

[2] Gawrychowski, Paweł; Krieger, Dalia; Rampersad, Narad; Shallit, Jeffrey Finding the growth rate of a regular or context-free language in polynomial time, Developments in Language, Theory. 12th 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] Hopcroft, John E.; Ullman, Jeffrey D. Introduction to Automata Theory, Languages and Computation, Addison-Wesley Series in Computer Science, Addison-Wesley Publishing Group, 1979 | Zbl

[4] Krieger, Dalia 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] Lekkerkerker, Cornelis G. 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] Mignosi, Filippo; Pirillo, Giuseppe Repetitions in the Fibonacci infinite word, RAIRO, Inform. Théor. Appl., Volume 26 (1992), pp. 199-204 | DOI | MR | Numdam | Zbl

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

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

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

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

[11] Ostrowski, Alexander 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] Zeckendorf, Édouard 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

Cité par Sources :